ALGORITMI E COMPLESSITA'
Anno accademico 2024/2025 - Docente: PIETRO MAUGERIRisultati di apprendimento attesi
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 abilità comunicative ed un'adeguata appropriatezza espressiva nella comunicazione di problematiche inerenti gli studi algoritmici, anche ad interlocutori non esperti.
Capacità di apprendimento (learning skills): lo studente avrà la capacita di adattare le conoscenze acquisite anche a nuovi contesti, nonché di aggiornarsi attraverso la consultazione delle fonti specialistiche del settore algoritmico.
Modalità di svolgimento dell'insegnamento
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 DSAA 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 Daniele
Prerequisiti richiesti
Elementi di matematica discreta di analisi matematica oltre a competenze di base di programmazione.
Frequenza lezioni
Contenuti del corso
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.
Testi di riferimento
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
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Analisi ammortizzata. Stack con multipop e contatore binario. Metodi dell'aggregazione, degli accantonamenti e del potenziale. Tabelle dinamiche con inserimenti e cancellazioni. | Cap. 17.1-17.4 di 1) e materiale didattico integrativo |
| 2 | Splay trees: ricerca, inserimenti e cancellazioni, analisi ammortizzata di m operazioni di cui n sono inserimenti; top-down splay trees | Cap. 11.5 di 2) e materiale didattico integrativo |
| 3 | B-Tree: applicazioni, altezza, ricerca, inserimenti e cancellazioni | Cap. 18.1-18.4 di 1) e materiale didattico integrativo |
| 4 | 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 | Materiale didattico integrativo |
| 5 | 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 | Cap. 19.1-19.4 di 1) e materiale didattico integrativo |
| 6 | Strutture dati per insiemi disgiunti: unione per ranghi, compressione dei cammini, algoritmo Union-Find, notazione di Knuth, funzione di Ackermann e sua inversa | Cap. 21.1-21.3 di 1) e materiale didattico integrativo |
| 7 | Cammini minimi da una singola sorgente. Grafo dei cammini minimi, albero dei cammini minimi, algoritmo generico per i cammini minimi da singola sorgente, algoritmo di Bellman-Ford, algoritmo di Dijkstra, algoritmo lineare su grafi aciclici. | Materiale didattico integrativo e Cap. 24 di 1) |
| 8 | Cammini minimi tra tutte le coppie di nodi in grafi orientati. Algoritmo di Floyd-Warshall, chiusura transitiva, algoritmo di Johnson su grafi sparsi. | Materiale didattico integrativo e Cap. 25 di 1) |
| 9 | Alberi ricoprenti minimi. Passi rossi e passi blu, invariante del colore, algoritmi di Boruvka, di Kruskal e di Prim, clustering di massima separazione. | Materiale didattico integrativo e Cap. 23 di 1) |
| 10 | Reti di flusso e applicazioni | Cap. 26.1-26.3 e materiale didattico integrativo |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
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. La verifica dell'apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.
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.
Esempi di domande e/o esercizi frequenti
http://www.dmi.unict.it/~cantone/ESAMI/ESAMI_ALGORITMIeCOMPLESSITA/AeC-sample-2016.pdf