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 copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
Les calculatrices sont interdites
Preambule : les trois parties qui composent ce sujet sont indépendantes et peuvent être traitées par les candidats dans un ordre quelconque.
Pour les candidats ayant utilisé le langage CaML dans le cadre des enseignements d'informatique, la partie III (Algorithmique et programmation en CaML) se situe en page 7.
Pour les candidats ayant utilisé le langage PASCAL dans le cadre des enseignements d'informatique, la partie III (Algorithmique et programmation en PASCAL) se situe en page 14.
Partie I : logique et calcul des propositions
Dans une association de jeunes détectives, les membres s'entraînent à résoudre des problèmes logiques. Ceux-ci respectent les règles suivantes : «Lors d'une conversation, un même membre aura un comportement constant : il dira toujours la vérité, ou ne dira jamais la vérité. » et «Une conversation ne doit pas être absurde. »
Question I. 1 Soient membres intervenant dans une même conversation. Chaque membre est représenté par une variable propositionnelle avec qui représente le fait que ce membre dit, ou ne dit pas, la vérité. Chaque membre fait une seule déclaration représentée par la variable propositionnelle . Représenter le respect des règles dans cette conversation sous la forme d'une formule du calcul des propositions dépendant des variables et avec .
Vous assistez à deux conversations sur la véracité des déclarations de deux groupes de trois membres de cette association.
Nous nommerons et les participants de la première conversation. : «Les seuls qui disent la vérité ici sont et moi.» « ne dit pas la vérité.» «Soit dit la vérité. Soit ne dit pas la vérité.»
Nous noterons et les variables propositionnelles associées au fait que et disent respectivement la vérité.
Nous noterons et les formules du calcul des propositions associées respectivement aux déclarations de et dans la conversation.
Question I. 2 Représenter les déclarations de la première conversation sous la forme de formules du calcul des propositions et dépendant des variables et .
Question I. 3 En utilisant le calcul des propositions (résolution avec les tables de vérité), déterminer si et disent, ou ne disent pas, la vérité.
Nous nommerons et les participants de la seconde conversation. «Personne ne doit croire et disent toujours la vérité. » a dit la vérité.
Nous noterons et les variables propositionnelles associées au fait que et disent respectivement la vérité.
Nous noterons et les formules du calcul des propositions associées respectivement aux déclarations de et dans la seconde conversation.
Question I. 4 Représenter les déclarations de la seconde conversation sous la forme de formules du calcul des propositions et dépendant des variables et .
Question I. 5 En utilisant le calcul des propositions (résolution avec les formules de De Morgan), déterminer si et disent, ou ne disent pas, la vérité.
Partie II : automates et langages
Le but de cet exercice est de prouver qu'un homomorphisme de langage préserve la structure de langage régulier : l'image et l'image réciproque d'un langage régulier par un homomorphisme de langage sont des langages réguliers. Pour simplifier les preuves, nous nous limiterons à des homomorphismes -libres. Les résultats étudiés s'étendent au cas des homomorphismes quelconques.
1 Homomorphisme de langage
Déf. II. 1 (Alphabets, mots, langages) Un alphabet est un ensemble de symboles. Un mot de taille sur est une séquence de taille de symboles est le symbole représentant le mot vide ( ). est l'ensemble contenant et tous les mots sur . L'opérateur binaire est tel que: . Un mot de taille s'écrit de manière unique ). Un langage sur est un sous-ensemble de . L'opérateur binaire associatif sur de concaténation des mots . admet comme élément neutre.
Déf. II. 2 (Homomorphisme de langage) Soient deux alphabets et , un homomorphisme de langage est une application de domaine et co-domaine qui préserve le mot vide et l'opérateur de concaténation des mots, c'est-à-dire :
Déf. II. 3 (Homomorphisme -libre) Soit un alphabet , soit un homomorphisme de langage de domaine est -libre, si et seulement si :
Déf. II. 4 (Image d'un langage par un homomorphisme) Soit un alphabet , soit un homomorphisme de langage de domaine , soit un langage sur , l'image de par est définie par :
Déf. II. 5 (Image réciproque d'un langage par un homomorphisme) Soit un alphabet , soit un homomorphisme de langage de co-domaine , soit un langage sur , l'image réciproque de par est définie par :
Nous décomposons l'étude de la préservation de la structure de langage régulier par les homomorphismes de langage en plusieurs étapes qui reposent sur une restriction des homomorphismes de langage à un alphabet.
Déf. II. 6 (Extension de Kleene) Soient deux alphabets et , soit une application de domaine et co-domaine , nous notons l'extension au domaine définie par:
Question II. 1 Soient deux alphabets et , soit une application de domaine et co-domaine , montrer que est un homomorphisme de langage -libre.
Question II. 2 Soient deux alphabets et , soit un homomorphisme de langage de domaine et co-domaine , soit sa restriction au domaine , montrer que .
2 Langages et expressions régulières
Pour montrer que l'image d'un langage régulier par un homomorphisme de langage est un langage régulier, nous exploitons la définition des langages réguliers sous la forme d'expressions régulières.
Déf. II. 7 (Expression régulière) Soit un alphabet , une expression régulière sur est construite à partir des constantes et , de l'opérateur unaire de répétition et des opérateurs binaires associatifs de concaténation . et de choix + (qui est également commutatif). Les opérateurs ont les priorités croissantes suivantes : + , et .
Exemple II. 1 (Expression régulière) Soit l'alphabet , l'expression suivante est une expression régulière sur . Comme indiqué dans la définition des mots, pour simplifier l'écriture, nous n'utilisons pas explicitement l'opérateur . et . L'expression précédente sera donc notée .
Déf. II. 8 (Langage spécifié par une expression régulière) Soit l'alphabet , soit une expression régulière sur , le langage régulier spécifié par est défini par :
Déf. II. 9 (Homomorphisme d'expression régulière) Soient deux alphabets et , soit une application de domaine et co-domaine , soit une expression régulière sur , nous notons l'application, dont le domaine est l'ensemble des expressions régulières sur , définie par :
Question II. 3 Soient les alphabets et , soit l'application de domaine et co-domaine définie par et , calculer appliquée sur l'expression régulière de l'exemple II. 1 (ci-dessus).
Question II. 4 Soient deux alphabets et , soit h une application de domaine et co-domaine , soit e une expression régulière sur , montrer que est une expression régulière sur .
Question II. 5 Soient deux alphabets et , soit une application de domaine et co-domaine , soit e une expression régulière sur , montrer que .
Question II. 6 Soient deux alphabets et , soit h un homomorphisme de langage -libre de domaine et co-domaine , soit un langage régulier sur , montrer que est un langage régulier sur .
3 Langages réguliers et automates finis
Pour montrer que l'image réciproque d'un langage régulier par un homomorphisme de langage est un langage régulier, nous exploitons la définition des langages réguliers sous la forme d'automates finis. Pour simplifier les preuves, nous nous limiterons au cas des automates finis semi-indéterministes (automates indéterministes sans transition arbitraire sur ). Les résultats étudiés s'étendent au cadre des automates finis quelconques.
Déf. II. 10 (Automate fini semi-indéterministe) Soit l'alphabet , un automate fini semi-indéterministe sur est un quintuplet composé de :
un ensemble fini d'états : ;
un ensemble d'états initiaux : ;
un ensemble d'états terminaux : ;
une fonction de transition confondue avec son graphe : .
Pour une transition donnée, nous appelons o l'origine de la transition, l'étiquette de la transition et les différentes destinations de la transition.
Les automates peuvent être représentés par un schéma suivant les conventions :
les valeurs de la fonction de transition sont représentées par un graphe orienté dont les nœuds sont les états et les arêtes sont les transitions ;
tout état est entouré d'un cercle (q);
tout état initial est désigné par une flêche ;
tout état terminal est entouré d'un second cercle (t);
toute arête étiquetée par le symbole va de l'état à l'état si et seulement si .
Exemple II. 2 L'automate avec :
est représenté par le graphe suivant :
Déf. II. 11 (Fermeture réflexive et transitive) Soit ( ) un automate fini semi-indéterministe, la fermeture réflexive et transitive de sur est définie par :
Déf. II. 12 (Langage reconnu par un automate) Soit un automate fini semidéterministe, le langage régulier sur reconnu par est défini par :
Question II. 7 Donner, sans justification, l'expression régulière ou ensembliste représentant le langage sur reconnu par l'automate de l'exemple II. 2 (page 5).
Question II. 8 Soit ( ) un automate fini semi-déterministe, montrer que :
L'image réciproque du langage reconnu par un automate fini semi-indéterministe par un homomorphisme de langage peut être obtenue par transformation de cet automate selon la définition suivante.
Déf. II. 13 (Image réciproque d'un automate fini) Soient et deux alphabets, soit une application de dans , soit un automate fini semi-indéterministe, l'automate , image réciproque de l'automate , est défini par :
Question II. 9 Soient deux alphabets et soit une application de domaine et co-domaine telle que et , construire l'automate pour l'automate de l'exemple II.2.
Question II. 10 Caractériser le langage reconnu par par une expression régulière ou ensembliste. Comparer le langage reconnu par avec le langage reconnu par .
Question II. 11 Soit ( ) un automate fini semi-indéterministe, soit une application de domaine et co-domaine , montrer que :
Question II. 12 Soit un automate fini semi-indéterministe , soit une application de domaine et co-domaine , quelle relation liant les langages reconnus par et peut-on déduire des questions précédentes?
Question II. 13 Soient deux alphabets et , soit un homomorphisme de langage -libre de domaine et co-domaine , soit un langage régulier sur , montrer que est un langage régulier sur .
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. Elles ne devront pas utiliser d'instructions itératives (c'est-à-dire for, while,...) ni de références.
1 Exercice : le tri par sélection
L'objectif de cet exercice est d'étudier une implantation particulière d'un algorithme de tri d'une séquence d'entiers.
Déf. III. 1 Une séquence de taille de valeurs avec est notée . Sa taille est notée . Une même valeur peut figurer plusieurs fois dans . Nous noterons le cardinal de dans , c'est-à-dire le nombre de fois que figure dans , défini par :
Le type entiers représente une séquence d'entiers. Le type couple représente un couple dont le premier élément est un entier et le second est une séquence d'entiers. Les définitions de ces types sont :
type entiers == int list;;
type couple == int * entiers;;
Soit le programme en langage CaML :
let selection s =
let rec aux c a =
match a with
| [] -> (c,a)
| t::q ->
if (c < t) then
let (m,r) = aux c q in
(m, (t::r))
else
let (m,r) = aux t q in
(m, (c::r))
in
aux (hd s) (tl s);;
let rec tri s =
match s with
| [] -> []
| t::q ->
let (m,r) = selection s in
m :: (tri r);;
Soit la constante exemple définie et initialisée par:
let exemple = [ 3; 1; 4; 2];
Question III. 1 Détailler les étapes du calcul de (trier exemple) en précisant pour chaque appel aux fonctions selection, aux et trier, la valeur du paramètre et du résultat.
Déf. III. 2 (Symbole de Kronecker) Soient deux valeurs et , le symbole de Kronecker est une fonction égale à la valeur 1 si et sont égales et à la valeur 0 sinon.
Question III. 2 Soit l'entier m , soient les séquences d'entiers de taille et de taille , tels que (selection s ), montrer que:
(a)
(b)
(c)
Dans ce but, vous pouvez spécifier les propriétés que doit satisfaire la fonction aux. Montrer que celles-ci sont satisfaites et les exploiter ensuite.
Question III. 3 Soit la séquence de taille , soit la séquence de taille , telles que (trier s), montrer que:
(a)
(b)
(c)
Question III. 4 Montrer que le calcul des fonctions selection, aux et trier se termine quelles que soient les valeurs de leurs paramètres respectant le type des fonctions.
Question III. 5 Donner des exemples de valeurs du paramètre s de la fonction trier qui correspondent aux meilleur et pire cas en nombre d'appels récursifs effectués.
Montrer que la complexité de la fonction trier en fonction du nombre n de valeurs dans les séquences données en paramètre est de . Cette estimation ne prend en compte que le nombre d'appels récursifs effectués.
2 Problème : représentation d'images par des arbres quaternaires
La structure d'arbre quaternaire est une extension de la structure d'arbre binaire qui permet de représenter des informations en deux dimensions. En particulier, la structure d'arbre binaire est utilisée pour représenter de manière plus compacte des images. Il s'agit de décomposer une image par dichotomie sur les deux dimensions jusqu'à obtenir des blocs de la même couleur.
(1-a) Brute
(1-b) Par pixel
(1-c) Par bloc
Figure 1: images
Les images des figures 1 et 2 illustrent ce principe. L'image brute (1-a) contient des carrés de différentes couleurs. Cette image est découpée uniformément en pixels (picture elements) dans l'image (1-b). Les pixels sont des carrés de la plus petite taille nécessaire. Ce découpage fait apparaître de nombreux pixels de la même couleur. Pour réduire la taille du codage, l'image (1-c) illustre un découpage dichotomique de l'image en carrés qui regroupent certains pixels de la même couleur. L'arbre quaternaire de l'image (2-b) représente les carrés contenus dans (1-c). Les étiquettes sur les fils de chaque nœud réprésentent la position géographique des fils dans le nœud : Sud-Ouest, Sud-Est, NordOuest, Nord-Est comme indiqué dans (2-a).
(2-a) position géographique dans un nœud
(2-b) codage de l'image de la figure 1 par un arbre quaternaire
Figure 2: arbre quaternaire
L'objectif de ce problème est l'étude de cette structure d'arbre quaternaire et de son utilisation pour le codage d'images en niveau de gris. Pour simplifier les programmes, nous nous limitons à des images carrées dont la longueur du côté est une puissance de 2 . Les résultats étudiés se généralisent au cas des images rectangles de taille quelconque.
Figure 3: identification des pixels
2.1 Arbres quaternaires
Déf. III. 3 (Arbre quaternaire associé à une image) Un arbre quaternaire qui représente une image carrée est composé de nœuds, qui peuvent être des blocs ou des divisions. Les ensembles des nœuds, des divisions et des blocs, de l'arbre a sont notés et avec . Chaque nœud contient une abscisse, une ordonnée et une taille, notées et , qui correspondent aux coordonnées et à la longueur du côté de la partie carrée de l'image représentée par . Chaque bloc contient une couleur notée qui correspond à la couleur de la partie carrée de l'image représentée par . Chaque division contient quatre fils . Ces fils sont indexés par la position relative de la partie carrée de l'image qu'ils représentent dans l'image représentée par la division : Sud-Ouest, Sud-Est, Nord-Ouest et Nord-Est.
Figure 4: structure de données correspondant à l'image (3-a)
Exemple III. 1 La figure 3 contient l'image (3-a) représentée par le sous-arbre situé au Sud-Ouest de l'arbre (2-b) page 9 ainsi que l'indication (3-b) des coordonnées de chaque point de cette image. Elle contient également la technique de numérotation des points exploitée dans la section 2.3 (page 13). La figure 4 (ci-dessus) contient l'arbre qui représente cette image dont les blocs et les divisions ont été annotés avec les coordonnées, tailles et couleurs.
Déf. III. 4 (Profondeur d'un arbre quaternaire) La profondeur d'un bloc d'un arbre quaternaire est égale au nombre de divisions qui figurent dans la branche conduisant de la racine de au bloc . La profondeur d'un arbre est le maximum des profondeurs de ses blocs .
Exemple III. 2 La profondeur de l'arbre de la figure 2-b (page 9) est 3. La profondeur de l'arbre de la figure 4 (ci-dessus) est 2.
Déf. III. 5 (Arbre quaternaire valide) Un arbre quaternaire est valide, si et seulement si :
les tailles, abscisses et ordonnées de chaque nœud sont strictement positives;
les tailles des quatre fils de chaque division sont identiques et égales à la moitié de la taille de ;
les abscisses et ordonnées des fils de chaque division sont cohérentes avec la position géographique de chaque fils et avec l'abscisse, l'ordonnée et la taille de la division ;
au moins deux des quatre fils de chaque division contiennent des blocs de couleurs différentes.
Question III. 6 Exprimer le fait qu'un arbre quaternaire a est valide sous la forme d'une propriété .
2.2 Représentation en CaML
Un arbre quaternaire est représenté par le type quater. La position d'un sous-arbre dans un nœud est représentée par le type énuméré position contenant les valeurs et (représentant respectivement les sous-arbres situés au Sud-Ouest, Sud-Est, Nord-Ouest et Nord-Est d'une division). Les définitions en CaML de ces types sont :
type quater =
| Division of int * int * int * quater * quater * quater * quater
| Bloc of int * int * int * int;;
type position = SO | SE | NO | NE;;
Dans l'appel qui construit un arbre quaternaire dont la racine est un bloc, les paramètres et sont les coordonnées du point situé en bas à gauche de l'image représentée par ce bloc, est la longueur du côté de l'image carrée représentée par ce bloc et est la couleur des points de l'image représentée par ce bloc.
Dans l'appel Division ( , so, se, no, ne) qui construit un arbre quaternaire dont la racine est une division, les paramètres et sont les coordonnées du point situé en bas à gauche de l'image représentée par cette division, est la longueur du côté de l'image carrée représentée par cette division, so, se, no et ne sont quatre arbres quaternaires qui sont les quatre parties de la sub-division de l'image représentée par cette division. Celles-ci sont respectivement, so la partie en bas à gauche (Sud-Ouest), se la partie en bas à droite (Sud-Est), no la partie en haut à gauche (Nord-Ouest), ne la partie en haut à droite (Nord-Est).
Exemple III. 3 En associant les valeurs aux couleurs noir, gris foncé, gris clair et blanc, l'expression suivante :
let b11_2 = Bloc( 1, 1, 2, 0) in (* SO racine *)
let b31_1 = Bloc( 3, 1, 1, 0) in (* SO du SE racine *)
let b41_1 = Bloc( 4, 1, 1, 2) in (* SE du SE racine *)
let b32_1 = Bloc( 3, 2, 1, 1) in (* NO du SE racine *)
let b42_1 = Bloc( 4, 2, 1, 3) in (* NE du SE racine *)
let d31_2 = (* SE racine *)
Division( 3, 1, 2, b31_1, b41_1, b32_1, b42_1) in
let b13_2 = Bloc( 1, 3, 2, 1) in (* NO racine *)
let b33_2 = Bloc( 3, 3, 2, 2) in (* NE racine *)
Division( 1, 1, 4, b11_2, d31_2, b13_2, b33_2) (* racine *)
est alors associée à l'arbre quaternaire représenté graphiquement sur la figure 4 (page 10).
2.2.1 Scission d'un arbre quaternaire
Question III. 7 Ecrire en CaML une fonction scinder de type quater -> quater telle que l'appel (scinder a) sur un arbre quaternaire valide a renvoie, soit un arbre quaternaire identique à l'arbre a si la racine de celui-ci est une division, soit un arbre quaternaire dont la racine est une division contenant quatre blocs de même couleur identique à celle du bloc à la racine de l'arbre a. Les coordonnées et les tailles des blocs et de la division doivent être cohérentes. Toutes les contraintes de validité de l'arbre renvoyé doivent être satisfaites sauf celle concernant les couleurs.
2.2.2 Fusion d'arbres quaternaires
Question III. 8 Ecrire en CaML une fonction fusionner de type quater -> quater -> quater -> quater -> quater telle que l'appel (fusionner so se no ne) sur quatre arbres quaternaires valides so, se, no et ne renvoie un arbre quaternaire valide codant l'image dont les parties Sud-Ouest, Sud-Est, Nord-Ouest et NordEst sont codées par so, se, no et ne. Les abscisses, ordonnées et tailles de so, se, no et ne sont cohérentes avec leur position dans l'image représentée par le résultat renvoyé.
2.2.3 Calcul de la profondeur d'un arbre quaternaire
Question III. 9 Ecrire en CaML une fonction profondeur de type quater -> int telle que l'appel (profondeur a) sur un arbre quaternaire valide a renvoie la profondeur de l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.4 Consulter la couleur d'un point dans un arbre quaternaire
Question III. 10 Ecrire en CaML une fonction consulter de type int -> int -> quater -> int telle que l'appel (consulter x y a) sur un point d'abscisse x et d'ordonnée y et sur un arbre quaternaire valide a tel que le point d'abscisse x et d'ordonnée y soit contenu dans l'image représentée par l'arbre a, renvoie la couleur du point d'abscisse x et d'ordonnée y dans l'image représentée par l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.5 Peindre un point dans un arbre quaternaire
Question III. 11 Ecrire en CaML une fonction peindre de type int -> int -> int -> quater -> quater telle que l'appel (peindre x y c a) sur un point d'abscisse x et d'ordonnée y , une couleur c et un arbre quaternaire valide a renvoie un arbre quaternaire valide. Le point de coordonnées x et y doit être contenu dans l'image représentée par l'arbre a. L'arbre renvoyé représente une image contenant les mêmes couleurs que l'image représentée par l'arbre a sauf pour le point de coordonnées x et y dont la couleur sera c. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.6 Validation d'un arbre quaternaire
Question III. 12 Ecrire en CaML une fonction valider de type quater -> bool telle que l'appel (valider a) sur un arbre quaternaire a renvoie la valeur true si l'arbre a est valide, c'est-à-dire si VAQ(a) et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3 Sauvegarde et restauration
Pour sauvegarder dans un fichier les couleurs contenues dans un arbre quaternaire valide, celles-ci sont rangées dans une séquence triée selon la position des points dans l'arbre. L'ordre choisi permet de restaurer l'arbre efficacement. La figure (3-c) (page 10) indique l'ordre dans lequel les points doivent être sauvegardés. La séquence manipulée contiendra les couleurs et les numéros associés à la position de chaque couleur dans l'arbre.
2.3.1 Codage en CaML
Une séquence de positions et de couleurs est représentée par le type sequence dont la définition est :
type sequence == (int * int) list;;
La position figure avant la couleur associée dans la séquence.
Exemple III. 4 En associant les valeurs aux couleurs noir, gris foncé, gris clair et blanc, la sauvegarde de l'image de la figure (3-c) (page 10) produit la séquence :
Question III. 13 Ecrire en CaML une fonction sauvegarder de type quater -> sequence telle que l'appel (sauvegarder a) sur un arbre quaternaire valide a renvoie une séquence triée contenant les mêmes couleurs à la même position que l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a et ne devra pas reparcourir la (ou les) séquence(s) créée(s) en dehors de leur création. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.3 Restauration d'un arbre quaternaire
Question III. 14 Ecrire en CaML une fonction restaurer de type sequence -> quater telle que l'appel (restaurer s) sur une séquence valide s renvoie un arbre quaternaire valide contenant exactement les points contenus dans la séquence s . L'algorithme utilisé ne devra parcourir qu'une seule fois la séquence s et ne devra pas reparcourir les arbres quaternaires créés en dehors de leur création. 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 être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (c'est-à-dire for, while, repeat,...).
1 Exercice : le tri par sélection
L'objectif de cet exercice est d'étudier une implantation particulière d'un algorithme de tri d'une séquence d'entiers.
Déf. III. 1 Une séquence de taille de valeurs avec est notée . Sa taille est notée . Une même valeur peut figurer plusieurs fois dans . Nous noterons le cardinal de dans , c'est-à-dire le nombre de fois que figure dans , défini par :
Le type ENTIERS représente une séquence d'entiers. 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 :
Vide est une constante de valeur NIL qui représente une séquence vide d'entiers;
FUNCTION E_Inserer(e:INTEGER; s:ENTIERS) : ENTIERS; renvoie une séquence d'entiers composée d'un premier entier e et du reste de la séquence contenu dans ;
FUNCTION E_Tete (s:ENTIERS) : INTEGER; renvoie le premier entier de la séquence . Cette séquence ne doit pas être vide;
FUNCTION E_Queue ( : ENTIERS) : ENTIERS; renvoie le reste de la séquence privée de son premier entier. Cette séquence ne doit pas être vide;
FUNCTION E_Juxtaposer(s1,s2:ENTIERS):ENTIERS; renvoie une séquence composée des éléments de la séquence dans le même ordre que dans puis des éléments de la séquence dans le même ordre que dans .
Le type COUPLE représente un couple dont le premier élément est un entier et le second est une séquence d'entiers. 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 :
FUNCTION C_Creer (v:INTEGER;s:ENTIERS) : COUPLE; renvoie un couple contenant la valeur entière et la séquence d'entiers ;
FUNCTION C_Valeur (C:COUPLE) : INTEGER; renvoie la valeur entière située en première partie du couple ;
FUNCTION C_Sequence (c:COUPLE) : ENTIERS; renvoie la séquence d'entiers située en seconde partie du couple .
Soit le programme en langage PASCAL :
FUNCTION selection(s:ENTIERS):COUPLE;
FUNCTION aux(c:INTEGER; a:ENTIERS):COUPLE;
VAR t : INTEGER; q : ENTIERS;
BEGIN
IF (a = NIL) THEN
aux := C_Creer( c, a)
ELSE BEGIN
t := E_Tete( a);
q := E_Queue( a);
IF (c < t) THEN BEGIN
i := aux( c, q);
m := C_Valeur( i);
r := C_Sequence( i);
aux := C_Creer( m, E_Ajouter( t, r))
END ELSE BEGIN
i := aux( t, q);
m := C_Valeur( i);
r := C_Sequence( i);
aux := C_Creer( m, E_Ajouter( c, r))
END
END
END; (* aux *)
BEGIN
selection := aux( E_Tete( s), E_Queue( s))
END; (* selection *)
FUNCTION tri(s:ENTIERS):ENTIERS;
VAR i : Couple; m : INTEGER; r : ENTIERS;
BEGIN
IF (s = NIL) THEN
tri := s
ELSE BEGIN
i := selection( s);
m := C_Valeur( i);
r := C_Sequence( i);
tri := Ajouter( m, tri( r))
END
END; (* trier *)
Soit la constante exemple définie et initialisée par :
CONST exemple : ENTIERS
Question III. 1 Détailler les étapes du calcul de trier (exemple) en précisant pour chaque appel aux fonctions selection, aux et trier, la valeur du paramètre et du résultat.
Déf. III. 2 (Symbole de Kronecker) Soient deux valeurs et , le symbole de Kronecker est une fonction égale à la valeur 1 si et sont égales et à la valeur 0 sinon.
Question III. 2 Soit l'entier m , soient les séquences d'entiers de taille et de taille , soit le couple i , tels que i = selection(s), C_Valeur(i) et C_Sequence(i) montrer que:
(a)
(b)
(c)
Dans ce but, vous pouvez spécifier les propriétés que doit satisfaire la fonction aux. Montrer que celles-ci sont satisfaites et les exploiter ensuite.
Question III. 3 Soit la séquence de taille , soit la séquence de taille , telles que trier , montrer que:
(a)
(b)
(c)
Question III. 4 Montrer que le calcul des fonctions selection, aux et trier se termine quelles que soient les valeurs de leurs paramètres respectant le type des fonctions.
Question III. 5 Donner des exemples de valeurs du paramètre s de la fonction trier qui correspondent aux meilleur et pire cas en nombre d'appels récursifs effectués.
Montrer que la complexité de la fonction trier en fonction du nombre n de valeurs dans les séquences données en paramètre est de . Cette estimation ne prend en compte que le nombre d'appels récursifs effectués.
2 Problème : représentation d'images par des arbres quaternaires
La structure d'arbre quaternaire est une extension de la structure d'arbre binaire qui permet de représenter des informations en deux dimensions. En particulier, la structure d'arbre binaire est utilisée pour représenter de manière plus compacte des images. Il s'agit de décomposer une image par dichotomie sur les deux dimensions jusqu'à obtenir des blocs de la même couleur.
(1-a) Brute
(1-b) Par pixel
(1-c) Par bloc
Figure 1: images
Les images des figures 1 et 2 illustrent ce principe. L'image brute (1-a) contient des carrés de différentes couleurs. Cette image est découpée uniformément en pixels (picture elements) dans l'image (1-b). Les pixels sont des carrés de la plus petite taille nécessaire. Ce découpage fait apparaître de nombreux pixels de la même couleur. Pour réduire la taille du codage, l'image (1-c) illustre un découpage dichotomique de l'image en carrés qui regroupent certains pixels de la même couleur. L'arbre quaternaire de l'image (2-b) représente les carrés contenus dans (1-c). Les étiquettes sur les fils de chaque nœud réprésentent la position géographique des fils dans le nœud : Sud-Ouest, Sud-Est, NordOuest, Nord-Est comme indiqué dans (2-a).
(2-a) position géographique dans un nœud
(2-b) codage de l'image de la figure 1 par un arbre quaternaire
Figure 2: arbre quaternaire
L'objectif de ce problème est l'étude de cette structure d'arbre quaternaire et de son utilisation pour le codage d'images en niveau de gris. Pour simplifier les programmes, nous nous limitons à des images carrées dont la longueur du côté est une puissance de 2 . Les résultats étudiés se généralisent au cas des images rectangles de taille quelconque.
Figure 3: identification des pixels
2.1 Arbres quaternaires
Déf. III. 3 (Arbre quaternaire associé à une image) Un arbre quaternaire qui représente une image carrée est composé de nœuds, qui peuvent être des blocs ou des divisions. Les ensembles des nœuds, des divisions et des blocs, de l'arbre a sont notés et avec . Chaque nœud contient une abscisse, une ordonnée et une taille, notées et , qui correspondent aux coordonnées et à la longueur du côté de la partie carrée de l'image représentée par . Chaque bloc contient une couleur notée qui correspond à la couleur de la partie carrée de l'image représentée par . Chaque division contient quatre fils . Ces fils sont indexés par la position relative de la partie carrée de l'image qu'ils représentent dans l'image représentée par la division : Sud-Ouest, Sud-Est, Nord-Ouest et Nord-Est.
Figure 4: structure de données correspondant à l'image (3-a)
Exemple III. 1 La figure 3 contient l'image (3-a) représentée par le sous-arbre situé au Sud-Ouest de l'arbre (2-b) page 17 ainsi que l'indication (3-b) des coordonnées de chaque point de cette image. Elle contient également la technique de numérotation des points exploitée dans la section 2.3 (page 21). La figure 4 (ci-dessus) contient l'arbre qui représente cette image dont les blocs et les divisions ont été annotés avec les coordonnées, tailles et couleurs.
Déf. III. 4 (Profondeur d'un arbre quaternaire) La profondeur d'un bloc d'un arbre quaternaire est égale au nombre de divisions qui figurent dans la branche conduisant de la racine de au bloc . La profondeur d'un arbre est le maximum des profondeurs de ses blocs .
Exemple III. 2 La profondeur de l'arbre de la figure 2-b (page 17) est 3. La profondeur de l'arbre de la figure 4 (ci-dessus) est 2.
Déf. III. 5 (Arbre quaternaire valide) Un arbre quaternaire est valide, si et seulement si :
les tailles, abscisses et ordonnées de chaque nœud sont strictement positives;
les tailles des quatre fils de chaque division sont identiques et égales à la moitié de la taille de ;
les abscisses et ordonnées des fils de chaque division sont cohérentes avec la position géographique de chaque fils et avec l'abscisse, l'ordonnée et la taille de la division ;
au moins deux des quatre fils de chaque division contiennent des blocs de couleurs différentes.
Question III. 6 Exprimer le fait qu'un arbre quaternaire a est valide sous la forme d'une propriété .
2.2 Représentation en PASCAL
Un arbre quaternaire est représenté par le type de base QUATER. La position d'un sous-arbre dans un nœud est représentée par le type énuméré POSITION contenant les valeurs SO, SE, NO et NE (représentant respectivement les sous-arbres situés au Sud-Ouest, Sud-Est, Nord-Ouest et Nord-Est d'une division).
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 :
FUNCTION Bloc (x,y,t, C: INTEGER) : QUATER; est une fonction qui renvoie un arbre quaternaire dont la racine est un bloc, et sont les coordonnées du point le plus en bas, à gauche de l'image représentée par ce bloc; est la longueur du côté de l'image carrée représentée par ce bloc et est la couleur des points de l'image représentée par ce bloc;
FUNCTION Division(x,y,t:INTEGER;so,se,no,ne:QUATER):QUATER; est une fonction qui renvoie un arbre quaternaire dont la racine est une division, et sont les coordonnées du point le plus en bas, à gauche de l'image représentée par cette division; est la longueur du côté de l'image carrée représentée par cette division, so, se, no et ne sont quatre arbres quaternaires qui sont les quatre parties de la sub-division de l'image représentée par cette division. Celles-ci sont respectivement, so la partie en bas à gauche (Sud-Ouest), se la partie en bas à droite (Sud-Est), no la partie en haut à gauche (Nord-Ouest), ne la partie en haut à droite (Nord-Est);
FUNCTION EstBloc(a:QUATER):BOOLEAN; est une fonction qui renvoie la valeur TRUE si la racine de l'arbre a est un bloc et la valeur FALSE sinon;
FUNCTION Abscisse(a:QUATER) : QUATER; est une fonction qui, appliquée sur un arbre quaternaire , renvoie l'abscisse du point situé le plus en bas à gauche de l'image représentée par a;
FUNCTION Ordonnée(a:QUATER):QUATER; est une fonction qui, appliquée sur un arbre quaternaire , renvoie l'ordonnée du point situé le plus en bas à gauche de l'image représentée par ;
FUNCTION Taille(a:QUATER): QUATER; est une fonction qui, appliquée sur un arbre quaternaire , renvoie la longueur du côté de l'image représentée par ;
FUNCTION COuleur (a:QUATER) : QUATER; est une fonction qui, appliquée sur un arbre quaternaire a dont la racine est un bloc, renvoie la couleur de l'image représentée par ;
FUNCTION Fils (p:POSITION; a:QUATER) : QUATER; est une fonction qui, appliquée sur un arbre quaternaire dont la racine est une division, renvoie le fils de a situé à la position dans cette division.
Exemple III. 3 En associant les valeurs 0, 1, 2, 3 aux couleurs noir, gris foncé, gris clair et blanc, le programme suivant :
VAR
exemple : QUATER;
B11_2, B31_1 B41_1 B32_1 B42_1 D31_2 B13_2 B33_2 : QUATER;
CONST
B11_2 := Bloc( 1, 1, 2, 0); (* SO racine *)
B31_1 := Bloc( 3, 1, 1, 0); (* SO du SE racine *)
B41_1 := Bloc( 4, 1, 1, 2); (* SE du SE racine *)
B32_1 := Bloc( 3, 2, 1, 1); (* NO du SE racine *)
B42_1 := Bloc( 4, 2, 1, 3); (* NE du SE racine *)
D31_2 := (* SE racine *)
Division( 3, 1, 2, B31_1, B41_1, B32_1, B42_1);
B13_2 := Bloc( 1, 3, 2, 1); (* NO racine *)
B33_2 := Bloc( 3, 3, 2, 2); (* NE racine *)
BEGIN
exemple := (* racine *)
Division( 1, 1, 4, B11_2, B31_2, B13_2, B33_2)
END
affecte à la variable exemple l'arbre quaternaire représenté graphiquement dans la figure 4 (page 18).
2.2.1 Scission d'un arbre quaternaire
Question III. 7 Ecrire en PASCAL une fonction scinder (a: QUATER) : QUATER; telle que l'appel scinder (a) sur un arbre quaternaire valide a renvoie, soit un arbre quaternaire identique à l'arbre a si la racine de celui-ci est une division, soit un arbre quaternaire dont la racine est une division contenant quatre blocs de même couleur identique à celle du bloc à la racine de l'arbre a. Les coordonnées et les tailles des blocs et de la division doivent être cohérentes. Toutes les contraintes de validité de l'arbre renvoyé doivent être satisfaites sauf celle concernant les couleurs.
2.2.2 Fusion d'arbres quaternaires
Question III. 8 Ecrire en PASCAL telle une que
fusionner (so, se, no, ne: QUATER) : QUATER; l'appel
fusionner (so, se, no, ne) sur quatre arbres quaternaires valides so, se, no et ne renvoie
un arbre quaternaire valide codant l'image dont les parties Sud-Ouest, Sud-Est, Nord-Ouest et Nord-
Est sont codées par so, se, no et ne. Les abscisses, ordonnées et tailles de so, se, no et ne sont
cohérentes avec leur position dans l'image représentée par le résultat renvoyé.
2.2.3 Calcul de la profondeur d'un arbre quaternaire
Question III. 9 Ecrire en PASCAL une fonction profondeur (a:QUATER) : INTEGER; telle que l'appel profondeur (a) sur un arbre quaternaire valide a renvoie la profondeur de l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.4 Consulter la couleur d'un point dans un arbre quaternaire
Question III. 10 Ecrire en PASCAL une fonction
consulter ( : INTEGER; a : QUATER) : INTEGER; telle que l'appel consulter ( ) sur un point d'abscisse x et d'ordonnée y et sur un arbre quaternaire valide a tel que le point d'abscisse x et d'ordonnée y soit contenu dans l'image représentée par l'arbre a, renvoie la couleur du point d'abscisse x et d'ordonnée y dans l'image représentée par l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.5 Peindre un point dans un arbre quaternaire
Question III. 11 Ecrire en PASCAL une fonction peindre( : INTEGER; a : QUATER) : QUATER; telle que l'appel peindre ( ) sur un point d'abscisse x et d'ordonnée y , une couleur c et un arbre quaternaire valide a renvoie un arbre quaternaire valide. Le point de coordonnées x et y doit être contenu dans l'image représentée par l'arbre a. L'arbre renvoyé représente une image contenant les mêmes couleurs que l'image représentée par l'arbre a sauf pour le point de coordonnées x et y dont la couleur sera c. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.6 Validation d'un arbre quaternaire
Question III. 12 Ecrire en PASCAL une fonction valider (a:QUATER) : BOOLEAN; telle que l'appel valider (a) sur un arbre quaternaire a renvoie la valeur TRUE si l'arbre a est valide, c'est-à-dire si VAQ(a) et la valeur FALSE sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3 Sauvegarde et restauration
Pour sauvegarder dans un fichier les couleurs contenues dans un arbre quaternaire valide, celles-ci sont rangées dans une séquence triée selon la position des points dans l'arbre. L'ordre choisi permet de restaurer l'arbre efficacement. La figure (3-c) (page 18) indique l'ordre dans lequel les points doivent être sauvegardés. La séquence manipulée contiendra les couleurs et les numéros associés à la position de chaque couleur dans l'arbre.
2.3.1 Codage en PASCAL
Une séquence de positions et de couleurs est représentée par le type SEQUENCE et le type POINT qui contient la position et la couleur associée. 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 :
Vide est une constante de valeur qui représente une séquence vide;
FUNCTION P_Creer (p, c:INTEGER) : POINT; renvoie un point contenant la position et la couleur ;
FUNCTION P_Position(p:POINT):INTEGER; renvoie la position contenue dans le point ;
FUNCTION P_Couleur(p:POINT):INTEGER; renvoie la couleur contenue dans le point ;
FUNCTION S_Inserer(p:POINT;s:SEQUENCE):SEQUENCE; renvoie une séquence de points composée d'un premier point et du reste de la séquence contenu dans ;
FUNCTION S_Tete ( ) : POINT; renvoie le premier point de la séquence . Cette séquence ne doit pas être vide;
FUNCTION S_Queue ( : SEQUENCE) : SEQUENCE; renvoie le reste de la séquence privée du premier point. Cette séquence ne doit pas être vide;
FUNCTION S_Juxtaposer(s1,s2:SEQUENCE):SEQUENCE; renvoie une séquence composée des éléments de la séquence dans le même ordre que dans puis des éléments de la séquence dans le même ordre que dans .
Exemple III. 4 En associant les valeurs aux couleurs noir, gris foncé, gris clair et blanc, la sauvegarde de l'image de la figure (3-c) (page 18) produit la séquence calculée par :
Question III. 13 Ecrire en PASCAL une fonction sauvegarder (a:QUATER) : SEQUENCE; telle que l'appel sauvegarder (a) sur un arbre quaternaire valide a renvoie une séquence triée contenant les mêmes couleurs à la même position que l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a et ne devra pas reparcourir la (ou les) séquence(s) créée(s) en dehors de leur création. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.3 Restauration d'un arbre quaternaire
Question III. 14 Ecrire en PASCAL une fonction restaurer (s: SEQUENCE) : QUATER; telle que l'appel restaurer(s) sur une séquence valide s renvoie un arbre quaternaire valide contenant exactement les points contenus dans la séquence s . L'algorithme utilisé ne devra parcourir qu'une seule fois la séquence s et ne devra pas reparcourir les arbres quaternaires créés en dehors de leur création. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Fin de l'énoncé
CCINP Option Informatique MP 2014 - Version Web LaTeX | WikiPrépa | WikiPrépa
