Codice insegnamento

4S008896

Crediti

12

Coordinatore

Romeo Rizzi

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI

Corsi Singoli

Autorizzato

Moodle Seminari 0

L'insegnamento è organizzato come segue:

Obiettivi di apprendimento

Uno degli obiettivi più elevati del corso stà nel riuscire a trasmettere alcuni aspetti del profondo ed importante interscambio dialettico tra la ricerca di algoritmi e lo studio della complessità dei problemi. 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 gioca un profondo ruolo metodologico nell'analisi dei problemi. 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. Gli studenti acquisiranno competenze logico-matematiche, tecniche, esperienza e metodologie utili nell'analisi di problemi algoritmici, dal rilevarne la struttura ed analizzarne la complessità computazionale al progettare algoritmi efficienti, al pianificare e condurre l’implementazione degli stessi. Inoltre il corso si propone di fornire: le basi teoriche della complessità computazionale con particolare attenzione alla teoria della NP-completezza; nozioni di algoritmi di approssimazione ed approcci di base per l'analisi di algoritmi di approssimazione per problemi “difficili”; approcci parametrizzati alla risoluzione di problemi “difficili”. Gli studenti applicheranno le principali tecniche algoritmiche: ricorsione, divide et impera, programmazione dinamica, alcune strutture dati, invarianti e monovarianti. Acquisiranno così sensibilità riguardo a quali problemi possano essere risolti efficientemente e con quali tecniche, acquisendo strumenti anche dialettici per collocare la complessità di un problema algoritmico ed individuare approcci promettenti per lo stesso, guardando al problema per coglierne la struttura. Imparerà a produrre, discutere, valutare, e validare congetture, ed affrontare anche in autonomia il percorso completo dall'analisi del problema, al progetto di un algoritmo risolutore, alla codifica e sperimentazione dello stesso, anche in contesti di ricerca in ambito aziendale come presso istituti di ricerca. I fondamenti della teoria della complessità acquisiti, consentiranno allo studente di avvalersi di riduzioni quali tecniche standard della teoria della Complessità per analizzare la natura dei problemi computazionali e valutare quali possano essere approcci alternativi alla sua risoluzione (approssimazione, parametrizzazione) in assenza di soluzioni in assoluto efficienti. Al termine del corso lo studente sarà in grado di: i) classificare problemi computazionalmente intrattabili; ii) comprendere e verificare la correttezza di una prova formale; ii) leggere e comprendere un articolo scientifico in cui venga proposto un nuovo algoritmo con associata analisi della complessità.

Prerequisiti e nozioni di base

saper programmare in un qualche linguaggio di programmazione.

Programma

Lo Yin e lo Yang di come si affronta un problema sono gli Algoritmi (ossia i metodi generali per la soluzione di istanze del problema) da un lato e la contemplazione della sua Complessità (ricchezza del problema) dall'altro. Due cultori appassionati ti condurranno nell'esplorazione di queste due arti sinergiche con l'auspicio che in tè si fondano in una sola.
PROGRAMMA PARTE ALGORITMI (Romeo Rizzi):
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.
PROGRAMMA PARTE COMPLESSITA' (Ferdinando Cicalese):
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.
Complessità di spazio: modelli e differenze fondamentali tra misure di tempo e spazio.Completezza per le classi di complessità di spazio. La classe PSPACE 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. Esempi di approcci parametrizzati per la risoluzione di problemi difficili.

Bibliografia

Modalità didattiche

in presenza. Le lezioni saranno comunque registrate e ove agevole e su richiesta potremmo servire anche chi dovesse seguire da remoto.

Modalità di verifica dell'apprendimento

Concorrono al voto in pari misura una prova scritta che verte principalmente su argomenti di Complessità e una prova di laboratorio che verte principalmente su argomenti di Algoritmi.
Lo scritto si basa sul percorso avvenuto in classe. Per alcuni esempi di esercizi rimandiamo alla repo di riferimento per la prova scritta:
https://github.com/romeorizzi/prove_scritte_AlgoComp
In laboratorio di informatica gli studenti devono affrontare una prova di 5 ore dove vengono loro assegnati dei problemi.
Gli studenti devono analizzare e comprendere i problemi e la loro struttura, individuare delle soluzioni algoritmiche per gli stessi, ed implementare tali soluzioni in codice c/c++ oppure Pascal. Piu` efficiente questo si rivelera`, maggiori i punti raccolti.
Durante l'esame, gli studenti possono via via sottoporre quanto da loro prodotto ad un sito del tutto analogo a quello utilizzato durante le esercitazioni in laboratorio e/o da casa. In questo modo essi possono ottenere una valutazione immediata e contestuale che li possa guidare nel condurre la prova.
Le soluzioni vengono valutate in base ai subtask dell'esercizio che riescono a risolvere correttamente senza sforare le risorse di tempo e memoria predeterminate dall'esercizio.
Trovate dei problemi e materiali di riferimento per la prova di laboratorio ai seguenti repo e piattaforme dove potete cimentarvi con gli esercizi:
https://github.com/romeorizzi/esami-algo-public
https://rizzi.olinfo.it/algo-simula-prove
https://cms.di.unipi.it/algo/
I problemi che trovare li` proposti costituiscono la risorsa prima per prepararsi all'esame. Il sistema di sottoposizione che utilizzerai all'esame e` TALight.
Anche dopo aver conseguito un voto positivo, lo studente puo` partecipare a piu` appelli per vedere se riesce a migliorarlo: la politica e` di tenere il voto migliore sui vari appelli, ma sono previsti anche meccanismi con cui i voti vengono anche assommati.
Troverai il portafoglio dei tuoi voti al sito del corso:
http://profs.sci.univr.it/~rrizzi/classes/Algoritmi/index.html

Criteri di valutazione

Le varie parti dell'esame e della gestione del voto sono improntate alla massima trasparenza.

Criteri di composizione del voto finale

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. le tue generalita` (matricola VRxxxxxx);
2. voto che ti attendi ti venga verbalizzato;
3. voto per la parte di algoritmi specificando come composto (precisando gli appelli di riferimento);
4. ultimo appello di complessita' al quale hai consegnato, col voto conseguito.
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.

Lingua dell'esame

Italian. But, under request, we will prepare also an English text.