ALGORITMI E COMPLESSITA'

Capacità  di applicare conoscenza e comprensione (applying knowledge and understanding):  saranno acquisite le capacità di risolvere problemi di media difficoltà che richiedono la progettazione e l'analisi di soluzioni algoritmiche avanzate.

Autonomia di giudizio (making judgements): lo studente sarà in grado di valutare la qualità di una soluzione algoritmica in termini di efficienza e possibilità di riutilizzo.

Abilità comunicative (communication skills): saranno acquisite le necessarie capacità comunicative e un’adeguata padronanza espressiva nella presentazione di problematiche inerenti gli studi algoritmici, anche ad interlocutori non esperti.

Capacità  di apprendimento (learning skills): lo studente avrà la capacità di adattare le conoscenze acquisite anche a nuovi contesti, nonché di aggiornarsi attraverso la consultazione delle fonti specialistiche del settore algoritmico.

Lezioni frontali 

Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.

Informazioni per studenti con disabilità e/o DSA

A garanzia di pari opportunità e nel rispetto delle leggi vigenti, gli studenti interessati possono chiedere un colloquio personale in modo da programmare eventuali misure compensative e/o dispensative, in base agli obiettivi didattici ed alle specifiche esigenze.

E' possibile rivolgersi anche al docente referente CInAP (Centro per l’integrazione Attiva e Partecipata - Servizi per le Disabilità e/o i DSA) del nostro Dipartimento, prof.ssa Patrizia Daniele.

Strutture dati elementari e loro manipolazioni (liste, code, pile, alberi, ecc.)

Elementi di matematica discreta, di programmazione I e II, e di analisi matematica.

Algoritmi elementari e metodologie di programmazione dinamica e greedy.

La frequenza delle lezioni non è obbligatoria, ma per una piena comprensione degli argomenti del corso e delle tecniche risolutive illustrate essa è fortemente consigliata.

Descrizione generale del corso

Vengono presentate e analizzate, anche mediante la tecnica dell'analisi ammortizzata, diverse strutture dati avanzate (quali B-tree, splay tree, heap binomiali e heap di Fibonacci) e le procedure per la loro gestione. Inoltre vengono studiati, progettati e analizzati algoritmi su grafi per la soluzione efficiente di svariati problemi di ottimizzazione.

PROGRAMMA PARTICOLAREGGIATO DEL CORSO

Analisi ammortizzata
Stack con multipop e contatore binario
Metodi dell'aggregazione, degli accantonamenti e del potenziale
Tabelle dinamiche con inserimenti e cancellazioni

Strutture dati avanzate
B-alberi: applicazioni, altezza, ricerca, inserimenti e cancellazioni
Splay trees: ricerca, inserimenti e cancellazioni, analisi ammortizzata di m operazioni di cui n sono inserimenti; top-down splay trees
Strutture dati per insiemi disgiunti: unione per ranghi, compressione dei cammini, algoritmo Union-Find, notazione di Knuth, funzione di Ackermann e sua inversa
Heap binomiali: alberi binomiali, operazioni di inserimento, minimo ed estrazione del minimo, decremento di una chiave, cancellazione di una chiave, unione di due heap binomiali
Heap di Fibonacci: alberi binomiali non ordinati, operazioni di inserimento, minimo ed estrazione del minimo, decremento di una chiave, cancellazione di una chiave, unione di due heap di Fibonacci, analisi ammortizzata

Cammini minimi da una singola sorgente in grafi orientati
Grafo dei cammini minimi, albero dei cammini minimi, algoritmo generico per i camminimi minimi da singola sorgente, algoritmo di Bellman-Ford, algoritmo di Dijkstra, algoritmo lineare su grafi aciclici

Cammini minimi tra tutte le coppie di nodi in grafi orientati
Algoritmo di Floyd-Warshall, chiusura transitiva, algoritmo di Johnson su grafi sparsi

Alberi ricoprenti minimi
Passi rossi e passi blu, invariante del colore, algoritmi di Boruvka, di Kruskal e di Prim, clustering di massima separazione

Reti di flusso e applicazioni
Flusso reale e flusso netto in una rete di flusso, proprietà del flusso netto, reti con sorgenti e pozzi multipli, notazione di sommatoria implicita, il metodo di Ford-Fulkerson, capacità e rete residue, cammini aumentanti, tagli in reti di flusso, teorema del massimo flusso/minimo taglio, analisi della procedura di Ford-Fulkerson, abbinamento massimo in grafi bipartiti, algoritmo di Edmonds-Karp e sua analisi di complessità, edge-connectivity.

Il libro di testo consigliato è:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009

disponibile anche nella traduzione italiana 

1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.

Altra fonte:

2) M.A. Weiss. Data structures and algorithmic analysis in C (Second Edition), Addison-Wesley, 1996.

Modalità di verifica dell'apprendimento
La prova d’esame è finalizzata a valutare in modo approfondito la preparazione dello studente, la capacità di analisi e di ragionamento sugli argomenti trattati durante il corso, nonché l’adeguatezza del linguaggio tecnico utilizzato.

L’esame finale è essenzialmente scritto. La verbalizzazione potrà essere preceduta da una breve discussione sul compito scritto e, nei casi dubbi, da una breve verifica orale.

Tali prove potranno avere luogo per via telematica, qualora le condizioni lo dovessero richiedere. L’eventuale prova orale potrà svolgersi il giorno stesso in cui è stata svolta la prova scritta o a distanza di pochi giorni da esso. 

L’eventuale prova orale ha valore integrativo rispetto alla prova scritta e concorre alla determinazione del voto finale in modo inscindibile. Essa non rappresenta un’opportunità di incremento del punteggio, ma un completamento necessario per la valutazione complessiva della preparazione dello studente.

Per l'attribuzione del voto finale si seguiranno di norma i seguenti criteri:

- non approvato: lo studente non ha ancora acquisito i concetti di base e non riesce a svolgere in modo adeguato gli esercizi.

- 18-23: lo studente dimostra una conoscenza essenziale dei concetti di base; le capacità espositive e di collegamento tra i contenuti sono limitate, ma riesce a risolvere esercizi semplici.

- 24-27: lo studente dimostra una buona conoscenza dei contenuti del corso, sa esporli in modo chiaro e collegarli tra loro; risolve gli esercizi con pochi errori.

- 28-30 e lode: lo studente ha acquisito una conoscenza completa dei contenuti, li espone con chiarezza e spirito critico e risolve gli esercizi in modo accurato e senza errori.

Gli studenti con disabilità e/o DSA dovranno contattare con sufficiente anticipo rispetto alla data dell'esame il docente, il referente CInAP del DMI (prof.ssa Daniele) e il CInAP per comunicare che intendono sostenere l'esame fruendo delle opportune misure compensative.

A titolo esemplificativo, ecco alcuni esempi di domande d’esame:

1. Si definisca la struttura dati dei B-tree e si determini il grado minimo di un dato B-tree.

2.  Illustrare l'esecuzione di una lista di operazioni di ricerca, inserimento e cancellazione di una chiave in un dato B-tree.

3.  Si determini il numero massimo e il numero minimo di nodi che può essere contenuto in un B-tree di data altezza h e di dato grado minimo t.

4.  Si illustri un algoritmo efficiente (anche mediante pseudo-codice) per determinare i cammini minimi da una sorgente assegnata a tutti i nodi da essa raggiungibili in un grafo orientato aciclico con funzione peso a valori reali.

5.  Si definisca il grafo dei cammini minimi di un dato grafo pesato con pesi positivi e si illustri un algoritmo efficiente per calcolarlo.

6.  Si descriva l'algoritmo di Prim (anche mediante il suo pseudo-codice) e lo si applichi ad un dato grafo.

7.  Si descrivano i cosiddetti “passi blu” e “passi rossi” negli algoritmi per il calcolo del minimum spanning tree. Quindi si enunci l’invariante del colore e lo si dimostri limitatamente ai passi blu.

Nota: gli esercizi sopra riportati sono solo esempi; la prova potrà includere anche domande su altri argomenti del programma.