Dicionário de Algoritmos e Estruturas de Dados (Dictionary of Algorithms and Data Structures)

 (xlinux.nist.gov)
3 pontos por GN⁺ 2023-09-30 | 1 comentários | Compartilhar no WhatsApp
  • Dicionário online que reúne e organiza algoritmos, técnicas algorítmicas, estruturas de dados, problemas clássicos e definições relacionadas
  • Inclui verbetes de algoritmos, com funções comuns como Ackermann's function
  • Inclui verbetes de problemas clássicos, como traveling salesman e Byzantine generals
  • Alguns verbetes oferecem links para implementação (implementation) e informações adicionais; os verbetes são organizados em índices por área (area) e tipo (type)
  • Foca em algoritmos e estruturas de dados “gerais (general)”, excluindo áreas específicas como business data processing, AI e graphics

Visão geral do site e entidade responsável

  • Hospedado pela Software and Systems Division, parte do Information Technology Laboratory do NIST
  • O desenvolvimento do dicionário começou em 1998, sob a edição de Paul E. Black
  • Formato de dicionário que aborda algoritmos, técnicas algorítmicas, estruturas de dados, problemas clássicos e definições relacionadas

Composição dos verbetes

  • Os verbetes de algoritmos incluem funções comuns como Ackermann's function
  • Os verbetes de problemas incluem traveling salesman e Byzantine generals
  • Alguns verbetes oferecem links para implementação (implementation) e informações adicionais
  • As páginas de índice listam os verbetes por área (area) e por tipo (type)
  • O two-level index tem tamanho total de download equivalente a 1/20 desta página

Orientações de uso

  • Proíbe o uso com finalidade de trapaça (cheat); professores são orientados a entrar em contato caso precisem de ajuda
  • Sugestões, correções e comentários devem ser enviados a Paul Black

Escopo não coberto

  • Atualmente, algoritmos especializados nas seguintes áreas não estão incluídos
    • business data processing, communications, operating systems ou distributed algorithms
    • programming languages, AI, graphics, numerical analysis
  • O escopo é limitado porque apenas algoritmos e estruturas de dados “gerais (general)” já são difíceis o suficiente de cobrir

Índice e observações

  • Termos com variáveis prefixadas, como n-way, m-dimensional e p-branching, são classificados sob o verbete k-
  • É possível encontrar verbetes úteis em A Glossary of Computer Oriented Abbreviations and Acronyms

Leituras relacionadas

1 comentários

 
GN⁺ 2023-09-30
Comentários no Hacker News

  • Posts antigos relacionados:
    Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - outubro de 2016 (18 comentários)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - janeiro de 2015 (4 comentários)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - abril de 2013 (15 comentários)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - abril de 2011 (16 comentários)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - março de 2011 (1 comentário)

  • Eu queria gostar deste material, mas, entre as coisas que conheço, faltam a Fenwick tree e o algoritmo/estrutura de dados union-find
    O primeiro lugar em que vi Fenwick tree foi aqui: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
    Acho que vi union-find aqui: https://www.youtube.com/watch?v=PGZ64ob440I
    Mas, pelo que lembro, era uma implementação com dicionário/hashmap, não com um array de tamanho fixo

    • Parece que falta bastante coisa. Eu esperava que Fenwick aparecesse pelo menos com outro nome, mas não encontrei; e a ausência de union-find é ainda mais estranha. É uma estrutura de dados realmente excelente e útil, então nem consigo pensar em outro nome sob o qual ela pudesse estar escondida
      Entre as que me vêm à cabeça de imediato e que não encontrei estão decomposição por raiz quadrada, heavy-light decomposition e consultas de mínimo em intervalo (Range Minimum Query) em geral. Pessoalmente, considero consultas de mínimo em intervalo uma das minhas classes favoritas de problemas gerais, e, como conjunto de técnicas em que vale a pena investir tempo e foco, acho muito mais interessante do que ordenação
      A estrutura de dados union-find costuma ser apresentada com arrays fixos, porque assim a análise do algoritmo fica um pouco mais interessante. Se o custo de busca passar de O(1), a parte interessante da análise acaba ficando encoberta. Claro que a estrutura de dados em si funciona bem de qualquer forma
    • Como é uma coletânea finita, quase tudo inevitavelmente vai ficar de fora. Também não há soft heap nem finger tree, e faltam muitas das estruturas de dados puramente funcionais tratadas por Okasaki

  • É um ótimo material, mas eu gostaria que as aulas de estruturas de dados e algoritmos focassem mais em aplicações
    Mais do que simplesmente saber o que algo é, estou mais interessado em saber por que é útil e em que contexto devo recorrer a isso

    • https://www.redblobgames.com/ é um material muito bom, que oferece bastante contexto sem evitar os detalhes técnicos
    • Escrevi algo em uma direção parecida. Não era exatamente sobre aplicações em si, mas um guia/árvore de decisão, baseado no que aprendi resolvendo o conjunto de problemas Blind 75, para escolher qual estrutura de dados ou abordagem algorítmica aplicar a cada tipo de problema
      Ainda não sou especialista, então não é um material autoritativo, mas pode ser interessante: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
    • Pela minha experiência, as aulas já fazem isso. A complexidade de tempo e espaço de uma dada função, junto com sua análise, é o ponto central
    • Acho que Skiena deu uma boa palestra sobre esse tema
    • Conhecer o contexto e a história certamente torna tudo mais interessante e, em geral, também ajuda no aprendizado

  • Um verbete que chama a atenção: Marlena
    https://xlinux.nist.gov/dads/HTML/marlena.html
    Alguém sabe o que isso significa?

  • Não sei se uma lista de algoritmos em ordem alfabética é um bom ponto de partida para quem está aprendendo
    Para quem está começando agora ou quer realmente dominar o assunto, acho que este livro clássico é o caminho padrão.[1]
    Se o objetivo é crescer como desenvolvedor e passar em entrevistas de programação da FAANG, talvez este seja o melhor ponto de alavancagem
    [1] https://books.google.com/books/about/Introduction_To_Algorit...

    • Provavelmente não como ponto de partida. Mas, como material de referência, é excelente

  • Fico me perguntando como fazer uma busca reversa nesta lista
    Por exemplo, às vezes consigo descrever mais ou menos como certo algoritmo funciona, mas não sei o nome, e quero saber se ele está nesta lista. Hoje em dia, talvez dê para escrever em pseudocódigo, mandar para o ChatGPT e perguntar o nome, mas, fora isso, não sei bem

    • Vá ao Discord e pergunte; alguém deve saber responder

  • Seria bom se aceitassem pull requests. Faltam verbetes básicos, como acceleration structure

  • É um material realmente muito legal. Espero que sobreviva a coisas como cortes de orçamento, e ele deveria ser arquivado