Home » Archivo » Archvio 2009 » Computabilità e algoritmi (Mod. B) - 2009/2010

Laurea Magistrale

Salta il menu di secondo livello

Computabilità e algoritmi (Mod. B) - 5 CFU - A.A. 2009/2010

Insegnante

Prof. Livio Colussi

Periodo

I anno - 2 trimestre | 11/01/2010 - 12/03/2010

Curriculum:

Ore: 32 Frontali, 0 Laboratorio, 8 Esercizi

Torna su ▲

Programma del Corso

Algoritmi su grafi (Capitolo 6 del testo di riferimento). Visita in ampiezza e visita in profondità. Ordinamento topologico. Componenti fortemente connesse. Alberi di connessione minimi. Cammini minimi: algoritmi di Bellman-Ford e di Dijkstra. Flusso massimo: Ford-Fulkerson.

Algoritmi su stringhe. Preelaborazione fondamentale. Algoritmi basati su confronti: di Knuth Morris e Pratt, di Boyer e Moore e di Yao Corasich. Algoritmi seminumerici: Algoritmo ShiftAnd e algoritmo Fingerprint di Rabin e Karp. Alberi dei suffissi e algoritmo di Ukonnen per la loro costruzione in tempo lineare.

Algoritmi di geometria computazionale. Rappresentazione degli oggetti geometrici. La tecnica di "swapping". Calcolo dell'involucro convesso.

Introduzione agli algoritmi randomizzati e alle tecniche di progetto di algoritmi randomizzati.

Prerequisiti: Un primo corso di Algoritmi e Strutture Dati.

Propedeuticità:

Ausili Didattici: Dispense preparate dal docente.

Testi di Riferimento: Introduzione agli Algoritmi e Strutture Dati. (seconda edizione)
T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
Editore McGraw-Hill Italia.

Torna su ▲