Guía docente de Algorítmica (216112C)
Grado
Rama
Módulo
Materia
Year of study
Semestre
ECTS Credits
Tipo
Profesorado
Teórico
Práctico
Prerrequisitos y/o Recomendaciones
Los estudiantes no tendrán que tener asignaturas, materias o módulos aprobados como requisito indispensable para cursar el módulo. No obstante, se recomienda la superación de los contenidos y adquisición de competencias de las materias de formación básica relativas a Fundamentos de Programación, Metodología de la Programación y Estructuras de Datos.
Breve descripción de contenidos (Según memoria de verificación del Máster)
- Análisis de la eficiencia de algoritmos.
- Diseño de algoritmos.
- Técnicas: "Divide y Vencerás", Algoritmos Voraces, Exploración en Grafos, Programación Dinámica.
Competencias
Competencias Generales
- CG08. Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.
- CG09. Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.
Competencias Específicas
- CE12. Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.
Competencias Transversales
- CT02. Capacidad para tomar decisiones basadas en criterios objetivos (datos experimentales, científicos o de simulación disponibles) así como capacidad de argumentar y justificar lógicamente dichas decisiones, sabiendo aceptar otros puntos de vista.
Resultados de aprendizaje (Objetivos)
- Plantearse la búsqueda de varias soluciones distintas para un mismo problema y evaluar la bondad de cada una de ellas.
- Tomar conciencia de la importancia del análisis de la eficiencia de un algoritmo como paso previo a su implementación en un lenguaje de programación.
- Conocer la notación asintótica para describir la eficiencia de un algoritmo, distinguiendo entre los distintos tipos de análisis que se pueden realizar: caso más favorable, más desfavorable y promedio.
- Saber realizar el análisis de eficiencia de un algoritmo, tanto a nivel teórico como empírico, y saber contrastar resultados experimentales con los teóricos.
- Conocer las técnicas básicas de resolución de ecuaciones de recurrencia: expansión de la recurrencia, método de la ecuación característica y utilización de fórmulas maestras.
- Comprender la técnica de resolución de un problema por división en problemas más pequeños.
- Conocer y saber aplicar los esquemas básicos de los algoritmos divide y vencerás.
- Comprender la técnica voraz (avance rápido) de resolución de problemas y los distintos casos que se pueden presentar en la resolución de problemas por esta técnica: obtención de la solución óptima, de una solución no óptima, o no obtención de la solución.
- Comprender la técnica de resolución de problemas por programación dinámica, e identificar las diferencias con divide y vencerás y con avance rápido.
- Saber identificar problemas que cumplen el principio de optimalidad y qué es necesario para poder aplicar esta técnica.
- Saber ver al árbol de estados como una representación lógica del conjunto de todas las posibles soluciones de un problema.
- Conocer las técnicas de exploración de grafos (vuelta atrás y ramificación y poda) y su aplicación en la resolución de problemas, entendiendo sus características principales y las diferencias entre ellas.
- Comprender y saber aplicar el uso de cotas para reducir el espacio de búsqueda en las técnicas de exploración en grafos.
- Conocer los criterios de aplicación de cada una de las distintas técnicas de diseño de algoritmos.
- Saber seleccionar e implementar el mejor algoritmo que resuelve un problema dado.
Programa de contenidos Teóricos y Prácticos
Teórico
- Tema 1. La eficiencia de los algoritmos.
- Tema 2. Algoritmos "divide y vencerás".
- Tema 3. Algoritmos voraces [greedy].
- Tema 4. Algoritmos para la exploración de grafos.
- Tema 5. Algoritmos basados en programación dinámica.
- Tema 6. Otras metodologías algorítmicas.
Práctico
- Resolución de problemas propios de la materia en el laboratorio y en pizarra.
- Eficiencia de algoritmos.
- Análisis, diseño e implementación de diversos algoritmos basados en las técnicas de diseño estudiadas en la asignatura ("divide y vencerás", greedy, programación dinámica, exploración de grafos).
- Resolución de problemas utilizando la técnica más adecuada.
- Problemas sobre grafos.
- Desafíos y nuevas tendencias en Algorítmica.
Bibliografía
Bibliografía fundamental
- G. Brassard y P. Bratley: Fundamentos de Algoritmia. Prentice Hall, 1997
- T.H. Cormen, C.E. Leiserson, R. L. Rivest y C. Stein: Introduction to Algorithms. Fourth Edition. MIT Press, 2022.
- E. Horowitz, S. Sahni, S. Rajasekaran: Computer Algorithms. Comp Science Press, 2007.
- J.L. Verdegay: Lecciones de Algorítmica. Editorial Técnica AVICAM, 2017.
Bibliografía complementaria
- J. Kleinberg, E. Tardos. Algorithm Design. Addison-Wesley, 2005.
- S. Skiena. The Algorithm Design Manual. Springer, 2020 (3 edición).
- G. Heineman, G Pollice, S. Selkow. Algorithms in a Nutshell: A Practical Guide. O'Reilly Media 2016
- R. Sedgewick. Algorithms in C. Addison-Wesley, 3rd edition, 2001
- J. Erickson. Algorithms Univ. Illinois (2019) https://jeffe.cs.illinois.edu/teaching/algorithms/ (pdf)
- T. Roughgarden. Algorithms Illuminated: Omnibus edition. Soundlikeyourself Publishing LLC 2022.
Enlaces recomendados
Metodología docente
- MD01. Lección Magistral (Clases Teóricas-Expositivas)
- MD02. Actividades Prácticas (Resolución de Problemas, Resolución de Casos Prácticos, Desarrollo de Proyectos, Prácticas en Laboratorio, Taller de Programación, Aula de Informática, Prácticas de Campo).
- MD03. Seminarios (Debates, Demos, Exposición de Trabajos Tutelados, Conferencias, Visitas Guiadas, Monografías).
- MD04. Actividades no presenciales Individuales.
- MD05. Actividades no presenciales Grupales.
- MD06. Tutorías Académicas.
Evaluación (instrumentos de evaluación, criterios de evaluación y porcentaje sobre la calificación final)
Evaluación Ordinaria
- Para la parte teórica (valor numérico T expresado de 0 a 10) se realizará un examen final cuya ponderación será del 70% de la calificación final. Opcionalmente, en clase de teoría se podrán proponer eventuales entregas y presentaciones de ejercicios, o trabajos propuestos por el profesor, para subir nota.
- Para la parte práctica se realizarán prácticas de laboratorio, resolución de problemas y desarrollo de proyectos (individuales o en grupo), y se valorarán las entregas de los informes/memorias y presentaciones realizados por los alumnos. La ponderación de este bloque será del 30% (valor numérico P expresado de 0 a 10).
La calificación global (G) será una calificación numérica obtenida mediante la suma ponderada de las anteriores calificaciones (G= 0,7*T + 0,3*P). No existe calificación mínima requerida en ninguna de las dos partes para aprobar la asignatura.
Evaluación Extraordinaria
La evaluación se realizará en un único acto académico en la fecha establecida por el centro y consistirá en un examen (evaluado de 0 a 10) que incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en esta misma guía docente. La ponderación de los bloques de teoría y de prácticas se mantiene en el 70% para teoría (T) y el 30% para prácticas (P). Se podrá mantener la nota de prácticas obtenida en la convocatoria ordinaria si el estudiante así lo desea. En caso contrario el 100% de la calificación total se obtendrá de la nota del examen.
La calificación global (G) será una calificación numérica obtenida mediante la suma de las anteriores calificaciones (G= 0,7*T + 0,3*P). No existe calificación mínima requerida en ninguna de las dos partes para aprobar la asignatura.
Evaluación única final
La evaluación se realizará en un único acto académico en la fecha establecida por el centro y consistirá en un examen (evaluado de 0 a 10) que incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en esta misma guía docente.
Información adicional
Régimen de asistencia
La asistencia a las clases teóricas no será obligatoria, aunque la participación activa en clase y la entrega de ejercicios planteados por el profesor se tendrá en cuenta dentro del sistema de evaluación continua de la asignatura. Se requerirá, siguiendo el sistema de evaluación continua, que el estudiante asista al menos a alguna de las sesiones prácticas dentro de los límites de entrega de cada práctica y eventualmente defienda ante el profesor el resultado de la correspondiente práctica.