TD d’algorithmique numéro 4 Natacha Portier et Daniel Hirschkoff semaine du 18 au 22 octobre 1999

Question 1 ⋆ codage de Huffman ⋆

Soit Σ un alphabet, c’est à dire un ensemble fini, que l’on suppose de cardinal au moins deux. Ses éléments sont appelés des lettres. Un codage binaire est une application injective de Σ dans l’ensemble des suites finies de 0 et de 1. Il s’étend de manière naturelle par concaténation à une application définie sur l’ensemble Σ^{∗} des mots de Σ, c’est à dire des suites finies de Σ. Un codage est de longueur fixe si tous les caractères sont codés par un mot binaire de même longueur. Il est préfixe si aucun mot du code n’est préfixe d’un autre mot du code.

Question 1.1

Le décodage d’un codage de longueur fixe est unique. Montrer qu’il en est de même pour un codage préfixe.

Question 1.2

Représenter un codage préfixe par un arbre binaire dont les feuilles sont les lettres de l’alphabet.

On considère un texte dans lequel chaque caractère c apparaît avec une fréquence f(c). À chaque codage préfixe de ce texte, représenté par un arbre T, est associé un coût, défini par

B(T) = ∑_{c∈C} f(c)d_{T} (c) ,

où d_{T} (c) est la taille du mot binaire encodant c. Un codage préfixe est optimal si pour ce texte il est optimal parmi les codages préfixes.

Montrer qu’à un codage préfixe optimal correspond un arbre binaire complet, i.e. dans lequel tout noeud interne a deux fils. Montrer qu’un tel arbre a |Σ| feuilles et a |Σ| − 1 nœuds internes.

Question 1.3

Montrer qu’il existe un code préfixe optimal pour lequel les deux caractères de plus faible fréquence sont frères, i.e. leurs codes sont de même longueur et ne diffèrent que par le dernier bit (propriété du choix glouton).

Soit T l’arbre d’un codage binaire optimal pour la fréquence f sur l’alphabet Σ. Soient x et y deux lettres soeurs et soit z leur mère. Alors, en considérant z comme un caractère de fréquence f(z) = f(x) + f(y) montrer que l’arbre T′ = T − {x, y} représente un codage préfixe optimal pour l’alphabet Σ′ = Σ − {x, y} ∪ {z} (propriété de sous-structure optimale).

En déduire un algorithme pour trouver un codage optimal.

Question 2 ⋆ chaînes d’une permutation ⋆

On considère une permutation p = (p[1], …, p[n]) de [1, …, n]. On pose p_{i} = (i, p[i]) ∈ ℕ^{2}; on dit que p_{i} domine p_{j} si i ≥ j et p[i] ≥ p[j]. On écrit cela p_{i} ≥ p_{j}, et on note p_{i} > p_{j} pour p_{i} ≥ p_{j} et p_{i} ≠ p_{j}.

On vérifie aisément que la relation ≥ est un ordre partiel.

Une chaîne est une suite p_{i_{1}}, …, p_{i_{k}} telle que p_{i_{1}} > ⋯ > p_{i_{k}}. On définit la hauteur de p_{i} comme la longueur maximale d’une chaîne dans l’ensemble des p_{j} tels que p_{i} ≥ p_{j}. Soit S_{h} l’ensemble des points de hauteur h.

Question 2.1

On fixe i, et on note h la hauteur de p_{i}. Montrer que le point de S_{h−1} le plus à droite parmi ceux qui sont à gauche de p_{i} est dominé par p_{i} (les p_{i} sont vus comme des points du plan).

Question 2.2

Proposer un algorithme pour calculer les hauteurs des éléments d’un ensemble de n points.

Comment exhibe-t-on une chaîne de longueur maximale?

Question 3 ⋆ mini-exercice sur les BST ⋆

Donner un contre-exemple à la propriété suivante:

“On suppose que la recherche d’une clef k dans un arbre binaire de recherche se termine sur une feuille. On considère trois ensembles: A, les clefs situées à gauche du chemin de recherche; B, les clefs situées le long du chemin de recherche, et C, les clefs situées à droite du chemin de recherche. Alors ∀(a, b, c) ∈ A × B × C. a ≤ b ≤ c”.