1014263 - ALGORITMI E LABORATORIO M - Z
Modulo 1014264 - ALGORITMI
Risultati di apprendimento attesi
Conoscenza e capacità di comprensione (knowledge and understanding): saranno acquisite le conoscenze relative alle principali metodologie per la progettazione e l'implementazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi).
Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): gli studenti saranno dotati delle competenze necessarie per affrontare con successo problemi computazionali di livello elementare, richiedenti l'attenta progettazione e l'analisi di soluzioni algoritmiche.
Autonomia di giudizio (making judgements): lo studente acquisirà la capacità di valutare la qualità di una soluzione algoritmica, esaminandone attentamente l'efficienza intrinseca e la sua idoneità al riutilizzo in contesti vari.
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. Lo studente svilupperà altresì la competenza di esaminare e consultare articoli scientifici in modo flessibile in relazione alle specifiche problematiche che si intende affrontare.
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.
Prerequisiti richiesti
Lo studente dovrà conoscere le principali strutture dati elementari e le procedure che ne permettono la manipolazione. Nello specifico si richiede la buona conoscenza delle strutture dati liste, code, pile e alberi binari di ricerca. Si richiede una buona conoscenza della struttura dati grafo e degli algoritmi elementari per la sua visita, ovvero visita DFS e visita BFS. Si richiede anche una buona conoscenza dell'algoritmo per il calcolo delle componenti connesse di un grafo e quello per il calcolo di un ordinamento topologico di un grafo.
Si richiede inoltre una buona conoscenza degli elementi di matematica discreta e di analisi matematica e dei concetti presentati nei corsi di Programmazione I e II.
Frequenza lezioni
La frequenza delle lezioni è obbligatoria.
Contenuti del corso
Il corso presenta le principali metodologie di progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi) oltre a offrire alcune specifiche tecniche di implementazione degli algoritmi e delle strutture dati trattate attraverso l'utilizzo del linguaggio C++. Saranno inoltre forniti gli strumenti utili all'analisi del problema computazionale al fine di individuare la corretta strategia di risoluzione del problema.
PROGRAMMA PARTICOLAREGGIATO DEL CORSO
Introduzione
- Problemi computazionali e algoritmi: il problema dell'ordinamento
- Algoritmi come tecnologia
- Metodologia incrementale: esempi e implementazioni
- Metodologia ricorsiva o divide-et-impera: esempi e implementazioni
Ordinamento e statistiche d'ordine
- Metodologia incrementale applicata al problema dell'ordinamento
- Metodologia ricorsiva applicata al problema dell'ordinamento
- Heap e procedura per la sua costruzione
- Implementazione di un Heap e delle sue procedure
- L'algoritmo Heapsort e la sua implementazione
- Code di priorità e la loro implementazione
- L'algoritmo Quicksort e sua versione randomizzata
- Ordinamento in tempo lineare: algoritmi Counting-Sort, Radix-Sort, Bucket-Sort
- Implementazione del Counting-Sort
- Mediane e statistiche d'ordine
Hashing
- Definizione e caratteristiche delle tabelle hash
- Hashing con concatenazione
- Funzioni hash (metodo della divisione, metodo della moltiplicazione, hashing universale)
- Implementazione di una tabella hash con concatenazione
- Hashing con indirizzamento aperto
- Metodi di scansione (scansione lineare, scansione quadratica, hashing doppio)
- Implementazione di una tabella hash con indirizzamento aperto
Alberi rosso-neri
- Caratteristiche e definizioni
- Operazioni di Rotazione in un albero binario di ricerca
- Inserimento in un albero rosso-nero
- Cancellazione in un albero rosso-nero
Elementi della programmazione dinamica
- Caratterizzazione: sottostruttura ottima, ripetizione dei sottoproblemi, ricostruzione di una soluzione ottima.
- Alcuni casi di studio: programmazione delle catene di montaggio, moltiplicazione di una sequenza di matrici, problema dello zaino, problema del resto.
Elementi della strategia golosa
- Caratterizzazione: proprietà della scelta golosa, sottostruttura ottima
- Alcuni casi di studio: problema della selezione di attività, costruzione di un codice di Huffman, problema dello zaino, problema del resto.
Algoritmi elementari per grafi
- Cammini minimi da sorgente unica: algoritmo di Bellman-Ford, cammini minimi da sorgente unica nei grafi orientati aciclici, algoritmo di Dijkstra.
- Cammini minimi tra tutte le coppie: algoritmo basato sulla moltiplicazione di matrici, algoritmo di Floyd-Warshall.
- Implementazione degli algoritmi di cammino minimo su grafi.
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
1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Introduzione. Algoritmi come tecnologia. | Cap.1.1-1.2 di 1) |
| 2 | Algoritmo Insertion-Sort | Cap. 2.1 di 1) e materiale didattico integrativo |
| 3 | Divide-et-impera | Cap. 4.1 di 1) e materiale didattico integrativo |
| 4 | Heapsort | Cap. 6 di 1) e materiale didattico integrativo |
| 5 | Quicksort | Cap. 7 di 1) |
| 6 | Ordinamento in tempo lineare | Cap. 8 di 1) e materiale didattico integrativo |
| 7 | Hashing | Cap. 11.1-11.4 di 1) e materiale didattico integrativo |
| 8 | Alberi rosso-neri | Cap. 13 di 1) e materiale didattico integrativo |
| 9 | Elementi della programmazione dinamica | Cap. 15 di 1) e materiale didattico integrativo |
| 10 | Elementi della strategia golosa | Cap. 16.1-16.3 di 1) e materiale didattico integrativo |
| 11 | Algoritmi elementari per grafi | Cap. 24.1-24.4, 25-1 e 25-3 di 1) e materiale didattico integrativo |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
La prova di esame del modulo di Algoritmi è suddivisa in due parti: una prima prova scritta (obbligatoria) e una successiva prova orale (che potrà essere facoltativa per gli studenti ammessi senza riserva). Tali prove potranno avere luogo per via telematica, qualora le condizioni lo dovessero richiedere.
Alla fine della prova scritta lo studente riceverà una delle tre seguenti valutazioni:
- NON AMMESSO alla prova orale
- AMMESSO CON RISERVA alla prova orale
- AMMESSO ala prova orale
In quest'ultimo caso allo studente verrà comunicato il voto ottenuto nella prova scritta, voto che sarà compreso tra 18 e 25.
La prova orale potrà svolgersi il giorno stesso in cui è stata svolta la prova scritta o a distanza di pochi giorni da esso. Tale prova avrà lo scopo di valutare più nel dettaglio la preparazione dello studente, la sua capacità di ragionamento relativamente agli argomenti trattati a lezione, nonché la sua proprietà di linguaggio.
La valutazione della prova orale si dovrà intendere ad integrazione del voto ottenuto nella prova scritta e non a suo incremento.
- Gli studenti AMMESSI alla prova orale potranno chiedere di essere esonerati dal sostenere tale prova, accettando quindi il voto comunicato ad essi alla fine della prova scritta.
- Gli studenti AMMESSI CON RISERVA non potranno usufruire della precedente possibilità e, qualora desiderassero continuare l'iter dell'esame, dovranno sostenere obbligatoriamente la prova orale per concludere l’esame del modulo di Algoritmi.
- Gli studenti NON AMMESSI alla prova orale dovranno ripetere la prova scritta in un successivo appello.
Per l'attribuzione del voto finale si seguiranno di norma i seguenti criteri:
- non approvato: lo studente non ha acquisito i concetti di base e non è in grado di svolgere gli esercizi.
- 18-23: lo studente dimostra una padronanza minima dei concetti di base, le sue capacità di esposizione e di collegamento dei contenuti sono modeste, riesce a risolvere semplici esercizi.
- 24-27: lo studente dimostra una buona padronanza dei contenuti del corso, le sue capacità di esposizione e di collegamento dei contenuti sono buone, risolve gli esercizi con pochi errori.
- 28-30 e lode: lo studente ha acquisito tutti i contenuti del corso ed è in grado di esporli compiutamente e di collegarli con spirito critico; risolve gli esercizi in modo completo e senza errori.
Per partecipare all'esame è necessario avere effettuato la prenotazione sul portale SmartEdu.
Si fa presente che l'esame del modulo di Algoritmi e quello del modulo di Laboratorio di Algoritmi si svolgeranno contestualmente e verranno quindi valutati contestualmente.
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
English version