Teoria del calcolo
Automi, linguaggi formali, macchine di Turing, calcolabilità, complessità e P contro NP.
Approssimazione con garanzia: quando l'ottimo è NP-difficile
Rapporto di approssimazione, algoritmi con garanzia per copertura di vertici e commesso viaggiatore, schemi per lo zaino e limiti di inapprossimabilità.
Automi a pila: la memoria che rende possibili le parentesi
Come funziona un automa a pila, perché riconosce esattamente i linguaggi liberi dal contesto e perché la versione deterministica è strettamente più debole.
Automi a stati finiti deterministici: come funziona un DFA
Che cos'è un automa a stati finiti deterministico, come si definisce in modo formale, come si costruisce passo passo e quali linguaggi può riconoscere.
Automi non deterministici e costruzione dei sottoinsiemi
Come funziona un automa a stati finiti non deterministico (NFA), perché riconosce gli stessi linguaggi di un DFA e come si converte con i sottoinsiemi.
La classe coNP: tautologie, certificati del no e gerarchia
Che cos'è la classe coNP, perché le tautologie sono coNP-complete, che cosa sappiamo di NP ∩ coNP e come la gerarchia polinomiale generalizza l'idea.
La classe NP: verificatori, certificati e non determinismo
Che cosa vuol dire che un problema è in NP: le due definizioni equivalenti con verificatori e macchine non deterministiche, esempi ed equivoci.
La classe P: che cosa significa risolvere in tempo polinomiale
Definizione della classe P, perché il tempo polinomiale è il confine della trattabilità, il peso della codifica dell'input e i casi pseudo-polinomiali.
Complessità spaziale: PSPACE, teorema di Savitch e giochi
Come si misura la memoria usata da un algoritmo, il teorema di Savitch, il problema TQBF PSPACE-completo, il legame con i giochi e le classi logaritmiche.
La gerarchia di Chomsky: quattro classi di linguaggi formali
La gerarchia di Chomsky: grammatiche di tipo 0, 1, 2 e 3, gli automi corrispondenti, esempi che separano le classi e cosa si decide a ogni livello.
Grammatiche libere dal contesto: derivazioni e ambiguità
Che cosa sono le grammatiche libere dal contesto, come si scrivono le regole, come leggere derivazioni e alberi sintattici e come si elimina l'ambiguità.
Macchina di Turing: definizione formale, configurazioni, esempi
La macchina di Turing come modello matematico: nastro, testina, funzione di transizione, configurazioni, accettazione e un esempio svolto passo dopo passo.
La macchina di Turing universale: programmi come dati
Come si codifica una macchina di Turing come stringa e come una macchina universale la esegue: l'idea di interprete, la simulazione e le sue conseguenze.
Minimizzare un automa: Myhill-Nerode e stati equivalenti
Come si riduce un DFA al numero minimo di stati: stati indistinguibili, algoritmo per raffinamento di partizioni e teorema di Myhill-Nerode con esempi.
NP-completezza e teorema di Cook-Levin: il primo problema
Che cosa rende un problema NP-completo, come il teorema di Cook-Levin prova che SAT lo è con la tabella di calcolo e perché basta un problema di partenza.
P contro NP: la domanda, le conseguenze e perché è così difficile
Che cosa chiede davvero il problema P contro NP, che cosa cambierebbe nei due scenari, i problemi intermedi di Ladner e le barriere note finora.
Il problema della fermata: perché è indecidibile
La dimostrazione per diagonalizzazione che nessun algoritmo decide se un programma si ferma, spiegata passo per passo, con le conseguenze per il software.
Il problema di corrispondenza di Post: indecidibilità con le tessere
Il problema di corrispondenza di Post con esempi a tessere, l'idea della dimostrazione tramite storie di calcolo e le conseguenze sulle grammatiche.
Pumping lemma libero dal contesto e proprietà di chiusura
Come dimostrare che un linguaggio non è libero dal contesto: il pumping lemma con due parti da pompare, esempi svolti e le proprietà di chiusura utili.
Pumping lemma per linguaggi regolari: come usarlo davvero
Il pumping lemma per i linguaggi regolari spiegato con l'intuizione dei cicli, lo schema di dimostrazione per assurdo, esempi svolti ed errori tipici.
Riduzioni di mappatura: dimostrare l'indecidibilità per confronto
Che cos'è una riduzione di mappatura, in che verso si applica, esempi su linguaggio vuoto ed equivalenza e la differenza con le riduzioni di Turing.
Riduzioni polinomiali svolte: da 3-SAT a cricca e copertura
Tre riduzioni NP-complete spiegate passo passo: da 3-SAT a insieme indipendente, da insieme indipendente a cricca e copertura di vertici, con un esempio.
Teorema di Kleene: espressioni regolari e automi equivalenti
Il teorema di Kleene dimostra che espressioni regolari e automi finiti descrivono gli stessi linguaggi: le due costruzioni, con esempi passo per passo.
Il teorema di Rice: i limiti dell'analisi automatica dei programmi
Il teorema di Rice con esempi: perché ogni proprietà non banale del comportamento di un programma è indecidibile e che cosa si può ancora analizzare.
Tesi di Church-Turing: lambda calcolo, ricorsione e registri
Che cosa afferma la tesi di Church-Turing, perché non è un teorema e perché lambda calcolo, funzioni ricorsive e macchine a registri si equivalgono.
Varianti della macchina di Turing: perché sono equivalenti
Macchine multinastro, non deterministiche, enumeratori e nastri bidirezionali: come ognuna si simula con il modello base e quanto costa la simulazione.