| | | corso | | | | |
Algoritmica II
Codice: | 316AA | Crediti: | 9 | Semestre: | 1 | Sigla: | ALG2 | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Roberto Grossi
Tel. 0502212793Prerequisiti
- Introduction to algorithms.
- Programming.
- Discrete math.
Obiettivi di apprendimento
In questo corso studieremo, progetteremo e analizzeremo soluzioni algoritmiche e strutture di dati avanzate
per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato, quali interi, stringhe,
punti (geometrici), alberi, grafi.
Questo corso costituisce un naturale approfondimento e ampliamento delle
conoscenze di base apprese nel percorso della laurea triennale.
Il suo syllabus è organizzato per ambiti
applicativi, al fine di contestualizzare le tecniche studiate nella realizzazione di software efficiente per essi,
e così da consentire adattamenti e specializzazioni di anno in anno che si renderanno necessari e/o
opportuni.
Importante: il corso si terrà in inglese e affronterà tematiche avanzate, per cui è altamente consigliata la frequenza.
English Description
In this course we will study, design and analyze 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. This course deepens and extends the algorithmic notions of students.
The
syllabus is structured to highlight the applicative scenarios in which the studied algorithms and data
structures can be successfully applied. The level of detail with which each argument will be dealt with can
change year-by-year, and will be decided according to requests coming from other courses and/or specific
issues arising in, possibly novel, applicative scenarios.
The lectures will be given in English and the course will deal with complex problems, thus it is highly recommended to attend them.
Programma
- Accesso ai dati e loro compressione
- Compressione di testi e di interi
- Strutture di dati randomizzate
- Motori di ricerca: liste invertite
- Memorie gerarchiche
- Modelli di computazione
- Permutazioni e ordinamenti
- Dizionari
- Stringologia
- Array dei suffissi
- Albero dei suffissi
- Algoritmi di pattern matching
- Strutture di dati evolute
- Strutture di dati distribuite
- Analisi competitiva
- Algoritmi on-line
- Problemi "difficili" e loro soluzione
- I problemi NP-hard
- Algoritmi di approssimazione
- Algoritmi randomizzati