• Avvisi
• Organizzazione del Corso
• Finalità del Corso
• Programma del Corso
• Materiale didattico
• Modalità dell'esame
• Tracce di esame
• Date degli appelli

Avvisi

Organizzazione del Corso

Finalità del Corso

Programma del Corso

Teoria della Calcolabilità. Introduzione storica al problema della calcolabilità. Problemi decidibili e non decidibili. Classificazione dei problemi: problemi di ricerca, di decisione e di enumerazione. Un esempio classico: il problema del commesso viaggiatore (TSP). Altri esempi di complessità di algoritmi: il calcolo del determinante di una matrice con la regola di Laplace e con il metodo di Gauss. Definzione di grafo ed esempi di algoritmi legati alla teoria dei grafi. Raggiungibilità dei grafi. L'idea intuitiva di algoritmo. Proprietà degli algoritmi deterministici. Modelli di calcolabilità. Le macchine di Turing. Configurazione delle macchine di Turing. Esempi di macchine di Turing. Costo computazionale in tempo e in spazio di una macchina di Turing. Le macchine di Turing multinastro. La tesi di Church. Macchine ad Accesso Casuale (RAM). Istruzioni base di una RAM. Esempi di RAM. Configurazione di una RAM. Costo computazionale di una RAM. Teoria della Complessità Computazionale. Il concetto di complessità dei problemi decidibili. Le risorse Tempo e Spazio. Classificazione degli algoritmi. Il criterio di efficienza polinomiale. Le classi di complessità. Definizione e proprietà principali di una classe di complessità. La classe P. LA classe EXP. Progresso tecnologico ed algoritmi esponenziali. Non determinismo e classe NP. Relazioni tra le classi P e NP. Problemi NP-hard.

Materiale didattico

Modalità dell'esame

Tracce di esame

Date degli appelli