Codice: | 283AA | Crediti: | 6 | Semestre: | 1 | Sigla: | ALE | |
Settore disciplinare: | INF/01 - Informatica |
In questo corso studieremo, progetteremo e analizzeremo (con modelli teorici e attraverso risultati sperimentali) soluzioni algoritmiche e strutture dati avanzate per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato? quali interi, stringhe, punti (geometrici), alberi, grafi. Il progetto interesserà alcuni modelli di calcolo? RAM, 2-level memory, cache-oblivious, streaming? al fine di ottenere soluzioni algoritmiche le cui valutazioni teoriche ben riflettono le loro prestazioni reali, poiché tengono conto delle caratteristiche architetturali e della gerarchia di memoria dei moderni PC. Ogni lezione seguirà un approccio problem-driven che inizia considerando un problema reale, lo astrae in modo combinatorio, e poi procede al progetto e analisi di soluzioni algoritmiche tese a minimizzare l'uso di alcune risorse computazionali quali: tempo, spazio, communicazione, I/O, etc. Alcune soluzioni viste in classe saranno discusse anche a livello sperimentale al fine di introdurre degli strumenti appropriati per l' ingegnerizzazione e il tuning del codice.
Per ulteriori dettagli consultare la pagina web del corso: http://www.cli.di.unipi.it/doku/doku.php/magistraleinformaticanetworking/ae/start
Objectives
In this course we will study, design and analyze (theoretically and experimentally) advanced algorithms and data structures for the efficient solution of combinatorial problems involving all basic data types, such as integers, strings, (geometric) points, trees and graphs. These algorithmic tools will be designed and analyzed in several models of computation— such as RAM, 2-level memory, cache-oblivious, streaming— in order to take into account the architectural features and the memory hierarchy of modern PCs.
Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces algorithmic solutions aimed at minimizing the use of some computational resources like time, space, communication, I/O, etc. Some of these solutions will be discussed at an experimental level, in order to introduce proper engineering and tuning tools for algorithmic development.
For further details please check the web page:
http://www.cli.di.unipi.it/doku/doku.php/magistraleinformaticanetworking/ae/start
Ore lezione: | 48 |