PARTE PRIMA: Algoritmi e Problemi

5/10/04:

Definizione di algoritmo. Input, output, correttezza, istanza, programma, pseudocodice. Algoritmo di ordinamento INSERTION SORT. Analisi di correttezza ed esempio.

Approfondimento: Algoritmo INSERTION SORT modificato per l'ordinamento non crescente e con visita invertita della sequenza.
Dispense: 1, 2, 3.
 

6/10/04:

Analisi di un algoritmo. Modello di calcolo RAM, misure di complessità statiche e dinamiche, dimensione dell'input. Analisi della complessità temporale dell'algoritmo INSERTION SORT. Caso migliore, caso peggiore, caso medio. Definizione di complessità asintotica. Notazioni $\Theta, O, \Omega$.

Approfondimento: Algoritmo MAX-ELEMENTO per la ricerca dell'elemento massimo di un insieme dato ed analisi della complessità temporale.
Dispense: 4, 5, 6, 7, 8, 9.
 

7/10/04:

Algoritmo SEARCH-ELEMENT per la ricerca di un elemento un insieme dato ed analisi della complessità temporale. Notazioni $o, \omega$. Proprietà delle classi di complessità asintotica.

Algoritmo SELECTION SORT: Caso migliore e caso peggiore. Confronto con l'INSERTION SORT.
Approfondimento: Richiami sulla crescita asintotica relativa di alcune funzioni fondamentali. Classificazione di 25 diverse funzioni in ordine Non decrescente utilizzando le notazioni asintotiche $\Theta$ ed $o$.
Dispense: 9bis, 10, 11, 11bis, 12. 13, 14,