Informatica Teorica

Corso di Laurea Magistrale in Informatica

Contenuto delle lezioni - A.A. corrente



Data Argomento
28/2/2018 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. Insieme immagine. Funzioni inverse, composizione di funzioni, esempi
2/3/2018 Funzione parziale, dominio d'esistenza, esempi. 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. Sul concetto di cardinalità. Relazione di equivalenza, esempi
7/3/2018 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à. Non numerabilità di N->N, dimostrazione per diagonalizzazione. Dimostrazione (intuitiva) dell'esistenza di funzioni non calcolabilii, assunzioni intuitive DATI e PROG isomorfi a N
9/3/2018 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. 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
14/3/2018 Codifica di testi, suoni, immagini. Codifica di array, matrici, grafi, esempi. La macchina RAM: linguaggio e architettura. 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
16/3/2018 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. 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
21/3/2018 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. 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
23/3/2018 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
28/3/2018 Costruzione in while (con marco-istruzioni) dell'interprete di programmi RAM. Conseguenze dell'esistenza dell'interprete. F(RAM)=F(while), Teorema di Boehm-Jacopini sull'eliminazione del goto, equivalenza tra programmazione a basso livello e programmazione strutturata. Panoramica rigorosa di quanto ottenuto circa il concetto di calcolabilità, esistenza di funzioni non calcolabili. Esistenza dell'interprete universale nel sistema RAM. Esigenza di astrazione per il concetto di calcolabilità. Verso una definizione "matematica" del concetto di calcolabilità
4/4/2018 Nozione di operazione e chiusura rispetto ad un insieme di operazioni, esempi. 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
6/4/2018 Definizione induttiva di RicPrim. 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). 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)
11/4/2018 Panorama finale dei vari ampliamenti, funzioni ricorsive totali p Tesi di Church e suo significato, sinonimi: ricorsivo=calcolabile, ricorsivo totale=calcolabile da programmi che si arrestano su ogni input. 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 particolari 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
13/4/2018 Esistenza di un compilatore tra spa, esistenza di un compilatore esprimibile in qualunque spa. Teorema di isomorfismo di Rogers (compilatore/decompilatore). 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. Teorema di ricorsione e sua dimostrazione, conseguenze: esistenza di Quine e inesistenza di compilatori completamente errati. 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. Insieme associato a un problema di decisione. Concetto di decidibilità di problemi di decisione e ricorsività di insiemi (funzione caratteristica di un insieme ricorsiva totale)
18/4/2018 Esempi di problemi decidibili e insiemi ricorsivi. 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" (il corrispondente insieme A_"P cappuccio" non ` ricorsivo). Indecidibilità del problema generale dell'arresto, dimostrazione
20/4/2018 Tecniche per dimostrare la non ricorsività di insiemi. 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. Relazioni ricorsive, esempi. La relazione R_P e sua ricorsività. Definizione di A_"P cappuccio" mediante R_"P cappuccio". Insiemi ricorsivamente numerabili, definizione ed algoritmi di parziale riconoscimento e metafora del libro
2/5/2018 Tre differenti caratterizzazioni degli insiemi ricorsivamente numerabili, dimostrazione della loro equivalenza. Insiemi ricorsivi contenuti propriamente nei ricorsivamente numerabili, dimostrazione. Insieme A e suo complemento ricorsivamente numerabili implica A ricorsivo, dimostrazione. Insieme dell'arresto A_"P cappuccio" non ricorsivo ma ricorsivamente numerabile, dimostrazione
4/5/2018 Complemento di A_"P cappuccio" non ricorsivo e non ricorsivamente numerabile. Panoramica finale della gerarchia ricorsivi-ricorsivamente numerabili. Proprietà di chiusura degli insiemi ricorsivi e ricorsivamente numerabili. Esercizi su tecniche di dimostrazione di ricorsività e ricorsiva enumerabilità di insiemi. Sulla ricorsività e ricorsiva enumerabilità di insiemi che differiscono su un insieme finito di elementi
9/5/2018 Teoria della complessità, motivazioni ed oggetto, il "come": risorse di calcolo, loro definizione e misurazione, efficienza. Elementi di teoria dei linguaggi. Il modello di calcolo della macchina di Turing deterministica (mdT), definizione intuitiva e linguaggio accettato
11/5/2018 Definizione formale di mdT. Mossa, computazione, linguaggio accettato da una mdT. Configurazione in una mdT, computazione come sequenza di configurazioni 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
16/5/2018 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. Notazione "O" per la valutazione del tasso di crescita di funzioni Complessità logaritmiche, lineari, polinomiali, esponenziali, esempi. Esempi di complessità in tempo per il riconoscimento di linguaggi, il caso delle palindrome
18/5/2018 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 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
23/5/2018 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

Torna alla pagina del corso

Carlo Mereghetti, Beatrice Palano
Dipartimento di Informatica
Università degli Studi di Milano
via Comelico 39, 20135 Milano, Italy