vlaste

Tecnoclassico

User info:

Registered: Jun 2004
Posts: 472 (0.06 al dì)
Location: Estrema periferia
Corso: Informatica
Anno: terzo... bis
Time Online: 3 Days, 5:56:07: [...]
Status: Offline

Post actions:

Nella seconda parte ha svolto un altro esercizio.
ISTANZA: -T = <V,E> albero ordinato
-per ogni v appartenente a V, L(v) è la lista ordinata dei
figli di v
SOLUZIONE: per ogni v appartenente a V, A[v] = altezza di v in T.

Praticamente dato un albero, la procedura deve creare un vettore di interi, ciascun elemento del quale rappresenta l'altezza del nodo corrispondente. Per il nodo m, A[m] è la sua altezza.
Ha scritto l'algoritmo in maniera ricorsiva e in maniera iterativa e ne ha fatto una brevissima analisi secondo il criterio uniforme...

fdecollibus

User info:

Registered: Sep 2003
Posts: 261 (0.03 al dì)
Location: Milano
Corso: Ticom
Anno: 2°
Time Online: 11 Days, 17:06:51 [...]
Status: Offline

Post actions:

ATTENZIONE!

Giovedi 11/9/2004 le lezioni di Goldwurm e Aguzzoli non si terrano per una riunione sul decreto Moratti.

fdecollibus

(il vice-Polsy)

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

DIARIO DEL CORSO 16-11-2004
ALGORITMI DI ORDINAMENTO
definizione di relazione d'ordine e di insieme ordinato
relazione d'ordine lessicografica (definizione e esempi)
relazione d'ordine di rango (o militare)
RISOLUZIONE DI PROBLEMI DI ORDINAMENTO
-algoritmo di inserimento (procedura, esempio di esecuzione e calcolo del numero di confronti al variare dell'input)
-mergesort (procedura e esempio di esecuzione)

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

DIARIO DEL CORSO 18-11-2004
ancora mergesort:
piccola modifica alla procedura merge dell'altra volta
simulazione di esecuzione di mergesort sul vettore (7 5 10 6 9)
ANALISI DI MERGESORT
spazio richiesto (criterio uniforme)
tempo richiesto (inteso come n° di confronti effettuati) secondo il criterio uniforme

AVVISO
il prossimo compitino sarà probabilmente il 14 gennaio
argomenti del compito: algoritmi di ordinamento, divide et impera, greedy
probabile esercizio: simulare l'esecuzione di un algoritmo su un determinato input tipo la simulazione dello stack durante l'esecuzione del mergesort (in maniera molto generale, giusto evidenziare quali sono i confronti effettuati)

caste

.amico.

User info:

Registered: Nov 2004
Posts: 28 (0.00 al dì)
Location:
Corso: Informatica
Anno: 2
Time Online: 23:56:34 [...]
Status: Offline

Post actions:

Diario del corso (Aguzzoli)

• operatori aritmetici
  
• operatori di incremento e decremento
  
• operatori di assegnamento
  
• operatori di assegnamento combinati
  
• variabili e lvalue
  

vlaste

Tecnoclassico

User info:

Registered: Jun 2004
Posts: 472 (0.06 al dì)
Location: Estrema periferia
Corso: Informatica
Anno: terzo... bis
Time Online: 3 Days, 5:56:07: [...]
Status: Offline

Post actions:

AVVISO

Il prof. ha messo fuori i voti del primo compitino:

Eccoli qui

tata1283

dottoressa!!!

User info:

Registered: Oct 2002
Posts: 495 (0.06 al dì)
Location: Albino (BG)
Corso: Informatica
Anno: 3
Time Online: 5 Days, 17:07:20 [...]
Status: Offline

Post actions:

Qualcuno mi sa spiegare il criterio dei voti?
Grazie

fdecollibus

User info:

Registered: Sep 2003
Posts: 261 (0.03 al dì)
Location: Milano
Corso: Ticom
Anno: 2°
Time Online: 11 Days, 17:06:51 [...]
Status: Offline

Post actions:

Credo che dovresti chiederlo direttamente al professore....

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

in ritardissimo...
DIARIO DEL CORSO 19-11-2004
correzione di alcuni esercizi del compitino
analisi del n° di confronti e del tempo di calcolo (uniforme) richiesto da mergesort

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

DIARIO DEL CORSO 23-11-2004
metodo "DIVIDE ET IMPERA"
-idea intuitiva
-algoritmo generico

casi particolari di algoritmi divide et impera
-mergesort
-ricerca binaria

altri algoritmi divide et impera famosi (solo nominati, senza spiegazione)
-algoritmo di Strassen per il calcolo del prodotto di matrici
-algoritmo per il prodotto di interi
-algoritmo per il calcolo della trasformata di Fourier

analisi dei tempi di calcolo dell'algoritmo generico divide et impera

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

DIARIO DEL CORSO 25/11/2004
algoritmo x trovare il massimo e il minimo tra gli elementi di un vettore:

Algoritmo semplice

• procedura
  
• spazio di memoria richiesto
  
• tempo di calcolo
  
• numero dei confronti effettuati
  

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

DIARIO DEL CORSO 26-11-2004
Algoritmo generale x il prodotto di matrici
- procedura
- tempo di calcolo
Algoritmo di Strassen
- procedura
- tempo di calcolo
Algoritmo x il prodotto di interi
- procedura
- calcolo del n° di operazioni binarie richieste dall'algoritmo al variare dell'input

esercizi x casa
sezione 6.4.1 esercizi 1, 2, 4

AVVISO
martedì 30/11 non ci sarà lezione di algoritmi
venerdì 3/12 al posto della lezione di teoria ci sarà laboratorio con aguzzoli (sempre in G21)

Motomax

User info:

Registered: Nov 2004
Posts: 25 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: 2
Time Online: 9:02:47 [...]
Status: Offline

Post actions:

Ciao a tutti.
ma allora lamodalità dell'esame sarà:
progetto e compito scritto e orale?? se non ho passato il primo compitino!!

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

Originally posted by Motomax
Ciao a tutti.
ma allora lamodalità dell'esame sarà:
progetto e compito scritto e orale?? se non ho passato il primo compitino!!

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

DIARIO DEL CORSO 2-12-2004
algoritmo per calcolare il valore 7^n (mod k)
- procedura tradizionale
- calcolo tempo/spazio secondo il criterio uniforme/logaritmico
- procedura divide et impera
- calcolo tempo/spazio secondo il criterio uniforme/logaritmico

esercizi x casa
es. 3 tema 1-4-03
es. 2 tema 4-2-03
es. 3 tema 11-12-03 (temi 1 e 2)
es. 2 tema 5-12-01

altro esercizio:
ISTANZA: n , a1 , a2 , ... , an (naturali >0)
|ai|=m     per ogni i=1,...,n
SOLUZIONE: p=a1*a2*...*an

a) descrivere un algoritmo iterativo x risolvere il problema
fare l'analisi dei tempi di calcolo e dello spazio di memoria richiesti secondo i 2 criteri (in funzione di n e m)

b) descrivere un algoritmo divide et impera x lo stesso problema

c) valutare tempo e spazio secondo i 2 criteri
(NOTA: nel calcolo del tempo logaritmico basta dare una valutazione O "o grande")