Guía docente de la asignatura

Algorítmica

Curso 2021 / 2022
Fecha última actualización: 21/06/2021
Fecha de aprobación: 21/06/2021

Grado

Grado en Ingeniería Informática y Matemáticas

Rama

Ingeniería y Arquitectura

Módulo

Formación Obligatoria Informática

Materia

Programación e Ingeniería del Software (33)

Curso

2

Semestre

2

Créditos

6

Tipo

Obligatoria

Profesorado

Teoría

  • María Teresa Lamata Jiménez. Grupos: A

Prácticas

  • María Teresa Lamata Jiménez. Grupos: 1 y 2

Tutorías

María Teresa Lamata Jiménez

mlamata@ugr.es
  • Segundo semestre
    • Lunes de 8:30 a 11:30 (D08 Etsiit)
    • Martes de 8:30 a 11:30 (D08 Etsiit)
  • Primer semestre
    • Lunes de 10:30 a 13:30 (D08 Etsiit)
    • Martes de 10:30 a 13:30 (D08 Etsiit)

Prerrequisitos y/o Recomendaciones

Los alumnos 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 Grado)

  • 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 asociadas a materia/asignatura

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.

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.
  • Tema 4. Algoritmos Basados en Programación Dinámica.
  • Tema 5. Algoritmos para la Exploración en Grafos.
  • Tema 6. Otras Metodologías Algorítmicas.

Práctico

  • Resolución de problemas propios de la materia en el laboratorio y eventualmente en pizarra.
  • Eficiencia de Algoritmos.
  • Análisis, diseño e implementación de Algoritmos basados en las Técnicas Divide y Vencerás, Greedy, Programación Dinámica y/o de Exploración en 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. Third Edition. MIT Press. 2009
  • 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. 2004
  • S. Skiena. The Algorithm Design Manual. Springer 2008.

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 se realizará un examen final y, opcionalmente, eventuales entregas y presentaciones de ejercicios, o trabajos propuestos por el profesor. La ponderación de este bloque es del 70% (valor numérico T expresado de 0 a 10).
  • 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 de las anteriores calificaciones (G= T+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 valoració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= T+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. La modalidad del examen dependerá de los medios físicos y tecnológicos que la Universidad disponga para el alumnado y el profesorado, dependiendo del escenario A o B en el que se encuentre la docencia impartida.

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.

ESCENARIO A (ENSEÑANZA-APRENDIZAJE PRESENCIAL Y TELE-PRESENCIAL)

Horario (Según lo establecido en el POD)

https://decsai.ugr.es/docencia/profesorado

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

  • Correo Electrónico del profesor correspondiente
  • Video-sesiones con Google Meet

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

En el escenario A, y para la atención tele-presencial al estudiante, se impartirán las clases presenciales con medios telemáticos facilitados por la Universidad y/o el centro (Google Meet, video transmisión, etc.).

Evaluación ordinaria

No se requiere de medidas de adaptación para este escenario.

Evaluación extraordinaria

No se requiere de medidas de adaptación para este escenario.

Evaluación única final

No se requiere de medidas de adaptación para este escenario.

ESCENARIO B (SUSPENSIÓN DE LA ACTIVIDAD PRESENCIAL)

Horario (Según lo establecido en el POD)

https://decsai.ugr.es/docencia/profesorado

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

  • Correo Electrónico del profesor correspondiente
  • Video-sesiones con Google Meet

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

Las clases presenciales en instalaciones del centro se sustituirán por una o varias metodologías entre las siguientes:

  • Videotutoriales, cápsulas y material multimedia disponible en la plataforma.
  • Foros en diversos formatos (blog, clásico) para preguntas y resolución de dudas.
  • Colecciones de diapositivas y relaciones de problemas resueltos y no resueltos.
  • Acceso gratuito a apuntes y libros escritos por el profesorado de la asignatura.
  • Video-clases utilizando Google-Meet. 

Evaluación ordinaria

La evaluación en Convocatoria Ordinaria se realizará mediante la elaboración y entrega de proyectos y la explicación de sus fundamentos, relacionando los mismos con todos los contenidos teóricos de la asignatura. En los criterios de evaluación de teoría y prácticas se tendrá en cuenta el análisis, diseño e implementación de algoritmos, así como el cálculo de su eficiencia y la explicación de su funcionamiento sobre casos de ejemplo. Los proyectos podrán ser realizados de forma individual o en grupo, dependiendo de la naturaleza y objetivos de cada proyecto. La suma de las valoraciones de las memorias y presentación de resultados de los proyectos supondrá al menos el 70% de la nota final. Adicionalmente, se realizará una prueba individual (cuya calificación supondrá hasta el 30% de la nota final) para asegurar que los conceptos, habilidades y competencias hayan sido adquiridos correctamente por el estudiante.

Evaluación extraordinaria

La evaluación en convocatoria extraordinaria se realizará mediante un examen que consistirá en la resolución de problemas teórico-prácticos realizados sobre los medios físicos o tecnológicos permitidos y/o facilitados por la Universidad para este escenario, donde la calificación de cada uno de ellos estará guiada por la idoneidad de la solución aportada a cada ejercicio.

En esta convocatoria, la nota de prácticas se mantiene con una ponderación del 30% si el estudiante así lo desea. En caso contrario el 100% de la calificación total se obtendrá de la nota del examen.

Evaluación única final

La evaluación se realizará mediante un examen que consistirá en la resolución de problemas teórico-prácticos realizados sobre los medios físicos o tecnológicos permitidos y/o facilitados por la Universidad para este escenario, donde la calificación de cada uno de ellos estará guiada por la idoneidad de la solución aportada a cada ejercicio.