Algoritmia y Programación III

Usted está aquí

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

  • Enric Rodriguez Carbonell ( )

Otros

  • Albert Oliveras Llunell ( )

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 C++, 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 C++.
    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

Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Examen parcial


Objetivos: 2 1 3
Semana: 8
Tipo: examen de teoría
Teoría
3h
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)
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
9h

Proyecto - Algoritmos Voraces


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

Examen de laboratorio


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

Proyecto - Metaheurísticas


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

Examen final


Objetivos: 2 1 3 4 9 8
Semana: 15 (Fuera de horario lectivo)
Tipo: examen de teoría
Teoría
3h
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.

El curso utiliza el lenguaje de programación C++.

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ásica:

Complementaria:

Web links

Capacidades previas

- Familiaridad con las técnicas básicas de programación y el lenguaje de programación C++: iteraciones, alternativas, funciones recursivas, paso de parámetros, punteros, referencias, memoria dinámica, 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