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

Informazioni valide per gli studenti immatricolati nell'A.A. 2018/19

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INFORMATICA
SC1176, ordinamento 2014/15, A.A. 2018/19
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/2018/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 DAVIDE BRESOLIN 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 25/02/2019
Fine attività didattiche 14/06/2019

Commissioni d'esame
Nessuna commissione d'esame definita

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 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.
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, 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.
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: 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.
Attivita' di apprendimento previste e metodologie di insegnamento: 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.
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 del Docente.
Testi di riferimento:
  • 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
  • Cormen, Thomas H., Introduction to algorithmsThomas H. Cormen ... [et al.]. Cambridge (Mass.): MIT Press, 2009. Cerca nel catalogo

Didattica innovativa: Strategie di insegnamento e apprendimento previste
  • Laboratory
  • Problem based learning
  • Case study
  • Working in group
  • Problem solving
  • Flipped classroom
  • Files e pagine caricati online (pagine web, Moodle, ...)

Didattica innovativa: Software o applicazioni utilizzati
  • Moodle (files, quiz, workshop, ...)