Informatica teorica
A.A. 2018/2019
Obiettivi formativi
L'insegnamento introduce le nozioni fondamentali della teoria della calcolabilità e della complessità. Viene affrontato il concetto di problema risolvibile per via algoritmica e di problema che non ammette algoritmi di risoluzione. Vengono poi presentate la classificazione e la suddivisione dei problemi in classi di complessità, definite in termini di limiti alla quantità di risorse a disposizione.
Risultati apprendimento attesi
Non definiti
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
STUDENTI FREQUENTANTI
Programma
Teoria della calcolabilità
· Prerequisiti matematici
· Funzione coppia
· Linguaggi di programmazione RAM e while
· Sintassi e semantica operazionale
· Compilatori
· Aritmetizzazione di programmi
· Interprete e funzione universale
· Eliminazione del "goto"
· Funzioni ricorsive parziali
· Tesi di Church
· Esistenza di problemi non decidibili
· Passaggio automatico di parametri
· Sistemi di programmazione accettabili
· Teorema di ricorsione
· Insiemi ricorsivi e ricorsivamente numerabili
· Proprietà di chiusura
· Teorema di Rice
Teoria della complessità
· Introduzione alla complessità sequenziale
· Prerequisiti matematici: la notazione "O grande"
· Macchine di Turing deterministiche
· Risorse computazionali: tempo e spazio
· Classi di complessità in tempo e spazio
· Le classi L, P, PSPACE
· Tesi di Church ristretta
· Macchine di Turing nondeterministiche: tempo e spazio
· Le classi NL, NP, NPSPACE
· Teorema di Savitch
· Riduzioni tra problemi e completezza
· Problemi NP-completi, P-completi, PSPACE-completi
· Teorema di Cook ed esempi di riduzione
· Prerequisiti matematici
· Funzione coppia
· Linguaggi di programmazione RAM e while
· Sintassi e semantica operazionale
· Compilatori
· Aritmetizzazione di programmi
· Interprete e funzione universale
· Eliminazione del "goto"
· Funzioni ricorsive parziali
· Tesi di Church
· Esistenza di problemi non decidibili
· Passaggio automatico di parametri
· Sistemi di programmazione accettabili
· Teorema di ricorsione
· Insiemi ricorsivi e ricorsivamente numerabili
· Proprietà di chiusura
· Teorema di Rice
Teoria della complessità
· Introduzione alla complessità sequenziale
· Prerequisiti matematici: la notazione "O grande"
· Macchine di Turing deterministiche
· Risorse computazionali: tempo e spazio
· Classi di complessità in tempo e spazio
· Le classi L, P, PSPACE
· Tesi di Church ristretta
· Macchine di Turing nondeterministiche: tempo e spazio
· Le classi NL, NP, NPSPACE
· Teorema di Savitch
· Riduzioni tra problemi e completezza
· Problemi NP-completi, P-completi, PSPACE-completi
· Teorema di Cook ed esempi di riduzione
Informazioni sul programma
Il corso si compone di lezioni frontali in cui vengono presentati i principi della teoria della calcolabilità e della complessità computazionale
Propedeuticità
Nessuna
Prerequisiti
Nessun prerequisito particolare richiesto.
L'esame consiste in una prova scritta, o equivalentemente in un colloquio orale, obbligatoria che copre il più completamente possibile tutti gli argomenti trattati al corso di Informatica Teorica. Verranno proposte domande ed esercizi su entrambe le parti che caratterizzano il corso: teoria della calcolabilità e teoria della complessità. Domande ed esercizi saranno volti ad accertare la padronanza, da parte dello studente, sia dei concetti base sia della capacità di formalizzare gli stessi
nella maniera più precisa possibile. Verranno anche proposte domande in cui si chiederà un contributo "originale" da parte dello studente, al fine di cogliere una certa maturità scientifica. Durata della prova scritta: 2 ore circa.
L'esame consiste in una prova scritta, o equivalentemente in un colloquio orale, obbligatoria che copre il più completamente possibile tutti gli argomenti trattati al corso di Informatica Teorica. Verranno proposte domande ed esercizi su entrambe le parti che caratterizzano il corso: teoria della calcolabilità e teoria della complessità. Domande ed esercizi saranno volti ad accertare la padronanza, da parte dello studente, sia dei concetti base sia della capacità di formalizzare gli stessi
nella maniera più precisa possibile. Verranno anche proposte domande in cui si chiederà un contributo "originale" da parte dello studente, al fine di cogliere una certa maturità scientifica. Durata della prova scritta: 2 ore circa.
Metodi didattici
Modalità di erogazione: Lezioni frontali, in aggiunta videolezioni registrate.
Modalità di frequenza: Fortemente consigliata.
Modalità di frequenza: Fortemente consigliata.
Materiale di riferimento
STUDENTI NON FREQUENTANTI
· Dispense reperibili al sito del corso (vedi sotto)
· Teoria della calcolabilità: A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986
· Teoria della Complessità :M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979
· Teoria della calcolabilità: A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986
· Teoria della Complessità :M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979
Programma
Teoria della calcolabilità
· Prerequisiti matematici
· Funzione coppia
· Linguaggi di programmazione RAM e while
· Sintassi e semantica operazionale
· Compilatori
· Aritmetizzazione di programmi
· Interprete e funzione universale
· Eliminazione del "goto"
· Funzioni ricorsive parziali
· Tesi di Church
· Esistenza di problemi non decidibili
· Passaggio automatico di parametri
· Sistemi di programmazione accettabili
· Teorema di ricorsione
· Insiemi ricorsivi e ricorsivamente numerabili
· Proprietà di chiusura
· Teorema di Rice
Teoria della complessità
· Introduzione alla complessità sequenziale
· Prerequisiti matematici: la notazione "O grande"
· Macchine di Turing deterministiche
· Risorse computazionali: tempo e spazio
· Classi di complessità in tempo e spazio
· Le classi L, P, PSPACE
· Tesi di Church ristretta
· Macchine di Turing nondeterministiche: tempo e spazio
· Le classi NL, NP, NPSPACE
· Teorema di Savitch
· Riduzioni tra problemi e completezza
· Problemi NP-completi, P-completi, PSPACE-completi
· Teorema di Cook ed esempi di riduzione
· Prerequisiti matematici
· Funzione coppia
· Linguaggi di programmazione RAM e while
· Sintassi e semantica operazionale
· Compilatori
· Aritmetizzazione di programmi
· Interprete e funzione universale
· Eliminazione del "goto"
· Funzioni ricorsive parziali
· Tesi di Church
· Esistenza di problemi non decidibili
· Passaggio automatico di parametri
· Sistemi di programmazione accettabili
· Teorema di ricorsione
· Insiemi ricorsivi e ricorsivamente numerabili
· Proprietà di chiusura
· Teorema di Rice
Teoria della complessità
· Introduzione alla complessità sequenziale
· Prerequisiti matematici: la notazione "O grande"
· Macchine di Turing deterministiche
· Risorse computazionali: tempo e spazio
· Classi di complessità in tempo e spazio
· Le classi L, P, PSPACE
· Tesi di Church ristretta
· Macchine di Turing nondeterministiche: tempo e spazio
· Le classi NL, NP, NPSPACE
· Teorema di Savitch
· Riduzioni tra problemi e completezza
· Problemi NP-completi, P-completi, PSPACE-completi
· Teorema di Cook ed esempi di riduzione
Prerequisiti
Nessun prerequisito particolare richiesto.
L'esame consiste in una prova scritta, o equivalentemente in un colloquio orale, obbligatoria che copre il più completamente possibile tutti gli argomenti trattati al corso di Informatica Teorica. Verranno proposte domande ed esercizi su entrambe le parti che caratterizzano il corso: teoria della calcolabilità e teoria della complessità. Domande ed esercizi saranno volti ad accertare la padronanza, da parte dello studente, sia dei concetti base sia della capacità di formalizzare gli stessi
nella maniera più precisa possibile. Verranno anche proposte domande in cui si chiederà un contributo "originale" da parte dello studente, al fine di cogliere una certa maturità scientifica. Durata della prova scritta: 2 ore circa.
L'esame consiste in una prova scritta, o equivalentemente in un colloquio orale, obbligatoria che copre il più completamente possibile tutti gli argomenti trattati al corso di Informatica Teorica. Verranno proposte domande ed esercizi su entrambe le parti che caratterizzano il corso: teoria della calcolabilità e teoria della complessità. Domande ed esercizi saranno volti ad accertare la padronanza, da parte dello studente, sia dei concetti base sia della capacità di formalizzare gli stessi
nella maniera più precisa possibile. Verranno anche proposte domande in cui si chiederà un contributo "originale" da parte dello studente, al fine di cogliere una certa maturità scientifica. Durata della prova scritta: 2 ore circa.
Materiale di riferimento
· Dispense reperibili al sito del corso (vedi sotto)
· Teoria della calcolabilità: A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986
· Teoria della Complessità :M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979
· Teoria della calcolabilità: A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986
· Teoria della Complessità :M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979
Docente/i
Ricevimento:
su appuntamento via mail
Ufficio S 6008, VI piano, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy