A.A.  2004-2005


 

ALGORITMI

Prof. Stefano Kasangian



 

Programma

  • Analisi di Algoritmi e Complessità
  • Dimensione dei dati di un problema. Caso pessimo, ottimo e medio. 
  • Ordini di grandezza delle funzioni. 
  • Complessità polinomiale e superpolinomiale.
  • Progetto di Algoritmi 
  • Insertion Sort e Selection Sort. 
  • Divide et impera: Mergesort, Quicksort. 
  • Ricerca binaria su vettore ordinato. 
  • Ordinamento in tempo lineare. 
  • Grafi: rappresentazioni e visite. Ordinamento topologico di un grafo. Algoritmi greedy: Huffman 
  • Strutture Dati Elementari
  • Strutture di base: vettori, liste, code e pile. 
  • Dizionari: realizzazione con vettori e liste. 
  • Code con priorità:Heap e Heapsort. 
  • Alberi binari di ricerca: visita, ricerca, insert/delete. 
  • Alberi bilanciati mediante rotazioni. 
  • Grafi orientati e non orientati. 
  • Rappresentazione di un  grafo con matrice o lista di adiacenza. 
  • Classi di Complessità (corso avanzato)
  • Problemi decisionali, di ricerca e di ottimizzazione.
  • Enumerazione e backtracking.
  • Classi di complessità.
  • Le classi P e NP. 
  • Problemi NP-completi. 
 Lo studente potrà anche optare per un corso avanzato, che comprenderà anche l’argomento “Classi di complessità”

Testi consigliati: 

 T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli algoritmi, Jackson Libri, Milano, 1994] 
 D.Kozen, The  design and analysis of algorythms,Springer 92
 A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorythms,  Addison-Wesley
Dispense, esercizi, download