Informatica

Obiettivi generali: Durante il corso saranno introdotti i più importanti risultati dell’Informatica teorica: a partire dai fondamentali risultati in teoria della calcolabilità degli anni trenta, passando per quelli in teoria degli automi degli anni cinquanta per arrivare al problema aperto P contenuto o uguale a NP, esplicitamente sollevato negli anni settanta. Obiettivi specifici: Gli studenti capiranno che ci sono diversi modelli di computazione e cosa ne determina il potere computazionale. Gli studenti apprenderanno concetti astratti come classi di linguaggi, macchine universali, riducibilità e sapranno che alcuni problemi non possono essere risolti con un calcolatore e che altri sono computazionalmente difficili da risolvere o addirittura così difficili da poter essere considerati non risolvibili. Faremo vedere come alcuni di questi risultati sono utilizzati oggi. Conoscenza e comprensione: Al termine del corso gli studenti conosceranno i metodi e risultati di base della della teoria degli automi, della calcolabilità e della complessità e sapranno applicarli per individuare la complessità di problemi in diversi campi. In particolare sapranno: dimostrare l’equivalenza tra le diverse caratterizzazioni dei linguaggi regolari dimostrare l’equivalenza tra le diverse caratterizzazioni dei linguaggi context-free spiegare il concetto di non determinismo giustificare l'esistenza di problemi privi di soluzioni algoritmiche o intrattabili. Applicazione di conoscenza e comprensione: Gli studenti impareranno: come costruire automi finiti (deterministici e non) da una specifica (formale o informale) come costruire automi a pila (deterministici e non) da una specifica (formale o informale) a usare la riducibilità tra problemi per dimostrarne la decidibilità o l'indecidibilità a usare la riducibilità polinomiale per provare la NP-hardness di un problema Autonomia di giudizio: Capire il giusto livello di astrazione utile per risolvere un problema, scegliere il modello computazionale più conveniente in un determinato contesto alicativo Abilità comunicative: descrivere un linguaggio formale, a parole o attraverso uno degli strumenti offerti di descrizione finita, descrivere problemi indecidibili, intrattabili o trattabili, spiegare il significato e la rilevanza dele classi P ed NP nonché del problema “P=NP?" Capacità di apprendimento: Lo studente sarà in grado di imparare altri modelli computazionali, sia completamente diversi da quelli studiati durante il corso, sia variazioni di questi. Egli sarà capace di capire nuove prove di NP-completezza o più in generale prove di completezza per una qualunque classe di complessità