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

Testo a )   Cap. 0

Linguaggi regolari

Testo a )   Cap. 1

Macchine di Turing

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

Decidibilità

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

Riduzioni

Testo a )   Cap 5 

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

(esclusi Teorema 5.2 e pp. 233-246)

Complessità

Testo a )   Cap. 7 (solo 7.1 e 7.2)

Testo 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 possono sostituire  il libro di testo,  non sono immuni da imperfezioni e non  coprono totalmente le lezioni svolte.

Slides:  Introduzione, Notazione, Automi Finiti (DFA e NFA), Espressioni Regolari e Pumping Lemma,   Macchine di Turing,  Calcolo di funzioni con Macchine di Turing,  Varianti MdT, Problemi di decisione, Decidibilità, Complessità (I parte), Complessità (II parte)

 

Esercitazioni: MdT,  Complessità

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

 

Ricevimento studenti ETC: tramite appuntamento via email.

Esami: Gli esami si svolgeranno in modalità a distanza per il tempo in cui permarrà l’emergenza epidemiologica da COVID-19. La prova,  scritta con carta e penna, prevede l’uso di Microsoft Teams + Zoom

Elementi di Teoria della Computazione, a.a. 2018-19