| Data | Argomento |
| 27/2/2019 | 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 |
| 1/3/2019 | 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 |
| 6/3/2019 | 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 |
| 13/3/2019 | Dimostrazione (intuitiva) dell'esistenza di funzioni non calcolabili, assunzioni intuitive DATI e PROG isomorfi a N. Numerabilità di NxN: definizione operativa ed analitica della funzione coppia di Cantor |
| 15/3/2019 | 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. Codifica di testi, suoni, immagini. Codifica di array, matrici, grafi, esempi |
| 20/3/2019 | 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. 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 |
| 22/3/2019 | 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 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 |
| 27/3/2019 | 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. Confronto tra potenze computazionali, il concetto di traduzione o compilazione, sua definizione formale e conseguenze. Costruzione induttiva del compilatore while -> RAM(con etichette), compilazione dei comandi di assegnamento |
| 29/3/2019 | Compilazione dei comandi while composti e forma finale 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. 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à |
| 3/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 |
| 5/4/2019 | 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. 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 |
| 10/4/2019 | 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. 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). Teorema S^1_1 e S^m_n |
| 12/4/2018 | Il concetto di sistema di programmazione accettabile, i tre assiomi (Rogers '58): 1) tesi di Church 2) interprete universale 3) teorema S^1_1. Nozione di compilatore: correttezza e completezza 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). Esistenza di compilatori completamente errati. Teorema di ricorsione, conseguenze: esistenza di Quine (esempio in C) e inesistenza di compilatori completamente errati. Dimostrazione del teorema di ricorsione. Uso del teorema di ricorsione per mostrare l'esistenza di programmi in spa (soluzione di equazioni in spa, esercizio) |
| 17/4/2019 | 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). 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 |
| 3/5/2019 | 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 |
| 8/5/2019 | 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 |
| 10/5/2019 | 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 |
| 15/5/2019 | 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. Definizione formale di mdT deterministica. 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 |
| 22/5/2019 | 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. Notazione "O" per la valutazione del tasso di crescita di funzioni Complessità logaritmiche, lineari, polinomiali, esponenziali, esempi. |
| 24/5/2019 | Esempi di complessità in tempo per il riconoscimento di linguaggi, il caso dei numeri pari e delle palindrome. 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 |
| 29/5/2019 | 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 |
| 31/5/2018 | Problemi di difficile soluzione generale ma di facile "verificabilità", esempi: CNF-SAT, HC (Hamiltonian Circuit), 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)) |
| 3/6/2019 | Relazioni con DTIME(f(n)), determinizzazione di algoritmi. 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. |
| 5/6/2019 | Discussione sul significato di NP-completezza. 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 |