Insegnamento mutuato da: B010474 - INFORMATICA TEORICA Laurea Triennale (DM 270/04) in INGEGNERIA INFORMATICA Curriculum TECNICO APPLICATIVO
Lingua Insegnamento
Lezioni sono in italiano, con diapositive e altra materia didattica in inglese. L'esame si può sostenere in italiano o inglese.
Contenuto del corso
Il corso è organizzato in un assortimento argomenti tecnici e teorici che, presi insiemi, forniscono una formazione sulla Teoria del Calcolo. Vede il programma del corso per dettagli.
Le lezioni (e le presentazioni corrispondenti) sono complete e piuttosto auto-contenute. Però la materia presentata a lezioni è stata presa da diversi fonti:
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson.
Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.
Martin, John (2002). Introduction to Languages and the Theory of Computation (3rd ed.). McGraw-Hill.
Obiettivi Formativi
Obiettivo del corso è quello di fornire le conoscenze dei concetti e modelli di calcolo più importante nell'informatica teorica:
- Conoscenza delle tecniche dimostrative utilizzate nell'informatica teorica: dimostrazione costruttiva, dimostrazione per assurdo, dimostrazione induttiva (usando induzione matematica, induzione completa, e induzione strutturale)
- Conoscenza dei modelli di calcolo più importanti dell'informatica teorica: automi deterministici e non deterministici a stati finiti, linguaggi regolari, linguaggi liberi dal contesto, automi a pila, e la Macchina di Turing.
- Conoscenza della teoria della calcolabilità: linguaggi ricorsivi e ricorsivamente enumerabile, l'esistenza di problemi non decidibili, il problema di terminazione e la sua non calcolabilità.
- Conoscenza di base della teoria della complessità computazionale: complessità asintotica, riduzione polinomiale, le classi P, NP, NP-hard, NP-complete, NP-completezza di SAT, e l'importanza della proposizione P=NP.
A fine corso lo studente saprà applicare queste conoscenze a problemi di calcolo, calcolabilità e complessità computazionale.
Prerequisiti
Familiarità con metodi di dimostrazione, particolarmente dimostrazione per induzione, sarebbe molto utile ma non essenziale. Il corso comincia con una basica introduzione a questi argomenti.
Metodi Didattici
Il corso consiste interamente in lezioni frontali.
Modalità di verifica apprendimento
La verifica finale consta di una prova scritta e una prova orale in cui attraverso uno o più esercizi e domande si verifica la capacità di:
- Saper costruire automi/grammatiche semplici che accettano/generano un linguaggio specifico.
- Saper applicare tecniche di dimostrazione matematica per dimostrare proprietà di linguaggi e automi.
- Saper riconoscere grammatiche ambigue e disambiguare una grammatica.
- Saper dimostrare linguaggi non regolari e non liberi da contesto.
- Saper dimostrare problemi non decidibili.
- Saper distinguere le classi principali della complessità computazionale
A metà corso ha luogo una prova scritta intermedia. Se l'esito della prova intermedia è >= 18 è possibile svolgere una prova scritta solo sulla parte restante del programma.
Programma del corso
Il corso è organizzato intorno ai seguenti argomenti:
- Linguaggi regolari: espressioni regolari, automi finiti e deterministici, automi finiti e non deterministici, i limiti di linguaggi regolari, il teorema di Myhill-Nerode e il Pumping Lemma per linguaggi regolari.
- Linguaggi liberi di contesto: grammatiche libere di contesto, automi a pila, i limiti di linguaggi liberi di contesto e il Pumping Lemma per linguaggi liberi di contesto.
- La Macchina di Turing: il modello di calcolo basato sulla Machina di Turing, equivalenza di macchine a nastri multipli a macchine mono-nastro, la Macchina di Turing Universale.
- La teoria di calcolabilità: i limiti della Macchina di Turing, il problema di terminazione, problemi non decidibili e il Teorema di Rice.
- La complessità computazionale: complessità asintotica, la complessità di una Macchina di Turing, le classi P e NP, la congettura P=NP, il Teorema di Cook.