Docente
|
Caminiti Saverio
(programma)
INTRODUZIONE Algoritmo: etimologia della parola e suo significato. Precisione, finitezza ed eseguibilità di un algoritmo. Studio di algoritmi: progetto, validazione e analisi. Primi esempi di algoritmi: calcolo del massimo, calcolo del minimo, calcolo delle somme prefisse. Introduzione all' efficienza computazionale. Confronto fra funzioni tipiche del calcolo dell'efficienza al crescere di n. Esempi di diversi approcci allo stesso problema: Algoritmo di Euclide per la ricerca del MCD. Somma dei primi n numeri interi.
COMPLESSITA' COMPUTAZIONALE Analisi della complessità computazione di un algoritmo: approccio sperimentale e teorico. Definizione di tempo di esecuzione: caso migliore e caso peggiore. Efficienza asintotica degli algoritmi: limite asintotico superiore, inferiore e stretto: notazione O grande, notazione Omega, notazione Teta. Algebra della notazione asintotica. Proprietà delle operazioni in notazione asintotica. Un polinomio di grado m è un Teta(n alla m) (dimostrazione). 2 algoritmi per la valutazione di un polinomio. Calcolo del costo computazione di un algoritmo: conteggio delle iterazioni in Teta (n) e Teta(nlogn). Ridurre la costante moltiplicativa: calcolo sia del massimo che del minimo in un vettore. Ricerca iterativa in un vettore: ricerca sequenziale, ricerca dicotomica.
ALGORITMI DI ORDINAMENTO: Algoritmi di ordinamento quadratici: ordinamento per inserzione, per selezione, a bolle. Validazione per induzione (dimostrazione) e calcolo della complessità dell'algoritmo di ordinamento per inserzione. Calcolo della complessità dell'algoritmo di ordinamento per selezione. Algoritmo di ordinamento a bolle: come utilizzare una bandiera per migliorare la complessità. Introduzione al concetto di albero: alberi radicati, alberi binari ed m-ari, alberi di decisione. Computo del livello e dell'altezza di un albero binario. Conteggio del numero di nodi e foglie in un albero binario. Teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti e scambi (dimostrazione). Algoritmo di fusione di due vettori ordinati e di due sottovettori ordinati adiacenti. Merge-sort iterativo: calcolo della complessità computazione dell'algoritmo. La struttura dati Heap e sua rappresentazione vettoriale. Algoritmi per "salire" e "scendere" su un Heap. Algoritmo per la creazione di un Heap; dimostrazione della linearità della creazione di un Heap. Algoritmi per aggiungere e cancellare elementi in un Heap. Algoritmo Heap-sort. Calcolo della complessità computazione dello Heap-sort iterativo. 2 algoritmi per partizionare un vettore; come scegliere un pivot. Ordinare in tempo lineare: counting sort. Proprietà degli algoritmi di odinamento: sensibilità all'input, stabilità e capacità di operare in loco.
ALGORITMI RICORSIVI: Ricorsione e Iterazione. Funzioni matematiche ricorsive.calcolo del fattoriale. Analisi di algoritmi ricorsivi. Equazioni di ricorrenza del calcolo del fattoriale e della ricerca binaria. Soluzione di una equazione di ricorrenza: metodo iterativo; metodo di sostituzione; metodo dell'albero di ricorsione. Enunciato del Teorema Master. Versione ricorsiva delle ricerche sequenziale e dicotomica; risoluzione delle relative equazioni di ricorrenza. Versione ricorsiva di algoritmi di ordinamento per inserzione e selezione; risoluzione delle relative equazioni di ricorrenza. Versione ricorsiva dell' algoritmo Merge-sort e dell'algoritmo Heapsort; risoluzione delle relative equazioni di ricorrenza. Confronto di complessità computazionale fra la versione iterativa e la versione ricorsiva dell'algoritmo per il calcolo dei numeri di Fibonacci. Algoritmo Quicksort. Analisi del Quicksort nel caso di partizionamento migliore e partizionamento peggiore. Dimostrazione della complessità dell'algoritmo Quicksort nel caso medio.
STRUTTURE DATI ELEMENTARI ED ALBERI: Organizzazione logica dell'informazione: strutture dati astratte. Implementazione delle strutture dati astratte: strutture dati concrete. Pile, code, code di priorità e alberi. Implementazione con strutture ad accesso diretto e ad accesso sequenziale. Computo della complessità di operazioni di interrogazione e manipolazione su diverse strutture dati. Rappresentazioni in memoria di alberi binari. Visite di alberi binari: preordine, postordine, inordine. Calcolo dell'equazione di ricorrenza relativa agli algoritmi ricorsivi di visita.
DIZIONARI: La struttura dati Dizionario. Implementazioni banali: vettori ordinati e liste collegate. Alberi binari di ricerca (ABR). Ricerca iterativa e ricorsiva su un ABR. Inserimento e cancellazione su un ABR. Calcolo del minimo e del massimo in un ABR. Calcolo del predecessore e del successore in un ABR. Bilanciamento degli ABR: fattori di bilanciamento e rotazioni. Alberi AVL: rotazioni L(R) e RL(LR); esempi di alberi AVL. Gli Alberi di Fibonacci. L'altezza di un albero AVL è logaritmica: dimostrazione. Inserimento e ri-bilanciamento in un albero AVL. Cancellazione e ri-bilanciamento in un albero AVL. Confronto dell'efficienza fra tutte le strutture dati studiate.
[DFI] Demetrescu, Finocchi, Italiano: Algoritmi e strutture dati, Mc Graw Hill.
[CLRS] Cormen, Leiserson, Rivest, Stein: Introduzione agli algoritmi e strutture dati, Mc Graw Hill.
[CLR] Cormen, Leiserson, Rivest: Introduzione agli algoritmi (vecchia edizione in tre volumi), vol. 1, Jackson Libri.
|