Ateneo - UPO

Tecniche algoritmiche, nozione di grafo e algoritmi su grafi

P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi Strutture di dati e algoritmi, Seconda edizione, Pearson
oppure
C. Demetrescu, I.Finocchi, G.F. Italiano, Algoritmi e Strutture Dati, Seconda Edizione, McGraw-Hill
oppure
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Introduzione agli algoritmi e strutture dati,, terza edizione,
McGraw-Hill, 2010

L'insegnamento si propone di:
-introdurre grafi, insegnare come modellare problemi con grafi e fornire strumenti per gestirli;
-insegnare strategie algoritmiche greedy e di programmazione dinamica, e introdurre tecniche di approssimazione di soluzioni di algoritmi di ottimizzazione;
-affinare le capacità degli studenti nel problem solving e nella valutazione della complessità delle soluzioni.

Prerequisiti formali: 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; le nozioni base di algoritmica insegnate nel corso di Algoritmi 1. Principi e linguaggi di programmazione insegnati nei corsi di semestri precedenti.

Il corso è insegnato in aula e in laboratorio.
Nelle lezioni in aula vengono esposte le nozioni fondamentali, corredate di esempi, anche utilizzando un software di simulazione di algoritmi. Le dimostrazioni vengono presentate come strumento di analisi del problema per la progettazione degli algoritmi e 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. Sulla piattaforma DIR sono indicati i libri di testo suggeriti ed è a disposizione degli studenti del materiale integrativo aggiuntivo. Inoltre dopo ogni lezione, vengono indicati sul DIR gli argomenti trattati, con riferimento bibliografico, per chi non avesse seguito la lezione (ma anche per i presenti).
In laboratorio lo studente viene guidato nell'implementazione degli algoritmi visti a lezione, realizzando per ciascun algoritmo alcune varianti, come esercizio propedeutico all'uso degli algoritmi per la soluzione di problemi. Sul DIR sono a disposizione, per ogni argomento trattato nelle lezioni in laboratorio, delle slide come riferimento e guida sia per chi ha seguito la lezione che per gli assenti.
Sul corso DIR è attivo un forum di domande e risposte per offrire agli studenti un luogo di approfondimento e discussione degli argomenti insegnati; dopo ogni lezione la docente propone alcuni quesiti mirati a sollecitare gli studenti a ragionare su specifici argomenti. La docente controlla le risposte ma partecipa solo il minimo indispensabile per fornire una ragionevole guida, lasciando il dibattito agli studenti.
Sul DIR sono disponibili dei quiz di esercizio e autovalutazione (identici agli esercizi d'esame, presentano di volta in volta istanze diverse di domande di ciascun tipo) che forniscono allo studente un modo di misurarsi con gli argomenti presentati, in modo da scoprire eventuali proprie lacune o dubbi e poter quindi rivolgersi per tempo al docente per chiarimenti. Inoltre, allo stesso scopo, sono fornite le specifiche di quesiti di programmazione d'esame usati in passato.
Sul DIR sono disponibili anche link a registrazioni di lezioni, tenute dalla docente, divise per argomento, per agevolare gli studenti che non possono seguire le lezioni e come complemento per tutti.

L'attività in laboratorio richiede una partecipazione attiva e individuale degli studenti, che in tal modo sviluppano abilità pratiche (le 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.

Prova pratica seguita da esame orale
La prova in laboratorio è costituita da un semplice problema da risolvere con l'implementazione di uno degli algoritmi visti a lezione. E' seguita nella stessa giornata (compatibilmente con il numero di iscritti) da una prova orale tesa a verificare la comprensione dello studente della teoria alla base degli algoritmi insegnati nel corso, del funzionamento degli algoritmi classici presentati a lezione. Inoltre, nel corso della discussione si verifica che lo studente abbia acquisito la terminologia formale, che sia in grado di spiegare i ragionamenti alla base della progettazione e della dimostrazione di correttezza degli algoritmi e che abbia acquisito capacità di analisi. Il numero di domande può variare a seconda del modo in cui lo studente risponde (formalità, chiarezza, completezza, precisione,...) e della qualità del programma implementato.
La valutazione complessiva tiene conto della qualità del lavoro di programmazione e della discussione orale.

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: matrici e liste di adiacenza 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
Tecnica golosa (greedy):
-introduzione e algoritmi di esempio;
-cammini minimi su grafo pesato da un nodo sorgente: algoritmo di Dijkstra e applicazioni
-minimo albero ricoprente: algoritmi di Prim e Kruskal e loro utilizzo per risolvere problemi pratici
-tecniche di dimostrazione di correttezza e loro funzione in relazione alla progettazione di algoritmi greedy
-limiti della tecnica golosa
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 impementazione: 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, sottosequenza comune di lunghezza massima);
-cammini minimi da un nodo sorgente: algoritmo di Bellman-Ford
-cammini minimi da tutti i nodi: algoritmo di Floyd-Warshall
Cenni sui problemi intrattabili:
-classi P, NP ed NP completezza
-algoritmi di complessità pseudopolinomiale
-introduzione alle tecniche per affrontare i problemi difficili.

Conoscenza e capacità di comprensione: familiarità con il concetto di grafo, visita di grafo, tecnica greedy e di programmazione dinamica, e con alcuni problemi classici sui grafi.

Capacità di applicare conoscenza e comprensione:
- modellare problemi utilizzando grafi
- risolvere problemi tramite l'implementazione di algoritmi classici di visita di grafi
- risolvere problemi utilizzando tecniche greedy e di programmazione dinamica, anche implementando algoritmi classici
Come aspetto collaterale il corso sviluppa le competenze di programmazione (in particolare nel linguaggio Java).

Autonomia di giudizio:
- analizzare correttezza e costo di algoritmi greedy e di programmazione dinamica
- saper affrontare con spirito critico gli algoritmi proposti, distinguendo i diversi gradi di difficoltà, e apprezzando la necessità di utilizzare tecniche avanzate (appena accennate in questo corso) per problemi per i quali non si conoscono algoritmi polinomiali
- riconoscere gli ingredienti comuni delle le strategie per la progettazione di algoritmi greedy o di programmazione dinamica per i problemi studiati

Abilità comunicative: aver acquisito e saper utilizzare la terminologia formale specifica relativa alle aree citate.

Capacità di apprendere: la comprensione delle tecniche algoritmiche e dei meccanismi di ragionamento e analisi relativi permetterà agli studenti di comprendere e apprendere algoritmi per problemi diversi che utilizzano le tecniche algoritmiche presentate.