Fondamenti Di Informatica 2025/2026

Parte I: calcolabilità.

Introduzione al corso: algoritmi, problemi, modelli di calcolo.

Macchine di Turing: trasduttori e riconoscitori, a un nastro e a k nastri, deterministiche e non deterministiche. Macchina di Turing universale. Linguaggi e funzioni. Linguaggi e linguaggi complemento. Accettabilità e decidibilità di linguaggi. Calcolabilità di funzioni. La tesi di Church-Turing e modello di calcolo equivalenti alla macchina di Turing. Linguaggi non decidibili. Halting problem. Riducibilità tra linguaggi.

Grammatiche di Chomsky e loro gerarchia. Equivalenza fra grammatiche di tipo 0 e macchine di Turing.

Decidibilità dei linguaggi di tipo 1. Grammatiche di tipo 2: linguaggi context-free e automi a pila, forme normali, ambiguità. Grammatiche di tipo 3: linguaggi, espressioni regolari, automi a stati finiti.

Parte II: complessità.

Misure di complessità: dtime, dspace, ntime, nspace. Classi di linguaggi: DTIME, DSPACE, NTIME, NSPACE. Gap theorem e funzioni time-constructible. Teoremi di compressione e di accelerazione. Definizione delle classi di complessità spaziale e temporale: P, NP, PSPACE, NPSPACE, EXP, coNP. Inclusione, inclusione propria, coincidenza. Completezza.

Problemi e codifiche. Problemi decisionali e loro complemento. La classe P. La classe NP. Problemi NP-completi e Teorema di Cook-Levin. Chiusura rispetto alla riduzione polinomiale. Esempi di dimostrazioni di NP-completezza: 3-SAT, Vertex Cover, 3-Colorability, Colorability, Independent Set, Clique, Hamiltonian Circuit/Path, Longest Path, Commesso Viaggiatore. Problemi NP-intermedi: il teorema di Ladner.