ALGORITMI E LABORATORIO A - L
Modulo ALGORITMI

Anno accademico 2022/2023 - Docente: Domenico CANTONE

Risultati di apprendimento attesi

Conoscenza e capacità  di comprensione (knowledge and understanding): saranno acquisite le conoscenze relative alle principali metodologie per la progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi) nonché le tecniche per la loro analisi di complessità, sia nel caso pessimo che in quello medio.
Capacità  di applicare conoscenza e comprensione (applying knowledge and understanding):  saranno acquisite le capacità di risolvere semplici problemi che richiedono la progettazione e l'analisi di soluzioni algoritmiche.
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.

Prerequisiti richiesti

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

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

Frequenza lezioni

Per una piena comprensione degli argomenti del corso e delle tecniche illustrate, la frequenza delle lezioni è fortemente consigliata.

Contenuti del corso

Descrizione generale del corso

Il corso presenta le principali metodologie di progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi) e le tecniche per l'analisi di complessità, sia nel caso pessimo che nel caso medio.

PROGRAMMA PARTICOLAREGGIATO DEL CORSO

Introduzione
Problemi computazionali e algoritmi: il problema dell'ordinamento
Algoritmi come tecnologia
Metodologia incrementale: algoritmo Insertion-Sort (correttezza e complessità)
Metodologia divide-et-impera: algoritmo Merge-Sort (complessità)
Notazioni asintotiche e relazioni tra esse
Notazioni standard e funzioni comuni

Ricorrenze
Il metodo di sostituzione
Il metodo iterativo e dell'albero di ricorsione
Il teorema master

Ordinamento e statistiche d'ordine

Heap e procedura per la sua costruzione
L'algoritmo Heapsort
Code di priorità
L'algoritmo Quicksort e sua versione randomizzata
Analisi di Quicksort nel caso peggiore e nel caso medio
Limiti inferiori per l'ordinamento
Ordinamento in tempo lineare: algoritmi Counting-Sort, Radix-Sort, Bucket-Sort
Mediane e statistiche d'ordine

Hashing
Tabelle hash
Funzioni hash (metodo della divisione, metodo della moltiplicazione, hashing universale)
Indirizzamento aperto

Alberi rosso-neri
Rotazioni, inserimenti, cancellazioni
Analisi di complessità

Elementi della programmazione dinamica
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, la più lunga sottosequenza comune, distanza di editing

Elementi della strategia golosa
Proprietà della scelta golosa, sottostruttura ottima
Alcuni casi di studio: problema della selezione di attività, costruzione di un codice di Huffman

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 di Floyd-Warshall, chiusura transitiva di un grafo orientato

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

 ArgomentiRiferimenti testi
1Introduzione. Algoritmi come tecnologia.Cap.1.1-1.2 di 1)
2Algoritmo Insertion-SortCap. 2.1 di 1) e materiale didattico integrativo
3Divide-et-imperaCap. 4.1 di 1) e materiale didattico integrativo
4RicorrenzeCap. 4.3-4.5 di 1) e materiale didattico integrativo
5HeapsortCap. 6 di 1) e materiale didattico integrativo
6QuicksortCap. 7 di 1)
7Ordinamento in tempo lineareCap. 8 di 1) e materiale didattico integrativo
8HashingCap. 11.1-11.4 di 1) e materiale didattico integrativo
9Alberi rosso-neriCap. 13 di 1) e materiale didattico integrativo
10Elementi della programmazione dinamicaCap. 15 di 1) e materiale didattico integrativo
11Elementi della strategia golosaCap. 16.1-16.3 di 1) e materiale didattico integrativo
12Algoritmi elementari per grafiCapp. 24.1-24.4, 25-1 e 25-3 di 1) e materiale didattico integrativo

Verifica dell'apprendimento

Modalità di verifica dell'apprendimento

Si ricorda che, in ogni caso, prima della verbalizzazione finale lo studente dovrà avere superato l’esame del modulo di Laboratorio di Algoritmi.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 prova orale integra la prova scritta e la sua valutazione non è dunque da intendersi come mero incremento del voto ottenuto in quest’ultima.

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 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.

Si ricorda che, in ogni caso, prima della verbalizzazione finale lo studente dovrà avere superato l’esame del modulo di Laboratorio di Algoritmi.

Esempi di domande e/o esercizi frequenti

http://www.dmi.unict.it/cantone/ESAMI/ESAMI_ALGORITMI_TRIENNALE/Algoritmi-sample-2016.pdf