| | Lingua insegnamento |
|---|
| Italiano |
| | Obiettivi formativi e risultati di apprendimento |
|---|
| Il corso mira a far acquisire le competenze di base necessarie per comprendere la modellistica del calcolo secondo l’inquadramento classico dell’Informatica Teorica mostrando anche come essa sia realizzabile seguendo i più moderni principi dell’algebra computazionale e della teoria dei sistemi.
|
| | Prerequisiti |
|---|
| Algebra, combinatoria e probabilità discreta di base, architetture ed algoritmi |
| | Contenuti del corso |
|---|
| Modelli e sistemi di calcolo, classi di complessità, riducibilità logica, teoria degli automi di base, fondamenti di linguaggi formali |
| | Programma esteso |
|---|
| - Assunzioni di base per la progettazione di un modello formale di calcolo, RAMs (Random Access Machines), Componenti funzionali, Modalità di riferimento alla memoria, Istruzioni, Programmi, Configurazioni, Criteri di calcolo, Riconoscimento di linguaggi, Calcolo di funzioni, Analisi di complessità, Costo uniforme e logaritmico, Relazione polinomiale tra grandezze
- Macchine di Turing (TMs): Definizioni di base, Configurazioni, Computazioni, Criteri di arresto e di calcolo, Componenti funzionali e dettagli tecnologici, Riconoscimento di linguaggi e trasduzione, Linguaggi e funzioni calcolabili, Ipotesi di Church
- Varianti di TMs, Programmazione formale, Esempi notevoli di programmazione formale, Simulazione RAM
- Determinismo e non determinismo, Macchine di Turing non deterministiche, Computazioni parziali, dinamiche e criteri di calcolo, Programmazione non deterministica efficiente e tecniche di enumerazione, Verificabilità logica
- TMs fisicamente realizzabili (cenni): Stati, Dinamica, Osservabilità, Sistemi di calcolo stocastici e quantistici, Criteri di calcolo fault-tolerant, Simulabilità
- Classi di complessità, classi P ed NP, Indecidibilità (cenni), Equivalenza tra accettare e decidere in tempo polinomiale, P contenuto in NP
Riducibilità, NP-completezza (NPC) ed NP-hardness, L appartiene ad NPC ed P implica P = NP, Soddisfacibilità, Teorema di Cook (enunciato)
- Riduzioni: SAT a 3-SAT (enunciato), 3-SAT ad IS, 3-SAT a CLIQUE, Discussione sulla dimostrabilità di 3-SAT a (D)HAM
- Automi a stati finiti, Automi deterministici e non, Automi con ?-mosse, Equivalenza, Varianti di automi (cenni)
- Linguaggi regolari ed automi, Pumping Lemma per insiemi regolari, Proprietà di chiusura ed Algoritmi di decisione (cenni)
- Grammatiche formali (cenni), Gerarchia di Chomsky (enunciato) |
| | Metodi didattici |
|---|
| Lezioni, seminari, proiezioni diapositive, discussioni interattive |
| | Modalità di verifica dell'apprendimento |
|---|
| Presentazione di elaborati scritti sugli argomenti di programma, seminari/colloqui orali/scritti
|
| | Testi di riferimento e di approfondimento, materiale didattico Online |
|---|
| 1. Introduction to Algorithms, T. Cormen, R. Rivest, C. Leiserson, MIT Press, (II-Ed.) 2001
2. The Design and Analysis of Computer Algorithms, Aho, John E. Hopcroft, Jeffrey, D. Ullman, Addison-Wesley, (I-Ed.) 1974
3. Introduction to Automata Theory, Languages and Computation, J. E. Hopcroft, J. D. Ullman, Addison-Wesley, (III-Ed.) 2007 (tradotto in Italiano: Automi, Linguaggi e Calcolabilità, J. E. Hopcroft, J. D. Ullman, Motwani, Addison-Wesley, 2003)
4. Compilers: Principles, Techniques and Tools, A. V. Aho, R. Seti, J. D. Ullman, (II-Ed.) 2006
5. Computational Complexity, C. H. Papadimitriou, Addison-Wesley, 1993
6. The Art of Computer Programming, D. E. Knuth, Addison-Wesley, Massachussets,1997
7. Dispense a cura del docente |
| | Metodi e modalità di gestione dei rapporti con gli studenti |
|---|
| Lezioni frontali, seminari, presentazioni diapositive commentate, discussioni interattive, modalità telematiche |
| | Date di esame previste |
|---|
| Nei mesi di febbraio, maggio, luglio, settembre e dicembre (preferibilmente terza o quarta settimana del mese) |
| | Seminari di esperti esterni |
|---|
| Eventuali da definire |
