Wörterbuch der Algorithmen und Datenstrukturen (Dictionary of Algorithms and Data Structures)

 (xlinux.nist.gov)
3 Punkte von GN⁺ 2023-09-30 | 1 Kommentare | Auf WhatsApp teilen
  • Ein Online-Wörterbuch, das Algorithmen, Algorithmus-Techniken, Datenstrukturen, typische Probleme und verwandte Definitionen sammelt und ordnet
  • Enthält Algorithmus-Einträge einschließlich gängiger Funktionen wie Ackermann's function
  • Enthält Einträge zu typischen Problemen wie traveling salesman und Byzantine generals
  • Einige Einträge bieten Links zu Implementierungen (implementation) und weiteren Informationen; die Einträge sind über Indizes nach Bereich (area) und Typ (type) geordnet
  • Konzentriert sich auf „allgemeine (general)“ Algorithmen und Datenstrukturen und schließt bestimmte Bereiche wie business data processing, AI und graphics aus

Überblick über die Website und Trägerschaft

  • Gehostet von der Software and Systems Division des Information Technology Laboratory von NIST
  • Die Entwicklung des Wörterbuchs begann 1998 unter der Redaktion von Paul E. Black
  • Es hat die Form eines Wörterbuchs zu Algorithmen, Algorithmus-Techniken, Datenstrukturen, typischen Problemen und verwandten Definitionen

Aufbau der enthaltenen Einträge

  • Algorithmus-Einträge umfassen gängige Funktionen wie Ackermann's function
  • Problem-Einträge umfassen traveling salesman und Byzantine generals
  • Einige Einträge bieten Links zu Implementierungen (implementation) und weiterführenden Informationen
  • Die Indexseiten listen Einträge nach Bereich (area) und Typ (type) auf
  • Der two-level index hat nur 1/20 des gesamten Download-Umfangs dieser Seite

Hinweise zur Nutzung

  • Nutzung zum Zweck des Betrugs (cheat) ist untersagt; Lehrkräfte sollen sich bei Unterstützungsbedarf melden
  • Für Vorschläge, Korrekturen und Kommentare soll Paul Black kontaktiert werden

Nicht abgedeckter Umfang

  • Derzeit sind auf die folgenden Bereiche spezialisierte Algorithmen nicht enthalten
    • business data processing, communications, operating systems oder distributed algorithms
    • programming languages, AI, graphics, numerical analysis
  • Der Umfang ist eingeschränkt, weil bereits „allgemeine (general)“ Algorithmen und Datenstrukturen allein schwer genug vollständig zu behandeln sind

Index und Hinweise

  • Begriffe mit vorangestellter Variable wie n-way, m-dimensional oder p-branching sind unter dem Eintrag k- einsortiert
  • Nützliche Einträge finden sich in A Glossary of Computer Oriented Abbreviations and Acronyms

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-09-30
Hacker-News-Kommentare

  • Verwandte frühere Beiträge:
    Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - Oktober 2016 (18 Kommentare)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - Januar 2015 (4 Kommentare)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - April 2013 (15 Kommentare)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - April 2011 (16 Kommentare)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - März 2011 (1 Kommentar)

  • Ich würde diese Ressource gern mögen, aber von den Dingen, die ich kenne, fehlen der Fenwick tree und der Union-Find-Algorithmus/die Union-Find-Datenstruktur
    Den Fenwick tree habe ich zum ersten Mal hier gesehen: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
    Union-Find habe ich vermutlich hier gesehen: https://www.youtube.com/watch?v=PGZ64ob440I
    Meiner Erinnerung nach war es allerdings eine Implementierung mit Dictionary/Hashmap statt mit einem Array fester Größe

    • Es scheint ziemlich viel zu fehlen. Ich hätte erwartet, Fenwick zumindest unter einem anderen Namen zu finden, aber ich sehe es nicht; dass Union-Find fehlt, ist noch seltsamer. Es ist eine wirklich großartige und nützliche Datenstruktur, und mir fällt auch kein anderer Name ein, unter dem sie versteckt sein könnte
      Was mir spontan einfällt und ich nicht finden konnte: Quadratwurzel-Zerlegung, Heavy-Light Decomposition und Range Minimum Query allgemein. Persönlich zählt Range Minimum Query als allgemeines Problem zu meinen Favoriten, und als Bündel von Techniken, in das man Zeit investieren kann, finde ich es deutlich interessanter als Sortieren
      Die Union-Find-Datenstruktur wird üblicherweise mit einem festen Array gezeigt, weil dadurch die Algorithmusanalyse etwas interessanter wird. Wenn die Lookup-Kosten über O(1) liegen, geht der interessante Teil der Analyse meiner Meinung nach unter. Natürlich funktioniert die Datenstruktur selbst auf beide Arten gut
    • Bei einer endlichen Sammlung muss zwangsläufig fast alles fehlen. Soft heap oder Finger tree fehlen ebenfalls, und auch viele der rein funktionalen Datenstrukturen, die Okasaki behandelt, sind nicht enthalten

  • Eine hervorragende Ressource, aber ich wünschte, Kurse zu Datenstrukturen und Algorithmen würden sich stärker auf Anwendungen konzentrieren
    Mich interessiert weniger, einfach zu wissen, was etwas ist, sondern eher, warum es nützlich ist und in welchem Kontext man es hervorholen sollte

    • https://www.redblobgames.com/ ist eine sehr gute Ressource, die viel Kontext liefert und technische Details trotzdem nicht scheut
    • Ich habe einmal etwas in eine ähnliche Richtung geschrieben. Es ging nicht direkt um Anwendungen, sondern um einen Leitfaden/Entscheidungsbaum dafür, welchen Datenstruktur- oder Algorithmusansatz man auf welches Problem anwenden sollte, basierend auf dem, was ich beim Lösen des Blind-75-Problemsets gelernt habe
      Ich bin noch kein Experte, daher ist es keine autoritative Quelle, könnte aber interessant sein: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
    • Meiner Erfahrung nach machen Kurse genau das bereits. Die Zeit- und Speicherkomplexität einer gegebenen Funktion und deren Analyse stehen im Mittelpunkt
    • Skiena hatte, glaube ich, eine gute Vorlesung zu diesem Thema
    • Kontext und Geschichte zu kennen macht es definitiv interessanter und hilft in der Regel auch beim Lernen

  • Ein Eintrag, der auffällt: Marlena
    https://xlinux.nist.gov/dads/HTML/marlena.html
    Weiß jemand, was das bedeuten soll?

  • Ich weiß nicht, ob eine alphabetische Liste von Algorithmen für Lernende ein guter Ausgangspunkt ist
    Für jemanden, der gerade anfängt oder dieses Thema wirklich beherrschen möchte, ist dieses klassische Buch meiner Meinung nach der Standard.[1]
    Wenn das Ziel ist, als Entwickler zu wachsen und FAANG-Coding-Interviews zu bestehen, könnte das der stärkste Hebel sein
    [1] https://books.google.com/books/about/Introduction_To_Algorit...

    • Als Ausgangspunkt wahrscheinlich eher nicht. Als Referenz ist es aber hervorragend

  • Ich frage mich, wie man diese Liste rückwärts durchsuchen sollte
    Zum Beispiel, wenn man ungefähr beschreiben kann, wie ein Algorithmus funktioniert, aber seinen Namen nicht kennt und wissen möchte, ob er in dieser Liste steht. Heutzutage könnte man ihn vielleicht als Pseudocode aufschreiben, ChatGPT geben und nach dem Namen fragen, aber sonst wüsste ich es nicht

    • Geh auf Discord und frag dort; irgendjemand wird es wissen

  • Ich wünschte, sie würden Pull Requests annehmen. Grundlegende Einträge wie acceleration structure fehlen

  • Eine wirklich tolle Ressource. Ich hoffe, sie übersteht Dinge wie Budgetkürzungen und bleibt erhalten; man sollte sie archivieren