Automi, Calcolabilità e Complessità
a.a. 2019/2020

Prof. EMANUELA FACHINI
STUDIO: D.to Scienze dell'Informazione Via Salaria,113 - 00198 ROMA
TEL: 0649918314.
E-MAIL: fachini[AT]di.uniroma1.it
ORARIO DI RICEVIMENTO: Mercoledì ore 10,30-12,30 o su appuntamento.


Diario delle lezioni dell'a.a. 2019/2020

Diario delle lezioni dell'a.a. 2018/2019 Diario delle lezioni dell'a.a. 2017/2018 Diario delle lezioni di Calcolabilità e Complessità dell'a.a. 2016-2017 Diario delle lezioni dell'a.a. 2015-2016


Avvisi per gli studenti Presentazione del corso

Informazioni generali: lezioni, libro di testo, esercizi proposti nelle sedute di esami, valutazioni degli esami appelli a.a. 2016/2017.

Obiettivi e risultati attesi

Programma del corso


Avvisi

Appello di ottobre

Qui la valutazione della prova scritta ValACCstraordOtt20.pdf.

Appello di settembre

Il testo: _ACC17Sett20_17.01.07.pdf e la valutazione: ValACCsett20.pdf. La soluzione: SolACC17Sett20.pdf.

Testo prova di luglio

Qui il testo: * ACC8Lu2020.pdf.

testo prova di giugno

Qui il testo ACC17Giu20.pdf.

Aggiornamento sull'appello di giugno

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.

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à. 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.

Attrezzature necessarie

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!

Azioni da compiere

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à.

Sessioni di prova

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.

Inquadratura della postazione di lavoro mediante cellulare

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.

testo prova del 4 maggio 2020

ACC4Maggio20.pdf.

valutazione prova del 3 febbraio 2020

Qui i voti: MatACC3Feb2020.pdf, le persone non elencate sono risultate insufficienti.

testo della prova del 13 gennaio e de 3 febbraio 2020

ACC13Gen20.pdf, ACC3Feb20.pdf.

Avviso appello gennaio: la valutazione

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 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. 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ì.

La valutazione finale

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.

Organizzazione prossimi esoneri e testi del primo

Qui i testi dell'esercitazione dell'11 dicembre: ACC4Dic11RidV1_.pdf, ACC4Dic11V2.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. PresRidRec11Dic19.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à. 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.

Valutazione esercitazione in aula

Dovete cercarvi in uno dei file allegati. Alcuni sono direttamente ammessi all'ultima esercitazione dell'11 dicembre: 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à. MatRidRec11Dic19.pdf. Alcuni sono invitati a presentarsi il 16 dicembre in orario di lezione per un esonero di recupero delle insufficienze. MatEsRecupero16Dic19.pdf. Altri ancora sono rinviati agli appelli di esame di gennaio e febbraio. 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.

Testi esercitazione in aula

ACC3_serie_2.pdf, ACC3_serie_4.pdf, ACC3_serie_3.pdf, ACC3_serie_1_.pdf.

Esonero non frequentanti 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.

Programma parziale 2019/2020 Qui il programma svolto finora. ProgrammaACC1920Parti_I_e_II.pdf.

Testo e soluzione esercizi proposti per l'appello straordinario e in aula

Qui testo e soluzioni esercizi proposti in aula: ACC2serie_3.pdf, ACC2serie_4.pdf, ACC2serie_2.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. StraordACC4nov2019.pdf

Avviso valutazione seconda serie di esercizi in aula

Trovate qui i risultati della valutazione 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ì.

Avviso valutazione esonero del 4 novembre

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: MatEsACC4nov2019.pdf. Chi vuole visionare la correzione può venire martedì mattina alle 11 nel mio ufficio di via salaria.

Avviso nuove modalità esoneri

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.

Avviso apertura fogli prenotazioni esoneri ACC

Gli studenti frequentanti 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 non frequentanti è 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!!

Avviso scambio lezioni 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.

Avviso appello di settembre

Qui trovate la valutazione della prova scritta: 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: ACCSett19.pdf, SolEsNFA-R.E_e_riduzione.pdf.

Appello del 5 luglio 2019: il testo, la soluzione e la valutazione

Qui il testo della prova: ACC5luglio2019.pdf,

La soluzione: SolACC5luglio2019.pdf.

L'esito della valutazione: 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.

Appello dell'11 giugno 2019: valutazione

In questo file l'esito della valutazione. 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.

Appello dell'11 giugno 2019 Gli esercizi proposti: ACC11Giu19.pdf. E le soluzioni: SolACC11Giu19.pdf.

Appello straordinario: esito

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


Presentazione del corso 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?
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 teoria della calcolabità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.
Alcuni problemi , comunque, pur essendo teoricamente affrontabili con un calcolatore, non lo sono in pratica (nessuno ha abbastanza tempo per aspettare la risposta). La teoria della complessità 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).



Obiettivi corso

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
1.giustificare l'esistenza di problemi privi di soluzioni algoritmiche o intrattabili.
2.descrivere esempi concreti di problemi indecidibili, non dimostratamente intrattabili o intrattabili.
3. la definizione formale dei diversi modelli, deterministici e non, di macchina introdotti
4. le definizioni di complessità di tempo e spazio per macchine di Turing e quella di riducibilità polinomiale
5. il senso e l'importanza della questione "P=NP?"

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



Programma del corso

Automi e Linguaggi

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

Teoria della Calcolabità

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.

Teoria della Complessità

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 NP-completezza. Teorema di Cook- Levin e altri problemi NP-completi. il teorema di Savitch

Qui trovate il programma dettagliato dell' a.a. 2018/2019 ProgrammaACC1819.pdf.

Qui trovate il programma dettagliato dell' a.a. 17/18 ProgrammaACC17-18.pdf.

Qui quelli degli anni accademici precedenti 2014/2015, 2015/2016 e 2016/2017: ProgrammaCC1516.pdf, ProgrammaACC1617.pdf.


Informazioni generali.

Lezioni

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

Prerequisiti
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).



Materiale per il corso
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.

I libri

Il corso si baserà sul testo di
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] , Motwani R., Ullman J.D., Automi, linguaggi e calcolabilità, I edizione italiana,Addison-Wesley,2003

Chi volesse leggere l'articolo originale di Turing può scaricarlo qui: Turing.pdf.

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



Valutazione degli studenti

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.
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.


DIARIO DELLE LEZIONI 2019/2020

mercoledì 11/12/2019 3 ore; Ultima esercitazione in aula.

lunedì 9/12/2019 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. coNP.pdf.

mercoledì 4/12/2019 3 ore; Problemi NP- completi, teorema di Cook. Esempi di problemi NP-completi. NPcomplCook.pdf NPcompleti_.pdf

lunedì 2/12/2019 2 ore; Il concetto di verificatore e la definizione alternativa di NP basata sull'esistenza di un verificatore polinomiale. Esempi di problemi in NP. Verificatore.pdf.

mercoledì 27/11/2019 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: cobham_intrinsic.pdf, J.Edmonds.pdf.

lunedì 25/11/2019 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. ClassiCompl.pdf.

mercoledì 20/11/2019 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. Esaula20nov19.pdf

lunedì 18/11/2019 2 ore;Riduzioni: uno strumento per dimostrare decidibilità o indecidibilità dei problemi. Riduzioni.pdf, RideIndecidibilit.pdf.

mercoledì 13/11/2019 3 ore; Macchina di Turing universale, TMUniversale.pdf.Indecidibilità e Turing riconoscibilità del problema della fermata e dell'accettazione. IndFermataTM.pdf.

lunedì 11/11/2019 2 ore; Esistenza di problemi non Turing riconoscibili, NonDecEsiste.pdf.

mercoledì 6/11/2019 3 ore; TM: varianti a k nastri e non deterministiche. Equivalenza. TMKnastri.pdf. TMNonDet.pdf.

lunedì 4/11/2019 2 ore; TM: definizioni ed esempi. TMDef.pdf.

mercoledì 30/10/2019 3 ore; CFG: proprietà di chiusura e problemi di decisione. Equivalenza di CFL e la classe dei linguaggi accettati da PDA. AmbiguitCFG.pdf, CFGePDA.pdf. ChiusCFLDec.pdf.

lunedì 28/10/2019 2 ore; CFG: definizioni ed esempi. CFG.pdf.

mercoledì 23/10/2019 3 ore; . Esercizi: Es2.pdf, Es3.pdf, Es1.pdf: Es1.pdf, Es4.pdf. Altri esercizi risolti: UltimoGiaOPresente.pdf, oi1jijPARI.pdf, NFA2.pdf, EsNFA1.pdf, ultimoNonPresente.pdf, 0i1jpari.pdf.

lunedì 21/10/2019 2 ore; Ancora su PDA esempi,. non determinismo e determinismo. Esercizi

mercoledì 16/10/2019 3 ore; PDA: definizione, esempi e prime proprietà. PDA.pdf.

martedì 15/10/2019 2 ore; (grazie allo scambio con il prof. Bottoni) Espressioni regolari e loro equivalenza con i linguaggi accettati dai DFA. 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.

mercoledì 9/10/2019 3 ore; Esistenza di linguaggi non regolari e uno strumento per dimostrare la non regolarità dei linguaggi: il pumping lemma. Esercizi. PumpingLemma.pdf, SolEsPumping.pdf.

lunedì 7/10/2019 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à. PorblemiDecDFA.pdf.

mercoledì 2/10/2019 3 ore;Automi a stati finiti non deterministici e equivalenza con i DFA. Esercizi. NFA.pdf.

lunedì 30/9/2019 2 ore; DFA: chiusura rispetto a unione, intersezione e complemento. PrimeChiusure.pdf. Non determinismo: introduzione. Esercizio: si dimostri la chiusura della classe dei linguaggi regolari rispetto alla differenza tra linguaggi.

mercoledì 25/9/2019 3 ore; Linguaggi e problemi. DFA: definizione ed esempi. LinguaggiDFA.pdf.

lunedì 23/9/2019 2 ore; Introduzione al corso. IntrACC.pdf.


DIARIO DELLE LEZIONI 2018/2019


giovedì 20/12/2018 3 ore; Esercitazione in aula.

martedì 18/12/2018 3 ore; La classe coNP, problemi in NP e in CoNP. Esercizi

venerdì 14/12/2018 3 ore; Classi di complessità di spazio. Esempio di problema in PSPACE e di uno in NPSPACE. Teorema di Savitch. Esercizi sulle riduzioni.

martedì 11/12/2018 3 ore; La riduzione polinomiale: esempi di riduzioni tra problemi CNFSAT ≤p 3SAT, 3SAT≤p CLIQUE, 3SAT≤p INDEPENDETSET. La definizione di NP-completo. Il teorema di Cook-levin (solo enunciato). Esercizio: CLIQUE≤pINDEPENDENTSET. 3 giovedì 6/12/2018 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.

martedì 4/12/2018 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: cobham_intrinsic.pdf, J.Edmonds.pdf.

giovedì 29/11/2018 3 ore; Esercitazione in aula.

martedì 27/11/2018 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.

giovedì 22/11/2018 3 ore; Indecidibilità del problema della fermata e non Turing riconoscibilità per il complemento del problema dell'appartenenza.

martedì 20/11/2018 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: ModuloTM1.pdf; una TM che calcola la stringa binaria successiva a quella da in input: moduloTM2.pdf; una TM che genera tutte le stringhe binarie in ordine canonico: moduloTM3.pdf.

venerdì 16/11/2018 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.

giovedì 15/11/2018 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à.

venerdì 9/11/2018 3 ore; Esercitazione in aula.

mercoledì 7/11/2018 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 ->SS| S->0S1| S->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->AS | 0S1 | A ; A -> 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.

venerdì 2/11/2018 3 ore; lezione non tenuta

mercoledì 31/10/2018 3 ore;Forma normale di Chomsky, appunti_cnf.pdf, AppuntiAlgVuotoCFG.pdf

venerdì 26/10/2018 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.

mercoledì 24/10/2018 3 ore; Linguaggi content-free e le grammatiche che li generano, primi esempi e proprietà.

venerdì 19/10/2018 3 ore; dalle 11,30 alle 13 esercitazione in aula con valore di primo esonero, sugli argomenti trattati fino a mercoledì.

mercoledì 17/10/2018 3 ore; Espressioni regolari e loro equivalenza con NFA. Esercizi SolEsPumping.pdf.

venerdì 12/10/2018 3 ore; Esistenza di linguaggi non regolari e uno strumento per dimostrare la non regolarità dei linguaggi: il pumping lemma. Esercizi.

martedì 9/10/2018 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.

giovedì 4/10/2018

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.

mercoledì 3/10/2018

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.

venerdì 28/9/2018

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

mercoledì 26/9/2018

3 ore;Introduzione al corso.

DIARIO DELLE LEZIONI 2017/2018

venerdì 22/12/2017 2 ore; Le classi di spazio: PSPACE, L e NL. InPoltreNP.pdf
12,15 - 13 V prova in aula II gruppo Es22Dic17.pdf, Riduzione22Dic17.pdf.

mercoledì 20/12/2017 2 ore; La classe coNP, FACTOR, l'isomorfismo tra grafi e i problemi intermedi. coNP.pdf.
12,15 - 13 V prova in aula I gruppo. Es20Dic17.pdf, RidEs20Dic17.pdf.

venerdì 15/12/2017 3 ore; Ancora esempi di problemi NP completi e Teorema di Savitch. Savitch.pdf, NPcompleti2.pdf.

mercoledì 13/12/2017 3 ore; Teorema di Cook-Levin. NPcomplCook.pdf NPcompleti_.pdf

venerdì 8/12/2017 3 ore; vacanza accademica

mercoledì 6/12/2017 3 ore; Il verificatore: nuova definizione di NP, Verificatore.pdf.

venerdì 1/12/2017 2 ore; classi di complessità, ClassiCompl.pdf.
12,15 - 13 IV prova in aula II gruppo, EsACC4Dic.pdf.

mercoledì 29/11/2017 2 ore; Riduzioni: definizione ed esempi. Riduzioni.pdf, RideIndecidibilit.pdf.
12,15 - 13 IV prova in aula I gruppo, EsACC29Nov.pdf.

venerdì 24/11/2017 3 ore; Il problema dell'accettazione e della fermata per macchine di Turing: loro indecidibilità e loro Turing riconoscibilità. Macchina di Turing universale, IndFermataTM.pdf, TMUniversale.pdf. Qualche esercizio: NumerabilitTuringCalc.pdf. Due problemi decidibili per CFG: DecChiusCFL.pdf.

mercoledì 22/11/2017 3 ore; Macchine di Turing non deterministiche, TMNonDet.pdf. Esistenza di problemi non Turing riconoscibili, NonDecEsiste.pdf.

venerdì 17/11/2017 2 ore; Macchine di Turing a k nastri e loro equivalenza con le macchine di Turing a un solo nastro, TMKnastri.pdf.
12,15 - 13,00: III prova in aula per il secondo gruppo, EsACC17Nov.pdf.

mercoledì 15/11/2017 2 ore; Macchine di Turing: definizione ed esempi, TMDef.pdf.
12,15 - 13,00: III prova in aula per il primo gruppo, EsACC15Nov.pdf.

venerdì 10/11/2017 3 ore; La lezione non si terrà per un concomitante e irrinunciabile impegno del docente.

mercoledì 8/11/2017 2 ore; Ambiguità e CFG, AmbiguitCFG.pdf. PDA e CFG, CFGePDA.pdf.
12,15 - 13,00: II prova in aula per il primo gruppo, Es811.pdf.

venerdì 3/11/2017 2 ore; CFG: introduzione ed esempi, CFG.pdf.
12,15 - 13,00: II prova in aula per il secondo gruppo, Es311.pdf.

mercoledì 1/11/2017 3 ore; lezione non tenuta perché giorno festivo

venerdì 27/10/2017 3 ore; Esercizi di costruzione di NFA, PDA e problemi di decisione per i DFA. EserciziNFAePDA_.pdf.

mercoledì 25/10/2017 3 ore; Automi a pila: definizioni ed esempi, PDA.pdf. Esercizi sul pumping lemma.

venerdì 20/10/2017 3 ore; Espressioni regolari e loro equivalenza con i DFA (teorema di Kleene), EspressioniRegolari.pdf. Esercizi sul pumping lemma, EsPumping.pdf
13,15 - 13,45: I prova in aula per il secondo gruppo, i testi: Es2010.pdf.

mercoledì 18/10/2017 3 ore; Chiusura rispetto a concatenazione e stella di Kleene Linguaggi_e_operazioni.pdf, Pumping lemma per i regolari PumpingLemma.pdf. Soluzioni esercizi su DFA,NFA e proprietà di chiusura proposti nella lezione precedente.
13,15 - 13,45: I prova in aula per il primo gruppo, i testi: EsEsame18Ott17.pdf.

venerdì 13/10/2017 3 ore; NFA: gli automi finiti non deterministici. NFAdefDimEq.pdf, EserciziAutomi.pdf.

mercoledì 11/10/2017 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. PrimeChiusure.pdf

venerdì 6/10/2017 3 ore; Automi a stati finiti, Deterministic Finite Automata, prime definizioni ed esempi. DFA1Intr.pdf.

mercoledì 4/10/2017 3 ore; Introduzione al corso: breve descrizione contenuto del programma, problemi di decisione e linguaggi, problemi di decisione e problemi di ricerca. IntrACC17.pdf.


DIARIO DELLE LEZIONI 2016/2017

mercoledì 21/12/2016 4 ore; Esercitazione riassuntiva sulla seconda parte del programma. EsAula21dic2016.pdf.

giovedì 15/12/2016 2 ore; dalle 9 alle 11, nell'orario di Linguaggi e Compilatori: Teorema di Savicth. Savitch.pdf, qualche incursione dentro P e oltre NP, InPoltreNP.pdf.

mercoledì 14/12/2016 3 ore; Problemi NP completi. NPcompleti_.pdf

venerdì 9/12/2016 2 ore; lezione annullata e anticipata al 6 dicembre.

mercoledì 7/12/2016 3 ore; Teorema di Cook. NP-complCook.pdf, Esercizi di uso delle riduzioni in prove di indecidibilità e sulla Turing riconoscibilità. EserciziDecTuringRic.pdf

martedì 6/12/2016 3 ore; dalle ore 9 alle ore 10,45. ll verificatore. Nuova definizione di NP, Verificatore.pdf

venerdì 2/12/2016 2 ore; Classi di complessità, definizioni ed esempi, ClassiCompl.pdf.

mercoledì 30/11/2016 3 ore; Riduzioni: uno strumento per dimostrare decidibilità o indecidibilità dei problemi. Riduzioni.pdf, TMUniversale.pdf, RideIndecidibilit.pdf.

venerdì 25/11/2016 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.

mercoledì 23/11/2016 3 ore; Esistenza di problemi indecidibili. NonDecesiste.pdf. Il problema della fermata. IndFermataTM.pdf.

venerdì 18/11/2016 2 ore;Macchine di Turing non deterministiche e loro equivalenza con le deterministiche. TMNonDet.pdf

mercoledì 16/11/2016 3 ore; Macchine di Turing a k nastri e loro equivalenza con le macchine di Turing a un solo nastro. TMKnastri.pdf

venerdì 11/11/2016 2 ore;Macchine di Turing: prime definizioni ed esempi. TMDef.pdf.

mercoledì 9/11/2016 3 ore; Prova intermedia. PIACCNov16.pdf:.

venerdì 4/11/2016 2 ore;Esercizi riassuntivi programma svolto EsAula.pdf.

mercoledì 2/11/2016 2 ore; Proprietà di chiusura e problemi di decisione per i CFL. ChiusureCFL.pdf

venerdì 28/10/2016 2 ore; lezione annullata

lunedì 24/10/2016 3 ore; Equivalenza CFG e PDA, Ambiguità e forme normali per CFG. Problemi di decisione per CFG. CFGePDA.pdf, AmbiguitCFG.pdf, algCYK.pdf.

venerdì 21/10/2016 2 ore; Grammatiche context-free, prime proprietà. CFGIntr.pdf

mercoledì 19/10/2016 3 ore; Automi a pila, definizioni ed esempi. Prime proprietà. PDA.pdf.

venerdì 14/10/2016 2 ore; espressioni regolari ed equivalenza con i DFA. EspressioniRegolari.pdf.

mercoledì 12/10/2016 3 ore; Conclusione NFA e pumping lemma per i regolari ed esercizi in aula. EserciziNFAPumping.pdf Il file è stato corretto, c'era un errore nel DFA prodotto.

venerdì 7/10/2016 2 ore;Equivalenza tra DFA e NFA, NFA.pdf, Pumping Lemma per i regolari * PumpingLemma.pdf.

mercoledì 5/10/2016 3 ore;Linguaggi e operazioni su di essi. Automi a stata finiti non deterministici Linguaggi_e_operazioni.pdf, NFA.pdf.

venerdì 30/09/2016 2 ore;Introduzione alla teoria degli automi. DFA1Intr.pdf: il file è stato aggiornato.

mercoledì 26/09/2016 3 ore; Introduzione al corso. IntrACC16.pdf


DIARIO DELLE LEZIONI 2015/2016

venerdì 18/12/2015 2 ore; Esercitazione sui contenuti della seconda parte del corso, EsACCDic2015.pdf.

mercoledì16/12/2015 2 ore;teorema di Savitch. PSPACE e PSPACE-completezza, Savitch.pdf, PSPACE-completeness.pdf.

venerdì 11/12/2015 2 ore; Esempi di problemi NPcompleti. NPcompleti.pdf.

mercoledì 9/12/2015 2 ore; 12,30 - 13,45. Teorema di Cook Levin. Cook.pdf

mercoledì 9/12/2015 2 ore; 10,45 - 12,15. Verificatore polinomiale ed esempi di problemi in NP. DefCompl2.pdf

venerdì 4/12/2015 2 ore; lezione annullata per evento in dipartimento "incontro con le aziende"

mercoledì 2/12/2015 2 ore; Complessità: prime definizioni DefComp.pdf

venerdì 27/11/2015 2 ore; lezione annullata.

mercoledì 25/11/2015 2 ore; Riduzioni e loro utilizzo per costruire algoritmi o dimostrare l'indecidibilità. Riduzioni.pdf, Rid_Indecidibilita.pdf.

venerdì 20/11/2015 2 ore; Macchina universale, Esistenza problemi non Turing riconoscibili e proprietà di chiusura dei linguaggi Turing riconoscibili, FermataTM.pdf.

mercoledì 18/11/2015 2 ore; Esistenza di problemi indecidibli. EsistenzaNonDec.pdf, IndFermataTM.pdf

venerdì 13/11/2015 2 ore; TM a più nastri e non deterministiche TMPiuNastri.pdf, TM3NonDet.pdf

mercoledì 11/11/2015 2 ore; Macchine di Turing: definizione ed esempi, TMDef.pdf.

venerdì 6/11/2015 2 ore; Prova intermedia. Qui i testi: ProvaIntermediaACC2015.pdf

mercoledì 4/11/2015 2 ore; Esercizi sul programma svolto, EseAula.pdf.

venerdì 30/10/2015 2 ore; CFG e PDA. Ambiguità e proprietà di chiusura CFGePDA.pdf, AmbiguitaCFG.pdf, IlComplemento.pdf.

mercoledì 28/10/2015 2 ore; lezione non tenuta per malattia

venerdì 21/10/2015 2 ore; Grammatiche acontestuali, CFGIntr.pdf.

mercoledì 20/10/2015 2 ore; Automi a pila PDA.pdf

venerdì 16/10/2015 2 ore; lezione non tenuta per evento in Città universitaria.

mercoledì 14/10/2015 2 ore; Espressioni regolari ed equivalenza DFA, EspressioniRegolari.pdf.

venerdì 9/10/2015 2 ore; Il pumping lemma. Esercizi di costruzione NFA e problemi di decisione per DFA PumpingLemma.pdf

mercoledì 7/10/2015 2 ore; Automi nondeterministici, equivalenza con DFA e chiusura classe dei regolari rispetto a concatenazione e stella di Kleene, NFA.pdf.

venerdì 2/10/2015 2 ore; Le principali operazioni sui linguaggi e la chiusura della classe dei linguaggi accettati da unDFA rispetto a queste operazioni. Linguaggi_e_operazioni.pdf

mercoledì 30/9/2015 2 ore; Definizioni formali e prime proprietà DFA DFA1Intr.pdf. Ho aggiunto l'automa dell'esercizio e il teorema dimostrato a lezione

venerdì 25/9/2015 2 ore; conclusione descrizione degli argomenti che verranno trattati durante il corso. Prime definizioni: linguaggi e automi a stati finiti.

mercoledì 23/9/2015 2 ore; Introduzione al corso con breve descrizione degli argomenti che verranno trattati, IntCCII.pdf.


Calcolabilità e Complessità a.a. 2014-2015

Programma del corso

Diario delle lezioni


Programmi definitivi dell'insegnamento di Calcolabilità e Complessità

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

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


DIARIO DELLE LEZIONI 2014/2015

martedì 16/12/2014

2 ore; La classe dei giochi: PSPACE-completi. PSPACE.pdf

giovedì 11/12/2014

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

martedì 9/12/2014

2 ore; conclusione rassegna problemi NP-completi.

giovedì 4/12/2014

2 ore; NP-completezza, SAT e altri problemi NP-completi. Cook.pdf, NP-completi.pdf

martedì 2/12/2014

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

giovedì 27/11/2014

2 ore; Definizioni di complessità di tempo e di spazio e loro relazioni. Classi di complessità. DefComp.pdf.

martedì 25/11/2014

2 ore; riduzioni definizioni ed esempi, Riduzioni.pdf, RideIndecidibilita.pdf.

giovedì 20/11/2014

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

martedì 18/11/2014

2 ore; Esistenza di problemi indecidibili, EsistenzaNonDec.pdf.

giovedì 13/11/2014

2 ore; TM non deterministiche e loro equivalenza alle deterministiche, TMNonDet.pdf.

martedì 11/11/2014

2 ore; Lezione dedicata a domande sul programma svolto fino ad ora, Domande.pdf.

giovedì 6/11/2014

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

martedì 4/11/2014

2 ore; Prime varianti di TM: le TM a più nastri, TMKnastri.pdf.

giovedì 30/10/2014

2 ore; Macchine di Turing: prime definizioni e proprietà. TM1Def.pdf.

martedì 28/10/2014

2 ore;Lezione in aula seminari. Il problema dell'appartenenza per CFG e altri problemi di decisione per i linguaggi contex-free. CFGalgCYK.pdf

giovedì 23/10/2014

2 ore; Grammatiche contex-free ed equivalenza PDA, CFGIntr.pdf, CFGePDA.pdf

martedì 21/10/2014

2 ore; PDA.pdf

giovedì 16/10/2014

2 ore;Automi a stati finiti non deterministici e loro equivalenza con le espressioni regolari EspressioniRegolari.pdf

martedì 14/10/2014

2 ore; Il pumping lemma per i regolari. PumpingLemma.pdf

giovedì 9/10/2014

2 ore;Automi a stati finiti non deterministici e loro equivalenza con i DFA: NFA.pdf.

martedì 7/10/2014

2 ore;DFA: prime definizioni ed esempi. DFAIntr.pdf, ChiusureDFA.pdf

giovedì 2/10/2014

2 ore; problemi come linguaggi, prime definizioni sui linguaggi, CCLinguaggi.pdf.

martedì 30/9/2014

2 ore;Introduzione al corso. CCintr.pdf

Date e Scadenze

March 2024
          01 02
03 04 05 06 07 08 09
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            


Avvisi Importanti

Avviso JFLAP

Seguendo questo link: http://www.cs.duke.edu/csed/jflap/log/form.php è possibile scaricare l'applicazione che vi consente di costruire e verificare vari tipi di macchine a stati finiti: DFA, automi a pila, macchine di Turing.


LinksUtili

Qui un tutorial sul modello quantistico

Un ricordo e un omaggio a Cobham: nel blog di Jeffrey Shallit "Recurrent thoughts about mathematics, science, politics, music, religion, and ... "

Questa è la homepage di David S. Johnson che insieme a Mike Garey ha pubblicato il testo in cui c'è la prima collezione ragionata di problemi NP-completi. Computers and Intractability: A Guide to the Theory of NP-Completeness. Nella pagina di Johnson trovate un link a un file pdf con un catalogo aggiornato di problemi NP-completi.

Questa è la pagina del corso diPhilosophy and Theoretical Computer Science, tenuto al MIT da S. Aaronson, dove trovate il link a vari articoli interessanti.

In questa pagina trovate un'applicazione Java, JFLAP, che vi consente di costruire automi a stati finiti di vario tipo, grammatiche e macchine di Turing, eseguirli su particolari input e verificare alcune costruzioni.

Cliccando qui andrete alla pagina dove il The Clay Mathematics Institute di Cambridge, Massachusetts (CMI) presenta sette problemi da un milione di dollari, tra cui P vs NP.
Qui trovate l'elenco dei vincitori del Turing Award, il Nobel per l'Informatica.

Qui potete documentarvi sulla storia del calcolatore e trovare i vincitori del premio annuale conferito dal Computer History Museum.

I link seguenti vi porteranno alle pagine bibliografiche di matematici, logici o infomatici citati durante le lezioni
CHURCH
GODEL
KLEENE
POST
THUE
TURING
ROBINSON
GREIBACH
CHOMSKY
CHOMSKI
RABIN
KARP
MATIYASEVICH
HILBERT
RUSSEL
CANTOR
HOPPER
PEANO
FREGE

ACKERMANN
HERBRAND
CURRY


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






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback