Codice insegnamento

4S008896

Docenti

Romeo Rizzi, Ferdinando Cicalese

Coordinatore

Romeo Rizzi

Crediti

12

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI

Periodo

II semestre dal 1 mar 2021 al 11 giu 2021.

Orario Lezioni Moodle Seminari 0

Obiettivi formativi

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à.

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.

Modalità d'esame

Concorrono al voto in pari misura una prova di laboratorio ed una prova scritta. Entrambe le prove vertono sia su argomenti di Algoritmi che di Complessità per giungere ad una sintesi più stretta di queste competenze complementari e sinergiche.

Come piattaforma tecnologica e come primi materiali di riferimento, la prova di laboratorio sarà in continuità con quanto in:

https://rizzi.olinfo.it/algo-simula-prove
https://github.com/romeorizzi/esami-algo-public

Lo scritto sarà composto a 4 mani dai due docenti di riferimento avendo in mente il 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

Partecipazione a progetti didattici ed altre parti speciali/opzionali del corso, potranno concorrere alla valutazione o sostituire in tutto la parte di laboratorio.