ALGORITMI
Anno accademico 2015/2016 - 2° anno - Curriculum A e Curriculum BCrediti: 9
Organizzazione didattica: 225 ore d'impegno totale, 153 di studio individuale, 72 di lezione frontale
Semestre: 1°
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.
Obiettivi formativi generali dell'insegnamento in termini di 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.
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
Visita in ampiezza
Visita in profondità (classificazione degli archi)
Ordinamento topologico
Componenti fortemente connesse
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 | * | 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 | Cap. 22 di 1) e materiale didattico integrativo |
N.B. La conoscenza degli argomenti contrassegnati con l'asterisco è condizione necessaria ma non sufficiente per il superamento dell'esame. Rispondere in maniera sufficiente o anche più che sufficiente alle domande su tali argomenti non assicura, pertanto, il superamento dell'esame.
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
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.
Esempi di domande e/o esercizi frequenti
http://www.dmi.unict.it/~cantone/ESAMI/ESAMI_ALGORITMI_TRIENNALE/Algoritmi-sample-2016.pdf