Ateneo - UPO

Tecniche algoritmiche, nozione di grafo e algoritmi su grafi

- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Algoritmi e strutture dati 2/ed MacGraw-Hill, 2008; ISBN: 978 88 386 64687
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction to Algorithms, third edition
McGraw-Hill, 2010. (presente anche in italiano)

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.

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 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 lo studente viene guidato 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.
Sul sito DIR del corso sono disponibili dei quiz di esercizio e autovalutazione 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.

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.

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.

Esame scritto seguito da orale (con valutazione degli esercizi svolti in laboratorio)
L'esame scritto ha lo scopo di verificare che lo studente abbia capito gli algoritmi classici e il loro utilizzo, e sia in grado di applicarli alla risoluzione di problemi. Principalmente, sono richiesti due tipi di competenze: (i) aver capito, e saper utilizzare in casi semplici, gli algoritmi classici visti a lezione e (ii) saper risolvere, tramite l’implementazione o la modifica di un algoritmo classico, dei semplici problemi posti.
L’esame scritto è solitamente composto da 5 domande, delle quali
- almeno una richiede l’applicazione di un algoritmo standard sui grafi,
- almeno una richiede l’applicazione di un algoritmo greedy o di programmazione dinamica
- almeno una richiede di modificare un algoritmo conosciuto per affrontare un problema posto
- almeno una riguarda la teoria, con risposte aperte o a crocette V/F
Lo studente che supera l’esame scritto (con votazione >= 18) può accedere alla prova orale.
L’esame orale verifica le competenze teoriche. In particolare, si verifica che lo studente abbia acquisito la terminologia formale e la capacità di analisi. Vengono poste delle domande (solitamente 3, il cui numero può variare in base alle risposte date) che hanno come obbiettivo: (i) verifica della familiarità con il concetto di grafo nelle sue varianti, (ii) capacità di analisi di algoritmi di visita di grafi, (iii) capacità di analisi di algoritmi greedy e di programmazione dinamica, (iv) basilare sensibilità su come affrontare problemi difficili.
Al termine della prova orale viene espresso un voto che tiene conto per il 50% della prova scritta e per l’altro 50% della prova orale. Se lo studente svolge gli esercizi di laboratorio (obbligatori per studenti frequentanti) il voto della prova orale può essere modificato dalla valutazione del laboratorio (l’ammontare del modificatore è comunicato ad inizio corso)

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 (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 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 (utilizzo negli algoritmi di routing)
-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.

Enunciare la definizione di grafo, ed analizzare i diversi modi di rappresentare un grafo in relazione alle applicazioni.
Descrivere il concetto di visita di grafo, e identificarne esempi.
Descrivere le strategie greedy e di programmazione dinamica.
Identificare esempi per ciascuna delle strategie elencate.
Descrivere e spiegare il ragionamento che porta alla progettazione (e che dimostra la correttezza) di algoritmi classici su grafi.
Descrivere l'analisi di complessità/correttezza di tali algoritmi.
Applicare gli algoritmi classici a semplici istanze.
Descrivere le classi P ed NP e il loro rapporto e l'idea di soluzione approssimata; illustrare l'analisi degli algoritmi approssimati visti a lezione.
Modellare un problema dato con un problema classico su grafo, scegliendo il tipo di grafo appropriato.
Implementare in Java gli algoritmi classici sui grafi presentati a lezione.