Dettagli sull'Insegnamento per l'A.A. 2019/2020

Prerequisiti

Indispensabili: avere sviluppato e implementato algoritmi di base in un qualsiasi linguaggio di programmazione. Conoscere le strutture dati iniziali quali code e pile e sapere usare forme elementari di ricorsione e conoscere bene le visite in ampiezza e in profondità di grafi e alberi. Propedeuticità: algoritmi e strutture dati con laboratorio.

Obiettivi

Il corso tratta nella prima parte dei limiti intrinsechi di quel che si può calcolare con un computer e nella seconda parte introduce alla teoria della Complessità. Alla fine delle lezioni, e il superamento dell’esame, lo studente dovrebbe essere in grado 1) di conoscere i fondamenti della teoria della Calcolabilità e della Complessità e comprendere i limiti intrinsechi a quel che qualsiasi modello di calcolo è in grado di fare in termini di accettazione di linguaggi ma anche in termini di funzioni calcolabili e quindi comprendere la tesi di Church-Turing. 2) Di conoscere le principali risorse a disposizione di chi calcola ovvero tempo e spazio e 3) di conoscere e comprendere le prime principali classi di linguaggi sia in teoria della Calcolabilità che in teoria della Complessità anche nel caso randomizzato. 4) Di sapere distinguere problemi potenzialmente non risolvibili dai calcolatori sia in teoria della Calcolabilità (indecidibilità, non calcolabili ovvero non R.E.) che in teoria della Complessità (non appartenenti alla classe P) al fine di trovare alternative soddisfacenti in pratica; quindi 5) di sapere dell’esistenza di metodologie, non trattate in questo corso ma alcune presenti come argomenti in altre materie, quali model Checking, analisi statica, analisi e testing, teoria dell’ottimizzazione combinatorica, algoritmi approssimati etc. 6) Di riuscire a modellizzare problemi e proporne soluzioni algoritmiche efficienti. 7) Di sapere distinguere dimostrazioni lacunose da quelle complete.Essere in grado di seguire dimostrazioni con catene di deduzioni logiche complesse e sapere integrare e completare prove lacunose. 8) DI riuscire a descrivere gli argomenti del corso con sufficiente rigore matematico, 9) di riuscire a descrivere algoritmi in modo completo anche se non totalmente formale. 10) Di riuscire a formalizzare e a comunicare problemi, idee e soluzioni algoritmiche. 11) Di avere le competenze necessarie per intraprendere studi successivi con un alto grado di autonomia. 12) Di sapere apprendere con facilità argomenti, connessi al corso, di cui si ha solo una parziale conoscenza.

Sillabo

• Contenuti;All’inizio del corso viene dato il programma dettagliato, riferito al libro di testo principale. Detto programma dettagliato viene anche spedito a una mailing list creata ogni anno e a chiunque ne abbia diritto e ne faccia richiesta, come ad esempio a studenti non frequentanti. Sinteticamente il programma è diviso in due parti, come dal nome dell’insegnamento, ovvero Teoria della calcolabilità e teoria della complessità, che sono interconnesse e difatti alcuni risultati della prima parte trovano ovvia continuazione nella seconda parte. Vista una base comune, la seconda parte viene iniziata leggermente dopo la metà temporale del corso. Nella prima parte si discute della corrispondenza tra linguaggi e problemi e viene discussa in profondità la relazione tra accettare un linguaggio (di n-upe di stringhe) e calcolare funzioni. Si introducono le macchine di Turing e si svolgono esercizi semplici di calcolo, quali calcolare in binario il +1 o il +2. Si sviluppano tecniche di programmazione con macchine di Turing e si fanno variazioni del modello di calcolo dimostrandone l’equivalenza con numerose varianti. Si passa dal modello non-deterministico (e si motiva con legami alla crittografia) al modello multinastro (analogie al parallellismo) sino ad arrivare alle macchine a due contatori, sempre dimostrando teoremi di equivalenza tra modelli. Si sviluppa la Tesi di Church Turing a partire dalle precedenti dimostrazioni. Si parla di robustezza del concetto di algoritmo e di calcolo e si accenna alle tesi di Church-Turing forte e al modello quantistico. Si introducono le classi R.E., dei linguaggi Ricorsivi si definiscono le riduzioni e si sviluppano teoremi sia relativi alle operazioni booleane interne alle classi sia teoremi che legano le riduzioni alle precedenti classi. Si definiscono i linguaggi Lu e Ld e si provano loro proprietà classiche, e infine si completa la prima parte con i linguaggi Le, Lne e loro proprietà e il Teorema di Rice. Nella seconda parte, si parla di problemi trattabili e intrattabili per iniziare la teoria della Calcolabilità e si definiscono le classi P ed NP. Si usa sempre la crittografia per motivare la classe NP. Poi si introducono le riduzioni polinomiali, la classe dei linguaggi NP-completi e si sviluppano teoremi connessi riguardanti questi argomenti. Si prova la appartenenza a NP del problema SAT e si sviluppano riduzioni polinomiali tra i molti problemi NP completi trattati nel libro per fare acquisire familiarità agli studenti con la classe dei problemi NP-completi. Successivamente si passa alla classe dei linguaggi co-NP, PS, NPS e teoremi connessi quale il teorema di Savitch. Poi si passa alle classi di linguaggi legate alla randomizzazione ZPP, RP, Co-RP e relazioni tra loro e le classi precedentemente studiate. Si termina il corso con la descrizione di un test randomizzato di primalità.

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

Testi di riferimento

• Hopcroft, Motwani, Ullman, AUTOMI LINGUAGGI E CALCOLABILITA' , Pearson, Addison Wesley. PARTE DEI CAPITOLI 1, 8, 9, 10 e 11.    
• Arora, Barak, Computational Complexity: a modern approach , Cambridge University press. Testo di approfondimento    

Modalità d'esame

Viene fatto uno scritto che viene chiamato “interattivo”. Difatti dopo che lo studente ha risposto alle prime domande riguardanti concetti e definizioni e prove basilari e necessarie al superamento dell’esame, la correzione viene fatta insieme allo studente stesso e, di norma, vengono fatte domande in funzione delle risposte date, ovvero dalla precisione, correttezza, capacità espositiva dello studente, dalla capacità logica dimostrata. Questo avviene in più fasi analoghe sino a quando la commissione non raggiunge un giudizio ritenuto valido e affidabile. In generale uno studente deve conoscere le definizioni di base e le tecniche fondamentali per potere superare l’esame e successivamente il voto inoltre crescerà anche in proporzione agli argomenti in cui è stato capace di rispondere e anche, e ci ripetiamo, in funzione delle risposte date, ovvero dalla precisione, correttezza, capacità espositiva dello studente, dalla capacità logica dimostrata. In particolare per valutare la capacità di applicare conoscenza e comprensione e anche le capacità di apprendimento si valuteranno le capacità degli studenti di capire e integrare e completare insieme al docente che compie l’esame dimostrazioni e ragionamenti logici su 1) argomenti connessi a corso ma che non sono stati strettamente trattati come argomenti del corso o discussione sugli argomenti più avanzati in caso di studenti con una valutazione vicino al massimo oppure 2) argomenti in cui gli studenti abbiano manifestato incertezze o imprecisioni per vedere se riescono ad essere più certi o precisi. A volte si chiede anche una autovalutazione da parte dello studente a cui segue una discussione.

Note

• Nei periodi di insegnamento l’orario di ricevimento è il mercoledì dalle 15:00 alle 19:00 e il giovedì dalle 11:30 alle 13:30. Negli altri periodi il Professor Mignosi può essere contattato @ filippomignosiunivaqit

Aggiornamenti alla pagina del corso

• A.A. 2011/2012
• A.A. 2012/2013
• A.A. 2013/2014
• A.A. 2014/2015
• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020