INTRODUCTION TO ALGORITHMS & LABORATORY

9 CFU - 1° semestre

Docenti titolari dell'insegnamento

DOMENICO CANTONE - Modulo INTRODUCTION TO ALGORITHMS - INF/01 - 6 CFU
DANIELE FRANCESCO SANTAMARIA - Modulo LABORATORY - INF/01 - 3 CFU

Obiettivi formativi

INTRODUCTION TO ALGORITHMS
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.
LABORATORY
Conoscenza e capacità di comprensione (knowledge and understanding): saranno acquisite le conoscenze relative alle al funzionamento e all'implementazione delle principali stutture dati analizzate durante il modulo teorico di Algoritmi. Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): saranno acquisite le capacità di implementazione e di progettazione di soluzioni algoritmiche. Autonomia di giudizio (making judgements): Lo studente sarà in grado di giudicare l'efficacia della propria implementazione e del proprio lavoro progettuale. Capacità di apprendimento (learning skills): lo studente sarà in grado di adattare le soluzioni analizzate durante le lezioni anche in altri contesti.

Modalità di svolgimento dell'insegnamento

INTRODUCTION TO ALGORITHMS
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.
LABORATORY
Lezioni frontali dedicate all'implementazione in tempo reale degli algoritmi e delle strutture dati presentati nel modulo teorico. Qualora l'insegnamento venisse impartito in modalità 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. La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.

Prerequisiti richiesti

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

Elementi di matematica discreta, di programmazione I e II, e di analisi matematica
LABORATORY
Il corso presuppone una buona conoscenza di Elementi di Matematica Discreta, e di Analisi Matematica. Inoltre lo studente deve conoscere i paradigmi base di programmazione e delle principali strutture dati. La conoscenza del linguaggio di programmazione ad oggetti C++ è un prerequisito fondamentale.

Frequenza lezioni

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

Contenuti del corso

INTRODUCTION TO ALGORITHMS
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
LABORATORY
Il modulo di Laboratorio di Algoritmi ha lo scopo di fornire gli strumenti per l'implementazione degli algoritmi e delle strutture dati trattate nel corso di Algoritmi, attraverso l'utilizzo della programmazione ad oggetti. Il linguaggio C++ verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.

Testi di riferimento

INTRODUCTION TO ALGORITHMS
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.
LABORATORY
I testi di riferimento sono gli stessi specificati per il modulo teorico di Algoritmi.

Altro materiale didattico

INTRODUCTION TO ALGORITHMS
I lucidi delle lezioni e delle esercitazioni sono messi a disposizione degli studenti sul sito http://www.dmi.unict.it/~cantone/HomeAlgoritmi-17/itAlgoritmi.html
LABORATORY
Tutto il materiale utilizzato nel corso, inclusi i codici degli esempi o degli esercizi svolti durante le lezioni, verrà reso disponibile in un'apposita pagina web che verrà comunicata all'inizio delle lezioni.

Programmazione del corso

INTRODUCTION TO ALGORITHMS
	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	Ricorrenze	Cap. 4.3-4.5 di 1) e materiale didattico integrativo
5	Heapsort	Cap. 6 di 1) e materiale didattico integrativo
6	Quicksort	Cap. 7 di 1)
7	Ordinamento in tempo lineare	Cap. 8 di 1) e materiale didattico integrativo
8	Hashing	Cap. 11.1-11.4 di 1) e materiale didattico integrativo
9	Alberi rosso-neri	Cap. 13 di 1) e materiale didattico integrativo
10	Elementi della programmazione dinamica	Cap. 15 di 1) e materiale didattico integrativo
11	Elementi della strategia golosa	Cap. 16.1-16.3 di 1) e materiale didattico integrativo
12	Algoritmi elementari per grafi	Capp. 24.1-24.4, 25-1 e 25-3 di 1) e materiale didattico integrativo
LABORATORY
	Argomenti	Riferimenti testi
1	Heap ed HeapSort	Materiale didattico integrativo fornito dal docente
2	Ordinamento in tempo lineare	Materiale didattico integrativo fornito dal docente
3	Indicizzazione e Hashing	Materiale didattico integrativo fornito dal docente
4	Alberi Rosso Neri	Materiale didattico integrativo fornito dal docente
5	Programmazione dinamica	Materiale didattico integrativo fornito dal docente
6	Programmazione greedy	Materiale didattico integrativo fornito dal docente
7	Grafi e cammini minimi	Materiale didattico integrativo fornito dal docente

Verifica dell'apprendimento

MODALITÀ DI VERIFICA DELL'APPRENDIMENTO

INTRODUCTION TO ALGORITHMS
L’esame finale è essenzialmente scritto. La verbalizzazione sarà 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.
LABORATORY
L'esame si svolgerà in due prove.

Prima prova: consiste di un test a risposta multipla attraverso il sistema di esercitazione, secondo le modalità specificate all'interno dello stesso. La prova avrà durata di 45 minuti.

Seconda Prova: consiste nell'implementazione in C++ di una, o più strutture dati ed algoritmi presentati e analizzati a lezione.

Alla seconda prova si potrà accedere se si è conseguita una valutazione superiore o uguale a 18 nella prima prova. La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.

ESEMPI DI DOMANDE E/O ESERCIZI FREQUENTI

INTRODUCTION TO ALGORITHMS
http://www.dmi.unict.it/~cantone/ESAMI/ESAMI_ALGORITMI_TRIENNALE/Algoritmi-sample-2016.pdf
LABORATORY
Le domande relative alla prima prova d'esame e gli esercizi di programmazione relativi alla seconda prova sono le medesime che gli studenti potranno trovare all'interno del Sistema di Esercitazione.

Apri in formato Pdf English version