Corso di Fondamenti dell'Informatica (Laurea Triennale in Informatica L-31)

Docente: Elena Zucca

Obiettivo

Presentare gli aspetti sintattici ed algoritmici dei linguaggi (riconoscimento di stringhe a seconda del tipo di linguaggio), e introdurre alcuni risultati chiave di calcolabilità (studio dell'espressività computazionale degli elaboratori), relativi alla decidibilità dei problemi, che ne definiscono potenzialità e confini.

Perché è importante?

La Teoria degli Automi e dei Linguaggi ha applicazioni ubique: modellazione di circuiti, linguaggi di programmazione e compilatori, trasformazioni di programmi e modelli di software, sistemi operativi e scripting, intelligenza artificiale e linguaggio naturale, database e semantic web, semantica, modellazione, analisi e verifica di sistemi sequenziali e concorrenti. Inoltre ha applicazioni in campi meno usuali come la biologia e la genetica (automi come modello del comportamento umano, ragionamento su sequenze DNA,...), nei sistemi industriali e robotica (sistemi ibridi).

La Teoria della Calcolabilità permette di capire cosa si può fare con un elaboratore e cosa invece non si può fare. In particolare dato un particolare problema fornisce metodi formali per capire se il problema ha una soluzione algoritmica completa ed effettiva o se si può risolvere solo in maniera parziale o approssimata. La calcolabilità quindi è propedeutica allo studio della complessità degli algoritmi. La teoria della calcolabilità è nata con il fondamentale lavoro On computable numbers, with an application to the Entscheidungsproblem di Alan Turing.

I contenuti del corso sono inseriti nel corso considerato core AL/Basic Automata Computability and Complexity del Computer Science Curriculum dell'ACM/IEEE (link).

Dal 15/16 prevede 6 CFU ed è al terzo anno mentre le precedenti edizioni erano di 9 CFU al secondo anno. Per effetto di questo cambiamento nell'anno 14/15 è stato silente.


AulaWeb a.a. 17/18

AulaWeb a.a. 16/17

AulaWeb a.a. 15/16

AulaWeb a.a. 13/14


Programma

  • Automi e Linguaggi
    • Alfabeti, stringhe, linguaggi, operazioni su linguaggi
    • Automi a stati finiti deterministici (DFA) e non deterministici (NFA)
    • Minimizzazione di DFA, espressioni regolari
    • Proprietà di chiusura dei regolari, pumping lemma
    • Grammatiche context-free, alberi di derivazione, ambiguità
    • Automi push-down deterministici e non deterministici
    • Equivalenza di PDA e grammatiche CF
    • Proprietà di chiusura dei linguaggi CF, pumping lemma
    • [Gerarchia di Chomsky, linguaggi context-sensitive, risultati di semi-decidibilità e decidibilità]
    • [Equivalenza di grammatiche lineari e automi a stati finiti]
  • Calcolabilità
    • Nozione di algoritmo e funzioni ricorsive primitive
    • Macchine di Turing e funzioni ricorsive
    • Tesi di Church-Turing, numerazione algoritmica delle funzioni ricorsive
    • Macchina di Turing universale e calcolatore
    • Problema dell'arresto, insiemi ricorsivi e ricorsivamente enumerabili, problemi decidibili e indecidibili
    • Riducibilità e teorema di Rice
    • Altri modelli di calcolo: funzioni mu-ricorsive, varianti delle macchine di Turing

    Testi di riferimento

    Le note delle lezioni sono disponibili su Aulaweb. Per approfondimenti potete consultare:

    Modalità d'esame

    Scritto e orale. Lo scritto consiste di due parti, ognuna della quali può non essere svolta da chi ha già superato il corrispondente compitino. I voti delle due parti fanno media, per superare l'esame scritto il voto di ognuna delle due parti deve essere >= 15 e il voto medio >= 18. Un voto sufficiente allo scritto può essere conservato per i due appelli successivi. I voti dei compitini valgono per tutto l'anno accademico.

    Esempi di esercizi d'esame

    Archivio esami

    Inoltre, trattandosi di argomenti standard, potete cercare online esercizi da analoghi corsi presso altre sedi.





    Ritorno alla pagina precedente

    Ultima modifica: 6 luglio 2017