Docente

Prof. Carla Piazza

Indirizzo e-mail

carla.piazza@uniud.it

Indirizzo Pagina Web Personale

http://www.dimi.uniud.it/piazza

Crediti

12 CFU

Finalità e obbiettivi formativi

Il corso si propone di introdurre ai fondamenti della teoria degli algoritmi, delle strutture dati e all'analisi della complessità computazionale di programmi. Il principale obiettivo del corso e' familiarizzare lo studente con le principali problematiche e tecniche relative al disegno e alla progettazione di algoritmi. Ci si propone inoltre di introdurre i metodi di base utilizzati per stabilire la complessità di programmi e i criteri utilizzati per scegliere e progettare strutture dati.

Dopo aver superato l'esame si ritiene che lo studente sia in grado di risolvere algoritmicamente problemi classici e scegliere motivatamente le strutture dati adatte ad ottenere soluzioni computazionalmente efficienti. Sia in grado di porre limiti superiori sufficientemente precisi e indipendenti dall'architettura alla complessità computazionale di programmi di media difficoltà. Conosca i più importanti problemi e algoritmi classici del campo nonché le più importanti e utilizzate tecniche di analisi della complessità e di strutturazione dei dati.

Programma

1. Introduzione e nozioni preliminari

Introduzione. Elementi di logica e teoria degli insiemi. Alberi e grafi. Matematica discreta e analisi asintotica. Modelli di calcolo per la determinazione della complessità degli algoritmi. Problemi ricorsivi e aspetti algoritmici.

2. Algoritmi di ricerca e ordinamento

Algoritmi primitivi di ordinamento e ricerca: selection-sort, insertion-sort, bubble-sort, heap-sort. Algoritmi ricorsivi: quick-sort, merge-sort. Analisi della complessità e limiti inferiori. Algoritmi lineari non basati sul confronto: counting-sort, radix-sort, bucket-sort. Determinazione dell'elemento medio.

3. Strutture dati

Strutture dati primitive: liste, pile, code, heap. Algoritmi e strutture dati per la gestione e manipolazione di insiemi: tabelle hash, alberi di ricerca, bilanciamento, red-black alberi e B-alberi. Algoritmi e strutture dati per il problema Union-Find.

4. Algoritmi sui grafi

Tecniche di rappresentazione di grafi orientati e e non orientati. Algoritmi di visita in ampiezza e profondità. Algoritmi di visita su alberi. Calcolo delle componenti fortemente connesse. Algoritmi per la determinazione di topological-sort, minimum spanning tree (Prim e Kruskal), cammino minimo da una sorgente (Dijkstra, Bellmann-Ford) cammini minimi da sorgenti multiple (Floyd-Warshall, Johnson).

Prerequisiti

E’ utile che lo studente abbia buona padronanza con i contenuti dei corsi del I anno del corso di Laurea Triennale in Informatica/Tecnologie Web e Multimediali, con particolare riferimento ai corsi di Matematica Discreta, Analisi Matematica, Programmazione, Architettura degli Elaboratori.

Bibliografia

1.     Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., Introduction to Algorithms, MIT Press, Third edition, 2009.

2.     Altri testi utili/Further useful textbooks:

1.     A. Bertossi, A. Montresor. Algoritmi e Strutture Dati, 2/ed, Città Studi Edizioni, 2010.

2.     C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e Strutture Dati, 2/ed, McGraw-Hill, 2007.

3.     P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Addison-Wesley Pearson, 2006.

4.     Aho A.V., Hopcroft J.E., Ullman J.D., Data Structures and Algorithms, Addison-Wesley, 1983.

5.     Aho A.V., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

Modalità d'esame

L’esame consta di una parte scritta e una orale.

**********************************************************************************************************

Aims

The course is an introduction to the foundations of the theory of algorithms and data structures, as well as to the analysis of the computational complexity of programs. The course main aim is to familiarize the student with the most important issues and techniques relative to the algorithm design and project. Moreover the basic methods employed to establish the computational complexity of programs and the criteria used to choose and design data structures are introduced.

After the exam the student should be able to solve algorithmically classical problems and justify the choice for data structures capable to support efficient solutions as far as the computational complexity is concerned. Also, the student should be able to determine with sufficient precision architecture-independent upper bounds to the computational complexity of programs of medium difficulty. Finally, the most important problems and classical algorithms should be known and the most used techniques for the complexity analysis and the structuring of data should be familiar.

Program

1. Introduction and preliminary notions
   Introduction. Elements of logic and set theory. Trees and graphs. Discrete mathematics and asymptotic analysis. Models of computation to determine the computational complexity of algorithms. Recursive problems and algorithmic aspects.
2. Sorting and searching algorithms
   Basic sorting and searching algorithms: selection-sort, insertion-sort, bubble-sort, heap-sort. Recursive algorithms: quick-sort, merge-sort. Complexity analysis and lower bounds. Non Linear algorithms not based on comparison: counting-sort, radix-sort, bucket-sort. Order statistics.
3. Data structures
   Basic data structures: lists, stacks, queues, heaps. Algorithms and data structures for dynamic sets: hash tables, search trees, balancing, red-black trees and B-trees. Algorithms and data structures for Union-Find problem. Elements relative to self-adjusting data structures.
4. Graph algorithms
   Representation techniques for oriented and non-oriented graphs. Depth-first and breadth-first visits. Tree visits. Determination of the strongly connected components. Topological-sort, minimum spanning tree (Prim e Kruskal), single-source shortest paths (Dijkstra, Bellmann-Ford) many-sources shortest paths (Floyd-Warshall, Johnson).

Prerequisites

It is useful for the student to master the contents of the courses of the I year of Informatics/Web Technologies, with particular reference to the courses of Discrete Mathematics, Analysis, Programming, Computer Architectures.

Exam

The exam is both written and oral. Upon agreement with the teacher, the exam can be given in English.