Automata, Languages, and Computing
(Laurea Magistrale in Ing. Informatica - 1° anno)
Anno Accademico 2023-2024
Anni Accademici precedenti (corso di Informatica Teorica):
2019-2020
2020-2021
2021-2022
2022-2023
Corso Quantum Computing
Informazioni sugli obiettivi formativi, sui docenti, sull'orario delle lezioni e sul calendario
degli esami sono disponibili nella pagina del Collegio Didattico di Ingegneria Informatica.
Docente: Giuseppe Di Battista
In questa pagina potrete trovare:
- ALC - Avviso del 28/02/2024
Esame di febbraio 2024 - esiti
Gli esiti dell'esame sono stati inseriti su Gomp. Gli studenti che desiderano spiegazioni possono contattare il docente su Teams o per e-mail.
La verbalizzazione avverra' con il meccanismo del silenzio-assenso.
|
- ALC - Avviso del 20/02/2024
Esame di febbraio 2024 - aula
L'esame del 23 febbraio si terrą in Aula N13.
|
- ALC - Avviso del 24/1/2024
Valutazione in itinere ed esame di febbraio 2024
Gli studenti che intendono usufruire del voto ottenuto nelle prove intermedie come voto per l'esame di febbraio devono:
(1) iscriversi all'esame su Gomp e (2) spedire al docente, entro e non oltre il 16/2, un apposito messaggio.
Il messaggio deve avere come subject: ALC - voto prove in itinere.
Il messaggio deve contenere nel body una frase nella quale si dice esplicitamente di accettare il voto ottenuto nella valutazione
in itinere, menzionando esplicitamente il voto. La verbalizzazione avverra' il 23/2 o nei giorni immediatamente seguenti.
|
Archivio avvisi
Il programma di massima del corso di Automata, Languages, and Computing è il seguente:
- Proprietà elementari dei linguaggi: operazioni su linguaggi, operatore
di Kleene, espressioni regolari, cardinalità dei linguaggi
- Grammatiche formali: grammatiche di Chomsky, produzioni, riconoscimento di linguaggi.
- Linguaggi regolari: automi a stati finiti, relazioni tra automi e linguaggi regolari, pumping
lemma, chiusura dei linguaggi regolari, espressioni regolari e linguaggi regolari, decidibilità
e linguaggi regolari, teorema di Myhill-Nerode.
- Linguaggi non contestuali: automi a pila non deterministici, relazioni tra automi e linguaggi CF,
pumping lemma, chiusura e decidibilità, ambiguità.
- Macchine di Turing (MT) e Turing calcolabilità: funzionamento delle MT, MT multinastro,
MT non deterministiche, descrizione linearizzata delle MT, MT universale, il problema della fermata,
calcolabilità secondo Turing, teorema di Rice, linguaggi di tipo 0 e MT.
- Teoria della complessità: tipologie di problemi, problemi di decisione, complessità
e problemi di decisione su linguaggi, classi di complessità, relazioni
elementari tra classi di complessità, riducibilità, completezza, la classe NP, NP-completezza,
esempi di problemi NP-completi. La classe PSPACE.
|
Materiale didattico (i link inattivi corrispondono a materiale in corso di revisione)
|
- I testi consigliati (non considerati indispensabili) sono:
- Slide del corso di Automata, Languages, and Computing:
Prova scritta
L'esame è costituito da una prova scritta. Per sola comodità di erogazione, tale prova è
suddivisa in due parti relative al primo e al secondo modulo
Valutazione in itinere
Alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie).
- Solo gli studenti di "Automata, Languages and Computing" possono fruire della valutazione in intinere.
Per gli studenti del corso spento di Informatica Teorica non è prevista.
- La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale,
tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente
- il voto della valutazione in itinere.
- Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato
esclusivamente nella prima sessione d'esame di febbraio 2022.
- Si prevedono 4 prove intermedie in tutto, distribuite nel primo semestre. Il programma di
ciascuna prova comprende tutto il programma svolto dal primo giorno di lezione fino alla lezione
immediatamente precedente la prova. Il voto finale si otterrà facendo la media dei voti delle
singole prove dopo aver scartato il voto più basso (oppure, non considerando la prova a cui
lo studente è stato assente).
- Le date (preliminari e soggette a conferma) delle prove intermedie sono le seguenti:
- Venerdì 3 novembre 2023, Aula N18, dalle 16:00 alle 18:00.
Risultati
- Venerdì 17 novembre 2023, Aula N18, dalle 17:00 alle 19:00.
Risultati
- Venerdì 15 dicembre 2022, Aula N18, dalle 16:00 alle 18:00.
Risultati
- Venerdì 19 gennaio 2024, Aula N18, dalle 16:00 alle 18:00.
Risultati
Esempi di prove d'esame
Le seguenti prove d'esame si riferiscono al corso di Informatica Teorica I (Ord. D.M. 509/99), corrispondente grosso modo alla prima parte del corso attuale, e sono fornite a titolo d'esempio.
- Prove d'esame di Informatica Teorica I (Ord. D.M. 509/99):
Le seguenti prove d'esame si riferiscono al corso di Informatica Teorica II (Ord. D.M. 509/99), corrispondente grosso modo alla seconda parte del corso attuale, e sono fornite a titolo d'esempio.
- Prove d'esame di Informatica Teorica II (Ord. D.M. 509/99):
Automata, Languages, and Computing
/ A cura di Giuseppe Di Battista
e Maurizio Patrignani / 22 settembre 2021