Guía docente de la asignatura

Algorítmica (216112C)

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

Grado

Grado en Ingeniería Informática y Administración y Dirección de Empresas

Brach

Ciencias Sociales y Jurídicas

Módulo

Formación Específica de Rama

Materia

Programación e Ingeniería de Software

Curso

2

Semestre

2

Créditos

6

Tipo

Obligatoria

Profesorado

Teórico

José Luis Verdegay Galdeano. Grupo: A

Práctico

  • Francisco Javier Arnedo Fernández Grupo: 2
  • Eugenio Martínez Cámara Grupo: 1
  • Fernando Pérez Bueno Grupo: 1

Tutorías

José Luis Verdegay Galdeano

Show email
  • Lunes de 11:30 a 13:30 (D07 Etsiit)
  • Miércoles de 11:30 a 13:30 (D07 Etsiit)
  • Viernes de 11:30 a 13:30 (D07 Etsiit)

Francisco Javier Arnedo Fernández

Show email
No hay tutorías asignadas para el curso académico.

Eugenio Martínez Cámara

Show email
  • Martes de 12:00 a 13:00 (D1.12 Edif.Aux. Etsiit)
  • Jueves de 12:00 a 13:00 (D1.12 Edif.Aux. Etsiit)

Fernando Pérez Bueno

Show email
No hay tutorías asignadas para el curso académico.

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

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

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.

Additional information

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

Tools for tutorial support (Include virtual tools for tutorial support)

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

Adjustment measures for assessment methods (Instruments, criteria and percentages)

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

Ordinary examination diet

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

Extraordinary examination diet

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

Single final assessment (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

Tools for tutorial support (Include virtual tools for tutorial support)

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

Adjustment measures for assessment methods (Instruments, criteria and percentages)

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. 

Ordinary examination diet

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.

Extraordinary examination diet

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.

Single final assessment (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.