CC30B Fundamentos de la Ciencia de la Computación
10 UD

  1. Requisitos

    2. CC20A, MA26B

  2. Objetivos

    3. Conocer qué problemas puede resolver un computador a través de diversos modelos simples de computación. Estos modelos son usados en diversas áreas como la construcción de compiladores (análisis léxico y sintáctico), sistemas de entrada y salida de datos discretos, editores de texto, búsqueda de patrones, etc.

  3. Programa

    1. Cadenas y lenguajes

      2. Conceptos básicos de alfabeto, cadena y operaciones asociadas. Lenguajes. Representación finita de lenguajes.

    2. Lenguajes regulares y autómatas finitos

      3. Expresiones regulares. Lenguajes regulares. Modelo simple de un computador. Autómata finito. Propiedades. Determinismo y no determinismo. Equivalencia entre ambos modelos. Equivalencia entre autómatas y lenguajes regulares. Lema Pumping. Igualdad entre lenguajes regulares.

    3. Lenguajes libres del contexto y autómatas de pila

      4. Gramáticas libres del contexto. Derivación de palabras. Lenguajes libres del contexto. Autómatas de pila. Propiedades. Determinismo y no determinismo. Lema Pumping. Equivalencia entre autómatas de pila y lenguajes libres del contexto.

    4. Máquinas de Turing y Computabilidad

      5. Modelo general de un computador. Gramáticas sensibles al contexto. Máquina de Turing. Variaciones del modelo. No determinismo. Decidibilidad. Problema de la parada. Modelos alternativos. Tesis de Church.

    5. Problemas NP-Completos

      6. Complejidad computacional. Las clases P y NP. Problemas NP-completos. NP-completitud de SAT. Reducción de problemas.

  4. Bibliografía

    1. H. Lewis y C. Papadimitrou. Elements of the Theory of Computation. Prentice-Hall, 1981.

    2. J. Hopcroft y J. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.