ALGORITMI E LABORATORIO A - L

Anno accademico 2018/2019 - 2° anno
Docenti Crediti: 9
SSD: INF/01 - Informatica
Organizzazione didattica: 225 ore d'impegno totale, 153 di studio individuale, 36 di lezione frontale, 36 di laboratorio
Semestre:

Obiettivi formativi

  • ALGORITMI

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

  • ALGORITMI

    Lezioni frontali

  • LABORATORIO

    Laboratorio.


Prerequisiti richiesti

  • ALGORITMI

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

    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

  • ALGORITMI

    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

  • ALGORITMI

    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

  • 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

  • ALGORITMI

    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.

  • LABORATORIO

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


Programmazione del corso

ALGORITMI
 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 
LABORATORIO
 ArgomentiRiferimenti testi
1Heap Binario e HeapSort 
2Ordinamento in tempo lineare 
3Indicizzazione e Hashing 
4Alberi Rosso-Neri 
5Programmazione dinamica 
6Programmazione Greedy 
7Algoritmi 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

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

  • LABORATORIO

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