WebHome < Calcolabilita

Tags: view all tags

<table border="2"> <tbody> <tr valign="top"> <td width="70%">

<center>

<b><font color="#107D1D"><font size="+3">Automi, Calcolabilità e Complessità</font></font></b>
<br /><b><font size="+1">a.a. 2019/2020</font></b></center>

<b><font color="#191A91"><font size="+2"> Prof. EMANUELA FACHINI </font></font></b>
<br /><b>STUDIO: </b> D.to Scienze dell'Informazione Via Salaria,113 - 00198 ROMA
<br /><b>TEL:</b> 0649918314.
<br /><b>E-MAIL:</b> fachini[AT]di.uniroma1.it
<br /><b><font color="#0E4F10">ORARIO DI RICEVIMENTO: </font></b>
<b><font color="#191799"><font size="+1"> Mercoledì </font> ore 10,30-12,30  o su appuntamento.</font></b>


<hr width="100%"></hr>
<b> [[#diario][<font size="+1"><font color="#2D1585">Diario delle lezioni dell'a.a. 2019/2020</font></font>]]</b>


<b> [[#diario18][<font size="+1"><font color="#2D1585">Diario delle lezioni dell'a.a. 2018/2019</font></font>]]</b>
<b> [[#diario17][<font size="+1"><font color="#2D1585">Diario delle lezioni dell'a.a. 2017/2018</font></font>]]</b>
<b> [[#diario16][<font size="+1"><font color="#2D1585">Diario delle lezioni di Calcolabilità e Complessità dell'a.a. 2016-2017</font></font>]]</b>
<b> [[#diario15][<font size="+1"><font color="#2D1585">Diario delle lezioni dell'a.a. 2015-2016</font></font>]]</b>

<hr width="100%"></hr>
<b> [[#Avvisi][<font size="+1"><font color="#2D1585">Avvisi per gli studenti</font></font>]]</b>
<u>
<b> [[#Presentazione][<font size="+1"><font color="#2D1585">Presentazione del corso</font></font>]]</b></u>

<u>
<b> [[#Info][<font size="+1"><font color="#2D1585">Informazioni generali: lezioni, libro di testo, esercizi proposti nelle sedute di esami, valutazioni degli esami appelli a.a. 2016/2017. </font></font>]]</b></u>

<u>
<b> [[#obiettivi][<font size="+1"><font color="#2D1585">Obiettivi e risultati attesi</font></font>]]</b></u>

<u>
<b> [[#progr][<font size="+1"><font color="#2D1585">Programma del corso</font></font>]]</b></u>


<br /><a NAME="Avvisi"></a><b><u><font size="+1"><font color="#2D1585">Avvisi</font></font></u></b>

<b><font color="#107D1D"><font size="+1"> Appello di ottobre </font></font></b>

Qui la valutazione della prova scritta [[%ATTACHURL%/ValACCstraordOtt20.pdf][ValACCstraordOtt20.pdf]].



<b><font color="#107D1D"><font size="+1"> Appello di settembre </font></font></b>

 
Il testo:  [[%ATTACHURL%/_ACC17Sett20_17.01.07.pdf][_ACC17Sett20_17.01.07.pdf]] e la valutazione:
 [[%ATTACHURL%/ValACCsett20.pdf][ValACCsett20.pdf]].
La soluzione: [[%ATTACHURL%/SolACC17Sett20.pdf][SolACC17Sett20.pdf]].


<b><font color="#107D1D"><font size="+1">Testo prova di luglio </font></font></b>

Qui il testo: * [[%ATTACHURL%/ACC8Lu2020.pdf][ACC8Lu2020.pdf]].

<b><font color="#107D1D"><font size="+1">testo prova di giugno </font></font></b>

Qui il testo  [[%ATTACHURL%/ACC17Giu20.pdf][ACC17Giu20.pdf]].


<b><font color="#107D1D"><font size="+1">Aggiornamento sull'appello di giugno </font></font></b>

L'appello ora è aperto su infostud. La prova scritta si svolgerà il 17 giugno 2020 eventualmente su più turni di cui il primo dalle 10 alle 12. Le prenotazioni chiudono il 10 giugno.
<p>
L'esame scritto di giugno (terza settimana di giugno per ACC) si svolgerà certamente da remoto. E' da premettere che, per ragioni tecniche, sarà possibile somministrare lo scritto a non più di 25-30 studenti contemporaneamente e, pur prevedendo sessioni parallele, dovremo ripetere l'intera procedura (con un testo d'esame diverso) fino all'esaurimento di tutti i prenotati, eventualmente anche su giorni diversi. E' importante perciò che ogni studente si prenoti all'esame solo se si sente preparato e ragionevolmente certo di superarlo: prenotarsi tanto per vedere come vanno le cose rischierebbe infatti di allungare ulteriormente i tempi dell'appello, impedendo magari a qualche vostro collega di poter sostenere tutti gli esami che aveva programmato. Ci appelliamo al vostro senso di responsabilità. 
<b> Le prenotazioni su Infostud saranno chiuse una settimana prima della data prevista per lo scritto (è indispensabile per avere il tempo di organizzare tutto quanto necessario); Non sarà possibile accedere all'esame senza la prenotazione e non sarà possibile prenotarsi dopo la chiusura della prenotazione.</b>

<b> Attrezzature necessarie </b>

Verificate di possedere le attrezzature elencate nel seguito e che esse funzionino correttamente.
- Collegamento a Internet stabile e di qualità sufficiente a mantenere attiva una sessione di exam.net sul PC ed una sessione Zoom sul cellulare. In sua assenza non sarà possibile svolgere l'esame. 
- Telefono cellulare che sia in grado di collegarsi a Internet. In sua assenza non sarà possibile svolgere l'esame. 
- PC fisso o portatile con Sistema operativo Windows o Mac OS e dotato di webcam e microfono, browser web Google Chrome (preferibile, altrimenti anche altro browser).
SE NON SIETE IN GRADO DI AVERE ALL'ESAME UN PC CON SISTEMA OPERATIVO WINDOWS O MAC OS FATEMELO SAPERE AL PIU' PRESTO!

<b>Azioni da compiere </b>

Se non lo avete già fatto per altri esami, dovete installare i seguenti software:
- Client Zoom, da installare sullo smartphone (e anche sul pc se l'audio dello smartphone non funziona a dovere); - SEB (Safe Exam Browser), da installare solo sul PC con sistema operativo Mac OS o Windows.
Inoltre, se non lo avete già fatto per altri esami, caricate su Infostud un vostro documento in corso di validità.

<b>Sessioni di prova </b>

Appena noto il numero degli studenti che intendono presentarsi allo scritto di giugno, sarà organizzata una simulazione dell'esame, in modo che vi possiate impratichire sull'uso di Zoom, sull'uso di SEB (Safe Exam Browser) e della piattaforma exam.net sul PC.
Durante la seduta di prova :
vi saranno illustrate le varie fasi dell'esame; sarà messo punto il posizionamento del cellulare; usando il pc vi collegherete a exam.net inserendo il codice dell'esame di prova che vi verrà fornito; si avvierà automaticamente SEB e avvierete l'esame di prova, al fine di impratichirvi con l'interfaccia utente di exam.net.

<b> Inquadratura della postazione di lavoro mediante cellulare </b>

Il vostro cellulare dovrà essere posizionato in modo da inquadrare la vostra postazione di lavoro da una distanza di circa due metri: deve essere visibile la vostra persona, lo schermo del PC, il piano della scrivania, la parte inferiore della scrivania e, possibilmente, la porta della stanza che deve rimanere chiusa durante l'esame. Poiché tale inquadratura sarà visibile anche agli altri partecipanti, vi invitiamo a predisporla in modo che non violi la vostra privacy. Approfittate dei prossimi giorni per fare delle prove.



<b><font color="#107D1D"><font size="+1">testo prova del 4  maggio 2020</font></font></b>

 [[%ATTACHURL%/ACC4Maggio20.pdf][ACC4Maggio20.pdf]].
 


<b><font color="#107D1D"><font size="+1">valutazione prova del 3  febbraio 2020</font></font></b>

Qui i voti:  [[%ATTACHURL%/MatACC3Feb2020.pdf][MatACC3Feb2020.pdf]], le persone non elencate sono risultate insufficienti.

<b><font color="#107D1D"><font size="+1">testo della prova del 13 gennaio e de 3 febbraio 2020 </font></font></b>

 [[%ATTACHURL%/ACC13Gen20.pdf][ACC13Gen20.pdf]], [[%ATTACHURL%/ACC3Feb20.pdf][ACC3Feb20.pdf]].

<b><font color="#107D1D"><font size="+1">Avviso appello gennaio: la valutazione  </font></font></b>

Qui trovate i risultati di coloro che hanno completato l'esame eseguendo uno o due esercizi. Il file comprende anche coloro che avevano già ottenuto la sufficienza con gli esoneri   [[%ATTACHURL%/MatACC13Gen20EsParziale.pdf][MatACC13Gen20EsParziale.pdf]]
Chi volesse esaminare il proprio elaborato può presentarsi dalle 10,30 alle 13 del prossimo mercoledì mattina. 

Qui invece i risultati di coloro che si sono presentati a sostenere l'esame completo e che hanno ottenuto la sufficienza. [[%ATTACHURL%/ACC13Gen20EsameCompleto.pdf][ACC13Gen20EsameCompleto.pdf]]. Chi non si trova in questo elenco consulti l'altro, se non si trova in alcun elenco allora è insufficiente.
Chi volesse esaminare il proprio elaborato può presentarsi dalle 10,30 alle 13 del prossimo venerdì mattina, previo invio di email per prenotarsi entro giovedì.

<b><font color="#107D1D"><font size="+1">La valutazione finale</font></font></b>

 [[%ATTACHURL%/MatElEserciziAula19.pdf][MatElEserciziAula19.pdf]].

Coloro che intendono migliorare il voto presentandosi durante l'appello di gennaio dovranno prenotarsi su infostud ma anche in una pagina su TWiki che predisporrò domani con la possibilità di indicare quale/i esercizi si intendono riaffrontare. Coloro che intendono migliorare il voto con un colloquio possono farmelo sapere per email e fisseremo una data. 
Tutti  potranno prendere visione dei loro elaborati martedì 7 gennaio alle 10,30. Coloro che entro questa data non  mi avranno fatto sapere nulla vedranno il loro voto registrato su infostud.

<b><font color="#107D1D"><font size="+1">Organizzazione prossimi esoneri e testi del primo</font></font></b>

Qui i testi dell'esercitazione dell'11 dicembre:
 [[%ATTACHURL%/ACC4Dic11RidV1_.pdf][ACC4Dic11RidV1_.pdf]], [[%ATTACHURL%/ACC4Dic11V2.pdf][ACC4Dic11V2.pdf]], [[%ATTACHURL%/ACC4Dic11V1.pdf][ACC4Dic11V1.pdf]].


Gli studenti presenti nei due elenchi qui sotto  affronteranno l'ultimo esercizio in aula sulla complessità il giorno 11 dicembre in orario di lezione.
 [[%ATTACHURL%/PresRidRec11Dic19.pdf][PresRidRec11Dic19.pdf]],
 [[%ATTACHURL%/PresPrenUltimoEs11Dic2019.pdf][PresPrenUltimoEs11Dic2019.pdf]]. Gli studenti del primo elenco sosterranno anche un secondo esercizio di recupero sulle riduzioni dopo avere svolto il primo.

Gli studenti qui elencati posso presentarsi il 16 dicembre in orario di lezione per sostenere un esonero di recupero su ciascuna delle tre parti sulla quale sono risultati insufficienti. In particolare chi ha l'insufficienza su entrambi gli esercizi sui linguaggi formali potrà svolgere un esercizio per superare le due insufficienze. Chi ha una sufficienza su uno dei due esercizi sulla teoria dei linguaggi formali può svolgere solo i due esercizi di calcolabili e complessità. [[%ATTACHURL%/PresRecupero16Dic19.pdf][PresRecupero16Dic19.pdf]].

Infine i non frequentanti possono prenotarsi per il secondo esonero seguendo questo link. : http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2019_12_16_IIEsoneroACC. Coloro che sono presenti nell'elenco degli ammessi all'esonero del 16 dicembre non devono prenotarsi.
Si fa presente che chi risultasse insufficiente a questo esonero in modo grave (voto inferiore a 12/30) non potrà sostenere l'esame nel primo appello di gennaio.

<b><font color="#107D1D"><font size="+1">Valutazione  esercitazione in aula</font></font></b>

Dovete cercarvi in uno dei file allegati.
Alcuni sono direttamente ammessi all'ultima esercitazione dell'11 dicembre: [[%ATTACHURL%/MatPrenUltimoEs11Dic2019.pdf][MatPrenUltimoEs11Dic2019.pdf]].
Altri sono ammessi all'esercitazione dell'11 dicembre, con un esercizio di recupero sulla riduzione da svolgere dopo aver svolto quello sulla complessità.
 [[%ATTACHURL%/MatRidRec11Dic19.pdf][MatRidRec11Dic19.pdf]].
Alcuni sono invitati a presentarsi il 16 dicembre in orario di lezione per un esonero di recupero delle insufficienze. [[%ATTACHURL%/MatEsRecupero16Dic19.pdf][MatEsRecupero16Dic19.pdf]].
Altri ancora sono rinviati agli appelli di esame di gennaio e febbraio. [[%ATTACHURL%/MatEsame2020.pdf][MatEsame2020.pdf]].
Potete venire domani mattina  alle 10,30 o pomeriggio alle 14 per prendere visione dei vostri elaborati, nel mio ufficio di via Salaria.
Oggi pomeriggio, 2 dicembre porterò i pacchi dei compiti sufficienti, esercizio 1 e 2. Porterò gli altri sufficienti mercoledì mattina. Poiché il tempo a margine della lezione è poco, vi invito ad approfittare del ricevimento a via Salaria, lasciando le alternative a chi è davvero nell'impossibilità di venire domani, martedì 3.   
Le persone che non compaiono in nessun elenco non sono previste in alcun esonero. 

<b><font color="#107D1D"><font size="+1">Testi esercitazione in aula</font></font></b>

[[%ATTACHURL%/ACC3_serie_2.pdf][ACC3_serie_2.pdf]], [[%ATTACHURL%/ACC3_serie_4.pdf][ACC3_serie_4.pdf]],
 [[%ATTACHURL%/ACC3_serie_3.pdf][ACC3_serie_3.pdf]], [[%ATTACHURL%/ACC3_serie_1_.pdf][ACC3_serie_1_.pdf]].


<b><font color="#107D1D"><font size="+1">Esonero non frequentanti</font></font></b>
Il secondo esonero per non frequentanti si terrà il 16 dicembre, la mattina o il pomeriggio in funzione del numero dei prenotati.
Tale incertezza deriva dalla possibilità di fornire ai frequentanti una seconda possibilità. Chi è andato male in una delle prove previste  potrà recuperare la prova mancante in quella data. Chi invece risulta insufficiente in più di una prova dovrà recuperare nell'appello di gennaio.

<b><font color="#107D1D"><font size="+1">Programma parziale 2019/2020</font></font></b>
Qui il programma svolto finora. [[%ATTACHURL%/ProgrammaACC1920Parti_I_e_II.pdf][ProgrammaACC1920Parti_I_e_II.pdf]].

<b><font color="#107D1D"><font size="+1">Testo e soluzione esercizi proposti per l'appello straordinario e in aula</font></font></b>

Qui testo e soluzioni esercizi proposti in aula:  [[%ATTACHURL%/ACC2serie_3.pdf][ACC2serie_3.pdf]],  [[%ATTACHURL%/ACC2serie_4.pdf][ACC2serie_4.pdf]], [[%ATTACHURL%/ACC2serie_2.pdf][ACC2serie_2.pdf]],  [[%ATTACHURL%/ACC2serie_1.pdf][ACC2serie_1.pdf]].

Qui trovate testo e soluzione degli esercizi proposti per la prova. Il primo esercizio era proposto anche come esercizio di esonero per i non frequentanti. [[%ATTACHURL%/StraordACC4nov2019.pdf][StraordACC4nov2019.pdf]]

<b><font color="#107D1D"><font size="+1">Avviso valutazione seconda serie di esercizi in aula</font></font></b>

Trovate qui i risultati della valutazione   [[%ATTACHURL%/MatEs201920.pdf][MatEs201920.pdf]]. Porterò gli esercizi 1 e 2 in aula lunedì in modo che al termine della lezione chi è interessato a capire i propri errori possa prenderne visione. Porterò gli esercizi 3 e 4 in aula mercoledì.

<b><font color="#107D1D"><font size="+1">Avviso valutazione esonero del 4 novembre</font></font></b>

Tutti coloro che risultano prenotati per questo esonero saranno cancellati e non potranno partecipare ai successivi esoneri in aula.
Qui trovate la valutazione degli esercizi proposti: [[%ATTACHURL%/MatEsACC4nov2019.pdf][MatEsACC4nov2019.pdf]]. Chi vuole visionare la correzione può venire martedì mattina alle 11 nel mio ufficio di via salaria. 

<b><font color="#107D1D"><font size="+1">Avviso nuove modalità esoneri </font></font></b>

Le prossime  3 esercitazioni in aula si svolgeranno con le stesse modalità della prima e non ci saranno altre esercitazioni in aula.
Il prossimo esonero verterà ancora sulla prima parte del programma, fino ai linguaggi Context-free.
Coloro che superano la sufficienza in tre sui quattro esoneri (compreso l'ultimo e il penultimo) saranno esonerati dalla prova scritta, restando sempre la possibilità di un colloquio orale.

<b><font color="#107D1D"><font size="+1">Avviso apertura fogli prenotazioni esoneri ACC</font></font></b> 

Gli studenti <b>frequentanti </b> che intendono partecipare agli esoneri in aula sono pregati di prenotarsi sul foglio predisposto seguendo il link.
http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2019_10_01_EsoneriDiAutomiCalcolabilitaEComplessita
Questa prenotazione è valida solo per gli esoneri "a sorpresa" che si terranno in aula e che sono riservati agli studenti frequentanti.

Per gli studenti <b>non frequentanti </b>  è previsto un esonero in concomitanza dell'appello straordinario,   il 4 novembre in aula alfa, sede di via Salaria dalle 10,30 alle 12.
Prenotarsi qui http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2019_11_04_EsoneroDiACCRiservatoAgliStudentiNonFrequentanti.  Le prenotazioni chiudono il 30 ottobre!!

<b><font color="#107D1D"><font size="+1">Avviso scambio lezioni</font></font></b>
Lunedì 14 ottobre dalle 14 alle 16 in aula T2 ci sarà lezione di Ingegneria del Software al posto della lezione di ACC, la lezione di ACC si terrà martedì 15 nelle ore di Ingegneria del  Software, sempre in aula T2 dalle 14 alle 16.


<b><font color="#107D1D"><font size="+1">Avviso appello di settembre</font></font></b>

Qui trovate la valutazione della prova scritta:   [[%ATTACHURL%/MatACCSett19.pdf][MatACCSett19.pdf]].
Chi intende rifiutare il voto deve comunicarlo entro martedì prossimo alle ore 12.  Chi vuole visionare il proprio elaborato può venire martedì pomeriggio nel mio ufficio di via Salaria dalle 14 alle 16. A seguire procederò con la chiusura del verbale.
Qui trovate il testo e le soluzioni:  [[%ATTACHURL%/ACCSett19.pdf][ACCSett19.pdf]],  [[%ATTACHURL%/SolEsNFA-R.E_e_riduzione.pdf][SolEsNFA-R.E_e_riduzione.pdf]].

<b><font color="#107D1D"><font size="+1">Appello del 5 luglio 2019: il testo, la soluzione e la valutazione </font></font></b>

Qui il testo della prova:  [[%ATTACHURL%/ACC5luglio2019.pdf][ACC5luglio2019.pdf]],

La soluzione: [[%ATTACHURL%/SolACC5luglio2019.pdf][SolACC5luglio2019.pdf]].

L'esito della valutazione:  [[%ATTACHURL%/MatACCluglio19.pdf][MatACCluglio19.pdf]]. Gli studenti sono invitati a visionare la loro valutazione martedì 9 luglio dalle 14 alle 15 e poi dalle 15,30 alle 17. Registrerò i voti mercoledì 10 luglio, per cui se qualcuno vuole rifiutare il voto deve mandarmene comunicazione per email entro martedì, se non può venire al ricevimento.

<b><font color="#107D1D"><font size="+1">Appello dell'11 giugno 2019: valutazione</font></font></b>

In questo file l'esito della valutazione.  [[%ATTACHURL%/MatACCgiu19.pdf][MatACCgiu19.pdf]]. Gli studenti non elencati sono risultati insufficienti. Gli studenti che intendano prendere visione del loro elaborato sono invitati a presentarsi nel mio ufficio lunedì 24 alle 10,30. In quella data registrerò  i voti di coloro che non abbiano dichiarato di rifiutare il voto di persona o per email.

<b><font color="#107D1D"><font size="+1">Appello dell'11 giugno 2019</font></font></b>
Gli esercizi proposti:  [[%ATTACHURL%/ACC11Giu19.pdf][ACC11Giu19.pdf]]. E le soluzioni: [[%ATTACHURL%/SolACC11Giu19.pdf][SolACC11Giu19.pdf]].

<b><font color="#107D1D"><font size="+1">Appello straordinario: esito</font></font></b>

Qui il testo dell'esame:  * [[%ATTACHURL%/ACC12Apr2019.pdf][ACC12Apr2019.pdf]].
In questo file [[%ATTACHURL%/MatACCapr19.pdf][MatACCapr19.pdf]] i risultati della valutazione, gli insufficienti non sono elencati. 


<br /><a NAME="Presentazione "></a><b><u><font size="+1"><font color="#2D1585">Presentazione del corso </font></font></u></b>
L'insegnamento prevede lo studio dei risultati fondamentali di tre teorie:
la teoria dei linguaggi formali o degli automi, la teoria della calcolabilità e quella della complessità.
Si vedranno i risultati essenziali sugli automi a stati finiti e sugli automi  a pila, modelli limitati rispetto alle macchine di Turing.
La teoria della calcolabilità riguarda i risultati raggiunti a proposito di una
fondamentale domanda: quali sono le capacità fondamentali e quali
i limiti di un calcolatore?
<br />Negli anni '30 gli ormai famosi risultati negativi di Church e Turing  dimostrarono
l'esistenza di questi limiti: alcuni problemi non possono essere risolti
con un calcolatore. Questo ha dato origine alla <b><font color="#118F1D">teoria
della calcolabità</font></b>che essenzialmente
studia cosa rende un problema tanto difficile da non poter essere risolto
con un calcolatore. Lo studio ha prodotto una casistica di problemi e di
tecniche per dimostrare la possibilità o non possibilità
di soluzione algoritmica, ma anche vari modelli teorici di calcolo, che
spesso si sono rivelati utili anche nella progettazione di nuovi calcolatori.
<br />Alcuni problemi , comunque, pur essendo teoricamente affrontabili con
un calcolatore, non lo sono in pratica (nessuno ha abbastanza tempo per
aspettare la risposta). La <font color="#178524">t<b>eoria della complessità
</b></font>affronta
la questione: che cosa rende così difficili da risolvere alcuni
problemi e facili altri? Uno dei principali risultati di questa teoria
consiste in uno schema di classificazione dei problemi basato sulla loro
difficoltà computazionale. Il principale problema aperto di questa
teoria è anche il principale problema aperto dell'informatica (un
problema da un milione di dollari).

<hr width="100%"></hr>

<br /><a NAME="obiettivi"></a><b><u><font size="+1"><font color="#2D1585">Obiettivi
corso </font></font></u></b>
<br />
<br />
Al termine del corso gli studenti conosceranno i principali metodi e risultati della teoria degli Automi, della Teoria della
Calcolabilità e della Complessità e sapranno applicarli per individuare la complessità
di problemi in diversi campi. In particolare sapranno
<br />
1.giustificare l'esistenza di problemi privi di soluzioni algoritmiche o intrattabili.
<br />
2.descrivere esempi concreti di problemi indecidibili, non dimostratamente intrattabili o intrattabili.
<br />
3. la definizione formale dei diversi modelli, deterministici e non, di macchina introdotti
<br />
4. le definizioni di complessità di tempo e spazio per macchine di Turing e quella di riducibilità polinomiale
<br />
5. il senso e l'importanza della questione "P=NP?"

Gli studenti saranno in grado di
<br />1.
costruire DFA, automi a pila e Macchine di Turing deterministiche e non, da una specifica (formale o informale)
<br />2.
ridurre un problema ad un altro per dimostrarne la decidibilità o l'indecidibilità.
<br />3.
usare la riducibilità polinomiale per dimostrare la NP-completezza di problemi.
<br />4.
collocare problemi nell'opportuna classe di complessità di spazio o tempo.

<hr width="100%"></hr>

<br /><a NAME="progr"></a><b><u><font color="#2631FF">Programma del
corso </font></u></b>

<b>Automi e Linguaggi </b>

Linguaggi regolari e automi a stati finiti. Linguaggi acontestuali e automi a pila

<b>Teoria della Calcolabità </b>

Macchine di Turing.Tesi di Church-Turing. Problemi indecidibili: il problema della fermata
La riduzione tra problemi: uno strumento per dimostrarne l'indecibilità o la decidibilità.
Esempi di problemi decidibili e indecidibili.

<b>Teoria della Complessità </b>

Complessità di tempo e spazio per le macchine di Turing.Classi di complessità.Problemi trattabili e problemi non provatamente intrattabili: le classi P e NP. Riduzioni polinomiali e <i>NP</i>-completezza.
Teorema di [[http://www.cs.toronto.edu/~sacook/][Cook]]- [[http://www.cs.bu.edu/fac/lnd/.hm-bw.html][Levin]]
e altri problemi <i>NP</i>-completi. il teorema di  [[http://www-cse.ucsd.edu/faculty-research/faculty-research-profiles.html?selectname=SavitchW][Savitch]]

Qui trovate il programma dettagliato dell' a.a. 2018/2019 [[%ATTACHURL%/ProgrammaACC1819.pdf][ProgrammaACC1819.pdf]].
<p>Qui trovate il programma dettagliato dell' a.a. 17/18   [[%ATTACHURL%/ProgrammaACC17-18.pdf][ProgrammaACC17-18.pdf]].
<p>Qui quelli degli anni accademici precedenti 2014/2015, 2015/2016 e 2016/2017:  [[%ATTACHURL%/ProgrammaCC1516.pdf][ProgrammaCC1516.pdf]],  [[%ATTACHURL%/ProgrammaACC1617.pdf][ProgrammaACC1617.pdf]].

<br /><a NAME="Info"></a><b><u><font size="+1"><font color="#2D1585">Informazioni generali.
</font></font></u></b>

<b><u><font color="#2631FF">Lezioni</font></u></b>

Le lezioni  si svolgeranno nell'aula  T2 il lunedì, dalle 14 alle 16, e  il mercoledì dalle 11 alle 14,  nell'aula Cabibbo.
Consultate l'orario ufficiale qui: https://www.studiareinformatica.uniroma1.it/laurea/orario-lezioni

<b><u><font color="#2631FF">Prerequisiti</font></u></b>
<br />
E' indispensabile la conoscenza della notazione asintotica e il suo uso nell'analisi degli algoritmi. Bisogna aver una buona conoscenza di algoritmi fondamentali (in particolare su grafi) e di tecniche di analisi della complessità degli algoritmi.
E' utile conoscere le principali tecniche di progettazione di algoritmi (ricerca esaustiva, programmazione dinamica).

<hr width="100%"></hr>

<br /><a NAME="materiale"></a><b><u><font color="#2631FF">Materiale per il corso</font></u></b>
<br />
I link elencati nella pagina "Link utili" portano alle biografie o alle pagine web di alcuni dei protagonisti delle teorie oggetto del corso, forniscono quindi una prospettiva storica dei risultati ma anche materia di riflessione su problemi esistenziali di varia natura.

<b><u><font color="#121487"> I libri</font></u></b>

Il corso si baserà sul testo di
<br />
[[http://www-math.mit.edu/~sipser/][M. Sipser]], *Introduction to the Theory of Computation*, PWS Publishing
Company, II edizione (ma anche la prima va bene).
E' disponibile la traduzione in italiano: Introduzione alla teoria della computazione. Apogeo Edizioni.

Il  testo seguente è di utile consultazione:

[2] ,
[[http://theory.stanford.edu/~rajeev/][ Motwani R.]], [[http://www-db.stanford.edu/~ullman/][ Ullman J.D.]], *Automi, linguaggi e calcolabilità,*
 I edizione italiana,Addison-Wesley,2003

Chi volesse leggere l'articolo originale di Turing  può scaricarlo qui: [[%ATTACHURL%/Turing.pdf][Turing.pdf]].

Testi esercizi proposti negli appelli di esame o come esercitazioni in aula.
[[%ATTACHURL%/ACC4Maggio20.pdf][ACC4Maggio20.pdf]].
 [[%ATTACHURL%/SolACC4Maggio20.pdf][SolACC4Maggio20.pdf]].
[[%ATTACHURL%/Esercizi19ott18.pdf][Esercizi19ott18.pdf]]
[[%ATTACHURL%/Esercizi29novembre2018.pdf][Esercizi29novembre2018.pdf]].
[[%ATTACHURL%/SolEsercizi29novembre2018.pdf][SolEsercizi29novembre2018.pdf]].
[[%ATTACHURL%/Es20dic2018.pdf][Es20dic2018.pdf]]
[[%ATTACHURL%/SolEs20dic2018.pdf][SolEs20dic2018.pdf]]
[[%ATTACHURL%/SolEs20dic2018.pdf][SolEs20dic2018.pdf]]
[[%ATTACHURL%/ACC14Gen19.pdf][ACC14Gen19.pdf]]
e la loro soluzione [[%ATTACHURL%/SolACC14Gen19.pdf][SolACC14Gen19.pdf]].
[[%ATTACHURL%/ACC20Sett18.pdf][ACC20Sett18.pdf]],
[[%ATTACHURL%/ACC10Gen18.pdf][ACC10Gen18.pdf]],
 [[%ATTACHURL%/ACC6Giu18.pdf][ACC6Giu18.pdf]].
 [[%ATTACHURL%/ACC16apr18.pdf][ACC16apr18.pdf]].
 [[%ATTACHURL%/TestoACC4Sett17.pdf][TestoACC4Sett17.pdf]].
 [[%ATTACHURL%/ACCGiu17.pdf][ACCGiu17.pdf]]. E le soluzioni:
 [[%ATTACHURL%/SolACCGiu17.pdf][SolACCGiu17.pdf]]
 [[%ATTACHURL%/AppStrACCApr17.pdf][AppStrACCApr17.pdf]].
 [[%ATTACHURL%/_ACC13Gen17.pdf][_ACC13Gen17.pdf]].
 [[%ATTACHURL%/SolPIACCNov16.pdf][SolPIACCNov16.pdf]].
 [[%ATTACHURL%/ACC7Nov16.pdf][ACC7Nov16.pdf]],
 [[%ATTACHURL%/SolACC7Nov16.pdf][SolACC7Nov16.pdf]].
 [[%ATTACHURL%/ACC8Giu16.pdf][ACC8Giu16.pdf]]
 [[%ATTACHURL%/ACC1lu16.pdf][ACC1lu16.pdf]]
 [[%ATTACHURL%/Es4CC2015.pdf][Es4CC2015.pdf]]

<hr width="100%"></hr>

<br /><a NAME="valutazione"></a><b><u><font color="#2631FF">Valutazione degli studenti</font></u></b>

L'esame consiste di una prova scritta. Per informazioni ufficiali su date, orari e luoghi degli appelli (scritti, orali & verbalizzazioni), fate riferimento al http://www.studiareinformatica.uniroma1.it/appelli-d-esame nelle pagine Web del corso di laurea. 
Per il superamento dell'esame per tutti gli studenti che seguono il corso sono previste prove durante lo svolgimento delle lezioni e durante la settimana degli esoneri. Le prove consistono in domande di collegamento o approfondimento degli argomenti studiati o in esercizi. Chi supera queste prove può essere esonerato in tutto o in parte dall'esame.
Comunque ogni studente è tenuto a presentarsi all'esame dopo aver verificato che la propria preparazione è adeguata.
Lo studente che ha raggiunto la sufficienza può migliorare il voto con un colloquio o presentandosi all'appello successivo e svolgendo  l'esercizio o gli esercizi su cui è andato peggio.
<br />
Il voto finale sarà calcolato tenendo conto dei punteggi conseguiti nelle prove e, per coloro che seguono il corso,  anche del grado di partecipazione attiva allo stesso.

Gli studenti che si presentano all'esame, partire dall'appello di gennaio, e ottengono una valutazione inferiore a 12/30 dimostrano non solo di non essersi preparati ma anche di non essere in grado di valutare la propria preparazione  e quindi non saranno ammessi all'esame nell'appello successivo.

<hr width="100%"></hr>

<a NAME="diario"></a><b><font color="#830AAB"><font size="+2">DIARIO DELLE LEZIONI 2019/2020 </font></font> </b>

<font color="#CA1616"><font size="+1"><b>mercoledì 11/12/2019</b></font></font>
3 ore; Ultima esercitazione in aula.

<font color="#CA1616"><font size="+1"><b>lunedì 9/12/2019</b></font></font>
2 ore;  Classi di complessità di spazio. Esempio di problema in PSPACE e di uno in NPSPACE. Teorema di Savitch. La classe coNP, problemi in NP e in CoNP.  [[%ATTACHURL%/coNP.pdf][coNP.pdf]].


<font color="#CA1616"><font size="+1"><b>mercoledì 4/12/2019</b></font></font>
3 ore; Problemi NP- completi, teorema di Cook. Esempi di problemi NP-completi. 
  [[%ATTACHURL%/NPcomplCook.pdf][NPcomplCook.pdf]]
 [[%ATTACHURL%/NPcompleti_.pdf][NPcompleti_.pdf]]

<font color="#CA1616"><font size="+1"><b>lunedì 2/12/2019</b></font></font>
2 ore;  Il concetto di verificatore e la definizione alternativa di NP basata sull'esistenza di un verificatore polinomiale. Esempi di problemi in NP.
[[%ATTACHURL%/Verificatore.pdf][Verificatore.pdf]].

<font color="#CA1616"><font size="+1"><b>mercoledì 27/11/2019</b></font></font>
3 ore; Tempo asintotico di esecuzione  di una TM che simula una NTM. Definizione di classe di complessità, Le classi P e NP. la classe P e la tesi di Cobham-Edmonds. Per chi volesse approfondire qui trovate gli articoli di Cobham e di Edmonds: [[%ATTACHURL%/cobham_intrinsic.pdf][cobham_intrinsic.pdf]], [[%ATTACHURL%/J.Edmonds.pdf][J.Edmonds.pdf]]. 

<font color="#CA1616"><font size="+1"><b>lunedì 25/11/2019</b></font></font>
2 ore; Misure di complessità per TM: spazio e tempo. Relazioni tra le due misure. Tempo asintotico di esecuzione  di una TM che simula una TM a k nastri.     [[%ATTACHURL%/ClassiCompl.pdf][ClassiCompl.pdf]].

<font color="#CA1616"><font size="+1"><b>mercoledì 20/11/2019</b></font></font>
3 ore; Vari esempi di riduzioni dal problema per l'appartenenza per TM, tra cui una per il problema della fermata. Dimostrazione della non Turing riconoscibilità per EQ_TM e il suo complemento.
Esercizi sulle riduzioni.  [[%ATTACHURL%/Esaula20nov19.pdf][Esaula20nov19.pdf]]

<font color="#CA1616"><font size="+1"><b>lunedì 18/11/2019</b></font></font>
2 ore;Riduzioni: uno strumento per dimostrare decidibilità o indecidibilità dei problemi.
 [[%ATTACHURL%/Riduzioni.pdf][Riduzioni.pdf]], [[%ATTACHURL%/RideIndecidibilit.pdf][RideIndecidibilit.pdf]].

<font color="#CA1616"><font size="+1"><b>mercoledì 13/11/2019</b></font></font>
3 ore; Macchina di Turing universale, [[%ATTACHURL%/TMUniversale.pdf][TMUniversale.pdf]].Indecidibilità  e Turing riconoscibilità del problema della fermata e dell'accettazione.  [[%ATTACHURL%/IndFermataTM.pdf][IndFermataTM.pdf]]. 

<font color="#CA1616"><font size="+1"><b>lunedì 11/11/2019</b></font></font>
2 ore; Esistenza di problemi non Turing riconoscibili, [[%ATTACHURL%/NonDecEsiste.pdf][NonDecEsiste.pdf]].

<font color="#CA1616"><font size="+1"><b>mercoledì 6/11/2019</b></font></font>
3 ore; TM: varianti a k nastri e non deterministiche. Equivalenza.   [[%ATTACHURL%/TMKnastri.pdf][TMKnastri.pdf]].
[[%ATTACHURL%/TMNonDet.pdf][TMNonDet.pdf]].

<font color="#CA1616"><font size="+1"><b>lunedì 4/11/2019</b></font></font>
2 ore; TM: definizioni ed esempi.  [[%ATTACHURL%/TMDef.pdf][TMDef.pdf]].


<font color="#CA1616"><font size="+1"><b>mercoledì 30/10/2019</b></font></font>
3 ore; CFG: proprietà di chiusura e problemi di decisione. Equivalenza di CFL e la classe dei linguaggi accettati da PDA.
 [[%ATTACHURL%/AmbiguitCFG.pdf][AmbiguitCFG.pdf]], [[%ATTACHURL%/CFGePDA.pdf][CFGePDA.pdf]]. [[%ATTACHURL%/ChiusCFLDec.pdf][ChiusCFLDec.pdf]].

<font color="#CA1616"><font size="+1"><b>lunedì 28/10/2019</b></font></font>
2 ore; CFG: definizioni ed esempi.  [[%ATTACHURL%/CFG.pdf][CFG.pdf]].


<font color="#CA1616"><font size="+1"><b>mercoledì 23/10/2019</b></font></font>
3 ore; . Esercizi: [[%ATTACHURL%/Es2.pdf][Es2.pdf]],  [[%ATTACHURL%/Es3.pdf][Es3.pdf]],  [[%ATTACHURL%/Es1.pdf][Es1.pdf]]: Es1.pdf,  [[%ATTACHURL%/Es4.pdf][Es4.pdf]].
Altri esercizi risolti:  [[%ATTACHURL%/UltimoGiaOPresente.pdf][UltimoGiaOPresente.pdf]],  [[%ATTACHURL%/oi1jijPARI.pdf][oi1jijPARI.pdf]],  [[%ATTACHURL%/NFA2.pdf][NFA2.pdf]], [[%ATTACHURL%/EsNFA1.pdf][EsNFA1.pdf]],   [[%ATTACHURL%/ultimoNonPresente.pdf][ultimoNonPresente.pdf]],  [[%ATTACHURL%/0i1jpari.pdf][0i1jpari.pdf]].


<font color="#CA1616"><font size="+1"><b>lunedì 21/10/2019</b></font></font>
2 ore; Ancora su PDA esempi,. non determinismo e determinismo. Esercizi

<font color="#CA1616"><font size="+1"><b>mercoledì 16/10/2019</b></font></font>
3 ore; PDA: definizione, esempi e prime proprietà.  [[%ATTACHURL%/PDA.pdf][PDA.pdf]].

<font color="#CA1616"><font size="+1"><b>martedì 15/10/2019</b></font></font>
2 ore; (grazie allo scambio con il prof. Bottoni) Espressioni regolari e loro equivalenza con i linguaggi accettati dai DFA. 
 [[%ATTACHURL%/EspressioniRegolari.pdf][EspressioniRegolari.pdf]]. Esercizi per dimostrare la non regolarità con il Pumping Lemma.
In certi casi il Pumping Lemma non è d'aiuto, conviene trovare altre strade. Per esempio per dimostrare che il linguaggio L={w | w è in {0,1}* non è una palindroma}, conviene ragionare per assurdo: se L fosse regolare lo sarebbe anche il suo complemento che però abbiamo dimostrato non essere regolare (il linguaggio delle parole palindrome) quindi L non può essere regolare.

<font color="#CA1616"><font size="+1"><b>mercoledì 9/10/2019</b></font></font>
3 ore; Esistenza di linguaggi non regolari e uno strumento per dimostrare la non regolarità dei linguaggi: il pumping lemma.
 Esercizi.  [[%ATTACHURL%/PumpingLemma.pdf][PumpingLemma.pdf]],   [[%ATTACHURL%/SolEsPumping.pdf][SolEsPumping.pdf]].

<font color="#CA1616"><font size="+1"><b>lunedì 7/10/2019</b></font></font>
2 ore; Automi a stati finiti non deterministici con epsilon mosse e equivalenza con i DFA. Chiusura della classe dei linguaggi regolari rispetto a prodotto e stella di Kleene. Problemi di decisione per i DFA: il problema del vuoto, dell'infinito e della totalità.  [[%ATTACHURL%/PorblemiDecDFA.pdf][PorblemiDecDFA.pdf]].

<font color="#CA1616"><font size="+1"><b>mercoledì 2/10/2019</b></font></font>
3 ore;Automi a stati finiti non deterministici e equivalenza con i DFA. Esercizi. [[%ATTACHURL%/NFA.pdf][NFA.pdf]].

<font color="#CA1616"><font size="+1"><b>lunedì 30/9/2019</b></font></font>
2 ore;  DFA: chiusura rispetto a unione, intersezione e complemento.  [[%ATTACHURL%/PrimeChiusure.pdf][PrimeChiusure.pdf]]. Non determinismo: introduzione.
Esercizio: si dimostri la chiusura della classe dei linguaggi regolari rispetto alla differenza tra linguaggi.

<font color="#CA1616"><font size="+1"><b>mercoledì 25/9/2019</b></font></font>
3 ore; Linguaggi e problemi. DFA: definizione ed esempi.   [[%ATTACHURL%/LinguaggiDFA.pdf][LinguaggiDFA.pdf]].

<font color="#CA1616"><font size="+1"><b>lunedì 23/9/2019</b></font></font>
2 ore; Introduzione al corso.  [[%ATTACHURL%/IntrACC.pdf][IntrACC.pdf]].





<hr width="100%"></hr>

<a NAME="diario18"></a><b><font color="#830AAB"><font size="+2">DIARIO DELLE LEZIONI 2018/2019 </font></font> </b>
<hr width="100%"></hr>

<font color="#CA1616"><font size="+1"><b>giovedì 20/12/2018</b></font></font>
3 ore; Esercitazione in aula.

<font color="#CA1616"><font size="+1"><b>martedì 18/12/2018</b></font></font>
3 ore; La classe coNP, problemi in NP e in CoNP. Esercizi

<font color="#CA1616"><font size="+1"><b>venerdì 14/12/2018</b></font></font>
3 ore; Classi di complessità di spazio. Esempio di problema in PSPACE e di uno in NPSPACE. Teorema di Savitch.
Esercizi sulle riduzioni.

<font color="#CA1616"><font size="+1"><b>martedì 11/12/2018</b></font></font>
3 ore; La riduzione polinomiale: esempi di riduzioni tra problemi CNFSAT &le;p 3SAT, 3SAT&le;p CLIQUE, 3SAT&le;p INDEPENDETSET. La definizione di NP-completo. Il teorema di Cook-levin (solo enunciato). Esercizio: CLIQUE&le;pINDEPENDENTSET.
3
<font color="#CA1616"><font size="+1"><b>giovedì 6/12/2018</b></font></font>
3 ore; Tempo asintotico di esecuzione  di una TM che simula una NTM. La classe NP. Il concetto di verificatore e la definizione alternativa di NP basata sull'esistenza di un verificatore polinomiale. Esempi di problemi in NP: cammino hamiltoniano, k-clique.

<font color="#CA1616"><font size="+1"><b>martedì 4/12/2018</b></font></font>
3 ore; Misure di complessità per TM: spazio e tempo. Relazioni tra le due misure. Tempo asintotico di esecuzione  di una TM che simula una TM a k nastri. Definizione di classe di complessità, la classe P e la tesi di Cobham-Edmonds. Per chi volesse approfondire qui trovate gli articoli di Cobham e di Edmonds: [[%ATTACHURL%/cobham_intrinsic.pdf][cobham_intrinsic.pdf]], [[%ATTACHURL%/J.Edmonds.pdf][J.Edmonds.pdf]].

<font color="#CA1616"><font size="+1"><b>giovedì 29/11/2018</b></font></font>
3 ore; Esercitazione in aula.

<font color="#CA1616"><font size="+1"><b>martedì 27/11/2018</b></font></font>
3 ore; Vari esempi di riduzioni dal problema per l'appartenenza per TM, tra cui una per il problema della fermata. Dimostrazione della non Turing riconoscibilità per EQ_TM  e il suo complemento.

<font color="#CA1616"><font size="+1"><b>giovedì 22/11/2018</b></font></font>
3 ore; Indecidibilità del problema della fermata e non Turing riconoscibilità per il complemento del problema dell'appartenenza.

<font color="#CA1616"><font size="+1"><b>martedì 20/11/2018</b></font></font>
3 ore; Macchine di Turing non deterministiche e loro equivalenza con le macchine di Turing deterministiche.
Esistenza di problemi non Turing riconoscibili. Indecidibilità del problema dell'appartenenza.
Una TM che fa slittare di una cella a destra il contenuto del nastro:  [[%ATTACHURL%/ModuloTM1.pdf][ModuloTM1.pdf]]; una TM che calcola la stringa binaria successiva a quella da in input: [[%ATTACHURL%/moduloTM2.pdf][moduloTM2.pdf]]; una TM che genera tutte le stringhe binarie in ordine canonico: [[%ATTACHURL%/moduloTM3.pdf][moduloTM3.pdf]].

<font color="#CA1616"><font size="+1"><b>venerdì 16/11/2018</b></font></font>
3 ore; Problemi di decisione e linguaggi. Macchine di Turing a più nastri e loro equivalenza con le macchine di Turing a un solo nastro.

<font color="#CA1616"><font size="+1"><b>giovedì 15/11/2018</b></font></font>
Definizione di automa a pila deterministico (DPDA) e inclusine stretta della classe dei linguaggi accettati da un DPDA e quella dei linguaggi accettati da un PDA, senza dimostrazione. Equivalenza tra L(PDA) e CFL e dimostrazione del contenimento di CFL in L(PDA). Definizione ed esempi di macchine di Turing. Problemi e problemi di decisione: l'esempio del problema della soddisfacibilità.

<font color="#CA1616"><font size="+1"><b>venerdì 9/11/2018</b></font></font>
3 ore; Esercitazione in aula.

<font color="#CA1616"><font size="+1"><b>mercoledì 7/11/2018</b></font></font>
3 ore; Problemi di decisione e risultati di chiusura per i CFL.  PDA: introduzione ed esempi.  
Determinazione del linguaggio riconosciuto da una grammatica: esempio 1: sia G =  S -&gt;SS| S-&gt;0S1| S-&gt;1S0| epsilon, il linguaggio generato da G è l'insieme delle parole sull'alfabeto binario che hanno lo stesso numero di 1 e 0.
esempio 2 : sia G = S-&gt;AS | 0S1 | A ; A -&gt; A0 | 0, il linguaggio generato è l'insieme delle parole binarie in cui gli 0 precedono gli 1 e il numero degli 0 è strettamente maggiore del numero degli 1, che può essere 0.

<font color="#CA1616"><font size="+1"><b>venerdì 2/11/2018</b></font></font>
3 ore; lezione non tenuta

<font color="#CA1616"><font size="+1"><b>mercoledì 31/10/2018</b></font></font>
3 ore;Forma normale di Chomsky, [[%ATTACHURL%/appunti_cnf.pdf][appunti_cnf.pdf]],  [[%ATTACHURL%/AppuntiAlgVuotoCFG.pdf][AppuntiAlgVuotoCFG.pdf]]

<font color="#CA1616"><font size="+1"><b>venerdì 26/10/2018</b></font></font>
3 ore; Proprietà di chiusura rispetto a unione e prodotto di linguaggi dei CFL e loro uso nella costruzione di CFG complesse, ambiguità di una grammatica, linguaggi inerentemente ambigui, indecidibilità del problema dell'ambiguità per CFL. Decidibilità dei problemi dell'appartenenza, del contenimento, della totalità e varianti per i linguaggi regolari.

<font color="#CA1616"><font size="+1"><b>mercoledì 24/10/2018</b></font></font>
3 ore; Linguaggi content-free e le grammatiche che li generano, primi esempi e proprietà.

<font color="#CA1616"><font size="+1"><b>venerdì 19/10/2018</b></font></font>
3 ore; dalle 11,30 alle 13 esercitazione in aula con valore di primo esonero, sugli argomenti trattati fino a mercoledì.

<font color="#CA1616"><font size="+1"><b>mercoledì 17/10/2018</b></font></font>
3 ore; Espressioni regolari e loro equivalenza con NFA. Esercizi [[%ATTACHURL%/SolEsPumping.pdf][SolEsPumping.pdf]].

<font color="#CA1616"><font size="+1"><b>venerdì 12/10/2018</b></font></font>
3 ore; Esistenza di linguaggi non regolari e uno strumento per dimostrare la non regolarità dei linguaggi: il pumping lemma.
 Esercizi.

<font color="#CA1616"><font size="+1"><b>martedì 9/10/2018</b></font></font>
3 ore;  Lezione che anticipa quella di mercoledì 10 ottobre, al posto di Ingegneria del software.
NFA con mosse sulla parola vuota, equivalenza con DFA e proprietà di chiusura dei regolari rispetto a prodotto e stella di Kleene.
Esercizi sulle proprietà di chiusura: 1. Dato un linguaggio regolare L {a,b}, è regolare anche il linguaggio delle parole di L che hanno al più 4 occorrenze di b e almeno 2 occorrenze di a? 2. Si costruisca il DFA che accetta il linguaggio delle parole sull'alfabeto {a,b} che non contengono aba come sottoparola.
Soluzione esercizio 1:
L’insieme delle parole di L   che hanno al più 4 occorrenze di b e almeno 2 occorrenze di a si ottiene come l’intersezione di L con il linguaggio, L1,  delle parole che hanno al più 4 occorrenze di b e di quello delle parole in cui occorrono  almeno 2 a, L2. Poiché L1 e L2 sono regolari in quanto esistono due DFA che li accettano ed essendo la classe dei regolari chiusa rispetto all’intersezione allora è vero che  il linguaggio delle parole di L che hanno al più 4 occorrenze di b e almeno 2 occorrenze di a è ancora regolare. Si devono costruire i due DFA per L1 e L2.

<font color="#CA1616"><font size="+1"><b>giovedì 4/10/2018</b></font></font>

3 ore; Lezione che anticipa quella di venerdì 5 ottobre, al posto di Ingegneria del software.
NFA: definizione, esempi. Costruzione DFA  equivalente a un NFA dato, NFA con mosse sulla parola vuota.

<font color="#CA1616"><font size="+1"><b>mercoledì 3/10/2018</b></font></font>

3 ore; Automi a stati finiti. Esempi di automi unione/intersezione e di stati inutili. Algoritmi per il problema del vuoto e dell'infinito per DFA.
Automi a stati finiti non deterministici, NFA: primi esempi.

<font color="#CA1616"><font size="+1"><b>venerdì 28/9/2018</b></font></font>

3 ore; Automi a stati finiti: definizioni ed esempi. Chiusura rispetto  unione e intersezione  della classe dei linguaggi regolari.

<font color="#CA1616"><font size="+1"><b>mercoledì 26/9/2018</b></font></font>

3 ore;Introduzione al corso.

<a NAME="diario17"></a><b><font color="#830AAB"><font size="+2">DIARIO DELLE LEZIONI 2017/2018 </font></font> </b>

<font size="+1"><b>venerdì 22/12/2017</b></font>
2 ore; Le classi di spazio: PSPACE, L e NL.  [[%ATTACHURL%/InPoltreNP.pdf][InPoltreNP.pdf]]
<br />12,15 - 13 V prova in aula II gruppo [[%ATTACHURL%/Es22Dic17.pdf][Es22Dic17.pdf]],  [[%ATTACHURL%/Riduzione22Dic17.pdf][Riduzione22Dic17.pdf]].

<font size="+1"><b>mercoledì 20/12/2017</b></font>
2 ore; La classe coNP, FACTOR, l'isomorfismo tra grafi e i problemi intermedi. [[%ATTACHURL%/coNP.pdf][coNP.pdf]].
<br />12,15 - 13 V prova in aula I gruppo. [[%ATTACHURL%/Es20Dic17.pdf][Es20Dic17.pdf]],
 [[%ATTACHURL%/RidEs20Dic17.pdf][RidEs20Dic17.pdf]].

<font size="+1"><b>venerdì 15/12/2017</b></font>
3 ore;  Ancora esempi di problemi NP completi e Teorema di Savitch.
[[%ATTACHURL%/Savitch.pdf][Savitch.pdf]], [[%ATTACHURL%/NPcompleti2.pdf][NPcompleti2.pdf]].

<font size="+1"><b>mercoledì 13/12/2017</b></font>
3 ore; Teorema di Cook-Levin.  [[%ATTACHURL%/NPcomplCook.pdf][NPcomplCook.pdf]]
 [[%ATTACHURL%/NPcompleti_.pdf][NPcompleti_.pdf]]

<font size="+1"><b>venerdì 8/12/2017</b></font>
3 ore; vacanza accademica

<font size="+1"><b>mercoledì 6/12/2017</b></font>
3 ore; Il verificatore: nuova definizione di NP, [[%ATTACHURL%/Verificatore.pdf][Verificatore.pdf]].

<font size="+1"><b>venerdì 1/12/2017</b></font>
2 ore; classi di complessità,  [[%ATTACHURL%/ClassiCompl.pdf][ClassiCompl.pdf]].
<br />12,15 - 13 IV prova in aula II gruppo, [[%ATTACHURL%/EsACC4Dic.pdf][EsACC4Dic.pdf]].

 <font size="+1"><b>mercoledì 29/11/2017</b></font>
2 ore; Riduzioni: definizione ed esempi.  [[%ATTACHURL%/Riduzioni.pdf][Riduzioni.pdf]],  [[%ATTACHURL%/RideIndecidibilit.pdf][RideIndecidibilit.pdf]].
<br />12,15 - 13 IV prova in aula I gruppo,  [[%ATTACHURL%/EsACC29Nov.pdf][EsACC29Nov.pdf]].

<font size="+1"><b>venerdì 24/11/2017</b></font>
3 ore; Il problema dell'accettazione e della fermata per macchine di Turing: loro indecidibilità e loro Turing riconoscibilità. Macchina di Turing universale,  [[%ATTACHURL%/IndFermataTM.pdf][IndFermataTM.pdf]],
[[%ATTACHURL%/TMUniversale.pdf][TMUniversale.pdf]]. Qualche esercizio:  [[%ATTACHURL%/NumerabilitTuringCalc.pdf][NumerabilitTuringCalc.pdf]]. Due problemi decidibili per CFG:  [[%ATTACHURL%/DecChiusCFL.pdf][DecChiusCFL.pdf]].

 <font size="+1"><b>mercoledì 22/11/2017</b></font>
3 ore; Macchine di Turing non deterministiche,  [[%ATTACHURL%/TMNonDet.pdf][TMNonDet.pdf]]. Esistenza di problemi non Turing riconoscibili, [[%ATTACHURL%/NonDecEsiste.pdf][NonDecEsiste.pdf]].

<font size="+1"><b>venerdì 17/11/2017</b></font>
2 ore; Macchine di Turing a k nastri e loro equivalenza con le macchine di Turing a un solo nastro,   [[%ATTACHURL%/TMKnastri.pdf][TMKnastri.pdf]].
<br /> 12,15 - 13,00: III prova in aula per il secondo gruppo,
[[%ATTACHURL%/EsACC17Nov.pdf][EsACC17Nov.pdf]].

<font size="+1"><b>mercoledì 15/11/2017</b></font>
2 ore; Macchine di Turing: definizione ed esempi,  [[%ATTACHURL%/TMDef.pdf][TMDef.pdf]].
<br /> 12,15 - 13,00: III prova in aula per il primo gruppo,  [[%ATTACHURL%/EsACC15Nov.pdf][EsACC15Nov.pdf]].

<font size="+1"><b>venerdì 10/11/2017</b></font>
3 ore; La lezione non si terrà per un concomitante e irrinunciabile impegno del docente.

<font size="+1"><b>mercoledì 8/11/2017</b></font>
2 ore; Ambiguità e CFG,   [[%ATTACHURL%/AmbiguitCFG.pdf][AmbiguitCFG.pdf]]. PDA e CFG, [[%ATTACHURL%/CFGePDA.pdf][CFGePDA.pdf]].
<br /> 12,15 - 13,00: II prova in aula per il primo gruppo, [[%ATTACHURL%/Es811.pdf][Es811.pdf]].

<font size="+1"><b>venerdì 3/11/2017</b></font>
2 ore; CFG: introduzione ed esempi,  [[%ATTACHURL%/CFG.pdf][CFG.pdf]].
<br /> 12,15 - 13,00: II prova in aula per il secondo  gruppo, [[%ATTACHURL%/Es311.pdf][Es311.pdf]].

<font size="+1"><b>mercoledì 1/11/2017</b></font>
3 ore; lezione non tenuta perché giorno festivo

<font size="+1"><b>venerdì 27/10/2017</b></font>
3 ore; Esercizi di costruzione di NFA, PDA e problemi di decisione per i DFA.   [[%ATTACHURL%/EserciziNFAePDA_.pdf][EserciziNFAePDA_.pdf]].

<font size="+1"><b>mercoledì 25/10/2017</b></font>
3 ore; Automi a pila: definizioni ed esempi, [[%ATTACHURL%/PDA.pdf][PDA.pdf]]. Esercizi sul pumping lemma.

<font size="+1"><b>venerdì 20/10/2017</b></font>
3 ore; Espressioni regolari e loro equivalenza con i DFA (teorema di Kleene), [[%ATTACHURL%/EspressioniRegolari.pdf][EspressioniRegolari.pdf]].
Esercizi sul pumping lemma,  [[%ATTACHURL%/EsPumping.pdf][EsPumping.pdf]]
<br />13,15 - 13,45: I prova in aula per il secondo gruppo, i testi:  [[%ATTACHURL%/Es2010.pdf][Es2010.pdf]].

<font size="+1"><b>mercoledì 18/10/2017</b></font>
3 ore; Chiusura rispetto a concatenazione e stella di Kleene [[%ATTACHURL%/Linguaggi_e_operazioni.pdf][Linguaggi_e_operazioni.pdf]], Pumping lemma per i regolari  [[%ATTACHURL%/PumpingLemma.pdf][PumpingLemma.pdf]]. Soluzioni esercizi su DFA,NFA e proprietà di chiusura proposti nella lezione precedente.
<br /> 13,15 - 13,45: I prova in aula per il primo gruppo, i testi:  [[%ATTACHURL%/EsEsame18Ott17.pdf][EsEsame18Ott17.pdf]].

<font size="+1"><b>venerdì 13/10/2017</b></font>
3 ore; NFA: gli automi finiti non deterministici. [[%ATTACHURL%/NFAdefDimEq.pdf][NFAdefDimEq.pdf]],
 [[%ATTACHURL%/EserciziAutomi.pdf][EserciziAutomi.pdf]].

<font size="+1"><b>mercoledì 11/10/2017</b></font>
3 ore;Il problema del vuoto per DFA, l'algoritmo per  riduzione a PATH e quello basato sulla ricerca esaustiva dell'insieme delle parole sull'alfabeto di input di lunghezza minore al numero degli stati. Chiusura della classe dei linguaggi accettati da un DFA rispetto a unione, intersezione e complemento. [[%ATTACHURL%/PrimeChiusure.pdf][PrimeChiusure.pdf]]

<font size="+1"><b>venerdì 6/10/2017</b></font>
3 ore; Automi a stati finiti, Deterministic Finite Automata, prime definizioni ed esempi. [[%ATTACHURL%/DFA1Intr.pdf][DFA1Intr.pdf]].

<font size="+1"><b>mercoledì 4/10/2017</b></font>
3 ore; Introduzione al corso: breve descrizione contenuto del programma, problemi di decisione e linguaggi, problemi di decisione e problemi di ricerca. [[%ATTACHURL%/IntrACC17.pdf][IntrACC17.pdf]].

<hr width="100%"></hr>

<a NAME="diario16"></a><b><font color="#830AAB"><font size="+2">DIARIO DELLE LEZIONI 2016/2017 </font></font> </b>

<font size="+1"><b>mercoledì 21/12/2016</b></font>
4 ore; Esercitazione riassuntiva sulla seconda parte del programma.  [[%ATTACHURL%/EsAula21dic2016.pdf][EsAula21dic2016.pdf]].

<font size="+1"><b>giovedì 15/12/2016</b></font>
2 ore; dalle 9 alle 11, nell'orario di Linguaggi e Compilatori: Teorema di Savicth. [[%ATTACHURL%/Savitch.pdf][Savitch.pdf]],  qualche incursione dentro P e oltre NP,  [[%ATTACHURL%/InPoltreNP.pdf][InPoltreNP.pdf]].

<font size="+1"><b>mercoledì 14/12/2016</b></font>
3 ore; Problemi NP completi.   [[%ATTACHURL%/NPcompleti_.pdf][NPcompleti_.pdf]]

<font size="+1"><b>venerdì 9/12/2016</b></font>
2 ore; lezione annullata e anticipata al 6 dicembre.

<font size="+1"><b>mercoledì 7/12/2016</b></font>
3 ore; Teorema di Cook.   [[%ATTACHURL%/NP-complCook.pdf][NP-complCook.pdf]], Esercizi di uso delle riduzioni in prove di indecidibilità e sulla Turing riconoscibilità.  [[%ATTACHURL%/EserciziDecTuringRic.pdf][EserciziDecTuringRic.pdf]]

<font size="+1"><b>martedì 6/12/2016</b></font>
3 ore; dalle ore 9 alle ore 10,45.  ll verificatore. Nuova definizione di NP, [[%ATTACHURL%/Verificatore.pdf][Verificatore.pdf]]

<font size="+1"><b>venerdì 2/12/2016</b></font>
2 ore; Classi di complessità, definizioni ed esempi, [[%ATTACHURL%/ClassiCompl.pdf][ClassiCompl.pdf]].

<font size="+1"><b>mercoledì 30/11/2016</b></font>
3 ore; Riduzioni: uno strumento per dimostrare decidibilità o indecidibilità dei problemi.
 [[%ATTACHURL%/Riduzioni.pdf][Riduzioni.pdf]], [[%ATTACHURL%/TMUniversale.pdf][TMUniversale.pdf]],
 [[%ATTACHURL%/RideIndecidibilit.pdf][RideIndecidibilit.pdf]].

<font size="+1"><b>venerdì 25/11/2016</b></font>
2 ore; poiché lo sciopero indetto rende difficile per gli studenti pendolari e romani il raggiungimento della sede universitaria la lezione è annullata e sarà recuperata il 6 dicembre, durante l'orario dell'insegnamento della prof.ssa Finocchi.

<font size="+1"><b>mercoledì 23/11/2016</b></font>
3 ore; Esistenza di problemi indecidibili. [[%ATTACHURL%/NonDecesiste.pdf][NonDecesiste.pdf]].
 Il problema della fermata. [[%ATTACHURL%/IndFermataTM.pdf][IndFermataTM.pdf]].

 <font size="+1"><b>venerdì 18/11/2016</b></font>
2 ore;Macchine di Turing non deterministiche e loro equivalenza con le deterministiche.  [[%ATTACHURL%/TMNonDet.pdf][TMNonDet.pdf]]

<font size="+1"><b>mercoledì 16/11/2016</b></font>
3 ore; Macchine di Turing a k nastri e loro equivalenza con le macchine di Turing a un solo nastro.
[[%ATTACHURL%/TMKnastri.pdf][TMKnastri.pdf]]

<font size="+1"><b>venerdì 11/11/2016</b></font>
2 ore;Macchine di Turing: prime definizioni ed esempi. [[%ATTACHURL%/TMDef.pdf][TMDef.pdf]].

<font size="+1"><b>mercoledì 9/11/2016</b></font>
3 ore; Prova intermedia. [[%ATTACHURL%/PIACCNov16.pdf][PIACCNov16.pdf]]:.

<font size="+1"><b>venerdì 4/11/2016</b></font>
2 ore;Esercizi riassuntivi programma svolto [[%ATTACHURL%/EsAula.pdf][EsAula.pdf]].

<font size="+1"><b>mercoledì 2/11/2016</b></font>
2 ore; Proprietà di chiusura e problemi di decisione  per i  CFL.    [[%ATTACHURL%/ChiusureCFL.pdf][ChiusureCFL.pdf]]

<font size="+1"><b>venerdì 28/10/2016</b></font>
2 ore; lezione annullata

<font size="+1"><b><font color="#d3305d">lunedì </font> 24/10/2016</b></font>
3 ore; Equivalenza CFG e PDA, Ambiguità e forme normali per CFG. Problemi di decisione per CFG. [[%ATTACHURL%/CFGePDA.pdf][CFGePDA.pdf]], [[%ATTACHURL%/AmbiguitCFG.pdf][AmbiguitCFG.pdf]], [[%ATTACHURL%/algCYK.pdf][algCYK.pdf]].

<font size="+1"><b>venerdì 21/10/2016</b></font>
2 ore; Grammatiche context-free, prime proprietà. [[%ATTACHURL%/CFGIntr.pdf][CFGIntr.pdf]]

<font size="+1"><b>mercoledì 19/10/2016</b></font>
3 ore; Automi a pila, definizioni ed esempi. Prime proprietà.  [[%ATTACHURL%/PDA.pdf][PDA.pdf]].

<font size="+1"><b>venerdì 14/10/2016</b></font>
2 ore; espressioni regolari ed equivalenza con i DFA. [[%ATTACHURL%/EspressioniRegolari.pdf][EspressioniRegolari.pdf]].

<font size="+1"><b>mercoledì 12/10/2016</b></font>
3 ore; Conclusione NFA e pumping lemma per i regolari ed esercizi in aula.  [[%ATTACHURL%/EserciziNFAPumping.pdf][EserciziNFAPumping.pdf]]  Il file è stato corretto, c'era un errore nel DFA prodotto.

<font size="+1"><b>venerdì 7/10/2016</b></font>
2 ore;Equivalenza tra DFA e NFA,  [[%ATTACHURL%/NFA.pdf][NFA.pdf]], Pumping Lemma per i regolari
* [[%ATTACHURL%/PumpingLemma.pdf][PumpingLemma.pdf]].

<font size="+1"><b>mercoledì 5/10/2016</b></font>
3 ore;Linguaggi e operazioni su di essi. Automi a stata finiti non deterministici [[%ATTACHURL%/Linguaggi_e_operazioni.pdf][Linguaggi_e_operazioni.pdf]], [[%ATTACHURL%/NFA.pdf][NFA.pdf]].

<font size="+1"><b>venerdì 30/09/2016</b></font>
2 ore;Introduzione alla teoria degli automi. [[%ATTACHURL%/DFA1Intr.pdf][DFA1Intr.pdf]]: il file è  stato aggiornato.

<font size="+1"><b>mercoledì 26/09/2016</b></font>
3 ore; Introduzione al corso. [[%ATTACHURL%/IntrACC16.pdf][IntrACC16.pdf]]

<hr width="100%"></hr>

<a NAME="diario15"></a><b><font color="#830AAB"><font size="+2">DIARIO DELLE LEZIONI 2015/2016 </font></font> </b>

<font size="+1"><b>venerdì 18/12/2015</b></font>
2 ore; Esercitazione sui contenuti della seconda parte del corso, [[%ATTACHURL%/EsACCDic2015.pdf][EsACCDic2015.pdf]].

<font size="+1"><b>mercoledì16/12/2015</b></font>
2 ore;teorema di Savitch. PSPACE e PSPACE-completezza,  [[%ATTACHURL%/Savitch.pdf][Savitch.pdf]], [[%ATTACHURL%/PSPACE-completeness.pdf][PSPACE-completeness.pdf]].

<font size="+1"><b>venerdì 11/12/2015</b></font>
2 ore; Esempi di problemi NPcompleti.  [[%ATTACHURL%/NPcompleti.pdf][NPcompleti.pdf]].

<font size="+1"><b>mercoledì 9/12/2015</b></font>
2 ore; 12,30 - 13,45. Teorema di Cook Levin. [[%ATTACHURL%/Cook.pdf][Cook.pdf]]

<font size="+1"><b>mercoledì 9/12/2015</b></font>
2 ore; 10,45 - 12,15. Verificatore polinomiale ed esempi di problemi in NP. [[%ATTACHURL%/DefCompl2.pdf][DefCompl2.pdf]]

<font size="+1"><b>venerdì 4/12/2015</b></font>
2 ore; lezione annullata  per evento in dipartimento "incontro con le aziende"

<font size="+1"><b>mercoledì 2/12/2015</b></font>
2 ore; Complessità: prime definizioni [[%ATTACHURL%/DefComp.pdf][DefComp.pdf]]

<font size="+1"><b>venerdì 27/11/2015</b></font>
2 ore; lezione annullata.

<font size="+1"><b>mercoledì 25/11/2015</b></font>
2 ore; Riduzioni e loro utilizzo per costruire algoritmi o dimostrare l'indecidibilità. [[%ATTACHURL%/Riduzioni.pdf][Riduzioni.pdf]],
 [[%ATTACHURL%/Rid_Indecidibilita.pdf][Rid_Indecidibilita.pdf]].

<font size="+1"><b>venerdì 20/11/2015</b></font>
2 ore; Macchina universale, Esistenza problemi non Turing riconoscibili e proprietà di chiusura dei linguaggi Turing riconoscibili,
 [[%ATTACHURL%/FermataTM.pdf][FermataTM.pdf]].

<font size="+1"><b>mercoledì 18/11/2015</b></font>
2 ore; Esistenza di problemi indecidibli. [[%ATTACHURL%/EsistenzaNonDec.pdf][EsistenzaNonDec.pdf]], [[%ATTACHURL%/IndFermataTM.pdf][IndFermataTM.pdf]]

<font size="+1"><b>venerdì 13/11/2015</b></font>
2 ore; TM a più nastri e non deterministiche [[%ATTACHURL%/TMPiuNastri.pdf][TMPiuNastri.pdf]], [[%ATTACHURL%/TM3NonDet.pdf][TM3NonDet.pdf]]

<font size="+1"><b>mercoledì 11/11/2015</b></font>
2 ore; Macchine di Turing: definizione ed esempi,  [[%ATTACHURL%/TMDef.pdf][TMDef.pdf]].

<font size="+1"><b>venerdì 6/11/2015</b></font>
2 ore; Prova intermedia. Qui i testi:   [[%ATTACHURL%/ProvaIntermediaACC2015.pdf][ProvaIntermediaACC2015.pdf]]

<font size="+1"><b>mercoledì 4/11/2015</b></font>
2 ore; Esercizi sul programma svolto, [[%ATTACHURL%/EseAula.pdf][EseAula.pdf]].

<font size="+1"><b>venerdì 30/10/2015</b></font>
2 ore; CFG e PDA. Ambiguità e proprietà di chiusura [[%ATTACHURL%/CFGePDA.pdf][CFGePDA.pdf]],
[[%ATTACHURL%/AmbiguitaCFG.pdf][AmbiguitaCFG.pdf]], [[%ATTACHURL%/IlComplemento.pdf][IlComplemento.pdf]].

<font size="+1"><b>mercoledì 28/10/2015</b></font>
2 ore; lezione non tenuta per malattia

<font size="+1"><b>venerdì 21/10/2015</b></font>
2 ore; Grammatiche acontestuali, [[%ATTACHURL%/CFGIntr.pdf][CFGIntr.pdf]].

<font size="+1"><b>mercoledì 20/10/2015</b></font>
2 ore; Automi a pila   [[%ATTACHURL%/PDA.pdf][PDA.pdf]]

<font size="+1"><b>venerdì 16/10/2015</b></font>
2 ore; lezione non tenuta per evento in Città universitaria.

<font size="+1"><b>mercoledì 14/10/2015</b></font>
2 ore; Espressioni regolari ed equivalenza DFA, [[%ATTACHURL%/EspressioniRegolari.pdf][EspressioniRegolari.pdf]].

<font size="+1"><b>venerdì 9/10/2015</b></font>
2 ore; Il pumping lemma. Esercizi di costruzione NFA e problemi di decisione per DFA [[%ATTACHURL%/PumpingLemma.pdf][PumpingLemma.pdf]]

<font size="+1"><b>mercoledì 7/10/2015</b></font>
2 ore; Automi nondeterministici, equivalenza con DFA e chiusura classe dei regolari rispetto a concatenazione e stella di Kleene,  [[%ATTACHURL%/NFA.pdf][NFA.pdf]].

<font size="+1"><b>venerdì 2/10/2015</b></font>
2 ore; Le principali operazioni sui linguaggi e la chiusura della classe dei linguaggi accettati da unDFA rispetto a queste operazioni.  [[%ATTACHURL%/Linguaggi_e_operazioni.pdf][Linguaggi_e_operazioni.pdf]]

<font size="+1"><b>mercoledì 30/9/2015</b></font>
2 ore; Definizioni formali e prime proprietà DFA  [[%ATTACHURL%/DFA1Intr.pdf][DFA1Intr.pdf]]. Ho aggiunto l'automa dell'esercizio e il teorema dimostrato a lezione

<font size="+1"><b>venerdì 25/9/2015</b></font>
2 ore; conclusione  descrizione degli argomenti che verranno trattati durante il corso. Prime definizioni: linguaggi e automi a stati finiti.

<font size="+1"><b>mercoledì 23/9/2015</b></font>
2 ore; Introduzione al corso con breve  descrizione degli argomenti che verranno trattati, [[%ATTACHURL%/IntCCII.pdf][IntCCII.pdf]].

<hr width="100%"></hr>

<a NAME="a.a2014-2015"></a><b><center><font color="#107D1D"><font size="+3">Calcolabilità e Complessità  a.a. 2014-2015</font></font></center></b>

<u></u>

<u>
<b> [[#progr14][<font size="+1"><font color="#2D1585">Programma del corso</font></font>]]</b></u>

<u>
<b> [[#diario14][<font size="+1"><font color="#2D1585">Diario delle lezioni</font></font> ]]</b></u>

<hr width="100%"></hr>

<b>Programmi definitivi dell'insegnamento di Calcolabilità e Complessità </b>

Qui trovate il programma definitivo di CC per  l'a.a. 13/14: [[%ATTACHURL%/ProgrammaCC13:14.pdf][ProgrammaCC13:14.pdf]].

Qui quello probabilmente definitivo per l'a.a. 14/15: [[%ATTACHURL%/ProgrammaCC14:15.pdf][ProgrammaCC14:15.pdf]],
e quello dell'a.a. 16/17  [[%ATTACHURL%/ProgrammaACC.pdf][ProgrammaACC.pdf]].

<hr width="100%"></hr>

<a NAME="diario14/15"></a>

<b><font color="#830AAB"><font size="+2">
DIARIO DELLE LEZIONI 2014/2015 </font>  </font> </b>

<font color="#CA1616"><font size="+1"><b>martedì 16/12/2014</b></font></font>

2 ore; La classe dei giochi: PSPACE-completi.  [[%ATTACHURL%/PSPACE.pdf][PSPACE.pdf]]

<font color="#CA1616"><font size="+1"><b>giovedì 11/12/2014</b></font></font>

2 ore; Relazione tra problemi di ricerca e di ottimizzazione e i relativi problemi di decisione. Teorema di Savithc. [[%ATTACHURL%/DECvsRicOtt.pdf][DECvsRicOtt.pdf]],
[[%ATTACHURL%/Savitch.pdf][Savitch.pdf]]

<font color="#CA1616"><font size="+1"><b>martedì 9/12/2014</b></font></font>

2 ore; conclusione rassegna problemi NP-completi.

<font color="#CA1616"><font size="+1"><b>giovedì 4/12/2014</b></font></font>

2 ore; NP-completezza, SAT e altri problemi NP-completi.   [[%ATTACHURL%/Cook.pdf][Cook.pdf]],
[[%ATTACHURL%/NP-completi.pdf][NP-completi.pdf]]

<font color="#CA1616"><font size="+1"><b>martedì 2/12/2014</b></font></font>

2 ore;Definizione alternativa di NP: il verificatore, definizioni ed esempi. coNP e sua relazione con NP, [[%ATTACHURL%/Verificatore.pdf][Verificatore.pdf]].

<font color="#CA1616"><font size="+1"><b>giovedì 27/11/2014</b></font></font>

2 ore;  Definizioni di complessità di tempo e di spazio e loro relazioni. Classi di complessità. [[%ATTACHURL%/DefComp.pdf][DefComp.pdf]].

<font color="#CA1616"><font size="+1"><b>martedì 25/11/2014</b></font></font>

2 ore; riduzioni definizioni ed esempi, [[%ATTACHURL%/Riduzioni.pdf][Riduzioni.pdf]], [[%ATTACHURL%/RideIndecidibilita.pdf][RideIndecidibilita.pdf]].

<font color="#CA1616"><font size="+1"><b>giovedì 20/11/2014</b></font></font>

2 ore; Esempi di problemi indecidibili: appartenenza e fermata per TM, esistenza problemi non Turing riconoscibili, [[%ATTACHURL%/FermataTM.pdf][FermataTM.pdf]].

<font color="#CA1616"><font size="+1"><b>martedì 18/11/2014</b></font></font>

2 ore; Esistenza di problemi indecidibili, [[%ATTACHURL%/EsistenzaNonDec.pdf][EsistenzaNonDec.pdf]].

<font color="#CA1616"><font size="+1"><b>giovedì 13/11/2014</b></font></font>

2 ore; TM non deterministiche e loro equivalenza alle deterministiche, [[%ATTACHURL%/TMNonDet.pdf][TMNonDet.pdf]].

<font color="#CA1616"><font size="+1"><b>martedì 11/11/2014</b></font></font>

2 ore; Lezione dedicata a domande sul programma svolto fino ad ora,  [[%ATTACHURL%/Domande.pdf][Domande.pdf]].

<font color="#CA1616"><font size="+1"><b>giovedì 6/11/2014</b></font></font>

2 ore; lezione sospesa per decreto rettorale - allerta meteo.

<font color="#CA1616"><font size="+1"><b>martedì 4/11/2014</b></font></font>

2 ore; Prime varianti di TM: le  TM a più nastri, [[%ATTACHURL%/TMKnastri.pdf][TMKnastri.pdf]].

<font color="#CA1616"><font size="+1"><b>giovedì 30/10/2014</b></font></font>

2 ore; Macchine di Turing: prime definizioni e proprietà.  [[%ATTACHURL%/TM1Def.pdf][TM1Def.pdf]].

<font color="#CA1616"><font size="+1"><b>martedì 28/10/2014</b></font></font>

2 ore;<font color="#07775b"><b>Lezione in aula seminari.</b></font> Il problema dell'appartenenza per CFG e altri problemi di decisione per i linguaggi contex-free. [[%ATTACHURL%/CFGalgCYK.pdf][CFGalgCYK.pdf]]

<font color="#CA1616"><font size="+1"><b>giovedì 23/10/2014</b></font></font>

2 ore; Grammatiche contex-free ed equivalenza PDA,  [[%ATTACHURL%/CFGIntr.pdf][CFGIntr.pdf]], [[%ATTACHURL%/CFGePDA.pdf][CFGePDA.pdf]]

<font color="#CA1616"><font size="+1"><b>martedì 21/10/2014</b></font></font>

2 ore; [[%ATTACHURL%/PDA.pdf][PDA.pdf]]

<font color="#CA1616"><font size="+1"><b>giovedì 16/10/2014</b></font></font>

2 ore;Automi a stati finiti non deterministici e loro equivalenza con le espressioni regolari [[%ATTACHURL%/EspressioniRegolari.pdf][EspressioniRegolari.pdf]]

<font color="#CA1616"><font size="+1"><b>martedì 14/10/2014</b></font></font>

2 ore; Il pumping lemma per i regolari. [[%ATTACHURL%/PumpingLemma.pdf][PumpingLemma.pdf]]

<font color="#CA1616"><font size="+1"><b>giovedì 9/10/2014</b></font></font>

2 ore;Automi a stati finiti non deterministici e loro equivalenza con i DFA: [[%ATTACHURL%/NFA.pdf][NFA.pdf]].

<font color="#CA1616"><font size="+1"><b>martedì 7/10/2014</b></font></font>

2 ore;DFA: prime definizioni ed esempi. [[%ATTACHURL%/DFAIntr.pdf][DFAIntr.pdf]], [[%ATTACHURL%/ChiusureDFA.pdf][ChiusureDFA.pdf]]

<font color="#CA1616"><font size="+1"><b>giovedì 2/10/2014</b></font></font>

2 ore; problemi come linguaggi, prime definizioni sui linguaggi, [[%ATTACHURL%/CCLinguaggi.pdf][CCLinguaggi.pdf]].

<font color="#CA1616"><font size="+1"><b>martedì 30/9/2014</b></font></font>

2 ore;Introduzione al corso. [[%ATTACHURL%/CCintr.pdf][CCintr.pdf]]

</td> <td width="30%">

%INCLUDE{"Scadenze"}%
----
%INCLUDE{"AvvisiImportanti"}%
----
%INCLUDE{"LinksUtili"}%
----
</td> </tr> </tbody> </table>

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
pdf	0i1jpari.pdf	r1	manage	379.5 K	2019-10-28 - 16:34	EmanuelaFachini
pdf	2SATinP_.pdf	r2 r1	manage	118.0 K	2011-12-12 - 08:49	EmanuelaFachini
pdf	ACC10Gen18.pdf	r1	manage	54.7 K	2018-01-17 - 08:12	EmanuelaFachini
pdf	ACC11Gen16T1.pdf	r1	manage	57.3 K	2016-01-15 - 16:41	EmanuelaFachini
pdf	ACC11Gen16T2.pdf	r1	manage	59.9 K	2016-01-15 - 16:49	EmanuelaFachini
pdf	ACC11Giu19.pdf	r1	manage	56.3 K	2019-06-12 - 07:25	EmanuelaFachini
pdf	ACC12Apr2019.pdf	r1	manage	48.1 K	2019-05-20 - 12:12	EmanuelaFachini
pdf	ACC13Gen20.pdf	r1	manage	22.0 K	2020-01-28 - 13:09	EmanuelaFachini
pdf	ACC13Gen20EsameCompleto.pdf	r1	manage	31.5 K	2020-01-19 - 18:19	EmanuelaFachini
pdf	ACC14Gen19.pdf	r1	manage	45.8 K	2019-01-22 - 10:32	EmanuelaFachini
pdf	ACC16apr18.pdf	r1	manage	51.3 K	2018-04-16 - 14:37	EmanuelaFachini
pdf	ACC17Giu20.pdf	r1	manage	33.3 K	2020-09-11 - 19:13	EmanuelaFachini
pdf	ACC1lu16.pdf	r1	manage	54.7 K	2016-09-14 - 15:21	EmanuelaFachini
pdf	ACC20Sett18.pdf	r1	manage	49.6 K	2018-09-21 - 08:51	EmanuelaFachini
pdf	ACC2serie_1.pdf	r1	manage	20.4 K	2019-11-18 - 16:36	EmanuelaFachini
pdf	ACC2serie_2.pdf	r1	manage	34.6 K	2019-11-18 - 16:36	EmanuelaFachini
pdf	ACC2serie_3.pdf	r1	manage	20.3 K	2019-11-18 - 16:36	EmanuelaFachini
pdf	ACC2serie_4.pdf	r1	manage	38.2 K	2019-11-18 - 16:36	EmanuelaFachini
pdf	ACC3Feb20.pdf	r1	manage	20.9 K	2020-02-05 - 12:08	EmanuelaFachini
pdf	ACC3_serie_1_.pdf	r1	manage	17.1 K	2019-11-29 - 16:55	EmanuelaFachini
pdf	ACC3_serie_2.pdf	r1	manage	15.1 K	2019-11-29 - 16:55	EmanuelaFachini
pdf	ACC3_serie_3.pdf	r1	manage	17.3 K	2019-11-29 - 16:55	EmanuelaFachini
pdf	ACC3_serie_4.pdf	r1	manage	15.0 K	2019-11-29 - 16:55	EmanuelaFachini
pdf	ACC4Dic11RidV1_.pdf	r1	manage	16.9 K	2019-12-13 - 18:38	EmanuelaFachini
pdf	ACC4Dic11V1.pdf	r1	manage	17.9 K	2019-12-13 - 18:38	EmanuelaFachini
pdf	ACC4Dic11V2.pdf	r1	manage	18.1 K	2019-12-13 - 18:38	EmanuelaFachini
pdf	ACC4Feb19.pdf	r1	manage	63.6 K	2019-04-02 - 13:22	EmanuelaFachini
pdf	ACC4Maggio20.pdf	r2 r1	manage	19.1 K	2020-05-31 - 07:15	EmanuelaFachini
pdf	ACC5luglio2019.pdf	r1	manage	48.5 K	2019-07-10 - 07:55	EmanuelaFachini
pdf	ACC6Giu18.pdf	r1	manage	30.0 K	2018-06-12 - 12:57	EmanuelaFachini
pdf	ACC7Nov16.pdf	r1	manage	52.3 K	2016-11-17 - 14:36	EmanuelaFachini
pdf	ACC8Giu16.pdf	r2 r1	manage	63.3 K	2016-07-01 - 07:35	EmanuelaFachini
pdf	ACC8Lu2020.pdf	r1	manage	23.5 K	2020-09-11 - 19:09	EmanuelaFachini
pdf	ACCFeb17.pdf	r1	manage	49.3 K	2017-02-05 - 11:34	EmanuelaFachini
pdf	ACCGiu17.pdf	r1	manage	49.9 K	2017-06-05 - 14:53	EmanuelaFachini
pdf	ACCSett19.pdf	r1	manage	58.7 K	2019-09-19 - 15:23	EmanuelaFachini
pdf	AmbiguitCFG.pdf	r2 r1	manage	110.3 K	2017-11-11 - 15:16	EmanuelaFachini
pdf	AppStrACCApr17.pdf	r1	manage	50.6 K	2017-03-29 - 15:31	EmanuelaFachini
pdf	AppuntiAlgVuotoCFG.pdf	r1	manage	29.6 K	2018-11-02 - 08:56	EmanuelaFachini
pdf	CFG.pdf	r3 r2 r1	manage	127.3 K	2017-11-11 - 13:35	EmanuelaFachini
pdf	CFGePDA.pdf	r2 r1	manage	108.0 K	2017-11-11 - 15:16	EmanuelaFachini
pdf	ChiusCFLDec.pdf	r1	manage	71.7 K	2019-11-02 - 11:31	EmanuelaFachini
pdf	ChiusureCFL.pdf	r2 r1	manage	145.2 K	2016-11-03 - 17:08	EmanuelaFachini
pdf	Chiusure_e_Rice.pdf	r6 r5 r4 r3 r2	manage	140.6 K	2013-10-31 - 09:05	EmanuelaFachini
pdf	ClassiCompl.pdf	r4 r3 r2 r1	manage	284.3 K	2017-12-05 - 10:01	EmanuelaFachini
pdf	CommentoValACCDic15.pdf	r1	manage	17.5 K	2015-12-22 - 13:21	EmanuelaFachini
pdf	ComplessitaDef.pdf	r1	manage	276.3 K	2012-11-20 - 10:49	EmanuelaFachini
pdf	Cook.pdf	r3 r2 r1	manage	179.1 K	2015-12-09 - 15:49	EmanuelaFachini
pdf	Copia_di_ElEserciziAula19.pdf	r1	manage	236.0 K	2019-12-16 - 11:11	EmanuelaFachini
pdf	DECvsRic.pdf	r1	manage	107.9 K	2013-12-05 - 11:28	EmanuelaFachini
pdf	DECvsRicOtt.pdf	r1	manage	88.2 K	2014-12-10 - 14:10	EmanuelaFachini
pdf	DFA1Intr.pdf	r5 r4 r3 r2 r1	manage	237.2 K	2017-10-06 - 13:10	EmanuelaFachini
pdf	DFAIntr.pdf	r2 r1	manage	165.7 K	2016-09-30 - 12:20	EmanuelaFachini
pdf	DecChiusCFL.pdf	r1	manage	92.8 K	2017-11-24 - 14:31	EmanuelaFachini
pdf	DefComp.pdf	r2 r1	manage	212.6 K	2015-12-02 - 14:49	EmanuelaFachini
pdf	DefCompl1.pdf	r1	manage	171.5 K	2011-11-02 - 11:22	EmanuelaFachini
pdf	DefCompl2.pdf	r1	manage	226.7 K	2015-12-09 - 15:48	EmanuelaFachini
pdf	Diagonalizzazione.pdf	r1	manage	77.2 K	2012-10-16 - 10:26	EmanuelaFachini
pdf	ESAMI-ONLINE.pdf	r1	manage	60.1 K	2020-04-27 - 15:50	EmanuelaFachini
pdf	Es1.pdf	r1	manage	526.7 K	2019-10-27 - 11:38	EmanuelaFachini
pdf	Es2.pdf	r1	manage	262.9 K	2019-10-23 - 14:15	EmanuelaFachini
pdf	Es2010.pdf	r1	manage	17.9 K	2017-10-23 - 14:24	EmanuelaFachini
pdf	Es20Dic17.pdf	r1	manage	29.3 K	2017-12-20 - 14:08	EmanuelaFachini
pdf	Es20dic2018.pdf	r1	manage	20.0 K	2018-12-28 - 11:52	EmanuelaFachini
pdf	Es22Dic17.pdf	r1	manage	52.8 K	2017-12-22 - 14:07	EmanuelaFachini
pdf	Es3.pdf	r1	manage	231.1 K	2019-10-23 - 14:15	EmanuelaFachini
pdf	Es311.pdf	r1	manage	27.2 K	2017-11-20 - 15:52	EmanuelaFachini
pdf	Es4.pdf	r1	manage	229.8 K	2019-10-23 - 14:15	EmanuelaFachini
pdf	Es4CC2015.pdf	r1	manage	29.1 K	2016-01-25 - 15:32	EmanuelaFachini
pdf	Es811.pdf	r1	manage	20.0 K	2017-11-20 - 15:52	EmanuelaFachini
pdf	EsACC15Nov.pdf	r2 r1	manage	26.2 K	2017-11-20 - 15:52	EmanuelaFachini
pdf	EsACC17Nov.pdf	r1	manage	26.0 K	2017-11-19 - 08:57	EmanuelaFachini
pdf	EsACC29Nov.pdf	r1	manage	17.7 K	2017-12-01 - 15:09	EmanuelaFachini
pdf	EsACC4Dic.pdf	r1	manage	15.8 K	2017-12-01 - 15:07	EmanuelaFachini
pdf	EsACCDic2015.pdf	r1	manage	46.8 K	2015-12-21 - 14:00	EmanuelaFachini
pdf	EsAula21dic2016.pdf	r1	manage	280.1 K	2016-12-21 - 20:01	EmanuelaFachini
pdf	EsAula29Nov.pdf	r1	manage	31.8 K	2017-12-04 - 17:01	EmanuelaFachini
pdf	EsAula4Dic.pdf	r1	manage	28.5 K	2017-12-04 - 17:01	EmanuelaFachini
pdf	EsEsame18Ott17.pdf	r1	manage	12.5 K	2017-10-19 - 12:49	EmanuelaFachini
pdf	EsNFA1.pdf	r1	manage	232.0 K	2019-10-23 - 15:22	EmanuelaFachini
pdf	Esaula20nov19.pdf	r3 r2 r1	manage	82.6 K	2019-11-24 - 09:41	EmanuelaFachini
pdf	Esercizi19ott18.pdf	r1	manage	66.8 K	2018-11-13 - 17:09	EmanuelaFachini
pdf	Esercizi29novembre2018.pdf	r1	manage	39.6 K	2018-11-29 - 13:58	EmanuelaFachini
pdf	Esercizi9novembre2018.pdf	r2 r1	manage	58.8 K	2018-11-14 - 14:58	EmanuelaFachini
pdf	EserciziAutomi.pdf	r1	manage	22.6 K	2017-10-13 - 14:28	EmanuelaFachini
pdf	EserciziDecTuringRic.pdf	r1	manage	90.8 K	2016-12-07 - 15:28	EmanuelaFachini
pdf	EserciziNFAePDA.pdf	r3 r2 r1	manage	475.6 K	2017-11-03 - 14:14	EmanuelaFachini
pdf	EserciziNFAePDA_.pdf	r1	manage	497.3 K	2017-10-30 - 10:03	EmanuelaFachini
pdf	EsistenzaNonDec.pdf	r4 r3 r2 r1	manage	104.8 K	2015-11-18 - 14:45	EmanuelaFachini
pdf	EspressioniRegolari.pdf	r2 r1	manage	308.5 K	2017-10-21 - 14:25	EmanuelaFachini
pdf	FermataTM.pdf	r3 r2 r1	manage	156.7 K	2015-11-21 - 09:11	EmanuelaFachini
jpg	IMG_0822.JPG	r1	manage	1792.4 K	2016-02-11 - 09:18	EmanuelaFachini
jpg	IMG_0823.JPG	r1	manage	1934.5 K	2016-02-11 - 09:13	EmanuelaFachini
jpg	IMG_0824.JPG	r1	manage	1896.5 K	2016-02-11 - 09:38	EmanuelaFachini
pdf	IlComplemento.pdf	r1	manage	29.7 K	2015-10-30 - 14:52	EmanuelaFachini
pdf	InPoltreNP.pdf	r2 r1	manage	262.8 K	2017-12-22 - 14:07	EmanuelaFachini
pdf	IndFermataTM.pdf	r3 r2 r1	manage	57.6 K	2017-11-24 - 14:18	EmanuelaFachini
pdf	IntCCII.pdf	r1	manage	851.4 K	2015-09-23 - 15:15	EmanuelaFachini
pdf	IntrACC.pdf	r1	manage	1321.4 K	2019-09-20 - 10:55	EmanuelaFachini
pdf	IntrACC17.pdf	r1	manage	650.9 K	2017-10-04 - 14:06	EmanuelaFachini
docx	IstrStudenti.docx	r1	manage	11.0 K	2020-04-27 - 15:50	EmanuelaFachini
pdf	J.Edmonds.pdf	r1	manage	2063.1 K	2018-12-10 - 09:39	EmanuelaFachini
pdf	L__NL.pdf	r5 r4 r3 r2 r1	manage	102.1 K	2014-01-07 - 11:15	EmanuelaFachini
pdf	LinguaggiDFA.pdf	r1	manage	178.5 K	2019-09-24 - 08:49	EmanuelaFachini
pdf	Linguaggi_e_operazioni.pdf	r3 r2 r1	manage	113.6 K	2017-10-19 - 07:09	EmanuelaFachini
pdf	MATACC10Gen18.pdf	r1	manage	28.7 K	2018-01-17 - 08:41	EmanuelaFachini
pdf	MATACCsett18.pdf	r1	manage	31.2 K	2018-09-21 - 07:43	EmanuelaFachini
pdf	MATValACCFeb16.pdf	r1	manage	39.0 K	2016-02-05 - 10:00	EmanuelaFachini
pdf	Mat.Val.Turno3.pdf	r1	manage	37.5 K	2018-11-02 - 16:43	EmanuelaFachini
pdf	Mat.Val.turno2.pdf	r1	manage	47.1 K	2018-11-02 - 16:43	EmanuelaFachini
pdf	MatACC13Gen20EsParziale.pdf	r1	manage	309.7 K	2020-01-19 - 22:24	EmanuelaFachini
pdf	MatACC13Genn17.pdf	r1	manage	53.7 K	2017-01-20 - 16:35	EmanuelaFachini
pdf	MatACC17Giu20.pdf	r1	manage	54.2 K	2020-06-18 - 14:34	EmanuelaFachini
pdf	MatACC27giu18.pdf	r1	manage	25.8 K	2018-06-28 - 10:03	EmanuelaFachini
pdf	MatACC28giu17.pdf	r1	manage	25.4 K	2017-06-28 - 16:25	EmanuelaFachini
pdf	MatACC31Gen2018.pdf	r1	manage	39.5 K	2018-02-07 - 11:50	EmanuelaFachini
pdf	MatACC3Feb2020.pdf	r1	manage	29.2 K	2020-02-06 - 09:57	EmanuelaFachini
pdf	MatACC4Feb2019.pdf	r1	manage	22.4 K	2019-02-06 - 10:54	EmanuelaFachini
pdf	MatACC4sett17.pdf	r1	manage	58.8 K	2017-09-06 - 10:19	EmanuelaFachini
pdf	MatACC5Giu17.pdf	r1	manage	40.0 K	2017-06-08 - 12:09	EmanuelaFachini
numbers	MatACCFeb17.numbers	r1	manage	711.8 K	2017-02-27 - 10:43	EmanuelaFachini
pdf	MatACCFeb17.pdf	r1	manage	50.6 K	2017-02-27 - 11:05	EmanuelaFachini
pdf	MatACCMarzo2017.pdf	r1	manage	36.7 K	2017-03-27 - 14:14	EmanuelaFachini
pdf	MatACCNov16.pdf	r1	manage	61.3 K	2016-11-22 - 17:04	EmanuelaFachini
pdf	MatACCSett19.pdf	r1	manage	28.9 K	2019-09-19 - 10:16	EmanuelaFachini
pdf	MatACCapr19.pdf	r1	manage	33.0 K	2019-04-16 - 13:41	EmanuelaFachini
pdf	MatACCgiu19.pdf	r1	manage	27.3 K	2019-06-13 - 16:28	EmanuelaFachini
pdf	MatACCluglio19.pdf	r1	manage	40.1 K	2019-07-08 - 08:14	EmanuelaFachini
pdf	MatElEserciziAula19.pdf	r4 r3 r2 r1	manage	330.5 K	2019-12-17 - 20:30	EmanuelaFachini
numbers	MatEs201920.numbers	r1	manage	188.2 K	2019-11-15 - 16:25	EmanuelaFachini
pdf	MatEs201920.pdf	r1	manage	255.8 K	2019-11-15 - 16:26	EmanuelaFachini
pdf	MatEsACC4nov2019.pdf	r1	manage	41.1 K	2019-11-05 - 16:13	EmanuelaFachini
pdf	MatEsAulaMercoledi1718.pdf	r1	manage	32.6 K	2017-11-20 - 15:40	EmanuelaFachini
pdf	MatEsAulaVenerd1718.pdf	r1	manage	28.7 K	2017-11-20 - 15:40	EmanuelaFachini
pdf	MatEsRecupero16Dic19.pdf	r1	manage	67.8 K	2019-12-17 - 10:30	EmanuelaFachini
pdf	MatEsVenerd3Nov.pdf	r1	manage	34.4 K	2017-11-13 - 16:06	EmanuelaFachini
pdf	MatEsame2020.pdf	r1	manage	29.3 K	2019-12-02 - 11:01	EmanuelaFachini
pdf	MatEsameACCParziale.pdf	r1	manage	24.5 K	2017-12-29 - 14:26	EmanuelaFachini
pdf	MatIntrAlg3Feb2020.pdf	r1	manage	42.4 K	2020-02-06 - 09:02	EmanuelaFachini
pdf	MatPreEs201920.pdf	r5 r4 r3 r2 r1	manage	249.0 K	2019-11-15 - 13:15	EmanuelaFachini
pdf	MatPrenUltimoEs11Dic2019.pdf	r1	manage	125.3 K	2019-12-02 - 11:01	EmanuelaFachini
pdf	MatRidRec11Dic19.pdf	r1	manage	78.5 K	2019-12-02 - 11:01	EmanuelaFachini
pdf	MatStraACC4nov2019.pdf	r1	manage	21.9 K	2019-11-05 - 13:05	EmanuelaFachini
pdf	MatVal.Pren.Turno3.pdf	r1	manage	40.1 K	2018-11-20 - 16:04	EmanuelaFachini
pdf	MatVal.turno2Es1e2.pdf	r1	manage	48.5 K	2018-11-20 - 16:04	EmanuelaFachini
pdf	MatValACC.pdf	r1	manage	55.5 K	2019-01-18 - 09:40	EmanuelaFachini
pdf	MatValACC16Apr2018.pdf	r1	manage	18.6 K	2018-04-17 - 09:03	EmanuelaFachini
pdf	MatValACCSett16.pdf	r1	manage	30.0 K	2016-09-21 - 09:04	EmanuelaFachini
pdf	MatValEsParziale13gen2020.pdf	r1	manage	459.9 K	2020-01-19 - 18:19	EmanuelaFachini
pdf	MatValEsonACC.pdf	r1	manage	77.7 K	2019-01-01 - 08:54	EmanuelaFachini
pdf	MatValPren.Turno1Es1e2.pdf	r1	manage	40.6 K	2018-11-20 - 16:04	EmanuelaFachini
pdf	MatValTurno1.pdf	r2 r1	manage	36.8 K	2018-11-04 - 09:59	EmanuelaFachini
pdf	MatValTurno1Es123.pdf	r1	manage	37.9 K	2018-12-06 - 15:45	EmanuelaFachini
pdf	MatValTurno3Es123.pdf	r1	manage	38.8 K	2018-12-06 - 15:45	EmanuelaFachini
pdf	MatValturno2Es123.pdf	r1	manage	44.6 K	2018-12-06 - 15:45	EmanuelaFachini
pdf	MergeSort_con_analisi.pdf	r1	manage	166.5 K	2017-05-03 - 15:29	EmanuelaFachini
pdf	ModuloTM1.pdf	r1	manage	94.2 K	2018-11-19 - 10:34	EmanuelaFachini
pdf	NFA.pdf	r9 r8 r7 r6 r5	manage	566.4 K	2019-10-01 - 17:14	EmanuelaFachini
pdf	NFA2.pdf	r1	manage	395.5 K	2019-10-23 - 15:22	EmanuelaFachini
pdf	NFAdefDimEq.pdf	r1	manage	350.5 K	2017-10-13 - 14:28	EmanuelaFachini
pdf	NL=coNL.pdf	r1	manage	114.5 K	2014-01-09 - 13:30	EmanuelaFachini
pdf	NP-complCook.pdf	r1	manage	332.4 K	2016-12-05 - 16:43	EmanuelaFachini
pdf	NPcomplCook.pdf	r1	manage	171.3 K	2017-12-13 - 14:54	EmanuelaFachini
pdf	NPcompleti2.pdf	r1	manage	106.1 K	2017-12-15 - 14:16	EmanuelaFachini
pdf	NPcompleti_.pdf	r3 r2 r1	manage	156.5 K	2017-12-13 - 14:52	EmanuelaFachini
zip	NTM.zip	r2 r1	manage	104.2 K	2011-10-18 - 08:58	EmanuelaFachini	file aggiornato con esempi
pdf	NonDec.pdf	r3 r2 r1	manage	191.7 K	2012-10-23 - 09:26	EmanuelaFachini
pdf	NonDecEsiste.pdf	r1	manage	104.6 K	2017-11-22 - 14:46	EmanuelaFachini
jff	NonDetScriveBin.jff	r1	manage	1.9 K	2013-10-15 - 10:23	EmanuelaFachini
pdf	NumerabilitTuringCalc.pdf	r2 r1	manage	51.1 K	2017-11-26 - 17:27	EmanuelaFachini
pdf	PDA.pdf	r2 r1	manage	260.5 K	2017-11-02 - 08:32	EmanuelaFachini
pdf	PIACCNov16.pdf	r1	manage	49.9 K	2016-11-12 - 12:59	EmanuelaFachini
pdf	PSPACE-completeness.pdf	r9 r8 r7 r6 r5	manage	175.4 K	2015-12-21 - 11:09	EmanuelaFachini
pdf	Parity_games.pdf	r1	manage	88.3 K	2013-12-17 - 11:13	EmanuelaFachini
pdf	PorblemiDecDFA.pdf	r2 r1	manage	63.1 K	2019-10-09 - 14:08	EmanuelaFachini
pdf	PrePIACC15.pdf	r2 r1	manage	41.8 K	2015-11-11 - 15:31	EmanuelaFachini
pdf	Pren.Turno1030-1115.pdf	r1	manage	47.4 K	2018-10-17 - 14:50	EmanuelaFachini
pdf	Pren.Turno1220-1255.pdf	r1	manage	51.2 K	2018-10-17 - 14:52	EmanuelaFachini
pdf	Pren.turno1120-1215.pdf	r2 r1	manage	51.7 K	2018-10-17 - 15:06	EmanuelaFachini
pdf	PrenACC6Giu18.pdf	r1	manage	37.1 K	2018-06-06 - 16:31	EmanuelaFachini
pdf	PresPrenUltimoEs11Dic2019.pdf	r1	manage	133.6 K	2019-12-03 - 11:21	EmanuelaFachini
pdf	PresRecupero16Dic19.pdf	r1	manage	90.4 K	2019-12-03 - 11:26	EmanuelaFachini
pdf	PresRidRec11Dic19.pdf	r1	manage	77.9 K	2019-12-03 - 11:21	EmanuelaFachini
pdf	PrimeChiusure.pdf	r3 r2 r1	manage	613.7 K	2019-10-24 - 10:49	EmanuelaFachini
pdf	ProgCC2010:2011.pdf	r1	manage	27.4 K	2012-01-26 - 11:20	EmanuelaFachini
pdf	ProgCC2011:2012.pdf	r2 r1	manage	28.6 K	2012-01-26 - 11:21	EmanuelaFachini
pdf	ProgrammaACC.pdf	r1	manage	36.7 K	2017-05-29 - 09:48	EmanuelaFachini
pdf	ProgrammaACC1617.pdf	r3 r2 r1	manage	45.9 K	2016-12-15 - 11:49	EmanuelaFachini
pdf	ProgrammaACC17-18.pdf	r1	manage	40.2 K	2018-02-20 - 08:27	EmanuelaFachini
pdf	ProgrammaACC1819.pdf	r1	manage	35.5 K	2019-06-13 - 16:22	EmanuelaFachini
pdf	ProgrammaACC1920Parti_I_e_II.pdf	r1	manage	32.5 K	2019-11-26 - 11:31	EmanuelaFachini
pdf	ProgrammaCC13:14.pdf	r1	manage	28.0 K	2014-01-07 - 11:16	EmanuelaFachini
pdf	ProgrammaCC14:15.pdf	r1	manage	34.3 K	2014-11-17 - 11:34	EmanuelaFachini
pdf	ProgrammaCC1516.pdf	r1	manage	34.5 K	2016-10-10 - 13:13	EmanuelaFachini
pdf	ProvaIntermediaACC2015.pdf	r1	manage	39.5 K	2015-11-06 - 20:19	EmanuelaFachini
pdf	PumpingLemma.pdf	r2 r1	manage	144.3 K	2019-10-08 - 11:26	EmanuelaFachini
pdf	QuickSort.pdf	r1	manage	127.4 K	2017-05-03 - 13:04	EmanuelaFachini
pdf	RelRic.pdf	r1	manage	210.1 K	2017-05-03 - 15:29	EmanuelaFachini
pdf	RidEs20Dic17.pdf	r1	manage	54.2 K	2017-12-22 - 15:25	EmanuelaFachini
pdf	Rid_Indecidibilita.pdf	r1	manage	75.6 K	2015-11-25 - 14:08	EmanuelaFachini
pdf	RideIndecidibilit.pdf	r3 r2 r1	manage	85.4 K	2017-11-30 - 07:40	EmanuelaFachini
pdf	Riduzione22Dic17.pdf	r1	manage	61.4 K	2017-12-22 - 15:25	EmanuelaFachini
pdf	Riduzioni.pdf	r4 r3 r2 r1	manage	133.0 K	2017-11-30 - 07:40	EmanuelaFachini
pdf	Savitch.pdf	r3 r2 r1	manage	147.3 K	2017-12-15 - 14:16	EmanuelaFachini
pdf	SolACC11Giu19.pdf	r1	manage	71.2 K	2019-07-02 - 14:33	EmanuelaFachini
pdf	SolACC14Gen19.pdf	r1	manage	52.4 K	2019-01-28 - 09:18	EmanuelaFachini
pdf	SolACC17Sett20.pdf	r1	manage	58.2 K	2020-09-24 - 13:28	EmanuelaFachini
pdf	SolACC4Maggio20.pdf	r2 r1	manage	62.2 K	2020-05-06 - 12:22	EmanuelaFachini
pdf	SolACC5luglio2019.pdf	r1	manage	59.1 K	2019-07-14 - 10:48	EmanuelaFachini
pdf	SolACC7Nov16.pdf	r3 r2 r1	manage	84.2 K	2016-12-07 - 15:28	EmanuelaFachini
pdf	SolACCGiu17.pdf	r2 r1	manage	60.0 K	2018-10-18 - 05:57	EmanuelaFachini
pdf	SolEs20dic2018.pdf	r1	manage	28.8 K	2018-12-29 - 11:53	EmanuelaFachini
pdf	SolEsNFA-R.E_e_riduzione.pdf	r2 r1	manage	201.6 K	2019-09-19 - 15:32	EmanuelaFachini
pdf	SolEsPI14Nov12.pdf	r1	manage	80.9 K	2012-11-20 - 11:09	EmanuelaFachini
pdf	SolEsPumping.pdf	r3 r2 r1	manage	36.0 K	2019-10-14 - 13:54	EmanuelaFachini
pdf	SolEsercizi29novembre2018.pdf	r1	manage	56.7 K	2018-11-29 - 13:58	EmanuelaFachini
pdf	SolPIACCNov16.pdf	r1	manage	60.0 K	2016-11-17 - 13:34	EmanuelaFachini
pdf	StraordACC4nov2019.pdf	r1	manage	60.1 K	2019-11-07 - 14:14	EmanuelaFachini
pdf	StudentiTurno1.pdf	r2 r1	manage	48.1 K	2018-11-06 - 16:34	EmanuelaFachini
pdf	StudentiTurno2.pdf	r3 r2 r1	manage	59.6 K	2018-11-06 - 16:34	EmanuelaFachini
pdf	StudentiTurno3.pdf	r2 r1	manage	47.3 K	2018-11-06 - 16:34	EmanuelaFachini
zip	TM.zip	r1	manage	155.7 K	2013-10-03 - 10:20	EmanuelaFachini
pdf	TM1Def.pdf	r2 r1	manage	442.8 K	2014-11-03 - 14:58	EmanuelaFachini
jff	TM2Nastri0n1n.jff	r2 r1	manage	1.6 K	2013-10-10 - 12:32	EmanuelaFachini
pdf	TM3NonDet.pdf	r1	manage	130.7 K	2015-11-17 - 15:49	EmanuelaFachini
pdf	TM5Rid.pdf	r5 r4 r3 r2 r1	manage	165.6 K	2011-11-17 - 11:51	EmanuelaFachini
pdf	TMDef.pdf	r3 r2 r1	manage	633.4 K	2017-11-15 - 14:09	EmanuelaFachini
pdf	TMKnastri.pdf	r7 r6 r5 r4 r3	manage	249.2 K	2019-11-05 - 16:29	EmanuelaFachini
pdf	TMNonDet.pdf	r5 r4 r3 r2 r1	manage	309.5 K	2017-11-22 - 14:46	EmanuelaFachini
pdf	TMUniv-Fermata.pdf	r1	manage	183.8 K	2011-10-18 - 09:01	EmanuelaFachini
pdf	TMUniversale.pdf	r3 r2 r1	manage	129.8 K	2017-11-24 - 14:18	EmanuelaFachini
zip	TMesempi.zip	r2 r1	manage	3.0 K	2012-10-09 - 09:26	EmanuelaFachini
zip	TMknastri.zip	r1	manage	98.7 K	2011-10-12 - 10:16	EmanuelaFachini
pdf	TestoACC4Sett17.pdf	r1	manage	52.0 K	2017-09-06 - 10:19	EmanuelaFachini
pdf	Turing.pdf	r1	manage	42.1 K	2018-09-24 - 13:17	EmanuelaFachini
pdf	Turing36.pdf	r1	manage	331.5 K	2013-10-15 - 10:37	EmanuelaFachini
pdf	UltimoGiaOPresente.pdf	r1	manage	260.8 K	2019-10-23 - 15:22	EmanuelaFachini
pdf	ValACC11Gen16.pdf	r1	manage	43.5 K	2016-01-14 - 16:09	EmanuelaFachini
pdf	ValACC4Maggio2020.pdf	r1	manage	42.6 K	2020-05-06 - 10:04	EmanuelaFachini
pdf	ValACC8Lu20.pdf	r1	manage	27.8 K	2020-07-10 - 16:09	EmanuelaFachini
pdf	ValACCDic15.pdf	r2 r1	manage	36.5 K	2015-12-22 - 13:29	EmanuelaFachini
pdf	ValACCEs20ott17.pdf	r1	manage	35.9 K	2017-10-23 - 14:16	EmanuelaFachini
pdf	ValACCEsAulaMercoled18Ott.pdf	r1	manage	36.7 K	2017-10-23 - 14:16	EmanuelaFachini
pdf	ValACCMercoled1718.pdf	r2 r1	manage	30.0 K	2017-12-29 - 13:51	EmanuelaFachini
pdf	ValACCVenerd1718.pdf	r1	manage	29.5 K	2017-12-29 - 12:10	EmanuelaFachini
pdf	ValACCsett20.pdf	r1	manage	56.8 K	2020-09-21 - 07:23	EmanuelaFachini
pdf	ValACCstraordOtt20.pdf	r1	manage	46.5 K	2020-10-14 - 20:42	EmanuelaFachini
pdf	Verificatore.pdf	r5 r4 r3 r2 r1	manage	241.4 K	2017-12-06 - 14:26	EmanuelaFachini
pdf	_ACC13Gen17.pdf	r1	manage	67.8 K	2017-01-17 - 16:29	EmanuelaFachini
pdf	_ACC17Sett20_17.01.07.pdf	r1	manage	45.6 K	2020-09-17 - 17:42	EmanuelaFachini
pdf	algCYK.pdf	r1	manage	187.6 K	2016-10-24 - 13:03	EmanuelaFachini
pdf	appunti_cnf.pdf	r2 r1	manage	54.1 K	2018-10-31 - 21:54	EmanuelaFachini
pdf	coNP.pdf	r5 r4 r3 r2 r1	manage	295.1 K	2017-12-20 - 14:08	EmanuelaFachini
pdf	cobham_intrinsic.pdf	r1	manage	378.0 K	2018-12-10 - 09:39	EmanuelaFachini
pdf	matEsVenerd3Nov.pdf	r1	manage	35.3 K	2017-11-13 - 15:55	EmanuelaFachini
pdf	matMercoled8Nov.pdf	r1	manage	37.6 K	2017-11-13 - 15:55	EmanuelaFachini
pdf	moduloTM2.pdf	r1	manage	112.2 K	2018-11-19 - 10:34	EmanuelaFachini
pdf	moduloTM3.pdf	r1	manage	102.0 K	2018-11-19 - 10:34	EmanuelaFachini
pdf	tempoSpazioTM.pdf	r1	manage	200.3 K	2013-11-19 - 11:23	EmanuelaFachini
pdf	ultimoNonPresente.pdf	r1	manage	242.3 K	2019-10-23 - 15:28	EmanuelaFachini