Algoritmi e Strutture Dati

Trasparenze delle Lezioni

• Introduzione al Corso (pdf)
• Algoritmi e Strutture Dati (pdf)
• Analisi della complessita (pdf)
• Esempi di Divide et Impera (pdf)
• Laboratorio del 13/10/2008: Merge sort su vettori di interi, Merge sort su vettori di stringhe, Merge sort con i template.
• Strutture Dati Elementari (pdf)
• Heapsort (pdf)
• Quicksort (pdf)
• Counting Sort, Radix Sort (pdf)
• Hashing (pdf)
• Alberi binari di ricerca (pdf)
• Simulazioni della prima prova in itinere (1) e (2)

Programma del Corso

Gli obiettivi principali del corso sono due: (1) fornire un’introduzione alla programmazione orientata agli oggetti utilizzando il linguaggio C++; (2) dare una panoramica degli algoritmi e delle strutture dati maggiormente utilizzate, fornendo nel contempo le tecniche matematiche necessarie per valutarne la complessità.

• Algoritmi: definizione, complessità, notazione O-grande.
• La programmazione orientata agli oggetti e il C++
• Algoritmi di ordinamento
• Complessità: dividi et impera, equazioni alle ricorrenze.
• Algoritmi e Strutture Dati
• Strutture dati e algoritmi fondamentali: code, pile, liste; ricerca e ordinamento; tabelle di hash; alberi binari.
• Strutture ad albero (alberi binari, B-alberi, ecc.)
• Algoritmi su grafi.
• Applicazioni e argomenti scelti. Es. automi e algoritmi su stringhe.

Prerequisiti

Il programma del corso assume la conoscenza degli argomenti trattati nel corso di Informatica.

Bibliografia

Testo ufficiale: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduzione agli algoritmi e strutture dati, II edizione, McGraw-Hill, 2005. (Ed. Inglese: Introduction to Algorithms, 2nd ed., MIT Press, 2001).

Prima Prova in Itinere: 19/11/2008 (data provvisoria)

Calendario provvisorio delle lezioni/esercitazioni

• 1/10/2008
• 2/10/2008
• 8/10/2008
• 9/10/2008
• 14/10/2008
• 15/10/2008
• 22/10/2008
• 29/10/2008
• 30/10/2008
• 5/11/2008
• 6/11/2008
• 12/11/2008
• 13/11/2008
• 26/11/2008
• 27/11/2008
• 3/12/2008
• 4/12/2008
• 10/12/2008
• 11/12/2008
• 18/12/2008
• 7/1/2009