Dettagli sull'Insegnamento per l'A.A. 2014/2015

Le informazioni che state leggendo si riferiscono all'anno accademico 2014/2015. Per questo molti collegamenti non sono disponibili e i dati potrebbero essere incompleti. Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo. Per consultare le informazioni relative ad altri anni accademici, usa la lista in fondo a questa pagina.

A. Accademico:

2014/2015

Nome:

Ingegneria degli Algoritmi / Algorithm Engineering

Tipo:

Corso singolo

Informazioni

Codice:

I0665

SSD:

ING-INF/05

Crediti:

: Laurea Magistrale in Ingegneria Informatica e Automatica 9 CFU (b)

Periodo:

2^nd semester

Erogazione:

Laurea Magistrale in Ingegneria Informatica e Automatica 1^st anno curriculum Generale Compulsory

Lingua:

Italiano

Docenti:

Daniele Frigioni

Prerequisiti

Conoscenza delle tecniche di programmazione di base con esperienza di programmazione in un qualsiasi linguaggio. Conoscenza delle strutture di dati elementari come array e liste, e delle principali tecniche per la loro rappresentazione nella memoria RAM di un elaboratore elettronico. Familiarità con dimostrazioni e concetti matematici di base (induzione e dimostrazioni per assurdo). Conoscenza di nozioni elementari di probabilità.

Obiettivi

Il corso si propone di fornire allo studente una conoscenza approfondita delle principali tecniche per il progetto di strutture di dati ed algoritmi efficienti per la soluzione di problemi classici dell'informatica e per l'analisi sia teorica che sperimentale delle loro prestazioni computazionali. Il corso introduce le tematiche di base dell'ingegneria degli algoritmi, il cui obiettivo è quello di approfondire gli aspetti prestazionali legati allo sviluppo del software, coniugando il progetto e l'analisi teorica di algoritmi e strutture dati efficienti con la loro effettiva codifica in un linguaggio di programmazione reale e la loro validazione sperimentale.

Sillabo

Il processo dell'ingegneria degli algoritmi. Introduzione alle nozioni di algoritmo e struttura dati. Un esempio giocattolo: i numeri di Fibonacci. [1] cap. 1.
Modelli di calcolo e metodologie di analisi. I modelli elementari di calcolo. La nozione di complessità asintotica e le notazioni O, Omega e Theta. Delimitazioni inferiori e superiori. Metodi di analisi. Analisi di algoritmi ricorsivi. [1] cap. 2 (esclusi 2.7 e 2.8), [2] cap. 1 (esclusi 4.4 e 5.4).
Strutture di dati elementari. Tecniche per rappresentare collezioni di oggetti: array, liste concatenate, pile, code, alberi. [1] cap. 3.
Il problema dell’ordinamento. Delimitazione inferiore al numero di confronti per il problema dell’ordinamento. Metodi di ordinamento: SelectionSort, InsertionSort, BubbleSort, HeapSort, MergeSort, QuickSort, IntegerSort, BucketSort, RadixSort. [1] cap. 4.
Alberi di ricerca. Alberi binari di ricerca. Il problema del bilanciamento. Alberi AVL. Alberi 2-3. [1] cap. 6 (esclusi 6.3, 6.5 e 6.6).
Tabelle Hash. Tabelle ad accesso diretto. Tabelle Hash. Risoluzione delle collisioni. [1] cap. 7, [2] cap. 11 (escluso 11.5).
Code con priorità. Definizione e rappresentazione tramite strutture di dati elementari. Heap binari. Heap binomiali. [1] cap. 8 (escluso 8.3).
Grafi e visite di grafi. Definizioni. Tecniche di rappresentazione in memoria di un grafo. Algoritmi di visita in ampiezza e profondità. Componenti connesse di un grafo non orientato. Componenti fortemente connesse di un grafo orientato. [1] cap. 12.
Minimo albero ricoprente. Proprietà del minimo albero ricoprente. Tagli e cicli. Algoritmo greedy. Algoritmo di Kruskal. Algoritmo di Prim. [1] cap. 13 (escluso 13.2.1 e 13.4).
Cammini minimi. Cammini minimi e distanze in un grafo. La tecnica del rilassamento. Algoritmo di Bellmann-Ford. Algoritmo per grafi diretti aciclici. Algoritmo di Djikstra. Algoritmo di Floyd-Warshall. [1] cap. 14.
Teoria della NP-completezza. Complessità di problemi decisionali. Le classi di complessità P e NP. Problemi NP-completi. Algoritmi di approssimazione: copertura di vertici e orientazione di grafi. [2] cap. 34.
Ingegneria degli algoritmi. Definizione e metodologie di base. Metodologie dell'ingegneria degli algoritmi: analisi dei requisiti, valutazione difficoltà, progetto algoritmo, analisi teorica, implementazione, analisi sperimentale e ingegnerizzazione. Un caso di studio: il problema dei cammini minimi. Tecniche di speed-up per cammini minimi: BiDirectional Dijkstra, ALT, Reach, ALT+Reach, Arc Flags. [3] cap. 1, più materiale fornito dal docente.

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

Have profound knowledge of basic concepts of algorithm engineering; has profound knowledge and understanding of how these concept impact on the performance of a computer; have profound knowledge of advanced algorithms and data structures, complexity analysis of algorithms; knowledge of the practical applications scenarios of algorithms and data structures; knowledge of the algorithm engineering process and how it contribute in bridging the gap between classic algorithm theory and implementation of algorithms in practice.
Have ability to relate different topics; ability to solve algorithmic problems never faced in classroom, but solvable through logic deductions and reasoning; ability in analyzing the computational complexity of algorithms; ability to complement algorithmic theory by the benefits of experimentation driven by concrete applications; ability in realistic modelling, design, analysis, robust and efficient implementations, and careful experiments.
Have ability to critically analyze and synthesize algorithm engineering concepts; ability to apply these concepts to real world algorithmic problems coming from real application scenarios; interest in design and pragmatic implementation aspects of algorithms and their experimentation.
Demonstrate ability to understand and explain the knowledge acquired by the course.
Have capacity to read and understand other texts/papers on related topics using notions learnt by the course and understand their applications.

Testi di riferimento

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e Strutture Dati (seconda edizione) , McGraw-Hill. 2008 . Testo di riferimento
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli Algoritmi e Strutture Dati (terza edizione) , McGraw-Hill. 2005. Testo di approfondimento
Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano, Progetto di Algoritmi e Strutture Dati in Java , McGraw-Hill . 2007 . Testo di approfondimento

Modalità d'esame

Prova unica

Risorse Internet

Aggiornamenti alla pagina del corso

Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:

Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.

Ultimo aggiornamento delle informazioni sul corso: 02 ottobre 2014, 16:34