TEORÍA MATEMÁTICA DE LA COMPUTACIÓN
|
Objetivo:
Ofrecer los conocimientos
formales que sustentan el modelo teórico y conceptual de las computadoras
y del quehacer computacional en su sentido más amplio. Brindar elementos
para el enriquecimiento de la comprensión de la disciplina computacional.
1 Autómatas y lenguajes formales
MA28 Máquinas de estado finito. Definiciones elementales:
estados, símbolos, transiciones. Teoremas de equivalencia entre lenguajes
producidos por gramáticas y lenguajes reconocidos por autómatas.
Jerarquización de autómatas: finitos, autómatas de pila,
máquina de Turing; equivalencias de autómatas.
MA29 Reconocimiento de lenguajes. Relaciones estructurales entre
autómatas y gramáticas. Generación de lenguajes: árboles
de derivación. El problema del reconocimiento. Esquemas de análisis
sintáctico: parsing ascendente y descendente. Algoritmos de análisis
sintáctico para lenguajes independientes del contexto.
MA30 Lenguajes formales. Cadenas, lenguajes y operaciones. Gramáticas
formales: definiciones, operaciones, tipos de lenguajes, ambigüedad, equivalencia,
la jerarquización de Chomsky. Teoremas sobre gramáticas regulares
y sobre gramáticas independientes del contexto. Derivaciones canónicas,
lenguajes recursivos y recursivamente enumerables, los problemas indecidibles
en teoría de lenguajes y su importancia filosófico-conceptual.
2 Sistemas formales
MA31 Máquinas de Turing. Concepto de
computabilidad. Concepto de procedimientos, procedimiento efectivo y algoritmo.
Máquinas de Turing: modelos de computabilidad, problemas indecidibles
(The Halting Problem). Límites de la computabilidad. Relaciones
entre máquinas de Turing y teoría de funciones recursivas. Equivalencias
formales.
MA32 Funciones recursivas. Funciones computables y algoritmos.
Funciones recur-sivas primitivas. Predicados recursivos primitivos. Sistemas
de Post. Producciones, sistemas canónicos. Cálculo Lambda.
3 Computabilidad
MA33 Complejidad. Complejidad y computabilidad. Complejidad
de algoritmos. Teorema del acotamiento. Clases de complejidad. Computabilidad
polinomial. Clases P y NP. Algoritmos NP. Problemas NP completos. Problema
de la satisfabilidad. Problemas intratables demostrables. Complejidad de teorías
de primer orden.
MA34 Decidibilidad. Numeración de Gödel. Conjuntos
recursivamente enumerables. Teorema de Rice. Problema de correspondencia de
Post. Problemas insolubles. Tesis de Church-Turing.
|
|
| |
