Automata, Languages, and Computing
(Laurea Magistrale in Ing. Informatica - 1° anno)
Anno Accademico 2022-2023
Anni Accademici precedenti (corso di Informatica Teorica):
2018-2019
2019-2020
2020-2021
2021-2022
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: Maurizio Patrignani
In questa pagina potrete trovare:
- ALC - Avviso del 22/01/2023
Proposta di voto per le prove intermedie
Le valutazioni complessive delle prove intermedie sono reperibili qui:
ALC-2023-01-20-risultati.pdf.
Per accettare il voto delle prove intermedie è necessario:
- Inviare una mail a maurizio.patrignani@uniroma3.it specificando l'accettazione del voto
- Prenotarsi all'appello del 17 febbraio.
La verbalizzazione avverrà il 17 febbraio 2023.
|
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.
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:
- Mercoledì 2 novembre 2022, Aula N11, dalle 18:00 alle 19:00.
Testi: ALC-2022-11-02-prova1A-sol-corretto.pdf,
ALC-2022-11-02-prova1B-sol-corretto.pdf.
- Venerdì 11 novembre 2022, Aula N18, dalle 14:30 alle 16:00.
Testo: ALC-2022-11-11-prova2.pdf.
- Venerdì 2 dicembre 2022, Aula N18, dalle 14:30 alle 16:00.
Testo: ALC-2022-12-02-prova3.pdf.
- Venerdì 20 gennaio 2023, Aula N13 ed N14, dalle 10:00 alle 11:00 (data definitiva confermata).
Testo: ALC-2023-01-20-prova4.pdf.
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