Laurea
in
"Informatica" (primo anno, secondo semestre, 12 crediti)
PROGRAMMA
Strutture di dati. Dati, tipi di dato e strutture di dati. Specifica e realizzazione. Vettori, record e matrici. Liste, pile e code. Pile e procedure ricorsive. Alberi. Visite: anticipata, simmetrica e differita. Insiemi. Dizionari. Ricerca binaria e interpolazione. Tabelle hash. Code con priorita'. Heap. Heapsort. Alberi bilanciati di ricerca. Alberi 2-3 e B-alberi binari. MFSET (unione di insiemi disgiunti). Grafi orientati e non orientati. Visite: Depth-First-Search (DFS) e Breadth-First-Search (BFS). Alberi di copertura DFS.
Progettazione e analisi di algoritmi. Le nozioni di problema computazionale, funzione, algoritmo e linguaggio. Complessità computazionale. Ordini di grandezza. Equazioni di ricorrenza. Risoluzione di equazioni di ricorrenza lineari di ordine costate e con partizione bilanciata. Limitazioni inferiori: dimensione dei dati, eventi contabili, oracoli e alberi di decisione. Problemi decisionali, di ricerca, e di ottimizzazione. Caratterizzazione matematica della soluzione. Tecniche di progettazione. Divide-et-impera: algoritmi di ORDINAMENTO (Mergesort e Quicksort), MOLTIPLICAZIONE DI MATRICI (algoritmo di Strassen). Backtrack: algoritmo di Graham per INVILUPPO CONVESSO e algoritmo di Knuth-Morris-Pratt per STRING-MATCHING. Greedy: algoritmo di Kruskal per ALBERO DI COPERTURA MINIMO. Programmazione dinamica: algoritmo per lo string matching approssimato e algoritmo di Floyd per CAMMINI MINIMI. Ricerca locale: algoritmi Insertionsort e Shellsort.
Complessita'. Non determinismo ed enumerazione. Le istruzioni choice, success e failure. Certificati polinomiali. Le classi P ed NP. Riducibilità polinomiale. Teorema di Cook-Levin. NP-completezza dei problemi: DOMINO LIMITATO, CRICCA, SODDISFATTIBILITA', PROGRAMMAZIONE LINEARE 0/1, COMMESSO VIAGGIATORE, PARTIZIONE, COLORAZIONE DI GRAFI. Gerarchia di complessità. Algoritmi pseudo-polinomiali: SOMMA DI SOTTOINSIEME e ZAINO. NP-completezza forte. 3-PARTIZIONE. Algoritmi di approssimazione assoluta: COMMESSO VIAGGIATORE TRIANGOLARE e SCHEDULING. Algoritmo di approssimazione per SOMMA DI SOTTOINSIEME. Algoritmi branch-&-bound: COMMESSO VIAGGIATORE. Euristiche: greedy e ricerca locale per COMMESSO VIAGGIATORE.
LIBRO DI TESTO
A.A. BERTOSSI & A. MONTRESOR,
Algoritmi e Strutture di Dati, Citta'Studi Edizioni, Torino, 2010.
RICEVIMENTO
MARTEDI, ore 10 - 12
MODALITA' D'ESAME
Prova
scritta
con discussione orale dell'elaborato scritto
Laurea Magistrale in "Informatica" (secondo anno, primo semestre, 6 crediti)
PROGRAMMA
Algoritmi paralleli per reti a grado limitato. Sistemi sincroni con o senza memoria condivisa. Modello PRAM. Tesi della computazione parallela. Reti di interconnessione: mesh, ipercubo, shuffle, butterfly, CCC. Sommatoria e somme prefisse su mesh, shuffle, ipercubo. Mergesort bitonico e algoritmo di Batcher. Moltiplicazione di matrici su mesh e ipercubo. Trasformata di Fourier su butterfly e ipercubo.
Algoritmi paralleli VLSI. Integrazione su larghissima scala (VLSI). Area e tempo di un circuito VLSI. Il modello a griglia. Layout di reti a grado limitato. Algoritmo di Preparata-Vuillemin per moltiplicazione di matrici. Griglie riconfigurabili. Ordinamento: algoritmo Columnsort di Leighton.
Algoritmi concorrenti e distribuiti. Sistemi asincroni con o senza memoria condivisa. Concorrenza, sezioni critiche, mutua esclusione, primitive di sincronizzazione, stallo. Reti di calcolatori. Algoritmi distribuiti e scambio di messaggi. Topologie di reti: anello, stella, albero, grafo, grafo completo. Algoritmi distribuiti per la mutua esclusione in un grafo completo e per l'elezione del leader in un anello. Algoritmo di Gallager-Humblet-Spira per il minimo albero di copertura. Reti wireless.
LIBRO DI TESTO
A.A. BERTOSSI, Algoritmi Paralleli,
Pitagora, Bologna, 2009.
RICEVIMENTO
MARTEDI, ore 10 - 12
MODALITA' D'ESAME
Prova
scritta
con discussione orale dell'elaborato scritto