Prof. Simone Martini - Dott. Carla Piazza

Scopo del corso č la realizzazione di algoritmi di una certa complessitā, che operano su strutture dati articolate, e la determinazione sperimentale delle relative prestazioni. In questo modo, si intende dare un supporto concreto ai fini di una migliore comprensione delle idee e dei concetti discussi nel corso teorico di Algoritmi e Strutture Dati. Si assume una conoscenza non superficiale del linguaggio di programmazione Pascal, anche se i progetti potranno essere realizzati anche in C, C++, Java, ed altri linguaggi.

· Misura dei tempi di calcolo e confronto fra diversi ordini di complessitā. Stime teoriche dei tempi di calcolo nel caso di semplici algoritmi, notazione O-grande. Misure dei tempi, errore relativo, discussione dei risultati sperimentali. Limiti dell'analisi asintotica e ruolo delle costanti moltiplicative.

· Stima del tempo medio. Generatori di numeri casuali, tempo medio, varianza, intervalli di confidenza.

· Code tuning La regola del 80-20. Tecniche per migliorare l'efficenza di alcuni programmi. Eliminazione delle chiamate di procedura, macroespansione. Valutazione sperimentale.

4. Sperimentazione di algoritmi e strutture dati sviluppati nel corso teorico. Algoritmi di ordinamento; realizzazione di altre strutture dati e algoritmi (da determinare).

L'esame č integrato con il corso di Algoritmi e Strutture Dati. La prova di laboratorio dā luogo ad un giudizio espresso nell'intervallo A(ottimo) - B (buono) - C (sufficiente) - D (insufficiente, prova non superata). La prova consiste nella risoluzione di alcuni esercizi durante l'anno e nella redazione di tre relazioni, in cui devono essere descritti i risultati degli esperimenti assegnati che saranno assegnati. Le relazioni, che devono essere prodotte usando strumenti informatici di scrittura e produzione di tabelle e grafici, saranno valutate anche relativamente all'efficacia della presentazione dei dati sperimentali. Relazioni ed esercizi sono da consegnarsi in date fissate durante l'anno. Alternativamente, č permessa (anche se sconsigliata) la consegna cumulativa di tutti gli elaborati insieme con l'ultima relazione.

S. Martini: appunti disponibili sulla pagina web

Riferimento generale: Cormen et al., Introduction to Algorithms, MIT Press