Les structures de données représentent des types de données complexes pour résoudre des problèmes du monde réel. Les structures de données combinent des représentations de données spécifiques avec des fonctionnalités spécifiques.
Les types de données abstraits catégorisent les structures de données selon leur fonctionnalité et ignorent les différences de représentation de données. Les types de données abstraits incluent les listes, les ensembles, les cartes, les files de priorité et les graphes.
Pour sélectionner une structure de données appropriée, choisissez d'abord un type de données abstrait en fonction des exigences du problème. Ensuite, sélectionnez une implémentation de structure de données appropriée pour ce type de données abstrait.
Les structures de données linéaires organisent les éléments en ligne, idéal pour implémenter le type de données abstrait liste. Les structures de données linéaires incluent les listes de tableau et les listes chaînées.
Les structures de données linéaires peuvent implémenter n'importe quel type de données abstrait. L'étude des structures de données en général se concentre sur les opportunités d'améliorer l'efficacité (en termes de temps d'exécution ou d'utilisation de la mémoire) par rapport aux structures de données linéaires.
Les structures de données arborescentes organisent les éléments dans une hiérarchie de niveaux définis par des relations parent-enfant. Les arbres sont définis avec un nœud racine au sommet de l'arbre, des relations parent-enfant entre chaque niveau et des nœuds feuilles à la base de l'arbre.
Les arbres binaires de recherche exigent que les éléments de l'arbre soient organisés du plus petit au plus grand, de gauche à droite. Les arbres binaires de recherche sont souvent utilisés pour implémenter les types de données abstraits ensemble et carte.
Les arbres binaires de recherche équilibrés et les tas binaires représentent deux approches pour éviter la situation du pire cas avec les arbres binaires de recherche. Les tas binaires sont souvent utilisés pour implémenter le type de données abstrait file de priorité.
Les structures de données de graphe se concentrent sur la modélisation explicite des relations entre les éléments. Les graphes permettent d'accéder non seulement aux éléments, mais aussi aux relations entre les éléments.
Tout comme de nombreuses structures de données peuvent représenter le même type de données abstrait, de nombreux algorithmes existent pour résoudre le même problème. Dans la résolution de problèmes algorithmiques, les informaticiens résolvent des problèmes formels avec des données d'entrée et des données de sortie spécifiques qui correspondent à chaque entrée.
La modélisation est le processus de représentation d'un phénomène complexe, tel qu'un problème du monde réel, comme un problème formel. La modélisation est une question d'abstraction : la simplification ou l'effacement des détails afin que le problème puisse être résolu par un ordinateur.
Historiquement, le modèle de calcul mettait l'accent sur des algorithmes spécialisés opérant sur un modèle modeste du phénomène sous-jacent. La modélisation est un acte violent mais aussi nécessaire afin de simplifier le problème pour qu'il puisse être résolu par un ordinateur.
La recherche est le problème de la récupération d'un élément cible à partir d'une collection de nombreux éléments. La recherche séquentielle et la recherche binaire sont deux algorithmes pour résoudre le problème de recherche.
Pour résoudre des problèmes du monde réel, les informaticiens composent, modifient et appliquent des patrons de conception d'algorithmes, tels que les algorithmes de recherche.
L'analyse d'algorithme est l'étude des sorties produites par un algorithme ainsi que de la manière dont l'algorithme produit ces sorties.
L'exactitude examine si les sorties produites par un algorithme correspondent aux résultats attendus ou souhaités sur l'ensemble des entrées possibles. L'exactitude est définie comme une correspondance entre l'algorithme et le modèle du problème, et non entre l'algorithme et le monde réel.
L'exactitude est compliquée par la complexité des relations sociales, du pouvoir et de l'iniquité dans le monde réel. Puisque les algorithmes automatisent les processus et opèrent dans des structures de pouvoir existantes, ils sont susceptibles de reproduire et d'amplifier l'injustice sociale.
En plus de l'exactitude, les informaticiens s'intéressent également à la complexité, c'est-à-dire à la mesure des ressources de calcul qu'un algorithme consomme pendant son exécution en fonction de la taille de l'entrée.
L'analyse d'exécution est une étude du temps nécessaire pour exécuter un algorithme. L'analyse expérimentale est une technique d'analyse d'exécution qui consiste à évaluer le temps d'exécution d'un algorithme en enregistrant le temps qu'il faut pour exécuter une implémentation de programme de celui-ci.
La complexité temporelle est la mesure formelle du temps qu'un algorithme nécessite pendant son exécution en fonction de la taille du problème. L'objectif de l'analyse de la complexité temporelle est de produire une caractérisation simple et facile à comparer du temps d'exécution d'un algorithme en fonction de la taille du problème.
La complexité spatiale est la mesure formelle de la quantité de mémoire qu'un algorithme nécessite pendant son exécution en fonction de la taille du problème.
Les étapes de l'analyse de la complexité temporelle consistent à identifier une métrique pour représenter la taille du problème ; à modéliser le nombre d'étapes nécessaires pour exécuter l'algorithme ; et à formaliser le modèle en utilisant soit un anglais précis, soit la notation asymptotique pour définir l'ordre de grandeur. La notation grand O est le type de notation asymptotique le plus courant en informatique.
Les différences d'ordres de grandeur sont massives : à mesure que la taille de l'entrée augmente, la différence entre les ordres de grandeur devient de plus en plus vaste. Pour les problèmes traitant de seulement 1 000 éléments, le temps qu'il faudrait pour exécuter un algorithme en temps exponentiel sur ce problème dépasse l'âge actuel de l'univers — alors que le même problème, de même taille, exécuté sur le même ordinateur, ne prendrait qu'une seconde avec un algorithme en temps quadratique.
En pratique, dans les applications traitant de grandes quantités de données, O(N2) est souvent considéré comme la limite pour les algorithmes du monde réel. Pour les algorithmes qui doivent s'exécuter fréquemment sur de grandes quantités de données, les concepteurs d'algorithmes visent O(N), O(log N) ou O(1).
Les paradigmes algorithmiques sont les concepts et idées communs derrière les patrons de conception d'algorithmes, tels que les algorithmes diviser pour régner, les algorithmes par force brute, les algorithmes gloutons et les algorithmes de réduction.
Les algorithmes diviser pour régner décomposent un problème en sous-problèmes plus petits, résolvent récursivement chaque sous-problème (régner), puis combinent le résultat de chaque sous-problème pour former la solution globale. La récursivité est une idée algorithmique fondamentale aux algorithmes diviser pour régner qui résout des problèmes complexes en divisant les données d'entrée en instances plus petites et indépendantes du même problème, appelées sous-problèmes.
La recherche binaire est un exemple d'algorithme diviser pour régner avec un seul sous-problème récursif. Le tri fusion est un exemple d'algorithme diviser pour régner avec deux sous-problèmes récursifs.
Les algorithmes par force brute résolvent les problèmes combinatoires en énumérant systématiquement toutes les solutions potentielles afin d'identifier la meilleure solution candidate. Les problèmes combinatoires identifient la meilleure solution candidate parmi un espace de nombreuses solutions potentielles.
Des algorithmes par force brute existent pour chaque problème combinatoire, mais ils ne sont généralement pas utilisés en pratique en raison de problèmes de temps d'exécution longs. Pour énumérer toutes les solutions potentielles, un algorithme par force brute doit générer toutes les combinaisons possibles des données d'entrée.
Les algorithmes gloutons résolvent les problèmes combinatoires en appliquant de manière répétée une règle simple pour sélectionner l'élément suivant à inclure dans la solution. Contrairement aux algorithmes par force brute qui résolvent les problèmes combinatoires en générant toutes les solutions potentielles, les algorithmes gloutons se concentrent plutôt sur la génération d'une seule solution.
Les algorithmes gloutons ne sont pas toujours garantis de calculer la meilleure solution en fonction des hypothèses et des objectifs du problème. Un algorithme glouton pour le problème d'ordonnancement d'intervalles ne calculera pas le bon résultat si nous choisissons d'accomplir les tâches les plus courtes.
L'algorithme de Kruskal et l'algorithme de Prim sont deux exemples d'algorithmes gloutons pour le problème de l'arbre couvrant minimal. Ces algorithmes sont un rare exemple d'algorithme glouton qui est garanti de calculer le bon résultat.
Les algorithmes de réduction résolvent des problèmes en les transformant en d'autres problèmes. En d'autres termes, les algorithmes de réduction délèguent la majeure partie du travail de résolution du problème à un autre algorithme destiné à un problème différent.
Les algorithmes de réduction permettent aux concepteurs d'algorithmes de s'appuyer sur des algorithmes canoniques optimisés plutôt que de concevoir une solution en composant des patrons de conception d'algorithmes, ce qui peut entraîner des bogues de performance ou d'exactitude. Les algorithmes de réduction permettent également aux informaticiens de faire des affirmations sur la difficulté relative d'un problème.
Les problèmes de structure de données se concentrent sur le stockage et la récupération d'éléments pour l'implémentation de types de données abstraits tels que les listes, les ensembles, les cartes et les files de priorité. Les problèmes de structure de données incluent le tri, la recherche et le hachage.
La recherche est le problème de la récupération d'un élément cible à partir d'une collection d'éléments. La recherche dans une structure de données linéaire telle qu'une liste de tableau peut être effectuée en utilisant la recherche séquentielle ou la recherche binaire.
Le tri est le problème de la réorganisation des éléments dans un ordre logique, généralement du moins valorisé au plus valorisé. Le tri est un problème fondamental non seulement en raison des tâches qu'il résout directement, mais aussi parce qu'il est une base pour de nombreux autres algorithmes tels que l'algorithme de recherche binaire ou l'algorithme de Kruskal pour le problème de l'arbre couvrant minimal.
Le tri fusion et le tri rapide sont deux exemples d'algorithmes diviser pour régner pour le tri. Le tri par tas est un algorithme de tri qui repose sur l'ajout à un tas et ensuite la suppression répétée de chaque élément dans l'ordre trié.
Le hachage est le problème d'attribuer un index entier significatif pour chaque objet. Les tables de hachage sont une structure de données pour implémenter des ensembles et des cartes en appliquant le concept de hachage.
Les problèmes de graphe incluent une grande variété de problèmes impliquant le type de données graphe. Les problèmes de graphe incluent le parcours, les arbres couvrants minimaux et les plus courts chemins.
Le parcours est le problème de l'exploration de tous les sommets d'un graphe. La recherche en profondeur et le parcours en largeur sont tous deux des algorithmes de parcours de graphe qui s'étendent à partir d'un sommet de départ, visitant finalement chaque sommet atteignable.
Le problème de l'arbre couvrant minimal consiste à trouver le sous-ensemble de trouver le moyen le moins coûteux de connecter tous les sommets entre eux, où le coût est la somme des poids des arêtes sélectionnées. Les deux algorithmes gloutons canoniques pour trouver un arbre couvrant minimal dans un graphe sont l'algorithme de Kruskal et l'algorithme de Prim.
Le problème des plus courts chemins consiste à trouver le chemin de trouver le moyen le moins coûteux de se rendre d'un sommet à un autre. La sortie d'un algorithme des plus courts chemins est un arbre des plus courts chemins du sommet de départ vers tous les autres sommets du graphe.
Le parcours en largeur calcule l'arbre des plus courts chemins non pondérés, les plus courts chemins en termes de nombre d'arêtes. L'algorithme de Dijkstra calcule l'arbre des plus courts chemins pondérés, les plus courts chemins en termes de somme des poids des arêtes.
La modélisation de problèmes est contrainte par le modèle de calcul, ou les règles de l'ordinateur sous-jacent qui est finalement responsable de l'exécution de l'algorithme. L'explosion combinatoire pose un problème pour les algorithmes informatiques car notre modèle de calcul suppose que les ordinateurs n'ont qu'un seul fil d'exécution et n'exécutent qu'une seule opération de base à chaque étape.
Une machine de Turing est un modèle abstrait de calcul pour l'exécution de tout algorithme informatique. Une machine de Turing décrit les ordinateurs en termes de trois idées clés : une banque de mémoire, une table d'instructions et un compteur ordinal.
Bien que les ordinateurs d'aujourd'hui soient beaucoup plus efficaces que les premiers ordinateurs qui ont réalisé la machine de Turing, la plupart des ordinateurs s'appuient toujours sur les mêmes hypothèses fondamentales concernant l'exécution des algorithmes. Même si les ordinateurs deviennent plus rapides avec le temps, les algorithmes inefficaces ne peuvent toujours pas être utilisés pour résoudre des problèmes de plus de quelques milliers d'éléments.
La complexité d'un problème est la complexité (c'est-à-dire les ressources de temps ou de mémoire requises) des algorithmes les plus efficaces pour résoudre le problème. Dans ce chapitre, nous nous sommes concentrés sur la résolution de problèmes connus pour avoir des algorithmes en temps polynomial qui peuvent être décrits par une expression polynomiale telle que O(1), O(log N), O(N), O(N log N), O(N2), O(N3).
La classe de complexité en temps polynomial non déterministe (NP) fait référence à tous les problèmes qui peuvent être résolus en temps polynomial par un algorithme non déterministe. Un algorithme non déterministe est un type d'algorithme qui peut s'appuyer sur le pouvoir spécial d'explorer une infinité d'« univers alternatifs » possibles afin de compléter un calcul.
Techniquement, tous les problèmes P sont aussi des problèmes NP parce que nous avons déjà des algorithmes déterministes pour les résoudre et n'avons donc pas besoin de nous appuyer sur le pouvoir spécial du non-déterminisme. NP-complet fait référence à tous les problèmes NP les plus difficiles — les problèmes combinatoires pour lesquels nous n'avons pas d'algorithmes déterministes en temps polynomial.
Les plus longs chemins et le problème du voyageur de commerce sont deux exemples bien connus de problèmes NP-complets. Ce qui rend ces deux problèmes difficiles est que nous n'avons pas de règle simple pour sélectionner l'élément suivant à inclure dans la solution.
Tous les problèmes NP-complets peuvent être réduits à tous les autres, donc un algorithme pour résoudre n'importe quel problème NP-complet résout tous les problèmes NP-complets. La question de P versus NP demande s'il est possible de concevoir un algorithme déterministe en temps polynomial pour résoudre n'importe lequel — et donc tous — de ces problèmes NP-complets.
La plupart des informaticiens théoriciens pensent qu'il est impossible de concevoir un algorithme efficace pour les plus longs chemins, le TSP ou tout autre problème NP-complet. Un algorithme efficace pour l'un quelconque des problèmes NP-complets ne résoudrait pas seulement directement les problèmes de routage et de logistique, mais permettrait également des avancées massives dans la découverte de médicaments grâce à la simulation scientifique, par exemple. Il briserait également pratiquement tous les systèmes modernes de sécurité Internet et de mots de passe — parmi des milliers d'autres problèmes.