Codice insegnamento

4S02709

Docente

Romeo Rizzi

Coordinatore

Romeo Rizzi

Crediti

6

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI

Periodo

II semestre dal 4 mar 2019 al 14 giu 2019.

Orario Lezioni Moodle Seminari 0

Per visualizzare la struttura dell’insegnamento a cui questo modulo appartiene, consultare:  organizzazione dell'insegnamento

Obiettivi formativi

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

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

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 CMS 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. L'efficienza degli algoritmi progettati determina pertanto il punteggio. Viene garantito che almeno uno dei problemi proposti ad ogni singolo appello sia preso tra i problemi proposti al sito delle esercitazioni. Spesso altri problemi sono presi dalle gare COCI o da problemi delle olimpiadi di informatica o di problem solving.
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. Al voto esame vanno inoltre ad aggiungersi i punti guadagnati tramite un eventuale progetto. Come progetto, quest'anno proponiamo ai ragazzi di aiutarci nel mettere a punto dei pacchetti problema per il CMS, o nel contribuire alla realizzazione di un CMS di nuova generazione. Ogni studente ha quindi un portafoglio voti. Quando lo studente decide di registrare, si ottiene un voto per il modulo di algoritmi sommando gli eventuali punti progetto al max voto a prova di esame. Del voto per il modulo algoritmi si fa quindi la media col voto per il modulo di complessita`, e questo viene registrato come voto per l'intero insegnamento.

Il sito per le esercitazioni:
https://cms.di.unipi.it/algo/

ed i problemi che puoi trovare li` proposti costituiscono la risorsa prima per prepararsi all'esame. Il sistema di sottoposizione che utilizzerai all'esame e` analogo.

Per maggiori informazioni sulle modalita` di esame, ma anche per prepararti allo stesso, rimandiamo al sito del corso:

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

Qui` troverai il portafoglio dei tuoi voti,
i testi e le correzioni di temi precedenti che ti converra` prendere a riferimento, e piu` dettagliate istruzioni su vari aspetti dell'organizzazione e procedure per l'esame e composizione e registrazione del voto.