Foundations of Computing (2004/2005)

Course Not running, not visible

Course code
4S00005
Name of lecturer
Roberto Giacobazzi
Number of ECTS credits allocated
6
Other available courses
Language of instruction
Italian
Location
VERONA
Period
First four-month term for the second year onwards dal Sep 27, 2004 al Nov 26, 2004.
Web page
http://profs.sci.univr.it/~giaco/fondamenti3.html

Lesson timetable

Learning outcomes

Obiettivi formativi: Scopo del corso è quello di fornire gli strumenti formali e le nozioni fondamentali per studiare problemi trattabili e non mediante calcolatore. Il corso è strutturato in 2 parti. Nella prima parte viene presentata la teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione. La seconda parte delinea i concetti e la natura dei problemi che ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante calcolatore.

Propedeuticità consigliate: Il corso ha come prerequisiti i corsi del I e II anno. Esso è propedeutico per tutti i corsi di informatica teorica, in particolar modo per i corsi di complessità, analisi e verifica automatica di sistemi, sicurezza e crittografia, i corsi di linguaggi e compilatori, intelligenza artificiale, deduzione automatica, semantica, modelli di calcolo non convenzionali, etc.

Syllabus

* Automi e linguaggi formali (20h):
Linguaggi e grammatiche
Automi a stati finiti e linguaggi regolari
Linguaggi liberi da contesto, forme normali e automi a pila
Classificazione di Chomsky (cenni)

* Calcolabilità (25h):
Nozione intuitiva di algoritmo
Modelli formali per il calcolo:
Macchine di Turing/funzioni ricorsive/programmi While
Tesi di Church
Goedelizzazione, Universalità e Teorema s-m-n
Problemi solubili e non: problema della terminazione
Metaprogrammazione: compliazione, interpretazione e specializzazione
Insiemi ricorsivi e r.e.
Teoremi di Ricorsione e Teorema di Rice
Riducibilità funzionale: Insiemi completi, creativi e produttivi

Assessment methods and criteria

Esame scritto ed orale. Voto minimo di ammissione all'orale: 16. Il voto dello scritto è valido per l'ammissione all'orale solo nell'arco dell'Anno Accademico di riferimento, ovvero una volta scaduto tale termine (ultimo appello di Ottobre) lo scritto deve essere risostenuto al fine di essere ammesso all'orale.

Teaching aids

Documents