Elementi di Teoria della Computazione

(ETC)

Matricole DISPARI

 

Il corso è un'introduzione alla teoria della computazione. La finalità del corso è insegnare a ragionare con precisione sulla computazione ed a dimostrarne capacità e limiti. Gli argomenti includono automi a stati finiti, macchine di Turing, computabilità,  e  complessità computazionale.

 

PROGRAMMA  DEL CORSO 

 

Nozioni preliminari e Notazione

a)      Cap. 0

Linguaggi regolari

a)      Cap. 1

Macchine di Turing

a)      Cap. 3 (esclusi enumeratori pp. 189-190)

Decidibilità

a)      Cap.4  (escluse pp. 206-211)

Riduzioni

a)      Cap 5 

incluso il Teorema di Rice (Es. 5.16 e relativa soluzione)

(esclusi Teorema 5.2 e pp. 233-246)

Complessità

a)      Cap. 7 (solo 7.1 e 7.2)

b)      Cap. 8

Testi di riferimento:  

a)      Michael Sipser, Introduzione alla teoria della computazione, Maggioli.

b)      Jon Kleinberg, Eva Tardos,  Algorithm Design, Pearson

 I contenuti dei libri possono essere integrati con il materiale sottostante. Si sottolinea che le slides NON sostituiscono il libro di testo,  non sono immuni da imperfezioni e non coprono totalmente le lezioni svolte.

Slides:  Introduzione, Nozioni Preliminari, Notazione, Automi Finiti (DFA e NFA), Espressioni regolari e Pumping Lemma, Macchine di Turing, Computazione mediante MdT Problemi di decisione e linguaggi, Varianti Macchine di Turing, Decidibilità, Complessità I parte, Complessità II parte

 

Esercitazioni: Linguaggi regolari, MdT e decidibilità, Complessità

 

Esempi di prove: G11,  G14,  L14,  II11, II14,    Prova svolta

 


Ricevimento studenti ETC: Venerdì 16:00-17:00 oppure tramite appuntamento 


Elementi di Teoria della Computazione, a.a. 2015-16