Teoría de la Computación

Calendario

Semana Fecha Clase / actividad Evaluación Sec. Sipser Sec. Navarro Handout Slides
1 Mar. 4 ago. 1.1 Introducción al curso — 0.2 1.4 PDF PDF
Animadas
1 Jue. 6 ago. 1.2 Autómatas finitos deterministas — 1.1 2.2 PDF PDF
Animadas
2 Mar. 11 ago. 1.3 Autómatas finitos no deterministas — 1.2 2.3 PDF PDF
Animadas
2 Jue. 13 ago. 1.4 Equivalencia entre AFND y AFD, operaciones regulares y expresiones regulares — 1.2.2 y 1.3.1 2.5 y 2.7 PDF PDF
Animadas
3 Mar. 18 ago. 1.5 Lenguajes regulares — 1.3.2 2.1
2.4–2.61 		PDF PDF
Animadas
3 Jue. 20 ago. 1.6 Lenguajes no regulares — 1.4 2.8 PDF PDF
Animadas
4 Mar. 25 ago. 2.1 Gramáticas libres de contexto — 2.1.1-2.1.3 3.1-3.2 PDF PDF
Animadas
4 Jue. 27 ago. 2.2 Autómatas de pila — 2.2.1-2.2.2 3.3-3.4 PDF PDF
Animadas
5 Mar. 1 sept. 2.3 Equivalencia entre autómatas de pila y gramáticas libres de contexto — 2.2.3 3.4-3.5 PDF PDF
Animadas
5 Jue. 3 sept. 2.4 Ambigüedad y forma normal de Chomsky — 2.1.4-2.1.5 3.1 y 3.92 PDF PDF
Animadas
6 Mar. 8 sept. 2.5 Lenguajes no libres de contexto — 2.3 3.6 PDF PDF
Animadas
6 Jue. 10 sept. 3.1 Máquinas de Turing y sus lenguajes — 3.1 4.1-4.2 PDF PDF
Animadas
7 Mar. 22 sept. 3.1 Máquinas de Turing y sus lenguajes (continuación) — 3.1 4.1-4.2 PDF PDF
Animadas
7 Jue. 24 sept. 3.2 Variantes de máquinas de Turing — 3.2 4.4 PDF PDF
Animadas
8 Mar. 29 sept. 3.3 No determinismo y enumeradores — 3.2 4.5 + 5.2 PDF PDF
Animadas

Bibliografía

  1. El algoritmo presentado en la sección 2.6 es «distinto» del que vimos en clase. ↩

  2. Sólo los fragmentos que corresponden a Ambigüedad y Forma normal de Chomsky. ↩