Preguntas que piden ayuda para desarrollar la intuición de conceptos formales o complejos.
Creo que tengo una comprensión razonable de complejidades como O(1)O(1)\mathcal{O}(1) , Θ(n)Θ(n)\Theta(n) y Θ(n2)Θ(n2)\Theta(n^2) . En términos de una lista, O(1)O(1)\mathcal{O}(1) es una búsqueda constante, por lo que solo está encabezando la lista. Θ(n)Θ(n)\Theta(n) es donde recorrería toda la...
Entiendo la prueba de la indecidibilidad del problema de detención (dada, por ejemplo, en el libro de texto de Papadimitriou), basada en la diagonalización. Si bien la prueba es convincente (entiendo cada paso), no es intuitiva para mí en el sentido de que no veo cómo alguien la derivaría,...
Esta pregunta fue inspirada por un comentario en StackOverflow . Además de conocer los problemas NP-completos del libro de Garey Johnson, y muchos otros; ¿Existe una regla general para saber si un problema se parece a un NP completo? No busco algo riguroso, sino algo que funcione en la mayoría de...
Soy un estudiante graduado que está tomando un curso de teoría de la computación y tengo serios problemas para producir contenido una vez que me lo piden. Puedo seguir el libro de texto (Introducción a la teoría de la computación de Michael Sipser) y las conferencias; sin embargo, cuando se me pide...
A veces es fácil identificar la complejidad temporal de un algoritmo si lo examino cuidadosamente. Los algoritmos con dos bucles anidados de son obviamente . Los algoritmos que exploran todas las combinaciones posibles de grupos de dos valores son obviamenteN 2 N 2
Pensé que entendía el tipeo dependiente (DT) correctamente, pero la respuesta a esta pregunta: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% B6f-to-create-intuitionistic-type-theory me ha hecho pensar lo contrario. Después de leer sobre DT y tratar de entender lo que son, intento...
A continuación, supongamos que estamos trabajando con una máquina Turing de cinta infinita. Al explicar la noción de la complejidad del tiempo a alguien, y por qué se mide en relación con el tamaño de entrada de una instancia, me topé con la siguiente afirmación: [..] Por ejemplo, es natural...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...
Recibo la prueba de pasar de un enumerador a una máquina de Turing (sigo ejecutando el enumerador y ver si coincide con la entrada) pero no veo cómo funciona la otra manera. Según mis notas y el libro (Introducción a la teoría de la computación - Sipser), para obtener el enumerador de Turing de...
Dado un lenguaje , ¿cómo puedo decir directamente, sin mirar las reglas de producción, que este lenguaje no es regular?L = { anortesinorteCnorte}L={anbncn} L= \{a^n b^n c^n\} Podría usar el lema de bombeo, pero algunos chicos dicen simplemente mirando la gramática que este no es uno normal. ¿Como...
He leído muchos documentos sobre convolución en el procesamiento de imágenes, y la mayoría de ellos dicen acerca de su fórmula, algunos parámetros adicionales. Nadie explica la intuición y el significado real detrás de hacer convolución en una imagen. Por ejemplo, la intuición de derivación en el...
No estoy seguro de verlo. Por lo que entiendo, los bordes y los vértices son complementos entre sí y es bastante sorprendente que exista esta diferencia. ¿Hay una manera buena / rápida / fácil de ver que, de hecho, encontrar un camino hamiltoniano debería ser mucho más difícil que encontrar un...
Si tiene un lenguaje L, sin hacer ninguna prueba, ¿hay alguna manera de saber si es reconocible, co-reconocible o decidible? Básicamente, cualquier pista o truco que se pueda usar para contar. ¿O tal vez los patrones comunes a buscar para saber de qué tipo