Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
INGEGNERIA
INGEGNERIA INFORMATICA
Insegnamento
DATI E ALGORITMI 2
IN14112348, A.A. 2012/13

Informazioni valide per gli studenti immatricolati nell'A.A. 2012/13

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INGEGNERIA INFORMATICA
IN0521, ordinamento 2009/10, A.A. 2012/13
N0
porta questa
pagina con te
Crediti formativi 9.0
Tipo di valutazione Voto
Denominazione inglese DATA STRUCTURES AND ALGORITHMS 2
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA
Corso singolo NON è possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile GEPPINO PUCCI INF/01

Mutuazioni
Codice Insegnamento Responsabile Corso di studio
IN14112348 DATI E ALGORITMI 2 GEPPINO PUCCI IN0527

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Ingegneria informatica ING-INF/05 9.0

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

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
LEZIONE 9.0 72 153.0

Calendario
Inizio attività didattiche 01/10/2012
Fine attività didattiche 26/01/2013
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2009

Commissioni d'esame
Commissione Dal Al Membri
9 A.A. 2017/2018 01/10/2017 30/09/2019 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
FANTOZZI CARLO (Supplente)
VANDIN FABIO (Supplente)
8 A.A. 2015/2016 10/01/2017 15/03/2017 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
VANDIN FABIO (Supplente)
7 A.A. 2016/2017 01/10/2016 15/03/2018 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
FANTOZZI CARLO (Supplente)
VANDIN FABIO (Supplente)
6 A.A. 2015/2016 01/10/2015 15/03/2017 BILARDI GIANFRANCO (Presidente)
FANTOZZI CARLO (Membro Effettivo)
PESERICO STECCHINI NEGRI DE SALVI ENOCH (Supplente)
VANDIN FABIO (Supplente)
5 A.A. 2014/2015 01/10/2014 15/03/2016 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
AGOSTI MARISTELLA (Supplente)
BILARDI GIANFRANCO (Supplente)
COMIN MATTEO (Supplente)
DE POLI GIOVANNI (Supplente)
FANTOZZI CARLO (Supplente)
FERRARI CARLO (Supplente)
PIZZI CINZIA (Supplente)
SATTA GIORGIO (Supplente)
01/10/2013 15/03/2015 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
BILARDI GIANFRANCO (Supplente)
DE POLI GIOVANNI (Supplente)
FANTOZZI CARLO (Supplente)
FERRARI CARLO (Supplente)
PINI MARIA SILVIA (Supplente)
PIZZI CINZIA (Supplente)
3 2012 01/10/2012 30/09/2013 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
BILARDI GIANFRANCO (Supplente)
FANTOZZI CARLO (Supplente)

Syllabus
Prerequisiti:
Risultati di apprendimento previsti: Competenze di problem-solving. Capacità di affrontare il processo di risoluzione di un problema computazionale con strumenti rigorosi basati su alcuni paradigmi algoritmici generali. Conoscenza di primitive algoritmiche notevoli. Comprensione del concetto di problema intrattabile.
Contenuti: Paradigmi algoritmici: progetto e analisi. Casi di studio notevoli. Teoria dell'intrattabilità computazionale.
Programma: 1. Introduzione agli argomenti del corso. Richiami: definizione di problema e algoritmo; modello computazionale; modello di costo; uso dello pseudolinguaggio

2. Il paradigma divide-and-conquer: Caratteristiche generali e strumenti per l'analisi;
Casi di studio:
Moltiplicazione di interi: algoritmo di Karatsuba;
Moltiplicazione di matrici: algoritmo di Strassen;
Moltiplicazione di polinomi: la Fast Fourier Trasform.


3. Il paradigma dynamic programming: Caratteristiche generali: sottoproblemi ripetuti e tecniche di risoluzione;
Casi di studio:
Algoritmo di Matrix-chain multiplication;
Problemi su stringhe: Longest Common Subsequence.


4. Il paradigma greedy: Problemi risolvibili con l'approccio greedy e tecniche di risoluzione;
Casi di studio:
Il problema della selezione di attività
I codici di Huffman per la compressione dei dati.


5. La teoria della NP-Completezza: Classi di complessità P, NP, co-NP e NPC; Tecniche di riducibilità in tempo polinomiale e riduzioni notevoli.

Testi di riferimento: T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein., Introduction to Algorithms (Third Edition). Boston: MIT Press, 2009.
Metodi didattici:
Metodi di valutazione: Esame scritto diviso in due parti: a) teoria e b) risoluzione di problemi.

Eventuale esame orale.
Altro: Si veda il materiale online sul sito del corso:

http://www.dei.unipd.it/~geppo/DA2