INF1130 SESSION A14 DEVOIR 2 : SOLUTIONS
Professeurs : Anne Bergeron et Elmahdi Driouch
Question 1 (30 points) sur les entiers.
Dans cette question, il est utile de rappeler le resultat suivant :
PGCD(a, b) = PGCD(a, a + b).
a) Donnez, a N la valeur de PGCD(a, a + 2). Justifiez.
On a PGCD(a, a + 2) = PGCD(a, 2), donc si a est impair,
PGCD(a, a + 2) = 1, et si a est pair PGCD(a, a + 2)=2.
b) On definit la suite an de la facon suivante :
1. a0 = 2
2. a1 = 4
3. an = an1 + an2 si n 2.
Les premiers elements de la suite sont donc 2, 4, 6, 10, 16, 26, . . . Calculez le
PGCD(an , an+1 ) pour chaque valeur de n. Demontrez votre resultat par induction simple.
n N, PGCD(an , an+1 ) = 2.
Preuve par induction :
1) Cas de base : si n = 0, on calcule PGCD(2, 4) = 2, puisque 4 est un
multiple de 2.
2) Etape
inductive : Supposons que PGCD(an , an+1 ) = 2, montrons que
PGCD(an+1 , an+2 ) = 2.
On a PGCD(an+1 , an+2 ) = PGCD(an+1 , an+1 + an ) par la r`egle 3.
Puis PGCD(an+1 , an+1 + an ) = PGCD(an+1 , an ) par le resultat ci-haut.
Enfin PGCD(an+1 , an ) = 2, par lhypoth`ese dinduction.
Donc n N PGCD(an , an+1 ) = 2
c) Decrivez les suites suivantes au moyen de la fonction modulo. Par exemple,
la suite 0, 1, 2, 0, 1, 2, 0 peut etre decrite comme {i mod 3}6i=0 .
i. 2, 1, 0, 1, 2, 1, 0, 1, 2 {(i mod 4) 2]}8i=0
ii. 0, 1, 4, 9, 16, 0, 1, 4, 9, 16 {(i mod 5)2 ]}9i=0
iii.. 8, 12, 4, 8, 12, 4, 8, 12, 4, 8, 12, 4 {4[1 + i mod 3]}12
i=1
Question 2 sur les ensembles d
efinis r
ecursivement (30 points)
Un ensemble de chaines M sur lalphabet {0, 1} est defini recursivement
comme suit :
1. , la chaine vide, est dans M.
2. Si x et y sont dans M, alors la chaine 0xy1 est dans M.
a) Decrivez, dune mani`ere simple et facile `a lire, toutes les chaines de longueur
inferieure ou egale `
a 10. Le probl`eme est double ici : votre reponse doit etre
correcte, ET le correcteur doit pouvoir juger en moins dune minute si votre
reponse est bonne. Il y a beaucoup de bonnes representations differentes.
b) Montrez, par induction sur le nombre de fois o`
u la r`egle 2 est appliquee,
que, pour toute chaine de M, le nombre de caract`eres 0 est egal au nombre de
caract`eres 1.
c) (* Bonus 10 points *) Pourquoi avons-nous choisi lidentificateur M pour
designer cet ensemble ? Quelle est limportance de ces chaines en informatique ?
[Vous avez le droit de chercher sur Internet : citez vos sources !]
Solution de a) : Les chaines sont ordonnees par longueur. Le souligne est utilise
pour montrer quelles sont les chaines x et y non-vides utlisees.
Longueur 0 : il y en a 1.
Longueur 2 : il y en a 1.
01
Longueur 4 : il y en a 1.
0 01 1
Longueur 6 : il y en a 2.
0 01 01 1
0 0011 1
Longueur 8 : il y en a 4.
0 01 0011 1
0 0011 01 1
0 001011 1
0 000111 1
Longueur 10 : il y en a 9.
0 01 001011 1
0 001011 01 1
0 01 000111 1
0 000111 01 1
0 0011 0011 1
0 00101111 1
0 00001011 1
0 00010111 1
0 00001111 1
Solution de b) :
Preuve par induction generalisee sur le nombre de fois o`
u la r`egle 2 est appliquee.
1) Cas de base : si la r`egle 2 est appliquee 0 fois, on a la chaine vide, qui
contient le meme nombre de 0 que de 1.
2) Etape
inductive : supposons que toutes les chaines obtenues avec au plus
n, n > 0, applications de la r`egle 2 ont le meme nombre de 0 que de 1, et
montrons que cest vrai pour une chaine obtenue avec n + 1 applications de la
r`egle 2.
Soit z une chaine obtenue avec n + 1 applications de la r`egle 2. Comme on
a applique au moins une fois la r`egle 2, z = 0xy1 o`
u x et y ont ete obtenues
avec au plus n applications de la r`egle 2. Par hypoth`ese dinduction, x et y ont
toutes les deux le meme nombre de 0 et de 1. Comme on ajoute un seul 0, et
un seul 1, la chaine z a le meme nombre de 0 que de 1.
Donc, toute chaine de M a le meme nombre de 0 que de 1.
Solution de c) :
1. Parce que les chaines de longueur 2n sont enumerees par les nombres de
Motzkin.
2. Parmi les bonnes reponses : ces chaines sont liees `a levaluation dexpression arithmetiques unaires et binaires dans les compilateurs.
Question 3 sur les fonctions d
efinies r
ecursivement (30 points)
a) La fonction f (n) de N vers N est definie recursivement par les r`egles suivantes :
1. f (0) = 1.
2. f (n + 1) = f (n) + 2n + 3.
Donnez les valeurs de f (n) pour n [1..5]. Demontrez, par induction simple,
que f (n) = n2 + 2n + 1, pour n 0.
Les valeurs de f (n) pour n [1..5] sont : 1, 4, 9, 16 et 25.
Preuve par induction simple que f (n) = n2 + 2n + 1.
1) Cas de base : f (0) = 1 et 02 + 2 0 + 1 = 1 aussi.
2) Etape
inductive : supposons que f (n) = n2 + 2n + 1 et montrons que
f (n + 1) = (n + 1)2 + 2(n + 1) + 1.
On a que f (n + 1) = f (n) + 2n + 3 par definition. En appliquant lhypoth`ese
dinduction sur f (n), on trouve :
f (n + 1) = (n2 + 2n + 1) + 2n + 3 = (n + 1)2 + 2n + 3 = (n + 1)2 + 2(n + 1) + 1.
Donc f (n) = n2 + 2n + 1, pour n 0.
b) Demontrez, par induction simple sur n, que toute fonction p : N Z o`
u
p(n) = an2 + bn + c peut etre definie de facon recursive, peu importe les entiers
a, b et c. Remarque : vous devez dabord deviner lexpression recursive et
ensuite demontrer sa validite par induction simple.
Pour trouver une definition recursive de p(n), une facon de proceder est de
calculer p(n + 1) p(n) :
p(n + 1) p(n) = a(n + 1)2 + b(n + 1) + c (an2 + bn + c) =
an2 + 2an + a + bn + b + c an2 bn c =
2an + a + b.
Donc une definition recursive pour p(n) pourrait etre :
1. p(0) = c.
2. p(n + 1) = p(n) + 2an + a + b.
Preuve par induction simple que p(n) = an2 + bn + c
1) Cas de base : p(0) = c et a 02 + b 0 + c = c aussi.
2) Etape
inductive : supposons que p(n) = an2 + bn + c et montrons que
p(n + 1) = a(n + 1)2 + 2b(n + 1) + c.
On a que p(n + 1) = p(n) + 2an + a + b par definition. En appliquant
lhypoth`ese dinduction sur p(n), on trouve :
p(n + 1) = (an2 + bn + c) + 2an + a + b =
(an2 + 2an + a) + (bn + b) + c =
a(n + 1)2 + 2b(n + 1) + c
Donc p(n) = an2 + bn + c, pour n 0.
Question 4 sur les relations (30 points)
Un intervalle de nombres naturels est un ensemble note [a, b] o`
u a b et
tel que [a, b] = {n|a n b}. On definit les relations suivantes sur les couples
intervalles :
(Inclus) Le couple ([a, b], [c, d]) R1
si c a b d.
(Disjoints) Le couple ([a, b], [c, d]) R2
si (b < c) ou (a > d).
(Chevauchants) Le couple ([a, b], [c, d]) R3
si [(a < c b) et (d > b)] ou [(c < a d) et (b > d)].
a) Dites `
a quelle(s) relation(s) appartiennent chacun des couples suivants :
1.
2.
3.
4.
5.
6.
([1, 2], [3, 4]) R2
([1, 5], [3, 7]) R3
([1, 2], [2, 4]) R3
([1, 5], [2, 3]) Aucune
([4, 8], [1, 10]) R1
([3, 3], [1, 3]) R1
b) Pour chacune des relations R1 , R2 et R3 , dites si la relation est symetrique
ou non, reflexive ou non, transitive ou non. Dans chaque cas, cest-`a-dire 9 cas,
demontrez vos affirmations a` laide dun preuve ou dun contrexemple.
R1 est la relation dinclusion [a, b] [c, d], Elle est :
(1) Non-symetrique : Contre-exemple ([4, 8], [1, 10]) R1 , mais ([1, 10], [4, 8])
/
R1 car 4 > 1.
(2) Reflexive : Quelque soit [a, b], on a ([a, b], [a, b]) R1 , puisque a a b b.
(3) Transitive : Soit ([a, b], [c, d]) R1 et ([c, d], [e, f ], ) R1 , on veut montrer
que ([a, b], [e, f ]) R1 . Comme e c et c a, on a bien e a ; et comme b d
et d f , on a bien aussi b f . Donc ([a, b], [e, f ]) R1 , puisque a b est vrai
par definition.
R2 est la relation entre deux intervalles disjoints. Elle est :
(4)Symetrique : Soit ([a, b], [c, d]) R2 , alors (b < c) ou (a > d). Si on echange
le r
ole de [a, b] et [c, d] dans cette dernire affirmation, on a la condition (d < a)
ou (c > b), qui a exactement la meme valeur de verite, donc ([c, d], [a, b]) R2 .
(5) Non-reflexive : Le couple ([1, 2], [1, 2]), par exemple, nest pas dans R2 .
(6) Non-transitive : Les couples ([1, 2], [3, 4]) et ([3, 4], [1, 2]) sont dans R2 , mais
le couple ([1, 2], [1, 2]) ny est pas.
R3 est la relation de chevauchement, avec [a, b] \ [c, d], [c, d] \ [a, b] et [a, b] [c, d]
tous non-vides. Elle est :
(7) Symetrique : Soit ([a, b], [c, d]) R3 , alors [(a < c b) et (d > b)] ou [(c <
a d) et (b > d)]. Si on echange le role de [a, b] et [c, d] dans cette dernire
affirmation, on obtient [(c < a d) et (b > d)] ou [(a < c b) et (d > b)] qui a
exactement la meme valeur de verite, donc ([c, d], [a, b]) R3 .
(8) Non-reflexive : Le couple ([1, 2], [1, 2]), par exemple, nest pas dans R3 ., car
1 < 1 est faux.
(9) Non-transitive : Les couples ([1, 5], [3, 7]) et ([3, 7], [1, 5]) sont dans R3 , mais
pas ([1, 5], [1, 5]).
Question 5 sur les relations d
equivalence (30 points)
Le syst`eme de fichiers de la compagnie Unique est organise en repertoires
hierarchiques, dont la racine est toujours nommee A. Chaque repertoire est
identifie par une chane de caract`eres, et chaque repertoire, sauf la racine, est
enfant dun unique repertoire. Par exemple, le repertoire D de lutillisateur
Alpha (voir Figure 1) est enfant du repertoire C, et son repertoire P est enfant
du repertoire A.
Pour acceder `
a un repertoire r `a partir de la racine A, il faut utiliser une
commande de la forme Acc`es <argument>, o`
u <argument> est la liste des
enfants successifs de la racine A qui m`ene `a r. Par exemple, pour acceder au
repertoire N de lutillisateur Alpha, `a partir de la racine, la commande dacc`es
a comme argument A K L N .
A!
B!
G!
C!
H!
E!
D!
F!
K!
I! J!
P!
L!
Q!
M!
N!
R!
Figure 1 Le bureau virtuel de lutilisateur Alpha.
Le niveau dun repertoire r est defini comme le nombre de symboles que
contient largument de la commande pour acceder au repertoire r `a partir de la
racine A. Par exemple, le niveau du repertoire N est 3. Le niveau du repertoire
A est 0.
On definit la relation R suivante sur lensemble des repertoires dun utilisateur :
(r, s) R si r et s sont au meme niveau.
a) Demontrez que la relation R est une relation dequivalence.
Reflexivite : Quel que soit r, r est au meme niveau que lui-meme.
Symetrie : Si r est au meme niveau que s, alors s est au meme niveau que r.
Transitivite : Si r est au meme niveau que s, et s est au meme niveau que t,
alors r est au meme niveau que t.
b) Donnez, pour lutilisateur Alpha, la partition de ses repertoires engendree
par la relation R.
{A}, {B, G, K, P }, {C, E, H, L, Q}, {D, F, I, M, N, R}, {J}
