Algoritmia y Programación III

• Profesorado
• Horas semanales
• Competencias
• Objetivos
• Contenidos
• Actividades
• Metodología docente
• Método de evaluación
• Bibliografía
• Web links
• Capacidades previas

Profesorado

Responsable

• Enric Rodriguez Carbonell ( )

Otros

• Albert Oliveras Llunell ( )

Horas semanales

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

Metodología docente

Método de evaluación

Bibliografía

Básica:

• Introduction to algorithms - Cormen, T.H [et al.], MIT Press, 2022. ISBN: 9780262046305
  
• Computers and intractability: a guide to the theory of NP-Completeness - Garey, M.R.; Johnson, D.S, W.H. Freeman, 1979. ISBN: 0716710447
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000087999706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Foundations of algorithms - Neapolitan, R.E, Jones and Bartlett Learning, 2015. ISBN: 9781284049190
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004097269706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Metaheuristics - Siarry, P. (ed.), Springer, 2017. ISBN: 9783319832845
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004156469706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Llenguatges, gramàtiques i autòmats: curs bàsic - Cases, R.; Màrquez, L, Edicions UPC, 2003. ISBN: 8483017288
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002699299706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Handbook of metaheuristics - Gendreau, M.; Potvin, J.-Y, Springer , 2018. ISBN: 9783319910857
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004151509706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Dasgupta, S.; Papadimitriou, C.; Vazirani, U., Mc Graw Hill Higher Education , 2008. ISBN: 9780073523408
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003202339706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Sedgewick, R.; Wayne, K, Addison-Wesley , 2011. ISBN: 9780321573513
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004156419706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithm design - Kleinberg, J.; Tardos, É, Pearson , 2014. ISBN: 9781292023946
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004001669706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to automata theory, languages, and computation - Hopcroft, J.E.; Motwani, R.; Ullman, J.D, Pearson/Addison Wesley , 2007. ISBN: 0321462254
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003933959706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• Jutge automàtic per les sessions de laboratori https://jutge.org/

Capacidades previas