Presentazione

Organizzazione della Didattica

DM270
INFORMATICA ORD. 2014

Algoritmi avanzati

6

Corsi comuni

 

Frontali Esercizi Laboratorio Studio Individuale
ORE: 48 0 0 102

Periodo

AnnoPeriodo
I anno2 semestre

Frequenza

Facoltativa

Erogazione

Convenzionale

Lingua

Italiano

Calendario Attività Didattiche

InizioFine
02/03/202012/06/2020

Tipologia

TipologiaAmbitoSSDCFU
caratterizzanteDiscipline informaticheINF/016


Responsabile Insegnamento

ResponsabileSSDStruttura
Dott. SCQUIZZATO MICHELEINF/01

Altri Docenti

DocenteCoperturaSSDStruttura
DA ASSEGNARE-N.D.

Attività di Supporto alla Didattica

Non previste

Bollettino

Il corso richiede familiarità con alcuni concetti algoritmici di base, quali complessità asintotica, algoritmi di ricerca e ordinamento e strutture dati di base come alberi, liste, mappe, vettori e matrici. Non ci sono corsi propedeutici.

Il corso si pone l'obiettivo di insegnare agli studenti a pensare "in modo algoritmico", fornendo le seguenti conoscenze e abilità attese: 1. Essere in grado di comprendere un problema da risolvere, di quali sono i dati disponibili e come deve essere fornita la soluzione. 2. Essere in grado di formulare un problema in termini di input e output trattabili da un calcolatore. 3. Essere in grado di definire un algoritmo e di analizzarne le proprietà di correttezza e complessità computazionale. 4. Essere in grado di implementare un algoritmo in un linguaggio di programmazione concreto. 5. Essere in grado eseguire l'implementazione su un dataset di media dimensione e di comprenderne ed analizzarne i risultati.

Il corso è suddiviso in blocchi tematici. Ogni blocco inizia con una serie di lezioni frontali in aula durante le quali vengono affrontati i contenuti del corso. Terminata l'attività frontale, il blocco prosegue con una o più lezioni di laboratorio dove gli studenti divisi a gruppi implementeranno e testeranno la soluzione del problema reale su un dataset di media dimensione, e si conclude con una fase di confronto e discussione delle varie soluzioni realizzate.

1) Algoritmi su grafi: Nozioni di base sui grafi e loro rappresentazione. Generazione randomizzata di grafi. Visite in ampiezza e in profondità di un grafo. Componenti Connesse. Algoritmi ``greedy''. Grafi pesati: cammini mimimi e alberi di connessione minimi. Strutture dati per insiemi disgiunti. 2) Algoritmi di approssimazione per problemi intrattabili: Problemi trattabili e problemi intrattabili. Problemi NP-completi e algoritmi di approssimazione. Approssimazione per il problema del vertex cover. Il problema del Commesso Viaggiatore: soluzioni esatte ed euristiche di approssimazione. 3) Algoritmi randomizzati: Tecniche principali e applicazioni: le diseguaglianze di Markov, i Chernoff bounds, analisi di Quicksort, algoritmi randomizzati per il problema del taglio minimo

L'esame è diviso in una parte di teoria ed una parte pratica. La parte di teoria consiste in una prova scritta che si tiene nelle normali sessione d'esame. La parte pratica può essere svolta in due modalità diverse: - DURANTE IL CORSO: un gruppo di massimo tre studenti implementa tutti gli algoritmi visti nei laboratori e consegna il codice ed i risultati ottenuti. - DOPO IL CORSO: un unico progetto personale. In questo caso il progetto va svolto da soli, non in gruppo.

I criteri di valutazione con cui verrà effettuata la verifica delle conoscenze e delle abilità acquisite sono: 1. Completezza delle conoscenze acquisite; 2. Proprietà della terminologia tecnica utilizzata; 3. Capacità di formalizzare un problema in termini algoritmici 3. Capacità di analizzare correttezza e complessità computazionale di un algoritmo 4. Capacità di implementare un algoritmo in modo coerente con la teoria 5. Capacità di utilizzare un algoritmo per risolvere un problema concreto

Cormen, Thomas H., Introduction to algorithmsThomas H. Cormen ... [et al.]. Cambridge (Mass.): MIT Press, 2009 Cormen, Thomas H.; Colussi, Livio, Introduzione agli algoritmi e strutture datiThomas Cormen ... [et al.]edizione italiana a cura di Livio Colussi. Milano [etc.]: McGraw-Hill, 2010

Il corso ha una sezione dedicata sul Moodle del Dipartimento di Matematica. Il Moodle raccoglierà le dispense del corso, le specifiche dettagliate dei singoli laboratori, gli esercizi e le loro soluzioni. Verrà usato anche per comunicazioni e aggiornamenti da parte dei docenti.