Responsable: | (-) |
Altres: | (-) |
Crèdits | Dept. |
---|---|
7.5 (6.0 ECTS) | CS |
Responsable: | (-) |
Altres: | (-) |
Ampliar el ventall de tècniques algorismiques i aprofundir en els seus fonaments teòrics. Aprofundir en el disseny i evaluació dels algorismes. Introduïr els algorismes probabilístics com a eina de disseny d'algorismes. Introduïr eines algorismiques pel tractament de problemes computacionalmente difícils com els algorismes d'aproximació i els mètodes basats en cerca local. Introduïr l'enginyeria algorísmica com a selecció de les estructures de dades i de les tècniques algorismiques mes adients per a la resolució d'un problema concret.
Hores estimades de:
T | P | L | Alt | L Ext. | Est | A Ext. |
Teoria | Problemes | Laboratori | Altres activitats | Laboratori extern | Estudi | Altres hores fora d'horari fixat |
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
3,0 | 3,0 | 0 | 0 | 0 | 10,0 | 0 | 16,0 | |||
L'esquema voraç. Fonaments teòrics. Aplicacions.
Programació dinàmica. Fonaments teòrics. Aplicacions. |
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
8,0 | 7,0 | 0 | 0 | 0 | 13,0 | 0 | 28,0 | |||
Camins curts. Algorismes de Bellman-Ford, Floyd-Warshall y Johnson. Algorismes per flux màxim i matchings. Programació Lineal.
|
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
11,0 | 8,0 | 0 | 0 | 0 | 15,0 | 0 | 34,0 | |||
Repàs de probabilitats. Verificació d'identitats polinomials. Algorismes Monte-Carlo i Las Vegas. Amplificació de probabilitat. Test de primalitat. Fites de concentració. Exemples en l'anàlisi d'algorismes aleatoris. Passeig aleatori. Algorismes per la Web.
|
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
9,0 | 6,0 | 0 | 0 | 0 | 10,0 | 0 | 25,0 | |||
Concepte d'aproximació. Eficiència i qualitat. Tècniques d'anàlisi i disseny. Esquemes de aproximació. Límits computacionals a l'aproximabilitat de problemes. Esquemes d'arrodoniment aleatori.
|
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
6,0 | 0 | 4,0 | 0 | 5,0 | 4,0 | 0 | 19,0 | |||
Espai de solucions i de cerca. Els fonaments de la cerca local. Hill Climbing. Variacions probabilístiques de la cerca local: . Metròpolis i Simmulated annealing. Avaluació experimental de rendiment. Cerca local iterada. GRASP: Greedy randomized adaptive search procedures.
|
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
6,0 | 0 | 4,0 | 0 | 5,0 | 4,0 | 0 | 19,0 | |||
Optimització amb colònies de formigues. Algorismes evolutius. Hibridització de meta heurístics amb mètodes exactes. La avaluació experimental de metaheurístiques.
|
Total per tipus | T | P | L | Alt | L Ext. | Est | A Ext. | Total |
45,0 | 26,0 | 8,0 | 0 | 10,0 | 59,0 | 0 | 148,0 | |
Hores addicionals dedicades a l'avaluació | 6,0 | |||||||
Total hores de treball per l'estudiant | 154,0 |
Les classes es divideixen en dos tipus: sessions de teoria i sessions de problemes. En mitjana, la teoria ocupa tres hores setmanals i els problemes les altres dues hores. El professor adaptarà la repartició d'aquestes hores de la forma que millor s'ajusti al temari.
Les sessions de teoria són classes de tipus magistral en les que el professor aporta nous conceptes o noves tècniques conjuntament amb exemples que els motivin o els il¿lustrin.
Les classes de problemes tenen com objectiu desenvolupar exercicis i es basen en la participació activa dels alumnes. Els professors proposen els problemes per avançat. La finalitat es que els alumnes presentin el treball fet i que es discuteixen les diverses solucions i/o alternatives.
Aportacions per escrit a les classes de problemes (Pro). Examen Final (Fin).
La nota final es calcula d'acord amb la fórmula
max(Fin, 0.7 * Fin + 0.3*Pro).
Coneixements basics sobre disseny i anàlisis d'algorismes