Algoritmi (2019/2020)

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 semestre Ferdinando Cicalese
ALGORITMI 6 ING-INF/05-SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI II semestre Romeo Rizzi

Obiettivi formativi

Per mantenere maggiore modularita` e struttura, rimandiamo ai singoli moduli per l'elencazione ed enunciazione ordinata degli obiettivi isolati e fissati entro gli stessi. Tuttavia, uno degli obiettivi piu` elevati del corso, richiamato poi separatamente anche nelle descrizioni offerte per i singoli moduli, sta` nel riuscire a percepire e rendere vivi alcuni aspetti del profondo ed importante interscambio dialettico tra la ricerca di algoritmi e lo studio della complessita` dei problemi. La cornice e natura di tale rapporto privilegiato e connubio tra queste due discipline (di fatto le due facce Yin e Yang di un'unica arte) viene di seguito accennata sperando possa venire a utile riferimento nella lettura di queste schede come nell'orientare lo studente nell'affrontare col giusto entusiasmo e prospettiva queste avventurose discipline.

Gli algoritmi costituiscono l'ossatura e la sostanza dell'informatica, ma allo stesso tempo il loro studio esula dall’ambito ristretto della scienza dei calcolatori e risulta trasversale e pervasivo a tutte le discipline che sono portatrici di problemi.
Il progetto di un algoritmo prende avvio dallo studio della struttura del problema da risolvere ed il più 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 mira dunque a far acquisire agli studenti competenze e metodologie fondamentali nell'analisi dei problemi e nel progetto di algoritmi risolutori per gli stessi. Particolare enfasi viene data all'efficienza degli algoritmi stessi, e la teoria della Complessità Computazionale (del modulo Complessità) gioca un profondo ruolo metodologico nell'analisi dei problemi. Per problemi non banali, il processo di ideazione di algoritmi attinge alla teoria della complessità non solo per individuare su quali problemi, e sottoproblemi, possa avere senso concentrare gli sforzi, ma anche come controparte dialettica che oltre a distinguere il giorno dalla notte consenta di distinguere svariate sfumature di grigio e possa essere impiegata per interrogare il problema su come esso richieda di essere risolto. Un'obiettivo del corso è evidenziare ed illustrare questa simbiosi tra le competenze affrontate nei due moduli.

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 problemi, algoritmi, e sistemi di calcolo, fornendo un bagaglio di strumenti avanzati per affrontare problemi non banali nei diversi ambiti dell’informatica.

Programma

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

A causa dell'emergenza CoVid19 le modalità dell'esame sono cambiate rispetto a quanto quì più sotto riportato. Siccome in alcuni aspetti delle cose sono in continua evoluzione, ed è in tutto richiesta la collaborazione dello studente, rimandiamo l'eventuale studente smarrito al sito di servizio e riferimento che possiamo tenere costantemente aggiornato:

http://profs.sci.univr.it/~rrizzi/classes/Algoritmi/index.html

Altrettanto preziosi per rimanere in buon contatto sono i gruppi Telegram istituiti per il corso e per la sperimentazione delle installazioni, configurazioni, ed ambienti per l'esame.
Tutte queste risorse possono essere convenientemente raggiunte partendo dallo URL riportato quì sopra.


SEGUE ORA LA VERSIONE UFFICIALE INSERITA QUI' AD INIZIO ANNO ACCADEMICO:

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.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
J. Kleinberg, É. Tardos Algorithm Design (Edizione 1) Addison Wesley 2006 978-0321295354
Garey, M. R. and Johnson, D. S. Computers intractability: a guide to the theory of NP-completeness Freeman 1979 0-7167-1045-5
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7
Michael Sipser Introduction to the Theory of Computation PWS 1997 053494728X
Cristopher Moore, Stephan Mertens The Nature of Computation Oxford 2011
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani Algorithms (Edizione 1) McGraw-Hill Higher Education 2007 978-0-07-352340-8
Steven S Skiena, Miguel A. Revilla Programming Challenges: The Programming Contest Training Manual (Edizione 2013) Springer New York, 2013 2003 147578970X