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, 2014
(3a edizione).
RICEVIMENTO
MARTEDI, ore 11 – 13
MODALITA' D'ESAME
Prova
scritta
con discussione orale dell'elaborato scritto
Laurea Magistrale in "Informatica" (primo anno, primo semestre, 6 crediti)
Corso Integrato (C.I.) con Intelligenza Artificiale (primo anno, secondo semestre, 6 crediti); il voto del C. I. Di 12 CFU e' unico ed e' dato dalla media dei voti di Algoritmi Paralleli e di Intelligenza Artificiale
PROGRAMMA
Algoritmi paralleli per reti a grado limitato. Sistemi sincroni con o senza memoria condivisa. Modello EREW-PRAM. Somme prefisse e pointer jumping. Tesi della computazione parallela. La classe NC e problemi Log-spazio-completi. 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. Integrazione su grandissima scala (VLSI). Modello a griglia e layout di circuiti VLSI. Circuiti VLSI per ordinamento e moltiplicazione di matrici.
Algoritmi concorrenti e distribuiti. Sistemi asincroni con o senza memoria condivisa. Concorrenza, sezioni critiche, mutua esclusione, primitive di sincronizzazione, stallo. Algoritmi concorrenti per ordinamento, cammini minimi, branch&bound. 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. Cenni alle reti wireless.
LIBRO DI TESTO MODULO I
A.A. BERTOSSI, Algoritmi Paralleli,
Pitagora, Bologna, 2009.
RICEVIMENTO
MARTEDI, ore 11 – 13
MODALITA' D'ESAME
Prova
scritta con discussione orale dell'elaborato scritto