A menudo escucho a personas hablando de computación paralela y computación distribuida , pero tengo la impresión de que no hay un límite claro entre los 2, y las personas tienden a confundirlo con bastante facilidad, aunque creo que es muy diferente: La computación paralela está más estrechamente...
Sabemos que el problema de detención (en máquinas de Turing) es indecidible para las máquinas de Turing. ¿Hay alguna investigación sobre qué tan bien la mente humana puede manejar este problema, posiblemente ayudado por las máquinas de Turing o las computadoras de uso general? Nota : Obviamente,...
Estoy tratando de escribir un script que genere gráficos aleatorios y necesito saber si un borde en un gráfico ponderado puede tener el valor 0. en realidad tiene sentido que 0 pueda usarse como el peso de una arista, pero he estado trabajando con gráficos en los últimos días y nunca he visto un...
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...
Hay muchas aplicaciones donde se usa un generador de números pseudoaleatorios. Entonces, las personas implementan uno que piensan que es genial solo para descubrir más tarde que es defectuoso. Algo así sucedió recientemente con el generador de números aleatorios de Javascript. RandU mucho antes...
Tengo un programa lineal entero (ILP) con algunas variables que están destinadas a representar valores booleanos. Las están restringidas a ser enteros y a contener 0 o 1 ( ).x i 0 ≤ x i ≤ 1xixix_ixixix_i0≤xi≤10≤xi≤10 \le x_i \le 1 Quiero expresar operaciones booleanas en estas variables con valor...
Si tengo una lista de valores clave del 1 al 100 y quiero organizarlos en una matriz de 11 cubos, me han enseñado a formar una función mod H=kmod 11H=kmod 11 H = k \bmod \ 11 Ahora todos los valores se colocarán uno tras otro en 9 filas. Por ejemplo, en el primer depósito habrá 0,11,22…0,11,22…0,...
¿Alguien podría explicar la diferencia entre los tipos dependientes y los tipos de refinamiento? Según tengo entendido, un tipo de refinamiento contiene todos los valores de un tipo que cumple un predicado. ¿Existe una característica de los tipos dependientes que los distingue? Si ayuda, me...
Tengo una comprensión de alto nivel del problema y entiendo que si se "probara" absolutamente que es cierto con una solución provista, se abriría la puerta para resolver numerosos problemas dentro del ámbito de la informática.P=NPP=NPP=NP Mi pregunta es, si alguien publicara una prueba...
Leí en este tutorial de programación de ensamblaje que 8 bits se usan para datos mientras que 1 bit es para paridad, que luego se usa para detectar errores de paridad (causados por fallas de hardware o perturbaciones eléctricas). ¿Es esto
¿Existe un conjunto de construcciones de lenguaje de programación en un lenguaje de programación para que pueda considerarse Turing Complete? Por lo que puedo decir de Wikipedia , el lenguaje debe admitir la recursividad o, al parecer, debe poder ejecutarse sin detenerse. ¿Es esto todo lo que hay...
Me he encontrado con muchos algoritmos de clasificación durante mis estudios de secundaria. Sin embargo, nunca sé cuál es el más rápido (para una matriz aleatoria de enteros). Entonces mis preguntas son: ¿Cuál es el algoritmo de clasificación más rápido conocido actualmente? Teóricamente, ¿es...
¿Son todas las cadenas de código Morse exclusivamente descifrables? Sin los espacios, ......-...-..---.-----.-..-..-.. podría ser, Hello Worldpero tal vez la primera letra es una 5, de hecho, parece muy poco probable que una secuencia arbitraria de puntos y guiones deba tener una traducción...
Los lenguajes de programación seguros (PL) están ganando popularidad. Me pregunto cuál es la definición formal de PL seguro. Por ejemplo, C no es seguro, pero Java es seguro. Sospecho que la propiedad "segura" debería aplicarse a una implementación de PL en lugar de a la propia PL. Si es así,...
Estoy interesado en la complejidad temporal de un compilador. Claramente esta es una pregunta muy complicada ya que hay muchos compiladores, opciones de compilador y variables a considerar. Específicamente, estoy interesado en LLVM pero estaría interesado en cualquier pensamiento que las personas...
Estoy de acuerdo en que una máquina de Turing puede resolver "todos los posibles problemas matemáticos". Pero eso se debe a que es solo una representación de la máquina de un algoritmo: primero haga esto, luego haga eso, finalmente obtenga eso. Quiero decir que cualquier cosa que sea solucionable...
Siempre me he preguntado por qué los procesadores se detuvieron en 32 registros. Es, con mucho, la pieza más rápida de la máquina, ¿por qué no simplemente hacer procesadores más grandes con más registros? ¿No significaría eso menos ir a la
Conozco el concepto general de recursión. Encontré el concepto de recursión de la cola mientras estudiaba el algoritmo de clasificación rápida. En este video del algoritmo de clasificación rápida del MIT a las 18:30 segundos, el profesor dice que este es un algoritmo recursivo de cola. No me queda...
En computación cuántica, ¿cuál es el modelo equivalente de una máquina de Turing? Para mí está bastante claro cómo los circuitos cuánticos pueden construirse a partir de puertas cuánticas, pero ¿cómo podemos definir una máquina cuántica de Turing (QTM) que realmente pueda beneficiarse de los...
Los problemas de la mochila se resuelven fácilmente mediante programación dinámica. La programación dinámica se ejecuta en tiempo polinomial; Por eso lo hacemos, ¿verdad? Sin embargo, he leído que en realidad es un problema NP-completo, lo que significaría que resolver el problema en un problema...