Las frases: El rápido zorro marrón salta sobre el perro perezoso [A] y El zorro marrón de Uick salta sobre el perro perezoso [B] se puede comparar usando el algoritmo de distancia de Levenshtein para determinar la similitud calculando el número mínimo de adiciones, eliminaciones o...
Sabemos que todos los autómatas push down son representables utilizando gramáticas libres de contexto. Además, existe un algoritmo para construir un CFG a partir de cualquier PDA (por ejemplo, la prueba de Sipser introducida a la teoría de la computación). ¿Hay alguna herramienta que haga esta...
Considere los siguientes dos algoritmos para buscar en una matriz ordenada de nnn elementos: A) búsqueda de interpolación y búsqueda binaria simulada en paralelo, y B) busque a través de pasos de interpolación alternos y pasos binarios. Ambos algoritmos son de peor complejidad de caso...
Dada una lista de salto de altura nnn , ¿cuál es su longitud esperada, dentro de un factor constante (multiplicativo)? En la sección 2.2 de Cache-Ajeno B-Trees , Fuertemente Peso equilibrado de la búsqueda árboles se definen como: Para alguna constante ddd , cada nodo vvv a la altura hhh tiene...
Para un lenguaje libre de contexto determinado G, que llamamos un no terminal nullable si , es decir, podemos derivar la cadena vacía de después de aplicar un número finito de producciones.UNAyoAiA_i UNAyo→∗ϵAi→∗ϵA_i \rightarrow^* \epsilonUNAyoAiA_i Hay un algoritmo simple para determinar qué no...
Tengo algunas preguntas sobre la conjetura de Quantum PCP: ¿Cuál es la declaración de la conjetura de PCP cuántica? ¿Qué implicaciones tendría el teorema de PCP Quantum para la simulación de hamiltonianos? ¿Se cree que la adopción de la prueba de Irit Dinur del teorema clásico de PCP puede...
La seguridad basada en simulación proporciona una definición de seguridad más natural y poderosa que la seguridad basada en juegos. He visto que los enfoques basados en simulación usan las pruebas basadas en juegos en parte para demostrar la seguridad de algunas partes del protocolo. Por ejemplo,...
Una pregunta genérica: ¿hay alguna técnica espectral para estimar el género de un gráfico? Estoy interesado en gráficos
Link-cut tree es una estructura de datos inventada por Sleator y Tarjan, que admite varias operaciones y consultas en unbosque de nodos en el tiempo O ( log n ) . (Por ejemplo, el enlace de operacióncombina dos árboles en el bosque en uno, mientras que la operación de corte divide un árbol en el...
¿Podría recomendar un artículo de encuesta o un capítulo de libro de texto que presente la teoría de las funciones recursivas?
Es bien sabido en la teoría de modelos finitos que sin un orden en la entrada, la expresividad es muy limitada. Por ejemplo, se sabe que es igual a PSPACE , y F O ( PFP ) (sin ningún orden en la entrada) es solo PSPACE -relacional, una noción definida por Abiteboul y Vianu cuando demostraron su...
Esta es una pregunta algo frívola que surgió en mi cabeza después de leer las diversas respuestas a "¿Cuál es la clase de complejidad" más pequeña "para la que se conoce un circuito superlineal? ". Las respuestas se refieren a , y cuando miré la entrada del zoológico , descubrí...
Espero haber llegado al lugar correcto ... es (probablemente) una pregunta de programación lógica bastante sencilla. Si tengo dos cláusulas de la forma: B:-A C:-A puedo transformarlas en: B,C:-A ( Editar: dónde B,Ces una conjunción. Estoy haciendo una evaluación de abajo hacia arriba y me es...
En nuestro grupo de investigación estamos trabajando en la aplicación de métodos heurísticos al problema de iluminación inversa (es decir, dada una serie de restricciones sobre las condiciones de iluminación en una escena, encontrar los lugares donde se deben colocar las fuentes de luz y sus...
Recientemente he leído algunas cosas sobre problemas de optimización incremental, pero no puedo ver cuál es la diferencia entre esos y los problemas de optimización en línea. Mi impresión es que puedo definir cada problema en línea como una contraparte incremental (lo contrario es claramente...
El problema de optimización de CSP es resistente a la aproximación si es difícil de superar el factor de aproximación de una asignación aleatoria. Por ejemplo, MAX 3-LIN es resistente a la aproximación ya que una asignación aleatoria satisface fracción de las ecuaciones lineales, pero lograr un...
¿Podría alguien dar una explicación intuitiva ( no intuitiva) de la correspondencia de la introducción a la izquierda y la eliminación de la implicación en el cálculo secuencial (SC) y la deducción natural (ND) respectivamente? Sé que deberían hacerlo por la simetría de SC pero no veo cómo se...
Existen numerosas herramientas / paquetes de teorías gráficas. Cada uno con sus pros y sus contras. ¿Cuál debería ser la semántica / sintaxis de un lenguaje de programación para resolver problemas de teoría de
Estoy buscando trabajo para calcular el cierre transitivo de una relación afín en el siguiente sentido: Sea la relación definida por un sistema de desigualdades lineales sobre las variables reales , es decirx 1 , ... , x n , x ′ 1 , ... , x ′
Mi deseo es describir la complejidad temporal de varios enfoques de agrupación. Por ejemplo, supongamos que tenemos puntos de datos en m espacio dimensional.nnnmmm Supongamos además que la matriz de diferencia de pares ΔΔ\Delta de n×nn×nn\times n dimensiones ya está calculada y que ya hemos...