Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Informatique (presque) débranchée Chapitre 8 Chapitre 8 Structures de données a

Informatique (presque) débranchée Chapitre 8 Chapitre 8 Structures de données avancées Une structure de données est une organisation logique des données permettant de simplifier ou d'accélérer leur traitement. 8.1. Pile En informatique, une pile (en anglais stack) est une structure de données fondée sur le principe « dernier arrivé, premier sorti » (ou LIFO pour Last In, First Out), ce qui veut dire que les derniers éléments ajoutés à la pile seront les premiers à être récupérés. Le fonctionnement est donc celui d'une pile d'assiettes : on ajoute des assiettes sur la pile, et on les récupère dans l'ordre inverse, en commençant par la dernière ajoutée. Primitives Voici les primitives communément utilisées pour manipuler des piles : • « empiler » : ajoute un élément sur la pile. Terme anglais correspondant : « Push ». • « dépiler » : enlève un élément de la pile et le renvoie. En anglais : « Pop » • « vide » : renvoie vrai si la pile est vide, faux sinon • « remplissage » : renvoie le nombre d'éléments dans la pile. Applications • Dans un navigateur web, une pile sert à mémoriser les pages Web visitées. L'adresse de chaque nouvelle page visitée est empilée et l'utilisateur dépile l'adresse de la page précédente en cliquant le bouton « Afficher la page précédente ». • L'évaluation des expressions mathématiques en notation post-fixée (ou polonaise inverse) utilise une pile. • La fonction « Annuler la frappe » (en anglais « Undo ») d'un traitement de texte Didier Müller 8-1 janvier 2019 Structures de données avancées mémorise les modifications apportées au texte dans une pile. • Un algorithme de recherche en profondeur utilise une pile pour mémoriser les nœuds visités. • Les algorithmes récursifs admis par certains langages (LISP, Algol, Pascal, C, etc.) utilisent implicitement une pile d'appel. Dans un langage non récursif (FORTRAN par exemple), on peut donc toujours simuler la récursion en créant les primitives de gestion d'une pile. Exercice 8.1 Exercice 8.1 Implémentez en Python une classe « pile » avec ces quatre méthodes, ainsi qu'une méthode « afficher » qui liste tous les éléments de la pile, du dernier entré au premier entré. 8.2. File Une file (queue en anglais ) est une structure de données basée sur le principe « Premier entré, premier sorti », en anglais FIFO (First In, First Out), ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés. Le fonctionnement ressemble à une file d'attente : les premières personnes à arriver sont les premières personnes à sortir de la file. Primitives Voici les primitives communément utilisées pour manipuler des files : • « ajouter » : ajoute un élément dans la file. Terme anglais correspondant : « enqueue » • « enlever » : renvoie le prochain élément de la file, et le retire de la file. Terme anglais correspondant : « dequeue » • « vide » : renvoie « vrai » si la file est vide, « faux » sinon • « remplissage » : renvoie le nombre d'éléments dans la file. Applications • En général, on utilise des files pour mémoriser temporairement des transactions qui doivent attendre pour être traitées. • Les serveurs d'impression, qui doivent traiter les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente (ou une queue). • Certains moteurs multitâches, dans un système d'exploitation, qui doivent accorder du temps-machine à chaque tâche, sans en privilégier aucune. • Un algorithme de parcours en largeur utilise une file pour mémoriser les nœuds visités. Exercice 8.2 Exercice 8.2 Implémentez en Python une classe « file » avec ces quatre méthodes, ainsi qu'une méthode « afficher » permettant de voir tous les éléments de la file, du premier entré au dernier entré. Files à priorités Dans une file à priorités, on peut effectuer trois opérations : • insérer un élément • supprimer le plus grand élément • tester si la file à priorités est vide ou pas Les principales implémentations de ces files à priorités sont le tas (voir § 8.9), le tas binomial et le tas de Fibonacci. Didier Müller 8-2 janvier 2019 Informatique (presque) débranchée Chapitre 8 Donald Knuth, né en 1938), professeur émérite à Stanford, auteur de l'ouvrage de référence sur l'algorithmique, en plusieurs volumes, intitulé « The Art of Computer Programming », considère les arbres comme « la structure la plus fondamentale de l'informatique ». 8.3. Arbres Un arbre est un graphe sans cycle, où des nœuds sont reliés par des arêtes. On distingue trois sortes de nœuds : • les nœuds internes, qui ont des fils ; • les feuilles, qui n'ont pas de fils ; • la racine de l'arbre, qui est l'unique nœud ne possédant pas de père. Traditionnellement, on dessine toujours la racine en haut et les feuilles en bas. La profondeur d'un nœud est la distance, i.e. le nombre d'arêtes, de la racine au nœud. La hauteur d'un arbre est la plus grande profondeur d'une feuille de l'arbre. La taille d'un arbre est son nombre de nœuds (en comptant les feuilles ou non). Les arbres peuvent être étiquetés. Dans ce cas, chaque nœud possède une étiquette, qui est en quelque sorte le « contenu » du nœud. L'étiquette peut être très simple (un nombre entier, par exemple) ou plus complexe : un objet, une instance d'une structure de données, etc. Les arbres sont en fait rarement utilisés en tant que tels, mais de nombreux types d'arbres avec une structure plus restrictive existent et permettent alors des recherches rapides et efficaces. Nous en reparlerons bientôt. 8.3.1. Parcours Parcours en largeur Le parcours en largeur correspond à un parcours par niveau de nœuds de l'arbre. Un niveau est un ensemble de nœuds ou de feuilles situés à la même profondeur. Ainsi, si l'arbre ci-contre est utilisé, le parcours sera A, B, C, D, E, F, G. Parcours en profondeur Le parcours en profondeur est un parcours récursif sur un arbre. Il existe trois ordres pour cette méthode de parcours. Le parcours en profondeur préfixé est le plus courant. Parcours en profondeur préfixé Dans ce mode de parcours, le nœud courant est traité avant le traitement des nœuds gauche et droit. Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, D, E, C, F, G. Parcours en profondeur suffixé Dans ce mode de parcours, le nœud courant est traité après le traitement des nœuds gauche et droit. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C, A. Didier Müller 8-3 janvier 2019 Structures de données avancées Jan Łukasiewicz (1878-1956) Ce mode de parcours correspond à une notation polonaise inverse (NPI, en anglais RPN pour Reverse Polish Notation), également connue sous le nom de notation post-fixée, utilisée par certaines calculatrices HP. Dérivée de la notation polonaise présentée en 1924 par le mathématicien polonais Jan Łukasiewicz, elle s'en différencie par l'ordre des termes, les opérandes y étant présentés avant les opérateurs et non l'inverse. HP-11C (1981-1989) On observant bien le clavier, on s'aperçoit qu'il n'y a ni parenthèses, ni signe =, ce qui peut surprendre… Sur ces modèles, on utilise des piles. L'expression « 3 × (5 + 10) » peut s'écrire en NPI sous la forme « 10 ENTER 5 + 3 × », ou encore sous la forme « 3 ENTER 10 ENTER 5 + × », illustrée sur le schéma ci-dessous : On peut représenter les expressions arithmétiques par des arbres étiquetés par des opérateurs, des constantes et des variables. La structure de l'arbre rend compte de la priorité des opérateurs et rend inutile tout parenthésage. L'arbre binaire ci-dessous représente l'expression arithmétique (y/2 - t) x (75 + z). Didier Müller 8-4 janvier 2019 Informatique (presque) débranchée Chapitre 8 Parcours en profondeur infixé Dans ce mode de parcours (qui n'est applicable qu'à des arbres binaires), le nœud courant est traité entre le traitement des fils gauche et droit. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, B, E, A, F, C puis G. Exercice 8.3 Exercice 8.3 Parcourez l'arbre ci-dessous selon les quatre méthodes vues précédemment (si possible). 8.4. Arbres binaires Dans un arbre binaire, chaque nœud possède au plus deux fils, habituellement appelés « gauche » et « droit ». Du point de vue des fils, l'élément dont ils sont issus au niveau supérieur est logiquement appelé père. 8.4.1. Types d'arbres binaires • Un arbre binaire entier est un arbre dont tous les nœuds possèdent zéro ou deux fils. • Un arbre binaire parfait est un arbre binaire entier dans lequel toutes les feuilles sont à la même hauteur. • L'arbre binaire parfait est parfois nommé arbre binaire complet. Cependant certains définissent un arbre binaire complet comme étant un arbre binaire entier dans lequel les feuilles ont pour profondeur n ou n-1 pour un n donné. Didier Müller 8-5 janvier 2019 Structures de données avancées La fonction floor(x) retourne l'entier inférieur ou égal à x. 8.4.2. Méthodes pour stocker des arbres uploads/Ingenierie_Lourd/ hffvivopp.pdf