Cette séance a pour objet l’étude d’une méthode de compression de données inventée par David Albert Huffman en 1952. Cette méthode permet de réduire la longueur du codage d’un alphabet et repose sur la création d’un arbre binaire.
Dans la suite, nous utiliserons un alphabet composé seulement des 8 lettres A, B, C, D, E, F, G et H.
[Lire]Quelle structure de données permet :
Un arbre binaire de recherche, ou ABR, est un arbre binaire avec la propriété suivante : quel que soit le nœud $x$, tous les nœuds situés dans le sous-arbre gauche de $x$ ont une valeur inférieure à la valeur du nœud $x$, et tous ceux situés dans son sous-arbre droit ont une valeur supérieure à la valeur du nœud $x$.
[Lire]Un arbre binaire est une structure de données abstraite formée d’un ensemble de nœuds organisés hiérarchiquement selon la définition par récurrence suivante :
Un arbre binaire est :
On note $T(r,g,d)$ l’arbre non vide dont la racine $r$ (on peut aussi indiquer l’étiquette de cette racine).
[Lire]Document de référence pour ce coursLa 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)$).
Lorsqu’on manipule une information présentant une certaine hiérarchie, il est commun de la représenter graphiquement :
[Lire]Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :
Une file est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des personnes dans une file d’attente (au guichet de la poste par exemple) :
[Lire]Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :
Une pile est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des assiettes dans une pile d’assiettes contenue dans une boite de profondeur quelconque mais étroite (ce qui empêche de manipuler les assiettes par le côté).
On peut donc seulement :
| Type Python | Type | Opération | Exemple | Complexité |
|---|---|---|---|---|
| N’existe pas | Tableau | Accès à un élément | tab[i] |
$O(1)$ |
| Modification d’un élément | tab[i] = x |
$O(1)$ | ||
| Effacement d’un élément | retire(tab, i) |
$O(n)$ | ||
| Insertion d’un élément | insere(tab, x, i) |
$O(n)$ | ||
| Recherche d’un élément | est_dans(tab, x) |
$O(n)$ |
Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.
Python possède dans la bibliothèque standard un grand nombre de structures de données, programmées de manière efficace.
Pour chaque module, on distingue :
sa réalisation (ou implémentation) : c’est le code lui-même.
son interface (API) : c’est l’énumération des fonctions définies dans le module qui sont utilisées depuis d’autres modules/programmes, les clients.
L’interface doit présenter une documentation dans laquelle tout ce que doit savoir le client doit être indiqué.
[Lire]Au zoo de Beauval, il y a 5 éléphants d’Asie, 17 écureuils d’Asie, 2 pandas d’Asie, etc. On représente cet inventaire à l’aide d’un dictionnaire, de façon suivante :
|
|
On représente de la même façon le zoo de La Flèche :
|
|
On souhaite se doter d’une fonction plus_grand_nombre() qui prend un zoo en paramètre et qui renvoie le nom de l’animal le plus représenté dans ce zoo.
Par exemple
Le tri par insertion a été étudié en classe de 1ère. Dans ce document, après un rappel du cours de 1ère, nous allons implémenter une version récursive de cet algorithme et ensuite utiliser la possibilité que les fonctions en Python ont d’accepter des fonctions comme paramètres, afin de rendre plus générale et utile cette fonction de tri.
Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ». Comment un joueur de carte fait-il pour trier les cartes ?
- Au début, la main gauche du joueur est vide et ses cartes sont posées sur la table.
- Le joueur prend alors sur la table les cartes, une par une avec sa main droite, pour les placer dans sa main gauche.
- Pour savoir où placer une carte dans son jeu, le joueur la compare avec chacune des cartes déjà présentes dans sa main gauche, *en examinant les cartes de la droite vers la gauche*.
- *À tout moment, les cartes tenues par la main gauche sont triées* ; ces cartes étaient, à l'origine, les cartes situées au sommet de la pile sur la table.
La méthode du tri par insertion est ilustré à ici , ou, de façon plus folklorique, ici .
[Lire]