Atributos
Sigla: 
CI-0124
Créditos: 
4
Horas: 
5
Clasificación: 
Curso propio
Énfasis y ciclo: 
Tecnología de la Información 3.I
Ingeniería de Software 4.I
Descripción: 

“Si solo tienes un martillo, todo tiene forma de clavo”. (Anónimo)

Este curso tiene un enfoque práctico y busca visibilizar las clasificaciones de problemas computacionales en términos de computabilidad, decidibilidad y complejidad, además de la existencia de heurísticas y algoritmos de aproximación, para propiciar la selección del modelo computacional más apropiado en el desarrollo de una solución. Se estudiarán asimismo problemas de complejidad polinomial y no polinomial, para poder decidir cuándo es más adecuado buscar una solución óptima a un problema y cuándo es preferible, o necesario, optar por una solución aproximada.
 

Objetivo general: 

El objetivo general del curso es que cada estudiante sea capaz de reconocer las restricciones impuestas por el nivel jerárquico, la complejidad computacional o decidibilidad de un problema, para poder seleccionar el modelo computacional más adecuado para el diseño de una solución eficiente, a través de un enfoque práctico, con ejemplos clásicos, solución de problemas puntuales y tareas programadas.

Objetivos específicos: 

Durante este curso el estudiante desarrollará habilidades para:

  1. Clasificar los problemas computacionales según la máquina abstracta más simple que sea capaz de resolverlos, para poder solucionar problemas específicos diseñando máquinas abstractas como autómatas y máquinas de Turing, a través del estudio teórico de dichas máquinas y su aplicación práctica. (JERARQUÍA DE LENGUAJES Y DECIDIBILIDAD)
  2. Determinar si un problema computacional puede ser resuelto en tiempo polinomial o no, para poder decidir si se requiere una solución exacta o una aproximación, a través del estudio de problemas clásicos polinomiales y no polinomiales. (COMPLEJIDAD)
  3. Usar algoritmos de aproximación y heurísticas, para encontrar soluciones a problemas computacio-nales NP-completos, NP-duros y ofrecer soluciones parciales para problemas no decidibles, a través de la explicación de dichas técnicas y su aplicación práctica a problemas clásicos (HEURÍSTICAS)

Transversales

Además, cada estudiante practicará las siguientes habilidades transversales:

  1. Comunicación de resultados, tanto de manera escrita como oral.
  2. Trabajo en equipo
Contenidos: 

Los ejes temáticos del curso y los objetivos a los que contribuyen se muestran en la tabla que sigue:

Objetivo específico Eje temático Contenido
1 Computabilidad Lenguajes regulares, expresiones regulares, autómatas finitos deterministas y no deterministas. Lema del bombeo para lenguajes regulares
Aplicaciones de lenguajes regulares: reconocimiento de tokens, análisis léxico, scripting
Lenguajes libres de contexto, autómatas de pila y gramáticas libres de contexto. Lema del bombeo para lenguajes libres de contexto
Aplicaciones de lenguajes libres de contexto: Análisis sintáctico, estructura de un lenguaje
Máquinas de Turing, problemas decidibles y no decidibles, teorema de Rice
2 Complejidad P y NP (Polinomial y no polinomial), complejidad temporal y complejidad espacial
Problemas NP-Completos y NP-Duros
Reducciones
3 Heurísticas y algoritmos de aproximación Introducción al uso de heurísticas y algoritmos de aproximación
Programación dinámica, búsqueda local, búsqueda greedy
Aplicación de los algoritmos a problemas clásicos como bin packing o el problema del viajero
Bibliografía: 

Texto

  1. J. Hopcroft, R. Motwani y J. Ullman. “Introduction to Automata Theory, Languages, and Computation”.  Editorial Pearson/Addison-Wesley, 3a ed., 2007.

Apoyo

  1. H. Lewis y C. Papadimitriou. “Elements of the Theory of Computation”. Editorial Prentice-Hall; 2a ed., 1997. 
  2. Garey, Michael R., and David S. Johnson. “A Guide to the Theory of NP-Completeness”. WH Freemann, New York , 1979. 
  3. Thomas H. Cormen, et al. “Introduction to algorithms”. Vol. 6. Cambridge: MIT press, 2001. 
  4. Williamson, David P., and David B. Shmoys. “The design of approximation algorithms”. Cambridge university press, 2011. 
  5. Rothlauf, Franz. “Design of modern heuristics: principles and application”. Springer Science & Business Media, 2011. 
     
LIberación de responsabilidad: 

Este no es un documento oficial. Documentos oficiales se entregan en la secretaría de la escuela.