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.

Strutture dati e ricerca

Strutture per la gestione di dati in  memoria secondaria: file sequenziali e ad accesso casuale. Accesso diretto. Tabelle hash. File con indice. Strutture basate su alberi: alberi di ricerca, alberi AVL, alberi paginati, alberi B e B*. Trie.

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. Minimo albero ricoprente: l'algoritmo di Kruskal. Visite di un grafo in profondità e in ampiezza. Verifica della presenza di cicli, ordinamento topologico per grafi aciclici. Problemi di cammino minimo: l'algoritmo di Dijkstra e l'algoritmo di Floyd.

Grammatiche e linguaggi

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 a operatori con precedenza. Grammatiche LR(1). Uso delle utilità per la generazione di analizzatori sintattici: YACC.

Linguaggi di programmazione

Linguaggi imperativi, funzionali, descrittivi e ad oggetti. Un linguaggio funzionale: gli elementi di base di  Scheme. Un linguaggio descrittivo: la programmazione in Prolog. Linguaggi ad oggetti: il concetto di oggetto; l'incapsulamento; il polimorfismo; le classi; l'eredità; le proprietà e i metodi.

Il linguaggio JAVA. La Java Virtual Machine. La programmazione ad oggetti in Java: classi, interfacce, classi astratte. Eredità. Tipi primitivi. Classi di base. La programmazione di interfacce grafiche: AWT e Swing. Gestione degli eventi: i Listeners. Le applets. Le classi per l'I/O. Cenni su Threads e programmazione concorrente in Java. Il garbage collector.

Testi di consultazione

[1] F. Luccio, "La struttura degli algoritmi," Bollati Boringhieri
[2] D.E.Knuth, "The Art of Computer Programming," voll.1 e 3 Addison Wesley 1973
[3] Ravi Sethi, "Linguaggi di programmazione," Zanichelli
[4] John E. Hopcroft, Jeffrey D. Ullman, "Introduction to automata theory, languages and computation," Addison Wesley
[5] Alfed V. Aho, Jeffrey D. Ullman, "Fondamenti di informatica," Zanichelli
[6] Bruce Eckel, "Thinking in Java"
[7] Cay S. Hortsmann, Gary Cornell, "Java 2: i fondamenti," McGrawhill
[8] Jamie Jaworski, "Java 2: tutto & oltre," Apogeo
[9] William F. Clocksin, Christopher S. Mellish, "Programmare in PROLOG," Franco Angeli
[10] P:L. Livadas, "File Structures: Theory and Practice," Prentice-Hall, 1990
[11] Alfred V. Aho, Ravi Sethi. Jeffrey D. Ullman, "Compilers: Principles, Techniques and Tools," Addison-Wesley.

 

[Home] [Scuola Dottorato del GII] [Calcolatori Elettronici] [Fondamenti di Informatica II] [Tesi di Laurea]