Tenemos un DAG Tenemos una función en los nodos (en términos generales, numeramos los nodos). Nos gustaría crear un nuevo gráfico dirigido con estas reglas:F:V→NF:V→NF\colon V\to \mathbb N Solo los nodos con el mismo número pueden contraerse en el mismo nodo nuevo. . (Sin embargo,...
Hace media década, estaba sentado en una clase de estructuras de datos donde el profesor ofrecía crédito adicional si alguien podía atravesar un árbol sin usar recursividad, una pila, cola, etc. (o cualquier otra estructura de datos similar) y solo algunos indicadores. Se me ocurrió lo que pensé...
Estoy tratando de estudiar para un examen y me di cuenta de que estoy confundido acerca de cómo funcionan el TLB y el caché de datos. Entiendo que el TLB es esencialmente un caché de las direcciones físicas utilizadas más recientemente. Sin embargo, estaba mirando un diagrama en mi libro de texto...
El problema de la camarilla es un conocido completo donde el tamaño de la camarilla requerida es parte de la entrada. Sin embargo, el problema k-clique tiene un algoritmo de tiempo polinómico trivial ( cuando es constante). Estoy interesado en los límites superiores más conocidos cuando k es...
Por lo que he aprendido, la unión asintóticamente estrecha significa que está unida desde arriba y desde abajo como en la notación theta. Pero, ¿qué significa el límite superior asintóticamente ajustado para la notación
Estoy tratando de construir todas las matrices equivalentes (o n × n si lo desea) con los elementos 0 o 1. La operación que da matrices equivalentes es el intercambio simultáneo de la fila i y j Y la columna i y j. p.ej. para 1 ↔ 2 ( 0 0 0 0 1 1 1 0 0 ) ∼ ( 1 0 1 0 0 0 0 1 0 )8×88×88\times...
Sé que se puede demostrar que PROLOG es Turing completo mediante la construcción de un programa que simula una máquina de Turing como esta: turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls,...
Estoy tratando de entender una prueba de integridad de NP que parece girar en torno a SAT / 3CNF-SAT. Tal vez sea tarde, pero me temo que no puedo pensar en una fórmula 3CNF que no pueda satisfacerse (probablemente me falta algo obvio). ¿Me puede dar un ejemplo para tal
Tengo un tetraedro un poliedro p . t está restringido de tal manera que siempre comparte todos sus vértices con p . Quiero determinar si t se encuentra dentro de p .ttt pagpagptttpagpagpttt pagpagp Me gustaría agregar un detalle al problema en caso de que pueda contribuir a la solución: es un...
Estoy confundido sobre por qué los diseñadores de MIPS incluirían 5 bits dedicados al cambio y tienen códigos de operación y bits de función separados. Debido a que MIPS es tan RISC, supongo que solo se realizarán cambios en unas pocas instrucciones, por lo que esos 5 bits parecen estar...
Algunas CPU tienen un registro de banderas (ARM, x86, ...), otras no (MIPS, ...). ¿Cuál es la ventaja de tener una instrucción CMP para actualizar el registro de banderas seguido de una instrucción de bifurcación en lugar de usar un registro cero y bifurcaciones condicionales para verificar signos,...
Un rompecabezas "Flow Free" consiste en un entero positivo y un conjunto de pares (desordenados) de vértices distintos en el gráfico de cuadrícula n × n , de modo que cada vértice esté en un par como máximo. Una solución para tal rompecabezas es un conjunto de rutas no dirigidas en el gráfico de...
Es posible analizar un documento con una sola pasada desde una máquina de estado. ¿Cuál es el beneficio de tener dos pases, es decir. ¿Tiene un lexer para convertir texto en tokens y un analizador para probar las reglas de producción en esos tokens? ¿Por qué no tener una sola pasada que aplique las...
He estado leyendo Álgebra lineal y sus aplicaciones para ayudar a comprender el material informático (principalmente el aprendizaje automático), pero me preocupa que mucha de la información no sea útil para CS. Por ejemplo, saber cómo resolver eficientemente sistemas de ecuaciones lineales no...
El otoño pasado hice un recorrido por la supercomputadora Blue Waters en la Universidad de Illinois. Le pregunté si alguien alguna vez usó toda la computadora. Me dijeron que siempre estaba trabajando en múltiples proyectos. Eso me hizo preguntarme sobre la utilidad de las supercomputadoras. Quizás...
En mi libro de texto se menciona que: ∅∗={ϵ}∅∗={ϵ}\emptyset^*=\{\epsilon\} donde ∅∅\emptyset es un idioma vacío. Sin embargo, sabemos que L⋅∅=∅L⋅∅=∅L \cdot \emptyset = \emptyset , donde LLL es cualquier lenguaje. No puedo comprender intuitivamente este concepto porque la operación en estrella de...
¿Qué significa log O ( 1 ) nlogO(1)n\log^{O(1)}n ? Soy consciente de la notación big-O, pero esta notación no tiene sentido para mí. Tampoco puedo encontrar nada al respecto, porque no hay forma de que un motor de búsqueda interprete esto correctamente. Para un poco de contexto, la oración donde...
Un algoritmo de tiempo pseudo-polinomial es un algoritmo que tiene tiempo de ejecución polinomial en el valor de entrada (magnitud) pero tiempo de ejecución exponencial en el tamaño de entrada (número de bits). Por ejemplo, probar si un número nnn es primo o no, requiere un ciclo a través de los...
En el artículo de Philip Wadler sobre Theorems for Free , afirma en la Sección 2 sobre Parametricidad que no existen modelos ingenuos de teoría de conjuntos de cálculo lambda polimórfico En el ingenuo modelo teórico de conjuntos, los tipos son conjuntos y las funciones son funciones teóricas...
Deje Σ={0,1}Σ={0,1}\Sigma = \{ 0, 1 \} . Un lenguaje L⊆Σ∗L⊆Σ∗L \subseteq \Sigma^* se dice que tiene la propiedad "anti-palíndromo" si para cada cadena www que es un palíndromo, w∉Lw∉Lw\notin L . Además, para cada cadena que no es un palíndromo, o , pero no ambos (!) (Exclusivo o).u ∈ L R e v e r s...