Obiettivi
del corso
La
prima parte del corso presenta una panoramica di tecniche algoritmiche
e strutture dati fondamentali, ricorrenti nelle applicazioni. La
seconda parte del corso di Fondamenti di Informatica II ha invece
l'obiettivo di fornire agli studenti una prima introduzione a modelli
formali che permettono di astrarre le capacità di calcolo dei sistemi
reali dalla loro effettiva implementazione, permettendo tra l'altro di
introdurre nozioni di complessità dei problemi. Lo studente che abbia
seguito con profitto il corso avrà una buona conoscenza di base
dell'area e sarà in grado di realizzare soluzioni algoritmiche
sofisticate a problemi di interesse.
Programma
preliminare del corso - A.A. 2018/2019
Parte
1
1.1 Tecniche di progettazione ricorsiva
1.2 Modelli e analisi degli algoritmi (RAM a costi uniformi)
1.3 Code di priorità e heap
1.4 Tabelle e funzioni hash
1.5 Dizionari e loro implementazione
1.6 Mappe ordinate e alberi binari di ricerca
1.7 Algoritmi avanzati di ordinamento
1.8 Operazioni su insiemi
1.9 Grafi, strutture dati per la loro rappresentazione e operazioni di
base
1.10 Sottografi e connettivitÃ
1.11 Visita in profondità su Grafi Diretti
1.12 Percorsi minimi
1.13 Alberi ricoprenti minimi e algoritmi per il loro calcolo
Parte 2
Linguaggi formali
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