Algoritmi e Strutture Dati (12 cfu) A—L


Orario Lezioni:
Lunedì: 9-11 Aula A
Mercoledì: 14-17 Aula A
Venerdì: 15-17 Aula A

Orario Laboratorio:
Gruppo AL: Giovedì dalle 10 alle 13, Laboratorio Vela

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 alla Dottoressa Greta Sasso.

Libro di Testo
Introduzione agli Algoritmi e Strutture Dati. Terza Edizione
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein
McGraw-Hill