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

Eje temático

Contenido

1

Computabilidad

Lenguajes regulares, expresiones regulares, autómatas finitos deterministas y no deterministas. Lema del bombeo para lenguajes regulares.

Lenguajes libres de contexto, autómatas de pila y gramáticas libres de contexto. Lema del bombeo para lenguajes libres de contexto.

Aplicaciones prácticas de lenguajes regulares y libres de contexto:

  • Análisis léxico y sintáctico, herramientas similares a Lex, Yacc, o PLY;
  • Uso de expresiones regulares en scripts de AWK y herramientas similares a grep y sed.

Lenguajes recursivamente enumerables. Máquina de Turing (MT): descripción formal, simulación de problemas sencillos (por ejemplo, suma de números binarios, sucesor de un número binario).

Lenguajes regulares y decidibilidad: Cuestionamiento acerca de las expectativas de resultados de un algoritmo para un problema dado.

2

Complejidad

P y NP (Polinomial y no polinomial), complejidad temporal y complejidad espacial.

Problemas clásicos NP-Completos (NP-C) y NP-Duros (NP-H).

Métricas temporales y espaciales. Unidades para medir el tamaño de un problema. Cantidad de pasos requeridos para que la MT alcance una solución.

3

Heurísticas y algoritmos de aproximación

Introducción al uso de heurísticas y algoritmos de aproximación. Soluciones óptimas y casi-óptimas, espacio de búsqueda.

Meta-heurísticas clásicas, al menos: algoritmos genéticos, búsqueda tabú y simulated annealing.

Meta-heurísticas no tradicionales, por ejemplo, enjambres.

Aplicación de los algoritmos a problemas clásicos como bin packing o el problema del viajero.

 

 

Metodología

Metodología pedagógica o didáctica. Ver artículo 14 del Reglamento de Régimen Académico Estudiantil.

 

Evaluación

Indicar aspectos a evaluar en el curso y su ponderación (no incluir el rubro de “concepto”). Especificar normas o reglas de evaluación particulares, si hubiera. Ver artículo 14 del Reglamento de Régimen Académico Estudiantil.

 

Cronograma

Incluir al menos fechas de exámenes y de elementos de evaluación cuyo puntaje singular sea significativo.

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

Recursos estudiantiles

Para información sobre recursos estudiantiles disponibles en la UCR, incluyendo el Sistema de bibliotecas y la normativa universitaria vigente, favor visitar la página: https://www.ecci.ucr.ac.cr/vida-estudiantil/servicios-institucionales-para-estudiantes/guia-de-recursos-estudiantiles-de-la-ucr

LIberación de responsabilidad: 

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