SITE TITLE

LOGO DIETI

Complessità computazionale

Titolo insegnamento in inglese: 

Computational complexity

lingua: italiano 

Insegnamento: Complessità computazionale

Anno di corso: I

CFU: 6

SSD: INF/01

Ore di lezione: 48

Semestre: 2

Modulo: Nessuno

Codice:

Obiettivi formativi:

Questo corso estende e completa la preparazione algoritmica spostando l'attenzione dalla complessità dei singoli algoritmi alla complessità intrinseca dei problemi, espressa rispetto alle risorse computazionali necessarie per la loro risoluzione.  In questo modo si apprendono criteri per stimare l'ottimalità degli algoritmi, si identificano tecniche comuni per la risoluzione sistematica di ampie classi di problemi, si acquisiscono approcci più scientifici alla risoluzione di nuovi problemi. Verranno spiegate le relazioni tra consumo di memoria e lunghezza della computazione e il ruolo del nondeterminismo nell'analisi dei problemi la cui complessità esatta non è nota. Verranno altresì analizzate le relazioni tra questi aspetti e aree applicative importanti quali crittografia, ricerca operativa e ottimizzazione combinatoria.

Contenuti:

Problemi e algoritmi: formulazioni intuitive e formalizzazioni mediante linguaggi e macchine di Turing multinastro. Misure appropriate di complessità in termini di spazio e di tempo. Teoremi di speedup. Confronti con altre formalizzazioni delle computazioni e tesi di Church (cenni). Classi di complessità, teoremi di gerarchia e teorema di Savitch.  Riduzioni e completezza come formalizzazioni delle difficoltà relative e della complessità caratteristica dei problemi. Alcuni risultati di separazione. Problemi logici, su grafi e su insiemi completi per NP e coNP. Teorema di Cook.  La gerarchia polinomiale e PSPACE. Relazioni con la crittografia moderna. Breve analisi dell'impatto del quantum computing sulla risoluzione di problemi e sulla crittografia. Cenni delle classi oltre PSPACE: problemi che richiedono risorse esponenziali e problemi indecidibili.

Prerequisiti: Algebra, Elementi di Informatica teorica (Laurea triennale), Logica

Modalità didattiche:

Lezioni frontali. Esercitazioni.

 

Materiale didattico:

Christos H. Papadimitriou, Computational complexity. Addison-Wesley 1994, ISBN 978-0-201-53082-7, pp. I-XV, 1-523

 

Modalità di esame: 

L'esame si articola in prova

Scritta e orale

 

 

 

     

 

 

 

 

 

 

 

 

 

 

In caso di prova scritta i quesiti sono 

A risposta multipla

 

 

A risposta libera

 

 

 

 

Altro

 

Docente: Bonatti Piero