ALGORITMI E LABORATORIO

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 ad altri contesti.

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

  Lo studente dovrà conoscere i proncipali paradigmi di programmazione e le 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 delle lezioni è 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
  Visita in ampiezza
  Visita in profondità (classificazione degli archi)
  Ordinamento topologico
  Componenti fortemente connesse

• 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 iul modulo teorico di Algoritmi

Programmazione del corso

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.
  La prima prova, della durata di 45 minuti, consiste in un test a risposta multipla, che viene sostenuto attraverso il sistema di esercitazione e secondo le modalità specificate all'interno dello stesso.
  Gli studenti che avranno ottenuto una valutazione superiore o uguale a 18 nella prima prova potranno accedere all seconda prova, della durata di circa 90 minuti. Tale prova di laboratorio consisterà nell'implementazione, in C++, di una o più tre le strutture dati studiate a lezione. La seconda prova verrà svolta attraverso l'utilizzo di un editor di testo e di un compilatore.

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. I testi delle prove di laboratorio in C++ sono invece disponibili sul sito internet del docente.