ANNO ACCADEMICO 2014/2015
Lezione 2 marzo 2015 ore 10.30-12.30 Aula D1
Introduzione al contenuto del Corso. Considerazioni generali sul rapporto tra matematica e informatica. L'emergere della teoria della calcolabilità. Trasparenze Informazioni Lezione 3 marzo 2015 ore 12.30-13.30 Aula D1 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 3 marzo 2015 ore 14.30-17.00 Aula 5 DMI Seminario integrativo tenuto dai dottori Marco Tabacchi, Valerio Perticone e Michele Fiordispina Una introduzione "interattiva" agli automi finiti. Gli automi deterministici a stati finiti sono stati illustrati utilizzando un’applicazione ludica su piattaforma mobile che utilizza la teoria dei DFA come meccanismo sottostante. L’applicazione può essere scaricata cliccando su: iOS Android Lezione 4 marzo 2015 ore 11.30-13.30 Aula D1 Lettura di altri passi dell'articolo originale di Turing. Definizione di Macchina di Turing (MdT). Primi esempi. Definizione di produttività di una Macchina di Turing. Definizione della funzione "produttività" p. Dimostrazione della non Turing calcolabilità della funzione p (Busy beaver problem). Trasparenze 1 Trasparenze 2 Lezione 5 marzo 2015 ore 14.30-17.00 aula 5 (DMI) 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. Trasparenze 1 Trasparenze 2 Lezione 6 marzo 2015 ore 11.00-13.00 aula D1 Predicati ricorsivi primitivi. Meccanismi di codifica ricorsivi primitivi. Trasparenze 1 Trasparenze 2 Lezione 9 marzo 2015 ore 10.30-12.30 aula D1 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. Trasparenze Lezione 10 marzo 2015 ore 12.30-13.30 Aula D1 Cenni a come usare i due meccanismi di codifica introdotti per codificare istruzioni e programmi. Lezione 10 marzo 2015 ore 14.30-17.00 Aula D1 Seminario integrativo del dottor Valerio Perticone e introdotto dal dottor Marco Tabacchi Esempi di MdT con implementazione utilizzando JFLAP. Lezione 11 marzo 2015 ore 11.30-13.30 Aula D1 Codifiche dei programmi. Il problema della fermata per i programmi di S. Definizione del predicato HALT. Dimostrazione della sua non calcolabilità in S Trasparenze Lezione 16 marzo 2015 ore 10.30-12.30 Aula D1 Presentazione del programma universale. Trasparenze Lezione 17 marzo 2015 ore 12.30-13.30 Aula D1 Codifiche e decodifiche di programmi di S. Esempi di funzionamento del programma universale. Lezione 18 marzo 2015 ore 11.30-13.30 Aula D1 Il predicato "contapassi". Sua calcolabilità in S. Definizione di insieme ricorsivamente enumerabile e di insieme ricordavo. Il teorema di Post. Esempi di insiemi ricorsivamente numerabili ma non ricorsivi e di insiemi neanche ricorsivamente enumerabili (TOT). Trasparenze Lezione 23 marzo 2015 ore 10.30-12.30 Aula D1 Il teorema s-m-n (o del parametro) di Kleene. Introduzione qualitativa ai linguaggi Sn e al linguaggio di Post-Turing. Trasparenze Lezione 24 marzo 2015 ore 12.30-13.30 Aula D1 I linguaggi Sn e il linguaggio di Post-Turing. Simulazione di S negli Sn e di un Sn in Post-Turing. Trasparenze Lezione 25 marzo 2015 ore 11.30-13.30 Aula D1 Dimostrazione dell'equivalenza computazionale tra tutti questi modelli di computo: linguaggi S, Sn, Post-Turing, Macchine di Turing classiche, MdT a quintuple, Mdt con nastro infinito in una sola direzione. Trasparenze Lezione 30 marzo 2015 ore 10.30-12.30 Aula D1 Processi di Thue e simulazione di MdT non deterministiche mediante processi di Thue. Definizione di grammatica. Equivalenza tra i linguaggi accettati da MdT non deterministiche e i linguaggi generati da grammatiche. Ricorsività primitiva degli operatori di derivabilità in una grammatica. Equivalenza tra linguaggi ricorsivamente enumerabili e linguaggi generati da una grammatica. Trasparenze Lezione 31 marzo 2015 ore 12.30-13.30 Aula D1 Varie caratterizzazioni degli insiemi ricorsivamente enumerabili. Enunciato del teorema della forma normale di Kleene. Trasparenze Lezione 1 aprile 2015 ore 11.30-13.30 Aula D1 Dimostrazione del teorema della forma normale di Kleene per funzioni di una variabile. Sua estensione alle funzioni di più variabili. Illustrazione di vari problemi insolubili. Cenno al X problema di Hilbert. Insiemi diofantei e insiemi ricorsivamente numerabili. I problemi del millennio come la riproposizione dei 23 problemi di Hilbert. Trasparenze 1 Trasparenze 2 Lezione 13 aprile 2015 ore 10.30-12.30 Aula D1 Il linguaggio LOOP (o CICLO). Dimostrazione dell'equivalenza tra le funzioni ciclo-calcolabili e le funzioni ricorsive primitive. Trasparenze 1 Trasparenze 2 Lezione 14 aprile 2015 ore 12.30-13.30 Aula D1 La profondità di nidificazione come misura di complessità. Dimostrazione dell'inverso del teorema di "limitazione alla crescita". Prime proprietà della famiglia di funzioni fn. Trasparenze Lezione 15 aprile 2015 ore 11.30-13.30 Aula D1 Proprietà di limitazione alla crescita del tempo di calcolo e dei valori delle variabili. Dimostrazione della non ricorsività primitiva della funzione di Ackermann. Presentazione di un programma che la calcola in S. Il linguaggio WHILE come estensione del linguaggio LOOP. Dimostrazione dell'equivalenza tra il linguaggio WHILE e il linguaggio S (e, quindi, sua equivalenza con le funzioni mu-ricorsive e quelle Turing calcolabili). Trasparenze 1 Trasparenze 2 Appunti Lezione 27 aprile 2015 ore 10.30-12.30 Laboratorio 1 Introduzione al Lisp. Gerarchia delle funzioni ricorsive aritmetiche in Lisp - Traccia del calcolo in Lisp - Liste: codifiche per evitare i numeri di Gödel. Appunti sul Lisp Lezione 28 aprile 2015 ore 12.30-13.30 Laboratorio 1 Funzioni ricorsive sulla lunghezza. Liste di liste, Funzioni ricorsive sulla struttura di liste. Predicati. Lezione 29 aprile 2015 ore 11.30-13.30 Laboratorio 1 Alberi, Simboli in Lisp. Calcolo simbolico in Lisp. Valutatore aritmetico. Definizione derivata simbolica. Esercizi Lisp delle prime tre lezioni Lezione 4 maggio 2015 ore 10.30-12.30 Laboratorio 1 Derivata simbolica. Semplificazioni algebriche. Derivata seconda ed n-esima. Valore della derivata in un punto. Funzionali. Schemi di programmi. Esercizi Lisp Scheda trasparenza Lezione 5 maggio 2015 ore 12.30-13.30 Laboratorio 1 Un predicato sulle funzioni: GETDEF. Confronto tra funzioni utente e funzioni standard. Valutatore generale per l'aritmetica con sostituzione. Misura tempo CPU Esercizi Lisp Lezione 6 maggio 2015 ore 11.30-13.30 Laboratorio 1 Valutatore generale aritmetico e liste senza sostituzione. Introduzione dell' "ambiente"; confronto tempo CPU, confronto programmi/dati, QUOTE. Valutatore generale per simboli. Valutazione delle strutture COND e QUOTE. Applicazione del Valutatore a se stesso. Confronto CPU della torre dei valutatori. Compilazione. MCD in linguaggio macchina, codice piatto. Confronto tempo CPU interpretato/compilato. Versione diversa "Appunti sul Lisp" Lezione 11 maggio 2015 ore 10.30-12.30 Seminario integrativo tenuto dal dr. Sergio Perticone Introduzione al lambda calcolo. Dal problema della decisione al LISP. Il lambda calcolo come modello computazionale; ma anche proto-linguaggio di programmazione, framework teorico per lo studio dei programmi e progenitore delle moderne tecniche di progettazione software. Trasparenze Lezione 12 maggio 2015 ore 12.30-13.30 Seminario integrativo tenuto dal dr. Mattia Di Gangi Introduzione alla logica fuzzy. Trasparenze Lezione 13 maggio 2015 ore 11.30-13.30 Seminario integrativo tenuto dal dr. Valerio Perticone Nuovi modelli di computo. Gli automi cellulari e il gioco della vita di Conway. Trasparenze. Lezione 25 maggio 2015 ore 11.30-13.00 Seminario integrativo tenuto dagli studenti Giacomo Calcara e Francesco Di Stefano Magic Turing Machine - La Turing completezza di un gioco noto. Trasparenze |
AVVISI
|