Diseño de Algoritmos26212
- Centro
- Facultad de Ciencia y Tecnología
- Titulación
- Grado en Matemáticas
- Curso académico
- 2024/25
- Curso
- 4
- Nº Créditos
- 6
- Idiomas
- Castellano
- Código
- 26212
DocenciaAlternar navegación
Guía docenteAlternar navegación
Descripción y Contextualización de la AsignaturaAlternar navegación
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/ Resultados de aprendizaje de la asignaturaAlternar navegación
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
Contenidos teórico-prácticosAlternar navegación
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.
MetodologíaAlternar navegación
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.
Sistemas de evaluaciónAlternar navegación
- Sistema de Evaluación Continua
- Sistema de Evaluación Final
- Herramientas y porcentajes de calificación:
- Ver orientaciones (%): 100
Convocatoria Ordinaria: Orientaciones y RenunciaAlternar navegación
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.
Convocatoria Extraordinaria: Orientaciones y RenunciaAlternar navegació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.
Materiales de uso obligatorioAlternar navegación
Lenguaje de programación Phyton.
Transparencias de clase y algún libro de la bibliografía básica.
BibliografíaAlternar navegación
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
GruposAlternar navegación
01 Teórico (Castellano - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 09:30-10:30 (1) | 09:30-10:30 (2) |
01 Seminario-1 (Castellano - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
19-28 | 08:30-09:30 (1) |
01 P. de Aula-1 (Castellano - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-19 | 08:30-09:30 (1) | ||||
21-29 | 08:30-09:30 (2) | ||||
30-30 | 08:30-09:30 (3) |
01 P. Ordenador-1 (Castellano - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-16 | 15:00-16:00 (1) | ||||
17-29 | 15:00-17:00 (2) |