[PDF] INF1130 SESSION H13 : SOLUTIONS du DEVOIR 2

View - Download INF1130 SESSION H13 : SOLUTIONS du DEVOIR 2

Previous PDF

Next PDF

INF1130 SESSION H13 : SOLUTIONS du DEVOIR 2

Question 1 sur l'induction (30points)

a)Utilisez le principe d'induction pour montrer que pour tout entiern>0 (2n+ 1)21 est divisible par 8. Cas de base : sin= 0, alors (2n+1)21 = 0, et est divisible par 8 puisque

0 est divisible par 8.

Hypothese d'induction : supposons que (2n+ 1)21 est divisible par 8. Il faut montrer que l'hypothese d'induction entra^ne que (2(n+ 1) + 1)21 est divisible par 8.

On developpe d'abord l'expression :

(2(n+ 1) + 1)21 = (2n+ 3)21 = 4n2+ 12n+ 91 = ((4n2+ 4n+ 1)1) + 8n+ 8 = ((2n+ 1)21) + 8(n+ 1): La derniere expression est divisibe par 8, puisque ((2n+ 1)21) est divisible par 8, par hypothese d'induction, et 8(n+ 1) est un multiple de 8. b)Utilisez le principe d'induction pour montrer que pour tout entiern>1 1

3+ 23+:::+n3=n2(n+1)24

Cas de base : sin= 1, on a bien 13= 12(1 + 1)2=4:

Hypothese d'induction : supposons que 1

3+ 23+:::+n3=n2(n+ 1)2=4:Il

faut montrer que l'hypothese d'induction entra^ne que 1

3+23+:::+n3+(n+1)3=

(n+ 1)2(n+ 2)2=4: On applique l'hypothese d'induction a la partie gauche de l'egalite a mon- trer : 1

3+ 23+:::+n3+ (n+ 1)3=n2(n+ 1)2=4 + (n+ 1)3

= (n+ 1)2(n2=4 +n+ 1) = (n+ 1)2(n2+ 4n+ 4)=4 = (n+ 1)2(n+ 2)2=4: c)Utilisez le principe d'induction pour montrer que pour tout entiern>1

1:1! + 2:2! +:::+n:n! = (n+ 1)!1:

Cas de base : sin= 1, on a bien 1:1! = (1 + 1)!1:

Hypothese d'induction : supposons que 1:1!+2:2!+:::+n:n! = (n+1)!1: Il faut montrer que l'hypothese d'induction entra^ne que 1:1!+2:2!+:::+n:n!+ (n+ 1)(n+ 1)! = (n+ 2)!1: 1 On applique l'hypothese d'induction a la partie gauche de l'egalite a mon- trer :

1:1! + 2:2! +:::+n:n! + (n+ 1)(n+ 1)! = (n+ 1)!1 + (n+ 1)(n+ 1)!

= (n+ 1)!(n+ 2)1 = (n+ 2)!1: Question 2 sur les codes correcteurs d'erreurs (20points) On s'interesse aux cha^nes de bits de longueurn1. Pour une taillendonnee, on divise les cha^nes en deux sous-ensembles :Bn, lesbonnescha^nes, contiennent un nombre pair de bits a `1'; etMn, lesmauvaises, contiennent un nombre im- pair de bits a `1'. par exemple, 000101002B8et 0111002M6. a)Donnez une denition recursive des ensemblesBnetMn, sachant queB1= f0getM1=f1g.

Pourn2, on a les 4 regles suivantes :

Six2Mn1alorsx12Bn:

Six2Bn1alorsx02Bn:

Six2Mn1alorsx02Mn:

Six2Bn1alorsx12Mn:

b)Ladistance de Hammingd(x;y) entre deux cha^nes de bitsxetyde lon- gueurnest le nombre de positions ou les cha^nes sont dierentes. Par exemple d(0101;1100) = 2 etd(0111;1100) = 3. L'enonce suivant est-il vrai ou faux?

Justiez.

Six;y2B4etx6=y;alorsd(x;y) = 2:

Les elements deB4sont les suivants :

B Il est vrai que pourd(x;y) = 2 pour presque chaque pairex;y, sauf pour x= 0000 ety= 1111. Donc l'enonce est faux.

Question 3 sur la suite deFibonacci(25points)

On s'interesse a la suite deFibonaccidenie recursivement comme suit : f

0= 1;f1= 1;fn=fn1+fn2;8n>2:

a)Donnez les 10 premiers termes de cette suite.

1;1;2;3;5;8;13;21;34;55

2 b)Montrez que le nombre1+p5 2 satisfait l'equationx2=x+ 1. [(1 + p5)=2]2= (1 + 2p5 + 5)=4 = (2 + 2p5)=4 + 4=4 = (1 +p5)=2 + 1 c)Utilisez le principe d'induction pour montrer quefn>(1+p5 2 )n2;8n>3:

Cas de base : sin= 3, on a l'inequation 3>(1+p5

2 ) qui est certainement vraie carp5<5. Sin= 4, comme (1+p5 2 )2= (1+p5)=2+1>3+1, on a bien

5>(1+p5

2 )2. Hypothese d'induction generalisee : supposons quefi>(1+p5 2 )i2pour tous les entiers 3in. Il faut montrer que l'hypothese d'induction entra^ne que f n+1>(1+p5 2 )n1. Les calculs suivants seront plus clairs si on remplace l'expression ( 1+p5 2 ) par un symbole,apar exemple. On a alors : f n+1=fn+fn1 > a n2+an3par hypothese d'induction, =an3(a+ 1) =an3(a2) par la partie b), =an1: d)Ordonnez, selon leur taux de croissance, les fonctions :fn,n2, 2net (3=2)n.

Justiez.

n

2;(3=2)n;fn;2n

Ceci provient du fait que

32
<1+p5 2 <2 et quefn< an, qui se demontre de faon analogue a la preuve donnee dans la partie c). Question 4 sur les suites denies recursivement (20points) Considerons la suite numerique denie recursivement, comme suit : f n=(

2;sinest impair

(f(n2 ))2;sinest pair a)Donnez les 10 premiers termes de cette suite.

2;4;2;16;2;4;2;64;2;4

3 b)Utilisez le principe d'induction pour montrer quefn62n;8n>1: Cas de base : sin= 1, on afn= 2 et 2n= 2, doncf121est verie . Hypothese d'induction generalisee : supposons quefi2ipour tous les entiers 1in. Il faut montrer que l'hypothese d'induction entra^ne que f n+12n+1. Sin+ 1 est impair, alorsfn+1= 2 et puisquen1, on a bienfn+1= 2 2 n+1. Sin+ 1 est pair, alors (f(n+12 ))2(2(n+1)=2)2= 2n+1, par hypothese d'induction. Question 5 sur les relations d'equivalence (25points)

Sur l'ensembleA=f1;13

;127 ;14 ;3;136 ;2;29 ;94 ;5g, on considere la relation binaire suivante :

8x;y2A:xRy() 9z2Z;xy

= 3z a)Tracez le graphe de la relationR. [Aide pour la correction : disposez vos

points autour d'un cercle imaginaire.]!"!#$%"!#&"&"!#'"(#'"!#&)"$"$#("*"b)Montrez queRest une relation d'equivalence surA.

Re exivite :xRxest toujours vrai carx=x= 1 = 30. Symetrie : SupposonsxRy, alors il existeztel quex=y= 3z, doncy=x= 3z. Commezest entier,zest aussi un entier, ce qui entra^ne queyRx. Transitivite : SupposonsxRyetyRz. On a doncx=y= 3zety=z= 3z0ou zetz0sont des entiers. Calculonsx=z: x=z= (x=y)(y=z) = (3z)(3z0) = 3z+z0: Commezetz0sont des entiers, leur somme est aussi un entier, doncxRz. 4 c)Donnez les classes d'equivalence deAdenies parR. f1;13 ;127 ;3g f 14 ;136 ;94 g f2;29 g f5g

Question 6 sur les graphes (30points)

a)Pour chacune des listes suivantes, determinez s'il existe un graphe simple ayant cette liste comme liste de degres. Donnez la reponse pour chaque liste avec oui ou non. 1. (2 ;3;3;3;4;4);Non. Le nombre de sommets de degre impair doit ^etre pair. 2. (1 ;2;3;4);Non. Le degre d'un sommet ne peut pas ^etre superieur ou egal au nombre de sommets. 3. (1 ;1;1;3);Oui. 4. (1 ;3;3;3);Non. Chacun des sommets de degre 3 devrait ^etre adjacent a tout autre sommet y compris le sommet de degre 1. 5. (1 ;2;2;3;4;4);Oui. 6. (1 ;3;3;4;5;5);Non. Chacun des sommets de degre 5 devrait ^etre relie a tout autre sommet y compris le sommet de degre 1. 7. (2 ;2;2);Oui. 8. (2 ;2;4;4):Non. Le degre d'un sommet ne peut pas ^etre superieur ou egal au nombre de sommets. b)Combien d'ar^etes un graphe contient-il si sa liste de degres est (2;2;2;4;4)?

Tracez un tel graphe.

Le graphe contient 7 ar^etes. Voici un exemple d'un tel graphe :c)Utilisez le principe d'induction pour montrer que le nombre d'ar^etes dansKn

(le graphe complet d'ordren) est egal an(n1)2 pour toutn>1. Cas de base : sin= 1, alors le graphe n'a pas d'ar^ete etn(n1)=2 = 0. Hypothese d'induction : supposons que le nombre d'ar^etes dansKnest n(n1)=2. Il faut montrer que le nombre d'ar^etes dansKn+1est (n+ 1)(n)=2. 5 Considerons le grapheKn+1. Commen1, le graphe a au moins 2 sommets, et le degre de chaque sommet estn. Eacons un sommet, ainsi que lesnar^etes qui lui sont rattachees. Le graphe resultant estKnqui comporte, par hypothese d'induction,n(n1)=2 ar^etes. Donc le nombre d'ar^etes deKn+1est : n(n1)=2 +n= (n2n+ 2n)=2 = (n2+n)=2 = (n+ 1)(n)=2: 6quotesdbs_dbs47.pdfusesText_47

[PDF] Montrer que pour tout entier c : =1

[PDF] montrer que q est dénombrable

[PDF] montrer que racine de 3 est irrationnel

[PDF] montrer que racine de n est irrationnel

[PDF] montrer que se sont des rationnels

[PDF] montrer que si x appartient ? l'intervalle

[PDF] montrer que x appartient ? un intervalle

[PDF] montrer que xn 1 axn

[PDF] Montrer que y=

[PDF] MONTRER QUELQUE CHOSE SANS LE MONTRER POUR PEUT ÊTRE MONTRER TOUT AUTRE CHOSE

[PDF] Montrer registre tragique

[PDF] Montrer si le nombre A est un entier ou pas

[PDF] montrer une inégalité avec valeurs absolues

[PDF] montrer une relation d'ordre

[PDF] montrer verbe