ANNO ACCADEMICO 2012/2013
Prime conclusioni sulla ricorsività primitiva. Le funzioni di Fibonacci e di Ackermann.
Teorema della fermata.
Enunciato e inizio dimostrazione del teorema del parametro (s-m-n).
Linguaggi di Post-Turing e calcolabilità in S.
Equivalenza tra S e funzioni mu-ricorsive. MdT con nastro infinito in una sola direzione.
Proprietà di limitazione alla crescita del tempo di calcolo e dei valori delle variabili.
Il linguaggio WHILE come estensione di LOOP. Dimostrazione della sua equivalenza con S, mu-ricorsive e MdT.
La teoria della complessità astratta di Manuel Blum: Presentazione
|
INFORMAZIONI UTILILibri di testo consigliati:
• M. Davis, E. J. Weyuker, (1983). Computability, complexity, and languages: Fundamentals of theoretical computer science. Acad. Press. (fondamentalmente i capitoli 1-7 e 13-14) • G. Boolos, R. Jeffrey. (1994). Computability and Logic. Cambridge University Press. (fondamentalmente i capitoli 1-5) Software utilizzato e suggerito • Simulatore di Macchine di Turing: JFLAP • Per accedere alla macchina remota (IP: 147.163.15.178), da Windows utilizzare PuTTY inserendo le vostre credenziali. Ricordiamo che per accedere alla macchina da una rete esterna a quella di ateneo si richiede la configurazione della VPN. • Chi è interessato può scaricare OpenLisp e CLISP. Si osservi però che sono dialetti del Lisp leggermente differenti da quello utilizzato nel corso (Le-Lisp). N.B. Gli esercizi del corso, per essere valutati, devono essere necessariamente eseguiti sulla macchina remota. Materiale utile: • Il libro SICP e le relative videolezioni di Abelson e Sussman Le lezioni si tengono: • Lunedì - ore 14-16 (Laboratorio B) • Martedì - ore 11-12 (Aula D2 - Consorzio Agrario) • Mercoledì - ore 12-14 (Laboratorio B) AVVISI
Il docente del corso può essere contattato via e-mail all'indirizzo: [email protected] Per questioni relative alle esercitazioni contattare: [email protected] |