N.B. : Le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copic et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.

Préambule : Les trois parties qui composent ce sujet sont indépendantes et peuvent être traitées par les candidats dans un ordre quelconque

Partie I: Logique et calcul des propositions

Lors de ses aventures au pays des merveilles rapportées par Lewis Carroll, Alice est souvent accompagnée par le chat de Cheshire. Ce félin énigmatique s'exprime sous la forme d'affirmations logiques qui sont toujours vraies.

Alice se trouve dans un corridor dont toutes les portes à sa taille sont fermées. La seule porte ouverte est nettement trop petite pour qu’elle puisse l’emprunter. Une étagère est fixée au-dessus de cette porte. Le chat dit alors à Alice: «L'un des flacons posés sur cette étagère contient un liquide qui te permettra de prendre une taille plus adéquate. Mais attention, les autres flacons peuvent contenir un poison fatal. *

Trois flacons sont effectivement posés sur l'étagère. Le premier est rouge, le second jaune, le troisième bleu. Une étiquette est collée sur chaque flacon. Alice lit l'inscription figurant sur chaque étiquette:

Flacon rouge : le flacon jaune contient un poison. Le flacon bleu ne contient pas un poison;
Flacon jaune : si le flacon rouge contient un poison, alors le flacon bleu aussi;
Flacon bleu: je ne contiens pas un poison, mais au moins l'un des deux autres flacons contient un poison.

Nous noterons

les variables propositionnelles correspondant au fait que les flacons rouge, jaune et bleu contiennent un poison.

Nous noterons

les propositions correspondant aux inscriptions sur les flacons rouge, jaune et bleu.

Question I. 1 Exprimer

sous la forme de formules du calcul des propositions dépendant de R. J et B.

Traduire les questions suivantes en formules du calcul des propositions puis résoudre les prohlèmes posés en utilisant le calcul des propositions (formules de De Morgan et/ou tables de vérité).

Question I. 2 Les inscriptions sur les trois flacons sont-elles compatibles (c'est-à-dire, peuvent-elles étre toutes vales)."

Question I. 3 Est-ce que les inscriptions sont dépendantes, c'est-à-dire est-ce qu'une inscription est impliquée par la comjungtion des dear aurres? Si oni. préciser la (ou lest dépendances

Question I. 4 Dans le cas où aucun des trois flacons ne contient un poison, est-ce qu'une ou plusieurs inscriptions sont fausses? Si oui, laquelle ou lesquelles?

Question 1.5 Si les trois inscriptions sont vraies, est-ce qu'un ou plusieurs flacons comiennent un poison? Si oui, lequel ou lesquels?

Question 1.6 Si seuls les flacons ne contenant pas un poison ont une inscription vraie, est-ce qu'un ou plusieurs facons ne contiennent pas un poison? Si oui, lequel ou lesquels?

Partie II : Automates et langages

Le but de cet exercicc est l'étude des propriétés de l'opération

de composition de deux automates finis déterministes.

Soit l'alphabet

un ensemble de symboles, soit

(parfois noté abusivement

) le symbole représentant le mot vide (

), soit

l'ensemble des mots composés de symboles de

, un automate fini déterministe sur

est un quintuplet

composé de :

Un ensemble d'états: ,
L'état initial: ,
Un ensemble d'états terminaux: ,
Une fonction de transition : , définic a priori sur une partie de .

Les valeurs de

seront représentées par un graphe dont les nouds sont les états. Un état initial sera entouré d'un cercle

et un état final sera entouré d'un double cercle (t).

Un automate déterministe est dit * complet * si

est totale (définic sur

tout entier).
Dans cette partie, les automates finis considérés seront complets.
Soit

l'extension de

définie par:

Le langage sur

reconnu par cet automate fini est:

Étude de l'exemple

Soit l'automate fini déterministe complet

dont la fonction de transition est définie par:

Question II. 1 Donner sans la justifier une expression régulière ou ensembliste représentant le langage reconnu par

Étude de l'automate

Soit l'automate fini déterministe complet

dont la fonction de transition est définie par:

Question II.2 Domer sans la justifier ane expression réguliére ou ensembliste représentant le langage recommu par

Composition des automates :

Soit l'opération interne

sur les automates finis déterministes détinie par:
Déf. II. 1 (Composition d'automates) Soient

deux automates finis déterministes, l'automate

est défini par:

On remarquera que les états de

sont des paires d'états de

.
Question II. 3 Construire l'automate

(seuls les états et les transitions atiles, c'est-à-dire accessibles depuis l'état initial, devrout êtré constraits).

Question II. 4 Caractériser le langage reconnu par

par une expression régulière ou ensembliste.

Étude de l'automate «composé »

Question II. 5 Montrer que : si

sont des automates finis déterministes complets, alors

est un automate fini déterministe complet.

Question II. 6 Montrer que

Question II.7 Montrer que:

Question II.8 Quelle relation liant les langages reconnus par les antomates

peut-on en déduire?

Partie III : Algorithmique et programmation en CaML

Cette partie doit être traitée par les étudiants qui ont utilisé le langage CaML dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Flles ne devront pas utiliser d'instructions itératives (for, while, ...) ni de références.
Lexplication du comportement d'une fonction doit au moins contenir:

L'objectif général.
-- Le rôle des paramètres de la fonction.
Les contraintes sur les valeurs des paramètres.
Les caractéristiques du résultal remoyé par la fonction.
Le rôle des variables locales à la fonction,
Le principe de l'algonthme.
Des arguments de terminaison du calcul quelles que soient les valeurs des paramètres.

Les équipements informatiques les plus courants sont basés sur des composants électroniques pour lesquels une information correspond à la présence ou l'absence d'un signal électrique sur une connexion. L'unité élémentaire d'information (dite binaire) est donc le « bit » prenant deux valeurs: 0 et 1 .

Toutes les domées sont ensuite codées en base 2 en utilisant un nombre suffisant de bits pour représenter toutes les valeurs utiles. Dans un cadre général où n'importe quelle valeur peut apparaître un nombre de fois quelconque, il est nécessaire d'utiliser un codage « uniforme » qui exploite le même nombre de bits pour représenter n'importe quelle valeur d'une même donnée. Par contre, si l'ensemble des valeurs possibles est connu ainsi que le nombre de fois où elles apparaissent (leur nombre d'occurrences), il est possible de choisir des codages qui utilisent moins de bits pour coder une même suite de valeurs. Ce type de codage, appelé stochastique, est couramment utilisé pour compresser des données, éest-à-dire réduire l'espace occupé par une information connue a priori.

Nous allons étudier dans cette partie une technique de construction dun codage minimal due à Huffman. Nous appliquerons cette technique à la compression et la décompression d'une suite de caractères dont le contenu est connu a priori.

1 Principe de l'algorithme

La suite de

caractères que nous allons traiter est notée

. Un même caractère peut apparaître plusieurs fois. La suite est donc composée de

caractères distincts appartenant à l'ensemble

avec

. Nous appellerons nombre d'occurrences d'un caractère

de la suite le nombre de fois que ce caractère ligure dans la suite. La fonction

renvoie le nombre d'occurrences de

dans la suite étudiće.

1.1 Principe du codage

Dans une première étape, définissons formellement la notion de codage.

1.1.1 Codage d'un caractère

Déf. III. 1 Une clé de codage binaire d'un ensemble de caractères est une application qui associe à chaque caractère un code composé d'une suite non vide de valeurs binaires ( 0 ou I).

Exemple III.

sont des clés de codage possibles pour l'ensemble

. La seconde clé est uniforme car elle utilise le même nombre de bits pour chaque caractère.

1.1.2 Codage d'une suite

Une clé de codage permet de coder une suite de caractères par une suite de bits en remplaçant chaque caractère de la suite par son code.

Si nous considérons la suite abad, son code est 000100111 selon la première clé et 00011011 sclon la clé uniforme (seconde clé). Remarquons que le premier codage utilise 9 bits alors que le codage uniforme

utilise que 8 bits.

Par contre, si nous considérons la suite dadbcd, son code est 10010100111 selon la première clé et 110011011011 selon la clé uniforme. Remarquons que le codage uniforme utilise 12 bits alors que le premier codage n'utilise que 11 bits.

La première clé de codage semble donc plus adaptée aux suites contenant un plus grand nombre de

que de

1.1.3 Représentation en CaML

Un caractère est représenté par le type de base char.
Une suite de caractères est représentée par le type suite équivalent à une liste de caractères.
Un code binaire est représenté par le type code équivalent à une liste de booléens.
Une clé de codage qui associe à un caractère son code binaire est représentée par le type cle équivalent à une liste de paires caractère/code binaire.

type suite == char list;;
type code == boolean list:;
type cle == (char * code) list;;

1.1.4 Application au codage d'une suite

Nous supposons que nous disposons déjà d'une clé de codage nous permettant de coder la suite de caractères.

Question III.1 Écrirc en (aML une fonction coder de type suite

cle

code telle que l'appel (coder

c) remoie le code de la suite de caractères

selon la clé de codage c. Nous supposons que la clé c contient tous les caractères de la suite s. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question III. 2 Expliquer la fonction coder proposée pour la question précédente.
Question III. 3 Calculer me estimation de la complexité dans le pire cas de la fonction coder en fonction de la taille des listes set c. Cette estimation ne prendra en compte que le nombre d'appels récursifs cffectués.

1.1.5 Propriétés d'un codage

La définition précédente est trop générale pour permeture une opération de décodage simple. Nous étudierons donc des codages possédant des propriétés supplémentaires.

Nous noterons

l'image de

selon la clé de codage.

contient donc l'ensemble des valeurs de code possibles.

Déf. III. 2 Une clé de codage est séparable si et seulement si:

Cette propriété indique que le code d'un caractère n'est jamais un préfixe du code d'un autre caractère. Elle est nécessaire pour permettre le décodage.

Les deux premiers exemples sont des clés séparables. Le troisième exemple n'est pas séparable.

Déf. III. 3 Une clé de codage est optimale si et seulement si:

Cette propriété indique que le

-ème bit permet de distinguer

.
Les deux premiers exemples sont optimaux. Le troisième exemple n'est pas optimal.
Cette propriété permet de minimiser la taille des codes indépendamment de la suite considérée.
La propriété suivante prend celle-cí en compte.
Nous noterons

le nombre de bits utilisé pour coder le caractère

.
Le coût du codage de la suite est alors:

Déf. III. 4 Un codage est minimal pour une suite de caractères donnée s'il permet de coder tous les caractères en utilisant le plus petit nombre de bits possible lors du coduge de la suite, c'est-à-dire s'il permet de minimiser

L'algorithme étudić dans cette partie construit une clé de codage optimale séparable assurant un codage minimal pour une suite de caractères donnée. Nous appellerons cette clé * minimale».

1.2 Arbre de Huffman

La clé de codage d'un ensemble de caractères peut être représentée par un arbre binaire dont certains nœuds sont étiquetés par un caractère et toutes les arêtes sont étiquetées par la valeur d'un bit de code.

Nous considérerons uniquement des arbres dont toutes les feuilles contiennent un caractère.

1.2.1 Structure arborescente d'un codage

Les arbres suivants correspondent aux trois exemples précédents :

Déf. III. 5 Un arbre binaire est complet si et seulement si chaupe neud de cet arbre possède soit deux fils, soit aucun fils (ces nouds sont alors appelés des feuilles).

Question III. 4 Montrer que la clé de codage associée à an arbre complet est optimale.
Question III. 5 Monirer que la clé de codage associée à un arbre complet est séparable si et seulement si seules les feuilles de cet arbre contiennent des caractéres.

Les arbres utilisés pour construire une clé de codage optimale séparable seront donc tels que :

les nœuds ont deux fils et ne contiennent pas de caractère;
les teuilles n'ont pas de fils et contiennent un caractère.

Nous appellerons ces arbres des arbres de codage. Nous supposerons par la suite qu'un même caractère ne figure pas dans plusieurs feuilles distinctes.

Déf. III.6 Soit une suite

de caractères appartenant à l'ensemble

avec les nombres d'occurrences

, à chaque arbre de codage de cet ensemble est associé un arbre appelé arbre de Huffinan obtenu en ajoutant à chaque feuille de l'arbre de codage contenaut le caractère vj l'occurrence

du caractère

dans la suite '

. Chaque feuille de l'arbre de Huffman contient donc un caractère

et le nombre d'occurrence

dans

1.2.2 Représentation en CaML

Un arbre de Huffman est représenté par le type arbre:
type arbre =
Vide |
Feuille of char * int |
Noeud of arbre * arbre; ;
Une feuille contient un caractère ainsi que le nombre d'occurrences de ce caractère dans la suite

. Le cas Vide permet de construire des arbres non complets. Il ne sera utilisé que lors de la reconstruction de l'arbre dans la phase de décodage.

Exemple III. 2 Les deux premiers excmples précúdents seront codés pour la suite daacadbed par:
Noeud (
Noeud(Feuille('a', 3),
Noeud(Feuille('b', 1), Feuille('c', 2))),
Feuille('d', 3))

Noeud (
Noeud(Feuille('a',3),Feuille('b',1)),
Noeud(Feuille('c', 2), Feuille('d', 3)))
Le dermier exmple né peur pas être codé car les nouds ne peurent pas contenir de caractères (clé de codage séparable).

Une liste d'arbres est représentée par le type liste.
type liste == arbre list; ;

1.2.3 Calcul du nombre d'occurrences

Les feuilles des arbres sont étiquetées jar un caractère et par un entier qui indique le nombre d'occurrences du caractère dans la suite étudiée. Le nombre global des occurrences des différents caractères qui figurent dans un arbre correspond alors à la somme des nombres d'occurrences de toutes les feuilles de cet arbre. La fonction

est ainsi étendue à l'arbre

Question III. 6 Écrire en CaML anc fonction nombre de type arbre -> int telle que l'appel (nombre a) remoie le nombre d'occurrences

des caractères figurant dans l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

1.3 Codage de Huffman

1.3.1 Principe général

L'algorithme de Huffman exploite la connaissance du contenu de la suite à coder pour générer une clé de codage minimale. Son principe repose sur la construction d'un arbre de Huffman minimal par transformations successives d'un arbre de Huffman quelconque.

L'algorithme découle de l'idéc naturelle suivante : «Pour minimiser le nombre de bits utilisés par le codage d'une suite de caractères. il faut associer le plus petit nombre de bits aux caractères les plus fréquents et le plus grand nombre de bits aux caractères les moins fréquents ».

La longueur d'un code correspond à la profondeur du caractère associé dans l'arbre. Pour optimiser les codes, il faut donc que les caractères les plus rares étiquettent les feuilles les plus profondes de l'arbre et que les caractères les plus nombreux étiquettent les feuilles les moins profondes.

Réduire le coût d'un codage consiste donc à échanger une des leuilles les plus profondes de l'arbre avec un sous-arbre dont la profondeur et le nombre d'occurrences sont strictement plus petits.

Pour éviter les nombreux parcours d’arbres intermédiarres non minimaux pour rechercher les candidats à un échange, l'algorithme de Huffman construit directement l'arbre de Huffman minimal. Pour cela, il manipule un cnsemble de sous-arbres de Huffman minimaux partiels. Cet ensemble contient initialement l'ensemble des feuilles étiquetées par les caractères de

. Chaque étape de l'algorithme remplace les deux sous-abbes

contenant les plus petits nombres d'occurrences par un
arbre de Huffman dont les fils sont

. L'algorithme s'arrête lorsque l'ensemble ne contient plus qu'un seul arbre qui est alors l'arbre de Huffman minimal de l'ensemble des caractères de la suite.

Question III. 7 Appliquer l'algorithme précédent pour construire l'arbre de Huffman correspondant à l'exemple darbord en cétaillant chaque enscmble intermédiaire.

1.3.2 Preuve de minimalité

Considérons

un arbre de Huffman de

. L'arbre

est obtenu en permutant les feuilles

dans

Question III. 8 Calculer la différence, notée

, entre le coût de

et le coût de

en fonction des occurrences at profondams de vioty.

Question III. 9 Montrer que dans un arbre de Huffman minimal, les feuilles de profondeur maximale contiennent des caractères d'occurrence minimale.

Considérons

un arbre de Iluffman minimal de

sont deux caractères d'occurrence minimale possćdant un même noud père

dans

. L'arbre

est obtenu en enlevant les feuilles

dans

et en considérant que

est une feuille d'occurrence

Question III. 10 Montrer que II' est un arbre de Huffman minimal (Indication: supposons que H est minimal ct que

'est pas minimal).

Question III. 11 Montrer que l'arbre de Huffman construit par l'algorithme de Huffman est minimal (lndication: II correspond à un problème de taille

correspond à un problème de taille

2 Préliminaires: Tri par insertion

L'algorithme de Huffman extrait de l'ensemble les sous-arbres contenant les plus petits nombres d'occurrences. Pour cela, nous exploiterons une liste de sous-arbres triée selon le nombre d'occurrences. Cette liste sera triée par un algorithme de tri par insertion.

Question III. 12 Ecrire en CaML une fonction comparer de type
arbre

arbre -> boolean telle que l'appel (comparer a1 a2) renvoie la valeur faux si

est strictement plus petit que

et la valeur vrai sinon.

Question III.13 Érire en CaML me fonction inserer de type arbre -> liste -> liste telle que l'appel (inserer a 1) remoic la liste d'arbres obtenue en insérant l'arbre a dans la liste 1 en respectant l'ordre croissant du nombre d'occurrences. Nous supposons que la liste 1 respecte l'ondre croissant du nombre d'occurrences. Cette fonction devra être récursive ou faire appel

des fonctions anxiliaires récursives.

Question III. 14 Écrire en CaML me fonction trier de type 1 iste

liste telle que l'appel (trier 1) remoie we liste d'arbres triée selon l'ordre croissant des nombres d'occurrences et composée des mémes arbres que 1 . Caté fonction devra être récursive ou faire appel à des fonctions auviliaires récursives.

3 Construction des codes de Huffman

Pour calculer le code minimal pour chaque caractère de la suite, il faut déterminer l'ensemble des caractères distincts et le nombre d'occurrences de chaque caractère, puis construire l'arbre par fusion successive des éléments de cet ensemble.

3.1 Construction de la liste d'occurrences

Question III. 15 Écrire en CaML une fonction ajouter de type char

liste

liste telle que l'appel (ajouter

) remoie une liste de feuilles étiquetées par les mêmes caractèrés que 1 et telle que si 1 contenait

alors son occurrence est augmentée de 1 et si 1 ne contenail pas

, le résultat contient v avec l'occurrence 1. Nous supposons que v figure au plus ane fois dans 1. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question III. 16 Écrire en CaML me fonction compter de type suite

listetelle aue l'appel (compter s) renvoie une liste de feuilles étiquetées par les mêmes caractères que s et par les nombres d'occurrences de ces caractères dans s. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

3.2 Construction de l'arbre

L'algorithme de Huffman de construction de l'arbre minimal présenté dans la sous-section 1.3.1 consiste à remplacer les deux sous-arbres ayant les plus petits nombres d'occurrences par le neud ayant pour fils ces deux sous-arbres tout en préservant l'ordre de la liste triée.

Question III. 17 Écrire en CaML ane fonction fusionner de type liste

arbretelle que l'appel (fusionner 1) sur ane liste non vide de feuilles 1 triée selon le nombre d'occurrences des caractères renvoie un arbre de Huffman contenant les mêmes caractères que la liste 1 et carrespondant au codage minimal de la suite. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question III. 18 Expliquer la fonction fusionner proposée pour la question précédente.
Question III. 19 Écrire en CaML une fonction huffmande type suite

arbre telle que l'appel (huffman s) renvoie un arbre de Huffman comenant les mêmes caractères que la suite s et correspondant au codage minimal de la suite.

4 Codage d'une suite

L'étape précédente a permis de construire un arbre dont les chemins qui conduisent à chaque caractère sont étiquetés implicitement ( 0 pour le fils gauche, I pour le fils droit) par le code associé à ce caractère. Pour éviter de multiples parcours de l'arbre lors du codage d'une suite de caractères, il faut construire une clé de codage à partir de l'arbre qui associe à chaque caractère son code puis parcourir la suite pour remplacer chaque caractère par son code en utilisant la fonction coder proposée dans la question III.1.

4.1 Construction de la clé

Question III. 20 Écrive en CaML une fonction construire de type arbre

cle telle que l'appel (construire a) remoie mé clé de codage associant à chaque curactère contena dans l'arbre de Huffman a son code, c'est-à-dire la suite de valeurs binaires (O ou I) correspondan au chemin suvi dans l'arbre pour attendre le caractère. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

5 Décodage d'une suite

Le principal défaut du codage de Huffman est la nécessité de transmetre la clé de codage avec chaque suite codée. En effet, il faut reconstruire l'arbre de lluffanampropre à chaque suite codée pour décoder celle-ei par un parcours de l'arbre en suivant chaque code de la suite codée.

5.1 Reconstruction de la clé

Question III. 21 Écrire en CaML une fonction reconstruirede type cle -> arbre telle que l'appel (reconstruire c) remoie un arbre de Huffinan obtenu à partir de la clé de codage c, c'est-à-dire contenant les mêmes caractères que c placées dans l'arbre selon le code associé au caractère dans la clé c. L'occurrence du caractère c prendra la valeur 0 . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

5.2 Décodage de la suite

Question III. 22 Écrire en CaML ane fonction decoder de type
suite

arbre

suite telle que l'appel (decoder

a) nawie wae suite de caractéres contespondant au décodage de la suite de valeurs binaires (t) ou 11 comenaes dans s. Ce décodage est effectue par un parcours de l'arbue de Huffman den saivan les chemins correspondam aux valeurs binaires contenues dans s. Cette function deva être récursive ou faire appel à des fonctions auxiliaires récursives.

6 Optimisation de la construction de l'arbre

Question III. 23 Quelle est la fonction la plus souvent appelée lors de la construction de l'arbre?
Question III. 24 Proposer une ou plusieurs modifications des structures de données et/ou des fonctions pour réduire le nombre d'appels à cette fonction.

La construction de l'arbre exploite une liste triée d'arbres. L'algorithme étudié dans la section 3.1 construit la liste dans an ordre quelcongue puis effectue un at de la liste obtenue. If est possible d'éviter ce tri par une construction de la liste qui assure que les leuilles soient triées selon l'ordre croissant des nombres d'occurrences.

Question III. 25 Écrive en CaML ane fonction a jouter de type
char

liste

listetelle que l'appel (ajouter v 1) sur une liste 1 de feulles triée selon l'ordre croissant des nombres d'occurrences remove une liste de feuilles triée selon l'ordre
croissant des nombres d'occurrences. étiquetées par les mêmes caractères que 1 et telle que si 1
contenait v alors son occurrence est augmentée de

et si

ne contenait pas v. le résultat contient
vavec l'occurrence 1. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires
récursives.

Partie III : Algorithmique et programmation en PASCAL

Cette partie doit être traitée par les étudiants qui ont utilisé le langage PASCAL dans le cadre des enseignements d'informatique. Les fonctions écrites devront êrre récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (for, while, repeat,...).
L'explication du comportement d'une fonction doit au moins contenir:

L'objectif général,
Le rôle des paramètres de la fonction,
Les contraintes sur les valeurs des paramètres,
Les caractéristiques du résultat renvoyé par la fonction,
Le rôle des variables locales à la fonction,
Le principe de l'algorithme,
Des arguments de terminaison du calcul quelles que soient les valeurs des paramètres.

Toutes les données sont ensuite codées en base 2 en utilisant un nombre suffisant de bits pour représenter toutes les valeurs utiles. Dans un cadre général où n'importe quelle valeur peut apparaître un nombre de fois quelconque, il est nécessaire d'utiliser un codage * uniforme * qui exploite le même nombre de bits pour représenter n'importe quelle valeur d'une même donnée. Par contre, si l'ensemble des valeurs possibles est connu ainsi que le nombre de fois où elles apparaissent (leur nombre d'occurrences), il est possible de choisir des codages qui utilisent moins de bits pour coder une même suite de valeurs. Ce type de codage, appelé stochastique, est couramment utilisé pour compresser des données, c'est-à-dire réduire l'espace occupé par une information connue a priori.

Nous allons étudier dans cette partie une technique de construction d'un codage minimal due à Huffman. Nous appliquerons cette technique à la compression et la décompression d'une suite de caractères dont le contenu est connu a priori.

1 Principe de l'algorithme

La suite de

caractères que nous allons traiter est notée

. In même caractère peut apparaître plusieurs fois. La suite est donc composée de

caractères distincts appartenant à l'ensemble

avec

. Nous appellerons nombre d'occurrences d'un caractère

de la suite le nombre de fois que ce caractère figure dans la suite. La fonction

renvoie le nombre d'occurrences de

dans la suite étudiée.

1.1 Principe du codage

Dans une première étape, définissons formellement la notion de codage.

1.1.1 Codage d'un caractère

Déf. III. 1 Une clé de codage binaire d'un ensemble de caractères est ane application qui associè à chaque caractère an code composé d'une suite non vide de valears binaires ( 0 ou 1 ).

Exemple III.

soma des clés de codage possibles pour l'ensemble

. La seconde clé est anifome car elle utilise le même nombre de birs pour chaque caraçère.

1.1.2 Codage d'une suite

Une clé de codage permet de coder une suite de caractères par une suite de bits en remplaçant chaque caractère de la suite par son code.

Si nous considérons la suite abol, son code est 000100111 selon la première clé et 00011011 selon la clé uniforme (seconde clé). Remarquons que le premier codage utilise 9 bits alors que le codage uniforme n'utilise que 8 bits.

La première clé de codage semble donc plus adaptée aux suites contenant un plus grand nombre de

que de

1.1.3 Représentation en PASCAL

Un caractère est représenté par le type de base CHARACTER.
Une suite de caractères est représentée par le type de base SUTTF représentant une liste de caractères.

Un code binaire est représenté par le type de basc CODE représentant une liste de booléens.
Une clé de codage qui associe à un caractère son code binaire cst représentée par le type de base CLE représentant une liste de paires caractere/code biname.

Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:

NIL représente la suite, le code et la clé de codage vide,
FUNCTION SAjouter(C:CHARACTER; S: SUITE) : SUITE; renvoie une suite de caractères composée d'une première valeur et du reste de la suite contenu dans ,
FUNCTION S_Premier ( : SUITP.) : CHARACTER; renvoie le premier caractère de la suite s ,
FUNCTION S_RESte(s: SUITE) : SUL'IE; renvoie le reste de la suite privée de son premier caractère,
FUNCTION S_Juxtaposer(s1, s2: SUITE): SUITE; renvoie la suite composée de la suite suivie de la suite ;
FUNCTION C_Ajouter (b:BOOLEAN;C:CODE) : CODE; tenvoie un code composé d'un premier bit b et du reste du code contenu dans c ,
FUNCTION C.Premier ( : CODE) : BOOLEAN; renvic le premier bit du code .
FUNCTION C_Reste (c:CODE) : CODE; renvoie le reste du code c privée de son premier bit,
FUNCTION C_Juxtaposer ( : CODE) : CODE; renvoic le code composé du code suivi du code c 2 :
FUNCTION DAjouter (v:CHARACTER; c:CODE; d:CLE) : CLE; renvoic unc clé composée d'un premier caractère , de son code et du reste de la clé contenu dans ,
FUNCTION D_Caractere (d:CLE) : CHARACTER; renvoie le premier caractère de la clé d,
FUNCTION D_COde ( : CLE) : CODE; renvoie le code du premier caractère de la clé ,
FUNCTION D.Reste (c:CLE) : CLE; renvoic le reste de la clé d privée de son premier caractère et du code de celui-ci.
FUNCTION D_Juxtaposer (d1,d2:CLE) : CLE; renvoie la clé composée de la clé d1 suivi de la clé d2.

1.1.4 Application au codage d'une suite

Nous supposons que nous disposons déjà d'une clé de codage nous permettant de coder la suite de caractères.

Question III. 1 Écrire en PASCAL une fonction coder (s : SUITE; c: CLE) : CODE; telle que l'appel coder

remoie le code de la suite de caractères s selon la clé de codage c. Nous supposons que la clé c contient tous les caractères de la suite s. Cette fonction devra êrre récursive ou faire appel à des fonctions auxiliaires récursives.

Question III. 2 Expliquer la fonction coder proposée pour la question précédente.
Question III. 3 Calculer me estimation de la complexité dans le pire cas de la fonction coder en fonction de la taille des listes set c. Cerre estimation ne prendra en compre que le nombre d'appels récursifs effectués.

1.1.5 Propriétés d'un codage

La définition précédente est trop générale pour permettre une opération de décodage simple. Nous étudierons donc des codages possédant des propriétés supplémentaires.

Nous noterons

l'image de

selon la clé de codage.

contient donc l'ensemble des valeurs de code possibles.

Déf. III. 2 Une clé de codage est séparable si et seulement si:

Cette propriété indique que le code d'un caractère n'est jamais un préfixe du code d'un autre caractère. Elle est nécessairc pour permettre le décodage.

Les deux premiers exemples sont des clés séparables. Le troisième exemple n'est pas séparable.
Déf. III. 3 Une clé de codage est optimale si et seulement si:

Cette propriété indique que le

-ème bit permet de distinguer

le mombre de bits utilisé pour coder le caractère

.
Le coût du codage de la suite est alors :

Déf. III. 4 Un codage est minimal pour une suite de caractères donnée s'il permet de coder tous les caractères en utilisant le plus petit nombre de bits possible lors du codage de la suite, c'est-à-dire s'il permet de minimiser

L'algorithme étudié dans cette partie construit une clé de codage optimale séparable assurant un codage minimal pour unc suite de caractères donnée. Nous appellerons cette clé * minimale *.

1.2 Arbre de Huffman

La clé de codage d'un ensemble de caractères peut être représentée par un arbre binaire dont certains næuds sont étiquetés par un caractère et toutes les arêtes sont étiquetées par la valeur d'un bit de code.

Nous considércrons uniquement des arbres dont toutes les feuilles contiennent un caractère.

1.2.1 Structure arborescente d'un codage

Les arbres suivants correspondent aux trois exemples précédents :

Déf. III. 5 Un arbre binaire est complet si et seulement si chaque noud de cet arbre possède soit deux fils. soit aucun fils (ces nouds sont alors appelés des feuilles).

Question III.4 Montrer que la clé de codage associée à un arbre complet est optimale.
Question III. 5 Montrer que la clé de codage associée à un arbre complet est séparable si et seulement si seules les feuilles de cet arbre contiennent des caractères.

Les arbres utilisés pour construire une clé de codage optimale séparable seront donc tels que:

les nœuds ont deux fils et ne contiennent pas de caractère;
les feuilles n'ont pas de fils et contiennent un caractère.

Nous appellerons ces arbres des arbres de codage. Nous supposerons par la suite qu'un même caractère ne figure pas dans plusieurs feuilles distinctes.

Déf. III. 6 Soit ane suite

de caractères appartenant à l'ensemble

avec les nombres d'occurrences

, à chaque arbre de codage de cet ensemble est associé un arbre appelé arbre de Huffman obtem en ajoutant à chaque feuille de l'arbre de codage contenant le caractère "j l'occurrence

du caractère

dans la suite

. Chaque feuille de l'arbre de Huffman comient donc un caractère

et le nombre d'occurrence

dans

1.2.2 Représentation en PASCAL

Un arbre de Huffman est représenté par le type de base ARBRE.
Une feuille contient un caractère ainsi que le nombre d'occurrences de ce caractère dans la suite

. L'arbre vide utilisé comme une feuille sans caractère permet de construire des arbres non complets. Il ne sera utilisé que lors de la reconstruction de l'arbre dans la phase de décodage.

Une liste d'arbres est représentée par le type de base LISTE.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:

NIL représente l'arbre vide et la liste vide d'arbres,
FUNCTION Noeud(g:ARBRE;d:ARBRE) : ARBRE; est une fonction qui renvoie un neud dont le fils gauche et le fils droit de la racine sont respectivement et ,
FUNCTION Feuille(v:CHARACTER; : INTEGER) : ARBRE; est une fonction qui renvoie une feuille étiquetée par le caractère et le nombre d'occurrences de ce caractère ,
FUNCTION EstFeuille(a:ARBRE) : BOOIFAN; est une fonction qui renvoie la valeur vrai si a est une feuille et la valeur faux sinon,
FUNCTION EStNOeud(a:ARBRE) : BOOLEAN; est une fonction qui renvoie la valeur vrai si a est un nœud et la valeur faux sinon,
FUNCTION Valeur (a:ARBRE) : CHARACTER; est une fonction qui renvoie le caractère qui étiquette la feuille ,
FUNCTION Nombre (a:ARBRE) : INTEGER; est une fonction qui renvoie le nombre d'occurrences du caractère qui étiquette la feuille ,
FUNCTION Gauche (a:ARBRE) : ARBRE; est une fonction qui renvoie le fils gauche du noud a,
FUNCTION Droit (a: ARBRE) : ARBRE; est une fonction qui renvoie le fils droit du noud a;
FUNCTION LAjouter (a:ARBRE; 1: LISTE) : LISTE; renvoie une liste d'arbres composée d'un premier arbre a et du reste de la liste contenu dans 1 ,
FUNCTION L_Premier(1:LISTE): ARBRE; renvoie le premier arbre de la liste 1,
FUNCI'ION L.Reste(1:LISTE):LISTE; renvoie le reste de la liste 1 privée de son premier arbre,
FUNCTION L_Juxtaposer(11,12:LISTE): LISTE; renvoie la liste composée de la liste 11 suivie de la liste 12.

Exemple III. 2 les deux premiers exemples prérédents seront codés pour la suite daacadbed par:
Noeud (

Noeud(Feuille('a', 3),
    Noeud(Feuille('b',1),Feuille('c',2))),
Feuille('d',3))

Noeud (
Noeud(Feuille('a', 3), Feujl]e('b', 1)),
Noeud(Feuille('c',2),Feuille('d',3)))
Le demier exemple ne peut pas être codé car les nauds ne peureut pas contenir de caractères (clé de codage séparable).

1.2.3 Calcul du nombre d'occurrences

Les feuilles des arbres sont étiquetées par un caractère et par un entier qui indique le nombre d'occurrences du caractère dans la suite étudiée. Le nombre global des occurrences des différents caractères qui figurent dans un arbre correspond alors à la somme des nombres d'occurrences de toutes les feuilles de cet arbre. La fonction

est ainsi étendue à l'arbre

Question III. 6 Écrite en PASCAL une fonction nombre (a : ARBRE) : INTEGER telle que l'appel nombre (a) renoie le nombre d'occurrenes O(a) des caractives figuram dans l'arbre a. Cette fonction devra êrre récursive ou faire appel à des fonctions auviliaires récursives.

1.3 Codage de Huffiman

1.3.1 Principe général

L'algorithme de Huffman exploite la comaaissance du contenu de la suite à coder pour générer une clé de codage minimale. Son principe repose sur la construction d'un arbre de Huffman minimal par transformations successives d'un arbre de Huffman quelconque.

L'algorithme découle de l'idée naturelle suivante: «Pour minimiser le nombre de bits utilisés par le coalage d'une suite de caractères, il faut associer le plus petit mombre de bits aux caractères les plus fréquents of le pluc grand nombre do bits ant caracteres les moins fréquents ".

La longueur d'un code correspond à la profondeur du caractère associé dans l'arbre. Pour optimiser les codes, il faut done que les caractères les plus rares étiquettent les féuilles les plus profondes de l'arbre et que les caractères les plus nombreux étiquettent les feuilles les moins protondes.

Réduire le coût d'un codage consiste donc à échanger une des fenilles les plus protondes de l'arbre avec un sous-arbre dont la profondeur et le nombre d'occurrences sont strictement plus petits.

Pour éviter les nombreux parcours d'arbres intermédiaires non minimaux pour rechercher les candidats à un échange, l'algorithme de Huffman construit directement l'arbre de Huffonan minimal. Pour cela, il manipule un ensemble de sous-arbres de Huffman minimaux partiels. Cet ensemble contient initialement l'ensemble des feuilles étiquetées par les caractères de

. Chaque étape de l'algorithme remplace les deux sous-arbres

contenant les plus petits nombres d'occurrences par un
arbre de Huffman dont les fils sont

. L'algorithme s'arrête lorsque l'ensemble ne contient plus qu'un seul arbre qui est alors l'arbre de Huffman minimal de l'ensemble des caractères de la suite.

Question III. 7 Appliquer I algonthme précident pour construire l'arbre de Hulfinan correspondant à l'exemple dadbod en détaillant chaure ensemble intermédiaire.

1.3.2 Preuve de minimalité

Considérons

un arbre de Huffman de

. Larbre

est obtenu en permutant les feuilles

dans

Question III. 8 Calculer la différence, notée

, entre le coût de

et le coût de

en fonction des occurrences et profondeurs de

Question III. 9 Montrer que dans un arbre de Huffman minimal, les feuilles de profondeur maximale contiennent des caractéres d'ocewrance' minimale.

Considérons

un arbre de Huffaan minimal de

sont deux caractères d'occurrence minimale possédant un même noud père

dans

. L'arbre

est obtenu en enlevant les feuilles

dans

et en considérant que

est une feuille d'occurrence

Question III. 10 Montrer que II' est un arbre de Huffman minimal (Indication : supposons que

est minimal et que

n'est pas minimal).

Question III. 11 Montrer que l'arbre de Huffman construit par l'algorithme de Huffman est minimal (lndication:

correspond à un problème de taille n,

correspond à un problème de taille

2 Préliminaires: Tri par insertion

Lalgorithme de Huffman extrait de l'ensemble les sous arbres contenant les plus petits nombres d'occurrences. Pour cela, nous exploiterons une liste de sous-arbres triée selon le nombre d'occurrences. Cette liste sera triée par un algorithme de tri par insertion.

Question III. 12 Écrire en PASCAL une fonction comparer (a1 : ARBRE; a2 : ARBRE) : BOOLEAN; telle que l'appel comparer (a], a2) runoie la valeur fux si a 2 contiont moins d'occurrences que a1 et la valeur vrai sinon.

Question III. 13 Écrire en PASCAL une fonction inserer (a:ARBRE; 1:LISTE) : LISTE; telle que l'appel inserer (

) remoic la liste d'arbres obtenue en insérant l'arbre a dans la liste 1 en respectant l'ordre croissant du nombre d'occurrences. Nous supposons que la liste 1 respecte l'ordre croissant du nombre d'occurrences. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question III. 14 Écric on PASCAL me fonction trier (LISTE) : LISTE; telle que l'appel trier(1) remoie une liste d'arbres triée selon l'ordre croissant des nombres d'occurrences et composée des mêmes arbres aur 1 . Catte fonction devora etre récursive ou faire appel à des fonctions auxiliares récursives.

3 Construction des codes de Huffman

3.1 Construction de la liste d'occurrences

Question III.15 Écrire en PASCAL une fonction a jouter (v:CHARACTER;

LISTE) : LISTE; telle que l'appel ajouter (v, 1) renvoie une liste de feuilles étiquetées par les mêmes caractères que 1 et telle que si 1 contenait valors son occurrence est augmentée de 1 et si 1 ne contenait pas

, le résultat contient

avec l'occurrence 1. Nous supposons que v figure au plus une fois dans 1. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question III. 16 Écrire on PASCAL une fonction compter (s:SUITE) : LISTE; telle que l'appel compter(s) renvoie une liste de feuilles étiquetées par les mêmes caractères que s et par les nombres d'occurrences de ces caractères dans s. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

3.2 Construction de l'arbre

L'algorithme de Huffman de construction de l'arbre minimal présenté dans la sous-section 1.3.1 consiste à remplacer les deux sous-arbres ayant les plus petits nombres d'occurrences par le noeud ayant pour fils ces deux sous-arbres tout en préservant l'ordre de la liste triée.

Question III. 17 Écrirc en PASCAL une fonction fusionner ( 1 : LISTE) : ARBRE; telle que l'appel fusionner (1) sur une liste non vide de feuilles 1 triée selon les nombres d'occurrences des caractères renvoie un arbre de Huffman contenant les mêmes caractères que la liste 1 et correspondant au codage minimal de la suite. Cette fonction devra être récursive ou faire appel à des fonctions auailiaires récursives.

Question III. 18 Expliquer la fonction fusionner proposée pour la question précédente.
Question III. 19 Écrire en PASCAL ane fonction huffman (

: SUITE) : ARBRE; telle que l'appel huffman(s) remoie un arbre de Huffman comenant les mêmes caractères que la suite s et correspondant au codage minimal de la suite.

4 Codage d'une suite

L'étape précédente a permis de construire un arbre dont les chemins qui conduisent à chaque caractère sont étiquetés implicitement ( 0 pour le fils gauche, 1 pour le fils droit) par le code associé à ce caractère. Pour éviter de multiples parcours de l'arbre lors du codage d'une suite de caractères, il faut construire une clé de codage à partir de l'arbre qui associe à chaque caractère son code puis parcourir la suite pour remplacer chaque caractère par son code en utilisant la fonction coder proposée dans la question III. I.

4.1 Construction de la clé

Question III. 20 Écrire en PASCAL une fonction construire (a: ARBRE) : CLE; telle que l'appel construire (a) renvoie une clé de codage associant à chaque caractère comtenu dans l'arbre de Huffman a son code, c'est-à-dire la suite de valeurs binaires ( 0 ou 1) conrespondana au chemin suivi dans l'arbre pour atteindre le caractère. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

5 Décodage d'une suite

Le principal défaut du codage de Huffinan est la nécessité de transmettre la clé de codage avec chaque suite codée. En effet, il faut reconstruire l'arbre de Huffman propre à chaque suite codée pour décoder celle-ci par un parcours de l'arbre en suivant chaque code de la suite codée.

5.1 Reconstruction de la clé

Question III. 21 Écrire en PASCAL me fonction reconstruire(c:CLE) : ARBRE; telle que l'appel reconstruire(c) remoie un arbre de Huffman obtemu à partir de la clé de codage c. c'est-à-dire contenant les mêmes caractères que c placées dans l'arbre selon le code associé au caractère dans la clé c. L'occurrence du caractère c prendra la valeur 0 . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

5.2 Décodage de la suite

Question III. 22 Écrire en PASCAL une fonction decoder (s : SUITE ; a : ARBRE) : SUITE; telle que l'appel decoder (

, a) remoie une suite de caractères correspondant an décodage de la suite de valeurs binaires ( 0 ou 1 ) contenues dans 5 . Ce décodage est effectué par un parcours de l'arbre de Huffinan a en suivant les chemins correspondant aux valeurs binaires contenues dans s. ('ette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

6 Optimisation de la construction de l'arbre

Question III. 23 Quelle est la fonction la plus souvent appelée lors de la construction de l'arbre'?
Question III. 24 Proposer une ou plusieurs modifications des structures de domées et/ou des fonctions pour réduire le nombre d'appels à cette fonction.

La construction de l'arbre exploite une liste triée d'arbres. L'algorithme étudié dans la section 3.1 construit la liste dans un ordre quelconque puis effectue un tri de la liste obtenue. Il ext possible d'éviter ce tri par une construction de la liste qui assure que les feuilles soient triées selon l'ordre croissant des nombres d'occurrences.

Question III. 25 Ecrire en PASCAl, unefonction ajouter (v:CHARACTER; 1 : LISTE) : LISTE; telle que l'appel ajouter (

) sur une liste 1 de feuilles triée selon l'ordre croissandes nombres d'occurrences renvoie une liste de feuilles triée selon l'ordre croissant des nombres d'occurrences
étiquetées par les mêmés caractères que 1 et tellé que si 1 contenait valors son occurrence est augmemtée de 1 et si 1 ne comtenait pas v. le résaltat contient v avec l'occurrence 1. Cette fonction devra être récursive ou faire appel à des fonctions anailiaires récursives.