Ateneo - UPO

Tecniche algoritmiche, nozione di grafo e algoritmi su grafi, cenni ai problemi computazionalmente difficili e alle tecniche di approssimazione.

- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, *Algoritmi e strutture dati*, McGraw-Hill (è utilizzabile sia la 2/ed, 2008, ISBN 978 88 386 64687, sia la più recente 3/ed).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, *Introduction to Algorithms*, third edition, McGraw-Hill, 2010 (disponibile anche in italiano).

L'insegnamento (6 CFU: circa 32 ore di didattica erogativa in aula, circa 16 ore di didattica interattiva tra laboratorio informatico ed esercitazioni, a cui si aggiunge un carico di studio autonomo proporzionato ai crediti secondo il Regolamento Didattico di Ateneo) si propone i seguenti obiettivi.

Conoscenza e comprensione: le studentesse e gli studenti acquisiranno familiarità con il concetto di grafo e con le sue rappresentazioni, con le tecniche di visita di un grafo, con la tecnica greedy e con la tecnica di programmazione dinamica, con alcuni problemi classici sui grafi risolti con tali tecniche, e con i concetti di base relativi alla trattabilità computazionale dei problemi (classi P ed NP) e alle tecniche di approssimazione e di ricerca locale per affrontare problemi difficili.

Capacità di applicare conoscenza e comprensione: le studentesse e gli studenti sapranno modellare un problema utilizzando un grafo, scegliendo la rappresentazione più adatta; risolvere problemi tramite l'implementazione di algoritmi classici di visita di grafi; risolvere problemi utilizzando tecniche greedy e di programmazione dinamica, anche tramite l'implementazione di algoritmi classici; riconoscere un problema computazionalmente difficile e impostarne una soluzione approssimata o basata su ricerca locale. Come aspetto collaterale, il corso sviluppa le competenze di programmazione, in particolare nel linguaggio Java.

Autonomia di giudizio: le studentesse e gli studenti sapranno analizzare la correttezza e il costo computazionale di algoritmi greedy e di programmazione dinamica; affrontare con spirito critico gli algoritmi proposti, distinguendone i diversi gradi di difficoltà e apprezzando la necessità di ricorrere a tecniche avanzate per i problemi per cui non sono noti algoritmi polinomiali; riconoscere gli ingredienti comuni alle strategie di progettazione di algoritmi greedy o di programmazione dinamica per i problemi studiati.

Abilità comunicative: le studentesse e gli studenti avranno acquisito e sapranno utilizzare la terminologia formale specifica delle aree citate, anche in vista della discussione orale delle soluzioni proposte.

Capacità di apprendere: la comprensione delle tecniche algoritmiche e dei meccanismi di ragionamento e di analisi ad esse relativi metterà le studentesse e gli studenti in condizione di comprendere e apprendere autonomamente algoritmi per problemi diversi da quelli visti a lezione, purché riconducibili alle tecniche algoritmiche presentate.

Prerequisiti formali: la studentessa o lo studente non può accedere alle prove d'esame se non ha già sostenuto e verbalizzato gli esami di Programmazione 1 e Programmazione 2.

Prerequisiti sostanziali: nozioni di programmazione insegnate nei corsi di Programmazione 1 e 2; nozioni base di algoritmica insegnate nella prima parte del corso di Algoritmi; principi e linguaggi di programmazione insegnati nei corsi dei semestri precedenti.

Il corso è insegnato in aula e in laboratorio.

Nelle lezioni in aula vengono esposte le nozioni fondamentali, corredate di esempi. Le dimostrazioni vengono presentate come strumento di approfondimento delle tecniche, facendo leva sull'analogia tra gli algoritmi che utilizzano una stessa tecnica. Viene discussa l'utilità ai fini pratici dei diversi algoritmi per risolvere specifiche tipologie di problemi.

In laboratorio la studentessa o lo studente viene guidato/a nell'implementazione degli algoritmi visti a lezione, realizzando per ciascun algoritmo diverse varianti, in modo da apprezzare le informazioni che si possono trarre dall'utilizzo di ciascun algoritmo.

Sulla piattaforma Moodle del corso sono disponibili quiz di esercizio e autovalutazione (comprendenti anche esercizi di prova analoghi a quelli della prova scritta d'esame), che forniscono alle studentesse e agli studenti un modo di misurarsi con gli argomenti presentati, così da individuare per tempo eventuali lacune o dubbi e rivolgersi al docente per chiarimenti.

Il confronto diretto con il/la docente durante le lezioni, il laboratorio e il ricevimento, insieme alla discussione orale in sede d'esame, contribuisce inoltre allo sviluppo delle abilità comunicative comprese tra i risultati di apprendimento attesi.

L'attività in laboratorio richiede una partecipazione attiva e individuale delle studentesse e degli studenti, che in tal modo sviluppano abilità pratiche (la capacità di realizzare un programma). Inoltre, il coinvolgimento attivo li induce a porsi dei quesiti (e spesso, di conseguenza, a porne al docente); in tal modo si realizza una regolare verifica del modo in cui gli argomenti vengono recepiti.

Le studentesse e gli studenti con disabilità o con Disturbi Specifici dell'Apprendimento (DSA) o con Bisogni Educativi Speciali (BES) possono richiedere servizi e strumenti specifici a loro dedicati rivolgendosi allo Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse e agli Studenti e consultando la pagina dedicata del sito di Ateneo: https://uniupo.it/it/servizi/servizi-studenti-disabili-e-dsa

Le studentesse e gli studenti con disabilità, DSA, BES, una volta preso contatto con lo Staff di Ateneo, possono contattare la/il docente titolare dell'insegnamento in relazione alla declinazione delle modalità di esame, in merito agli aspetti didattici.

L'esame si svolge in un'unica giornata per appello: nella prima parte della mattinata si sostiene la prova scritta al calcolatore, sulla piattaforma Moodle, che ne effettua la correzione automatica; chi raggiunge la sufficienza nello scritto sostiene, nella stessa giornata, la prova orale.

La prova scritta ha lo scopo di verificare che la studentessa o lo studente abbia capito gli algoritmi classici e il loro utilizzo, e sia in grado di applicarli alla risoluzione di problemi. È composta da:
- 3 esercizi pratici (svolgimento o modifica di un algoritmo visto a lezione, oppure scrittura di codice), per un totale di 26 punti ripartiti in maniera pressoché equa tra i tre esercizi;
- 3 domande teoriche a risposta chiusa (a scelta multipla, con 3 opzioni di risposta ciascuna), per un totale di 6 punti: 2 punti per risposta corretta, -1 punto per risposta errata, 0 punti per risposta non data (penalità calibrata in modo che il valore atteso di una risposta data a caso sia nullo).

Il punteggio massimo della prova scritta è 32/30 (30 e lode); la prova si ritiene superata con un punteggio pari o superiore a 18/30, soglia che dà accesso alla prova orale nella stessa giornata. La prova scritta dura circa un'ora e mezza.

La prova orale verifica le competenze teoriche: in particolare la familiarità con il concetto di grafo nelle sue varianti, la capacità di analisi di algoritmi di visita di grafi, di algoritmi greedy e di programmazione dinamica, e la sensibilità verso l'affronto di problemi computazionalmente difficili (classi P/NP, approssimazione, ricerca locale). Sono poste 3 domande, relative all'intero programma del corso, che comprendono dimostrazioni e spiegazione/discussione di argomenti trattati a lezione; dura circa 20 minuti per studentessa/studente. Anche la prova orale è valutata in trentesimi, con punteggio massimo 32/30.

Il voto finale è determinato per circa il 50% dal voto della prova scritta e per circa il 50% dal voto della prova orale, fatta salva la possibilità per il/la docente di applicare correttivi motivati in casi specifici. Al voto della prova orale si somma inoltre un modificatore legato allo svolgimento degli esercizi di laboratorio (obbligatori per le studentesse e gli studenti frequentanti), che può variare da -2 a +2 punti a seconda della qualità del lavoro svolto.

Il materiale più adatto alla preparazione della prova scritta è costituito dagli esercizi di pratica disponibili sulla piattaforma Moodle del corso; il materiale più adatto alla preparazione della prova orale è costituito dai testi di riferimento e dal materiale teorico disponibile sulla stessa piattaforma.

**Grafi**
- definizioni e terminologia: grafi non orientati, grafi orientati, archi pesati, cammini, cicli, componenti connesse e fortemente connesse: significato e utilizzo delle diverse varianti per modellare diverse situazioni;
- rappresentazioni di grafi (liste di archi, liste di adiacenza, liste di incidenza, matrici di adiacenza e di incidenza) e loro impatto dal punto di vista dell'implementazione;
- visita di grafi in ampiezza e in profondità: caratteristiche comuni e differenze delle varie visite proposte, e loro applicazioni per il calcolo delle componenti connesse, delle componenti fortemente connesse, dell'ordinamento topologico e del test di aciclicità.

**Tecnica golosa (greedy)**
- introduzione alla tecnica tramite l'esempio del problema dello zaino frazionario; tecniche di dimostrazione di correttezza (proprietà della sottostruttura ottima e della scelta greedy) e loro funzione nella progettazione di algoritmi greedy; l'algoritmo di Huffman per la codifica ottima;
- cammini minimi su grafo pesato da un nodo sorgente: algoritmo di Dijkstra e applicazioni;
- minimo albero ricoprente: il lemma del taglio, algoritmi di Prim e Kruskal e loro utilizzo per risolvere problemi pratici;
- la struttura dati Union-Find (quick find, quick union, euristiche di bilanciamento e di compressione del cammino, analisi ammortizzata) e il suo utilizzo nell'algoritmo di Kruskal;
- limiti della tecnica golosa (problema del resto).

**Tecnica di programmazione dinamica**
- introduzione alla tecnica e proprietà della sottostruttura ottima; confronto con la tecnica golosa e con il divide et impera; aspetti e scelte di implementazione (algoritmi ricorsivi e iterativi, memoization);
- utilizzo dei teoremi della sottostruttura ottima per l'analisi di problemi e la progettazione di algoritmi di programmazione dinamica; analisi di problemi classici (massimo sottoinsieme indipendente, zaino 0-1, sottosequenza comune di lunghezza massima);
- cammini minimi da un nodo sorgente: algoritmo di Bellman-Ford (utilizzo negli algoritmi di routing);
- cammini minimi da tutti i nodi: algoritmo di Floyd-Warshall.

**Problemi intrattabili e tecniche di approssimazione**
- classi di complessità P ed NP, NP-completezza; algoritmi di complessità pseudopolinomiale;
- tecniche per affrontare problemi computazionalmente difficili: algoritmi di approssimazione (con il problema della copertura minima di vertici come esempio) e ricerca locale (con il problema del commesso viaggiatore, TSP, come esempio).

**Conoscenza e comprensione**
- Enunciare la definizione di grafo e descriverne le diverse rappresentazioni, analizzandone vantaggi e svantaggi in relazione alle applicazioni.
- Descrivere il concetto di visita di un grafo (in ampiezza e in profondità) e identificarne le applicazioni (componenti connesse, componenti fortemente connesse, ordinamento topologico, test di aciclicità).
- Descrivere la tecnica greedy e la tecnica di programmazione dinamica, identificando esempi di algoritmi che le utilizzano (Dijkstra, Prim, Kruskal, Huffman; Bellman-Ford, Floyd-Warshall, zaino 0-1, LCS).
- Descrivere le classi di complessità P ed NP e il concetto di NP-completezza, e illustrare l'idea alla base delle tecniche di approssimazione e di ricerca locale.

**Capacità di applicare conoscenza e comprensione**
- Modellare un problema dato tramite un problema classico su grafo, scegliendo il tipo di grafo e la rappresentazione più appropriati.
- Applicare gli algoritmi classici presentati a lezione a semplici istanze, anche modificandoli per risolvere varianti dei problemi affrontati.
- Implementare in Java gli algoritmi classici sui grafi presentati a lezione.

**Autonomia di giudizio**
- Spiegare il ragionamento che porta alla progettazione e che dimostra la correttezza degli algoritmi classici presentati, e analizzarne la complessità computazionale.
- Riconoscere se un problema dato è riconducibile a un problema noto e scegliere la tecnica algoritmica più appropriata per affrontarlo.

**Abilità comunicative**
- Esporre in modo chiaro e con terminologia formale corretta la definizione di un problema, l'algoritmo risolutivo proposto e la relativa dimostrazione di correttezza.

**Capacità di apprendere**
- Estendere autonomamente le tecniche algoritmiche presentate a problemi non trattati esplicitamente a lezione, riconoscendone la struttura comune.

Per la sufficienza è richiesto quanto sopra applicato a istanze semplici e ben strutturate; per una valutazione eccellente è richiesta piena autonomia nell'affrontare varianti dei problemi trattati e nell'esposizione critica e formale dei risultati.