Fondamenti di Informatica II

Docenti: Prof. Luca Becchetti, Prof. Alberto Marchetti-Spaccamela



 
Instructor's address: Dipartimento di Ingegneria Informatica Automatica e Gestionale
Universita' di Roma "La Sapienza" 
Via Ariosto 25, II floor, room B206
00185, Rome - ITALY
Tel.: +39 06 77274026
E-mail: becchetti@diag.uniroma1.it



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



Sito Web del corso - anno accademico 2018/2019