El principal objetivo de la asignatura es presentar las técnicas fundamentales de diseño de algoritmos. Se estudiarán el objetivo y funcionalidad de cada técnica para la resolución de problemas, su esquema general, posibles implementaciones, estudio de costes computacionales y aplicaciones.

Se parte de los conocimientos básicos de computación y las competencias básicas en programación adquiridas hasta el momento en los estudios de grado, particularmente, aunque no solo, en las asignaturas de primer curso "Introducción a la Computación" y "Fundamentos de Programación". Sobre esta base se presentan las técnicas básicas de diseño de algoritmos sobre un lenguaje algorítmico. Se realizan análisis comparativos en función de especificaciones, costes, restricciones y se estudian también implementaciones eficaces de las técnicas presentadas. Se realizarán también análisis de costes reales y sobre computadora.

Las técnicas y competencias adquiridas en esta asignatura servirán al alumno en la resolución por computadora de cualquier problema algorítmico planteado en las demás asignaturas.

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.

• Sistema de Evaluación Continua
• Sistema de Evaluación Final
• Herramientas y porcentajes de calificación:
  • Ver orientaciones (%): 100

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.

Evaluación Final en Convocatoria extraordinaria:

- 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.

Direcciones web

* Wikipedia (versión en inglés) [en.wikipedia.org]
* Clever Algorithms: http://www.cleveralgorithms.com/nature-inspired/index.html
* Lenguaje algorítmico en Latex
- Algorithm2e: http://www.ctan.org/pkg/algorithm2e
- Uso Algorithm2e en español: http://tex.stackexchange.com/questions/146050/how-to-write-pseudo-code-in-other-languages-spanish
* Python Programming Language
- Official Website: http://python.org/
- The Python Tutorial: https://docs.python.org/3/tutorial/
- Python 3 documentation: https://docs.python.org/3/
- Problem Solving with Algorithms and Data Structures Using Python - Official Website: http://interactivepython.org/runestone/static/pythonds/index.html