PARTE 1: Algoritmi e Strutture Dati 1. Ricorsione Lineare, di coda. Binaria. Multipla. Esempi. 2. Algoritmi avanzati di ordinamento 3. Strutture dati Code di priorità e heap. Mappe e dizionari. Tavole hash. Mappe e dizionari ordinati. Alberi binari di ricerca e tecniche di bilanciamento 4. Algoritmi su grafi diretti e indiretti Il tipo di dato astratto grafo. rappresentazione dei grafi in memoria. Visite DFS e BFS e loro applicazioni. Cammini minimi (s-t, SSSP, APSP). Alberi ricoprenti minimi (e Union Find). Chiusura transitiva. D-DFS: topological sort, componenti fortemente connesse 5. Algoritmi su stringhe Pattern matching, compressione e algoritmo di Huffman. DNA e allineamento di sequenze 6. Randomizzazione Quicksort e Quickselect. Test di primalità randomizzato. PARTE 2: Modelli e linguaggi 1. Modello analisi algoritmi a costi uniformi. Delimitazioni inferiori e superiori alla complessità di algoritmi e problemi. 2. Macchine di Turing A un nastro, multinastro, non deterministiche, macchina universale 3. Calcolabilità Decidibilità, indecidibilità. Halting problem; riduzioni ed altri problemi indecidibili. Equivalenza di modelli di calcolo e la tesi di Church-Turing. 4. Complessità Classi P, NP. Riduzioni polinomiali e NP-completezza; esempi di problemi NP-completi. Oltre NP. Tecniche algoritmiche per problemi intrattabili. 5. Tecniche algoritmiche di base Divide et impera, Algoritmi greedy, Programmazione dinamica. Esempi. 6. Linguaggi Grammatiche, la gerarchia di Chomsky. Grammatiche e linguaggi regolari e context-free. Alberi di derivazione sintattica. Analisi lessicale. Tecniche per l'analisi sintattica. Generatori di parser. Attività di laboratorio richiedono di programmare soluzioni per esercizi relativi ad una selezione degli argomenti precedenti.

Parte I Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. Algoritmi e strutture dati in Java. Apogeo Education - Maggioli Editore. 2015. http://www.apogeoeducation.com/9788891613394-algoritmi-e-strutture-dati-in-java.html Parte II Dispensa Pilu Crescenzi. "Dispense di Informatica Teorica". https://www.pilucrescenzi.it/wp/books/dispense-di-informatica-teorica/ Materiale integrativo distribuito dal docente

PARTE 1: Algoritmi e Strutture Dati 1. Ricorsione 2. Introduzione e modello a costi uniformi (limiti) 2.1. Modelli di costo degli algoritmi: modello a costi uniformi 2.2. Analisi del caso peggiore e analisi asintotica 3. Algoritmi avanzati di ordinamento 3.1. Introduzione della tecnica divide-and-conquer 3.2. Algoritmi Merge-Sort e Quick-Sort 3.3. Limiti inferiori al costo dell'ordinamento 3.4. Algoritmi lineari di ordinamento: Bucket Sort e Radix Sort 4. Tecniche algoritmiche di base 4.1. Algoritmi greedy 4.2. Divide et impera 4.3. Programmazione dinamica 5. Strutture dati 5.1. Code di priorità e heap 5.2. Mappe 5.3. Tabelle hash 5.4. Mappe ordinate: alberi binari di ricerca 6. Algoritmi su grafi diretti e indiretti 6.1. Visita 6.2. Componenti connesse e applicazioni delle visite in profondità e ampiezza 6.3. Algoritmi per la ricerca di cammini minimi 6.4. Algooritmi per l'individuazione di alberi ricoprenti minimi 6.5. Union Find 7. Algoritmi su stringhe 7.1. Pattern matching: algoritmi di Boyer-Moore e Knuth-Morris-Pratt 7.2. Compressione e algoritmo di Huffman 7.3. DNA e allineamento di sequenze 8. Randomizzazione 8.1. Quicksort e Quickselect 8.2. Test di primalità 8.3. Algoritmi randomizzati efficienti per il test di primalità PARTE 2: Modelli e linguaggi 2.1 Automi a stati finiti 2.2 Espressioni regolari e grammatiche (Abstract Syntax Tree) 2.3 Analisi lessicale e sintattica 2.4 Traduttori: compiler generators Calcolabilità e complessità 2.5 Macchina di Turing 2.6 Decidibilità 2.7 Classi di complessità (P, NP, PSPACE, ecc.) 2.8 Tecniche non polinomiali: enumerazione, backtracking

- Testo di riferimento: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. Algoritmi e strutture dati in Java. Apogeo Education. 2015.

PARTE 1: Algoritmi e Strutture Dati 1. Ricorsione Lineare, di coda. Binaria. Multipla. Esempi. 2. Algoritmi avanzati di ordinamento 3. Strutture dati Code di priorità e heap. Mappe e dizionari. Tavole hash. Mappe e dizionari ordinati. Alberi binari di ricerca e tecniche di bilanciamento 4. Algoritmi su grafi diretti e indiretti Il tipo di dato astratto grafo. rappresentazione dei grafi in memoria. Visite DFS e BFS e loro applicazioni. Cammini minimi (s-t, SSSP, APSP). Alberi ricoprenti minimi (e Union Find). Chiusura transitiva. D-DFS: topological sort, componenti fortemente connesse 5. Algoritmi su stringhe Pattern matching, compressione e algoritmo di Huffman. DNA e allineamento di sequenze 6. Randomizzazione Quicksort e Quickselect. Test di primalità randomizzato. PARTE 2: Modelli e linguaggi 1. Modello analisi algoritmi a costi uniformi. Delimitazioni inferiori e superiori alla complessità di algoritmi e problemi. 2. Macchine di Turing A un nastro, multinastro, non deterministiche, macchina universale 3. Calcolabilità Decidibilità, indecidibilità. Halting problem; riduzioni ed altri problemi indecidibili. Equivalenza di modelli di calcolo e la tesi di Church-Turing. 4. Complessità Classi P, NP. Riduzioni polinomiali e NP-completezza; esempi di problemi NP-completi. Oltre NP. Tecniche algoritmiche per problemi intrattabili. 5. Tecniche algoritmiche di base Divide et impera, Algoritmi greedy, Programmazione dinamica. Esempi. 6. Linguaggi Grammatiche, la gerarchia di Chomsky. Grammatiche e linguaggi regolari e context-free. Alberi di derivazione sintattica. Analisi lessicale. Tecniche per l'analisi sintattica: anlaisi bottom-up e analisi top-down Generatori di parser. Attività di laboratorio richiedono di programmare soluzioni per esercizi relativi ad una selezione degli argomenti precedenti.

Il materiale (dispense, lucidi, appunti e video) e' disponibile sulla piattaforma Pizza.com allla sezione del corso.