Algoritmi (2017/2018)

Codice insegnamento
4S02709
Crediti
12
Coordinatore
Romeo Rizzi
L'insegnamento è organizzato come segue:
Modulo Crediti Settore disciplinare Periodo Docenti
COMPLESSITÀ 6 ING-INF/05-SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI II sem. Ferdinando Cicalese
ALGORITMI 6 ING-INF/05-SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI II sem. Romeo Rizzi

Obiettivi formativi

------------------------
MM: COMPLESSITÀ
------------------------
Obiettivo del corso è fornire le nozioni di base della teoria della complessità computazionale con particolare attenzione alla teoria della NP-completezza, alle differenze e analogie nella classificazione dei problemi computazionali rispetto alle risorse di tempo e/o spazio necessarie alla loro risoluzione algoritmica ed infine introdurre approcci di base per l'approssimazione di problemi "difficili". Con riferimento agli obiettivi del percorso formativo del CdS il corso porta gli studenti ad approfondire e ampliare la formazione triennale in ambito di analisi e valutazione di algoritmi e sistemi di calcolo fornendo un bagaglio di strumenti avanzati per affrontare problemi non banali nel settore. Lo studente che ha seguito il corso con profitto avrà acquisito gli strumenti necessari per comprendere e affrontare la difficoltà nel risolvere alcuni problemi comuni da un punto di vista computazionale. Lo studente potrà analizzare in maniera indipendente un nuovo problema, comprendere le caratteristiche strutturali che lo rendono "difficile" o meno e valutare quali possano essere approcci alternativi alla sua risoluzione (approssimazione, parametrizzazione) in assenza di soluzioni probabilmente efficienti.
------------------------
MM: ALGORITMI
------------------------
Gli algoritmi costituiscono l'ossatura e la sostanza dell'informatica, ma ne sono anche i piu` antichi antesignani e sono trasversali e pervasivi a tutte le discipline. Il loro progetto prende avvio dallo studio della struttura dei problemi ed il piu` delle volte ne rappresenta il coronamento. Lo studio degli algoritmi richiede ed offre metodologie e tecniche di problem solving, competenze logiche e matematiche. Il corso si prefigge di stimolare gli studenti e di guidarli nel cammino all'acquisire competenze e metodologie di base spendibili nell'analisi dei problemi e nel progetto di algoritmi risolutori per gli stessi. Un primo obiettivo del corso e` chiarire agli studenti come per l'ottenimento di soluzioni (algoritmi) sia necessario passare per uno studio e comprensione del problema. Particolare enfasi viene data agli aspetti metodologici: studio di casi particolari, ruolo del congetturare, tecniche di dimostrazione, ascolto del problema e rilevamento della sua struttura. Un secondo obiettivo e` costruire un buon rapporto con l'approccio induttivo nello studio dei problemi, ed una buona dimestichezza con la ricorsione. Gli studenti vengono incoraggiati ad integrare l'approccio induttivo tra le loro tecniche con cui affrontare i problemi. Tra i dialetti della ricorsione, si approfondisce in particolare sulla programmazione dinamica. Allo studente si richiede di acquisire la programmazione dinamica come sua tecnica di problem solving. Particolare enfasi viene data all'efficienza degli algoritmi stessi, e la teoria della Complessita` Computazionale del modulo coniugato gioca un profondo ruolo metodologico nell'analisi dei problemi. Un'obiettivo del corso e` evidenziare ed illustrare questo ruolo. Infine ma non ultimo, il percorso di soluzione dei problemi deve essere completo. Allo studente si richiede di acquisire dimestichezza e capacita` di gestirsi nelle seguenti fasi: studio e comprensione del problema, individuazione di soluzioni algoritmiche, progetto di algoritmi efficienti, organizzazione della fase di implementazione, cura dell'implementazione, testing e debugging.

Programma

------------------------
MM: COMPLESSITÀ
------------------------
Concetto di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile. Relazioni tra problemi computazionali. Riduzioni polinomiale tra problemi computazionali. Le classi P, NP e co-NP. Concetto di completezza. Dimostrazioni di NP-completezza: il teorema di Cook; dimostrazioni mediante riduzioni polinomiali. Differenza tra Problemi di Ricerca e Problemi di Decisione. Self-reducibility dei problemi NP-completi ed esistenza di problemi non self-reducible. Richiami di teoria della computabilità: macchine di Turing e diagonalizzazione. Teoremi di Gerarchia rispetto al tempo. Esistenza di problemi intermedi nell'ipotesi P diverso da NP Complessità di spazio: modelli e differenze fondamentali tra misure di tempo e spazio. Le classi NL ed L e relazioni con la classe P. La centralità del problema Reachability. Completezza per le classi di complessità di spazio. Riduzioni log-space. NL-completezza di reachability. Non-determinismo e complessità di spazio. Il teorema di Savitch. Il teorema di Immerman-Szlepcsenyi. Le classe PSPACE e NPSPACE ed esempi e riduzioni per dimostrare PSPACE-completezza. Introduzione all'approssimazione. Problemi di Ottimizzazione. Esempi di algoritmi di approssimazione. Classificazione dei problemi rispetto alla possibilità di fornire approssimazioni più o meno buone. Classi di problemi: APX, PTAS, FPTAS. Nozioni di inapprossimabilita: la tecnica del gap per provare inapprossimabilità, e cenni di riduzioni che preservano l'approssimabilità. Esempi di uso della randomizzazione per la risoluzione di problemi computazionale difficili. Prerequisiti raccomandati ------------------------- Per seguire con profitto l'insegnamento è raccomandato che lo studente abbia già acquisito competenze in: 1. Comuni strutture dati astratte come lista, stack, code, alberi, heap. 2. Rappresentazione di grafi e principali algoritmi sui grafi: 2.1 Visita di grafi: BFS, DFS. 2.2 Ordinamento topologico. Componenti connesse. 2.3 Alberi di copertura di costo minimo. Algoritmi di Kruskal e Prim. 2.4 Cammini minimi da singola sorgente: Algoritmi di Dijkstra e Bellman-Ford. 2.5 Cammini minimi per tutte le coppie: Algoritmi di Floyd-Warshall e Johnson. 2.6 Flusso massimo. Algoritmo di Ford-Fulkerson. Un testo consigliato per rivedere tali concetti è "Introduction to Algorithms" di T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein (3 ed.).
------------------------
MM: ALGORITMI
------------------------
1. Workflow del problem solving: analisi e comprensione del problema e della sua struttura, concepimento di soluzioni algoritmiche, progetto di algoritmi efficienti, pianificare l'implementazione, condurre l'implementazione, testing e debugging. 2. Metodologia nell'analisi del problema: Lo studio di casi particolari. Particolarizzazione e generalizzazione. Costruire un dialogo col problema. Congetture. Ipotesi di semplicita`. Risolvere un problema riducendolo ad un altro. Riduzioni tra problemi per raccoglierli in classi. Ridurre i problemi a forme piu` fondamentali. Il ruolo della teoria della complessita` nel classificare i problemi in classi. Il ruolo della teoria della complessita` nell'analizzare i problemi. Controesempi e dimostrazioni di NP-hardness. Buone congetture e buone caratterizzazioni. La fede puo` rendere vere le congetture. Decomporre i problemi ed approccio induttivo. 3. Tecniche generali per il progetto di algoritmi. Ricorsione. Divide et impera. Ricorsione con memoizzazione. Programmazione dinamica (DP). Greedy. DP su sequenze. DP su DAGs. Approfondimento: buona caratterizzazione dei DAGs e scheduling; comporre ordinamenti parziali in nuovi ordinamenti parziali. DP su alberi. Approfondimento: adottare i figli uno ad uno; vantaggi della visione arco-centrica rispetto alla nodo-centrica. L'occhio asintotico sulle prestazioni guida nel progetto degli algoritmi: l'esempio della ricerca binaria; miglioramenti trascurabili da non inseguire; analisi ammortizzata. Alcune strutture dati: heaps binari; somme prefisse; Fenwick trees; range trees. 4. Algoritmi su grafi e digrafi. Grafi bipartiti: algoritmi di riconoscimento e buone caratterizzazioni. Grafi Euleriani: algoritmi di riconoscimento e buone caratterizzazioni. Cammini minimi. Minimo spanning tree. Flusso massimo e minimo taglio. Matching bipartito e node covers. Bipartite matchings. Il kernel di un DAG. Progressively finite games. Somma di giochi. 5. Accortezze ed approcci nell'condurre l'implementazione, la codifica, il testing ed il debugging. Pianificare l'implementazione. Prefigurarsi le decisioni importanti ed individuare gli aspetti ancora non chiari. Codifica passo passo. Verifiche passo passo, incrociate, e uso di asserts. Tecniche di testing e di debugging. Algoritmi auto-certificanti.

Modalità d'esame

Quando lo studente ha, nel proprio portafoglio voti, sia un voto positivo (almeno 18) per il modulo di Complessita` sia un voto positivo (almeno 18) per il modulo di Algoritmi, egli puo` richiedere al docente titolare del corso di procedere con la registrazione del voto per l'intero insegnamento, ottenuto come media dei voti per i due moduli.
La media e` arrotondata per eccesso ed un 30 e lode vale 33. Per generare un 30 e lode come voto finale serve almeno una lode e nessuna delle due valutazioni sotto il 30.
Quando ritieni giunto il momento di registrare il tuo voto, mandi una mail a romeo.rizzi@univr.it specificando:
1. voto per la parte di algoritmi e appello a cui lo hai conseguito (regola del max);
2. ultimo appello di complessita' al quale hai consegnato e voto conseguito;
3. voto che ti attendi ti venga verbalizzato e le tue generalita` (matricola VRxxxxxx).

Le modalita` con cui richiedere la registrazione e l'intero workflow sono riportati alla pagina:
http://profs.sci.univr.it/~rrizzi/classes/Algoritmi/index.html

Alla stessa pagina trovi inoltre il portafoglio dei tuoi voti, nonche` le informazioni su come venga prodotto e gestito il voto per il modulo di Algoritmi.
Per tali informazioni rimandiamo inoltre alle schede Dashboard della Didattica dei singoli moduli.

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2017/2018 non sono ancora disponibili