Bases, logarithmes, r´ecurrence

Plus sur les mathématiques :

http://www.audentia-gestion.fr/MATHEMATIQUES/

ou juste avant la balise de fermeture -->

Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices 1 Bases, logarithmes, r´ecurrences 1.1 Manipulations de bases Exercice 1 Cole Sear, le petit gar¸con du Sixi`eme sens, disait : « I see dead people ». Ce que le protagoniste, jou´e par Bruce Willis, ne savait pas, c’est que le petit gar¸con comptait en hexad´ecimal. Combien de personnes voyait-il ? Exercice 2 Faire les conversions suivantes : – (101010)2 en base 10 – (483)10 en binaire – (111100011)2 en hexad´ecimal Exercice 3 Calculer, sans passer syst´ematiquement par la base 10, les expressions suivantes : – (102013)4 + (1)4 – (102013)4 × (4)10 et (102013)4 ÷ (4)10 – (101011)2 + (2A)16 – (10110)2 + (111)1 1.2 Logarithmes et puissances Exercice 4 1. Quel est le nombre le plus grand que l’on puisse repr´esenter avec n caract`eres en binaire ? 2. En d´eduire le nombre de caract`eres n´ecessaires pour repr´esenter en binaire un nombre m quelconque. 3. G´en´eraliser `a une base b quelconque. Exercice 5 1. Combien faut-il de caract`eres pour repr´esenter (42)10 en binaire ? 2. Combien vaut log2 (16) ? 3. A partir des deux questions pr´ec´edentes, calculer combien il faut de caract`eres pour ` repr´esenter (42)10 en hexad´ecimal. 1.3 Preuves par r´ecurrence Exercice 6 D´emontrer par r´ecurrence les propri´et´es suivantes : 1. ?n = 1, 1 + 2 + . . . + n = n(n + 1) 2 2. ?n = 1, 7 n - 1 est divisible par 6 3. ?n = 1, (n 3 - n) est divisible par 3 Exercice 7 1Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices Un nombre premier est un entier sup´erieur `a 1 qui n’a pas d’autre diviseurs que 1 et lui-mˆeme. Montrer que tout entier positif sup´erieur `a 1 peut ˆetre d´ecompos´e en un produit de facteurs premiers. Exercice 8 On se propose de d´emontrer le th´eor`eme suivant : Th´eor`eme : tout le monde est d’accord avec le professeur Preuve : 1. On consid`ere tout d’abord un groupe de taille n = 1, compos´e uniquement du professeur. La propri´et´e est naturellement v´eri?´ee ; 2. On suppose maintenant que la propri´et´e est vraie pour un groupe de taille n. On consid`ere alors un groupe de taille n + 1, o`u le professeur est la n i`eme personne. Si on exclue la personne n + 1, alors tout le monde est d’accord avec le professeur (par hypoth`ese de r´ecurrence). Si on retire maintenant la premi`ere personne, les n personnes restantes sont ´egalement d’accord avec le professeur, toujours pas hypoth`ese de r´ecurrence. On conclue donc que la propri´et´e est vraie pour n + 1. Question : cette preuve est-t-elle correcte ? Si non, o`u est l’erreur ? 2 R´ecursivit´e Exercice 9 Dans cet exercice, on consid`erera une liste L contenant n nombres entiers. 1. Proposer une m´ethode r´ecursive pour rechercher un nombre k dans L 2. Proposer deux m´ethodes r´ecursives permettant de rechercher le plus grand entier contenu dans L. Exercice 10 Alice pense `a un nombre entre 1 et 100, et Bob doit deviner quel est ce nombre. Pour cela, il a le droit de poser des questions du type : « le nombre est-il k ? », auxquelles Alice doit r´epondre (honnˆetement) par « oui », « inf´erieur » ou « sup´erieur ». 1. Quelle est la strat´egie la plus rapide que Bob puisse utiliser ? 2. Combien de questions devra-t-il poser au maximum avant de trouver la r´eponse ? Exercice 11 Proposer une m´ethode permettant d’´enum´erer tous les mots de k lettres sur un alphabet `a n lettres. Combien y en a-t-il ? Exercice 12 D´e?nition : un palindrome est un mot (ou une phrase) dont les lettres peuvent ˆetre lue de la mˆeme mani`ere qu’on les lise de gauche `a droite ou de droite `a gauche. Par exemple : « radar », ou encore « Et si l’arˆome des bottes r´ev`ele ma d´eviante et na¨ive dame, le verset t’obs`ede, moraliste ! ». Proposer une d´e?nition r´ecursive d’un palindrome (on ignorera les espaces et la ponctuation). Exercice 13 D´e?nition : Soient a, b ? N, avec a = 0 ou 6 b = 0. On s’int´eresse `a l’ensemble 6 D des nombres qui divisent a et b. D contient au moins un ´el´ement, 1, et est ?ni, donc D contient un plus grand ´el´ement, qu’on nomme le plus grand commun diviseur (ou pgcd) de a et b. On cherche `a calculer pgcd(a, b). 2Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices 1. Montrer que si n divise a et b, n divise aussi le reste r de la division euclidienne de a par b. En d´eduire que pgcd(a, b) = pgcd(b, r). 2. En d´eduire un algorithme permettant de calculer pgcd(a, b). Exercice 14 Dans le jeu de Nim, un certain nombre de bˆatons sont dispos´ees en rang devant deux joueurs. Chaque joueur, `a tour de rˆole, choisit de prendre 1, 2 ou 3 bˆatons. Celui qui prend le dernier bˆaton a perdu. 1. Qui gagne si la position de d´epart comporte 1, 2, 3, 4 ou 5 bˆatons ? 2. Si la position de d´epart comporte un nombre quelconque de bˆatons, quelle est la strat´egie `a suivre pour gagner ? Exercice 15 On appelle un ´echiquier `a trou de rang n un plateau compos´e de 2 n × 2 n cases, dont une des cases a ´et´e enlev´ee. Un ´echiquier `a trou de rang 1 comporte donc 3 cases et un trou. Un ´echiquier `a trou de rang 2 est repr´esent´e sur la ?gure ci-dessous. Un triomino en « L » est un bloc de trois carr´es dispos´es comme indiqu´e sur la ?gure. triomino échiquier à trou 1. Est-il possible de paver l’´echiquier de la ?gure `a l’aide de triominos ? 2. Est-il toujours possible de paver un ´echiquier `a trou `a l’aide de triominos ? Exercice 16 On cherche `a calculer le nombre maximum de parts de pizza que l’on peut obtenir en e?ectuant k coupes droites dans une pizza. Peu importe la taille ou la forme des parts. Appelons ce nombre Pk. 1. Calculer P0, P1, P2, P3 `a la main. 2. Si l’on a d´ej`a e?ectu´e k coupes, quelle est la meilleure strat´egie pour placer la coupe k + 1 a?n de maximiser le nombre de parts cr´e´ees ? 3. Exprimer Pk+1 en fonction de Pk 4. Exprimer Pk en fonction de k 3 Fonctions, relations, structures alg´ebriques 3.1 Les ensembles Exercice 17 Soit E = {1, 2, 3, 4, 5, 6, 7} et soit les parties suivantes de E : 3Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices A = {1, 2, 3, 4}, B = {4, 5, 6, 7}, C = {1, 3, 5, 7}, et D = {2, 3, 4, 5, 6} Calculer 1. A, A ? C, A ? C, A n C, A n C, 2. (A n B) ? (C n D), (A ? C) n (B ? D) 3. A - D, D - A, A 4 D Exercice 18 On s’int´eresse au nombre de voitures gar´ees dans un parking. On a les informations suivantes : il y a – 100 voitures de la marque « Renault », – 85 voitures de couleur claire, – 36 voitures de la marque « Renault » et de couleur fonc´ee, Peut-on calculer le nombre de v´ehicules sur le parking ? Si, oui, calculer le. Si non, dire pourquoi. Exercice 19 Donner les positions relatives de A, B, C ? E si A ? B = B n C Exercice 20 Soit A, B deux parties d’un ensemble E. A l’aide de dessins, comparer 1. entre (A n B) et A n B 2. entre (A ? B) et A ? B Exercice 21 Soient A, B, C trois sous-ensembles quelconques d’un ensemble E. D´emontrer que – A n (B ? C) = (A n B) ? (A n C) – A ? B = A n B – A n B = A ? B – A - B = A n B – A ? B = (A n B) ? (A n B) ? (A n B). Exercice 22 Montrer que : A n B = A n C ?? A n B = A n C Exercice 23 Soit f : E ? F une application. Soit A, B ? E et soit C, D ? F . A-t-on n´ecessairement : 1. f(A n B) = f(A) n f(B) 2. f(A ? B) = f(A) ? f(B) 3. f -1 (C n D) = f -1 (C) n f -1 (C) 4. f -1 (C ? D) = f -1 (C) ? f -1 (C) 5. f -1 (f(A)) = A 6. f(f -1 (C)) = C Justi?er chaque cas par une preuve ou par un contre-exemple. 4Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices 3.2 Les fonctions Exercice 24 A l’aide de ` « patates », dessiner une application non injective, puis une application non surjective. Exercice 25 D´eterminer si les applications suivantes sont surjectives ou non : 1. l’application f : N ? N d´e?nie par f(n) = b n 2 c ; 2. l’application f : N ? N d´e?nie par f(n) = 2n ; 3. l’application f : N ? Z d´e?nie par f(n) = (-1) n d n 2 e. Exercice 26 Montrer que les applications suivantes sont injectives ou non 1. l’application f : N ? N d´e?nie par f(n) = b n 2 c ; 2. l’application f : N ? N d´e?nie par f(n) = 2n ; 3. l’application f : N ? Z d´e?nie par f(n) = (-1) n d n 2 e. Exercice 27 L’application f(x) = x + 1 est-elle bijective de N vers N ? Et de Z vers Z ? Exercice 28 Interpr´eter les phrases suivantes en terme d’injectivit´e et de surjectivit´e : 1. il existe des nombres entiers relatifs di?´erents (dans Z) qui ont le mˆeme carr´e ; 2. tout nombre r´eel positif a une racine carr´ee ; 3. le nombre 3 n’est le sinus d’aucun nombre ; 4. un nombre complexe est caract´eris´e par ses parties r´eelles et imaginaires. Exercice 29 Soient A et B des ensembles ?nis, et soit f : A ? B une application : 1. si f est injective, alors |A| = |B| ; 2. si f est surjective, alors |A| = |B|. Exercice 30 Soient f : E ? F et g : F ? G deux applications et h = g ? f. Montrer les propositions suivantes : 1. h surjective ? g surjective 2. h injective ? f injective 3. (h injective et f surjective) ? g injective 4. (h surjective et g injective) ? f surjective Les implications r´eciproques sont-elles vraies ? Exercice 31 Soit f : E ? E une application. On d´e?nit par r´ecurrence les applications f n par f 1 = f et f n = f ? f n-1 . 1. On suppose que f est injective. Montrer que ?n ? N, f n est injective. 2. On suppose que f est surjective. Montrer que ?n ? N, f n est surjective. 5Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices 4 Relations 4.1 Relations Exercice 32 Ecrire sous forme d’ensemble les relations suivantes : ´ – « est inf´erieure strictement `a » – « est inf´erieure ou ´egal `a » Sont-elles re?exives, sym´etriques, transitives ? Exercice 33 Ecrire sous forme de relation les applications suivantes : ´ 1. l’application f : N ? {0, 1} d´e?nie par f(x) = x mod 2 ; 2. l’application f : N ? N d´e?nie par f(n) = 2n Exercice 34 Consid´erons le graphe de compatibilit´e des groupes sanguins : x ? y signi?e que une personne du groupe sanguin x peut donner son sang `a une personne du groupe sanguin y. D´e?nir la relation « compatibilit´e ». Est-elle re?´exive, transitive, sym´etrique, antisym´etrique ? Exercice 35 La relation suivante est-elle une relation d’´equivalence : T : T = {(a, b) : a, b ? N, et a + b pair }. Donner la classe d’´equivalence de 3, 4, 5, 6 Exercice 36 Donner des exemples de relations qui sont 1. r´e?exives et sym´etriques mais pas transitives, 2. r´e?exives et transitives mais pas sym´etriques, 3. sym´etriques et transitives mais pas r´e?exives, Exercice 37 Les relations suivantes sont-elles des relations d’ordre ? 6Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices 1. P : ?x, y ? N, xPy ? x = y. 2. Q : ?x, y ? N, xQy ? x < y. 3. R : ?x, y ? N, xRy ? x est multiple de y. Exercice 38 Montrer que pour tout entier n, la relation « ´equivalent modulo n » est une relation d’´equivalence sur les entiers. Cette relation partitionne-t-elle les entiers ? Rappel : On dit que a = b mod n s’il existe une entier q tel que a - b = qn. Exercice 39 Soit E = {1, 2, 3, 4, 5, 6, 7, 8}. On d´e?nit sur l’ensemble E × E la relation R : (p, q)R(p 0 , q 0 ) si p - p 0 est pair et q - q 0 est divisible par 3. 1. Donner le cardinal de E × E. 2. V´eri?er que R est une relation d’´equivalence. On d´esigne par (p, q) la classe d’´equivalence de (p, q). 3. Combien y a-t-il de classes d’´equivalence di?´erentes ? Donner leur liste. (a) Calculer le nombre d’´el´ements des classes (1, 1), (1, 2) et (1, 3). (b) Soit q ? E. Montrer que si (x, y) ? (1, q), alors (x + 1, y) ? (2, q) 4. D´eterminer le cardinal de chaque classe d’´equivalence. Le r´esultat est-il compatible avec celui de la question 1 ? 5 Structures alg´ebriques Exercice 40 Dans Z, trouver : 1. une loi non associative 2. une loi n’ayant pas d’´el´ement neutre 3. une loi pour lequel il n’y a pas toujours d’´el´ement inverse 4. une loi non commutative Exercice 41 Consid´erons l’ensemble E = {0, 1, . . . , k -1} et la loi ? : E ×E ? E d´e?nie de la fa¸con suivante x ? y = (x + y) mod k 1. Montrer que la loi ? admet un ´el´ement neutre, un ´el´ement inverse pour chaque ´el´ement de E. 2. Montrer que loi ? est associative. 3. Que peut-on en d´eduire ? Exercice 42 Construire un groupe `a partir de E1 = {e}, de E2 = {e, a} D´e?nition : Soient (G, ?), et (G0 , •) deux groupes. On appelle un morphisme de groupes de (G, ?) dans (G0 , •), toute application f : G ? G0 qui v´eri?e la condition ?(x, y) ? G2 f(x ? y) = f(x) • f(y) 7Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices Exercice 43 Montrer que f : G ? G tel que f(x) = x est un morphisme de groupe. Exercice 44 Soit f morphisme de groupes de (G, ?) dans (G0 , •). Montrer que – L’image par f de l’´el´ement neutre e de G est l’´el´ement neutre e 0 de G0 – pour tout x ? G, f(x -1 ) = (f(x)) -1 – pour n ? Z pour tout x ? G, f(x n ) = (f(x)) n Exercice 45 On poss`ede un bol B rempli de pierres blanches et un bol N rempli de pierres noires •. On consid`ere l’op´eration ./ qui consiste `a prendre des pierres dans B ou dans N , et `a les poser sur la table, en respectant la rˆegle suivante : chaque • annule un ?. On a par exemple : ? ./ ?? = ? ? ? ? ? ? ./ • = ?? •• ./ ? = • On consid`ere P l’ensemble des combinaisons de pierres que l’on peut former : P = {Ø, •, ?, ••, ??, . . .} De plus, apr`es avoir remarqu´e que les ´el´ements de P ne peuvent contenir qu’une couleur de pierres, on notera ? n le lot ? . . . ? contenant n pierres. 1. ./ est-elle une loi de composition interne sur P ? 2. (P, ./) est-il un groupe ? Est-il ab´elien ? 3. On consid`ere la fonction f, qui prend un lot de pierres quelconques et rajoute autant de pierres de la mˆeme couleur sur la table. On a donc f(??) = ? ? ??, et f(•) = ••. f : P ? P f(x k ) ? x 2k Montrer que f est un automorphisme. 4. On consid`ere maintenant g : P 2 ? P qui a x a , y b ? P associe le lot de pierres z construit de la mani`ere suivante : – pour chaque pierre blanche de x, on ajoute b pierres de la couleur de y au lot z. – pour chaque pierre noire de x, on ajoute b pierres de la couleur oppos´ee `a y. Ainsi, g(?, ••) = ••, g(•, ??) = ••, g(•, ••) = ?? et g(??, ••) = • • ••. Montrer que g est une loi de composition associative, distributive, avec un ´el´ement neutre. 5. Montrer que (P, ./, g) est un anneau. 6 Permutations Exercice 46 Sam Loyd, un auteur de jeux math´ematiques am´ericain, est r´eput´e avoir commercialis´e `a la ?n du XIXi`eme si`ecle le puzzle suivant (nomm´e « 14-15 »), en o?rant une prime de $1000 au premier qui trouverait la solution. Il s’agit d’une variante du jeu de taquin, invent´e par Noyes Chapman vers 1874, comportant 4x4 cases num´erot´ees, o`u les cases 14 et 15 sont invers´ees et o`u la 16i`eme case est manquante. 8Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 Il s’agit de replacer les cases dans le bon ordre, en faisant glisser une pi`ece touchant un trou `a la place du trou. On se propose dans cet exercice de v´eri?er si la r´esolution de ce puzzle est possible, ou si monsieur Loyd ´etait sˆur de garder ses $1000. Pour cela, nous allons ´etudier les permutations. D´e?nition : Soit E un ensemble. L’ensemble SE des bijections de E muni de la loi de composition des applications est un groupe. En particulier pour n > 0, l’ensemble des bijections de {1, . . . , n} muni de ? est un groupe qu’on note Sn. On appelle permutations les ´el´ements de Sn. Notation : Soit s une permutation de S6 telle que s(1) = 6, s(3) = 5 et s(n) = n sinon. On notera s de la fa¸con suivante : s = 1 2 3 4 5 6 6 2 5 4 3 1 1. Soit E un ensemble `a n ´el´ements. Montrer que SE est isomorphe `a Sn. 2. Quel est le cardinal de Sn ? D´e?nition : on appelle cycle de longueur r > 1 de Sn une permutation c ? Sn telle qu’il existe x1, . . . , xr ? {1, . . . , n} v´eri?ant c(x1) = x2, . . . , c(xr-1) = xr et c(xr) = x1, et telle que c laisse ?xes les autres ´el´ements de {1, . . . , n}. La notation usuelle pour un cycle est c = (x1 . . . xr). 3. Toute permutation se d´ecompose en produit de cycles disjoints. Chercher, sur l’exemple suivant, cette d´ecomposition (qui est unique, `a l’ordre des cycles pr`es) et proposer une m´ethode pour obtenir la d´ecomposition en g´en´eral. 1 2 3 4 5 6 7 8 9 10 11 3 9 5 2 1 6 8 7 10 4 11 D´e?nition : Une transposition est une permutation qui ´echange deux ´el´ements, et laisse tous les autres inchang´es. C’est aussi un cycle de longueur 2. On note t = (i j) la transposition qui ´echange i et j (n est sous-entendu). 4. Montrer que Sn est engendr´e par l’ensemble des transpositions (c’est `a dire qu’une permutation peut ˆetre d´ecompos´ee en produit de transpositions). Th´eor`eme : Si s est une permutation de Sn qui peut s’´ecrire comme produit de transpositions de deux mani`eres di?´erentes s = t1 ? . . . ? tr et s = t 0 1 ? . . . ? t 0 r 0 , alors r et r 0 sont de mˆeme parit´e. 5. Les mouvements des pi`eces du jeu du 14-15 sont des transpositions sur S16, en consid´erant que la case vide est num´erot´ee 16. Comment exprimer la con?guration recherch´ee en termes de transpositions ? 6. Observer les mouvements de la case vide, num´erot´ee 16. Que peut-on dire d’une s´erie de transpositions qui ram`ene 16 `a sa place ? 7. Conclure. Exercice 47 9Math´ematiques pour l’informatique (MI150) 2009-2010 – exercices Si f est un morphisme de (G, ) dans (H, ) et g un morphisme de (H, ) dans (K, ~), montrer que g ? f r´ealise un morphisme de (G, ) dans (K, ~). Exercice 48 Soit f un morphisme de (G, ) dans (H, ). Montrer que f est injectif si et seulement si son noyau est r´eduit `a e (l’´el´ement neutre de ). 7 Logique (1/2) Logique Exercice 49 Pour chacun des ´enonc´es suivants, choisir une lettre de proposition pour repr´esenter les propositions ´el´ementaires et montrer quelle est la forme logique de l’´enonc´e. 1. Ou ce n’est pas Sophia, ou bien elle a beaucoup chang´e. 2. Si c’est Sophia, elle a beaucoup chang´e. 3. Karpov doit sacri?er une tour ou Kasparov fera mat en trois coups. 4. Si Karpov ne sacri?e pas une tour, Kasparov fera mat en trois coups. 5. Ni Paul ni Maurice n’ont r´eussi. 6. Paul et Maurice ne r´eussiront pas tous les deux. 7. Si Maurice r´eussit, Paul r´eussira, sinon aucun des deux ne r´eussira. Exercice 50 Relier les propositions ´equivalentes. 1. ¬(p ? q) 2. ¬(p ? q) 3. p ? (¬q) 4. ¬(p ? q) a. (¬p ? ¬q) b. q ? (¬p) c. (¬p ? ¬q) d. p ? (¬q) Exercice 51 Soient p et s les propositions signi?ant respectivement « Paul aime Sophie » et « Sophie aime Paul ». Pour chacune des formules suivantes, trouver un ´enonc´e en fran¸cais (coh´erent et simple) qui lui corresponde. 1. (¬p ? s) 2. ¬(p ? s) 3. ¬(p ? s) 4. (p ? s) 5. ¬(p ? s) Exercice 52 Un connecteur logique binaire (?, ?, ?) peut-ˆetre vu comme une application de {v, f } 2 vers {v, f }. 1. D´ecrire l’application correspondant au connecteur logique ?. 2. Combien existe-t-il de connecteurs logiques di?´erents ? 3. Ecrire la table de v´erit´e d’un connecteur logique autre que ceux usuels. ´ 10