Informatica Teorica

Corso di Laurea Magistrale in Informatica

Contenuto delle lezioni - A.A. corrente



Data Argomento
28/2/2017 Presentazione del corso, struttura, motivazioni e organizzazione. Teoria della calcolabilità, teoria della complessità: una panoramica. Prerequisiti matematici: funzioni iniettive, esempi Funzioni suriettive e biiettive, esempi. Funzioni inverse, composizione di funzioni, esempi. Funzione parziale, dominio d'esistenza, esempi
7/3/2017 Totalizzazione di una funzione parziale, simbolo di indefinito. Prodotto cartesiano (generalizzato), proiettori, esempi. Classi di funzioni, funzione di valutazione. Modellazione di un sistema di calcolo, programma e sua funzione calcolata (semantica), esempi. Potenza computazionale di un sistema di calcolo come insieme delle funzioni calcolate. Problema dell'esistenza di funzioni non calcolabili. Calcolo di funzioni come soluzione di problemi generali
9/3/2017 Sul concetto di cardinalità. Relazione di equivalenza, partizione indotta, insieme quoziente. Relazione d'isomorfismo tra insiemi (equinumerosità). Nozione di cardinalità come quoziente della relazione di isomorfismo. Insiemi finiti, insiemi numerabili, esempi: razionali, stringhe, pari. Insiemi non numerabili, insiemi continui: reali, intervalli dei reali insieme delle parti di N, loro non numerabilità
14/3/2017 Non numerabilità di N->N, dimostrazione per diagonalizzazione. Dimostrazione (intuitiva) dell'esistenza di funzioni non calcolabilii, assunzioni intuitive DATI e PROG isomorfi a N. Numerabilità di NxN: definizione operativa ed analitica della funzione coppia di Cantor. Inversa della funzione coppia di Cantor, funzioni sin e des, costruzione ed esempi
16/3/2017 Isomorfismo DATI=N sulle principali strutture dati: liste di interi, codifica e decodifica in/da interi. Scrittura di codice per le principali primitive di gestione delle liste come interi. Codifica di testi, suoni, immagini. Codifica di array, matrici, grafi, esempi. La macchina RAM: linguaggio e architettura
21/3/2017 Esecuzione di programmi RAM, spiegazione intuitiva operativa. Definizione intuitiva di semantica (funzione calcolata) di un programma RAM. Esempi di scrittura di programmi RAM e di calcolo delle relative semantiche. Definizione formale di semantica di un programma RAM, semantica operazionale. Il concetto di stato, inizializzazione, terminazione. Funzione stato prossimo, computazione come sequenza di stati, definizione formale di semantica di un programma RAM. F(RAM)=insieme delle funzioni computabili in RAM. La questione PROGRAMMI=N dal punto di vista di PROG=insieme dei programmi RAM. Isomorfismo tra PROG ed N, Goedelizzazione di istruzioni e programmi
23/3/2017 Costruzione della codifica/decodifica di programmi RAM, esempi. F(RAM) come insieme di funzioni indicizzato da N (programmi in PROG). Dimostrazione formale che esistono funzioni non computabili in RAM. La macchina while: definizione induttiva del linguaggio e architettura, esempi di programmi e relativa semantica. Esempi di insiemi definiti induttivamente e tecniche di dimostrazione/definizione per induzione, esempi. Semantica operazionale dei programmi while data induttivamente. Concetto di stato e funzione stato prossimo. Funzione calcolata da un programma while, F(while)=insieme delle funzioni computabili in while
28/3/2017 Confronto tra potenze computazionali, il concetto di traduzione o compilazione, sua definizione formale e conseguenze. Costruzione induttiva del compilatore while -> RAM. Conseguenza: F(while) incluso in F(RAM). L'inclusione F(RAM) incluso in F(while) mediante interpretazione. Nozione di interprete, struttura di un interprete while di programmi RAM
30/3/2017 Costruzione in while (con marco-istruzioni) dell'interprete di programmi RAM. Conseguenze dell'esistenza dell'interprete: F(RAM)=F(while). Esistenza di un compilatore RAM -> while a partire dall'interprete. Panoramica rigorosa di quanto ottenuto circa il concetto di calcolabilità, esistenza di funzioni non calcolabili. Teorema di Boehm-Jacopini sull'eliminazione del goto, equivalenza tra programmazione a basso livello e programmazione strutturata. Esistenza dell'interprete universale nel sistema RAM. Esigenza di astrazione per il concetto di calcolabilità. Verso una definizione "matematica" del concetto di calcolabilità (Kleene). Nozione di operazione e chiusura rispetto ad un insieme di operazioni, esempi
4/4/2017 Costruzione della chiusura di un insieme rispetto ad un insieme di operazioni, esempi. Costruzione della classe delle funzioni ricorsive parziali mediante chiusure successive. Le funzioni elementari ELEM={successore, zero, proiezione} come nucleo delle funzioni calcolabili, necessità di espansione. L'operatore di composizione COMP, esempi. Chiusura di ELEM per COMP e necessità di espansione. L'operatore RP di ricorsione primitiva e la classe RicPrim delle funzioni ricorsive primitive come chiusura di ELEM per {COMP,RP}. Esempi di funzioni ricorsive primitive. Definizione induttiva di RicPrim
6/4/2017 RicPrim incluso in F(while), dimostrazione induttiva. Alcune proprietà di RicPrim: RicPrim=F(for), RicPrim incluso nella classe delle funzioni totali. Inclusione propria tra RicPrim e F(while), funzione di Ackermann. Necessità di ampliamento mediante l'operatore MIN di minimalizzazione, definizione ed esempi. La classe P=ELEM^{COMP,RP,MIN} delle funzioni ricorsive parziali, definizione induttiva. P incluso in F(while), dimostrazione induttiva. F(while) incluso in P, dimostrazione induttiva. P=F(while)=F(RAM). Panorama finale dei vari ampliamenti, funzioni ricorsive totali Tesi di Church e suo significato, sinonimi: ricorsivo=calcolabile, ricorsivo. totale=calcolabile da programmi che si arrestano su ogni input
11/4/2017 Necessità di astrarre il concetto di sistema di programmazione. Definizione assiomatica di sistema di programmazione accettabile (spa). Caratteristiche auspicabili verificate direttamente sul sistema RAM: tesi di Church, interprete universale, costruzione automatica di programmi particolare da programmi generali (funzione S^1_1). Il concetto di sistema di programmazione accettabile, i tre assiomi (Rogers '58): 1) tesi di Church 2) interprete universale 3) teorema S^1_1 e S^m_n. Nozione di compilatore: correttezza e completezza. Esistenza di un compilatore tra spa, esistenza di un compilatore esprimibile in qualunque spa. Esistenza in un spa di programmi che stampano se stessi (Quine), esempio in C e problema generale. Esistenza di compilatori completamente errati. Teorema di ricorsione, conseguenze: esistenza di Quine e inesistenza di compilatori completamente errati
20/4/2017 Teorema di ricorsione e sua dimostrazione, conseguenze: esistenza di Quine e inesistenza di compilatori completamente errati. Teorema di isomorfismo di Rogers (compilatore/decompilatore) come conferma della Tesi di Church. Uso del teorema di ricorsione per mostrare l'esistenza di programmi in spa (soluzione di equazioni in spa, esempi). Problemi di decisione, definizione formale ed esempi. Concetto di decidibilità per via "informatica" e "teorica" (funzione caratteristica del problema). Problemi decidibili, esempi
27/4/2017 Esistenza di problemi indecidibili, problema dell'arresto per programmi specifici, arresto per il programma "P cappuccio". Dimostrazione dell'indecidibilità del problema dell'arresto per il programma "P cappuccio". Indecidibilità del problema generale dell'arresto, dimostrazione. Riconoscimento automatico d'insiemi. Insiemi ricorsivi o decidibili, definizione ed esempi. Relazioni ricorsive, esempi. Esempi di insiemi non ricorsivi: insieme dell'arresto A
2/5/2017 Insiemi ricorsivamente numerabili come semidecidibili. Definizione ed algoritmi di parziale riconoscimento. Tre differenti caratterizzazioni degli insiemi ricorsivamente numerabili, dimostrazione della loro equivalenza. Insieme dell'arresto A: non ricorsivo, ricorsivamente numerabile, dimostrazione. Insiemi ricorsivi contenuti propriamente nei ricorsivamente numerabili, dimostrazione. Insiemi ricorsivi come algebra di Boole, conseguenze: complemento di A non ricorsivo
4/5/2017 Insieme B e suo complemento ricorsivamente numerabili implica B ricorsivo, dimostrazione, conseguenze: complemento di A non ricorsivamente numerabile. Panoramica finale della gerarchia ricorsivi-ricorsivamente numerabili. Proprietà di chiusura degli insiemi ricorsivamente numerabili. Insiemi che rispettano le funzioni, nozione ed esempi. Il teorema di Rice, dimostrazione ed utilizzo, esempi e conseguenze: impossibilità di scrivere programmi che testano la correttezza semantica di programmi
9/5/2017 Seminario Massimo Santini: "A Programming Approach to Computability" (Compresenza)
11/5/2017 Teoria della complessità, motivazioni ed oggetto, il "come": risorse di calcolo, loro definizione e misurazione, efficienza. Il modello di calcolo della macchina di Turing deterministica (mdT), definizione intuitiva e formale. Mossa, computazione, linguaggio accettato da una mdT. Configurazione in una mdT, computazione come sequenza di configurazioni
16/5/2017 MdT per il riconoscimento di insiemi: mdT come procedura o algoritmo per riconoscere un insieme. Caratterizzazione degli insiemi ricorsivi e ricorsivamente numerabili mediante mdT. MdT per risolvere problemi di decisione. Esempi di costruzione di mdT per il riconoscimento di linguaggi e soluzione di problemi di decisione. Pseudo-programmazione di mdT. MdT per il calcolo di funzioni, mdT come sistema di programmazione accettabile. La risorsa tempo: tempo di calcolo su un input, complessità in tempo di una mdT, esempi. Riconoscimento di linguaggi entro vincoli in tempo, esempi
18/5/2017 Notazione "O" per la valutazione del tasso di crescita di funzioni Complessità logaritmiche, lineari, polinomiali, esponenziali, esempi. Nozione di classe di complessità di linguaggi o problemi di decisione, la classe di complessità in tempo DTIME(g(n)). Classi di complessità di funzioni e problemi generali, la classe FTIME(g(n)). Le classi P ed FP come classi dei problemi efficientemente risolubili in termini di tempo: giustificazione "sperimentale". Robustezza di P ed FP, modello di mdT a più nastri, tesi di Church estesa
23/5/2017 La risorsa spazio: spazio di calcolo su un input, complessità in spazio di una mdT. Modello di MdT con nastro di input e di lavoro per una misura più fedele dello spazio, nuova definizione. Spazio di computazione e complessità in spazio. La classe DSPACE(g(n)), invarianza rispetto al numero di nastri. La classe L=DSPACE(log n) dei linguaggi riconoscibili efficientemente in termini di spazio. Esempi di linguaggi in L: palindrome. Trade-off spazio-tempo per le palindrome e in generale. Architettura di mdT su cui calcolare funzioni (nastro di output). La classe FSPACE(g(n)). La classe FL=FSPACE(log n) delle funzioni calcolabili efficientemente in termini di spazio. Confronto tra classi di complessità. DTIME(g(n)) incluso in DSPACE(g(n)), dimostrazione. Inclusione generale di DSPACE in DTIME con tempo esponenziale, dimostrazione. Corollario: L incluso in P, problema aperto sull'inclusione stretta. Considerazioni sul concetto di efficienza in senso teorico e pratico
25/5/2017 Problemi di difficile soluzione generale ma di facile "verificabilità", esempi: CNF-SAT, HC (Hamiltonian Circuit), CLIQUE, algoritmi esaustivi esponenziali per la loro soluzione. Il concetto di algoritmo nondeterministico: fase congetturale, fase di verifica. Algoritmi nondetrministici per il riconoscimento di linguaggi e la soluzione di problemi di decisione. La mdT nondeterministica, definizione e linguaggio accettato. MdT nondeterministiche per la soluzione di problemi di decisione. Complessità in tempo per le mdT nondeterministiche. La classe NTIME(f(n)), relazioni con DTIME(f(n)), determinizzazione di algoritmi
30/5/2017 La classe NP, relazione con P, la questione aperta P=NP. Il concetto di riduzione polinomiale tra linguaggi, sua importanza nella classificazione dei linguaggi in NP. Problemi NP-completi. Teorema: P=NP sse esiste un problema NP-completo risolubile in tempo polinomiale. Implicazioni del concetto di NP-completezza. Esempi di problemi NP-completi: CNF-SAT (teorema di Cook-Levin, 1970), HC, CLIQUE. Discussione sul significato di NP-completezza
6/6/2017 Problemi in NP la cui NP-completezza non è nota: GRAPH ISOMORPHISM. Varianti di CNF-SAT: 3CNF-SAT (difficile), 2CNF-SAT (facile), DNF-SAT (facile). La questione aperta L=P. Il concetto di riduzione log-space tra linguaggi, sua importanza nella classificazione dei linguaggi in P. Problemi P-completi e loro importanza, esempi. Problemi P-completi non efficientemente parallelizzabili

Torna alla pagina del corso

Carlo Mereghetti
Dipartimento di Informatica
Università degli Studi di Milano
via Comelico 39, 20135 Milano, Italy
phone(fax) +39 02 503 16261(16276)
mail: mereghetti@di.unimi.it