Corso di
Fondamenti di Informatica II
Corso di Laurea in Ingegneria Informatica (canale didattico di Ingegneria delle Reti e dei Servizi Informatici), Facolta' di Ingegneria, Universita' degli Studi di Roma "La Sapienza" - Polo di Rieti, a.a. 2007/2008.
Testi di riferimento:
-
"Algoritmi e strutture dati" - Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano; McGraw-Hill, 2004.
-
"Progetto di algoritmi e strutture dati in Java" - Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano; McGraw-Hill, 2007.
Materiale didattico:
Esercitazioni:
Programma:
-
Introduzione agli algoritmi:
Definizione informale di algoritmo; correttezza ed efficienza; pseudocodice.
-
Modelli di calcolo e metodologie di analisi:
Macchina di Turing, macchina a registri (RAM); notazione asintotica, concetto di delimitazione inferiore e superiore (lower bound ed upper bound); analisi di un algoritmo nel caso peggiore, migliore e medio; ricerca sequenziale e ricerca binaria; analisi di algoritmi ricorsivi, equazioni di ricorrenza, metodo dell'iterazione, metodo della sostituzione, teorema fondamentale delle ricorrenze; cenni alla tecnica algoritmica divide et impera.
-
Strutture dati elementari:
Definizione di tipo astratto di dato e di struttura dati; rappresentazioni indicizzate e collegate; rappresentazioni di liste, pile, code, alberi; realizzazioni del tipo di dato Dizionario; visite di alberi in profondita' (ricorsiva ed iterativa) ed in ampiezza.
-
Algoritmi di ordinamento:
Lower bound per il problema dell'ordinamento nel modello basato su confronti; ordinamenti quadratici: SelectionSort, InsertionSort, BubbleSort; la struttura dati Heap; ordinamenti ottimi: HeapSort, MergeSort; QuickSort; ordinamenti lineari: IntegerSort.
-
Alberi di ricerca:
Alberi binari di ricerca (BST): definizione, operazioni (search, insert, max, pred, delete); Alberi AVL: definizione, operazioni, ribilanciamento tramite rotazioni.
-
Tavole hash:
Tavole ad accesso diretto; tavole hash; definizione di funzioni hash: uniformita' semplice, metodo della divisione; risoluzione delle collisioni: liste di collisione, indirizzamento aperto (scansione lineare, hashing doppio, cancellazione di chiavi, costo di scansione).
-
Code con priorita':
Definizione del tipo astratto di dato CodaPriorita; realizzazione mediante d-heap; cenni alle realizzazioni tramite heap binomiali e heap di Fibonacci.
-
Union-find:
Approcci elementari: QuickFind, QuickUnion; euristiche di bilanciamento nell'operazione Union: bilanciamento per algoritmi di tipo QuickFind, bilanciamento per algoritmi di tipo QuickUnion (union by rank, union by size). Cenni alle migliori prestazioni asintotiche otttenibili tramite euristiche di compressione nell'operazione Find.
-
Grafi e visite di grafi:
Definizioni preliminari; rappresentazioni di grafi orientati e non orientati: lista di archi, liste di adiacenza, liste di incidenza, matrice di adiacenza, matrice di incidenza; visite di grafi (orientati e non orientati): visita in ampiezza, visita in profondita'; prestazioni degli algoritmi di visita in funzione della rappresentazione del grafo di input; componenti connesse di un grafo non orientato; componenti fortemente connesse di un grafo orientato.
-
Minimo albero ricoprente:
Definizione e proprieta' dei minimi alberi ricoprenti; tecnica algoritmica golosa (greedy); algoritmo di Kruskal: descrizione, implementazione mediante union-find, analisi; algoritmo di Prim: descrizione, implementazione mediante code con priorita', analisi; algoritmo di Boruvka, descrizione, analisi.
-
Cammini minimi:
Cammini minimi in un grafo: definizione, proprieta' di sottostruttura ottima; cammini minimi in grafi con cicli; distanza fra vertici in un grafo, disuguaglianza triangolare, condizione di Bellman; costruire cammini minimi a partire da distanze; esistenza dell'albero dei cammini minimi; tecnica del rilassamento; algoritmo di Bellman e Ford: descrizione, analisi; definizione di ordinamento topologico; variante dell'algoritmo di Bellman e Ford per grafi aciclici; algoritmo di Dijkstra: descrizione, implementazione mediante code con priorita', analisi.
Testi d'esame: