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 no es regular, que 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 libres de contexto decidibles reconocibles. ” no acepta ” incluye dos casos: que rechace y que no se detenga. es el conjunto de las cadenas que acepta. Un decididor es una máquina que se detiene con toda entrada.
- Máquinas de Turing: se escriben en el formato
.tmde los laboratorios, con una líneaestado lee -> destino escribe movimientopor transición. La cinta es infinita solo hacia la derecha. Un par de estado y símbolo sin línea lleva a , sin mover el cabezal. Una configuración se escribe , con el cabezal sobre el primer símbolo de . - Problemas difíciles que ya tienen demostración. Indecidibles: , , , , , PCP y . 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 , 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 y A las que llevan ; 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: es un vector de ceros y unos. Se calcula , después , y . El vector detecta la diferencia si . Las cuentas de este examen son con enteros, sin módulo. La entrada de una matriz está en la fila y la columna , contando desde 1.
- Clases: . En BPP el error de cada ejecución es a lo sumo .
| 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
Por ejemplo, y están en , y y no. En están y , y no están ni .
a) Den un DFA para : la tabla de transiciones y, para cada estado, una frase que diga qué recuerda.
b) Demuestren que 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 y una derivación de . ¿En qué nivel del mapa queda ?
Pregunta 2 — Una máquina de Turing
Tiempo estimado: 8 min
La máquina 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 con la entrada y con la entrada , desde la inicial hasta que se detiene.
b) ¿Qué lenguaje decide ? 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 con una entrada de longitud ? ¿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)
b) . 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 de las máquinas de Turing que aceptan al menos dos cadenas distintas.
d) El lenguaje de las descripciones de las máquinas de Turing que aceptan a lo sumo una cadena.
e) El lenguaje de los pares tales que acepta sin que su cabezal salga nunca de las primeras celdas de la cinta.
Pregunta 4 — Indecidible por reducción
Tiempo estimado: 11 min
Sea
a) Demuestren que 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 es reconocible. Cuiden que su máquina no se quede esperando a una simulación que no termina.
c) ¿Es reconocible el complemento de ? Justifiquen con a), con b) y con un teorema de la semana 9.
d) Alguien escribe: “Demostré que , y como es indecidible, 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 , 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) y .
b) tiene alguna transición que escribe el símbolo blanco.
c) Existe una máquina con más estados que y con .
d) se detiene con toda entrada.
e) 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 y la columna dice si acepta ; “no” quiere decir que rechaza o que no se detiene.
| acepta | no | no | acepta | |
| no | no | acepta | acepta | |
| acepta | acepta | acepta | no | |
| no | acepta | no | no |
Escriban las primeras cuatro casillas de la fila de la máquina de la semana 9. ¿En qué columna difiere de cada ? La tabla existe aunque sea indecidible: ¿qué es, entonces, lo que no puede existir, y en qué casilla aparece la contradicción?
b) Sea
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.
- “El primer teorema de incompletitud dice que hay una afirmación verdadera de la aritmética que ningún sistema formal correcto puede demostrar.”
- “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 es dominante si cada vértice del grafo está en o es vecino de algún vértice de . Sea
a) Demuestren que : digan cuál es el certificado, escriban el verificador y justifiquen su tiempo. ¿Cuántos bits tiene el certificado para un grafo de vértices?
b) El grafo 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 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) no está en . ¿Cómo se convence alguien de eso, y cuántos certificados tiene que descartar? En general, ¿en qué clase está el complemento de , 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 nodos es una lista con todos los nodos, una vez cada uno, tal que el grafo tiene el arco de cada a y también el arco de a . Sea
a) Demuestren que .
b) Demuestren que 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 y , 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 el arco de a . Den un grafo de tres nodos, con su y su , 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 está en NP, el teorema de Cook-Levin da una reducción 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
a) Evalúen a mano , dibujando el árbol. ¿Quién tiene una estrategia ganadora en el juego de ? Escríbanla como una regla: qué elige en cada turno, en función de lo que se eligió antes.
b) Evalúen , 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 , la pregunta es si 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 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 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 :
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 a . ¿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) Corran una ronda del algoritmo de Freivalds con y otra con . En cada una escriban , y , y lo que responde el algoritmo. ¿Qué se puede concluir de cada respuesta, por separado?
b) Les dicen que difiere de exactamente en dos entradas: la y la . 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 ?
c) Con la cota del teorema, que vale para cualquier incorrecta, ¿cuántas rondas hacen falta para que la probabilidad de error sea menor que ? 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 y que .
b) Si , entonces .
c) Si mañana se publica un algoritmo de tiempo polinomial para , 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 .
e) Existe un lenguaje que se decide en espacio y que no está en NL.
f) Como , todo algoritmo probabilístico de tiempo polinomial se puede reemplazar por uno determinista de tiempo polinomial.
g) Se sabe que , el problema de aceptación con un tope de pasos escrito en binario, no está en P ni en NP.
h) Si , 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 , 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 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,geographyyfreivalds_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.