Marco CARPENTIERI | INFORMATICA 3

Italiano

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.
Si propone di introdurre gli studenti alle problematiche che riguardano la classificazione dei modelli in base ai principi di comportamento dei sistemi deterministici, stocastici, quantistici e non deterministici al fine di rendere chiara la centralità del problema della rappresentazione del calcolo in ambito scientifico.

Attenzione particolare è rivolta allo studio della teoria delle classi di complessità P e NP, alle relazioni che intercorrono tra i modelli deterministici e non deterministici di calcolo.
La teoria degli automi a stati finiti è sviluppata con l’intento di rendere più semplice la comprensione degli aspetti di analisi e modellistica orientati alle applicazioni.
Si introduce ai fondamenti della teoria dei linguaggi formali, accennando ai principi base per la progettazione modulare dei sistemi di traduzione.

- Teoria degli insiemi, Alfabeti, Linguaggi, Funzioni, Relazioni, Principio di induzione.
- Permutazioni, Gruppo simmetrico, Matrici, Sistemi di equazioni, Trasformazioni lineari.
- Spazi vettoriali, Spazi di Hilbert, Sistemi fisici.
- Spazi e distribuzioni di probabilità, Variabili  aleatorie, Aspettazione e Varianza, Risultati di concentrazione di probabilità, Legge dei grandi numeri, Stima parametrica.
- Logica Booleana, Logica del primo ordine, Dimostrazioni per induzione e per assurdo.
- Grafi, Alberi, Strutture dati.
- Macchina di Von-Neumann, Unità funzionali, Istruzioni, Programmi, Microsequenze, Funzioni Booleane, Porte elementari, Circuiti, Algebra Booleana, Analisi e sintesi circuitale, Basi, Calcolo uniforme e non.
- Istanze, Soluzioni, Problemi astratti, Categorie, Problemi di ottimizzazione e varianti decisionali, Riducibilità.
- Dimensione, Complessità, Algoritmi Ricorsivi, Analisi di complessità, Traduzione di algoritmi ricorsivi.
- Tecniche efficienti di programmazione (cenni (*)): Divide-et-Impera (Merge-Sort), Programmazione greedy (Selezione attività), Programmazione dinamica (Distanze minime), Programmazione esaustiva (Permutazioni).

(*) Si richiede una conoscenza adeguata, ma non approfondita.

Algebra, Logica, Teoria della probabilità, Grammatiche formali, Architetture e modelli, Macchine di Turing, Automi a stati finiti, Complessità, Classi P e NP, Riduzioni, Modelli di calcolo realizzabili fisicamente  

- 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 e NP, Indecidibilità (cenni (*)), Equivalenza tra accettare e decidere in tempo polinomiale, P contenuto in NP .
Riducibilità, NP-completezza (NPC) e NP-hardness, L appartiene a NPC e P implica P = NP, Soddisfacibilità, Teorema di Cook (enunciato).
- Riduzioni:  SAT a  3-SAT (enunciato), 3-SAT a 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).

(*) Si richiede una conoscenza adeguata, ma non approfondita.

Lezioni forntali, Seminari.

Tesine, Seminari, Prove scritte.

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, appunti, e integrazioni a cura del docente (verranno consigliate di volta in volta durante lo svolgimento delle lezioni).

Piattaforma Moodle, Discussioni interattive a lezione, E-mail,Proposte di problem-solving e ricerca, Comprensione e discussione di problemi, tirocini e indirizzi di tesi, Chiarimenti motivazionali, Aspettative professionali e/o lavorative.

Mesi di febbraio, maggio, giugno-luglio, settembre e dicembre.

Da decidere.