LEZIONIAnno accademico 2015-16
Lezione martedì 6 ottobre 2015 ore 11.30-13.30 - Aula 2 Introduzione al contenuto del Corso. Considerazioni generali sul rapporto tra matematica e informatica. L'emergere della teoria della calcolabilità. Trasparenze Lezione mercoledì 7 ottobre 2015 ore 11.30-13.30 - Laboratorio 1 Ruolo cruciale svolto dall'articolo di A. M. Turing "On computable numbers with an application to the Entscheidungsproblem". Lettura commentata di alcuni passi significativi di questo lavoro. Trasparenze Articolo originale di Turing Lezione giovedì 8 ottobre 2015 ore 8.30-10.30 - Aula 2 La nozione di quadrupla. Definizione di Macchina di Turing (MdT) e di funzioni Turing calcolabili. Primi esempi. Usare le MdT per scrivere stringhe di simboli sul nastro. Definizione di produttività di una MdT. Definizione della funzione "produttività". Dimostrazione della non Turing- calcolabilità della funzione produttività (Busy Beaver Problem, dovuto a T: Rado). Suo corollario: il teorema della fermata per le MdT. Trasparenze Materiale aggiuntivo: Articolo di Tibor Rado "On Non-Computable Functions" Due articoli interessanti e chiari sulla funzione produttività, in italiano, apparsi sulla Lettera Matematica, si trovano sul sito di Matepristem. Lezione martedì 13 ottobre 2015 ore 11.30-13.30 - Aula 2 Le funzioni ricorsivi primitive. Definizione ed esempi. Riflessione sui modi in cui si può presentare il meccanismo di ricorsione. La funzione di Fibonacci. Il meccanismo di ricorsione a incastro. La funzione di Ackermann. Trasparenze1 Trasparenze2 Lezione mercoledì 14 ottobre 2015 ore 11.30-13.30 - Laboratorio 1 Predicati ricorsivi primitivi. Meccanismi di codifica ricorsivi primitivi. Codifica "coppia" e Codifiche (numeri) di Goedel. Definizione del linguaggio di programmazione S. Trasparenze1 Trasparenze2 Lezione giovedì 15 ottobre 2015 ore 8.30-10.30 - Aula 2 Il linguaggio di programmazione S. Definizione delle funzioni mu-ricorsive, come estensione proprio delle funzioni ricorsive primitive. Calcolabilità in S sia delle funzioni ricorsive primitive sia delle funzioni mu-ricorsive. Come codificare le istruzioni e i programmi di S. Trasparenze Lezione martedì 20 ottobre 2015 ore 11.30-13.30 - Aula 2 Il teorema della fermata. Il teorema del programma universale. Trasparenze1 Trasparenze2 Lezione mercoledì 21 ottobre 2015 ore 11.30-13.30 - Laboratorio 1 Esempi di codifiche e decodifiche di programmi, simulando il programma universale. Lezione giovedì 22 ottobre 2015 ore 8.30-10.30 - Aula 2 Il teorema contattassi. Insiemi ricorsivi e ricorsivamente enumerabili. Il teorema di Post che collega le due nozioni precedenti. Esempi di un insieme che è ricorsivamente enumerabile ma non ricordavo. Esempio di un insieme che non è neanche ricorsivamente enumerabile (l'insieme TOT dei numeri di codice delle funzioni totali). Trasparenze Lezione mercoledì 28 ottobre 2015 ore 11.30-13.30 - Laboratorio 1 I linguaggi Sn. I programmi di Post-Turing. Dimostrazione prime equivalenze di modelli di computo. Trasparenze1 Trasparenze2 Lezione giovedì 29 ottobre 2015 ore 8.30-10.30 - Aula 2 Completamento delle dimostrazioni di equivalenza tra MdT, MdT a quintuple, linguaggio S, linguaggi Sn, linguaggio di Post-Turing. Equivalenza tra MdT con nastro infinito in una e in tutte e due le direzioni. Trasparenze Lezione martedì 3 novembre 2015 ore 11.30-13.30 - Aula 2 Regole di produzione e sistemi di riscrittura (semi-Thue e Thue). Simulazione delle MdT non deterministiche in sistemi di riscrittura. Trasparenze Lezione mercoledì 4 novembre 2015 ore 11.30-13.30 - Laboratorio 1 Grammatiche. Rapporto tra linguaggi generate da una grammatica e insiemi ricorsivamente enumerabili. Equivalenza tra MdT deterministiche e non deterministiche. Lezione giovedì 5 novembre 2015 ore 8.30-10.30 - Aula 2 Varie caratterizzazione insiemi r.e. Teorema della forma normale di Kleene. Dimostrazione equivalenza tra mu-ricorsività e calcolabilità in S. Richiamo definizione di grammatica. Cenni alla gerarchia di Chomsky. Varie famiglie di automi e linguaggi. Il problema di corrispondenza di Post. Elenco di alcuni problemi indecidibili. Trasparenze1 Trasparenze2 Lezione martedì 10 novembre 2015 ore 11.30-13.30 - Aula 2 Dimostrazione dell'indecidibilità del teorema di corrispondenza di Post. Equazioni diofantee e il X problema di Hilbert. Trasparenze1 Trasparenze2 Trasparenze3 Articolo Hilbert 1900 Lezione mercoledì 11 novembre 2015 ore 11.30-13.30 - Laboratorio 1 Il linguaggio CICLO che calcola tutte e sole le funzioni ricorsivi primitive. Sua estensione. Il linguaggio WHILE. Trasparenze Articolo Meyer Ritchie Lezione giovedì 12 novembre 2015 ore 8.30-10.30 - Aula 2 Caratteristiche del linguaggio CICLO. La profondità di nidificazione come "misura di complessità". Teorema di limitazione alla crescita. Trasparenze Lezione martedì 24 novembre 2015 ore 11.30-13.30 - Aula 2 Ln come vera gerarchia. Dimostrazione della non ricorsività primitiva della funzione di Ackermann. Calcolabili in S della funzione di Ackermann. Dimostrazione equivalenza tra il linguaggio S e il linguaggio WHILE. Trasparenze Appunti sul linguaggio Ciclo Lezione mercoledì 25 novembre 2015 ore 11.30-13.30 - Laboratorio 1 Inverso del teorema di limitazione alla crescita. Problemi della complessità. La tesi di Cook-Karp. Calcolabilità in tempo polinomiale. I problemi P e NP. Problemi NP completi. P versus NP: uno dei problemi del Millennio del Clay Institute. Trasparenze1 Trasparenze2 Lezione giovedì 26 novembre 2015 ore 8.30-10.30 - Aula 2 Il teorema di Cook. SAT è NP completo. Trasparenze Lezione martedì 1 dicembre 2015 ore 11.30-13.30 - Aula 2 Seminari svolti dagli studenti su argomenti già svolti ma presentati in modo creativo e innovativo con possibili aggiunte e nuovi collegamenti proposti da loro e discussi poi in aula. Lezione mercoledì 2 dicembre 2015 ore 11.30-13.30 Laboratorio 1 La teoria della complessità di Blum. Il teorema del collegamento ricorsivo. Il teorema della lacuna. Il teorema dell'accelerazione. Trasparenze1 Trasparenze2 Lezione giovedì 3 dicembre 2015 ore 8.30-10.30 - Aula 2 La Teoria della calcolabilità come sfondo teorico e tecnico per i progetti dell'I.A. Un confronto tra le idee pionieristiche di Turing della fine degli anni '40 e i progetti di oggi. Articoli Turing Lezione mercoledì 9 dicembre 2015 ore 11.30-13.30 Laboratorio 1 Seminari svolti dagli studenti su argomenti già svolti ma presentati in modo creativo e innovativo con possibili aggiunte e nuovi collegamenti proposti da loro e discussi poi in aula. Lezione giovedì 10 dicembre 2015 ore 8.30-10.30 - Aula 2 Costruttivismo versus Ricorsività. L'impostazione di Bishop della matematica costruttiva. La visione dell'Universo come struttura "computabile". I nuovi tentativi fondazionali di Voevodsky. Si vedano: - Errett Bishop, Foundations of Constructive Analysis, McGraw-Hill (1967), nuova edizione - Hector Zenit (ed), A Computable Universe, World Scientific (2013) - V. Voevodsky, Bernays Lectures sul suo sito: https://www.math.ias.edu/vladimir/Lectures (Lectures N° 7) - Stefano Leonesi, Carlo Toffalori, e Samanta Tordini - Matematica, miracoli e paradossi sito: http://matematica.unibocconi.it/articoli/matematica-miracoli-e-paradossi Lezione martedì 15 dicembre 2015 ore 11.30-13.00 - Aula 2 Ultimo seminario svolto dagli studenti secondo le stesse modalità dei precedenti. |
AVVISI
|