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à nel problem solving e nella valutazione della complessità delle soluzioni.

Prerequisiti formali: Non è possibile accedere alle prove d'esame senza aver 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 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 le persone presenti).
In laboratorio le persone presenti vengono guidate 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 le persone assenti.
Durante la lezione viene usato lo strumento wooclap in modalità anonima per porre domande volte a verificare la comprensione degli argomenti e per stimolare la partecipazione.
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 un modo di misurarsi con gli argomenti presentati, in modo da scoprire eventuali proprie lacune o dubbi e poter quindi rivolgersi per tempo alla 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 coloro che non possono seguire le lezioni e come complemento e supporto anche per le persone che seguono.

L'attività in laboratorio richiede una partecipazione attiva e individuale, che consente in tal modo di sviluppare abilità pratiche (le capacità di realizzare un programma). Inoltre, il coinvolgimento attivo induce le persone che seguono a porsi dei quesiti (e spesso di conseguenza a porne alla docente); in tal modo si realizza una regolare verifica del modo in cui gli argomenti vengono recepiti.
In aggiunta, le domande poste tramite Wooclap permettono un costante monitoraggio delle difficoltà.

Le persone 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 persone con disabilità, DSA, BES, una volta preso contatto con lo Staff di Ateneo,
possono contattare la docente titolare dell'insegnamento in relazione alla declinazione delle
modalità di esame, in merito agli aspetti didattici.

Esistono due modalità d'esame distinte, a scelta dello studente. L'esame completo si articola in tre fasi: 10 domande a scelta multipla per verificare la comprensione delle funzioni, applicabilità uso e costi degli algoritmi; un semplice problema da risolvere con l'implementazione di uno degli algoritmi visti a lezione, per verificare la capacità di applicare gli algoritmi; domande orali, sui ragionamenti alla base della progettazione e della dimostrazione di correttezza degli algoritmi con verifica che la persona abbia acquisito la terminologia formale. L'orale si svolge nella stessa giornata (compatibilmente con il numero di persone iscritte). Il numero di domande può variare a seconda del modo in cui vengono date le risponde (formalità, chiarezza, completezza, precisione,...). La valutazione complessiva tiene conto delle varie parti. Per ottenere la sufficienza, è necessario raggiungere il livello comprensione della tassonomia di Bloom (secondo la revisione di Anderson e Krathwohl del 2001) nei tre argomenti proposti all'orale, che nello specifico per questo corso implica l'uso basilare della terminologia tecnica, la conoscenza di definizioni, pseudocodici degli algoritmi, complessità degli algoritmi, enunciato del teorema del taglio, e capacità di spiegare tali contenuti. Si raggiunge l'eccellenza mostrando una preparazione al livello di creazione della tassonomia, con conoscenza degli argomenti del corso, capacità di illustrare e spiegare i ragionamenti che portano alla progettazione degli algoritmi oggetto del corso, competenze per risolvere problemi, capacità di esprimersi con proprietà di linguaggio e di presentare gli argomenti con chiarezza. La seconda modalità d'esame si svolge completamente in laboratorio, con due quiz per un totale di 20 domande e non richiede conoscenza di dimostrazioni. Il primo quiz è lo stesso proposto nella prima modalità e un secondo quiz di 10 domande valuta la conoscenza del funzionamento degli algoritmi. Il quiz è a correzione automatica. La sufficienza si ottiene come nella versione normale dimostrando di avere raggiunto il livello comprensione della tassonomia, che concretamente si ottiene rispondendo correttamente al 70% delle domande. Il voto massimo, 22/30, denota il raggiungimento del livello applicazione della tassonomia e si raggiunge rispondendo correttamente al 90% delle domande. Chi ha raggiunto 22/30 può rispondere ad una domanda aperta aggiuntiva che propone la descrizione della soluzione a un problema usando gli algoritmi studiati. Si può raggiungere un voto fino a 24/30. Se i due quiz e la domanda aperta sono corretti al 100%, il voto diventa 25/30.

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à di comprendere e apprendere algoritmi per problemi diversi che utilizzano le tecniche algoritmiche presentate.