Algoritmi e Strutture Dati

e Laboratorio

 

Emanuela Merelli

 Corso di Laurea in Informatica - Università di Camerino
a.a. 2003-2004 -- Vecchio Ordinamento 5 CFU

Progettazione di algoritmi 
Tecniche di progettazione
Analisi di algoritmi
cap. 1,2,3,4

Algoritmi di Ordinamento

Heapsort
Quicksort
Sorting in Linear Time
cap. 6,7,8

Strutture Dati
Elementari (code,pile,liste alberi)
Hash Tables
Alberi binari di ricerca
cap. 10,11,12
Tecniche avanzate di analisi e progettazione 
Programmazione dinamica
Greedy Algorithms
cap. 15,16

Strutture Dati avanzate
B-Trees
Binomial Heaps
Fibonacci Heaps
cap.18,19,20

Algoritmi su grafo
Minimum Spanning Trees
Single-Source Shortest Paths
Maximum Flow
cap.22,23,24,26

String Matching
The naive string-matching algorithm
The Rabin-Karp algorithm
The Knuth-Morris-Pratt algorithm
cap.32

Cenni alla Teoria della Computabilità e Complessità Computazionale
Algoritmi e Macchina di Turing
Analisi e valutazione della complessità degli algoritmi, Analisi asintotica
Problemi trattabili e intrattabili, 
Classi di problemi P e NP
cap. 34

Algoritmi di approssimazione
Metodi di approssimazione
cap.35

 

Libri di testo:

  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to algorithms, The MIT Press, seconda edizione. Capitoli: 1,2,3,6,7,8,10,11,12,15,16,18,19,20,22,23,24,26,32,34,35, Appendix B.4 e B.5
  2. L. Margara, V. Maniezzo, Lezioni di algoritmi, Pitagora 2002.
  3. R. Sedgewick, Algoritmi in Java, McGrawHill 2003, terza edizione