Propriedades e aplicativos de estruturas de dados, como limites inferiores de espaço ou complexidade de tempo de inserção e exclusão de objetos.
Desde o livro de Chris Okasaki, de 1998, "Estruturas de dados puramente funcionais", não vi muitas novas estruturas de dados puramente funcionais interessantes; Eu posso citar apenas alguns: IntMap (também inventado por Okasaki em 1998, mas não presente nesse livro) Dedo árvores (e sua...
Paul Erdos falou sobre o "Livro", onde Deus guarda a prova mais elegante de cada teorema matemático. Isso até inspirou um livro (que eu acredito que está agora em sua 4ª edição): Provas do livro . Se Deus tivesse um livro semelhante para algoritmos, quais algoritmos você acha que seriam...
Quais são alguns algoritmos de utilidade legítima que são simplesmente muito complexos para implementar? Deixe-me esclarecer: não estou procurando algoritmos como o atual algoritmo de multiplicação de matriz assintótica ideal (Coppersmith-Winograd), que é razoável de implementar, mas tem uma...
fundo Vários anos atrás, quando eu era graduado, recebíamos uma lição de casa sobre análise amortizada. Não consegui resolver um dos problemas. Eu havia perguntado isso em teoria , mas nenhum resultado satisfatório foi encontrado. Lembro que o curso da TA insistiu em algo que ele não podia provar...
Duas maneiras de analisar a eficiência de um algoritmo são: colocar um limite superior assintótico em seu tempo de execução e executá-lo e coletar dados experimentais. Gostaria de saber se existem casos conhecidos em que existe uma lacuna significativa entre (1) e (2). Com isso, quero dizer que...
Essa pergunta é inspirada em outra pergunta sobre o que há de novo no PFDS desde a publicação do livro de Okasaki em 1998 . Vou começar com duas perguntas que tenho: Existe uma estrutura de dados de conjunto puramente funcional que se aproxima da velocidade das tabelas de hash? Tentativas ainda...
Estou procurando uma fonte de enormes conjuntos de dados para testar alguma implementação do algoritmo gráfico. Forneça também algumas informações sobre o tipo / distribuição (por exemplo, direcionado / não direcionado, simples / não simples, ponderado / não ponderado) dos gráficos na fonte, se...
Estou curioso para saber se existe uma maneira de armazenar um hash de um conjunto múltiplo de números inteiros que possua as seguintes propriedades, idealmente: Utiliza espaço O (1) Pode ser atualizado para refletir uma inserção ou exclusão no tempo O (1) Duas coleções idênticas (ou seja,...
A maioria dos algoritmos conhecidos é de primeira ordem, no sentido de que sua entrada e saída são dados "simples". Alguns são de segunda ordem de uma maneira trivial, por exemplo, classificação, hashtables ou funções map e fold: são parametrizadas por uma função, mas na verdade não fazem nada de...
Portanto, os filtros Bloom são bem legais - são conjuntos que suportam a verificação de associação sem falsos negativos, mas com uma pequena chance de um falso positivo. Recentemente, porém, eu estava querendo um "filtro Bloom" que garanta o contrário: sem falsos positivos, mas potencialmente...
Existe uma estrutura de dados que pega uma matriz não ordenada de nnn itens, executa o pré-processamento em O ( n )O(n)O(n) e responde a consultas: existe algum elemento xxx na lista, cada consulta no pior momento O ( log n )O(logn)O(\log n) ? Eu realmente acho que não há, então uma prova de que...
Existe uma estrutura de dados da fila prioritária que ofereça suporte às seguintes operações? Inserir (x, p) : adiciona um novo registro x com prioridade p StableExtractMin () : retorne e exclua o registro com prioridade mínima, quebrando os vínculos por ordem de inserção . Assim, após Inserir...
Tenho alguma experiência em computação científica e usei extensivamente kd-trees para aplicativos BSP (particionamento de espaço binário). Recentemente, familiarizei-me com octrees, uma estrutura de dados semelhante para particionar espaços euclidianos em 3D, mas que funciona em intervalos...
Suponha que eu possua um poset "S" e um predicado monotônico "P" em S. Quero encontrar um ou todos os elementos máximos de S satisfazendo P. EDIT : Estou interessado em minimizar o número de avaliações do P . Quais algoritmos existem para esse problema e quais propriedades e operações adicionais...
Não consegui encontrar essa estrutura de dados, mas não sou especialista na área. A estrutura implementa um conjunto e é basicamente uma matriz de elementos comparáveis com um invariante. O invariante é o seguinte (definido recursivamente): Uma matriz de comprimento 1 é uma matriz de...
Preciso calcular a mediana em execução: Entrada: nnn , kkk , vetor .( x1, x2, … , Xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Saída: vetor , em que é a mediana de .y i ( x i , x i + 1 , … , x i + k - 1 )( y1, y2, … , Yn - k + 1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1})yEuyiy_i( xEu, xi + 1, … , Xi...
Estou procurando um livro sobre estruturas de dados avançadas que vão além do que é abordado em livros-texto padrão como Cormen, Leiserson, Rivest e "Introduction to Algorithms" de Stein. Um livro que pode ser usado para ministrar um curso de pós-graduação em estruturas avançadas de dados, como...
Existe um análogo paralelo natural às árvores de vermelho-preto com propriedades semelhantes ou até mesmo terrivelmente piores para atualizações, sendo razoavelmente eficiente no trabalho? De um modo mais geral, o que podemos fazer de melhor para pesquisas paralelas com atualizações?...
Acabei de perceber que estou assumindo que a resposta para minha pergunta é "sim", mas não tenho um bom motivo. Imagino que talvez exista um coletor de lixo que, provavelmente, introduza apenas a desaceleração do pior dos casos . Existe uma referência definitiva que posso citar? No meu caso, estou...
x∈Rnx∈Rnx \in \mathbb{R}^n∥x∥0<k‖x‖0<k\|x\|_0 < kAxAxAxAAARRRnnnR≪nR≪nR \ll nAAAkkk-parte com tão pequeno quanto . Talvez eu não tenha os parâmetros mais conhecidos, mas essa é a ideia geral.xxxRRRO(kno(1))O(kno(1))O(k n^{o(1)}) Minha pergunta é: existem fenômenos semelhantes em outras...