.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi - Goldwurm] Diario del Corso 2004/05 (http://www.dsy.it/forum/showthread.php?threadid=13819)

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...

ATTENZIONE!

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

fdecollibus

(il vice-Polsy)

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)

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)

Diario del corso (Aguzzoli)

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

• dichiarazioni di variabili
  
• inizializzazione e assegnamento
  
• il tipo char
  
• il tipo int
  
• i tipi short, long e unsigned
  
• i tipi reali float, double, long double
  
• l'operatore sizeof
  
• conversione e cast
  
• conversioni aritmetiche
  
• cast
  

Voti primo compitino

AVVISO

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

Eccoli qui

Qualcuno mi sa spiegare il criterio dei voti?
Grazie

Credo che dovresti chiederlo direttamente al professore....

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

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

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
  

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

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)

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

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!!

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")