Diccionario de algoritmos y estructuras de datos (Dictionary of Algorithms and Data Structures)

 (xlinux.nist.gov)
3 puntos por GN⁺ 2023-09-30 | 1 comentarios | Compartir por WhatsApp
  • Diccionario en línea que reúne y organiza algoritmos, técnicas algorítmicas, estructuras de datos, problemas típicos y definiciones relacionadas
  • Incluye entradas de algoritmos con funciones comunes como Ackermann's function
  • Incluye entradas de problemas típicos como traveling salesman y Byzantine generals
  • Algunas entradas ofrecen enlaces a implementaciones (implementation) e información adicional, y las entradas están organizadas con índices por área (area) y tipo (type)
  • Excluye ciertos campos específicos como business data processing, AI y graphics, y se enfoca en algoritmos y estructuras de datos "generales (general)"

Descripción del sitio y entidad operadora

  • Está alojado por la Software and Systems Division del Information Technology Laboratory de NIST
  • El desarrollo del diccionario comenzó en 1998 bajo la edición de Paul E. Black
  • Tiene formato de diccionario y cubre algoritmos, técnicas algorítmicas, estructuras de datos, problemas típicos y definiciones relacionadas

Composición de las entradas

  • Las entradas de algoritmos incluyen funciones comunes como Ackermann's function
  • Las entradas de problemas incluyen traveling salesman y Byzantine generals
  • Algunas entradas ofrecen enlaces a implementaciones (implementation) e información adicional
  • La página de índices enumera las entradas por área (area) y por tipo (type)
  • El two-level index tiene un tamaño de descarga total equivalente a 1/20 de esta página

Guía de uso

  • Se prohíbe usarlo con fines de trampa (cheat); si un docente necesita ayuda, se le indica ponerse en contacto
  • Las propuestas, correcciones y comentarios deben dirigirse a Paul Black

Alcance que no cubre

  • Actualmente no incluye algoritmos especializados en las siguientes áreas
    • business data processing, communications, operating systems o distributed algorithms
    • programming languages, AI, graphics, numerical analysis
  • El alcance se limita porque incluso solo los algoritmos y estructuras de datos "generales (general)" ya son suficientemente difíciles de cubrir

Índices y notas de referencia

  • Los términos con una variable inicial como n-way, m-dimensional y p-branching se clasifican bajo la entrada k-
  • Se pueden consultar entradas útiles en A Glossary of Computer Oriented Abbreviations and Acronyms

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-09-30
Opiniones en Hacker News

  • Publicaciones anteriores relacionadas:
    Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - octubre de 2016 (18 comentarios)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - enero de 2015 (4 comentarios)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - abril de 2013 (15 comentarios)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - abril de 2011 (16 comentarios)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - marzo de 2011 (1 comentario)

  • Me gustaría que me gustara este recurso, pero entre las cosas que conozco faltan Fenwick tree y el algoritmo/estructura de datos union-find
    La primera vez que vi Fenwick tree fue aquí: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
    Creo que union-find lo vi aquí: https://www.youtube.com/watch?v=PGZ64ob440I
    Aunque, si mal no recuerdo, era una implementación con diccionario/hashmap, no con un arreglo de tamaño fijo

    • Parece que faltan bastantes cosas. Pensé que Fenwick aparecería aunque fuera con otro nombre, pero no lo veo, y que no esté union-find es aún más raro. Es una estructura de datos realmente excelente y útil, así que no se me ocurre otro nombre bajo el que pudiera estar escondida
      De lo que se me viene a la mente de inmediato y no encontré: descomposición por raíz cuadrada, heavy-light decomposition y consultas de mínimo en rango (Range Minimum Query) en general. Personalmente, las consultas de mínimo en rango están entre mis problemas favoritos como tema general, y como conjunto de técnicas en el que dedicar tiempo y concentrarse me parecen mucho más interesantes que el ordenamiento
      La estructura de datos union-find normalmente se presenta con un arreglo fijo, porque así el análisis del algoritmo se vuelve un poco más interesante. Si el costo de búsqueda supera O(1), creo que la parte interesante del análisis queda opacada. Por supuesto, la estructura de datos en sí funciona bien de cualquier manera
    • Como es una colección finita, inevitablemente casi todo va a faltar. Tampoco están soft heap ni finger tree, y faltan muchas de las estructuras de datos puramente funcionales que trata Okasaki

  • Es un gran recurso, pero me gustaría que las clases de estructuras de datos y algoritmos se enfocaran más en las aplicaciones
    Más que saber simplemente qué es algo, me interesa saber por qué es útil y en qué contexto conviene sacarlo y usarlo

    • https://www.redblobgames.com/ es un recurso muy bueno que aporta mucho contexto sin evitar los detalles técnicos
    • Escribí algo en una línea parecida. No era tanto sobre aplicaciones en sí, sino una guía/árbol de decisión para elegir qué estructura de datos o enfoque algorítmico aplicar a cada problema, basado en lo que aprendí resolviendo el conjunto de problemas Blind 75
      Todavía no soy experto, así que no es un recurso de autoridad, pero podría resultar interesante: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
    • En mi experiencia, en las clases ya se hace eso. El núcleo es la complejidad temporal y espacial de una función dada y su análisis
    • Creo que Skiena dio una buena clase sobre este tema
    • Conocer el contexto y la historia definitivamente lo hace más interesante, y por lo general también ayuda al aprendizaje

  • Un elemento que llama la atención: Marlena
    https://xlinux.nist.gov/dads/HTML/marlena.html
    ¿Alguien sabe qué significa?

  • No sé si una lista de algoritmos en orden alfabético sea un buen punto de partida para quienes están aprendiendo
    Para alguien que recién empieza o quiere dominar bien este tema, creo que este libro clásico es el estándar.[1]
    Si el objetivo es crecer como desarrollador y pasar entrevistas de programación de FAANG, quizá sea la palanca más potente
    [1] https://books.google.com/books/about/Introduction_To_Algorit...

    • Probablemente no como punto de partida. Pero como material de referencia es excelente

  • Me pregunto cómo habría que hacer una búsqueda inversa en esta lista
    Por ejemplo, a veces uno puede describir más o menos cómo funciona cierto algoritmo, pero no sabe su nombre, y quiere saber si está en la lista. Hoy en día quizá podría escribirlo en pseudocódigo, dárselo a ChatGPT y preguntarle el nombre, pero fuera de eso no se me ocurre bien

    • Ve a Discord y pregunta; alguien te lo dirá

  • Ojalá aceptaran pull requests. Faltan entradas básicas como acceleration structure

  • Es un recurso realmente genial. Espero que sobreviva a cosas como recortes de presupuesto, y habría que archivarlo