Em um gráfico direcionado, , , se é um DAG (gráfico acíclico direcionado), é chamado de conjunto de arco de feedback. F ⊂ E G ∖ F FG = ( V, E)G=(V,E)G=(V,E)F⊂ EF⊂EF\subset EG ∖ FG∖FG\setminus FFFF Se cada aresta estiver associada a um peso , o problema do conjunto de arcos de feedback de custo...
A função inversa de Ackermann ocorre frequentemente ao analisar algoritmos. Uma ótima apresentação está aqui: http://www.gabrielnivasch.org/fun/inverse-ackermann . α1(n)=[n/2]α1(n)=[n/2]\alpha_1(n) = [n/2] α2(n)=[log2n]α2(n)=[log2n]\alpha_2(n) = [\log_2 n] α3(n)=log∗nα3(n)=log∗n\alpha_3(n) =...
Estou procurando uma estrutura de dados e um algoritmo para calcular o número mínimo de alterações necessárias para transformar uma palavra em outra, considerando as duas palavras como entradas, onde as únicas alterações permitidas são adicione uma letra em uma das extremidades (por exemplo, AB...
Na seção 2.2 das Árvores B sem cache , as Árvores de pesquisa fortemente equilibradas são definidas como: Para alguma constante , todo nó v na altura h tem Θ ( d h ) descendentes.dddvvvhhhΘ(dh)Θ(dh)\Theta(d^h) Eles afirmam: As árvores de pesquisa que atendem às Propriedades 1 e 2 incluem...
Suponha que tenhamos um semigrupo com os elementos S = { s 1 , s 2 , … , s n } . Nosso objetivo é produtos de computação s i ∘ s i + 1 ∘ ⋯ ∘ s j .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j Em seu...
Estou procurando uma estrutura de dados altamente eficiente para armazenamento de dados semelhante à seguinte. Tags de identificação Pedido1 Pedido2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 Eu preciso ser capaz de consultar essa estrutura de tal forma a que ele iria me...
O exercício a seguir foi entregue aos alunos que eu supervisiono: Dados nnn pontos no plano, crie um algoritmo que encontre um par de pontos cuja distância seja mínima entre todos os pares de pontos. O algoritmo deve ser executado no tempo o ( n2)o(n2)o(n^2) . Existe um algoritmo de divisão e...
Estou procurando por uma estrutura de dados com espaço eficiente que armazene conjuntos (sem repetição) de elementos de tamanho de palavras e suporte a inserção rápida (O (1) amortizado). Por "espaço eficiente", quero dizer, idealmente, palavras para armazenar n elementos.n+o(n)n+o(n)n +...
As tentativas permitem o armazenamento eficiente de listas de elementos. Os prefixos são compartilhados e, portanto, economizam espaço. Estou procurando uma maneira semelhante de armazenar árvores com eficiência. Eu gostaria de poder verificar a associação e adicionar elementos, sabendo se uma...
NOTA : A pergunta foi reafirmada em minhas respostas: Supondo que agora possamos encontrar os ancestrais de irmãos mais baixos no tempo , a RNA pode realmente ser executada em O ( log n ) ?O ( 1 )O(1)O(1)O ( logn )O(logn)O(\log n) Quadtrees são índices espaciais eficientes. Eu tenho um...
David Rodríguez - dribeas escreveu em um comentário no StackOverflow que "Nem todas as coleções podem ser implementadas sem bloqueios". Não tenho certeza se isso é verdade e não consigo encontrar provas de qualquer maneira. Essa declaração não é muito precisa, mas deixe-me reformulá-la de uma...
Existe uma estrutura de dados RAM de palavras de w bits com tempo O (1) por operação para o seguinte problema ?: Manter um conjunto de números inteiros não negativos de w bits que ofereça suporte às operações add (x): adiciona x ao conjunto remove (x): remove x do conjunto impressão digital ():...
Eu li um pouco sobre as seguintes estruturas de dados: O Hash ideal de Bagwell tenta Tabelas hash dinâmicas de Larson Árvores vermelho-pretas Patricia árvores ... e tenho certeza que existem muitos outros por aí. Eu tenho visto muito pouco sobre o que cada um é mais adequado, ou por que eu...
Qual é o melhor limite atual para a execução de consultas de contagem de intervalo no meio-espaço em um conjunto de pontos bidimensionais , expressos na forma de uma troca de tempo / espaço. De acordo com o artigo seminal de Matousek, de 1993 (Teorema 6.2, Pesquisa por Gama com Cortes Hierárquicos...
É fácil ver que para qualquer existe um mapeamento 1-1 F de {0,1} n a {0,1} n + O ( log n ), de modo que, para qualquer x, o vetor F ( x ) é " equilibrado ", ou seja, possui número igual de 1s e 0s. É possível definir tal F para que, dado x , possamos calcular F ( x ) eficientemente?nnnFFFnn^nn + O...
Temos um conjunto, , de listas de elementos do conjunto . Cada elemento de aparece em uma lista única em . Estou procurando uma estrutura de dados que possa executar as seguintes atualizações:N = { 1 , 2 , 3 , . . . , n } N LeuLLN= { 1 , 2 , 3 , . . . , n }N={1,2,3,...,n}N = \{ 1, 2, 3, ..., n...
Duas pilhas podem ser implementadas com eficiência usando uma matriz de tamanho fixo: a pilha nº 1 começa na extremidade esquerda e cresce para a direita e a pilha nº 2 começa na extremidade direita e cresce para a esquerda. O mesmo é possível para três pilhas? Mais especificamente, é possível...
Estou procurando uma estrutura de dados, que é basicamente uma árvore de mapas, onde o mapa em cada nó contém alguns novos elementos, bem como os elementos no mapa do nó pai. Por mapa aqui, quero dizer um mapa de programação com chaves e valores, como mapa no STL ou dict em python. Por exemplo,...
Suponha que eu tenho uma lista de subconjuntos de { 1 , . . . , n } . Eu posso fazer o pré-processamento nesta lista, se necessário. Após este pré-processamento, eu sou apresentado com um outro conjunto A ⊆ { 1 , . . . , n } . Quero identificar quaisquer conjuntos B ∈ X com B ⊆ A .XX\cal...
Eu tenho um grande conjunto de dados de árvores e gostaria de pesquisá-lo especificando uma árvore (subgrafo conectado). A consulta deve retornar todas as ocorrências da árvore no conjunto de dados. Existem algoritmos eficientes para fazer isso? Eu estava pensando em algo como matrizes de sufixo,...