Insegnamento MODELLI DI CALCOLO E ALGORITMI AVANZATI
| Nome del corso di laurea | Ingegneria informatica e robotica |
|---|---|
| Codice insegnamento | A003177 |
| Curriculum | Robotics |
| Docente responsabile | Walter Didimo |
| Docenti |
|
| Ore |
|
| CFU | 9 |
| Regolamento | Coorte 2022 |
| Erogato | Erogato nel 2022/23 |
| Erogato altro regolamento | |
| Attività | Caratterizzante |
| Ambito | Ingegneria informatica |
| Settore | ING-INF/05 |
| Anno | 1 |
| Periodo | Secondo Semestre |
| Tipo insegnamento | Opzionale (Optional) |
| Tipo attività | Attività formativa monodisciplinare |
| Lingua insegnamento | Italiano |
| Contenuti | Linguaggi e grammatiche. Modelli di calcolo. Teoria della complessità. Tecniche algoritmiche per problemi NP-hard. Fondamenti di complessità parametrica. Applicazioni. |
| Testi di riferimento | Libro di testo: Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, "Linguaggi, Modelli, Complessità", Ed. Franco Angeli. Dispense: a cura del docente. Ulteriori letture: Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer 2013, ISBN 978-1-4471-5558-4, pp. I-SSS, 3-707 |
| Obiettivi formativi | L'insegnamento di prefigge di impartire agli studenti le nozioni teoriche di base sui linguaggi e le grammatiche formali, sui relativi modelli di calcolo, sull'analisi di complessità di algoritmi e problemi e sulla progettazione di tecniche algoritmiche avanzate per problemi computazionalmente difficili, incluse nozioni su algoritmi parametrizzati. In particolare, al termine del corso lo studente avrà acquisito: (a) conoscenza dei fondamenti teorici sui linguaggi formali di programmazione e dei relativi formalismi per la loro descrizione; (b) conoscenza dei vari modelli di calcolo per il riconoscimento delle diverse tipologie di linguaggi formali; (c) comprensione dei limiti degli attuali modelli di calcolo e dell'espressività delle relative tecniche algoritmiche; (d) capacità di classificare problemi di natura teorica e applicativa sulla base della loro difficoltà ad essere risolti con tecniche algoritmiche; (e) capacità di concepire tecniche algoritmiche euristiche o esatte per la risoluzione di problemi computazionalmente difficili. |
| Prerequisiti | [Conoscenze e competenze logico-matematiche]. Lo studente deve possedere buone capacità logico-matematiche, tipicamente acquisite nei corsi di analisi matematica e di geometria/algebra. Conoscenze in ambito di matematica discreta possono altresì essere di aiuto nella comprensione di alcuni argomenti. E' richiesta la conoscenza di tecniche dimostrative di base nel campo della matematica, ed in particolare la tecnica di dimostrazione per induzione e la tecnica di dimostrazione per assurdo. [Conoscenze e competenze informatiche]. Sono richieste conoscenze di base relativamente alla progettazione e all'analisi di algoritmi, nonché conoscenze di programmazione imperativa e ad oggetti tramite il linguaggio Java, impartite negli insegnamenti di Fondamenti di Informatica. |
| Metodi didattici | Il corso si articola in due principali blocchi di lezioni. (i) Nel primo blocco, che copre circa l'85% delle ore di lezione complessive, vengono svolte lezioni frontali in aula. Ogni lezione consiste, per circa il 50% della sua durata, nell'illustrazione da parte del docente di nuovi concetti teorici, attraverso la proiezione di appositi lucidi. Il restante 50% della durata della lezione è dedicato allo svolgimento guidato di esercizi sulle nozioni teoriche precedentemente illustrate, con l'obiettivo di consolidare la comprensione da parte dello studente e di aumentare le sue capacità di applicare tali nozioni alla risoluzione di problemi. (ii) Nel secondo blocco, che copre circa il 15% delle ore di lezione complessive, vengono discusse applicazioni delle nozioni illustrate nel primo blocco. La maggior parte di tali lezioni si svolgono nel laboratorio di ingegneria del software, prevedendo anche la progettazione e l'implementazione di algoritmi sotto la guida del docente. |
| Altre informazioni | |
| Modalità di verifica dell'apprendimento | [Obiettivi della valutazione.] I metodi di valutazione di questo insegnamento cercano di quantificare le conoscenze teoriche acquisite dallo studente, nonché le sue capacità di applicare tali conoscenze per la risoluzione di problemi teorici e applicativi. I tipi di prove previste per la valutazione sono descritti qui di seguito. Per ciascuna di esse vengono forniti dettagli sulla durata, struttura, punteggio e obiettivi specifici. (i) Esame scritto di natura teorica e applicativa Durata: 120 minuti Struttura: esercizi di natura teorica e applicativa Punteggio: 30/30 (ogni esercizio ha lo stesso peso). Obiettivo: verificare le conoscenze acquisite in merito alle varie nozioni teoriche dell'insegnamento e la capacità di applicare tali nozioni alla risoluzione di problemi relativi ai linguaggi formali, alla progettazione di modelli di calcolo, all'analisi di complessità di algoritmi e problemi, e alla progettazione di algoritmi avanzati. (ii) La correzione della prova scritta viene presentata allo studente nell'ambito di un breve colloquio orale, in cui lo studente può eventualmente confutare il giudizio del docente. Per informazioni sui servizi di supporto agli studenti con disabilità e/o DSA visita la pagina http://www.unipg.it/disabilita-e-dsa |
| Programma esteso | [Parte I - Linguaggi e grammatiche]. Alfabeti e linguaggi. Espressioni regolari. Grammatiche di Chomsky. [Parte II - Modelli di calcolo]. Linguaggi regolari: automi a stati finiti deterministici e non, proprietà dei linguaggi regolari (pumping lemma, proprietà di chiusura, predicati decidibili), il teorema di Myhill-Nerode. Linguaggi context-free: automi a pila deterministici e non, proprietà dei linguaggi context-free (pumping lemma, proprietà di chiusura, predicati decidicibili), grammtiche e linguaggi ambigui. Macchine di Turing deterministiche, non deterministiche e multinastro. Composizione di macchine di Turing. La macchina di Turing Universale. Problemi indecidibili: il teorema della fermata. Macchine a registri a costi logaritmici e a costi uniformi. Correlazione tra macchine di Turing e macchine a registri. [Parte III - Teoria della complessità]. Classi di problemi. Complessità temporale e spaziale dei problemi. Classi notevoli di complessità. Karp-riducibilità. Problemi NP-hard e NP-completi. Esempi di problemi NP-hard e prove di riduzione: CIRCUIT-SAT, SAT, 3CNF-SAT, CLIQUE, VERTEX-COVER. [Parte IV - Tecniche algoritmiche per problemi NP-Hard]. Ulteriori problemi NP-Hard e NP-completi (TSP geometrico, Bisaccia a valori interi). Algoritmi euristici. Algoritmi di approssimazione. Algoritmi di backtracking per problemi di ricerca. Algoritmi di branch and bound per problemi di ottimizzazione. Complessità parametrica, parametri strutturali, tecniche di programmazione dinamica, kernelizzazione, gerarchia W. [Parte V - Applicazioni]. Uso di espressioni regolari per ricerca di pattern testuali: la notazione POSIX. Automi a stati finiti per ricerche di parole chiave nei testi: implementazione di un programma di simulazione di automi a stati finiti non deterministici. Cenni alle applicazioni delle grammatiche context-free: cenni all'architettura e alle tipologie di parser; generatori automatici di parser; uso di YAAC per la generazione automatica di parser a partire da una grammatica. |