Algoritmia y Programación III

Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
En esta asignatura se estudian los principales esquemas algorítmicos para la resolución de problemas computacionales complejos. De forma paralela se introducen las herramientas necesarias para poder implementar estos algoritmos en un lenguaje de programación moderno.

Profesorado

Responsable

Otros

Horas semanales

Teoría
2
Problemas
1
Laboratorio
1
Aprendizaje dirigido
0
Aprendizaje autónomo
6

Competencias

Competencias Técnicas

Competencias técnicas

  • CE2 - Ser capaz de programar soluciones a problemas de ingeniería: Diseñar soluciones algorítmicas eficientes a un problema computacional dado, implementarlas en forma de Programa robusto, estructurado y mantenible, y comprobar la validez de la solución.
  • CE7 - Demostrar conocimiento y capacidad de aplicación de las herramientas necesarias para el almacenaje, el procesamiento y el acceso a los datos.

    • Competencias Transversales

    Transversales

  • CT4 [Avaluable] - Trabajo en equipo. Ser capaz de trabajar como miembro de un equipo interdisciplinar, ya sea como un miembro más o realizando tareas de dirección, con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.
  • CT5 - Uso solvente de los recursos de información. Gestionar la adquisición, la estructuración, el análisis y la visualización de datos e información en el ámbito de especialidad y valorar de forma crítica los resultados de dicha gestión.
  • CT6 - Aprendizaje autónomo. Detectar deficiencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar dicho conocimiento.
  • CT7 - Tercera lengua. Conocer una tercera lengua, preferentemente el inglés, con un nivel adecuado oral y escrito y en consonancia con las necesidades que tendrán los titulados y tituladas.

    • Básicas

  • CB5 - Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Concebir sistemas computacionales que integren datos de procedencias y formas muy diversas, creen con ellos modelos matemáticos, razonen sobre dichos modelos y actúen en consecuencia, aprendiendo de la experiencia.
  • CG2 - Elegir y aplicar los métodos y técnicas más adecuados a un problema definido por datos que representen un reto por su volumen, velocidad, variedad o heterogeneidad, incluidos métodos informáticos, matemáticos, estadísticos y de procesado de la señal.
  • CG5 - Poder recurrir a conocimientos fundamentales y metodologías de trabajo sólidas adquiridos durante los estudios para adaptarse a los nuevos escenarios tecnológicos del futuro.

    • Objetivos

    1. Tomar conciencia de los límites de la computación: comprender las implicaciones de la pregunta "P=NP?", entender el enunciado del Teorema de Cook-Levin, reconocer y identificar varios problemas NP-completos clásicos.
      Competencias relacionadas: CG5,
    2. Conocer, explicar, diseñar, analizar, comparar e implementar algoritmos de búsqueda exhaustiva usando la tècnica de backtracking.
      Competencias relacionadas: CE2, CB5,
    3. Conocer el esquema de programación dinámica, identificar cuándo se puede aplicar y cómo, y familiarizarse con algunos algoritmos de programación dinámica fundamentales.
      Competencias relacionadas: CE2,
    4. Conocer el esquema de los algoritmos voraces, identificar cuándo se pueden aplicar y cómo, conocer las técnicas más habituales para demostrar su corrección y familiarizarse con algunos algoritmos voraces fundamentales.
      Competencias relacionadas: CE2,
    5. Completar y modificar implementaciones, en el lenguaje de programación Python, de varios algoritmos para resolver problemas de dificultad media.
      Competencias relacionadas: CE2, CT6,
    6. Identificar y proponer soluciones a posibles problemas de eficiencia en programas escritos en el lenguaje de programación Python.
      Competencias relacionadas: CE2, CT6,
    7. Desarrollar proyectos de tamaño medio como miembro de un equipo, aprendiendo así a dividir un proyecto en partes pequeñas, distribuirlas entre sus miembros y actuar con responsabilidad de forma coordinada para la correcta finalización de las tareas asignadas.
      Competencias relacionadas: CE2, CT4, CT5, CT6, CT7, CG1, CG2,
    8. Conocer algoritmos basados en búsqueda local para resolver eficientemente problemas intratables. Conocer una variedad de metaheurísticas de diferente naturaleza y ser capaz de identificar cuándo y cómo se pueden aplicar en problemas concretos computacionalmente duros.
      Competencias relacionadas: CE2,
    9. Conocer los fundamentos de autómatas finitos y expresiones regulares para poderlos usar en la práctica (búsqueda de patrones en textos, etc.).
      Competencias relacionadas: CE7,

    Contenidos

    1. Tractabilidad: clases de problemas P y NP
      Clases P y NP, Teorema de Cook-Levin, reducciones, NP-completitud.
    2. Búsqueda exhaustiva
      Principios teóricos: espacio de soluciones, soluciones parciales, poda. Ejemplos: subconjuntos, permutaciones, viajante de comercio, suma de subconjuntos.
    3. Programación dinámica
      Esquema top-down (memoización). Esquema bottom-up (tabulación). Ejemplos: Fibonacci, números binomiales, mochila, multiplicación de secuencias matrices.
    4. Algoritmos voraces
      Principios teóricos: esquema general de los algoritmos voraces. Ejemplos: planificación de tareas, etc. mínimos.
    5. Metaheurísticas
      Búsqueda local. Simulated Annealing, Tabu Search, GRASP, algoritmos genéticos.
    6. Autómatas finitos y expresiones regulares
      Alfabetos, palabras, lenguajes. Autómatas finitos deterministas, autómatas finitos indeterministas, autómatas finitos con lambda-transiciones, equivalencia entre modelos de autómatas, minimización de autómatas. Expresiones regulares, equivalencia con autómatas. Operaciones.

    Actividades

    Actividad Acto evaluativo


    Tractabilidad


    Objetivos: 1
    Contenidos:
    Teoría
    6h
    Problemas
    4h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Búsqueda Exhaustiva


    Objetivos: 2 5 6
    Contenidos:
    Teoría
    4h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Programación Dinámica


    Objetivos: 3 5 6
    Contenidos:
    Teoría
    4h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Algoritmos Voraces


    Objetivos: 4 5 6
    Contenidos:
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Metaheurísticas


    Objetivos: 8 5
    Contenidos:
    Teoría
    4h
    Problemas
    0h
    Laboratorio
    6h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Autómatas finitos y expresiones regulares


    Objetivos: 9
    Contenidos:
    Teoría
    4h
    Problemas
    4h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Consolidación


    Objetivos: 2 1 3 4 9 8
    Contenidos:
    Teoría
    4h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Examen parcial


    Objetivos: 2 1 3
    Semana: 8
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Proyecto - Búsqueda Exhaustiva


    Objetivos: 2 5 6 7
    Semana: 8 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Proyecto - Algoritmos Voraces


    Objetivos: 4 5 6 7
    Semana: 12 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen de laboratorio


    Objetivos: 2 3 4 9 8 5 6
    Semana: 13
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Proyecto - Metaheurísticas


    Objetivos: 8 5 6 7
    Semana: 14 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen final


    Objetivos: 2 1 3 4 9 8
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    El temario se expone de forma muy práctica, a través de la presentación de muchos ejemplos.

    Las clases de teoría introducen todos los conceptos y técnicas necesarios, los cuales se posen en práctica en las clases de problemas y de laboratorio mediante una colección de problemas y ejercicios en un juez automático.

    Las dos horas de clases de teoría se hacen semanalmente. Las dos horas de clases de laboratorio se hacen quincenalmente. Las dos horas de clases de problemas se hacen quincenalmente.

    El proyecto integra los conocimientos y las competencias de todo el curso.

    Método de evaluación

    NPar = nota examen parcial
    NFT = nota examen final de teoría
    NFL = nota examen final de laboratorio
    NPro = nota proyecto

    NOTA FINAL = max( 30%Npar + 30%NFT + 20%NFL + 20% NPro, 60%NFT + 20%NFL + 20% NPro)

    La nota del examen de reevaluación, si hay y es más alta, sustituye la nota del examen final de teoría (NFT). Las notas de parcial, proyecto y laboratorio (NPar, NPro, NFL) se conservan.

    Bibliografía

    Básico

    Complementario

    Web links

    Capacidades previas

    - Familiaridad con las técnicas básicas de programación: iteraciones, alternativas, funciones recursivas, paso de parámetros, clases, objetos, métodos, ...

    - Conocimiento de conceptos algorítmicos básicos: eficiencia de algoritmos, notación asintótica, grafos, recorrido en grafos, estructuras de datos (listas, árboles de búsqueda, hash, heaps, ...)

    - Conocimientos básicos de matemática discreta, álgebra lineal y cálculo

    - Conocimientos básicos de teoría de la probabilidad y estadística