Fondamenti di Informatica II - Programma del corso

Algoritmi e complessità
Il concetto di algoritmo. Problemi risolubili con algoritmi.  La tecnica del Divide et impera e la ricorsione.  Il caso degli algoritmi di ordinamento: il selection sort, il quicksort e il merge sort. La generazione delle permutazioni di un insieme di elementi. Formule di ricorrenza. Il calcolo del livello massimo per gli alberi bilanciati. Valutazione della complessità. Crescita asintotica della complessità. Limiti inferiori. L'albero di decisione. Tecniche di enumerazione: backtracking. Problemi classici risolubili con algoritmi di enumerazione: le N regine; il problema dello zaino; la sottisfattibilità; i cicli hamiltoniani nei grafi e il problema del commesso viaggiatore. La tecnica di branch and bound. Algoritmi non deterministici. Problemi intrattabili. Problemi indecidibili. Il problema della terminazione per la macchina di Turing. Classi di complessità: le classi P, NP e NP-complete. Riduzione polinomiale di problemi. Il teorema di Cook.

Grammatiche, linguaggi e traduttori
Linguaggi formali e grammatiche. Espressioni regolari e automi a stati finiti. Uso delle espressioni regolari ed utilità basate su espressioni regolari (regexp). Generazione di analizzatori lessicali con LEX (Flex e JFlex). Riconoscitori di linguaggi context-free. Analisi sintattica. Ambiguità: il caso delle espressioni e dell'if..then..else. Analisi discendente ricorsiva.  Analizzatori discendenti predittivi. Analisi top-down guidata da tabella. Grammatiche LL(1).  Analisi ascendente. Grammatiche LR(1). Uso delle utilità per la generazione di analizzatori sintattici: YACC.

Strutture dati dinamiche
Strutture basate su alberi: alberi di ricerca, alberi AVL. Lo  heap: struttura, inserimento ed estrazione. Gestione di una coda con priorità. Heapsort. Grafi orientati e non orientati. Componenti connesse di un grafo non orientato. Visite di un grafo in profondità e in ampiezza. Verifica della presenza di cicli, ordinamento topologico per grafi aciclici.

Testi di consultazione

[1] F. Luccio, "La struttura degli algoritmi," Bollati Boringhieri
[2] Alfed V. Aho, Jeffrey D. Ullman, "Fondamenti di informatica," Zanichelli
[3] Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, "Compilers: Principles, Techniques and Tools," Addison-Wesley.
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Introduzioni agli algoritmi," Jackson libri.