FAQ algorithmesConsultez toutes les FAQ

Nombre d'auteurs : 6, nombre de questions : 125, dernière mise à jour : 23 août 2017  Ajouter une question

 

Cette FAQ a été réalisée à partir des questions fréquemment posées sur les forums de Developpez.com et de l'expérience personnelle des auteurs.

Nous tenons à souligner que cette FAQ ne garantit en aucun cas que les informations qu'elle propose sont correctes ; les auteurs font le maximum, mais l'erreur est humaine. Cette FAQ ne prétend pas non plus être complète. Si vous souhaitez devenir rédacteur, lisez ceci. Vous pouvez poster toutes vos remarques, questions, avis et corrections sur la FAQ sur le forum.

Nous espérons que cette FAQ saura répondre à un maximum de vos questions. Nous vous souhaitons une bonne lecture.

L'équipe algorithmique de Developpez.


SommaireTypes abstrait de données (15)
précédent sommaire suivant
 

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.

Exemple : la pile

On définit une pile. Ses opérations et leurs prototypes sont :

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

Les axiomes sont les suivants (pour toute pile p, pour tout élément e) :

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

Les opérations suivantes ne sont pas définies :

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

Les axiomes suffisent à eux seuls à déterminer d'une série d'instructions utilisant une pile.

Mis à jour le 9 juillet 2008 millie

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.


On l'implémente généralement :

  • 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)\].

Mis à jour le 9 juillet 2008 Alp dourouc05 snake264

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\].

On l'implémente généralement avec :
  • 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)\].

Mis à jour le 9 juillet 2008 Alp snake264

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.

Cette propriété n'est (habituellement) pas exprimable par le système de type et prend la forme d'un contrat :

  • 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.

L'invariant structurel est en général une propriété :

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

Mis à jour le 11 septembre 2009 SpiceGuid

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.

Mis à jour le 11 septembre 2009 SpiceGuid

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).

Mis à jour le 11 septembre 2009 SpiceGuid

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.

Un tas-min offre parfois les opérations supplémentaires suivantes :

  • 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.

Un tas-max est une autre variante de tas pour laquelle les opérations sont en ordre inverse de celles d'un tas-min :

  • 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.

Mis à jour le 11 septembre 2009 SpiceGuid

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.

L'idée du smart-constructor c'est d'encapsuler le maintien de la partie difficile de l'invariant structurel dans un constructeur intelligent qui a la même signature que le constructeur simple. De cette façon les algorithmes deviennent aussi simples qu'avec un type abstrait de données dont l'invariant structurel est moins fort. Il suffit de substituer le constructeur simple par le constructeur intelligent pour garantir le maintien de l'invariant structurel supplémentaire.

Exemple :

  • 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.

Mis à jour le 5 décembre 2009 SpiceGuid

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).

Mis à jour le 20 août 2017 dourouc05

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.

Mis à jour le 20 août 2017 dourouc05

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\].

On l'implémente généralement avec une liste liée. Complexité en temps des procédures : \[Θ(1)\], en espace : \[Θ(n)\].

On l'implémente généralement avec une liste liée. Complexité en temps des procédures : \[Θ(1)\], en espace : \[Θ(n)\].

Mis à jour le 22 août 2017 dourouc05

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\].

On l'implémente d'une manière similaire à la file double à l'aide d'une liste doublement liée et des sentinelles. Complexité en temps des procédures : \[Θ(1)\], en espace : \[Θ(n)\].

Mis à jour le 22 août 2017 dourouc05

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.

On peut l'implémenter à l'aide d'une liste liée ou d'un tableau extensible (généralement préféré pour des temps d'accès constants ; lors de la réallocation du tableau, il faudra veiller à doubler la taille pour amortir ce coût).

Mis à jour le 23 août 2017 dourouc05

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é.

Mis à jour le 23 août 2017 dourouc05

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\].

Un parcours infixe d'un tel arbre donnera les clés par ordre croissant.

Toutes les opérations auront une complexité dans le pire cas de \[O(h)\]. En supposant que les éléments ont été insérés en ordre aléatoire, on peut montrer que \[h∈O(logn)\].

Mis à jour le 23 août 2017 dourouc05

Proposer une nouvelle réponse sur la FAQ

Ce n'est pas l'endroit pour poser des questions, allez plutôt sur le forum de la rubrique pour ça


Réponse à la question

Liens sous la question
précédent sommaire suivant
 

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2018 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

 
Contacter le responsable de la rubrique Débuter - Algorithmique