Calcolabilità e complessità – corsi A-L e M-Z (laurea Informatica, a.a. 2022-2023)

Prego tutti di non contattarmi con problematiche relative a propedeuticità, prenotazioni, supposti malfunzionamenti di Esse3, ritardi; non sono io a dover prenotare i vostri esami e spetta a voi controllare di avere i requisiti adatti per accedere alle prove di esame.

La dottoressa Cives, il nostro manager didattico, è la persona a cui rivolgersi.

Docente: Emanuele Covino (emanuele.covino@uniba.it – 0805442142 – V piano Dip. Informatica)

Ricevimento: inviate una mail per concordare data e orario del ricevimento.

Codice per Teams 7lk7w54; Password per ADA CCab-2223;

Programma preliminare e fonti di studio: qui

Testi consigliati:

· Sipser – Introduzione alla teoria della computazione – Maggioli

· Ausiello, D’amore, Gambosi - Linguaggi, modelli, complessità – Utet

· Hopcroft, Motwani, Ullman – Automi, linguaggi e calcolabilità – Addison-Wesley

· Aho, Lam, Sethi, Ullman – Compilatori: principi, tecniche e strumenti, II ed., Pearson

Altro materiale:

· Dispense su compilatori, analisi lessicale e sintattica (gentilmente fornite dal Dott. Luca Tesei)

· La pagina di Jflap; in particolare, studiare il tutorial e gli esercizi svolti

· Altri simulatori

· Slides usate a lezione (aggiornate al 2/3/2023 – NON studiate dalle slides, bensì dai libri)

· Slides su Jflap usate a lezione (1)(2)(3)

· Esercizi da svolgere su DFA, NFA, espressioni regolari

· Esercizi pumping lemma per i linguaggi regolari e chiusure regolari

· Esercizi da svolgere su MdT

· Progetto di una macchina di Turing universale (da realizzare)

· Alcune domande frequenti

· Il nostro corso, fatto da uno bravo.

Modalità di svolgimento dell’esame: (date su esse3)

La prova in itinere consiste in 4 esercizi; è valutata da 0 a 4 punti (valida fino ad aprile 2024).

Sarà corretta contestualmente alla correzione della prova scritta di ogni candidato.

La prova di laboratorio prevede la realizzazione di un automa o mdT che riconosce un linguaggio o calcola una funzione, utilizzando il software Jflap, e sarà corretta immediatamente dopo la fine della prova stessa. E’ valutata da 1 a 6 punti. Chi supera la prova di laboratorio può sostenere lo scritto (valida fino ad aprile 2024).

La prova scritta prevede esercizi e domande su tutti i temi presenti nel programma definitivo; la correzione della prova scritta avverrà (tranne casi eccezionali) immediatamente dopo la fine della prova stessa; la prova scritta è valutata fino 24 punti (e si intende superata se il voto è superiore a 14).

Se la somma dei voti (prova in itinere, laboratorio e scritto) è inferiore a 18 il candidato deve ripetere la prova scritta (conservando le valutazioni di prova in itinere e laboratorio).

Se la somma dei voti supera 18 il candidato può verbalizzare il voto conseguito.