Algoritmia (ALG)

Ampliar el abanico de técnicas algorítmicas y profundizar en sus fundamentos teóricos. Profundizar en el diseño y evaluación de los algoritmos. Presentar los algoritmos probabilísticos como herramienta de diseño de algoritmos. Presentar herramientas algorítmicas para el tratamiento de problemas computacionalmente difíciles como los algoritmos de aproximación y los métodos basados en búsqueda local. Presentar la ingeniería algorítmica como selección de las estructuras de datos y de las técnicas algorítmicas más adecuadas para la resolución de un problema concreto.

Conocimientos

1. Análisis de algoritmos: Eficiencia, costes, notación asintótica. Recurrencias. Análisis en caso medio.
2. Fundamentos teóricos de los esquemas algorítmicos.
3. Algoritmos avanzados para problemas básicos: ordenación, grafos, hashing.
4. Algoritmos aleatorios: Tipos, técnicas elementales de diseño. Primalidad. Técnicas de análisis.
5. Algoritmos de aproximación: Concepto de aproximación. Eficiencia versus calidad. Técnicas de análisis y de diseño.
6. Métodos basados en búsqueda local: Búsqueda local y variaciones. Evaluación experimental.
7. Metaheurísticas: métodos para la solución aproximada de problemas de optimización combinatorica y continua

Habilidades

1. Ser capaz de usar técnicas avanzadas de diseño y análisis de algoritmos.
2. Saber razonar sobre la corrección y la eficiencia de algoritmos probabilísticos.
3. Conocer algunos algoritmos clásicos para problemas fundamentales.
4. Saber identificar los componentes más relevantes de un problema y seleccionar la técnica algorítmica más adecuada.
5. Ser capaz de escoger los tipos de datos más adecuados para mejorar la eficiencia de una solución algorítmica.

Competencias

1. Capacidad para el razonamiento crítico y lógico-matemático.
2. Capacidad para resolver problemas aplicando los métodos de la ciencia y la ingeniería.
3. Capacidad para diseñar sistemas, componentes o procesos que se ajusten a unas necesidades, usando los métodos, técnicas y herramientas más adecuadas en cada caso.
4. Capacidad de abstracción. Capacidad para enfrentarse a problemas nuevos recurriendo conscientemente a estrategias que han resultado útiles en problemas resueltos anteriormente.
5. Capacidad para estudiar de diversas fuentes, identificando cuándo la información recibida en clase no es suficiente y buscando información complementaria.
6. Capacidad para relacionar y estructurar información de diversas fuentes, para integrar ideas y conocimientos.
7. Capacidad para transmitir ideas efectivamente de forma escrita.
8. Disposición y capacidad para actualizarse a lo largo de la carrera profesional, respecto a conocimientos, procedimientos y técnicas.

Las clases se dividen en dos tipos: sesiones de teoría y sesiones de problemas. En media, la teoría ocupa tres horas semanales y los problemas las otras dos horas. El profesor adaptará la repartición de estas horas de la forma que mejor se ajuste al temario.

Las sesiones de teoría son clases de tipo magistral en las que el profesor aporta nuevos conceptos o nuevas técnicas conjuntamente con ejemplos que los motiven o ilustren.

Las clases de problemas tienen como objetivo desarrollar ejercicios y se basan en la participación activa de los alumnos. Los profesores proponen los problemas por adelantado. La finalidad es que los alumnos presenten el trabajo hecho y que se discutan las diversas soluciones y/o alternativas.

Aportaciones por escrito a las clases de problemas (Pro). Examen Final (Fin).

La nota final se calcula de acuerdo con la fórmula

max(Fin, 0.7 * Fin + 0.3*Pro).

• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.
• Jon Kleinberg, Éva Tardos Algorithm design, Pearson/Addison-Wesley, 2006.
• Michael Mitzenmacher, Eli Upfal Probability and computing : randomized algorithms and probabilistic analysis, Cambridge University Press, 2005.
• Vijay V. Vazirani Approximation algorithms, Springer, 2003.
• Holger H. Hoos, Thomas Stützle Stochastic local research : foundations and applications, Morgan Kaufmann Publishers, 2005.

• FERRI, F. J., ALBERT, J. V., MARTÍN, G. Introducció a l'anàlisi i disseny d'algorismes, Universitat de València, 1998.
• MOTWANI, R. i RAGHAVAN, P. Randomized Algorithms, Cambridge University Press, 1995.
• Steven S. Skiena The Algorithm design manual, TELOS--the Electronic Library of Science, 1998.
• Michael R. Garey, David S. Johnson Computers and intractability : a guide to the theory of NP-Completeness, W.H. Freeman, 1979.
• Zbigniew Michalewicz, David B. Fogel How to solve it : modern heuristics, Springer,, 2004.

Conocimientos básicos sobre análisis y diseño de algoritmos