Computabilidad y Lenguajes Formales

Información Básica

  • Código y Nombre: 300CIG007, Computabilidad y Lenguajes Formales.
  • Créditos y horas de contacto: 3 Créditos, 4 horas por semana.
  • Nombre del profesor o coordinador del curso: Gloria Inés Álvarez.
  • Tipo de curso: Abierto.

Textos del Curso

  • Sipser M. Introduction to the Theory of Computation. Segunda Edición. Thompson Course Technology. 2006.
  • Linz P. An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers. 4a.Edición. 2006.
  • Hopcroft John E., Motwani Rajeev, Ullman, Jeffrey D. Introduction to Automata Theory, Languajes and Computation. 3a Edición. Addison Wesley. 2007.
  • Harel D. Computers Ltd. What they really can't do. Oxford University Press. 2000.
  • Cormen T. et. al. Introduction to algorithms. Segunda Edición. MIT Press. 2001.
  • Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. Tercera Edición. Addison-Wesley. 2007.
  • Garey M. Johnson D. Computers and intractability A guide to the theory of NP-completeness. W.H.Freeman and Company. 1979.
  • Skiena S. The algorithm design manual. Springer-verlag. 1998.

Información Específica del Curso

  • Este curso tiene como objetivo reunir temas fundamentales de la informática teórica, que son parte indispensable de la formación de un ingeniero de sistemas. En lo referente al estudio de los lenguajes formales, el conocer y aprender a utilizar modelos como las expresiones regulares o los autómatas de estados finitos brinda la posibilidad de ampliar el conjunto de modelos que permiten una representación fiel de diversos aspectos del mundo real. De otro lado, conocer las limitaciones inherentes al concepto de computabilidad descubre una realidad a veces desconocida: que no todos los problemas son susceptibles de ser resueltos algorítmicamente, de hecho, que existe un sinfín de problemas que no pueden ser resueltos mediante un computador. Finalmente, este curso vuelve sobre un elemento muy importante para la práctica de la buena programación, que es el cálculo de complejidades temporales y espaciales de los algoritmos. En conclusión, este curso agrupa temas teóricos fundamentales, que enriquecerán la visión del estudiante acerca de las ciencias de la computación y lo llevarán a aplicar esta ciencia en el desempeño de una ingeniería de calidad.

Objetivos Específicos del Curso

Objetivos de aprendizaje:
  • Definir e interpretar modelos computacionales de variado poder expresivo.
  • Enunciar y argumentar la veracidad de los conceptos principales de la teoría de la computación.
  • Analizar la complejidad de una máquina de Turing y de un algoritmo.
Relación con los resultados de programa
Resultados de Programa
A B C D E F G H I J K
Relevancia 4 1 4

1: baja relevancia; 2: media relevancia; 3: alta relevancia.

Tópicos del Curso

  • Lenguajes regulares.
  • Autómatas de estados finitos deterministas y no deterministas.
  • Minimización de autómatas deterministas.
  • Expresiones regulares.
  • Aplicación al análisis léxico.
  • Lenguajes incontextuales.
  • Gramáticas incontextuales.
  • Autómatas de pila.
  • Forma normal de Chomsky.
  • Aplicación al análisis sintáctico.
  • Lenguajes Recursivos y Recursivamente Enumerables.
  • Máquinas de Turing determinista y no determinista, con una y varias cintas.
  • Funciones computables mediante máquinas de Turing.
  • Decidibilidad.
  • Reducibilidad.
  • Clases P, NP y NP-completo.
  • Notaciones de orden de magnitud y complejidad temporal.
  • Complejidad en espacio.
  • Complejidad de algoritmos sobre árboles.
  • Complejidad de algoritmos sobre grafos.
 
pregrados/dptoccomputacionyelectronica/computabilidad.txt · Última modificación: 2014/07/15 15:56 por lsosorio
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki