Je cherchais un bon cours en ligne sur les structures de données, mais j'ai constaté que Google renvoie également des résultats pour les cours d'algorithmes, qui disent des choses comme:

Dans ce cours, vous apprendrez plusieurs principes fondamentaux de la conception d'algorithmes: méthodes de division et de conquête, algorithmes de graphes, structures de données pratiques (tas, tables de hachage, arbres de recherche) , algorithmes aléatoires, etc. [la source]

et

À la fin de ce cours, vous comprendrez les concepts clés nécessaires pour concevoir de nouveaux algorithmes pour les graphiques et autres structures de données importantes et pour évaluer l'efficacité de ces algorithmes. [la source]

et

Ce cours fournit une introduction à la modélisation mathématique des problèmes de calcul. Il couvre les algorithmes courants, les paradigmes algorithmiques et les structures de données utilisés pour résoudre ces problèmes . [la source]

Ma question est la suivante: les algorithmes et les structures de données sont-ils intimement liés, ce qui signifie qu'ils doivent être compris ensemble ou est-ce qu'un sujet est plus fondamental que l'autre?

EDIT: Pour ceux qui votent pour clore cette question, pouvez-vous s'il vous plaît me dire pourquoi et peut-être comment améliorer celle-ci? Apprendre à poser les bonnes questions fait partie du processus éducatif.

Toutes sortes de mélanges existent. Vous avez des structures de données, qui ne sont pas associées à des algorithmes, des algorithmes, qui ne nécessitent pas de structures de données (réelles), mais le plus souvent, les deux viennent dans un seul paquet.

Edit: comme @Doval l'a correctement souligné, les structures de données en elles-mêmes n'ont aucune opération associée. L'acte de combiner la structure des données et l'algorithme forme un type de données abstrait.

Structures de données sans algorithmes

Considérons par exemple une structure de données pour stocker des coordonnées bidimensionnelles, appelée de manière appropriée Point. Il n'y a pas grand-chose en termes d'algorithmes à faire pour un point et c'est vraiment juste un conteneur pour un xet une yvaleur. Bien sûr, en donnant cette structure de données, vous pouvez maintenant ajouter toutes sortes d'algorithmes par-dessus (calcul de la distance, coques convexes, ce que vous avez).

Vous pouvez penser à de nombreuses structures de données, qui sont simplement une accumulation de données individuelles. Bien que ceux-ci se produisent fréquemment dans la pratique, ils ne constituent pas un bon matériel pédagogique, car il n'y a rien à en tirer, une fois que vous avez compris, que des éléments de données uniques peuvent être accumulés dans une nouvelle structure de données (comme ce que vous apprenez après l' Pointexemple ci-dessus , si je vous fournis cette impressionnante structure de données appelée Point3D, qui peut faire la même chose pour un espace en 3 dimensions?)

Algorithmes sans structures de données (réelles)

"Réel", car évidemment chaque algorithme intéressant a besoin de types de données primitifs comme des entiers ou des booléens, et nous ne voulons pas les considérer comme des structures de données dans ce contexte. De la même manière que ci-dessus, ces algorithmes sont généralement assez simples. En particulier, ils ne viennent pas avec un état compliqué d'aucune sorte, car cela va généralement dans une structure de données (voir la section suivante).

Un exemple d'un tel algorithme serait de calculer le plus grand diviseur commun de deux nombres. Les algorithmes d'Euklid pour le gcd n'ont vraiment besoin que de deux entiers et les manipulent.

Une fois que les choses commencent à devenir plus intéressantes, vous entrez très bientôt dans le monde des types de données abstraits. Par exemple, le tamis d'Eratosthène est basé sur un tableau. Nous pourrions avoir une discussion maintenant, si un tableau est encore primitif, ou en fait, vous pourriez discuter si un entier n'est pas déjà une structure de données. De toute façon, les algorithmes qui existent complètement sans structures de données sont plutôt ennuyeux, même si vous acceptez leur existence isolée.

Algorithmes combinés avec des structures de données, aussi appelés types de données abstraits

Maintenant, ce sont les plus intéressants, mais pour deux raisons très différentes. En règle générale, vous pouvez les aborder dans deux directions: la structure des données d'abord ou l'algorithme d'abord.

Alors qu'un type de données abstrait est défini par la combinaison de structure de données + algorithmes / opérations, nous les considérons souvent avec un accent sur l'un de ceux-ci et considérons l'autre comme des catalyseurs.

Structure des données, puis algorithme

Vous rencontrerez des types de données abstraits, assez simples à utiliser, mais qui impliquent des algorithmes plus ou moins compliqués pour les faire fonctionner en interne. Par exemple, a HashMapest trivial à utiliser, mais implique une fonction de hachage astucieuse et traitant des collisions de hachage à l'intérieur. Pourtant, de votre point de vue en tant qu'utilisateur, vous vous souciez de cela comme quelque chose qui contient des données pour vous, pas quelque chose qui fait quelque chose pour vous.

Contrairement au dernier groupe ci-dessous, ces structures de données n'exposent pas leurs utilisateurs à ces algorithmes. Vous n'avez pas besoin de connaître ni de vous soucier de HashMapla fonction de hachage interne pour pouvoir l'utiliser. (Pour l'utiliser efficacement, vous voudrez peut-être savoir ces choses;)

Algorithme, puis structure des données

L'autre direction signifie que vous avez un algorithme, que vous voulez pouvoir utiliser simplement, mais qui a besoin de structures de données en interne pour le faire fonctionner comme prévu. Un exemple serait un algorithme de partitionnement d'espace binaire (BSP), que vous pouvez simplement demander pour les 2 dimensions Pointd'un grand ensemble de points qui est le plus proche d'un point de requête donné. Cependant, vous avez besoin d'une structure arborescente (et même d'algorithmes supplémentaires comme les calculs de distance) à l'intérieur pour réellement écrire l'algorithme.

En général, on peut dire que les algorithmes de ce groupe utilisent des structures de données impliquées pour leur représentation d'état interne. Je dirais que ce groupe d'algorithmes est le plus diversifié et vous en trouverez de nombreux différents qui correspondent à ce schéma général. En ce qui concerne le point de vue, nous les considérons comme intéressants, car ils font quelque chose (tri par exemple) pour nous, et ne se soucient pas autant de la partie contenant les données.

Structures de données et algorithmes étroitement liés

Enfin, vous disposez de structures de données, très proches des algorithmes qui leur correspondent directement. Un exemple typique est un arbre binaire qui, lorsque vous voulez faire quoi que ce soit de significatif avec lui, vous impose le sujet des algorithmes d'arborescence (profondeur d'abord, largeur d'abord, peu importe).

Pour ces cas, nous modifions de temps en temps notre vision des types de données abstraits résultants. Parfois, vous vous souciez de la structure de votre arbre, quelques minutes plus tard, vous vous souciez de pouvoir exécuter une opération de recherche sur celui-ci, puis vous vous interrogez sur la suppression d'un nœud, et tout de suite sur l'aspect de la structure par la suite. Bien que tout cela soit également vrai pour les autres sections ci-dessus, ce n'est pas quelque chose qui vous intéresse principalement, par exemple, lorsque vous stockez / récupérez des données vers / depuis un Map, ou lorsque vous triez une liste liée.

Les structures de données influencent souvent les détails d'un algorithme. Pour cette raison, les deux vont souvent de pair.

Prenons par exemple un algorithme pour couper votre pelouse. La façon dont vous coupez votre pelouse est susceptible d'être influencée par la structure réelle de votre pelouse. Si vous vivez dans une petite maison dans une banlieue densément peuplée et que votre pelouse n'est qu'un petit rectangle de quelques mètres carrés, vous préféreriez probablement couper votre pelouse avec une tondeuse à pousser plutôt qu'avec un tracteur / tondeuse autoportée. Si votre pelouse comprend plusieurs acres de prairie plate, votre préférence peut être pour la tondeuse autoportée plutôt que pour la tondeuse à poussée (bien que l'une ou l'autre tondeuse puisse éventuellement faire le travail). Si votre pelouse comprend des hectares de terrain avec de grandes zones plates, mais quelques petites collines et un certain nombre d'arbres, vous pouvez développer un algorithme plus intéressant pour couper la pelouse qui implique à la fois une tondeuse autoportée et une tondeuse à pousser, ou une autre herbe techniques de coupe.

En fin de compte, la structure de vos données peut avoir un impact significatif sur vos décisions concernant la façon de développer votre algorithme (ou les algorithmes à utiliser). Pour cette raison, les deux sujets vont souvent de pair.

Et vice versa: parfois l'algorithme que nous voulons utiliser influence (au moins au début de l'informatique) les structures de données que vous développez pour prendre en charge l'algorithme. Par exemple, passer d'une liste de tableaux à l'idée d'une liste liée et éventuellement à un BST pour stocker une liste ordonnée qui permettra une recherche rapide.