ALGORITMI E LABORATORIO M - Z

DIPARTIMENTO DI MATEMATICA E INFORMATICA Corso di laurea in Informatica

Anno accademico 2018/2019 - 2° anno

ALGORITMI E LABORATORIO M - Z

9 CFU - 1° semestre

Docenti titolari dell'insegnamento

SIMONE FARO - Modulo ALGORITMI - INF/01 - 6 CFU Email: [email protected]

Edificio / Indirizzo: Dipartimento di Matematica e Informatica, Viale A.Doria n.6 Telefono: 095 7383053

Orario ricevimento: Disponibile all'indirizzo http://www.dmi.unict.it/~faro/calendar.php MARIO FRANCESCO PAVONE - Modulo LABORATORIO - INF/01 - 3 CFU

Email: [email protected]

Edificio / Indirizzo: Dipartimento di Matematica ed Informatica; v.le A. Doria 6 Telefono: +390957383038

Orario ricevimento: Giovedì dalle 10:30 alle 12:00.

OBIETTIVI FORMATIVI

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.

LABORATORIO

Conoscenza e capacità di comprensione (knowledge and understanding): saranno acquisite le conoscenze relative alle al funzionamento e all'implementazione delle principali stutture dati

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

L'insegnamento è suddiviso in due moduli. Il primo modulo sarà svolto attraverso delle lezioni frontali (per un totale di 36 ore) in cui verranno presentati i contenuti del corso e verrano fornite le basi teoriche relative agll'uso di strutture dati avanzate e alla progettazione efficace di algoritmi. Lo studente avrà a disposizione un secondo modulo (per un totale di 36 ore) ore di lezione frontale da svolgere con il docente di Laboratorio, durante le quali verranno presentate le implementazioni degli algoritmi e delle strutture dati viste durante le lezioni del primo modulo. Inoltre lo studente avrà a disposizione una piattaforma di apprendimento attraverso la quale sarà possibile esercitarsi durante le ore di studio e autovalutarsi sui contenuti appresi a lezione. La medesima piattaforma fornisce un valido strumento per la preparazione all'esame.

LABORATORIO Laboratorio.

PREREQUISITI RICHIESTI

Per la frequenza del corso è richiesto che lo studente conosca le strutture dati elementari e le loro manipolazioni (in particolare liste, code, pile, alberi, grafi). Inoltre è richiesta la conoscenza di elementi di matematica discreta, di programmazione I e II, e di analisi matematica.

LABORATORIO

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

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

LABORATORIO

La frequenza è fortemente consigliata.

CONTENUTI DEL CORSO

ESCRIZIONE 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; distanze di hamming ed editing.

Algoritmi elementari su 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.

LABORATORIO

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

Il libro di testo consigliato è:

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

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.

LABORATORIO

I testi di riferimento sono gli stessi specificati per il modulo teorico di Algoritmi.

ALTRO MATERIALE DIDATTICO

Durante il corso verrà fornito agli studenti il codice degli esempi e degli esercizi visti a lezione. Lo studente avrà a disposizione una piattaforma di apprendimento attraverso la quale sarà possibile esercitarsi durante le ore di studio e autovalutarsi sui contenuti appresi a lezione. La medesima piattaforma fornirà un valido strumento per la propria preparazione all'esame.

LABORATORIO

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

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 di 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 LABORATORIO

Argomenti Riferimenti testi

1 Heap Binario e HeapSort 2 Ordinamento in tempo lineare 3 Indicizzazione e Hashing 4 Alberi Rosso-Neri

5 Programmazione dinamica 6 Programmazione Greedy

7 Algoritmi di Cammino Minimo su Grafi

VERIFICA DELL'APPRENDIMENTO

MODALITÀ DI VERIFICA DELL'APPRENDIMENTO ALGORITMI

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.

LABORATORIO

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,

ESEMPI DI DOMANDE E/O ESERCIZI FREQUENTI ALGORITMI

I testi delle prove di laboratorio in C++ saranno disponibili sul sito internet del docente. Inoltre lo studente avrà a disposizione una piattaforma di apprendimento attraverso la quale sarà possibile esercitarsi durante le ore di studio e autovalutarsi sui contenuti appresi a lezione. La medesima piattaforma fornisce un valido strumento per la preparazione all'esame.

Le domande relative alla prima prova d'esame sono le medesime che gli studenti potranno trovare all'interno del Sistema di Esercitazione.