¿Hay algún problema conocido en N PNP\mathsf{NP} (y no en PAGSP\mathsf{P} ) que no sea N PNP\mathsf{NP} Complete? Tengo entendido que actualmente no hay problemas conocidos en este caso, pero no se ha descartado como una posibilidad. Si hay un problema que es NPNP\mathsf{NP} (y no PP\mathsf{P} )...
Después de leer varias fuentes, todavía estoy confundido acerca de los hilos de nivel de usuario y kernel. En particular: Los hilos pueden existir tanto a nivel de usuario como a nivel de núcleo ¿Cuál es la diferencia entre el nivel de usuario y el nivel de kernel?
En su artículo seminal de 1987, Dana Angluin presenta un algoritmo de tiempo polinómico para aprender un DFA a partir de consultas de membresía y consultas teóricas (contraejemplos a un DFA propuesto). Ella muestra que si está tratando de aprender un DFA mínimo con estados, y su contraejemplo más...
Hay nnn contenedores mmm tipo de bolas. El iii th bin tiene etiquetas ai,jai,ja_{i,j} para 1≤j≤m1≤j≤m1\leq j\leq m , es el número esperado de bolas de tipo jjj . Comienzas con bjbjb_j bolas de tipo jjj . Cada bola de tipo jjj tiene peso wjwjw_j , y desea colocar las bolas en los contenedores de...
EDITAR: ahora he hecho una pregunta similar sobre la diferencia entre categorías y conjuntos. Cada vez que leo acerca de la teoría de tipos (que ciertamente es bastante informal), no puedo entender realmente en qué se diferencia de la teoría de conjuntos, concretamente . Entiendo que hay una...
Es bien sabido que este algoritmo 'ingenuo' para barajar una matriz intercambiando cada elemento con otro elegido al azar no funciona correctamente: for (i=0..n-1) swap(A[i], A[random(n)]); Específicamente, dado que en cada una de las iteraciones, se realiza una de las elecciones (con...
En mi clase, un estudiante preguntó si todos los autómatas finitos podían dibujarse sin cruzar bordes (parece que todos mis ejemplos lo hicieron). Por supuesto, la respuesta es negativa, el autómata obvio para el idioma tiene la estructura de K_5 , el gráfico completo en cinco nodos . Yuval ha...
Dijkstra, en su ensayo Sobre la crueldad de enseñar realmente ciencias de la computación , hace la siguiente propuesta para un curso introductorio de programación: Por un lado, enseñamos lo que parece el cálculo predicado, pero lo hacemos de manera muy diferente a los filósofos. Para entrenar al...
¿Existe una diferencia fundamental entre la programación dinámica de arriba hacia abajo y de abajo hacia arriba? En particular, ¿hay algún problema que pueda resolverse de abajo hacia arriba pero no de arriba hacia abajo? ¿O es el enfoque ascendente solo un desenrollamiento de la recurrencia en...
Lo siento de antemano si esta pregunta suena tonta ... Hasta donde sé, construir un algoritmo usando programación dinámica funciona de esta manera: expresa el problema como una relación de recurrencia; implementar la relación de recurrencia ya sea mediante la memorización o mediante un enfoque...
Si algo es simple, entonces debería ser completamente explicable con unas pocas palabras. Esto se puede hacer para el cálculo λ: El cálculo λ es una gramática sintáctica (básicamente, una estructura) con una regla de reducción (lo que significa que un procedimiento de búsqueda / reemplazo se...
Estoy buscando ayuda para comprender el algoritmo de detección de ciclo de Floyd. He revisado la explicación en wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare ) Puedo ver cómo el algoritmo detecta el ciclo en el tiempo O (n). Sin embargo, no puedo visualizar el hecho de...
Este programa de 579 bits en el cálculo binario de Lambda tiene un estado de detención
Estoy planeando enseñar un curso de invierno sobre un número variable de temas, uno de los cuales será compiladores. Ahora, me encontré con este problema mientras pensaba en tareas para dar durante el trimestre, pero me tiene perplejo, por lo que podría usarlo como un ejemplo. public class...
Estoy estudiando CPU y sé cómo lee un programa de la memoria y ejecuto sus instrucciones. También entiendo que un sistema operativo separa los programas en los procesos, y luego alterna entre cada uno tan rápido que cree que se están ejecutando al mismo tiempo, pero de hecho cada programa se...
Estaba leyendo sobre Iota y Jot y encontré esta sección confusa: A diferencia de Iota, donde el árbol sintáctico para una cadena puede ramificarse tanto a la izquierda como a la derecha, la sintaxis de Jot se ramifica uniformemente a la izquierda. Como resultado, Iota es estrictamente libre de...
Ni siquiera soy un estudiante de CS, así que esta podría ser una pregunta estúpida, pero por favor tengan paciencia conmigo ... En la era anterior a la computadora, solo podemos implementar una estructura de datos de matriz con algo así como una matriz de cajones. Dado que uno tiene que ubicar el...
Cuando una computadora almacena una variable, cuando un programa necesita obtener el valor de la variable, ¿cómo sabe la computadora dónde buscar en la memoria el valor de esa
¿Existe algún cálculo lambda tipificado completo de Turing? Si es así, ¿cuáles son algunos
Digamos que y b 1 b 2 ... b n son dos cadenas de la misma longitud. Una anagramación de dos cadenas es un mapeo biyectivo p : [ 1 ... n ] → [ 1 ... n ] tal que a i = b p ( i ) para cada i .a1a2…ana1a2…ana_1a_2\ldots a_nb1b2…bnb1b2…bnb_1b_2\ldots b_np:[1…n]→[1…n]p:[1…n]→[1…n]p:[1\ldots n]\to[1\ldots...