Obiettivi
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.
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 di sistemi, sicurezza e crittografia, i corsi di linguaggi e compilatori, intelligenza artificiale, deduzione automatica, semantica, modelli di calcolo non convenzionali, etc.
Programma del Corso (~52h)
Automi e linguaggi formali (circa 25h):
- Linguaggi formali e grammatiche generative
- Classificazione di Chomsky
- Linguaggi regolari e ASF
- Linguaggi liberi da contesto, forme normali e Automi a Pila
- Linguaggi dipendenti da contesto (cenni)
- Nozione intuitiva di algoritmo
- Modelli formali per il calcolo:
- Macchine di Turing/funzioni ricorsive e programmi for-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. Teorema di Post
- Teoremi di Ricorsione e Teorema di Rice
- Riducibilità funzionale: Insiemi creativi e produttivi
Modalità d’esame e progetti per la parte di Linguaggi.
Esame scritto della durata di circa 2h. L’esame è sempre composto da due parti corrispondenti alle due parti del corso. Coloro che conseguono allo scritto un voto superiore a 18 possono verbalizzare direttamente il voto conseguito fino ad un massimo di 25. Per Ottenere un voto più alto o per confermare un voto più alto di 25 ottenuto allo scritto, è necessario svolgere un orale. L’orale è quindi obbligatorio solo per coloro che vogliono un voto maggiore di 25. Il voto dello scritto è ottenuto come media approssimata per eccesso del voto conseguito nelle due parti. Possono essere introdotti correttivi premianti per coloro che svolgono l’esame nei primi appelli (si veda a tal proposito i comunicati della pagina facebook del corso). Gli studenti possono sfruttare i vari appelli per recuperare o migliorare anche solo una parte dell’esame. La consegna di una sola parte rimpiazza il voto già ottenuto sulla corrispondente parte, anche se quest’ultimo era di valore superiore!! Coloro che desiderano recuperare una delle due parti, avendo già un voto soddisfacente nell’altra, devono consegnare il testo con gli esercizi della parte corrispondente entro la prima metà del tempo a disposizione per lo scritto. Consegnando oltre tale termine, si recuperano entrambe le parti ed il voto è la media dei voti ottenuti nelle due parti.
È prevista una sola prova parziale a Novembre che verte sulla prima parte del corso solamente ed è funzionale a metà del corso.
Gli orali si possono svolgere su appuntamento con il docente dopo aver conseguito almeno 18/30 allo scritto e comunque NON oltre il 1 Ottobre dell'anno solare corrente. Oltre tale data non sarà possibile svolgere l'esame orale. I voti conseguiti nell'A.A. X/Y sono validi fino e NON oltre il 1 Ottobre dell’anno Y. Chi avesse sostenuto l'esame e non avesse verbalizzato il voto entro tale data dovrà risostenere gli scritti per entrambe le parti nel successivo anno accademico.