Corso di recupero
anno accademico 2011/2012
"One
day, ladies will be walking their computers in the park and saying 'do you
know, my little computer said a very funny thing to me this morning!'"
Alan
Turing, 1951
"Turing
is a fascinating and controversial figure who lived before his time. He's an
incredibly inspiring character who deserves to be a hero beyond the world of
the technophiles, who already sit at his feet." Julia Harrington
Le lezioni avranno luogo
secondo il seguente orario (per un totale di 24 ore):
· Lunedì 11-13, Aula F2
· Giovedì 14-16, Aula F2
Testi di riferimento:
1.
[HMU] J. Hopcroft, R. Motwani, J. Ullman, Automi,
linguaggi e calcolabilità, Addison Wesley Pearson
Education Italia s.r.l,
2003 (titolo della versione in inglese: Introduction to Automata Theory, Languages, and Computation,
Addison Wesley, 2001).
2.
G. Ausiello, F.
D’Amore, G. Gambosi, Linguaggi, Modelli, Complessità, F. Angeli Ed., 2003.
3. Hartley
Rogers, Theory of recursive functions and effective computability, Mc Graw-Hill Book Company
4.
[Dispense1] A. Dovier, R. Giacobazzi, Fondamenti dell’Informatica: Linguaggi
Formali, Calcolabilità e Complessità, http://users.dimi.uniud.it/~agostino.dovier/DID/dispensa.pdf
5. [Dispense2] Marcello Frixione, Dispense di teoria della ricorsivita'
e calcolabilita' effettiva, http://www.dif.unige.it/epi/hp/frixione/appunti_computabilita.pdf
L’orario di ricevimento lo trovate qui.
Calendario provvisorio delle lezioni
Lezione 1 - Lunedì 16 Aprile: Presentazione del corso. Automi a pila: definizione
ed esempi.
Lezione 2 - Giovedì 19 Aprile: Automi a pila: automi deterministici,
relazioni fra le classi definite.
Lezione 3 - Lunedì 23 Aprile: Automi a pila: equivalenza dei due modi di
accettazione. Esercizi consigliati: da questo elenco.
Lezione 4 - Giovedì 26 Aprile: Automi a pila
e linguaggi context-free. La macchina di Turing: definizioni e esempi. Eccone
una!
Lunedì 30 Aprile: Ponte del
1 Maggio
Lezione 5 – Giovedì 3 maggio: Macchine di Turing multinastro e loro equivalenza. Macchine di Turing che calcolano funzioni: un esempio
Lezione 6 – Lunedì 7 maggio: Macchine di Turing deterministiche
e loro equivalenza. Linguaggi ricorsivi e ricorsivamente enumerabili. Esercizio
1 di giugno 2008. Esercizio 2 del 14 febbraio 2008.
Lezione 7– Giovedì 10 maggio: Enumerazione di stringhe e
di Macchine di Turing. Un linguaggio non ricorsivamente
enumerabile: il linguaggio diagonale.
Lezione 8– Lunedì 14 maggio: Problemi
indecidibili. Il linguaggio universale. Riduzioni e loro proprietà. Proprietà dei
linguaggi ricorsivi: teoremi sul complemento.
Lezione 9– Giovedì 17 maggio: I linguaggi Le ed
Lne. Il Teorema di Rice.
Lezione 10– Lunedì 21 maggio: Funzioni ricorsive
primitive: esempi, proprietà. Esercizio 3 di giugno 2008, da questo elenco.
Lezione 11– Giovedì 24 maggio: Derivazioni
di funzioni ricorsive primitive e diagonalizzazione.
La funzione
di Ackermann. Funzioni
parziali ricorsive. Esercizi 3 di gennaio 2008, luglio 2008, luglio 2009. AVVISO: Al termine della lezione sarà possibile fermarsi per svolgere
ulteriori esercizi.
Lezione 12– Lunedì 28 maggio: Teorema: ogni funzione Turing calcolabile è ricorsiva. Esercizio 4 di settembre
2008.
Esercitazione supplementare
-Giovedì 31 maggio (14-17). Teorema: ogni funzione ricorsiva è Turing
calcolabile. Svolgimento esercizi d’esame.
Prove di esame previste
NOTA Si ricorda che per sostenere le prove scritte degli
esami è indispensabile prenotarsi sul Sistema di Ateneo ESSE3
con almeno 5 giorni lavorativi di anticipo e che è altresì possibile e doveroso cancellare la propria prenotazione (anche
inviando una e-mail in tempo utile) qualora si decida di non partecipare, per
evitare un inutile spreco di risorse.
1. Pre-appello nel periodo 4 - 13 Giugno 2012: 7 13 giugno ore 9,
aula P11. Sono disponibili il compito e i risultati.
2. Primo appello nel periodo 14 Giugno
2012 – 5 Luglio 2012: 28 Giugno 2012 ore 9, aula P4. Ecco il compito e i risultati.
3. Secondo appello nel periodo 6 – 27
Luglio 2012: 13 Luglio 2012 ore 9, aula P4. Ecco il compito e i risultati.
4. Appello nel periodo 3 – 20 Settembre
2012: 13 Settembre 2012 ore 9, aula P4. Ecco il compito e i risultati. Chi volesse anticipare
l’orale al 17 in mattinata può contattarmi.
