DIPARTIMENTO DI MATEMATICA E INFORMATICA
Corso di laurea in Informatica
Anno accademico 2021/2022 - 2° anno - Curriculum Elaborazione Dati e Applicazioni e Curriculum Sistemi e Applicazioni

ALGORITMI E LABORATORIO M - Z

Docenti titolari dell'insegnamento

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 al funzionamento e all'implementazione delle principali strutture 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 al meglio le soluzioni analizzate durante le lezioni anche in altri contesti.

Modalità di svolgimento dell'insegnamento

• ALGORITMI
  

  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.

• LABORATORIO
  

  Lezioni frontali saranno dedicate all'implementazione in tempo reale degli algoritmi e delle strutture dati presentati nel modulo teorico. Qualora l'insegnamento venisse impartito in modalità mista o a distanza, potranno essere introdotte le necessarie variazioni 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

• 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
  

  T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009. La versione in lingua originale è obbligatoria.

Altro materiale didattico

• ALGORITMI
  

  Appunti e ulteriore materiale didattico verrà fornito dal docente nel corso delle lezioni

• LABORATORIO
  

  Tutto il materiale utilizzato nel corso, inclusi i codici degli esempi o degli esercizi svolti durante le lezioni, verrà reso disponibile in nella pagina web del docente, la quale verrà comunicata all'inizio delle lezioni.

Programmazione del corso

Verifica dell'apprendimento

• 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 valutazione della prova orale si dovrà intendere ad integrazione del voto ottenuto nella prova scritta e non a suo incremento.

  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.

• LABORATORIO
  

  L'esame consiste nell'implementazione in C++ di una o più strutture dati e/o algoritmi presentati e analizzati a lezione. Al termine della prova lo studente riceverà una delle due seguenti valutazioni: "prova superata", "prova non superata". La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.

• ALGORITMI
  

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

• LABORATORIO
  

  Gli esercizi di programmazione possono essere o i medesimi che gli studenti troveranno all'interno del Sistema di Esercitazione o realizzati ex-novo dal docente