Final de práctica — Teoría de la Computación

Temas: todo el curso, con énfasis en las semanas 9 a 15 · Tiempo de trabajo estimado: 120 minutos

Este es un examen de práctica con el formato del final. Sirve para medir cuánto les toma cada tipo de pregunta: resuélvanlo en papel, con el reloj corriendo, y recién después comprueben sus respuestas con los programas de cada semana. Cada pregunta trae su tiempo estimado, y al final hay una tabla que dice con qué programa se comprueba cada una.

Indicaciones

  • Escriban el procedimiento, no solo el resultado: es lo que después van a comparar paso a paso. Si un inciso usa un resultado anterior que les salió mal, sigan con el suyo.
  • Una demostración dice primero qué afirma y qué técnica usa, y después va por pasos cortos, como en los apuntes.
  • Una reducción empieza con una línea que dice de qué problema a cuál va y por qué esa dirección es la que sirve. Recién después se construye algo.
  • Las máquinas se describen en alto nivel, con el formato de la semana 9: pasos numerados, y en la primera línea la forma de la entrada. De cada máquina que deba detenerse, digan por qué se detiene.
  • Pueden usar sin demostrar lo que los apuntes ya demostraron: las propiedades de cierre, que { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} no es regular, que { anbncn }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n \,\} no es libre de contexto, y los problemas difíciles de la lista de abajo. Lo demás se demuestra.

Convenciones del curso

  • El mapa: regulares ⊂\subset libres de contexto ⊂\subset decidibles ⊂\subset reconocibles. ”MM no acepta ww” incluye dos casos: que MM rechace ww y que no se detenga. L(M)L(M) es el conjunto de las cadenas que MM acepta. Un decididor es una máquina que se detiene con toda entrada.
  • Máquinas de Turing: se escriben en el formato .tm de los laboratorios, con una línea estado lee -> destino escribe movimiento por transición. La cinta es infinita solo hacia la derecha. Un par de estado y símbolo sin línea lleva a qrejectq_{\text{reject}}, sin mover el cabezal. Una configuración se escribe u q vu\,q\,v, con el cabezal sobre el primer símbolo de vv.
  • Problemas difíciles que ya tienen demostración. Indecidibles: ATMA_{\mathrm{TM}}, HALTTM\mathrm{HALT}_{\mathrm{TM}}, ETME_{\mathrm{TM}}, REGULARTM\mathrm{REGULAR}_{\mathrm{TM}}, EQTM\mathrm{EQ}_{\mathrm{TM}}, PCP y ALLCFG\mathrm{ALL}_{\mathrm{CFG}}. NP-completos: SAT, 3-SAT y HAMPATH. PSPACE-completos: TQBF y la geografía generalizada. NL-completo: PATH. Una reducción de este examen parte de uno de ellos.
  • Teorema de Rice: toda propiedad no trivial del lenguaje de una máquina de Turing es indecidible. Para aplicarlo se escriben tres cosas: que la propiedad depende solo de L(M)L(M), una máquina que la tiene y una que no.
  • Verificadores: el tiempo de un verificador se mide en la longitud de la instancia, sin contar el certificado. Un certificado mal formado se rechaza. Los vértices de un grafo se numeran desde 1.
  • Fórmulas cuantificadas: 0 es falso y 1 es verdadero. Se evalúan de afuera hacia adentro, en el orden del prefijo, probando primero el valor 0 y después el 1. En el juego de la fórmula, E elige las variables con ∃\exists y A las que llevan ∀\forall; E gana si la matriz queda verdadera.
  • Geografía generalizada: la ficha empieza en el nodo de partida, que ya cuenta como visitado. El jugador I mueve primero. Pierde quien no puede mover a un nodo sin visitar.
  • Freivalds: rr es un vector de ceros y unos. Se calcula x=B⋅rx = B \cdot r, después y=A⋅xy = A \cdot x, y z=C⋅rz = C \cdot r. El vector rr detecta la diferencia si y≠zy \neq z. Las cuentas de este examen son con enteros, sin módulo. La entrada (i,j)(i, j) de una matriz está en la fila ii y la columna jj, contando desde 1.
  • Clases: L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME}. En BPP el error de cada ejecución es a lo sumo 1/31/3.
Parte Preguntas Minutos
A. Repaso de la primera mitad 1–2 17
B. Computabilidad 3–6 40
C. Tiempo: P y NP 7–8 23
D. Espacio 9–10 18
E. Jerarquías, azar y lo que sigue abierto 11–12 22
Total 120

Parte A — Repaso de la primera mitad

Pregunta 1 — Un lenguaje regular y uno que no lo es

Tiempo estimado: 9 min

Sean

L1={ w∈{a,b}∗:∣w∣ es impar y w no contiene aa }L_1 = \{\, w \in \{\mathtt{a}, \mathtt{b}\}^* : \lvert w\rvert \text{ es impar y } w \text{ no contiene } \mathtt{aa} \,\} L2={ xcy:x,y∈{a,b}∗ y ∣x∣=∣y∣ }L_2 = \{\, x\mathtt{c}y : x, y \in \{\mathtt{a}, \mathtt{b}\}^* \text{ y } \lvert x\rvert = \lvert y\rvert \,\}

Por ejemplo, aba\mathtt{aba} y b\mathtt{b} están en L1L_1, y ab\mathtt{ab} y aab\mathtt{aab} no. En L2L_2 están c\mathtt{c} y abcba\mathtt{abcba}, y no están abc\mathtt{abc} ni acbcb\mathtt{acbcb}.

a) Den un DFA para L1L_1: la tabla de transiciones y, para cada estado, una frase que diga qué recuerda.

b) Demuestren que L2L_2 no es regular. Pueden usar el lema de bombeo, escrito como un juego, o un conjunto infinito de cadenas distinguibles dos a dos.

c) Den una gramática libre de contexto para L2L_2 y una derivación de abcba\mathtt{abcba}. ¿En qué nivel del mapa queda L2L_2?

Pregunta 2 — Una máquina de Turing

Tiempo estimado: 8 min

La máquina MM está escrita en el formato de los laboratorios:

states: q0 s0 s1 c0 c1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> s0 0 R
q0 1 -> s1 1 R
s0 0 -> s0 0 R
s0 1 -> s0 1 R
s0 _ -> c0 _ L
s1 0 -> s1 0 R
s1 1 -> s1 1 R
s1 _ -> c1 _ L
c0 0 -> q_accept 0 R
c1 1 -> q_accept 1 R

a) Escriban las configuraciones de MM con la entrada 0110\mathtt{0110} y con la entrada 01\mathtt{01}, desde la inicial hasta que se detiene.

b) ¿Qué lenguaje decide MM? Describan la máquina en el nivel de implementación, en tres o cuatro líneas: qué hace el cabezal y qué recuerda el estado.

c) ¿Cuántos pasos da MM con una entrada de longitud n≥1n \geq 1? ¿Hace falta una máquina de Turing para este lenguaje? Si no hace falta, den una expresión regular.

d) En una o dos frases: ¿qué afirma la tesis de Church-Turing, y por qué no se puede demostrar como un teorema?

Parte B — Computabilidad

Pregunta 3 — Clasificar

Tiempo estimado: 12 min

Para cada lenguaje, digan el nivel más pequeño al que pertenece: regular, libre de contexto, decidible, reconocible, o ninguno de los cuatro. Hacen falta dos argumentos: uno de pertenencia, que es una máquina, una gramática o un algoritmo, y uno de exclusión del nivel anterior, con la técnica que lo demuestra. En c), d) y e) basta ubicar el lenguaje entre decidible, reconocible y ninguno.

a) { 0i1j0k:j=i+k }\{\, \mathtt{0}^i\mathtt{1}^j\mathtt{0}^k : j = i + k \,\}

b) { 0n1n0n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n\mathtt{0}^n : n \geq 0 \,\}. Para la exclusión basta la cadena que eligen y la idea de por qué ningún bombeo sirve.

c) El lenguaje de las descripciones ⟨M⟩\langle M \rangle de las máquinas de Turing que aceptan al menos dos cadenas distintas.

d) El lenguaje de las descripciones ⟨M⟩\langle M \rangle de las máquinas de Turing que aceptan a lo sumo una cadena.

e) El lenguaje de los pares ⟨M,w⟩\langle M, w \rangle tales que MM acepta ww sin que su cabezal salga nunca de las primeras ∣w∣+1\lvert w\rvert + 1 celdas de la cinta.

Pregunta 4 — Indecidible por reducción

Tiempo estimado: 11 min

Sea

INTERTM={ ⟨M1,M2⟩:M1 y M2 son maˊquinas de Turing y L(M1)∩L(M2)≠∅ }.\mathrm{INTER}_{\mathrm{TM}} = \{\, \langle M_1, M_2 \rangle : M_1 \text{ y } M_2 \text{ son máquinas de Turing y } L(M_1) \cap L(M_2) \neq \emptyset \,\}.

a) Demuestren que INTERTM\mathrm{INTER}_{\mathrm{TM}} es indecidible, con una reducción. Escriban primero de qué problema a cuál va. Después, las máquinas que hagan falta, por qué la que construyen se detiene siempre y por qué responde bien en los dos casos.

b) Demuestren que INTERTM\mathrm{INTER}_{\mathrm{TM}} es reconocible. Cuiden que su máquina no se quede esperando a una simulación que no termina.

c) ¿Es reconocible el complemento de INTERTM\mathrm{INTER}_{\mathrm{TM}}? Justifiquen con a), con b) y con un teorema de la semana 9.

d) Alguien escribe: “Demostré que INTERTM≤mATM\mathrm{INTER}_{\mathrm{TM}} \leq_m A_{\mathrm{TM}}, y como ATMA_{\mathrm{TM}} es indecidible, INTERTM\mathrm{INTER}_{\mathrm{TM}} también”. ¿Qué está mal? ¿Qué demuestra en realidad esa reducción?

Pregunta 5 — El teorema de Rice: cuándo sí y cuándo no

Tiempo estimado: 9 min

Para cada propiedad de una máquina de Turing MM, digan si el teorema de Rice se aplica. Si se aplica, escriban las tres comprobaciones. Si no, digan cuál hipótesis falla, con un ejemplo, y si la propiedad es decidible o no.

a) 0∈L(M)\mathtt{0} \in L(M) y 1∉L(M)\mathtt{1} \notin L(M).

b) MM tiene alguna transición que escribe el símbolo blanco.

c) Existe una máquina M′M' con más estados que MM y con L(M′)=L(M)L(M') = L(M).

d) MM se detiene con toda entrada.

e) L(M)L(M) está en la clase P.

Pregunta 6 — La diagonal y la autorreferencia

Tiempo estimado: 8 min

a) La tabla tiene los primeros cuatro renglones y columnas de la tabla de la diagonal, con valores inventados. La casilla de la fila MiM_i y la columna ⟨Mj⟩\langle M_j \rangle dice si MiM_i acepta ⟨Mj⟩\langle M_j \rangle; “no” quiere decir que rechaza o que no se detiene.

⟨M1⟩\langle M_1 \rangle ⟨M2⟩\langle M_2 \rangle ⟨M3⟩\langle M_3 \rangle ⟨M4⟩\langle M_4 \rangle
M1M_1 acepta no no acepta
M2M_2 no no acepta acepta
M3M_3 acepta acepta acepta no
M4M_4 no acepta no no

Escriban las primeras cuatro casillas de la fila de la máquina DD de la semana 9. ¿En qué columna difiere de cada MiM_i? La tabla existe aunque ATMA_{\mathrm{TM}} sea indecidible: ¿qué es, entonces, lo que no puede existir, y en qué casilla aparece la contradicción?

b) Sea

AUTOTM={ ⟨M⟩:M es una maˊquina de Turing que acepta ⟨M⟩ }.\mathrm{AUTO}_{\mathrm{TM}} = \{\, \langle M \rangle : M \text{ es una máquina de Turing que acepta } \langle M \rangle \,\}.

Demuestren que es indecidible con el teorema de recursión, sin reducciones: supongan un decididor y construyan una máquina que obtiene su propia descripción.

c) Digan si cada afirmación es verdadera o falsa, y por qué, en dos líneas.

  1. “El primer teorema de incompletitud dice que hay una afirmación verdadera de la aritmética que ningún sistema formal correcto puede demostrar.”
  2. “Si un sistema formal es incompleto, entonces demuestra alguna afirmación falsa.”

Parte C — Tiempo: P y NP

Pregunta 7 — Certificados y verificadores

Tiempo estimado: 8 min

En un grafo no dirigido, un conjunto de vértices SS es dominante si cada vértice del grafo está en SS o es vecino de algún vértice de SS. Sea

DOM={ ⟨G,k⟩:G es un grafo no dirigido que tiene un conjunto dominante de exactamente k veˊrtices }.\mathrm{DOM} = \{\, \langle G, k \rangle : G \text{ es un grafo no dirigido que tiene un conjunto dominante de exactamente } k \text{ vértices} \,\}.

a) Demuestren que DOM∈NP\mathrm{DOM} \in \mathsf{NP}: digan cuál es el certificado, escriban el verificador y justifiquen su tiempo. ¿Cuántos bits tiene el certificado para un grafo de mm vértices?

b) El grafo GG tiene 7 vértices y estas aristas:

1-2   1-3   2-3   2-4   4-5   5-6   5-7   6-7

Corran su verificador a mano con ⟨G,2⟩\langle G, 2 \rangle y cada uno de estos certificados. Digan cuáles acepta y, de los que rechaza, en qué comprobación falla cada uno.

c1 = 2 5     c2 = 5 1     c3 = 4 7     c4 = 5 5     c5 = 2 8     c6 = 2 5 6

c) ⟨G,1⟩\langle G, 1 \rangle no está en DOM\mathrm{DOM}. ¿Cómo se convence alguien de eso, y cuántos certificados tiene que descartar? En general, ¿en qué clase está el complemento de DOM\mathrm{DOM}, y por qué el verificador de a) no muestra que ese complemento esté en NP?

Pregunta 8 — NP-completitud: el ciclo hamiltoniano

Tiempo estimado: 15 min

Un ciclo hamiltoniano de un grafo dirigido con m≥2m \geq 2 nodos es una lista v1,v2,…,vmv_1, v_2, \ldots, v_m con todos los nodos, una vez cada uno, tal que el grafo tiene el arco de cada viv_i a vi+1v_{i+1} y también el arco de vmv_m a v1v_1. Sea

HAMCYCLE={ ⟨G⟩:G es un grafo dirigido que tiene un ciclo hamiltoniano }.\mathrm{HAMCYCLE} = \{\, \langle G \rangle : G \text{ es un grafo dirigido que tiene un ciclo hamiltoniano} \,\}.

a) Demuestren que HAMCYCLE∈NP\mathrm{HAMCYCLE} \in \mathsf{NP}.

b) Demuestren que HAMCYCLE\mathrm{HAMCYCLE} es NP-difícil, con una reducción desde uno de los problemas de la lista de la portada. Sigan la receta: de qué problema a cuál, qué se construye, las dos direcciones y el tiempo. Apliquen su construcción a esta instancia, con s=1s = 1 y t=4t = 4, y den el ciclo que resulta:

1->2   2->3   3->1   3->4   1->4

c) Una compañera propone una construcción más corta: no agregar nodos, y solo agregar a GG el arco de tt a ss. Den un grafo de tres nodos, con su ss y su tt, en el que esa construcción cambia la respuesta. ¿Cuál de las dos direcciones de la demostración es la que falla?

d) Como HAMCYCLE\mathrm{HAMCYCLE} está en NP, el teorema de Cook-Levin da una reducción HAMCYCLE≤pSAT\mathrm{HAMCYCLE} \leq_p \mathrm{SAT} sin construir nada nuevo. En esa reducción: ¿de qué máquina sale la fórmula, y qué representa una asignación que la cumple? De los cuatro grupos de cláusulas, ¿cuál es el único que cambia cuando se cambia el grafo de entrada por otro cuya codificación tiene la misma longitud? ¿Por qué esta reducción no sirve para el inciso b)?

Parte D — Espacio

Pregunta 9 — Una fórmula cuantificada

Tiempo estimado: 9 min

Sea la matriz

ψ=(x∨y∨z)∧(¬x∨¬y∨z)∧(y∨¬z)∧(x∨¬y∨¬z).\psi = (x \lor y \lor z) \land (\lnot x \lor \lnot y \lor z) \land (y \lor \lnot z) \land (x \lor \lnot y \lor \lnot z).

a) Evalúen a mano φ1=∃x ∀y ∃z  ψ\varphi_1 = \exists x\, \forall y\, \exists z\; \psi, dibujando el árbol. ¿Quién tiene una estrategia ganadora en el juego de φ1\varphi_1? Escríbanla como una regla: qué elige en cada turno, en función de lo que se eligió antes.

b) Evalúen φ2=∃x ∃z ∀y  ψ\varphi_2 = \exists x\, \exists z\, \forall y\; \psi, que tiene la misma matriz. Expliquen la diferencia con a) en términos de quién elige antes que quién.

c) Con los tres cuantificadores ∃\exists, la pregunta es si ψ\psi es satisfacible. ¿Lo es? Den todas las asignaciones que la cumplen.

d) El algoritmo recursivo de la semana 14 evalúa una fórmula de mm variables. ¿Cuántas llamadas hace como máximo, y cuántas están activas a la vez? ¿Cuál de los dos números es el que pone a TQBF en PSPACE? Si las variables con ∃\exists las adivinara una máquina no determinista de espacio polinomial, ¿se saldría de PSPACE? Citen el teorema.

Pregunta 10 — Geografía generalizada

Tiempo estimado: 9 min

El juego se juega en este grafo, y la ficha empieza en aa:

nodes: a b c d e f
start: a
edges:
a b
a f
b d
c b
e c
e d
f b
f e

a) Resuelvan el juego a mano. Para cada primera jugada de I, digan si gana o pierde y con qué respuestas. ¿Quién tiene una estrategia ganadora?

b) Se agrega la arista de ff a dd. ¿Quién gana ahora? Basta revisar lo que cambia.

c) La búsqueda recursiva que resuelve el juego puede tardar un tiempo exponencial en la cantidad de nodos. ¿Por qué, aun así, muestra que la geografía generalizada está en PSPACE? ¿Qué guarda en cada momento?

d) Un problema más fácil sobre el mismo tipo de entrada: dado un grafo dirigido y un nodo de partida, ¿se puede llegar a algún nodo del que no sale ninguna arista? Muestren que está en NL: qué adivina la máquina, qué guarda en la cinta de trabajo y cuántos bits ocupa.

Parte E — Jerarquías, azar y lo que sigue abierto

Pregunta 11 — Freivalds a mano

Tiempo estimado: 10 min

Sean

A=(201130012),B=(120011302),C=(552153815).A = \begin{pmatrix} 2 & 0 & 1 \\ 1 & 3 & 0 \\ 0 & 1 & 2 \end{pmatrix}, \qquad B = \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 1 \\ 3 & 0 & 2 \end{pmatrix}, \qquad C = \begin{pmatrix} 5 & 5 & 2 \\ 1 & 5 & 3 \\ 8 & 1 & 5 \end{pmatrix}.

a) Corran una ronda del algoritmo de Freivalds con r=(0,0,1)r = (0, 0, 1) y otra con r=(1,1,0)r = (1, 1, 0). En cada una escriban B⋅rB \cdot r, A⋅(B⋅r)A \cdot (B \cdot r) y C⋅rC \cdot r, y lo que responde el algoritmo. ¿Qué se puede concluir de cada respuesta, por separado?

b) Les dicen que CC difiere de A⋅BA \cdot B exactamente en dos entradas: la (1,2)(1, 2) y la (3,1)(3, 1). Sin calcular más productos, ¿cuáles de los 8 vectores detectan la diferencia? ¿Con qué probabilidad falla una ronda? ¿Contradice eso al teorema, que habla de 1/21/2?

c) Con la cota del teorema, que vale para cualquier CC incorrecta, ¿cuántas rondas hacen falta para que la probabilidad de error sea menor que 10−1210^{-12}? Muestren que una ronda menos no alcanza.

d) Después de esas rondas, el algoritmo puede responder “iguales” o “distintos”. ¿De cuál de las dos respuestas se puede estar seguro, y por qué? ¿Cuántas rondas hacen falta, como mínimo, para que el algoritmo cumpla la definición de BPP?

Pregunta 12 — Verdadero o falso

Tiempo estimado: 12 min

Digan si cada afirmación es verdadera o falsa, y justifíquenlo en dos o tres líneas, citando el teorema que usan. Una afirmación que dice “se sabe que…” es falsa si lo que afirma sigue abierto. Una afirmación con dos partes es falsa si alguna de las dos lo es: digan cuál.

a) Se sabe que NP⊆PSPACE\mathsf{NP} \subseteq \mathsf{PSPACE} y que NP≠EXPTIME\mathsf{NP} \neq \mathsf{EXPTIME}.

b) Si TQBF∈NP\mathrm{TQBF} \in \mathsf{NP}, entonces NP=PSPACE\mathsf{NP} = \mathsf{PSPACE}.

c) Si mañana se publica un algoritmo de tiempo polinomial para HAMCYCLE\mathrm{HAMCYCLE}, el problema de la pregunta 8, se sigue que 3-SAT está en P y también que TQBF está en P.

d) Por el teorema de jerarquía de tiempo, SAT no se puede decidir en tiempo O(n3)O(n^3).

e) Existe un lenguaje que se decide en espacio O(n3)O(n^3) y que no está en NL.

f) Como BPP⊆PSPACE\mathsf{BPP} \subseteq \mathsf{PSPACE}, todo algoritmo probabilístico de tiempo polinomial se puede reemplazar por uno determinista de tiempo polinomial.

g) Se sabe que ATMrelojA_{\mathrm{TM}}^{\mathrm{reloj}}, el problema de aceptación con un tope de pasos escrito en binario, no está en P ni en NP.

h) Si P=NP\mathsf{P} = \mathsf{NP}, entonces todo lenguaje de coNP está en P, y el problema de la parada sigue siendo indecidible.

Cómo comprobar sus respuestas

Después de resolver el examen en papel, pasen sus respuestas a archivos y compárenlas con los programas del curso. En las demás preguntas no hay nada que ejecutar: comparen su demostración, paso a paso, con la sección de los apuntes que se indica.

Pregunta Qué escribir Con qué comparar
1 Su DFA, en un archivo .dfa; su gramática, en un archivo .cfg run_dfa de la semana 1; to_chomsky y cyk de la semana 5
2 La máquina MM, en un archivo .tm history de la semana 10 para las configuraciones; run_tm de la semana 7 para contar pasos
3 Su gramática de a), en un archivo .cfg to_chomsky y cyk de la semana 5; las demás, con El mapa completo del curso de la semana 15
4 Nada Las demostraciones de ETME_{\mathrm{TM}} y de Reducción por función, en la semana 10
5 Nada Las secciones Cómo se usa y Lo que Rice no dice de la semana 10
6 Nada Dónde está la diagonal, en la semana 9, y Primer uso, en la semana 11
7 Su verificador, como una función al estilo de verifiers.h Los verificadores de la semana 12 y sus pruebas
8 Nada La receta de la semana 13 y la demostración de HAMPATH
9 Las dos fórmulas, en archivos .qbf eval_qbf --tree de la semana 14
10 Los dos grafos, en archivos .graph geography --moves de la semana 14
11 Las tres matrices, en una copia de freivalds_demo.cpp La tabla de los 8 vectores que imprime ese programa, en la semana 15
12 Nada La cadena, par por par y Lo que sigue abierto, en la semana 15

Lista de resultados para el final

Al corregir su práctica, marquen lo que ya pueden hacer. Cada línea es un resultado de aprendizaje del programa del curso, con las semanas donde se enseña y las preguntas que lo ejercitan, de este final y del parcial de práctica. Si una línea queda sin marcar, vuelvan a esas semanas y rehagan esas preguntas sin mirar los apuntes.

  • Puedo diseñar un autómata finito, una expresión regular o una gramática para un lenguaje dado, y demostrar que reconoce exactamente ese lenguaje. Semanas 1, 2, 3 y 5. Preguntas 1 a), 1 c), 2 c) y 3 a). En el parcial de práctica: preguntas 1, 6 b), 6 c), 8 d), 9 c) y 11.
  • Puedo convertir entre DFA, NFA y expresiones regulares, y minimizar un DFA, a mano y con un programa. Semanas 2, 3 y 4. Este final no lo pregunta. En el parcial de práctica: preguntas 2, 3 y 5.
  • Puedo demostrar que un lenguaje no es regular o no es libre de contexto, con el lema de bombeo o con cadenas distinguibles. Semanas 4 y 6. Preguntas 1 b), 3 a) y 3 b). En el parcial de práctica: preguntas 4, 5 f), 9 y 11.
  • Puedo decidir si una cadena pertenece al lenguaje de una gramática con el algoritmo CYK, y relacionar gramáticas con autómatas de pila. Semanas 5 y 6. Este final solo lo toca al comprobar las preguntas 1 c) y 3 a) con cyk. En el parcial de práctica: preguntas 7 y 8.
  • Puedo describir una máquina de Turing en sus tres niveles de detalle y explicar qué afirma la tesis de Church-Turing. Semana 7. Pregunta 2, y las máquinas en alto nivel de las preguntas 3, 4 y 6. En el parcial de práctica: preguntas 10, 12 e) y 12 f).
  • Puedo demostrar que un problema es indecidible o no reconocible, por diagonalización o con una reducción en la dirección correcta. Semanas 9, 10 y 11. Preguntas 3 c), 3 d), 3 e), 4, 5 y 6.
  • Puedo ubicar un problema en P, NP, coNP o PSPACE, y demostrar que es completo para su clase con una reducción en tiempo polinomial. Semanas 12, 13 y 14. Preguntas 7, 8, 9 d), 10 c), 10 d) y 12.
  • Puedo explicar la demostración del teorema de Cook-Levin y lo que implican los teoremas de jerarquía. Semanas 13 y 15. Preguntas 5 e), 8 d), 12 d), 12 e) y 12 g).
  • Puedo implementar en C++ las construcciones del curso: simuladores de cada modelo, conversiones entre modelos y reducciones que se pueden ejecutar. Laboratorios de las semanas 1 a 7 y 9 a 15. En papel no se practica: es la tabla de la sección anterior, y las preguntas 9, 10 y 11 son las que más se parecen a lo que hacen eval_qbf, geography y freivalds_demo.
  • Puedo explicar qué preguntas del área siguen abiertas y qué cambiaría con cada respuesta. Semanas 12 a 15. Preguntas 7 c), 9 d), 11 d) y 12.