En un gráfico dirigido, , F ⊂ E , si G ∖ F es un DAG (gráfico acíclico dirigido), F se llama un conjunto de arco de retroalimentación. G = ( V, E)G=(V,E)G=(V,E)F⊂ EF⊂EF\subset EG ∖ FG∖FG\setminus FFFF Si cada borde está asociado con un peso , el problema del conjunto de arco de retroalimentación...
La función inversa de Ackermann ocurre a menudo al analizar algoritmos. Una excelente presentación está aquí: http://www.gabrielnivasch.org/fun/inverse-ackermann . y [Notación: [x] significa que redondeamos x al entero más cercano, mientras que log ∗ es la función de registro iterada discutida...
Estoy buscando una estructura de datos y un algoritmo para calcular la cantidad mínima de cambios necesarios para transformar una palabra en otra, dadas las dos palabras como entradas, donde los únicos cambios permitidos son agregue una letra en una de las extremidades (por ejemplo, AB ->...
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 , cada nodo en altura tiene descendientes .dddvvvhhhΘ(dh)Θ(dh)\Theta(d^h) Ellos reclaman: Los árboles de búsqueda que satisfacen las Propiedades 1 y 2...
Supongamos que tenemos un semigrupo con elementos S = { s 1 , s 2 , ... , s n } . Nuestro objetivo es calcular productos s i ∘ s i + 1 ∘ ⋯ ∘ s j .( S, ∘ )(S,∘)(S,\circ)S= { s1, s2, ... , snorte}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesyo∘ si + 1∘ ⋯ ∘ sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ...
Estoy buscando una estructura de datos altamente eficiente para el almacenamiento de datos similar a la siguiente. Etiquetas de identificación Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 Tengo que ser capaz de consultar esta estructura de tal manera que me...
El siguiente ejercicio ha sido entregado a los estudiantes que superviso: Dados nnn puntos en el plano, diseñe un algoritmo que encuentre un par de puntos cuya distancia sea mínima entre todos los pares de puntos. El algoritmo debe ejecutarse en el tiempo o(n2)o(n2)o(n^2) . Existe un algoritmo...
Estoy buscando una estructura de datos de espacio eficiente que contenga conjuntos (sin repetición) de elementos de tamaño de palabras y admita una inserción rápida (O (1) amortizado). Por "espacio eficiente" quiero decir, idealmente, n+o(n)n+o(n)n + o(n) palabras para almacenar nnn elementos. Ser...
Los intentos permiten el almacenamiento eficiente de listas de elementos. Los prefijos se comparten, por lo que ahorra espacio. Estoy buscando una forma similar de almacenar árboles de manera eficiente. Me gustaría poder verificar la membresía y agregar elementos, sabiendo si un árbol dado es un...
NOTA : La pregunta se ha reformulado en mis respuestas: Suponiendo ahora que podemos encontrar a los antepasados hermanos más bajos en el tiempo , ¿se puede realizar realmente el ANN en ?O ( log n )O ( 1 )O(1)O(1)O ( logn )O(logn)O(\log n) Los quadtrees son índices espaciales eficientes....
David Rodríguez - dribeas escribió en un comentario en StackOverflow que "No todas las colecciones se pueden implementar sin bloqueos". No estoy seguro de si esto es cierto, y no puedo encontrar pruebas de ninguna manera. Esta declaración no es muy precisa, pero permítanme tratar de reformularla...
¿Existe una estructura de datos de word-RAM de w-bit con tiempo O (1) por operación para el siguiente problema ?: Mantenga un conjunto de enteros no negativos de w-bit que respalde las operaciones add (x): agrega x al conjunto remove (x): elimina x del conjunto huella digital (): devuelve una...
He leído un poco sobre las siguientes estructuras de datos: El hachís ideal de Bagwell intenta Tablas hash dinámicas de Larson Árboles rojo-negro Arboles patricia ... y estoy seguro de que hay muchos otros por ahí. He visto muy poco en la forma en que cada uno es más adecuado, o por qué...
¿Cuál es el mejor límite actual para realizar consultas de conteo de rango de medio espacio en un conjunto de puntos dimensionales, expresados en forma de una compensación tiempo / espacio. De acuerdo con el artículo seminal de 1993 de Matousek (Teorema 6.2, Búsqueda de rangos con cortes...
Es fácil ver que para cualquier existe un mapeo 1-1 de {0,1} a {0,1} tal que para cualquier el vector está "equilibrado", es decir, tiene el mismo número de 1s y 0s. ¿Es posible definir tal para que dada podamos calcular eficiente?F n n + O ( log n ) x F ( x ) F x F ( x )nortennFFFnorten^nn + O (...
Tenemos un conjunto, , de listas de elementos del conjunto . Cada elemento de aparece en una única lista en . Estoy buscando una estructura de datos que pueda realizar las siguientes actualizaciones:N = { 1 , 2 , 3 , . . . , n } N LLLLnorte= { 1 , 2 , 3 , . . . , n }N={1,2,3,...,n}N = \{ 1, 2, 3,...
Se pueden implementar de manera eficiente dos pilas usando una matriz de tamaño fijo: la pila # 1 comienza desde el extremo izquierdo y crece hacia la derecha, y la pila # 2 comienza desde el extremo derecho y crece hacia la izquierda. ¿Es lo mismo posible para tres pilas? Más específicamente, es...
Estoy buscando una estructura de datos, que es básicamente un árbol de mapas, donde el mapa en cada nodo contiene algunos elementos nuevos, así como los elementos en el mapa de su nodo padre. Por mapa aquí me refiero a un mapa de programación con claves y valores, como mapa en STL o dict en...
Supongamos que tengo una lista de subconjuntos de . Puedo hacer un preprocesamiento en esta lista si es necesario. Después de este preprocesamiento, se me presenta otro conjunto . Quiero identificar cualquier conjuntos con .{ 1 , . . . , N } A ⊆ { 1 , . . . , n } B ∈ X B ⊆ AXX\cal...
Tengo un gran conjunto de datos de árboles y me gustaría buscarlo especificando un treelet (subgrafo conectado). La consulta debe devolver todas las ocurrencias del treelet en el conjunto de datos. ¿Hay algoritmos eficientes para hacerlo? Estaba pensando en algo así como matrices de sufijos, sin...