Manuel des structures de données avancées

24

Je suis à la recherche d'un livre sur les structures de données avancées qui va au-delà de ce qui est couvert dans les manuels standard comme Cormen, Leiserson, Rivest et Stein "Introduction to Algorithms".
Un livre qui peut être utilisé pour enseigner un cours de niveau supérieur sur les structures de données avancées comme Erik Demaine et le cours Advanced Data Structures d' André Schulz au MIT. Un manuel encyclopédique des structures de données serait encore plus agréable.

soft-question ds.data-structures survey books Kaveh
la source
il existe des structures avancées dans des domaines significativement différents, comme les listes de classes, par exemple les graphiques, la géométrie informatique, la récupération d'informations, les chaînes, etc., et chaque champ est susceptible de couvrir chacun séparément, ils semblent très différents ... peut-être mieux combinés dans une classe qu'un livre ...
vzn
2
@vzn: Vous avez raison - différents sous-champs utilisent des structures différentes - mais les outils se chevauchent plus que vous ne le pensez. Les structures de données de graphique, les structures de données de chaîne et les structures de données de récupération d'informations sont toutes utilisées par exemple en géométrie de calcul. Kaveh pose un problème ouvert bien connu des chercheurs en structure de données.
Jeffε
d'accord cependant, il semblerait que plus la structure de données dans un champ est avancée, moins le chevauchement est probable. il y a bien sûr un fort chevauchement entre les structures de base (par exemple les graphiques, les chaînes, la récupération d'informations, etc.) ....
vzn
1
Si de nombreux chercheurs en structures de données veulent un tel manuel (et d'après les réponses ci-dessous, j'ai l'impression que nous le faisons), pourquoi n'en existe-t-il pas?
Joe
2
@Joe: Tout le monde attend que quelqu'un d'autre franchisse le pas.
Jeffε

Réponses:

14

J'aimerais avoir une bonne réponse pour toi. J'utilise Book: Fundamental Data Structures (une collection d'articles pertinents de Wikipedia) pour mon cours sur ce sujet, mais ce n'est pas vraiment un manuel complet (d'une part, il n'a pas d'exercices). Le CLRS est, je pense, à un bon niveau de détail pour ce type de classe mais il manque trop de structures importantes.

David Eppstein
la source
10

Le seul livre sur les structures de données avancées que je connaisse est celui de Peter Braß ( Advanced Data Structures ). Ce n'est pas un mauvais livre, mais je ne suis pas convaincu qu'il soit vraiment avancé au niveau universitaire.

Suresh Venkat
la source
9

Le Handbook of Data Structures and Applications (Chapman & Hall / CRC Computer & Information Science Series) est principalement consacré aux structures de données élémentaires, mais il contient également quelques matériaux avancés qui peuvent vous être utiles pour l'enseignement d'un cours de niveau supérieur. Compte tenu de la taille énorme (1392 pages), ce livre peut être classé comme un manuel encyclopédique des structures de données, même s'il ne s'agit certainement pas d'un manuel axé principalement sur les structures de données avancées.

Massimo Cafaro
la source
8

Je suis presque sûr qu'aucun livre de ce genre n'existe.

J'ai rédigé une bibliographie annotée pour mon cours récent , qui était vaguement basé sur le cours d'Erik au MIT. Il est définitivement incomplet - j'ai couvert très peu de structures de données géométriques et aucune structure de données texte, par exemple - mais vous pourriez toujours le trouver utile.

Jeffε
la source