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
25/02/201914/06/2019

Tipologia

TipologiaAmbitoSSDCFU
caratterizzanteDiscipline informaticheINF/016


Responsabile Insegnamento

ResponsabileSSDStruttura
Prof. BRESOLIN DAVIDEINF/01Dipartimento di Matematica

Altri Docenti

Non previsti

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 Pensiero Algoritmico è quel processo che permette di analizzare e risolvere problemi computazionali anche molto complessi ad un livello di astrazione indipendente dal particolare linguaggio o sistema informatico che si sta utilizzando. 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, ognuno dei quali affronta un problema reale e lo risolve seguendo l'approccio del pensiero algoritmico. 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.

Introduzione al pensiero algoritmico. Grafi: nozioni di base e 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. Problemi trattabili e problemi intrattabili. Problemi NP-completi e algoritmi di approssimazione. Il problema del Commesso Viaggiatore: soluzioni esatte ed euristiche di approssimazione. Algoritmi ``divide et impera'': algoritmi di clustering. Programmazione dinamica: similarità e allineamento di sequenze.

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, da sviluppare seguendo i cinque passi del Pensiero Algoritmico. In questo caso il progetto va svolto da soli, non in gruppo. Il voto finale è la media aritmetica dei voti delle due parti.

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

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 del Docente.