FAQ algorithmesConsultez toutes les FAQ

De manière simple :

Un type abstrait est un objet qui dispose d'un ensemble d'opérations ayant chacun une syntaxe et une sémantique.

De manière plus formelle, un type abstrait dispose :

• d'une signature qui comprend le nom du type (par exemple entier) et qui comprend le prototype de ses opérations ;
• d'axiomes qui définissent toutes les propriétés de ses opérations.
  

• pileEstVide(Pile) -> Booléen ;
• pileCreer() -> Pile ;
• pileLire(Pile) -> Élément ;
• pileEmpiler(Pile, Élément) -> Pile ;
• pileDepiler(Pile) -> Pile.
  

• pileLire(pileEmpiler(p, e)) = e ;
• p = pileDepiler(pileEmpiler(p,e)) ;
• pileEstVide(pileCreer()) est vrai.
  

• pileDepiler(pileCreer()) ;
• pileLire(pileCreer()).
  

Une pile (stack ou LIFO, Last In First Out) est une structure de données qui consiste à récupérer les dernières données ajoutées à une pile, en premier et les premières, en dernier.

En d'autres termes, une pile (en anglais stack) est un ensemble dynamique d'objets accessibles selon une discipline LIFO. Son interface est constituée de :

• \[isEmpty(S)\] : renvoie vrai si et seulement si la pile SS est vide ;

• \[push(S,\, x)\] : pousse la valeur xx sur la pile SS ;

• \[pop(S)\] : extrait et renvoie la valeur au sommet de la pile SS.

• avec un tableau (bien que sa taille soit, a priori, de dimension fixée). Complexité en temps des procédures : \[\Theta(1)\] ; en espace : \[\Theta(1)\]. Cela signifie que la pile ne pourra pas grandir, et ici, ce n'est pas un avantage ;

• avec une liste liée. Complexité en temps des procédures : ; en espace : \[\Theta(1)\].

Une file (queue ou FIFO, First In First Out) est une structure de données qui fonctionne selon le principe premier entré, premier sorti. Les primitives de base de cette structure de données sont l'enfilement (Enqueue) et le défilement (Dequeue), qui permettent respectivement d'ajouter un élément et de retirer le prochain élément de la file après l'avoir renvoyé. On utilise la file notamment pour parcourir un arbre en largeur.

Autrement dit, une file (en anglais queue) est un ensemble dynamique d'objets accessibles selon une discipline FIFO. Son interface est constituée de :

• \[enqueue(Q,\, s)\] : ajoute l'élément \[s\] à la file \[Q\] ;

• \[dequeue(Q)\] : retire l'élément à la tête de la file \[Q\].

• un tableau circulaire. Complexité en temps des procédures : \[\Theta(1)\] ; en espace : \[\Theta(1)\] ;

• une liste liée. Complexité en temps des procédures : \[\Theta(1)\] ; en espace : \[\Theta(n)\].

Un invariant structurel est une propriété qu'une structure de données doit vérifier :

• à sa création ;
• avant toute opération ;
• après exécution de toute opération.
  

• le(s) constructeur(s) doivent respecter ce contrat ;
• les opérations ne peuvent violer l'invariant structurel que localement, toute opération terminée doit laisser la structure de données dans un état où elle respecte son invariant structurel.
  

• suffisamment peu coûteuse à maintenir ;
• suffisamment intéressante pour garantir une complexité plus avantageuse, au moins pour les opérations de base.
  

Une structure de données adaptative est une structure de données qui ne maintient pas d'invariant structurel additionnel mais dont certaines opérations (notamment la recherche) réorganisent la structure selon un schéma prédéterminé.

Cette adaptation est en général une transformation :

• suffisamment peu coûteuse à réaliser pour ne pas pénaliser la recherche ;
• suffisamment intéressante pour garantir une complexité plus avantageuse, au moins pour les opérations de base.
  

Une structure de données est dite persistante si et seulement si aucune de ses opérations n'invalide l'état antérieur de la structure :

• si une structure de données est non persistante alors un seul moment de l'histoire de la structure est disponible (son état après la dernière opération) ;
• si une structure de données est persistante alors la structure est disponible pour tout l'historique de ses opérations (son état à un moment quelconque de son histoire).
  

Une structure de tas est une structure de données qui vérifie la propriété de tas. Un tas est utile pour implémenter une file de priorité. Les tas sont aussi utilisés pour implanter efficacement certains algorithmes de graphe.

Un tas-min possède les opérations de base suivantes :

• l'insertion d'un l'élément ;
• la recherche de l'élément minimum ;
• la suppression de l'élément minimum.
  

• l'union avec un autre tas-min ;
• la suppression d'un élément quelconque dans le tas ;
• la réaffectation d'un élément à une priorité inférieure.
  

• insertion d'un l'élément ;
• recherche de l'élément maximum ;
• suppression de l'élément maximum ;
• union avec un autre tas-max ;
• suppression d'un élément quelconque dans le tas ;
• réaffectation d'un élément à une priorité supérieure.
  

Le smart-constructor est un type de constructeur spécifique à certains types abstraits de données munis d'un invariant structurel si contraignant qu'il devient trop difficile de concevoir des algorithmes pour eux.

La plupart de types abstraits de données sont conçus à base de constructeurs simples. Exemple :

• feuille est un constructeur sans argument pour l'arbre binaire vide ;
• nœud est un constructeur (pour arbre non vide) avec deux arguments, une étiquette et deux arbres.
  

• il est difficile de concevoir un algorithme pour l'union de deux arbres AVL qui renvoie un AVL ;
• la raison pour laquelle ceci est difficile est que le constructeur nœud peut construire un ABR à partir de deux ABR mais ne peut pas construire un AVL à partir de deux AVL, car rien ne garantit que leur différence de hauteur n'est pas supérieure à 1 ;
• la solution est d'introduire un smart-constructor joindre capable de construire un AVL à partir de deux AVL quelconques et une étiquette, puis partout là où on utilisait nœud, on utilisera joindre à la place ;
• rien de tout cela n'est spécifique aux AVL, les algorithmes sur les arbres rouge-noir et les tas font tout autant appel aux smart-constructors.
  

Une structure de données est une manière d'organiser et de stocker l'information pour en faciliter certaines opérations comme l'accès. Elle dispose d'une interface, un ensemble de procédures d'ajout, retrait, réorganisation, etc. des données. Elle conserve des données et des métadonnées (utilisées pour améliorer l'efficacité du traitement).

Un type de données abstrait est une définition des propriétés et de l'interface de la structure. Il admet généralement plusieurs implémentations, qui feront varier la complexité des opérations.

Une file double (en anglais, double-ended queue ou deque) est une collection ordonnée d'objets offrant la possibilité d'insérer ou d'extraire un élément à la tête ou à la queue. Il s'agit d'une généralisation des piles et des files. Son interface est constituée de :

• \[insertFirst(Q,x)\] : ajoute l'élément xx au début de la file double \[Q\] ;

• \[insertLast(Q,x)\] : ajoute l'élément xx à la fin de la file double \[Q\] ;

• \[removeFirst(Q)\] : extrait l'élément situé au début de la file double \[Q\] ;

• \[removeLast(Q)\] : extrait l'élément situé à la fin de la file double \[Q\].

Une liste est un ensemble dynamique d'objets ordonnés accessibles relativement les uns aux autres, sur base de leur position. Il s'agit d'une généralisation des piles, files et files doubles. Son interface est constituée de :

• \[insertFirst(L,x)\] : ajoute l'élément \[x\] au début de la liste \[L\] ;

• \[insertLast(L,x)\] : ajoute l'élément \[x\] à la fin de la liste \[L\] ;

• \[insertAfter(L,p,x)\] : ajoute l'élément \[x\] après \[p\] dans la liste \[L\] ;

• \[insertBefore(L,p,x)\] : ajoute l'élément xx avant pp dans la liste \[L\] ;

• \[removeFirst(L)\] : extrait l'élément situé au début de la liste \[L\] ;

• \[removeLast(L)\] : extrait l'élément situé à la fin de la liste \[L\]  ;

• \[remove(L,p)\] : extrait l'élément situé à la position \[p\]de la liste \[L\].

Un vecteur est un ensemble dynamique d'objets occupant des rangs entiers successifs permettant la consultation, le remplacement, l'insertion et la suppression d'éléments à des rangs arbitraires. Son interface est constituée de :

• \[at(V,r)\] : retourne l'élément situé au rang \[r\] dans le vecteur \[V\] ;

• \[replace(V,r,x)\] : remplace l'élément situé au rang \[r\] dans le vecteur \[V\]par \[X\]et retourne l'élément remplacé ;

• \[insert(V,r,x)\] : insère l'élément xx au rang rr dans le vecteur \[V\] ;

• \[remove(V,r)\]: extrait l'élément situé au rang rr du vecteur \[V\], en diminuant le rang des objets suivants ;

• \[size(V)\] : renvoie la taille du vecteur.

Une file à priorité est un ensemble dynamique d'objets classés par ordre de priorité, permettant d'extraire un objet ayant la plus grande priorité.
Cela suppose un ordre total défini sur les clés. Son interface est constituée de :

\[insert(S,x)\] : insérer l'élément xx dans la file \[S\] ;
\[maximum(S)\] : récupérer l'élément de \[S\] ayant la plus grande clé ;
\[extractMaximum(S)\] : supprimer et renvoyer l'élément de \[S\] ayant la plus grande clé.

Un arbre binaire de recherche est une structure d'arbre binaire implémentant un dictionnaire dont les opérations sont en \[O(h)\], \[h\]étant la hauteur de l'arbre. La propriété d'arbre binaire de recherche est la suivante, exprimée pour deux nœuds \[x\]et \[y\]:

• si \[y\] est dans le sous-arbre de gauche de \[x\], alors \[y.key\]<\[x.key\] ;

• si \[y\]est dans le sous-arbre de droite de \[x\], alors \[y.key\]≥\[x.key\].