Tengo estas preguntas de un antiguo examen que estoy tratando de resolver. Para cada problema, la entrada es una codificación de una máquina de Turing MMM . Para un entero c>1c>1c>1 , y los siguientes tres problemas: ¿Es cierto que para cada entrada xxx , M no pasa el |x|+c|x|+c|x|+c...
Una aplicación clásica de divide y vencerás es resolver el siguiente problema: Dada una matriz de elementos distintos y comparables, cuente el número de pares de inversión en la matriz: pares modo que e .( i , j ) a [ i ] > a [ j ] i < ja[1…n]a[1…n]a[1\dots
En esta pregunta sobre el recuento de inversiones , encontré un documento que demuestra un límite inferior en la complejidad del espacio para todos los algoritmos de transmisión (exactos) . He afirmado que este límite se extiende a todos los algoritmos de tiempo lineal. Esto es un poco audaz ya...
Trato de enseñarme el uso del bisonte. La página de manual bison (1) dice acerca de bison: Genere un analizador determinista LR o generalizado LR (GLR) empleando tablas LALR (1), IELR (1) o analizador canónico LR (1). ¿Qué es un analizador IELR? Todos los artículos relevantes que encontré en...
Soy un hombre de 16 años que recientemente recibió una gran enciclopedia sobre informática de un amigo mío. Por lo general, no estoy tan interesado en las computadoras y la tecnología, pero la informática ha comenzado a fascinarme. Sin embargo, tengo la intención de estudiar Física y / o...
Entiendo que es más rápido que Θ ( n log n ) y más lento que Θ ( n / log n ) . Lo que me resulta difícil de entender es cómo comparar Θ ( n log n ) y Θ ( n / log n ) con Θ ( n f ) donde 0 < f < 1 .Θ ( n )Θ(n)\Theta(n)Θ ( n logn )Θ(nlogn)\Theta(n\log n)Θ ( n / logn )Θ(n/logn)\Theta(n/\log...
Tengo varias preguntas relacionadas sobre estos dos temas. En primer lugar, la mayoría de los textos de complejidad sólo pasan por alto la clase NCNC\mathbb{NC} . ¿Existe un buen recurso que cubra la investigación más en profundidad? Por ejemplo, algo que discute todas mis preguntas a...
Planar 3SAT es NP-completo. Una instancia plana de 3SAT es una instancia de 3SAT para la cual el gráfico creado con las siguientes reglas es plano: agregue un vértice para cada yXyoXyox_iXyo¯Xyo¯\bar{x_i} agregue un vértice para cada cláusulaCjCjC_j añadir una ventaja para todos los par( xyo,...
De Wikipedia sobre algoritmos aleatorios Hay que distinguir entre algoritmos que usan la entrada aleatoria para reducir el tiempo de ejecución esperado o el uso de memoria, pero siempre terminan con un resultado correcto en una cantidad limitada de tiempo, y algoritmos probabilísticos , que,...
Supongamos que tenemos un conjunto y cada miembro de D es un par de datos y claves. Queremos una estructura de datos que soporte las siguientes operaciones:DreDDreD Inserte en D ,(d,k)(re,k)(d,k)DreD Eliminar miembro , (no es necesario buscar para encontrar e , por ejemplo, e apunta a un miembro...
Tengo un grupo de n conjuntos para los que necesito calcular una especie de valor de "unicidad" o "similitud". Me decidí por el índice Jaccard como una métrica adecuada. Desafortunadamente, el índice Jaccard solo opera en dos conjuntos a la vez. Para calcular la similitud entre todos los conjuntos,...
Si de hecho es igual a N P , ¿cómo mejoraría esto nuestros algoritmos para factorizar enteros más rápido? En otras palabras, ¿qué tipo de información nos daría este hecho para comprender mejor la factorización de enteros?PP{\sf P}NPNP{\sf
Me gustaría saber si hay una función de números de n bits a números de n bits que tenga las siguientes características:fff fff debe ser biyectivo Tanto como deben calcularse bastante rápidof - 1ffff−1f−1f^{-1} fff debería devolver un número que no tenga una correlación significativa con su...
El algoritmo Bellman-Ford determina la ruta más corta desde una fuente a todos los demás vértices. Inicialmente, la distancia entre todos los demás vértices se establece en . Luego se calcula la ruta más corta desde hasta cada vértice; esto continúa para las iteraciones . Mis preguntas...
Estoy tratando de resolver un problema gráfico (no es para la tarea, solo para practicar mis habilidades). Se da un DAG , donde es el conjunto de vértices y los bordes. El gráfico se representa como una lista de adyacencia, por lo que A v es un conjunto que contiene todas las conexiones de . Mi...
Soy un graduado que no es CS y mi campo de estudio no está relacionado con CS. Sin embargo, como parte de un plan más amplio para convertirse en un científico de la computación, quiero obtener una sólida formación en informática teórica y matemáticas en lo que se refiere a CS. Investigué mucho y...
Orden de aplicación: siempre evalúe completamente los argumentos de una función antes de evaluar la función en sí, como - (λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda...
Dado un tubo con bolas numeradas (al azar). El tubo tiene agujeros para quitar una pelota. Considere los siguientes pasos para una operación: Puede elegir una o más bolas de los agujeros y recordar el orden en que las recogió. Debe inclinar la tubería hacia el lado izquierdo para que las bolas...
Me he encontrado con una experiencia extraña en la programación en C. Considera este código: int main(){ int array1[6] = {0, 1, 2, 3, 4, 5}; int array2[6] = {6, 7, 8, 9, 10, 11}; printf("%d\n", array1[-1]); return 0; } Cuando compilo y ejecuto esto, no recibo ningún error o advertencia....
Quiero saber si el siguiente problema es decidible: Instancia: un NFA A con n estados Pregunta: ¿Existe algún número primo p tal que A acepte alguna cadena de longitud p. Creo que este problema es indecidible, pero no puedo probarlo. El decisor puede tener fácilmente un algoritmo para determinar...