¡Esta es una revisión vieja del documento!


Computabilidad y Lenguajes Formales (300CIG007)

Información Básica

  • Créditos: 3
  • Horas de Clase: 4 / semana
  • Horas de trabajo independiente: 5 / semana
  • Horas de Laboratorio al semestre:
  • Prerequisitos: Matemáticas Discretas para la Computación (300MAG031)
  • Tipo de curso: Núcleo de Formación Fundamental.

Descripción del Curso

Este curso reune 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

Al finalizar el curso los participantes podrán:

  1. Definir e interpretar modelos computacionales de variado poder expresivo.
    1. Definir qué es un lenguaje regular y representar dicho lenguaje mediante autómatas de estados finitos deterministas, no deterministas o expresiones regulares.
    2. Minimizar un autómata determinista.
    3. Demostrar que los autómatas deterministas, los no deterministas y las expresiones regulares son modelos equivalentes.
    4. A partir de la descripción de una situación del mundo real o de un sistema, definir un autómata de estados finitos que lo modela.
    5. Definir qué es un lenguaje incontextual.
    6. Calcular la derivación de una cadena en una gramática incontextual.
    7. Dado un lenguaje formal, definir una gramática incontextual que lo genera y dada una gramática incontextual, describir en forma verbal el lenguaje que genera.
    8. Convertir una gramática incontextual a la forma normal de Chomsky.
    9. Dado un lenguaje incontextual, definir un autómata de pila que lo reconoce y dado un autómata de pila, describir verbalmente cuál es el lenguaje que reconoce.
    10. Demostrar que autómatas de pila no deterministas y gramáticas incontextuales son modelos equivalentes.
    11. Definir qué es una máquina de Turing.
    12. Definir una máquina de Turing que reconoce un lenguaje formal dado y describir verbalmente el lenguaje que reconoce una máquina de Turing dada.
    13. Demostrar que la máquina de Turing no determinista tiene el mismo poder expresivo que la determinista.
    14. Definir una máquina de Turing que compute una función dada.
  2. Enunciar y argumentar la veracidad de los conceptos principales de la teoría de la computación.
    1. Enunciar la tesis de Church y Turing y argumentar su importancia.
    2. Definir qué es un lenguaje decidible y uno reconocible.
    3. Demostrar que un lenguaje dado es decidible y/o reconocible.
    4. Enunciar el problema de la parada y demostrar que es indecidible.
    5. Definir qué es una reducción entre lenguajes.
    6. Definir el lenguaje asociado a un problema de decisión.
    7. Definir la clase de Lenguajes P, NP, NP-Completo y PSPACE y demostrar la pertenencia de un lenguaje a alguna de estas categorías.
    8. Construir una jerarquía entre las clases de lenguajes estudiadas y argumentar las equivalencias o contenencias entre diferentes clases de lenguajes.
  3. Analizar la complejidad de una máquina de Turing y de un algoritmo.
    1. Utilizar la definición de las notaciones O, Omega y Theta para mostrar que una función matemática dada está o no acotada por otra mediante cada una de ellas.
    2. Aplicar las reglas de sumas y productos para calcular una cota superior de complejidad temporal a partir del pseudocódigo de un algoritmo.
    3. Estar en capacidad de evaluar la complejidad temporal y espacial de algoritmos que tienen como estructura de datos principal arreglos, árboles o grafos.

Contenido

Capítulo 1: Introducción

Sesión Horas de Clase Tópicos Bibliografía
1 2 Presentación del curso, historia de la teoría de la computación, cuáles son los límites teóricos de la computación? [1,cap 0]

Total de Horas: 2.

Capítulo 2: Lenguajes Formales

Sesión Horas de Clase Tópicos Bibliografía
2 10 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 [1,cap 1]
7 10 Lenguajes Incontextuales. Gramáticas incontextuales. Autómatas de pila. Forma normal de Chomsky. Aplicación al análisis sintáctico [1,cap 2]
12 6 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 [1,cap 3]

Total de Horas: 26.

Capítulo 3: Teoría de la computación

Sesión Horas de Clase Tópicos Bibliografía
15 6 Decidibilidad [1,cap 4]
18 4 Reducibilidad [1,cap 5]
20 6 Clases P, NP y NP-completo 18-20 [1,cap 7]

Total de Horas: 16.

Capítulo 4: Análisis de la complejidad

Sesión Horas de Clase Tópicos Bibliografía
23 4 Notaciones de orden de magnitud y complejidad temporal [1,cap 7]
25 4 Complejidad en espacio [1,cap 8]
27 4 Complejidad de algoritmos sobre árboles [5,cap 6,12]
29 4 Complejidad de algoritmos sobre grafos [5,cap 22,23,24]

Total de Horas: 16.

Integración Curricular

Resultados de Programa (ABET)

(A) La habilidad para aplicar conocimientos de matemáticas, ciencias e ingeniería.

(B) La habilidad para analizar un problema e identificar los requerimientos necesarios para su definición y solución.

(C) La habilidad para diseñar, implementar y evaluar procesos y sistemas computacionales.

(D) La habilidad para funcionar en equipos de trabajo.

(E) El entendimiento de la responsabilidad profesional y ética.

(F) La habilidad para comunicarse efectivamente.

(G) La habilidad para analizar los impactos de la computación y la ingeniería en las personas, organizaciones y la sociedad.

(H) El reconocimiento de la necesidad de, y la habilidad para, continuar con el desarrollo profesional.

(I) La habilidad para usar las técnicas, destrezas y herramientas modernas para la práctica de la computación.

(J) La habilidad para aplicar los fundamentos y principios de las matemáticas y de la computación en el modelamiento y diseño de sistemas computacionales de manera que se demuestre comprensión de las ventajas y desventajas en las decisiones de diseño.

(K) La habilidad para aplicar los principios de diseño y desarrollo de software en la construcción de sistemas de diferente complejidad.

Relevancia del curso con los resultados de programa

Resultados de Programa
a b c d e f g h i j k
Relevancia 4 0 0 0 0 1 0 0 0 4 0

1: baja relevancia - 5 alta relevancia

Relación de objetivos del curso con resultados de programa y estrategia de evaluación

Resultados del Programa Indicadores de Desempeño Objetivos/Contenido del Curso Actividades de aprendizaje Instrumentos de medición
(A) Aplicación de Conocimientos (A1) Identificar los fundamentos científicos y los principios de ingeniería que rigen un proceso o sistema. (Conocimiento) (A2) Resolver problemas relacionados con la disciplina y otras áreas por medio de la utilización de conocimientos, modelos y formalismos de las ciencias de la computación, las matemáticas y la ingeniería. (Aplicación) (A4) Interpretar modelos matemáticos para estimar su precisión y confiabilidad. (Comprensión) Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(F) Comunicación efectiva (F2) Comunicarse de manera efectiva de acuerdo al público objetivo haciendo uso correcto del lenguaje, estilo, tiempo y expresión corporal. (Aplicación). (F4) Defender ideas con precisión y claridad. (Evaluación). Cap 3,4 Ejercicios de demostración, sustentación del proyecto Talleres y proyecto
(J) Modelamiento y diseño de sistemas computacionales (J1) Reconocer la importancia del modelamiento cuando se resuelve un problema. (Compresión). (J2) Relacionar conceptos y principios teóricos para la resolución efectiva de un problema. (Síntesis). (J4) Evaluar decisiones de diseño basándose en principios matemáticos y de computación. (Evaluación). Cap 2,4 Exposiciones del profesor, talleres, tareas y proyectos Exámenes, proyecto, talleres y tareas

Recomendaciones del Director del Programa

Reglas del curso

Calificación y Balance del Curso

Instrumento Porcentaje A B C D E F G H I J K
Parcial I 20% 70% 20% 10%
Parcial II 20% 50% 20% 30%
Parcial III 20% 20% 10% 70%
Proyecto I 20% 50% 10% 40%
Talleres 20% 30% 70%

Uso de material en exámenes

No está permitido el uso de notas de clase, bibliografía, computadores personales ni teléfonos celulares. En caso que así se indique se puede utilizar calculadora.

Talleres, Quices y Proyecto

Se deben resolver en forma individual y todas las soluciones deben ser originales, es decir, no es aceptable reutilizar código ni descargar respuestas de internet.

Asistencia

Obligatoria

Matriculación

  1. 2013-1:
  2. 2012-2: 18
  3. 2012-1: 14
  4. 2011-2: 10
  5. 2011-1: 18
  6. 2010-2:

Recursos

Bibliografía

  1. Sipser M. Introduction to the Theory of Computation. Segunda Edición. Thompson Course Technology. 2006.
  2. Linz P. An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers. 4a.Edición. 2006.
  3. Hopcroft John E., Motwani Rajeev, Ullman, Jeffrey D. Introduction to Automata Theory, Languajes and Computation. 3a Edición. Addison Wesley. 2007.
  4. Harel D. Computers Ltd. What they really can't do. Oxford University Press. 2000.
  5. Cormen T. et. al. Introduction to algorithms. Segunda Edición. MIT Press. 2001.
  6. Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. Tercera Edición. Addison-Wesley. 2007.
  7. Garey M. Johnson D. Computers and intractability A guide to the theory of NP-completeness. W.H.Freeman and Company. 1979.
  8. Skiena S. The algorithm design manual. Springer-verlag. 1998.
  9. Herramienta JFLAP, que deben descargar de la página de internet http://www.cs.duke.edu/csed/jflap/ allí deben registrarse para poder bajar el software.

Instalaciones

Salón de clase con computador y proyector.

 
materias/computabilidad.1383927165.txt.gz · Última modificación: 2013/11/08 11:12 por alexvalencia
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki