(Epreuve commune aux ENS de Paris, Lyon et Cachan)
Filières MP et PC (groupe I)
(Epreuve commune aux ENS de Paris et Lyon)
INFORMATIQUE
Durée : 4 heures
L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.
Ordres pour la terminaison des programmes et suites de Goodstein
Les différentes parties du problème sont largement indépendantes les unes des autres. Plus précisément, la partie 1 introduit les concepts; à l'exception des questions 8 et 9 , la partie 3 est indépendante de la partie 2 . Les premières questions ( 1 à 5 ) de la partie 4 ne font référence ni à la partie 2 , ni à la partie 3 . La partie 5 peut être résolue indépendamment des autres.
1 Introduction
En informatique, la terminaison des programmes (c'est-à-dire le fait qu'un programme se termine pour tout valeur d'entrée qu'il peut prendre) est une propriété fondamentale que l'on cherche à démontrer. Dans ce problème, nous allons étudier des relations que l'on appelle «bien fondées» et qui permettent de garantir la terminaison des programmes. En fait, les relations bien fondées que nous examinerons sont puissantes et nous permettront d'aborder un problème de logique intéressant : les suites de Goodstein. Pour cela nous avons besoin de représenter les naturels par des arbres, ce qui nous conduira à de l'arithmétique sur ces représentations.
Ordres Une relation R sur E est irréflexive si elle vérifie (∀x ∈ E)¬(xRx). Un ordre strict est une relation irréflexive et transitive. Si⊐ est un ordre strict, ⊒ est la relation ⊐ ∪ =, c'est-à-dire la relation telle que x⊒y si et seulement si x⊐y ou x = y. Un ordre strict est total si pour tout (x, y) ∈ E × E on a x⊐y ∨ y⊒x.
Une suite (x_i)_(i ∈ ℕ) d'éléments de E telle que x_0⊐x_1…x_n⊐x_(n + 1)… est dite ⊐-décroissante. Une relation ⊐ est bien fondée sur E (on dit aussi que ( E, ⊐ ) est bien fondé) s'il n'existe pas de suite infinie ℶ-décroissante d'éléments de E.
S'il existe, le minimum d'un ensemble A pour un ordre strict ⊐ est l'élément min_⊐A tel que
min_⊐A ∈ A & (∀a ∈ A)a⊒min_⊐A.
Si elle existe, la borne supérieure d'un ensemble A pour un ordre ⊐ est
sup_⊐A = min_⊐{x ∈ E|(∀a ∈ A)x⊒a}.
Le successeur s_⊐(e) d'un élément e ∈ E est min_⊐{x ∈ E|x⊐e} si ce minimum existe.
Listes Une liste de E est une structure de données informatique qui implante une suite finie d'éléments de E. Si ses éléments sont dans l'ordre e_1, …, e_n, elle s'écrit [e_1; …; e_n]. On construit les listes à partir de la liste vide [ ] par ajout d'éléments en tête de liste. Le premier élément d'une liste non vide l s'écrit hd( l ), la liste obtenue à partir de l par suppression de son premier élément s'écrit t(l). L'ajout en tête de l de l'élément a s'écrit a : l. On a les relations suivantes :
hd(a : l), = a; tl(a : l), = l
tandis que hd([]) et tl([]) ne sont pas définis.
Arbres binaires Un arbre binaire est soit O, soit A_1 ⋅ A_2 où A_1 et A_2 sont eux-mêmes des arbres binaires. Dans la suite du problème, nous dirons simplement «arbre». Un arbre peut aussi être dessiné
Ainsi l'arbre O ⋅ (O ⋅ O) se dessine :
Les arbres forment l'ensemble 𝔸. La taille d'un arbre est le nombre d'occurrences de l'opérateur < ⋅ ≫ qu'il contient. Nous admettrons le principe d'induction structurelle sur 𝔸 : P(O)&(∀(A_1, A_2) ∈ 𝔸 × 𝔸)[P(A_1)&P(A_2) ⇒ P(A_1 ⋅ A_2)] ⇒ (∀A ∈ 𝔸)P(A)
qui permet de prouver par récurrence une propriété P pour tous les arbres.
La relation sur-arbre strict ▹ est définie par − A_1 ⋅ A_2▹O,
A_1 ⋅ A_2▹B si et seulement si A_1 = B ou A_2 = B ou A_1▹B ou A_2▹B.
On admettra que ▹ est un ordre strict.
Nous généralisons le principe d'induction structurelle aux triplets d'arbres en définissant sur 𝔸^3 l'ordre ▹▹▹ qui dit que (A, A^′, A^(′′))▹▹▹(B, B^′, B^(′′)) si et seulement si A⊵B, A^′⊵B^′ et A^(′′)⊵B^(′′) et l'une au moins des inégalités est stricte. Ce principe s'énonce :
Remarque: Si dans une preuve par induction structurelle, le prédicat P contient plusieurs occurrences d'arbres, le candidat veillera à indiquer clairement sur quelle variable il fait son induction.
Présentation des algorithmes Quand un algorithme est demandé, le candidat n'est pas supposé produire un programme complet, mais un texte suffisamment et clairement documenté pour qu'un programme puisse être extrait sans difficulté. Le candidat pourra aussi bien utiliser un style proche de celui de la figure 1 qu'un style proche du langage de programmation CAML. Les correcteurs attacheront de l'importance au fait que les candidats aient abordé les questions algorithmiques.
Montrer qu'un ordre strict est antisymétrique.
On considère la fonction R(A, l) qui prend un arbre A et une liste l d'arbres [A_1; …; A_n] et qui retourne
A si la liste l est vide
et R((A_1 ⋅ A), [A_2; …; A_n]) si la liste n'est pas vide.
Formellement,
R(A, []), = A; R(A, B : l), = R(B ⋅ A, l)
Dans la suite, nous utiliserons la fonction renv(l) définie par R(O, l).
Donner un algorithme qui calcule la fonction R.
2 Décomposition complète d'un nombre dans une base et suites de Goodstein
Étant donné un naturel b appelé base, l'exposant maximal d'un naturel n est le nombre p tel que b^p ≤ n < b^(p + 1) tandis que la décomposition complète de n dans la base b est
soit 0 si n = 0,
soit la somme de b^d et de d^′, où d est la décomposition complète de l'exposant maximal p de n dans la base b, et où d^′ est la décomposition complète de n − b^p.
Ainsi la décomposition complète de 83 dans la base 3 est obtenue à partir de
3^d + 3^0 + 3^0
où d est la décomposition complète de 4 .
Donner la décomposition complète de 4 et celle de 83 .
Étant donné une base b, montrer que la décomposition complète d'un naturel permet d'exprimer ce naturel à l'aide de l'addition, de l'exponentiation et de 0 et des ces opérations seulement.
On associe un arbre à la décomposition complète d'un naturel de la façon suivante :
φ_b(0), = O; φ_b(b^d + d^′), = φ_b(d) ⋅ φ_b(d^′)
Pour le naturel 83 et la base 3 , on obtient
Quel est l'arbre associé respectivement à 1 , à b, à b + 1 et à b^b dans toutes les bases? Soit decl la fonction qui prend un couple de naturels b (une base) et n (un naturel) et retourne un couple de naturels ( p, q ) tel que
n = b^p + q.
Donner la définition formelle (à la manière de la fonction R de la question 1.1) de la fonction arbre qui associe directement à ( b, n ) l'arbre donné par φ_b.
4. Dans l'algorithme de la figure 1 qui calcule la fonction arbre quelle est la nature (ou le
arbre(b, n) =
pile := [(0,[])]
courant := (n,[])
tant que pile ≠ [] faire
k, liste_res := courant
si k\not=0 alors (m,r) := dec1(b,k)
pile := (r, liste_res) :: pile;
courant := (m,[]))
sinon (q,l):= hd(pile)
pile := tl(pile)
courant := (q, renv(liste_res) :: l))
fait
k, liste_res := courant
retourne(hd(liste_res))
Fig. 1 -
type) des objets contenus dans pile, courant et liste_res? Que contient liste_res dans les étapes de l'algorithme et quand l'algorithme se termine?
5. On considère la fonction erbra qui prend un couple formé d'une base b et d'un arbre A et donne le naturel qui correspond à l'arbre A dans la base b; autrement dit on a erbra(b, arbre(b, n)) = n. Donner un algorithme récursif qui calcule la fonction erbra. Quelle est la complexité de cet algorithme en fonction de la taille de l'arbre, si l'on suppose que la somme et l'exponentiation se font en temps constant?
6. Les suites de Goodstein commencent au rang 2 . Si g_k ≠ 0, g_(k + 1) est défini à partir de g_k ainsi :
g_(k + 1) = erbra(k + 1, arbre(k, g_k)) − 1
Si g_3 = 83, quels sont g_2 et g_4 ? Montrer que pour la suite où g_3 = 83 il existe un k tel g_k > 1000^(1000).
7. Donner un algorithme directement dérivé des algorithmes précédents qui prend deux arbresarbre(b, m) et arbre(b, n) et construit l'arbre arbre (b, m + n). Cet algorithme pourra utiliser directement l'addition sur les naturels. Nous appellerons l'opération que cet algorithme implante l'addition des arbres en base b. Donner ensuite un algorithme qui permet d'additionner des arbres en base b en n'utilisant que des additions sur des nombres inférieurs à b.
8. Donner un algorithme qui prend deux arbres arbre (b, m) et arbre (b, n) et construit l'arbre arbre (b, m ⋅ n) où m ⋅ n est le produit des naturels m et n et qui n'utilise que des opérations sur des nombres inférieurs à b.
3 Un ordre sur les arbres
La relation ≻ est définie par − A_1 ⋅ A_2≻O,
A_1 ⋅ A_2≻A_1^′ ⋅ A_2^′ si et seulement si
ou bien A_1≻A_1^′
ou bien A_1 = A_1^′ et A_2≻A_2^′
Montrer que ≻ est un ordre strict.
Montrer par un contrexemple que ( 𝔸, ≻ ) n'est pas bien fondé.
Si (A, > _A) et (B, > _B) sont des ordres stricts bien fondés, on définit (A × B, > _A × > _B) par
(a, b) > _A × > _B(a^′, b^′) si a > _A a^′ ou a = a^′ et b > _B b^′
Montrer que (A × B, > _A × > _B) est un ordre strict bien fondé.
4. Soit A un alphabet muni d'une relation d'ordre > _A. Un mot a_1…a_n sur A^∗ est décroissant si pour 1 ≤ i < n on a a_i ≥ _A a_(i + 1). Les mots décroissants forment l'ensemble A ^(dec).
L'ordre du dictionnaire sur les mots est défini par − aα > _(A^∗)ε (où ε est le mot vide). − aα > _(A^∗)bβ si et seulement si a > _A b ou bien a = b et α > _(A^∗)β.
Montrer que ( A^(dec), > _(A^∗) ) est bien fondé si et seulement si (A, > _A) est bien fondé.
5. Un arbre A_1 ⋅ (A_2 ⋅ A_3) est ordonné si A_1 et A_2 ⋅ A_3 sont ordonnés et si A_1⪰A_2. De plus, O est ordonné et A_1 ⋅ O est ordonné si A_1 est ordonné. Les arbres ordonnés forment l'ensemble 𝕆. Montrer que pour tout arbre A de 𝕆 le successeur s_≻(A) existe.
6. A étant un arbre, montrer par induction structurelle que la relation ≻ est bien fondée sur l'ensemble 𝕆_A = {B ∈ 𝕆|A⪰B}. Indication : on montrera que l'ensemble ordonné (𝕆_A, ≻) est isomorphe à un ensemble, ordonné par un ordre du dictionnaire, de mots ordonnés.
7. Conclure de la question 6 que ≻ est bien fondée sur 𝕆.
8. Montrer pour tous les naturels b, n et m, que d'une part arbre (b, n) ∈ 𝕆 et que d'autre part, m > n implique arbre(b, m)≻arbre(b, n).
9. Montrer que toute suite de Goodstein atteint 0 , autrement dit pour toute suite de Goodstein g_2, …, g_k, …, il existe un naturel n, tel que g_n = 0.
4 Un autre ordre sur les arbres
On définit sur 𝔸 une relation par
A▹B si et seulement si
ou bien A ≠ O et B = O,
ou bien A = A_1 ⋅ A_2 et B = B_1 ⋅ B_2 et l'une des trois conditions suivantes est satisfaite:
A_1▹B_1 et A▹B_2,
A_1 = B_1 et A_2 − B_2,
A_2 − B ou A_2 = B.
Montrer que est un ordre strict total sur 𝔸.
Montrer que A▹B implique A▹B. Autrement dit que si A est un sur-arbre strict de B alors A▹B.
Donner un algorithme qui étant donnés deux arbres A et B retourne vrai si A▹B et faux sinon.
Montrer que pour tout élément de 𝔸 le successeur existe. Peut-on exprimer s_∙(A) à partir de A, ≪ ⋅ ≫ et O ?
Pour prouver que est bien fondée sur 𝔸, on va raisonner par l'absurde. S'il existe une suite infinie -décroissante, il en existe une que nous notons (A_i)_(i ∈ ℕ) et qui est plus petite que les autres au sens suivant :
A_0 est un plus petit arbre par la taille, qui commence une suite infinie décroissante.
Si l'on suppose A_0, …, A_i construits, A_(i + 1) est un plus petit arbre par la taille en ( i + 1 )-ème position pour une suite infinie décroissante qui commence par A_0, …, A_i.
Montrer que cette suite ne contient pas O. Montrer qu'on peut construire une suite infinie décroissante plus petite que la suite (A_i)_(i ∈ ℕ), d'où une contradiction.
Montrer que l'identité est une application croissante de (𝕆, ≻) vers (𝔸, >).
Déduire de la question précédente que la bonne fondation de (𝔸,) implique la bonne fondation de (𝕆, ≻). On a ainsi une nouvelle démonstration de la bonne fondation de ( 𝕆, ≻ ).
On considère la fonction croissante ψ : (𝕆, ≻) ⟶ (𝔸, ▹) qui satisfait les conditions suivantes :
La dernière identité doit se lire
«si sup _≻M existe, alors sup _⋆ψ(M) existe et ψ( sup _≻M) = sup _↓ψ(M)≫.
Que valent les quantités suivantes?
(a) ψ((O ⋅ O) ⋅ O) ?
(b) ψ(((O ⋅ O) ⋅ O) ⋅ O) ?
(c) ψ((((O ⋅ O) ⋅ O) ⋅ O) ⋅ O) ?
5 Un ordre sur les mots
Dans cette partie, on va étudier une catégorie d'ordres bien fondés qui possèdent certaines propriétés ainsi qu'un ordre sur les mots.
Une suite (x_i)_(i ∈ ℕ) dans laquelle il existe i et j tels que i < j et x_i ≤ x_j est dite bonne.
Une sous-suite de (x_i)_(i ∈ ℕ) est donnée par une application φ : ℕ → ℕ croissante, autrement dit la sous-suite est celle des (x_(φ(i)))_(i ∈ ℕ). Une suite (y_i)_(i ∈ ℕ) est faiblement croissante si i < j ⇒ y_i ≤ y_j. Une antichaîne de ( E, > ) est un sous ensemble A de E tel que pour tout (x, y) ∈ A^2 on a x ≥ y ⇒ x = y.
Montrer que les quatre propriétés suivantes sur un ordre strict ( E, > ) sont équivalentes.
(a) Tout ordre strict ⊐ qui satisfait (∀(x, y) ∈ E^2)(x > y ⇒ x⊐y) est bien fondé.
(b) (E, >) est bien fondé et sans antichaîne infinie.
(c) Toute suite est bonne,
(d) De toute suite (x_i)_(i ∈ ℕ) on peut extraire une sous-suite faiblement croissante.
Un ordre qui satisfait ces conditions équivalentes est dit unbel ordre.
2. On définit l'ordre ⋗ sur A^∗ qui étend l'ordre > _A sur A. − α⋗ε, − a ≥ _A b et α⋗β impliquent aα⋗bβ, − α ≥ β implique aα > β.
Montrer que ( A^∗, ⋗ ) est un bel ordre si et seulement si ( A, > _A ) est un bel ordre. Indication : On pourra utiliser une technique de démonstration qui s'inspire de celle de la question 4.5.
Pas de description pour le moment
Commentaires• ENS Informatique MP PC 2002
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même année, XPolytechnique Informatique Commune MP PC 2002X · 2002Corrigé
Même année, CCINPCCINP Option Informatique MP 2002CCINP · 2002Corrigé
Même année, CentraleCentrale Option Informatique MP 2002Centrale · 2002Corrigé.jpg)
