Corso di: Algoritmi & Sperimentazioni (CFU 6+3)

Laurea in Informatica (ind. S.T.I.S.I)

Anno accademico: 2002-2003

Docenti: Nello BALOSSINO, Ferruccio DAMIANI

INDICE

• Obiettivi del corso
• Prerequisiti del corso
• Modalita' d'esame
• Libri di testo
• Programma dettagliato del corso
• Lucidi
• Esercitazioni
• (Alcuni) testi degli scritti precedenti

Obiettivi del corso

Il corso ha lo scopo di fornire gli strumenti metodologici di base per il progetto, l'analisi ed il confronto di algoritmi e di introdurre alcuni algoritmi e strutture dati fondamentali.

Prerequisiti

Contenuti dei corsi di "Programmazione I & Laboratorio" e "Programmazione II & Laboratorio".

Modalità d'esame

L'esame si compone di due parti: una discussione del progetto di laboratorio e una verifica scritta sui contenuti delle lezioni.

Il voto d'esame sara' la media del punteggio conseguito nelle due parti.

Libri di testo

• per le lezioni in aula:
  T.H. Cormen, C.E. Leiserson, R.L. Rivest.
  "Introduzione agli Algoritmi" (volumi 1, 2, e 3).
  Jackson Libri.
• per le sperimentazioni in laboratorio:
  J. R. Hubbard.
  Strutture dati in Java.
  McGraw-Hill.

Programma dettagliato del corso

• Strutture dati avanzate
  • Heap, code con prioritą.
  • Alberi, grafi.
  • Insiemi disgiunti.
• Introduzione alle tecniche di progetto e nozioni di complessitą degli algoritmi.
  • Analisi nel caso peggiore e nel caso medio.
  • Ordine di grandezza delle funzioni.
  • Notazione asintotica.
  • Metodi per risolvere le equazioni di ricorrenza: metodo iterativo e metodo principale.
• Algoritmi di ordinamento e selezione.
  • Algoritmi "Divide et Impera": mergesort, quicksort, heapsort.
  • Counting sort.
  • Selezione con tempo medio lineare.
• Algoritmi "Greedy".
  • Minimo albero di copertura di un grafo pesato.
  • Camminini minimi su grafi pesati.
  • Selezione di attivitą.
  • Codice di Huffman.
• Algoritmi di visita sui grafi.
  • Visita in ampiezza e in profonditą.
  • Applicazione degli algoritmi di visita: componenti fortemente connesse, ordinamento topologico.

Lucidi (ATTENZIONE: i lucidi rappresentano solo una GUIDA ALLO STUDIO, essi NON SONO SOSTITUTI del libro di testo e delle lezioni)

Testi degli esercizi proposti a lezione

(Alcuni) testi degli scritti precedenti