désigne toutes les structures de données qui partagent une fonctionnalité commune
abstraction
processus de simplification d'un concept afin de le représenter dans un ordinateur
adjacent
dans un type abstrait de données de graphe, la relation entre deux sommets connectés par une arête
analyse d'algorithme
étude des résultats produits par les sorties ainsi que de la manière dont l'algorithme produit ces sorties
patron de conception d'algorithme
solution à des problèmes informatiques bien connus
paradigme algorithmique
concepts et idées communs derrière les patrons de conception d'algorithmes
résolution de problèmes algorithmiques
désigne un ensemble particulier d'approches et de méthodes pour la conception d'algorithmes qui s'appuie sur les liens historiques de l'informatique avec l'étude de la résolution de problèmes mathématiques
liste de tableau
structure de données qui stocke les éléments les uns à côté des autres en mémoire
analyse asymptotique
évalue le temps qu'un algorithme prend pour produire un résultat à mesure que la taille de l'entrée augmente
notation asymptotique
notation mathématique qui définit formellement l'ordre de grandeur
arbre AVL
structure de données d'arbre binaire de recherche équilibré souvent utilisée pour implémenter des ensembles ou des cartes qui organise les éléments selon la propriété d'arbre AVL
propriété d'arbre AVL
exige que les sous-arbres gauche et droit soient équilibrés à chaque nœud de l'arbre
arbre binaire de recherche équilibré
introduit des propriétés supplémentaires qui garantissent que l'arbre n'entrera jamais dans une situation du pire cas en réorganisant les éléments pour maintenir l'équilibre
notation grand O
type de notation asymptotique le plus courant en informatique, utilisé pour mesurer la complexité du pire cas
tas binaire
structure de données d'arbre binaire utilisée pour implémenter des files de priorité qui organise les éléments selon la propriété de tas
logarithme binaire
indique combien de fois un grand nombre doit être divisé par 2 jusqu'à ce qu'il atteigne 1
algorithme de recherche binaire
réduit récursivement les emplacements possibles pour la cible dans la liste triée
arbre binaire de recherche
structure de données d'arbre souvent utilisée pour implémenter des ensembles et des cartes qui organise les éléments selon la propriété d'arbre binaire et la propriété d'arbre de recherche
propriété d'arbre binaire
exige que chaque nœud puisse avoir zéro, un ou deux enfants
parcours en largeur
explore itérativement chaque voisin, étendant la recherche niveau par niveau en largeur d'abord
algorithme par force brute
résout les problèmes combinatoires en énumérant systématiquement toutes les solutions potentielles afin d'identifier la meilleure solution candidate
algorithme canonique
algorithme bien connu
analyse de cas
façon de tenir compte de la variation du temps d'exécution basée sur des facteurs autres que la taille du problème
nœud enfant
descendant d'un autre nœud
collision
situation où plusieurs objets hachent à la même valeur d'index entier
explosion combinatoire
nombre exponentiel de solutions à un problème combinatoire qui rend les algorithmes par force brute inutilisables en pratique
problème combinatoire
implique l'identification de la meilleure solution candidate parmi un espace de nombreuses solutions potentielles
tri par comparaison
tri d'une liste d'éléments où les éléments ne sont pas assignés de valeurs numériques mais plutôt définis en relation avec d'autres éléments
complexité
condition basée sur le degré de ressources computationnelles qu'un algorithme consomme pendant son exécution en relation avec la taille de l'entrée
compression
problème de représentation de l'information en utilisant moins de stockage de données
constante
type d'ordre de grandeur qui ne consomme pas plus de ressources à mesure que la taille du problème augmente
exactitude
le fait que les sorties produites par un algorithme correspondent aux résultats attendus ou désirés sur l'ensemble des entrées possibles
modèle de coût
caractérisation du temps d'exécution en termes d'opérations plus abstraites telles que le nombre de répétitions
tri par dénombrement
tri d'une liste d'éléments en organisant les éléments en catégories et en réorganisant les catégories dans un ordre logique
cryptographie
problème de masquage ou d'obfuscation de texte pour le rendre inintelligible
structure de données
type de données complexe avec une représentation spécifique et une fonctionnalité spécifique
problème de structure de données
problème computationnel impliquant le stockage et la récupération d'éléments pour l'implémentation de types abstraits de données tels que les listes, les ensembles, les cartes et les files de priorité
type de données
détermine comment les ordinateurs traitent les données en définissant les valeurs possibles pour les données et les fonctionnalités ou opérations possibles sur ces données
recherche en profondeur
algorithme de parcours de graphe qui explore récursivement chaque voisin, continuant aussi loin que possible le long de chaque sous-problème en profondeur d'abord
algorithme de Dijkstra
maintient une file de priorité de sommets dans le graphe ordonnés par distance du départ et sélectionne à plusieurs reprises le prochain plus court chemin vers une partie non connectée du graphe
algorithme diviser pour régner
paradigme algorithmique qui décompose un problème en sous-problèmes plus petits, résout récursivement chaque sous-problème (régner), puis combine le résultat de chaque sous-problème afin d'éclairer la solution globale
arête
relation entre les sommets ou les nœuds
élément
point de données individuel
analyse expérimentale
évalue 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
fonctionnalité
opérations telles que l'ajout, la récupération et la suppression d'éléments
graphe
représente des relations binaires entre une collection d'entités, spécifiquement des sommets et des arêtes
problème de graphe
problème computationnel impliquant des graphes qui représentent des relations entre les données
algorithme glouton
résout les problèmes combinatoires en appliquant à plusieurs reprises une règle simple pour sélectionner le prochain élément à inclure dans la solution
table de hachage
implémente des ensembles et des cartes en appliquant le concept de hachage
hachage
problème d'assignation d'un index entier significatif pour chaque objet
propriété de tas
exige que la valeur de priorité de chaque nœud dans le tas soit supérieure ou égale aux valeurs de priorité de ses enfants
algorithme de tri par tas
ajoute tous les éléments à une structure de données de file de priorité de tas binaire en utilisant l'opération de comparaison pour déterminer la valeur de priorité et renvoie la liste triée en retirant à plusieurs reprises de la file de priorité élément par élément
index
position ou adresse d'un élément dans une liste
problème d'ordonnancement d'intervalles
problème combinatoire impliquant une liste de tâches planifiées avec l'objectif de trouver le plus grand ensemble de tâches non chevauchantes pouvant être accomplies
intraitable
problèmes qui n'ont pas d'algorithmes efficaces en temps polynomial
algorithme de Kruskal
algorithme glouton qui trie la liste des arêtes du graphe par poids
nœud feuille
nœud au bas d'un arbre qui n'a pas d'enfants
linéaire
type d'ordre de grandeur où les ressources nécessaires pour exécuter l'algorithme augmentent à peu près au même rythme que la taille du problème augmente
structure de données linéaire
catégorie de structures de données où les éléments sont ordonnés en ligne
liste chaînée
structure de données qui ne stocke pas nécessairement les éléments les uns à côté des autres et fonctionne plutôt en maintenant, pour chaque élément, un lien vers l'élément suivant dans la liste
liste
séquence ordonnée d'éléments et permet d'ajouter, de récupérer et de supprimer des éléments de n'importe quelle position dans la liste
logarithme
indique combien de fois un grand nombre doit être divisé par un petit nombre jusqu'à ce qu'il atteigne 1
plus long chemin
problème de trouver le chemin le plus coûteux pour aller d'un sommet à un autre sans répéter les sommets
carte
représente des associations non ordonnées entre des paires clé-valeur d'éléments, où chaque clé ne peut apparaître qu'une seule fois dans la carte
appariement
problème de recherche d'un motif de texte dans un document
tri fusion
algorithme canonique diviser pour régner pour le tri par comparaison
arbre couvrant minimal
problème de trouver le moyen le moins coûteux de connecter tous les sommets entre eux
modèle de calcul
règles de l'ordinateur sous-jacent qui est finalement responsable de l'exécution de l'algorithme
nœud
représente un élément dans un arbre ou un graphe
algorithme non déterministe
type spécial de machine de Turing, qui à chaque étape peut choisir de manière non déterministe quelle instruction exécuter et est considérée comme trouvant une solution avec succès si toute combinaison de ces choix non déterministes conduit à une solution correcte
classe de complexité en temps polynomial non déterministe (NP)
tous les problèmes qui peuvent être résolus en temps polynomial par un algorithme non déterministe
NP-complet
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
ordre de grandeur
prédiction géométrique de la complexité temporelle ou spatiale d'un algorithme en fonction de la taille du problème
parfaitement équilibré
pour chaque nœud dans l'arbre binaire de recherche, ses sous-arbres gauche et droit contiennent le même nombre d'éléments
classe de complexité en temps polynomial (P)
tous les problèmes dont les temps d'exécution sont décrits par une expression polynomiale telle que O(1), O(log N), O(N), O(N log N), O(N2), O(N3)
algorithme de Prim
algorithme glouton qui maintient une file de priorité de sommets dans le graphe ordonnés par le poids de l'arête de connexion
file de priorité
représente une collection d'éléments où chaque élément a une valeur de priorité associée
problème
tâche avec des données d'entrée spécifiques et des données de sortie correspondant à chaque entrée
modèle de problème
représentation simplifiée et abstraite d'un problème du monde réel plus complexe
programme
réalisation ou implémentation d'un algorithme écrit dans un langage de programmation formel
algorithme de tri rapide
trie récursivement les données en appliquant le patron de conception d'algorithme d'arbre binaire de recherche pour partitionner les données autour d'éléments pivots
sommet atteignable
sommet qui peut être atteint si un chemin ou une séquence d'arêtes depuis le sommet de départ existe
algorithme de réduction
résout les problèmes en les transformant en d'autres problèmes
représentation
manière particulière d'organiser une collection d'éléments
nœud racine
nœud au sommet de l'arbre
analyse d'exécution
étude du temps nécessaire à l'exécution d'un algorithme
propriété d'arbre de recherche
exige que les éléments de l'arbre soient organisés du plus petit au plus grand de gauche à droite
recherche
problème de récupération d'un élément cible à partir d'une collection d'éléments
algorithme de recherche séquentielle
algorithme de recherche qui vérifie séquentiellement la collection élément par élément pour la cible
ensemble
représente une collection non ordonnée d'éléments uniques et permet d'ajouter, de récupérer et de supprimer des éléments de l'ensemble
plus court chemin
problème de trouver le chemin le moins coûteux pour aller d'un sommet à un autre
arbre des plus courts chemins
sortie du problème des plus courts chemins, le chemin le moins coûteux pour aller d'un sommet à tout autre sommet atteignable dans un graphe
tri
problème de réarrangement des éléments dans un ordre logique
complexité spatiale
mesure formelle de la quantité de mémoire qu'un algorithme requiert pendant son exécution en relation avec la taille du problème
étape
opération de base dans l'ordinateur, telle que la recherche d'une seule valeur, l'ajout de deux valeurs ou la comparaison de deux valeurs
problème de chaînes de caractères
problème computationnel impliquant du texte ou de l'information représentée comme une séquence de caractères
sous-problème
instance plus petite d'un problème qui peut être résolue indépendamment
complexité temporelle
mesure formelle du temps qu'un algorithme requiert pendant l'exécution en relation avec la taille du problème
traitable
problèmes que les ordinateurs peuvent résoudre en un temps raisonnable
problème du voyageur de commerce
problème de, étant donné le coût du chemin de chaque paire de sommets, trouver le parcours le moins coûteux, ou chemin d'un sommet de départ visitant chaque sommet du graphe une fois, y compris un retour au sommet de départ
parcours
problème d'exploration de tous les sommets d'un graphe
arbre
structure de données hiérarchique
machine de Turing
modèle abstrait de calcul pour l'exécution de tout algorithme informatique
plus court chemin non pondéré
problème de trouver les plus courts chemins en termes du nombre d'arêtes
sommet
représente un élément dans un graphe ou un type spécial de celui-ci tel qu'un arbre
plus court chemin pondéré
problème de trouver les plus courts chemins en termes de la somme des poids des arêtes