Arbres

Introduction

Dans ce document, on s'intéresse à une classe de problèmes d'optimisation connus sous le nom général de « problème du sac à dos ». On peut définir ce problème de la manière suivante : *« durant un cambriolage un voleur possède un sac dont la capacité (en poids par exemple) est limitée. Il se trouve face à un ensemble d'objets qu'il veut dérober. Chacun de ces objets est caractérisé par sa valeur et son poids. Le voleur souhaite optimiser la valeur totale des objets qu'il dérobe tout en ne dépassant pas le poids maximal supporté par son sac ».*

Ce problème est une abstraction pour un grand nombre d’autres problèmes d’optimisation. Il a été utilisé en cryptographie comme base pour différents schémas de chiffrement1. Il faut cependant noter que la plupart de ces schémas de chiffrement ne sont plus actuellement considérés comme sûrs. ^1, il est utilisé lors du chargement des bateaux ou d’avions, lors de la découpe de matériaux (minimisation des coupes « chutes » lors de la découpe), etc.

[Lire]

Introduction

Tableaux

---

Propriétés

• On peut ordonner des données dans un tableau mais l’algorithme de tri le plus rapide, pour un jeu de données aléatoires, est en $O(n \; \log n)$ ;
• On peut accéder à une donnée en $O(1)$ ;
• On peut rechercher une valeur efficacement en utilisant la dichotomie (si le tableau est trié !) : $O(\log n)$ ;
• Supprimer ou insérer une valeur n’est pas très efficace : $O(n)$ (sauf à la fin du tableau).

---

Dictionnaires

---

Propriétés

• Accéder à, supprimer et insérer une valeur se fait très efficacement : $O(1)$ ;
• Les données ne sont pas ordonnées.

---

Remarque

Dans la suite de ce document, on considérera que les valeurs des nœuds sont des entiers.

Arbres binaires

Définition

La notion de listes chaînées est parfaite pour structurer un ensemble d’élements destinés à être énumérés séquentiellement. Elle permet aussi d’implémenter les structures de piles et de files. Elle n’est cependant pas adaptée aux accès spécifiques à des positions données dans la séquence, puisqu’il faut alors parcourir toutes les cellules depuis le début de la liste jusqu’à la position souhaitée (complexité en $O(N)$).

Document de référence pour ce cours

Structures arborescentes

Lorsqu’on manipule une information présentant une certaine hiérarchie, il est commun de la représenter graphiquement :

[Lire]