COMPETENCIAS ESPECÍFICAS

M09CM07 - Seleccionar las técnicas de diseño de algoritmos más apropiadas para la resolución de cada problema.

M09CM08 - Estudiar el coste computacional de un algoritmo.

M09CM09 - Proponer alternativas válidas en función de especificaciones concretas del problema y/o de restricciones en las resoluciones.

M09CM010 - Proponer implementaciones eficaces.

RESULTADOS DE APRENDIZAJE

El alumno deberá conocer las técnicas fundamentales de diseño de algoritmos y ser capaz de elegir las técnicas algorítmicas adecuadas para la resolución de problemas propuestos así como realizar análisis comparativos en función de especificaciones y objetivos. Igualmente deberá ser capaz de diseñar implementaciones eficientes así como estimar y analizar la complejidad computacional de las mismas. Deberá igualmente ser capaz de realizar análisis de costes reales sobre computadora. Finalmente deberá comunicar ideas y resultados relativos a la materia de manera oral y escrita

1. INTRODUCCIÓN: eficiencia de los algoritmos, complejidad espacial y temporal, análisis de algoritmos recursivos, repaso de técnicas básicas.

2. ALGORITMOS DE EXPLORACIÓN: esquema general, búsqueda en profundidad con retroceso, ramificación y poda.

3. BÚSQUEDA INFORMADA: heurísticos y funciones de evaluación, búsqueda óptima, algoritmo A*.

4. ALGORITMOS VORACES: esquema general, algoritmo de Prim, algoritmo de Kruskal, algoritmo de Dijkstra, aplicaciones a problemas tecnológicos

5. PROGRAMACIÓN DINÁMICA: esquema general recursivo e iterativo, el principio de optimalidad, caminos mínimos, aplicaciones a problemas tecnológicos.



PRÁCTICAS DE ORDENADOR

P0.- Selección y verificación del entorno de programación

P1.- Análisis de algoritmos iterativos y recursivos.

P2.- Búsqueda en profundidad y búsqueda en anchura

P3.- Algoritmos de juegos.

P4.- Problemas de optimización: algoritmo A*, algoritmos voraces y programación dinámica.

El contenido teórico se expondrá en clases magistrales siguiendo referencias básicas que figuran en la Bibliografía y el material de uso obligatorio. Estas clases magistrales se complementarán con clases de problemas (prácticas de aula) en los que se propondrá a los alumnos resolver cuestiones y ejercicios en los que se aplicarán los conocimientos adquiridos en las clases teóricas. En los seminarios los alumnos realizarán exposiciones de cuestiones y ejemplos relacionados con el contenido de la asignatura. Además, se realizarán prácticas de ordenador orientadas a la consecución de las competencias de la asignatura.

Evaluación continua:

- Exposiciones en seminarios: 15%

- Resolución algorítmica de problemas: ejercicios individuales entregables y con evaluación escrita (15%) y examen final (45%).

- Trabajo práctico individual (prácticas): informes entregables y prueba adicional de verificación sobre ordenador 25%

Se exige un mínimo de 4 sobre 10 en cada uno de los elementos de evaluación.

Evaluación Final en Convocatoria Ordinaria:

- Resolución algorítmica de problemas (examen): 75%

- Trabajo práctico individual (prácticas): informes entregables y prueba adicional de verificación sobre ordenador 25%

Se exige un mínimo de 5 sobre 10 en cada uno de los elementos de evaluación.

Lenguaje de programación Phyton.
Transparencias de clase y algún libro de la bibliografía básica.

Bibliografía básica

- Gilles Brassard, Paul Bratley. Fundamentos de algoritmia. Prentice-Hall, 2006.

- Ian Parberry. Problems on Algorithms. Prentice Hall, 2002.

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (Third Edition). The MIT Press, 2009.

- Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran. Computer algorithms (second Edition). Universities Press, 2007.

- Francesc J. Ferri, Jesús v. Albert, Gregorio Martín, Introducció a l'anàlisi i disseny d'algorismes, Universitat de Valencia, 1998

- Robert Sedgewick an Kevin Wayne: Algorithms (Fourth Edition), 2011.

- Steven S. Skiena. The Algorithm Design Manual (Second Edition). Springer, 2008.

Bibliografía de profundización

* Jason Brownlee: Clever Algorithms: Nature-Inspired Programming Recipes. lulu.com, 2012
* Weixiong Zhang: State-Space Search. Algorithms, Complexity, Extensions and Applications. Springer 1999,
* Bo Xing and Wen-Jing Gao. Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms. Springer 2014.