Dettagli sull'Insegnamento per l'A.A. 2013/2014
Nome:
Algoritmi e Strutture Dati II / Algorithms and Data Structures II
Informazioni
Crediti:
: Laurea Magistrale in Informatica 6 CFU (b)
Erogazione:
Laurea Magistrale in Informatica 1° anno curriculum SDRC Obbligatorio
Laurea Magistrale in Informatica 1° anno curriculum ASSC Obbligatorio
Laurea Magistrale in Informatica 1° anno curriculum Generale Obbligatorio
Lingua:
Italiano
![[info]](img/info16.png)
Prerequisiti
CONOSCENZE : fondamenti di programmazione, matematica discreta, algoritmi e strutture dati, architetture degli elaboratori, lettura e comprensione in lingua inglese
CAPACITA' : capacità di integrazione dello studio in aula con lo studio personale, capacità di interazione con il docente in aula in modo da originare momenti comuni di confronto
Obiettivi
Conoscenza di tecniche algoritmiche avanzate, capacità di individuazione, formalizzazione e risoluzione di problemi di ottimizzazione, concetto di approssimazione, capacità di classificazione di problemi in base al loro grado di approssimabilità, capacità di collaborazione per la realizzazione progetti applicativi di gruppo
Sillabo
- Richiami di complessità ed intrattabilità. Problemi di ottimizzazione. Algoritmi di approssimazione.
- Tecniche algoritmiche: greedy.
- Tecniche algoritmiche: ricerca locale e programmazione dinamica.
- Tecniche di programmazione lineare: metodo dell'arrotondamento e metodo del primale-duale.
- Schemi di approssimazione polinomiali e pienamente polinomiali.
- Risultati negativi di approssimabilità e tecnica del Gap. Classi di complessità per problemi di ottimizzazione e loro contenimenti
Descrittori di Dublino
Alla fine del corso, lo studente dovrebbe
-
Acquire knowledge of advanced algorithmic techniques for NP-Hard optimization problems. In particular, the student will
have mastery command of main algorithmic (approximation) techniques like greedy, local search, dynamic programming, linear programming: rounding and primal-dual methods, Polynomial Time Approximation Schemes (PTAS) and Fully Polynomial Time Approximation Schemes (FPTAS). Moreover the student will acquire knowledge on negative approximation results and gap technique, and therefore on the complexity classes for optimization problems.
-
Acquire the ability of abstracting models and formal algorithmic problems from real computational problems, understanding the degree of approximability and designing efficient algorithmic solutions.
-
Acquire autonomy in individuating, formalizing and understanding the degree of approximability of real computational problems and identify independently their most efficient solutions.
-
Being able to understand complex algorithms solutions and to formal proving performances of their algorithmic solutions for complex computational problems.
-
The course aims to develop in graduate students competencies and abilities necessary in their future studies and/or works, especially with respect to doctoral studies and in general to any research activity on algorithmic topics.
Testi di riferimento
- Vijay V. Vazirani, Approximation Algorithms , Springer. 2001. ISBN: 3-540-65367-8
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation , Springer. 1999. ISBN: 3-540-65431-3
Modalità d'esame
Prova scritta ed un'eventuale discussione orale sulla prova scritta
Aggiornamenti alla pagina del corso
Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:
Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.
Ultimo aggiornamento delle informazioni sul corso: 19 marzo 2014, 16:51
English version
sad
strutture.univaq