Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Scienze
INFORMATICA
Insegnamento
ALGORITMI AVANZATI
SCP8084820, A.A. 2019/20

Informazioni valide per gli studenti immatricolati nell'A.A. 2019/20

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INFORMATICA
SC1176, ordinamento 2014/15, A.A. 2019/20
N0
porta questa
pagina con te
Crediti formativi 6.0
Tipo di valutazione Voto
Denominazione inglese ADVANCED ALGORITHMS
Sito della struttura didattica http://informatica.scienze.unipd.it/2019/laurea_magistrale
Dipartimento di riferimento Dipartimento di Matematica
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA
Corso singolo È possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile MICHELE SCQUIZZATO INF/01

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Discipline Informatiche INF/01 6.0

Organizzazione dell'insegnamento
Periodo di erogazione Secondo semestre
Anno di corso I Anno
Modalità di erogazione frontale

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
LEZIONE 6.0 48 102.0

Calendario
Inizio attività didattiche 02/03/2020
Fine attività didattiche 12/06/2020
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2014

Syllabus
Prerequisiti: 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.
Conoscenze e abilita' da acquisire: 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.
Modalita' di esame: 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.
Criteri di valutazione: 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
Contenuti: 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
Attivita' di apprendimento previste e metodologie di insegnamento: 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.
Eventuali indicazioni sui materiali di studio: 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.
Testi di riferimento:
  • Cormen, Thomas H., Introduction to algorithmsThomas H. Cormen ... [et al.]. Cambridge (Mass.): MIT Press, 2009. Cerca nel catalogo
  • 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. Cerca nel catalogo