Algoritmi e Strutture Dati (12 cfu)
Obiettivi del Corso:
Il corso ha lo scopo di illustrare le tecniche algoritmiche e le strutture di dati fondamentali per risolvere in modo efficiente problemi computazionali.
Propedeudicità:
Nessuna propedeuticità formale. Raggiunta maturità matematica e conoscenza di un qualunque linguaggio di programmazione imperativo.
Frequenza:
La frequenza delle lezioni è fortemente consigliata.
Programma del Corso:
- Ordini di grandezza, sommatorie, ricorrenze, richiami di calcolo delle probabilità discreta.
- Ordinamento e selezione.
- Strutture dati elementari: pile, code, liste, alberi, grafi, tabelle hash, alberi binari di ricerca, RB alberi.
- Programmazione dinamica
- Algoritmi greedy
- Atrutture dati avanzate: B-alberi, Heap Fibonacci, Heap binomiali, strutture dati per insiemi disgiunti
- Algoritmi elementari su grafi: visite in ampiezza e profondità, ordinamento topologico, componenti connesse
- Algoritmi su grafi avanzati: alberi di copertura minimi: kruskal e prim, cammini minimi con singola sorgente, cammini minimi tra tutte le coppie
-Algoritmi di approssimazione: copertura di vertici, commesso viaggiatore
- Euristiche: la ricerca locale.
Modalità di Esame
Scritto + Attivita' di Laboratorio Il candidato può richiedere di sostenere una prova orale integrativa (su appuntamento da richiedersi per email)
Per tutto ciò che riguarda l'attività di laboratorio rivolgersi a Francesco Strappaveccia (francesco.strappaveccia@gmail.com).
Libro di Testo
Introduzione agli Algoritmi e Strutture Dati. Terza Edizione
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein
McGraw-Hill
Dispense:
Lezioni di algoritmi e strutture dati
V. Maniezzo, L. Margara 2003
ISBN 88-371-1366-8