titulo

TEORÍA DE LA COMPUTACIÓN
Semestre:
Horas:
Hrs/sem:
Créditos:
Clave:

Primero
45 T 15 P
3
7
MCC-02

DESCRIPCIÓN DE LA ASIGNATURA:
Los algoritmos son parte medular del estudio de lasciencias computacionales y
para entenderlos plenamente es necesario conocer también las capacidades y
limitaciones de las computadoras. Para ello estudiaremos la teoría fundamental de
los autómatas,del cómputo y de la complejidad algorítmica utilizando métodos
matemáticos. Asimismo relacionaremos los resultados teóricos con aspectos
prácticos.
Los autómatas son máquinas abstractas capaces dereconocer numerosos
patrones de símbolos, conocidos como lenguajes. La teoría fundamental del
cómputo por su parte busca formalizar el concepto de computadora y descubre
hasta donde puede emplearseésta para resolver problemas. La complejidad
algorítmica establece métodos para la medición del desempeño de los algoritmos,
principalmente en términos de tiempo y memoria requeridos para elprocesamiento. Estos tres grandes temas son esenciales para el buen
entendimiento de las ciencias computacionales.
RECURSOS DIDÁCTICOS:
Conferencia: acetatos, pizarrón.
Comisión (equipos): computadora.OBJETIVO:
El alumno utilizará estrategias formales de demostración computacional que le
permitan resolver problemas reales de manera eficiente.
CONTENIDO:
1. Introducción
(12 horas)
Objetivo:Conocer los principales modelos de formales de computación, así como
su historia.
1.1 Modelos formales de computación.
1.2 Máquinas de Turing.
1.3 Cálculo Lambda.
1.4 Redes de Petri.
2. LenguajesRegulares
(12 horas)
Objetivo: Construir Autómatas Finitos para el reconocimiento y análisis de
Lenguajes Regulares.
2.1 Autómata Finito
2.2 No Determinismo
2.3 Expresiones Regulares

2.4Lenguajes No Regulares
3. Lenguajes Libres de Contexto
(12 horas)
Objetivo: Estudiar las características de los Lenguajes Libres de Contexto y los
autómatas de pila.
3.1 Gramáticas Libres de...