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
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. 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 e di SPACE-hardness. Buone congetture e buone caratterizzazioni. 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. 5. Approcci alla risoluzione di problemi “difficili”: algoritmi di approssimazione e classi di complessità rispetto all’approssimazione 6. Accortezze ed approcci nel 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
L'esame di compone di un test scritto ed una prova di laboratorio (in cui si richiede la progettazione e programmazione ed il testing di soluzioni a semplici problemi computazionali)
Le/gli studentesse/studenti con disabilità o disturbi specifici di apprendimento (DSA), che intendano richiedere l'adattamento della prova d'esame, devono seguire le indicazioni riportate QUI
Testi di riferimento
Vai alla bibliografia Visualizza la bibliografia con Leganto, strumento che il Sistema Bibliotecario mette a disposizione per recuperare i testi in programma d'esame in modo semplice e innovativo.
Codice insegnamento 4S008896