Dictionnaire des algorithmes et des structures de données (Dictionary of Algorithms and Data Structures)

 (xlinux.nist.gov)
3 points par GN⁺ 2023-09-30 | 1 commentaires | Partager sur WhatsApp
  • Dictionnaire en ligne regroupant des algorithmes, des techniques algorithmiques, des structures de données, des problèmes classiques et des définitions associées
  • Comprend des entrées d’algorithmes incluant des fonctions courantes comme la fonction d’Ackermann
  • Comprend des entrées de problèmes classiques comme traveling salesman et Byzantine generals
  • Certaines entrées fournissent une implémentation (implementation) et des liens vers des informations supplémentaires, et les entrées sont organisées dans des index par domaine (area) et par type (type)
  • Exclut certains domaines spécifiques comme le business data processing, l’IA et le graphisme, et se concentre sur les algorithmes et structures de données « généraux (general) »

Présentation du site et organisme responsable

  • Hébergé par la Software and Systems Division du Information Technology Laboratory du NIST
  • Le développement du dictionnaire a commencé en 1998 sous la direction éditoriale de Paul E. Black
  • Présenté sous la forme d’un dictionnaire couvrant les algorithmes, les techniques algorithmiques, les structures de données, les problèmes classiques et les définitions associées

Composition des entrées

  • Les entrées d’algorithmes incluent des fonctions courantes comme la fonction d’Ackermann
  • Les entrées de problèmes incluent traveling salesman et Byzantine generals
  • Certaines entrées proposent une implémentation (implementation) et des liens vers des informations complémentaires
  • La page d’index liste les entrées par domaine (area) et par type (type)
  • Le two-level index représente un volume de téléchargement total égal à 1/20 de cette page

Guide d’utilisation

  • Utilisation interdite à des fins de triche (cheat) ; les enseignants sont invités à prendre contact s’ils ont besoin d’aide
  • Pour les suggestions, corrections et avis, il est indiqué de contacter Paul Black

Périmètre non couvert

  • Les algorithmes spécialisés dans les domaines suivants ne sont actuellement pas inclus
    • business data processing, communications, operating systems ou distributed algorithms
    • programming languages, IA, graphisme, analyse numérique
  • Le périmètre est volontairement limité au motif qu’il est déjà suffisamment difficile de couvrir uniquement les algorithmes et structures de données « généraux (general) »

Index et remarques

  • Les termes avec une variable préfixée, comme n-way, m-dimensional et p-branching, sont classés sous l’entrée k-
  • Il est possible de consulter des entrées utiles dans A Glossary of Computer Oriented Abbreviations and Acronyms

À lire aussi

1 commentaires

 
GN⁺ 2023-09-30
Commentaires sur Hacker News

  • Articles antérieurs liés :
    Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - octobre 2016 (18 commentaires)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - janvier 2015 (4 commentaires)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - avril 2013 (15 commentaires)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - avril 2011 (16 commentaires)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - mars 2011 (1 commentaire)

  • J’aimerais aimer cette ressource, mais parmi les choses que je connais, il manque le Fenwick tree et l’algorithme/la structure de données union-find
    La première fois que j’ai vu un Fenwick tree, c’était ici : https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
    Je crois avoir vu union-find ici : https://www.youtube.com/watch?v=PGZ64ob440I
    De mémoire, toutefois, c’était une implémentation avec dictionnaire/hashmap plutôt qu’un tableau de taille fixe

    • Il semble manquer pas mal de choses. Je m’attendais à trouver Fenwick au moins sous un autre nom, mais je ne le vois pas, et l’absence de union-find est encore plus étrange. C’est une structure de données vraiment excellente et utile, et aucun autre nom sous lequel elle pourrait être cachée ne me vient à l’esprit
      Parmi les choses auxquelles je pense immédiatement et que je n’ai pas trouvées : la décomposition en racine carrée, la heavy-light decomposition, et les requêtes de minimum sur intervalle (Range Minimum Query) en général. Personnellement, les requêtes de minimum sur intervalle font partie de mes problèmes généraux préférés, et je trouve que l’ensemble des techniques sur lesquelles se concentrer à leur sujet est bien plus intéressant que le tri
      La structure de données union-find est généralement présentée avec un tableau fixe, car cela rend l’analyse de l’algorithme un peu plus intéressante. Si le coût de recherche dépasse O(1), les aspects intéressants de l’analyse se retrouvent noyés. Bien sûr, la structure de données elle-même fonctionne très bien dans tous les cas
    • Comme il s’agit d’un recueil fini, presque tout est forcément absent. Il n’y a pas non plus de soft heap ni de finger tree, et beaucoup de structures de données purement fonctionnelles traitées par Okasaki manquent aussi

  • Excellente ressource, mais j’aimerais que les cours de structures de données et d’algorithmes mettent davantage l’accent sur les applications
    Ce qui m’intéresse plus que de savoir simplement ce que c’est, c’est de comprendre pourquoi c’est utile et dans quel contexte il faut s’en servir

    • https://www.redblobgames.com/ est une très bonne ressource qui donne beaucoup de contexte sans éviter les détails techniques
    • J’ai écrit quelque chose dans une veine similaire. Ce n’était pas tant sur les applications elles-mêmes qu’un guide/arbre de décision pour choisir quelle structure de données ou approche algorithmique appliquer à quel problème, à partir de ce que j’avais appris en résolvant la série de problèmes Blind 75
      Je ne suis pas encore expert, donc ce n’est pas une ressource faisant autorité, mais cela peut être intéressant : https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
    • D’après mon expérience, les cours le font déjà. Le cœur du sujet est la complexité en temps et en espace d’une fonction donnée, ainsi que son analyse
    • Il me semble que Skiena a donné un bon cours sur ce sujet
    • Connaître le contexte et l’histoire rend clairement les choses plus intéressantes, et aide généralement aussi à apprendre

  • Une entrée qui attire l’attention : Marlena
    https://xlinux.nist.gov/dads/HTML/marlena.html
    Quelqu’un sait ce que cela signifie ?

  • Je ne sais pas si une liste d’algorithmes classés par ordre alphabétique est un bon point de départ pour les apprenants
    Pour quelqu’un qui débute ou qui veut vraiment maîtriser le sujet, ce livre classique est, à mon avis, la référence.[1]
    Si l’objectif est de progresser comme développeur et de réussir les entretiens de code chez les FAANG, c’est peut-être le levier le plus puissant
    [1] https://books.google.com/books/about/Introduction_To_Algorit...

    • Probablement pas comme point de départ. Mais comme référence, c’est excellent

  • Je me demande comment faire une recherche inversée dans cette liste
    Par exemple, il arrive qu’on puisse décrire grosso modo le fonctionnement d’un algorithme sans en connaître le nom, et qu’on veuille savoir s’il figure dans cette liste. Aujourd’hui, on pourrait peut-être l’écrire en pseudocode, le donner à ChatGPT et lui demander son nom, mais à part ça, je ne vois pas trop

    • Allez demander sur Discord, quelqu’un vous répondra

  • J’aimerais qu’ils acceptent les pull requests. Il manque des entrées de base comme acceleration structure

  • Ressource vraiment géniale. J’espère qu’elle survivra à des choses comme les coupes budgétaires, et il faut l’archiver