Autómatas y Lenguajes Formales
Teoría de la Computación
1 ¿De qué se trata el curso?
Éste es un curso introductorio a la Teoría de la Computación. Se estudian diferentes modelos de cómputo (y problemas que pueden resolver), todos enmarcados en una jerarquía que irá apareciendo naturalmente conforme avancemos con el temario hasta llegar a la máquina automática propuesta por Alan M. Turing, hoy conocida con Máquina de Turing en su honor. Cada nivel de la jerarquía estará descrito por una máquina abstracta, un lenguaje formal y una gramática formal.
Este curso, además de ayudar a las personas estudiantes a obtener una noción formal de qué es un cómputo, permite adquirir herramientas necesarias para desempeñarse satisfactoriamente en cursos como Complejidad Computacional y Compiladores. Utilizaremos el temario oficial del curso como guía.
2 Evaluación del curso
Opción A
50%
Exámenes
20%
Tareas
20%
Implementación
10%
Mini-exámenes
+10%
Exposición (opcional)
Desglose de la evaluación de la opción A
Exámenes parciales (50%): se realizará un examen por cada unidad de temario definida (apróx. 4 exámenes)
Tareas (20%): se dejarán al menos dos tareas por cada unidad de temario definida (apróx. 8 tareas). Se podrán resolver de manera individual o en equipos de hasta 3 personas.
Implementación creciente (20%): se realizará una implementación continua de los conceptos adquiridos para asentar los conocimientos estudiados en el curso. Se dará seguimiento a este rubro en las sesiones de ayudantía. Se podrán realizar de manera individual o en equipos de hasta 3 personas.
Mini-exámenes diarios (10%): aplicados al inicio de cada sesión (sea del profesor o del ayudante).
(Opcional, extra) Exposición (+10%): de un artículo o tema asignado desde mediados del semestre.
Notas de la opción A:
Quien lo deseé podrá reponer un examen parcial. No habrá reposiciones de los mini-exámenes.
Para el cálculo del promedio de exámenes, desecharemos la calificación más baja de sus exámenes si tienen al menos el 80% de los exámenes diarios aprobados. :)))
No habrá examen final.
Para tener NP deben no tenerse más de dos entregas calificadas en cualquier rubro y ni un examen presentado (de ninguno de lo dos tipos que tenemos), además de solicitarlo por correo al profesor del curso.
Opción B
60%
Tareas-examen a casa
20%
Implementación
20%
Mini-exámenes
+10%
Exposición (opcional)
Desglose de la evaluación de la opción B
Tareas-examen (60%): se realizará una o dos tareas-examen por cada unidad de temario definida (apróx. 8 tarea-exámenes). Se podrán realizar de manera individual o en equipos de hasta 3 personas.
Implementación creciente (20%): se realizará una implementación continua de los conceptos adquiridos para asentar los conocimientos estudiados en el curso. Se dará seguimiento a este rubro en las sesiones de ayudantía. Se podrán realizar de manera individual o en equipos de hasta 3 personas.
Mini-exámenes diarios (20%): aplicados al inicio de cada sesión (sea del profesor o del ayudante).
(Opcional, extra) Exposición (+10%): de un artículo o tema asignado desde mediados del semestre.
Notas de la opción B:
Podrán reponer máximo dos tareas-examen si presentaron todos los mini-exámenes correspondientes a la unidad de la tarea-examen.
Para el cálculo del promedio de exámenes, desecharemos la calificación más baja de sus tarea-exámenes si tienen al menos 8 en la evaluación del rubro de implementación creciente. :)))
No habrá examen final.
Para tener NP deben no tenerse más de dos entregas calificadas en cualquier rubro y ni una sola tarea-examen presentada, además de solicitarlo por correo al profesor del curso.
3 Dinámica del curso
Detalles del curso para el semestre 2023-2
El canal de comunicación oficial será un aula de Google Classroom. Por otro lado, tendremos un espacio de Google Chat funcionando como el canal de mensajes más amigable, o bien, si lo prefieren, un chat grupal en Telegram lo cual se votará en la primera sesión.
La opción de evaluación se votará en la primera sesión.
Como en el curso de Filosofía de la Ciencia de la Computación, contaremos con un par de charlas invitadas relevantes a la temática del curso para nutrir su formación.
Iniciaremos con la presentación del curso y con el temario en el primer día de clases, y ahí aclararemos todas las dudas.
En este curso (como en otros, realmente) no se sugiere saltarse las ayudantías, por lo que les rogamos no tener materias encimadas. Si tienen que hacerlo por causas de fuerza mayor, exigencias económicas (e.g. por sostener una beca) o cualquier otra razón, les pedimos nos lo comenten durante la primera sesión para encontrar alternativas. Estamos para ayudarles, no para obstaculizarles.
Las exposiciones las haremos al final del semestre durante las semanas de exámenes (más detalles al respecto en la primera sesión).
Modalidad
Clases presenciales en el Laboratorio de Ciencias de la Computación 3, último piso del Edificio Tlahuizcalpan.
Sesión de asesorías opcionales abiertas en la Sala de Maestros, primer piso del Edificio Tlahuizcalpan (junto al elevador)
Personal académico
Clases con el profesor: Lic. en C. Comp. Enrique Francisco Soto Astorga
Clases con el ayudante: José Manuel Madrigal Ramírez
Sesiones de asesoría opcionales abiertas: Ambos según disponibilidad (se avisará por Classroom y por la mensajería del grupo)
Horario (versión final actualizada el 29 de junio de 2023)
Lunes
Lab. C.C. 3
09:00 - 10:00
Martes
Lab. C.C. 3
09:00 - 10:00
Miércoles
Lab. C.C. 3
09:00 - 10:00
Jueves
Lab. C.C. 3
09:00 - 10:00
Viernes
Lab. C.C. 3
09:00 - 10:00
Sala de Maestros
15:00 - 19:00
4 Temario adaptado del oficial
Par este curso seguiremos el temario oficial y le haremos adaptaciones que consideramos vitales para darle un giro especial al contenido. De cualquier forma, la prioridad del curso será revisar al menos los tópicos incluídos en el temario oficial y, si hay tiempo y no hay paros, revisar lo extraordinario. Estamos considerando tiempos de holgura suficientes para sobrevivir a un paro, así que esperamos llegar al final del curso sin problemas.
I. Introducción
II. Gramáticas tipo-3, lenguajes regulares y máquinas finitas
III. Gramáticas tipo-2, lenguajes libres de contexto y máquinas con pila
IV. Gramáticas tipo-1, lenguajes dependientes de contexto y máquinas acotadas
V. Gramáticas tipo-0: lenguajes recursivamente enumerables y Máquinas de Turing
VI. Computabilidad y decidibilidad
VII. (opcional, tal vez no lleguemos) Temas selectos
5 Bibliografía básica
[1] Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2007). Introduction to Automata Theory, Languages, and Computation 3th Ed. Pearson Education.
[2] Viso-Gurovich, E. (2008) Introducción a la teoría de la computación. Las Prensas de Ciencias.