Home

informatique et mathématiques

Contents

1. 51 A 2 Arithm tique modulaire et applications quatre semaines 51 AD CGngr ences 2 4 n e a es QUE E U ND NAR 51 A 2 2 G n rateurs pseudo al atoires 51 A2 3 Cryptographic siae iiini a BEE E de pra a E E dre al 51 A 3 Ensembles finis deux semaines 51 A 4 Recherche et tri deux semaines 51 AA4 1 Algorithmes de recherche vuis en cours d info 51 A 4 2 Algorithmes detri 52 Conventions et notations g n rales Conventions La notation B signifiera que le terme A est d fini par la formule B Les expressions nouvelles sont crites en italiques au moment de la d finition Noter qu une d finition peut apparaitre au cours d un th or me d un exemple d un exercice etc Exemple 0 0 1 L entier r a qb est appel reste de la division euclidienne de a par b Notations Voici les plus courantes parmi celles qui ne sont pas totalement standardis es et ne sont pas introduites dans le cours Six R l unique entier n tel que n lt x lt n 1 est not x et appel partie enti re de x i sia E R etb E N b gt 2 on note log a E le logarithme en base b de a n Chapitre 1 Arithm tique l mentaire 1 1 Pr lude la division euclidienne dans Z Th or me 1 1 1 Soient a Z etb N Il existe alors un unique couple q r
2. Transitivit Quels que soient a b c Z si a b mod m et sib c mod m alors a c mod m On r sume ces propri t s en disant que la relation de congruence modulo m est une relation d qui valence Cela permet de regrouper les l ments de Z en classes d quivalence galement appel es dans ce cas classes de congruence on ne pr cise pas toujours le module m on dit que a et b sont dans la m me classe s ils sont congrus modulo m Exemple 2 1 3 Dans le cas o m 2 la relation de congruence est la relation a et b ont m me 299 parit Il y a deux classes d quivalence celle des entiers pairs et celle des entiers impairs On notera a mod m ou g la classe de a dans le second cas la notation ne pr cise pas le module m mais on esp re que cela ne causera pas de confusion La principale r gle retenir est la suivante a b lt 4 gt az b mod m 21 Remarque 2 1 4 Ce n est pas n importe quelle relation entre entiers qui permettrait de les regrou per en classes Par exemple aucune des relations a est diff rent de b a est sup rieur b a divise b n est une relation d quivalence et ces relations ne permettent pas un tel regroupement Bien que l ensemble Z des entiers relatifs soit infini il n y a qu un nombre fini de classes de congruence Si m 2 on a vu qu il y en avait deux Si m 3 il y a la classe de 0 not e 0 puis il y a
3. Z x Z tel que gh 1 1 1 1 op LU O lt r lt b I Les entiers q et r sont respectivement appel s quotient et reste de la division euclidienne de a par b Et l on dit parfois que a est le dividende et b le diviseur Preuve On commence par l unicit Si a qb r q b r avec 0 lt r r lt b 1 on a d une part b 1 lt r r lt b 1 autrement dit r r lt b 1 d autre part r r q q b Cela entraine r r 0 seul multiple de b de valeur absolue strictement inf rieure b donc q q 0 Pour prouver l existence on va utiliser un algorithme q 0 Tr Si a gt 0 alors tant que r gt b faire riz r b qg q l fin tant que sinon tant que r lt 0 faire r r b q q 1 fin tant que fin si rendre q r Tout d abord la terminaison de l algorithme est garantie dans le cas o a gt 0 le compteur r d croit strictement chaque tape donc la condition de continuation r gt b finit par tre fausse et dans le cas contraire le compteur r croit strictement chaque tape donc la condition de continuation r lt 0 finit par tre fausse Pour prouver la correction de l algorithme supposons d abord que l on est dans le premier cas a gt 0 On introduit l invariant de boucle a gb retr gt 0 Il est v rifi l initialisation De plus chaque ex cution de l instruction r r
4. addition a a max a a ne cro t pas ind finiment il reste major L criture math matique de cette propri t est co t de l addition a a O max a a 2 L ordre de grandeur du co t n est pas non plus meilleur qu un co t lin aire Plus pr cis ment lorsque la taille des donn es a a est de plus en plus grande le rapport max a a co t de l addition a a ne cro t pas ind finiment il reste major Avec la convention pr c dente on a donc max a a O co t de l addition a a 3 Pour dire que l ordre de grandeur du co t n est ni pire ni meilleur qu un co t lin aire on r sume les deux propri t s pr c dentes par la formule co t de l addition a a max a a Exercice 1 2 11 L entier k max a a tant fix d crire un cas o l addition se fait co t minimum resp co t maximum et calculer pr cis ment ce minimum et ce maximum 1 2 3 Multiplication en base b Multiplication d un nombre par un chiffre Soient a co cb criture propre en base b et c 0 b 1 Dans le cas o c 0 ou 1 le produit ca se calcule sans trop de peine En g n ral on calcule les produits cc et l on doit s occuper des retenues Nous admettrons que le produit de deux chiffres tables de multiplication de l cole pri maire se fait en temps constant il peut tre t
5. aide d int grales En fait ces int grales n apparaitront ici qu en tant qu aires de parties du plan Le principe est le suivant On choisit m assez grand et l on tire deux entiers au hasard a b dans 0 m 1 Le couple x y a m b m d signe donc un point du carr K 0 1 dont laire est 1 Soit maintenant X une partie de K d aire A On peut estimer que la probabilit que le point x y soit dans X est A Si donc on tire N fois de tels couples le nombre de ceux qui tombent dans X ne devrait pas tre trop diff rent de NA Exercice 2 2 10 On suppose un tang circulaire inscrit dans une parcelle carr e autrement dit le cercle et le carr ont m me centre et le diam tre du cercle est gal au c t du carr Des cloches de P ques larguent en grand nombre des oeufs en chocolat sur toute la campagne environnante Montrer que parmi les oeufs tomb s dans la parcelle la proportion de ceux r cup r s par les poissons est d environ x 4 TP 2 2 11 Programmer la mise en oeuvre de ce test 2 Dans la version historique de cet exemple il s agissait de tirs de canon 30 2 3 Cryptographie 2 3 1 Petit pr liminaire th orique Lemme 2 3 1 Soient u et v deux entiers premiers entre eux et soit b un entier multiple de u et de v Alors b est multiple de uv Preuve Par hypoth se il existe des entiers u et v tels que b uu vv D apr s le th or me de B zout
6. fin tant que si x 0 alors rendre y sinon rendre x fin si La terminaison est garantie parce qu chaque tape x y diminue strictement L invariant de boucle qui permet de prouver la correction d coule du lemme chaque tape on a x A y aAb et x y gt 0 En sortie de boucle on a soit x 0 d o x A y y soit y 0 d o x A y x Nous n analyserons pas le co t de cet algorithme qui n est pas tr s facile calculer ni m me noncer On peut montrer que le cas le pire est celui qui est trait dans l exercice suivant Exercice 1 4 2 On rappelle que la suite des nombres de Fibonacci est d finie par les conditions initiales F 0 et F 1 et par la relation de r currence deux pas F1 F F 1 Appliquer l algorithme ci dessus a Fp 1 et b Fn TP 1 4 3 Programmer cet algorithme 1 42 L algorithme classique Dans l algorithme de base si b est beaucoup plus petit que a on remplace a par a b un grand nombre de fois ce qui revient en fait effectuer une division euclidienne de a par b La version classique de l algorithme d Euclide incorpore directement cette division euclidienne x y b tant que y gt 0 q r divEucl x y 18 Yy r fin tant que rendre x A chaque tape y diminue strictement il est remplac par le reste de la division euclidienne par y ce qui garantit la terminaison de l algorithme P
7. tant que c est bien adapt un parcours de tableau 48 2 Nous avons not T p q le sous tableau de T form des l ments d indices allant de p q 3 On peut am liorer l algorithme en vitant les recopies il suffit pour cela de basculer chaque tape le tableau source et le tableau but la premi re phase de fusion se fait de T dans U la deuxi me de U dans T etc en alternant TP 4 2 6 Ecrire et programmer l algorithme avec alternance des tableaux source et but 4 3 Suppl ments facultatifs L arbre des choix et la minoration du co t d un tri par comparaisons Principe non d taill d un algorithme dichotomique et son co t 49 Annexe Rappel de la proposition Jacques Sauloy Universit Paul Sabatier UFR MIG Hiver 2011 Proposition de contenu pour l option Math Info C est con u avec l id e approximative de douze s ances de cours TD de 1h30 et autant de TP mais commen ant un peu plus tard La bibliographie indiqu e ci dessous est pour nous enseignants sauf 4 modules I 1 et II 8 ainsi qu une partie du module I 1 qui concerne les tudiants A propos des calculs de co t Les calculs de co t sont toujours faits dans le cas le pire et le cas le meilleur et en moyenne quand c est possible Le but p dagogique n est pas de montrer que tel algorithme est plus performant mais que l on peut pr voir le comportement d un algorithme au pr
8. 5 J P Ramis et A Warusfel Math matiques Tout en un pour la licence niveau L2 Dunod 2007 53
9. Clog n avec une constante C telle que Clog 500 1 10 secondes A l chelle de Toulouse cela donne un temps d ex cution de Clog 500000 1 10 x log 500000 log 500 1 10 x 2 2 secondes Le temps d ex cution n est pas outrageusement plus long et il nous faudra seulement attendre un peu plus de dix huit mois pour pouvoir utiliser notre algorithme co t logarithmique l chelle de Toulouse avec le m me temps de r ponse qu auparavant Les bons algorithmes profitent mieux de l am lioration du mat riel Reste que notre bon algorithme suppose le tableau tri Le tri d un tableau est lui m me une op ration couteuse Pratiquement il n est pas question de trier un tableau dans lequel on n ef fectuera qu une ou deux recherches mais si les recherches doivent tre fr quentes dictionnaire base de donn ees autant trier le tableau ou la liste ou le fichier selon le cas Exercice 4 1 3 On supose que le tableau est non tri et contient des entiers compris entre 1 et m Il y a donc m possibilit s de tels tableaux que l on consid rera comme quiprobables Combien de comparaisons sont en moyenne n cessaires pour trouver un l ment e 1 m TP 4 1 4 Programmer l algorithme de recherche dichotomique 4 1 2 Recherche du maximum dans un tableau On suppose encore que le type des l ments du tableau est muni d une relation d ordre et l on se propose de reche
10. il existe des entiers k et l tels que ku lv 1 Alors b kub lvb kuvv lvuu uv kv lu Proposition 2 3 2 Soient p et q deux entiers distincts Soient n pq etn p 1 q 1 Soit enfin m gt 2 un entier tel que m 1 mod n Alors VaeZ a a modn Preuve Pour montrer que b a a est multiple de n pq il suffit d apr s le lemme de montrer qu il est multiple de p et multiple de q Les deux nombres p et q jouant un r le sym trique nous ne prouverons que la premi re assertion Soit donc a Z Si a est multiple de p alors a aussi et a a galement On a donc bien a a mod p dans ce cas Si a n est pas multiple de p notant m 1 k p 1 q 1 on d duit du petit th or me de Fermat les congruences aP 1 mod p at P D4 1 1 mod p alt a mod p a a a mod p qui est la congruence voulue Remarque 2 3 3 L entier n n est autre que b n et le th or me d Euler nous assure que si a est premier avec n i e s il n est divisible ni par p ni par q alors a mod n d o l on d duit sans peine que a a mod n On pourrait donc prouver la proposition en partant de l il resterait examiner les cas o a est divisible par p ou q Exercice 2 3 4 Etendre la proposition au cas de r nombres premiers deux deux distincts 31 2 3 2 La m thode RSA La m th
11. l ments il ne sera videmment pas possible d crire un algorithme bas sur des si alors sinon comme celui ci 41 si a lt b alors si b lt c alors rendre a b c sinon si a lt c alors rendre a c b sinon rendre c a b fin si fin si sinon si b lt c alors si a lt c alors rendre b a c sinon rendre b c a fin si sinon rendre c b a fin si fin si Si l on suppose les six ordres a lt b lt c a lt c lt b b lt a lt cb lt c lt a c lt a lt betc lt b lt a quiprobables on voit que le nombre moyen de comparaisons effectu es donc le co t moyen est 2 3 3 3 3 2 6 8 3 2 67 La proc d des tests successifs avec r ponse binaire oui non peut tre mod lis par un arbre de d cision ici a b c a c b a lt b c a b b a c Les noeuds de l arbre repr sentent des tests la branche gauche resp droite correspondant une r ponse positive resp n gative les feuilles repr sentent les r sultats possibles de l algorithme La distance d une feuille la racine qui est le noeud le plus haut en informatique donc ici a lt b est appel e profondeur de cette feuille et elle est dans notre cas gale au co t de l ex cution qui a amen cette feuille On voit bien sur cet arbre pourquoi on n aurait pas pu s en 42 c b a tirer
12. me i AUB 4 gt i Aoui B lt gt x l ouy 14 gt xiy l de sorte que le vecteur de bits associ A U B est le vecteur XY x0 Yy0 lt Xn 1 Yn 1 avec la loi de composition d crite par la table O O 1 Attention Il ne s agit pas de l addition de Z 2Z que nous notons ici et qui est rappel e dans table ci dessous Ol OO 1I 11110 Cette op ration code la diff rence sym trique AAB ANCB U BNCA A B U B A On a not A B A NLB la diff rence de deux ensembles Par exemple CA E A et X 1 1 X 34 Enfin la relation d inclusion A C B entre deux sous ensembles de E peut galement s expri mer en termes des vecteurs de bits X et Y associ s Elle quivaut en effet ANB donc la relation X Y X Elle quivaut d ailleurs galement A U B B donc la relation X Y Y TP 3 2 1 Programmer ces fonctions 3 3 Le produit cart sien Le produit cart sien E x F des ensembles E et F est par d finition l ensemble des couples x y avec x E et y F On a card E x F cardE cardF Si l on a identifi E E et F Ep leur produit cart sien a donc np l ments et l on est conduit rechercher une bijection entre En X Ep et Enp Cela revient donc ordonner les l ments de En x Ep Prenons pour fixer les id es n 3 et p 4 Les 12 l ments de E3 x E4 sont n
13. 2 1 17 Programmer pour tout m la v rification du th or me 2 1 15 recherche de tous les l ments de Z mZ calcul de m et calcul de x pour x Z mZ 2 2 G n rateurs pseudo al atoires L un des p res fondateurs de l informatique John von Neumann a dit Anyone who consi ders arithmetical methods of producing random digits is of course in a state of sin 1 Nous ten terons donc plus modestement de simuler l al atoire Dans un premier paragraphe nous d crirons des moyens de produire de longues suites de nombres vari s et dans un deuxi me paragraphe des moyens de tester si ces suites ont l air al atoire Il y a pour ces deux phases une th orie riche et compliqu e et amusante Nous ne l effleurerons m me pas il n y a ici que quelques recettes faciles mettre en oeuvre Vu de l ext rieur un g n rateur pseudo al atoire est un programme qui rend un nombre chaque fois qu on l appelle Vu de l int rieur ce programme calcule en fait les termes d une suite num rique x Chaque fois qu on l appelle il renvoie un terme d un appel sur l autre il passe au terme suivant Autrement dit entre deux appels le programme garde trace du rang du dernier terme rendu l indice n est une variable r manente et il faut donc savoir programmer de telles variables Le plus souvent il s agit de suites d finies par r currence x 1 f xn Dans ce cas la variable r manen
14. W v v fin tant que rendre x S t La terminaison se prouve comme ci dessus Pour prouver la correction on ajoute l invariant de boucle les galit s x sa tb et y ua vb Exercice 1 4 6 A quoi sert la variable w dans cet algorithme TP 1 4 7 Programmer cet algorithme 19 1 5 Suppl ments facultatifs R solution de l quation ax by c Nombres premiers Le crible d Eratosth ne 20 Chapitre 2 Arithm tique modulaire et applications 2 1 Congruences 2 1 1 L ensemble Z mZ On fixe un entier naturel m gt 2 D finition 2 1 1 Soient a b Z On dit que a est congru b modulo m si b a est multiple de m on crit a b mod m a b modm KEZ b a km Proposition 2 1 2 Pour que les entiers a et b soient congrus modulo m il faut et il suffit que leurs divisions euclidiennes par m donnent le m me reste Preuve Si a qm r et si b q m r alors b a km avec k q q donc a b mod m R ciproquement supposons que a b mod m et soit k Z tel que b a km Si la division euclidienne de a par m s crit a gm r 0 lt r lt m 1 alors b q k m r de sorte que r est le reste de la division euclidienne de b par m La relation de congruence modulo m v rifie les trois propri t s suivantes R flexivit Quel que soit a Z on a a a mod m Sym trie Quels que soient a b Z si a b mod m alors b a mod m
15. b q q 1 sous la condition de continuation r gt b le conserve En effet notant r r les tats avant et apr s de r et g q les tats avant et apr s de q on a r r b et q q 1 donc q b r q 1 b r b q b r d o la conservation de la condition a qb r D autre part r gt b condition d ex cution de la boucle donc r gt 0 A la sortie de la boucle tant que on a r lt b la condition de sortie est la n gation de la condi tion r gt b et en plus l invariant de boucle a qb r et r gt 0 C est exactement quivalent aux conditions nonc es par le th or me a gb ret0 lt r lt b 1 Supposons maintenant que l on est dans le deuxi me cas a gt 0 On introduit l invariant de boucle a qb retr lt b Le raisonnement est alors similaire on laisse au lecteur le plaisir de le r diger On notera par la suite divEuc1 a b le r sultat de la division euclidienne de a par b donc les deux nombres q et r calcul s par l algorithme ci dessus Corollaire 1 1 2 Le quotient de la division euclidienne de a par b est q a b Preuve Puisque r et b sont des entiers la condition r lt b 1 est quivalente la condition r lt b L entier q est alors d fini par la condition 0O lt a qgb lt b 1 0 lt a gb lt b qb lt a lt g 1 b q lt a b lt q 1 d o la conclusion Bien qu un algorithme ait servi tablir l existen
16. co t 4 2 N 23 co t 2 4 3 01234567 co t 8 4 45 co t 2 x 5 4567 co t 4 6 i 67 co t 2 S 7 Co t Le calcul se g n ralise ainsi au cas d un tableau de 2 l ments Les fusions deux deux des 2 sous tableaux de 1 l ments nous donnent 2 sous tableaux tri s de 2 l ments pour un 46 co t total de 247 x 2 2 Les fusions deux deux des 2 sous tableaux tri s de 2 l ments nous donnent 242 sous tableaux tri s de 4 l ments pour un co t total de 2 2 x 4 2 et ainsi de suite Chaque tape fusionnant 2 sous tableaux tri s de 2 l ments a pour co t total 2471 x 21 2 et il y a k telles tapes pour i variant de 0 k amp 1 le co t total est donc k2 Comme n 2 on a bien un co t gal nlog n Remarque 4 2 5 Si l on a eu trier pour commencer un nombre n d l ments qui n est pas une puissance de 2 apr s remplissage on a travaill sur un tableau de 2 l ments avec 271 lt n lt 2 donc k 1 lt log n lt k et le co t total de k2 est compris entre nlog n et 2n 1 log n l ordre de grandeur est bien le m me On dit d un tel algorithme que son co t est quasi lin aire Voici pourquoi Les diff rentes classes de co t que nous avons rencontr es logarithmique lin aire quadratique peuvent tre caract ris es par la mani re dont le co t augmente lorsque l on double la taille des donn es 1 Pour un co t logarith
17. deux calculs soient coh rents il faut tre absolument certain que c heureusement le corollaire ci dessus nous le garantit En effet a d les deux sont gaux x et b b les deux sont gaux y donc en vertu du corollaire a b d b c est dire justement c L addition sur Z mZ est donc bien d finie Son mode d emploi tient principalement dans la r gle suivante qui traduit sa d finition b a b Voici titre d exemple les tables d addition modulo m pour m 2 3 4 5 6 Se 1001 1 21314 5 mere 01112131 4 011 21 3 001112131415 00 12 D LL 01011 213 4 101 00111213 1111213 41510 De 00 12 240 30h 111112131410 OO 1 11121310 2121314 51011 pre 1111210 2e IRE ec thee 21213 41011 1 10 11 112 213 011 3131415 0 112 2210 1 31314 01112 3113101112 414151011213 414101111213 515101121314 L addition dans Z mZ v rifie les propri t s suivantes Commutativit Pour tous x y Z mZ on a x y y x Associativit Pour tous x y z Z mZ on a x y z x y z El ment neutre Pour tout x Z mZ on ax 0 0 x x Sym trique Si x a l l ment x
18. le nombre de tirages soit assez grand Dans notre cas une r gle pratique est N gt 5m TP 2 2 9 Programmer la mise en oeuvre de ce test 29 ie 1 p 5 p 25 p 50 p 75 p 95 p 99 0 00016 0 00393 0 1015 0 4549 1 323 3 841 6 635 0 02010 0 1026 0 5753 1 386 2 773 5 991 9 210 0 1148 0 3518 1 213 2 366 4108 7815 11 34 0 2971 0 7107 1 923 3 357 5 385 9 488 13 28 0 5543 11455 2 675 4351 6 626 1107 15 00 0 8720 1635 3 455 5 348 7 841 1250 1681 1060 4 16m ass eea vousrol 1407 Lisa TE Nas cout ru lon ler 0 2 088 3 325 5 800 8343 1130 16 92 2167 v 10 2558 3 940 6 737 9 342 1255 1831 23 21 Dai 3053 4575 7 584 10 34 1370 1968 2473 Duo 3 571 5 226 8438 11 34 1484 2103 26 22 D 15 5 229 7 261 1104 1434 1825 2500 30 58 D 20 8 260 10 85 15 45 19 34 2385 3141 3757 De 30 1405 1849 2448 2034 3480 4377 5080 D 5o 2971 3476 42 94 49 33 56 33 6750 7615 Ds 50 D Var 4 3 H0 1 Vr ea a 67 ooo 0675 164 2 33 M thode de Monte Carlo l endroit et l envers La m thode de monte Carlo permet de calculer des int grales l aide de nombres al atoires Nous allons l utiliser l envers pour v rifier que des nombres sont al atoires l
19. le tout dans ce cas il s agit donc d additionner les k 1 produits ac bi Bien entendu cette heureuse poque l cole primaire l addition se faisait directement Pour crire un programme il est cependant plus simple de faire des additions successives de deux nombres Voici donc le sch ma de l al gorithme de multiplication en base b de deux nombres SEA c ibi et a pour produire le r sultat S s 0 i 0 tant que i lt k faire s s c i a b fin tant que rendre s Naturellement la multiplication c i a se fait selon l algorithme vu plus haut et la multiplica tion du r sultat par b n en est pas r ellement une il s agit simplement d un d calage avec ajout de chiffres 0 droite On peut d montrer que le co t de la multiplication est lin aire en le produit des tailles co t de la multiplication a a a x a Exercice 1 2 12 Le prouver TP 1 2 13 Programmer la multiplication et l exp rimenter pour v rifier l estimation annonc e du co t 12 1 3 Exponentiation rapide Il s agit de calculer les puissances a n N d un nombre a qui peut tre compliqu r el en criture flottante grand entier Un r flexe fr quent pour calculer a avec une calculette en vitant toute programmation est d crire en supposant bien entendu que a gt 0 a exp nlna Cette m thode est aberrante En effet le calcul des fonctio
20. rimentation sur des tableaux cr s l aide d un g n rateur al atoire 4 2 Algorithmes de tri Il y a d innombrables bonnes raisons pour trier des tableaux des listes des fichiers l une d entre elles tant que cela donne lieu des algorithmes int ressants et dont l analyse est elle m me int ressante Dans ce qui suit on suppose tous les l ments consid r s sont de m me type et que ce type est muni d une relation d ordre 4 2 1 Tri de trois l ments Commen ons par un cas d apparence anodin Soient a b c trois l ments distincts On veut produire un triplet a b c tel que 1 le triplet a b c soit une permutation du triplet a b c 2 onaita lt b lt c Pour cela on s autorise des tests qui sont des comparaisons a lt b a lt c et b lt c Il peut arriver que deux tests cons cutifs soient suffisants pour trancher si a lt b et b lt c sont tous deux vrais alors a b c a b c De m me si a lt b et b lt c sont tous deux faux alors a b c c b a Mais si a lt b est vrai et que b lt c est faux il y a deux possibilit s a b c a c b ou a b c c a b et il faudra un troisi me test a lt c pour trancher Dans tous les cas on devrait s en tirer avec un nombre de comparaisons compris entre deux et trois Pour aller plus loin crivons un algorihme possible 2 Si l on veut trier un nombre ind termin n d
21. G n rateurs lin aires congruentiels 2 22 Quelques tests nonea Drame do mea RAM pare 2 3 Crypiographi si ai m ane mio del es aie Ma net et ar Ms and 4 2 3 1 Petit pr liminaire th orique 2 3 2 La m thod RSA 4 a ace a eian a es a eo 2 1 PS RAR SLR E 2 4 Suppl ments facultatifs 3 Ensembles finis 3 1 Codage par vecteurs de bits 3 2 Calcul bool en sur les sous ensembles 3 31 Le produit cart sien 2 d students destine mnt des fun OS A BR 4 Recherche et tri 36 4 1 Algorithmes de recherche 36 4 1 1 Recherche d un l ment 36 4 1 2 Recherche du maximum dans un tableau 39 4 1 3 Recherche d un duplicata 40 4 2 Algorithmes detri 41 4 2 1 Tri de trois l ments 41 4 2 2 Tri par s lection 43 4 2 3 Tripat fusion 44 4 3 Suppl ments facultatifs 49 A Rappel de la proposition 50 A l Arithm tique l mentaire quatre semaines 50 A 1 1 Ecriture et calcul en base b 50 A 1 2 Exponentiation 50 A 1 3 Algorithme d Euclide
22. PROJET DE SUPPORT DE COURS TD POUR LE MODULE OPTIONNEL INFORMATIQUE ET MATH MATIQUES J Sauloy 13 juin 2011 1 U F R MI G Universit Paul Sabatier 118 route de Narbonne 31062 Toulouse CEDEX 4 Table des mati res 1 Arithm tique l mentaire 1 1 Pr lude la division euclidienne dans Z 1 27 Cal ul en base bi us r a AE a a L an re DE mate aus a 12 11 Ecrit re en base bis set ss rA an ha des A aoa A MUR ER EEE 1 2 2 Addition en baseb 1 2 3 Multiplication en base b 1 3 Exponentiation rapide 1 3 1 M thode naturelle 1 3 2 M thode dichotomique 1 3 3 Questions d optimalit TA T alsorithme d Euclide z eo ida ut Lundi se Los rat aa 14 1 L algorithme de base 14 2 L algorithme classique 14 3 L algorithme am lior 1 5 Suppl ments facultatifs 2 Arithm tique modulaire et applications 2 11 CONPTUENCES Les dpt JM pee NE ne Mine Mt nr Rte de na DL LCensembleZ mZ sites ARR MR GAS AA Ne aa 21 2 L sroupe MZ teenie g eue aa a die sat ave se 2 13 Lanneau Zee dus auras ei Steve de ne aa PA A RS CDS ET UE TT ET SU 2 2 G n rateurs pseudo al atoires 2 2 1
23. Za v rifie x x x x 0 On r sume ces propri t s en disant que l ensemble Z mZ muni de l addition est un groupe commu tatif Pratiquement cela signifie que le calcul avec les classes de congruence ressemble beaucoup au calcul sur les nombres usuels Il y a bien quelques diff rences auxquelles il faut prendre garde on les mentionnera la vol e Revenons sur le sym trique Il est facile de prouver que si a a alors a a On peut donc poser a a Si x 4 l l ment x de la derni re propri t ci dessus est tout simplement x a c est l oppos de x Son existence permet de d finir y x y x c est l unique z tel que x z y On a les r gles pratiques a et b a b 23 2 1 3 Panneau Z mZ x Nous allons d finir une multiplication sur Z mZ selon un processus tr s similaire celui de l addition nous irons donc un peu plus vite Proposition 2 1 10 Soient a a b b Z On suppose a a mod m etb b mod m Alors ab a b mod m Preuve Si a a km et b b Im alors a b ab la kb klm m La relation de congruence est donc compatible avec la multiplication d o Corollaire 2 1 11 Soient a a b b Z On suppose a et b b Alors ab a b Cela permet de d finir la multiplication sur Z mZ de la fa on suivante Soient x et y deux l ments de Z mZ On ch
24. a lt a C est cause de cette forme particuli re de l hypoth se de r currence que l on parle de r currence forte Si l on a une criture a cb cob on en d duit a ab co avec a cb cib On voit donc que co est n cessairement le reste de la division euclidienne de a par b que a est n cessairement le quotient de la division euclidienne de a par b et que cx c1 est n cessaire ment une criture de a en base b Mais d apr s le lemme a lt b 1 lt a D apr s l hypoth se de r currence l criture de a en base b est unique il en est donc de m me de l criture de a L analyse ci dessus nous sugg re l algorithme dont nous d duirons l existence de l criture en base b il consiste en des divisions euclidiennes successives Le r sultat est retourn sous la forme yk Jpi d un tableau c tel que a Xi ocli b xX E r 0 tant que x gt b faire qr divEucl x b c i r x i q Le nl fin tant que ci x k i rendre k c La terminaison est garantie par le fait que x d croit strictement donc que la condition de continua tion x gt b finit par tre fausse La correction repose sur l invariant de boucle a c 0 b cli 1 b xhi Nous laissons au lecteur le soin de prouver la validit de cet invariant et d en d duire la correction de l algorithme Plusieurs remar
25. abul les r sultats sont en m moire ou cabl r alis par du hardware ou r alis par un tout petit programme ad hoc Le r sultat de cette multiplication est inf rieur ou gal b 1 nombre deux chiffres qui s crit gb r avec q lt b 2 puisque b 1 lt b 1 b Attention c est q qui va servir de retenue et r sera le chiffre crire En effet par exemple cco qb r c co c1b do dib avec do r et di ceci q Naturellement on doit encore effectuer une division euclidienne de cc q par b pour calculer le chiffre d et la prochaine retenue mais cc1 q lt b 1 b 2 lt b b et le quotient prochaine retenue sera encore inf rieur ou gal b 2 Voici l algorithme nous notons maintenant s la retenue L algorithme ci dessous de multiplication du nombre EE oclib par le chiffre c a pour r sultat Y _0d i b 11 i 0 s 0 tant que i lt k q r divEucl c c i s b d i r S i qg iss iti fin tant que si s 0 alors 1 k sinon 1 k 1 d l s fin si Le co t de cet algorithme est lin aire en a Multiplication de deux nombres quelconques Pour multiplier les entiers a co cxbf et a ch cb l algorithme appris en primaire multiplications d un nombre par un chiffre avec d calages vers la gauche et additions revient calculer successivement ach puis ac b puis acib etc et additionner
26. actorisation m thodes l mentaires A 3 Ensembles finis deux semaines Bijection entre P A et 0 1 4 Calcul dans Z 2Z de compl mentaire intersection r union diff rence sym trique inclusion Codage du produit de deux ensembles Suppl ments facultatifs envisageables A4 Recherche et tri deux semaines A 4 1 Algorithmes de recherche vuis en cours d info Mod le probabiliste utilis Recherche d un l ment dans un tableau quelconque dans un tableau tri Correction Co t Recherche du maximum Correction Co t Recherche d un duplicata dans un tableau quelconque dans un tableau tri Co t 51 A 4 2 Algorithmes de tri Tri de trois l ments Co t Tri par s lection vu en cours d info Correction Co t Tribulle Correction Co t Lien avec les inversions d une permutation Suppl ments facultatifs envisageables L arbre des choix et la minoration du co t d un tri par comparaisons Principe non d taill d un algorithme dichotomique et son co t 52 Bibliographie 1 T H Cormen C E Leiserson R L Rivest C Stein Introduction l algorithmique Du nod 1994 2 M Demazure Cours d alg bre Primalit divisibilit codes Cassini 1997 3 D E Knuth The Art of Computer programming vol II Seminumerical Algorithms Addison Wesley 1081 4 J P Ramis et A Warusfel Math matiques Tout en un pour la licence niveau L1 Dunod 2006
27. ar ailleurs l invariant de boucle est y gt 0 et x y ab pour la preuve voir l exercice ci dessous qui donne en sortie x x 0 a Ab d o la correction L analyse du co t est difficile mais on peut montrer que le cas le pire est le m me que dans la version de base avec les nombres de Fibonacci Exercice 1 4 4 Si q r diveucl x y montrer que x A y y Ar En d duire la validit de lin variant de boucle ci dessus TP 1 4 5 Programmer cet algorithme 1 43 L algorithme am lior A chaque tape de l algorithme x et y sont des combinaisons lin aires coefficients entiers relatifs de a et b autrement dit on peut crire x sa tb et y ua vb avec s t u v Z C est vident au d part puisqu ils sont initialis s avec les valeurs x a 1 a 0 b et y b 0 a 1 b Cela reste vrai au cours de l ex cution de l algorithme puisque x est remplac par y et que y est remplac par x qy avec q Z Comme la fin de l algorithme on a x a A b on en d duit le th or me de B zout il existe des entiers relatifs s t tels que a Ab sa tb Naturellement on ne peut esp rer trouver s et t naturels puisque le pgcd est plus petit que a et que b L algorithme suivant exploite cette id e pour calculer les coefficients de B zout s f en m me temps que le pgcd E Ou K wx eg q r divEucl x y u u S q u 5 t q v t w X y a Eyr W W
28. aturellement rang s en un tableau rectangulaire une matrice Il y a deux parcours naturels de cette matrice par lignes ou par colonnes Le premier fournit Pordre suivant 0 0 0 1 0 2 0 3 1 0 1 1 1 2 1 3 2 0 2 1 2 2 2 3 Si l on veut num roter ces couples de 0 11 on voit que le couple i j re oit le num ro 4i j Le second parcours fournit l ordre suivant 0 0 1 0 2 0 0 1 1 1 2 1 0 2 1 2 2 2 0 3 1 3 2 3 Si l on veut num roter ces couples de 0 11 on voit que le couple i j re oit le num ro i 3j Th or me 3 3 1 i L application i j gt pi j r alise une bijection du produit cart sien E x Ep sur Enp ii L application i j gt i nj r alise une bijection du produit cart sien E x E sur Enp Preuve Dans les deux cas il suffit d exhiber l application r ciproque Dans le premier cas c est k gt i j ou i est le quotient et j le reste de la division euclidienne de k par p dans le second cas c est k gt i j ou j est le quotient et i le reste de la division euclidienne de k par n TP 3 3 2 Programmer ce codage Exercice 3 3 3 L ensemble des parties de E a 2 l ments il est donc en bijection avec Em Expliciter un algorithme qui permette de convertir un l ment de Ez 0 1 2 1 en un vecteur de n bits 35 Chapitre 4 Recherche et tri 4 1 Algorithmes de recherc
29. aux tant que non trouv et i lt j faire k i j div 2 si tab k e alors trouv vrai sinon si tab k lt e alors i k l sinon J kal fin si fin si fin tant que si trouv alors rendre i sinon ECHEC fin si On a fait appel la fonction floor qui calcule la partie enti re d un r el A chaque tape la longueur j i 1 de l intervalle de recherche est au moins divis e par deux puisque sa borne gauche passe droite de son centre ou sa borne droite gauche de son centre Le nombre total d tapes est donc au pire log n Le co t le pire d une recherche avec succ s ou avec chec est donc major par log n Nous ne calculerons pas le co t moyen mais on peut d montrer qu il est proche du co t le pire Quelques conclusions Nous allons d abord discuter d l inter t davoir un co t logarithmique plut t que lin aire A une poque ou la puissance des mat riels cro t de mani re si spectaculaire cela vaut il la peine de se soucier de la qualit des algorithmes Pour le voir nous prendrons comme hypoth se heuristique la loi de Moore une loi socio conomico technique qui dit que la puissance des mat riels informatiques est multipli e par deux tous les dix huit mois Remarque 4 1 2 La loi de Moore n a rien d une loi scientifique c est au mieux une constata tion empirique voir une discussion l dessus dans l article de Wikipedia consultab
30. avec deux comparaisons dans tous les cas Cela signifierait en effet que toutes les feuilles auraient une profondeur inf rieure ou gale 2 et l arbre ne pourrait alors avoir que 4 feuilles Mais cela ne suffirait pas puisque l on sait d avance qu il y a 6 ordres possibles donc qu il faut au moins 6 feuilles Co t optimal d un tri par comparaisons Ce raisonnement se g n ralise ainsi Supposons que l on veuille trier n l ments en effectuant un certain nombre de comparaisons entre eux L arbre de d cision correspondant doit avoir au moins n feuilles puisque l on doit pr voir au moins n r sultats diff rents possibles Par ailleurs si l on veut effectuer au plus k comparaisons dans tous les cas les feuilles de l arbre ont toutes une profondeur inf rieure ou gale k et l on voit facilement avec de petits dessins de tels arbres qu il y a alors au plus 2 feuilles En r sum si l on veut trier n l ments en effectuant dans tous les cas au plus k raisons on doit avoir 2 gt n k gt logn Th or me 4 2 1 Le nombre de comparaisons n cessaires pour trier n l ments est dans le pire des cas au moins gal log n On a de plus logan nlog n La deuxi me assertion est justifi e par l exercice ci dessous On peut d montrer une estimation analogue pour le co t moyen d un tel algorithme Comme nous le verrons plus loin ces ordres de grandeur en nlog n peuvent effective
31. b avec l addition de Z mZ Cas d un module premier Supposons m premier Puisque l on a exclu le cas o a 1 l l ment 1 a est inversible dans Z mZ et l on va pouvoir appliquer la m thode vue en terminale pour les suites arithm tico g om triques On cherche un point fixe u u au b T a u b u b f a o l on note x l inverse d un l ment inversible de Z mZ La relation de r currence devient alors Xn 1 aXn b 4 gt Xn41 U a x U et l on en d duit x u a xo u donc Yn E N xn a x o u u Attention la notation a d signe ici le produit de n facteurs gaux a avec la multiplication de Z mZ Finalement un d calage pr s de valeur u tout se passe comme si la suite tait g om trique Pour la suite de ce paragraphe nous supposons donc que b u 0 et donc que x a xo On prendra videmment xo 0 sinon la suite serait constante et n aurait pas du tout l air al atoire Finalement on est donc conduit examiner la suite des a x Pour savoir si elle a lair al atoire nous d crirons plus loin des tests empiriques On peut d j se demander si elle ne boucle pas trop vite En effet le petit th or me de Fermat nous dit que a T et donc que si n q m 1 r on a a a la a d o x x cela signifie que la suite se reproduit avec une p riode m 1 Mais ce n est pas n cessairemen
32. ce du quotient et du reste nous ne pr ten dons pas que les syst mes de calcul existants comme par exemple Maple utilisent r ellement cet algorithme pour effectuer une division euclidienne Dans la suite de ce chapitre nous lude rons cette question et admettrons l existence d une fonction primitive qui prend en argument le couple a b et donne comme r sultat le couple q r mode d emploi q r diveucl a b Nous admettrons de plus que ce calcul s effectue en temps constant Exercice 1 1 3 On appelle mantisse de x R le r el M x x x i Montrer que c est l unique r el amp 0 1 tel que x a Z ii Exprimer le reste de la division euclidienne de a par b en fonction de M a b TP 1 1 4 Programmer la fonction diveucl en utilisant l algorithme d crit dans la preuve du th o r me 1 2 Calcul en base b Dans toute cette section la base b est un entier naturel fix tel que b gt 2 Le cas b 1 correspond l criture en b tons 1 mammouth 1 b ton Nous ne traiterons que le cas des entiers naturels donc ni les entiers n gatifs ni les nombres non entiers 1 2 1 Ecriture en base b Rappelons le principe de l criture d cimale le nombre not 2011 est gal 2 10 0 10 1 10 1 10 Le m me nombre admet l criture binaire 11111011011 ce qui signifie 1 210 1 2 1 28 1 27 1 26 0 25 1 24 1 23 0 22 1 2 1 20 Si l on ne veut pas confondre cet
33. d coule en prenant i k et n px Et maintenant pour le r sultat qui nous int resse on renverse la conclusion 16 Corollaire 1 3 10 Le nombre de multiplications n cessaires pour calculer a est sup rieur ou gal log n Preuve D apr s la proposition ce nombre k v rifie n lt 2 donc k gt log n Exercice 1 3 11 Pour quelles valeurs de n lt 24 le co t c n par la m thode dichotomique peut il tre am lior 1 4 L algorithme d Euclide Le but est de calculer le pgcd plus grand commun diviseur de deux entiers naturels a et b Rappelons que si l on note D a m E N m divise a l ensemble des diviseurs de a alors le pgcd de a et b est d fini comme le plus grand l ment de D a N D b Cette d finition ne tombe en d faut que si a b 0 car alors D a D b N et il n y a pas de plus grand l ment dans D a N D b nous conviendrons que le pgcd de 0 et 0 est 0 Nous noterons a b le pgcd de a et b On a les r gles a b b aeta 0 a Si a et b sont tous deux non nuls on peut les d composer en facteurs premiers pl Fk a pi Pko EENES Sk b p p o l on a mis tous les facteurs premiers qui apparaissent dans a ou dans b quitte poser r 0 si pi ne divise que b resp s 0 si p ne divise que a On a alors min r1 51 min r 5k Malheureusement cette m thode est impraticable car il n existe aucun algorithme raisonnable men
34. e tab j le maximum de tab 1 tab i permuter tab i et tab j ii i 1 fin tant que Noter que l on n a rien faire pour i 1 lorsque les n 1 derniers l ments sont en place le premier l est galement La recherche du maximum de T 1 T i co te i 1 comparaisons le nombre total de comparaisons effectu est donc dans tous les cas gal n 1 n 2 1 n n 1 2 c est donc un co t quadratique On peut cependant choisir d autres crit res Par exemple le nombre total de mises jour de l indice lors des recherches de maximum mais ce nombre est difficile analyser Un autre crit re pertinent est le nombre d changes de T i avec T j En effet si les l ments du tableau sont volumineux ces changes peuvent prendre un temps non n gligeable Dans notre algorithme il y a dans tous les cas n 1 changes m me si par exemple le tableau est d j tri et que l on a chaque fois i j On peut am liorer l algorithme sur ce point et n effectuer l change que s il est n cessaire i n tant que i gt 1 faire tab j le maximum de tab 1 tab i si i lt gt j alors permuter tab i et tab j fin si Mere 1 fin tant que Le nombre minimum d changes est alors O tableau d j tri Le nombre maximum est n 1 il ne correspond d ailleurs pas un tableau en ordre inverse n 1 mais par exemple l ordre 2 3 n 1 O
35. e est appel e exponentiation dichotomique ou indienne ou chinoise ou babylonienne On la comprend mieux sur un exemple Le calcul de a qui devrait co ter 7 multiplications peut se r aliser en 3 multiplications comme suit X1 54X4 X2 X XX X3 X2 X X2 13 Remarque 1 3 3 Il y a un petit prix payer pour ce gain de performance l utilisation de va riables pour d signer les calculs interm diaires cache en r alit l utilisation d un peu de m moire pour stocker ces r sultats Naturellement l exposant 8 tant pair la puissance a a4 est un carr La situation n est pas toujours aussi favorable Par exemple le calcul de a qui aurait co t 6 multiplications par la m thode naturelle peut se r aliser en 4 multiplications donc plus que pour a La s quence est la suivante X1 54X4 X2 5X1 X4 X3 X2XX2 X4 X3 X Il a fallu compl ter le carr x a en le multipliant par a cause de l exposant impair 3 puis compl ter le carr x3 af en le multipliant par a cause de l exposant impair 7 Cela explique le relatif surco t On s attend en g n ral r aliser des gains de performance en accord avec le slogan plus il y a d exposants pairs plus on y gagne Nous allons tout de m me v rifier que la m thode est efficace dans tous les cas autrement dit que l on a une performance asymptotique infiniment meilleure que par la m thode naturelle ces termes
36. e qui n est pas mal mais on le trouvera suspect Nous donnons ici sans justification autre que l intuition quelques tests faciles comprendre et mettre en oeuvre 28 Tests empiriques de fr quence La premi re v rification inspir e de l exemple ci dessus est celle des fr quences dans une longue s quence de tirages successifs chacune des valeurs possibles 0 m 1 devrait appa raitre avec une fr quence proche de 1 m Le test consiste donc tirer N valeurs N tant grand compter pour chaque i 0 m 1 le nombre N de fois que l on a tir i puis v rifier qu au cun des nombres N N n est trop diff rent de 1 m Par exemple on peut calculer le maximum des valeurs absolues N N 1 m et d clarer l chec du test si ce maximum est sup rieur une certaine valeur limite amp fix e d avance Au lieu de calculer le maximum des N N 1 m on peut galement calculer leur somme Le test du chi deux d crit plus loin propose une approche plus rigoureuse Un autre test plus subtil repose sur l id e que chaque terme de la suite devrait sembler in d pendant du pr c dent Pour le v rifier on tirerait 2N fois d o une suite x0 x2n 1 puis on examinerait chacun des N couples x2 x2 1 pour k 0 N 1 et l on compterait pour tout couple i j 0 m 1 le nombre N de fois qu il apparait parmi les x2k x2k 1 Ce nombre ne devrait
37. e ses valeurs x i i 0 n 1 Autrement dit une partie A de E est repr sent e par un vecteur de bits bit vector X x0 Xn 1 0 1 avec les r gles xi l lt gt i A xi 0 4 gt igA Par exemple l ensemble vide 0 est cod par le vecteur nul 0 0 0 1 et l ensemble plein En est cod par le vecteur 1 1 0 1 TP 3 1 2 R aliser ce codage et programmer la fonction associ e de test d appartenance 33 Exercice 3 1 3 Montrer que l on peut coder les parties finies de N l aide de la bijection A Z 2 de l ensemble P N des parties finies de N sur l ensemble N neA 3 2 Calcul bool en sur les sous ensembles Le codage d crit ci dessus permet d arithm tiser le calcul sur les sous ensembles de E Ainsi si X x0 xn 1 0 1 est le vecteur de bits associ au sous ensemble A de E le vecteur de bits associ au compl mentaire CA de A dans E est X 3 0 1 o l on a pos 0 1 et 1 0 Soient maintenant X x0 xn 1 0 1 et Y y0 7 1 0 1 les vecteurs de bits respectivement associ s deux sous ensembles A et B de E Alors iEANB iEeAetieB x lety I xyi l de sorte que le vecteur de bits associ A NB est le vecteur X Y x0 Y0 Xn 1 Yn 1 avec la loi de composition d crite par la table O O O De m
38. e son ex cution sur des tableaux plus petits Pour ne pas se retrouver dans un cercle vicieux il faut donc que le tri de tr s petits tableaux soit direct et ne fasse pas appel au tri de tableaux encore plus petits C est bien entendu le cas de tableaux un l ment dont le tri est une op ration vide Pratiquement nous ne d crirons pas l algorithme sous sa forme r cursive mais sous la forme d une it ration directe d abord les tableaux un l ment puis les tableaux deux l ments puis quatre l ments etc La programmation r cursive c est pour plus tard 2 On doit disposer d une m thode pour fusionner deux tableaux tri s de huit l ments en un tableau tri de seize l ments Nous verrons qu il existe en effet une telle m thode ef ficace qui de mani re g n rale fusionne deux tableaux tri s ayant respectivement et m l ments en un tableau tri de n m l ments Nous prouverons que le co t d une telle fusion est dans le pire des cas gal n ceci que l on prenne comme unit s de compte les comparaisons ou les affectations d l ments du tableau 3 Pour que des divisions successives par deux des tailles de tableaux nous ram nent des tableaux de taille un il faut que la taille de d part soit une puissance de deux seize dans notre exemple Si l on part d un tableau ayant par exemple douze l ments il suffira de le compl ter par quatre l ments in
39. es o k 1 max a a En premi re approche on a a a co ch cx c bf C est facile crire malheureusement ce n est en g n ral pas une criture en base b puisque l on peut avoir c c gt b Il y a m me un peu plus d une chance sur deux que cela se produise pour un i donn donc si k est grand il est extr mement probable que cela se produise pour un i au moins Dans tous les cas c c lt 2b 2 Supposons par exemple que b lt co c lt 2b 2 On crira alors co cp ci c b co c b ci ci 1 b a a co ch b c1 c 1 b ck c b Le probl me se repose alors avec c1 c 1 ce nombre est a priori compris entre 0 et 2b 1 mais s il est sup rieur ou gal b on doit recommencer la m me manoeuvre Le lecteur aura reconnu le probl me de la retenue Pour finir on obtient l algorithme appris l cole primaire d addition en base b de deux nombres X c i b et X_ c ilb pour produire le r sultat Y _ d i bi 1 Fonction lin aire f x ax fonction affine f x ox B i 0 tant que i lt k d i i CE A en FES si d i gt b alors d i i dfi b sinon r 0 fin si i 1 fin tant que 0 alors k si r sinon L k d l r fin si rendre d L entier l apparu la fin est le nombre de chiffres de la somme donc k ou k 1 selon qu il y avait ou non une reten
40. es constantes Comme d j indiqu nous supposons que le co t d une division euclidienne est constant Il est raisonnable de supposer que toutes les autres instructions crites dans l algorithme s effectuent galement en temps constant il y a des additions des affectations etc Le temps total d ex cution est donc de la forme Ak B o k est l entier qui apparait dans l criture de a en effet le nombre d ex cutions de la boucle interne c est dire le nombre de fois que l on aura x gt b est gal au nombre de fois o l on calcule un chiffre c en ne comptant pas le dernier chiffre c qui est calcul la fin Le co t de l algorithme de codage en base b est donc une fonction affine de la taille de l entier cod en effet avec les m mes notations a k 1 d o Ak B A a B o B B A Pour des entiers de grande taille k c est presque la m me chose que si l on avait un co t de la forme a et il est d usage de dire plus simplement que le co t du codage est une fonction lin aire de la taille 1 2 2 Addition en base b Soient a co cybf et a ch cbr les critures propres des deux nombres additionner Supposons par exemple que k lt k On peut alors prolonger l criture de a en une criture impropre en posant ap 0 a 0 d o a co c b Cela permet dans tous les cas d additionner deux nombres crits avec k 1 chiffr
41. est gal H 1 5 n ces nombres forment la s rie harmonique Exemple 4 1 5 Si n 1 le seul rangement possible donne un co t de 1 Hi Si n 2 les deux rangements possibles donnent respectivement des co ts de 1 et 2 d o un co t moyen de 3 2 Hh Pour le cas n 3 on peut aussi bien supposer que les l ments du tableau sont 1 2 et 3 pris dans un certain ordre Il y a six permutations possibles 123 132 213 231 312 et 321 Les co ts correspondants sont respectivement 3 2 2 2 1 et 1 d o un co t moyen de 11 6 B3 On d montrera en cours d analyse de L1 que H Inn ce qui implique que le co t de l algo rithme ci dessus est logarithmique i 1 dt i 1 dt i 1 dt Exercice 4 1 6 En comparant f F f et f Ai d montrer l encadrement i i i i i 1 1 lt In i 1 ln i lt IS n i 1 In i lt En d duire par r currence l encadrement In n 1 lt H lt 1 1Inn puis l quivalence H Inn 4 1 3 Recherche d un duplicata Pour commencer on ne fait aucune hypoth se sur le type des l ments du tableau Le probl me est de d terminer s il en existe des indices distincts j tels que T i T j La seule m thode envisageable est a priori d effectuer toutes les comparaisons de couples T i T j pour 1 lt i lt j lt n ce qui repr sente n n 1 2 comparaisons Ce nombre correspond au cas le pire pas de 40 duplicata il faut
42. et j lt b m faire si tabl i lt tab2 j alors res k tabllil i i l k k l sinon res k tab2 j j j 1l k k fin_si fin tant que tant que i lt a l faire res k tablli i itl k k l fin tant que tant que j lt b m faire res k tab2 j j j t1 k k l fin tant que Sur les deux derni res boucles l une est vide car la condition de sortie de la premi re boucle est que l un des deux tableaux T U ait t enti rement parcouru Le nombre total d affectations de V k est exactement n le nombre de comparaisons est major par n dans tous les cas L algorithme de tri L algorithme de fusion ci dessus ne peut tre effectu sur place autrement dit si l on fusionne par exemple T 0 T 1 avec T 2 T 3 le r sultat ne peut tre directement crit dans T 0 T 1 7 2 T 3 La mani re la plus vidente de l exploiter est d crire les r sultats dans un tableau U puis de recopier U dans T et ceci chaque tape Voici le sch ma de l algorithme complet o l on note tab et aux les deux tableaux utilis s pour i dans 0 k 1 faire pour j dans 0 24 faire fusionner tab 2 2 2j 1 2 1 et tab 2j 1 2 23 2 2 1 dans aux 23 2 2j 2 2i 1 fin pour recopier aux dans tab fin pour Quelques remarques finales 1 Pour la premi re fois nous utilisons une boucle pour au lieu d une boucle
43. et m sont premiers entre eux On note Z mZ l ensemble de ces l ments et m card Z mZ le nombre de ces l ments La fonction est l indicatrice d Euler En examinant les lignes ou les colonnes o figure 1 les tables de multiplication on trouve par exemple Z 2Z 1 d o 2 1 Z 3Z 1 2 d o 3 2 Z 4Z 1 3 d o 4 2 Z 5Z 1 2 3 4 d o 6 5 4 et Z 6Z 1 5 d o 6 2 Si m est premier il est clair que Z mZ 1 m 1 d o m m I1 Le th or me qui suit est d une importance cruciale dans les deux applications que nous avons en vue g n rateurs pseudo al atoires voir la section 2 2 et m thode RSA de cryptographie cl publique voir la section 2 3 Th or me 2 1 15 i Pour tout x Z mZ on a x Gi Pour tout a Z tel que a Am 1 on a al 1 mod m iii Si m est premier et si a Z n est pas multiple de m alors a 1 mod m Preuve i C est un cas particulier du th or me de Lagrange qui sera d montr dans le cours d alg bre de L2 ii Ce th or me d Euler est simplement la traduction de 1 en termes de congruences Gii Ce cas particulier de ii est le petit th or me de Fermat r Exercice 2 1 16 Si m p o p est premier alors m p p Si m pq o p et q sont premiers distincts alors m p 1 q4 1 TP
44. he Nous allons examiner trois probl mes naturels de recherche dans un tableau dont les solutions illustrent diff rentes classes de co ts des algorithmes influence des structures de donn es utilis es l int r t de certaines m thodes dichotomiques associ es au paradigme diviser pour r gner De plus les probl mes de recherche motivent l tude des algorithmes de tri qui seront voqu s la section suivante 4 1 1 Recherche d un l ment On se donne un tableau T 1 T n d l ments d un type arbitraire non sp cifi L exemple canonique est celui d un tableau de chaines de caract res On cherche un l ment particulier e dans le tableau T autrement dit s il en existe un indice i 1 n tel que T i e Cas d un tableau arbitraire L algorithme de base est alors le suivant le tableau est not tab 1 1 tant que tabli lt gt e et i lt n faire i i 1 fin tant que si i lt n alors rendre i sinon ECHEC fin si Pour estimer le co t de cet algorithme nous prendrons pour crit re le nombre de comparaisons effectu es de T i avec e Si l l ment e recherch n est pas dans le tableau ce nombre est n Si l l ment e recherch est dans le tableau ce nombre est compris entre 1 et n Le meilleur des cas 36 est celui o T 1 e qui donne un co t de 1 Le pire des cas est celui o T n e et T i e pou
45. inois Tests de primalit factorisation m thodes l mentaires 32 Chapitre 3 Ensembles finis 3 1 Codage par vecteurs de bits Th or me 3 1 1 Soit E un ensemble quelconque A tout sous ensemble A de E on associe sa fonction caract ristique galement appel e indicatrice 4 A 0 1 qui est d finie par 1sixE VxeE x xala e sixgA Alors l application A gt 4 r alise une bijection de l ensemble P E des parties de E sur l en semble 0 1 des applications de E dans 0 1 Preuve Il suffit de d finir la bijection r ciproque c est dire pour un l ment arbitraire de l en semble d arriv e de d terminer son unique ant c dent Soit donc E 0 1 une application quelconque autrement dit un l ment de 0 1 Posons A x E O x 1 C est un sous ensemble de E et c est bien l unique sous ensemble tel que 4 donc l unique ant c dent de 6 par l application 4 Ce th or me fournit une m thode pour coder les sous ensemble d un ensemble fini quelconque E Pour cela notant n card E le nombre d l ments de E on commence par num roter ces l ments de 0 n 1 Cela revient identifier E avec l ensemble particulier E 0 n 1 Dor navant nous travaillerons directement sur l ensemble Une application 6 En 0 1 est alors totalement sp cifi e par le n uplet x0 xn 1 0 1 d
46. ix d un raisonnement math matique Il faudra ins rer une discussion des classes logarithmique lin aire quasi lin aire polynomiale exponentielle et peut tre quelques exp riences en TP pour observer les comportements correspondants A 1 Arithm tique l mentaire quatre semaines A 1 1 Ecriture et calcul en base b Division euclidienne rappel Ecriture en base b Algorithme de conversion Taille d un entier Addition et multiplication en base b Co t A 1 2 Exponentiation Exponentiation normale dichotomique optimale aberrante Correction Co t simple co t affin 1 Version r vis e apr s la r union du 31 01 2011 50 A 1 3 Algorithme d Euclide L algorithme d Euclide de calcul du pgcd Correction Co t L algorithme d Euclide tendu avec calcul des coefficients de B zout Co t Suppl ments facultatifs envisageables R solution de l quation ax by c Nombres premiers Le crible d Eratosth ne A 2 Arithm tique modulaire et applications quatre semaines A 2 1 Congruences Calcul modulo m addition multiplication A 2 2 G n rateurs pseudo al atoires G n rateur pseudo al atoire lin aire congruentiel A 2 3 Cryptographie Puissances Logarithme discret RSA Suppl ments facultatifs envisageables Recherche de la p riode m thode de Brent R solution de l quation ax b mod m R solution simultan e lemme chinois Tests de primalit f
47. la classe de 1 not e l puis il y a celle de 2 not e 2 puis celle de 3 not e 3 mais c est la m me que celle de 0 puisque 3 0 mod 3 De m me on constate que 4 1 que 5 2 etc Si l on part gauche de 0 rien de neuf 1 2 puisque 1 2 mod 3 En fin de compte il n y a que trois classes 0 1 et 2 Il y en a bien trois car par exemple 0 1 puisque 1 0 mod 3 Proposition 2 1 5 i Pour tout a Z il existe un unique b 0 m 1 tel que b ii Il y a exactement m classes de congruence modulo m qui sont 0 1 m 1 Preuve i L unique b dont on affirme l existence est tout simplement le reste de la division eu clidienne de a par m ii C est une cons quence imm diate de i On notera Z mZ l ensemble des classes de congruence modulo m On a donc Z mZ 0 1 m 1 Par cons quent card Z mZ m Pratiquement si l on veut travailler avec un l ment x de Z mZ c est dire avec une classe de congruence modulo m on choisit un entier a Z dont x est la classe x 4 et l on travaille avec a voir un peu plus bas l exemple de l addition des classes de congruence On dit que a est un repr sentant de la classe x Exemple 2 1 6 On a Z 2Z 0 1 Les entiers 8 et 39 sont des repr sentants respectifs de ces deux classes On a Z 3Z 0 1 2 Les entiers 39 et 8 sont des repr sentants respectifs des deu
48. le sur l URL http fr wikipedia org wiki Loi_ de Moore On se place dans la situation suivante nous avons un ordinateur et un programme qui nous permettent de retrouver un nom dans une liste de cinq cents l ments en un dixi me de secondes Il est donc bien adapt la gestion de l ensemble des tudiants en informatique de l UPS par 38 exemple Pouvons nous utiliser le m me ordinateur et le m me programme dans le cas d une liste de cinq cents mille l ments population de la ville de Toulouse par exemple Combien de temps faudra t il alors pour trouver un l ment dans cette liste Avec notre premier algorithme co t lin aire le temps d ex cution est proportionnel la taille de la liste du tableau Il faut donc mille fois plus de temps soit cent secondes ce n est pas viable Cette d gradation peut elle tre compens e par les progr s de la technologie Quand ces progr s nous permettront ils de travailler sur une telle grosse liste mais avec le temps de r ponse actuel Nous interpr terons la loi de Moore comme nous disant que les machines vont deux fois plus vite tous les dix huit mois donc 21 1024 fois plus vite au bout de 180 mois Il nous faudra donc attendre quinze ans pour pouvoir utiliser notre algorithme co t lin aire l chelle de Toulouse avec le m me temps de r ponse qu auparavant Avec notre second algorithme co t logarithmique le temps d ex cution est de la forme
49. lleurs une approximation de la r alit puisqu il faut bien indiquer quelque part que l on est au bout de l criture de cet entier Remarque 1 2 5 Une autre possibilit serait que tous les entiers soient cod s dans des espaces de m me taille donc en criture impropre avec le m me nombre total de chiffres C est ce qui se pratique quand les entiers manipul s ne sont pas trop grands Dans cette section nous suppo serons que les entiers peuvent tre tr s grands et que la taille de leur codage doit tre estim e correctement Nous supposerons galement que tous les chiffres de l criture en base b d un entier occupent des espaces de m mes tailles notons K l espace occup par un chiffre disons que c est un nombre de bits Si a co cbt avec cg Z 0 l espace total occup par a est k 1 K Proposition 1 2 6 Le nombre de chiffres de l criture de a en base b est gal 1 log a Preuve Ce nombre de chiffres est k 1 or d apr s le lemme 1 2 1 na L Heder 1 peace chti k Inb nb ji Pour ne pas avoir tenir compte de l unit de taille m moire ici les K bits occup s par chaque chiffre nous ne prendrons en compte dans l estimation de la taille de a que le nombre de chiffres D finition 1 2 7 La taille d un entier a N sous entendu crit en base b est le nombre de ses chiffres 1 log a On la notera a donc sans pr ciser la base b relativeme
50. ment tre r alis s par de bons algorithmes Exercice 4 2 2 D montrer l encadrement 1 nlnn lt n 1 in n 1 ninn lt 1 1In n 1 En d duire par currence un encadrement de In1 In2 1Inn Inn puis une preuve de la deuxi me assertion du th or me 4 2 2 Tri par s lection On consid re un tableau T 1 T n Le principe de l algorithme qui va suivre est le suivant on d termine le plus grand l ment T j du tableau et l on permute T j avec T n qui est alors en place d finitivement puis on d termine le plus grand l ment du sous tableau T 1 T n 1 que l on permute avec T n 1 etc L invariant de boucle qui permet de d montrer la correction de l algorithme est donc le suivant apr s k tapes les k derniers l ments du tableau sont en place autrement dit ce sont les k plus grands et ils sont tri s Il s agit videmment de la boucle externe la boucle interne visant chaque fois d terminer le maximum des n k premiers l ments 3 Il existe des m thodes de tri radicalement diff rentes qui ne reposent pas sur une s quence de comparaisons ni le raisonnement qui suit ni sa conclusion ne s appliquent ces m thodes 4 On rappelle que n d signe la factorielle de n c est dire le produit 1 x 2 x x n des n premiers entiers non nuls et que le nombre de permutations de n l ments distincts est gal n 43 i n tant que i gt 1 fair
51. mique C n alogn on a C 2n alog 2n alogn alog2 C n alog2 donc le co t augmente d une constante lorsque l on double la taille des donn es 2 Pour un co t lin aire C n an on a C 2n a 2n 2an 2C n donc le co t double lorsque l on double la taille des donn es 3 Pour un co t logarithmique C n n on a C 2n 2n 4n 4C n donc le co t quadruple lorsque l on double la taille des donn es Pour un algorithme tel que C n anlogn on a C 2n 2anlog 2n 2anlogn 2anlog2 2C n cez 2C n n La mani re dont le co t augmente lorsque l on double la taille des donn es est donc asymptoti quement la m me que pour un algorithme de co t lin aire Pour de grandes donn es cela revient donc pratiquement au m me L algorithme de fusion Cet algorithme est destin servir de proc dure l int rieur d un autre algorithme nous utiliserons donc des notations un peu plus g n rales pour les indices et les noms des tableaux On suppose donn s un tableau tri de l ments T a 1 T a 4 et un tableau tri de m l ments U b 1 U b m L algorithme les fusionne et remplit un tableau de n m l ments V c 1 V c n qui sera tri nous notons tab1 et tab2 les tableaux fusionner tab celui qui re oit le r sultat de la fusion 47 i a 1 j b 1 kresa 4 tant que i lt a l
52. n peut prouver que le nombre moyen d changes est n H L am lioration n apporte donc pas vraiment grand chose puisque H Inn est n gligeable devant n Exercice 4 2 3 Combien y a t il d changes dans le cas de l ordre inverse n 17 TP 4 2 4 Programmer la version am lior e de l algorithme 4 2 3 Tri par fusion Nous allons d crire un algorithme de tri dichotomique Le nombre de comparaisons effectu es par cet algorithme dans le cas d un tableau de n l ments est de l ordre de nlog n c est donc l ordre de grandeur optimal Cela ne signifie d ailleurs pas pour autant que l algorithme lui m me est optimal mais les autres crit res pertinents pour en juger difficult de mise en oeuvre co t des op rations l mentaires ad quation de la structure de donn es et la comparaison pratique des diff rents algorithmes en situation rel vent du cours d informatique Description informelle Le principe est le suivant Pour trier un tableau de seize l ments par exemple on coupe celui ci en deux sous tableaux de huit l ments on trie chacun de ces sous tableaux puis on fusionne ces derniers Le tri des tableaux de huit l ments a t effectu de la m me mani re on les a coup s en tableaux de quatre l ments que l on a tri s puis fusionn etc Cette description appelle plusieurs remarques 1 L algorithme est r cursif son ex cution sur un gros tableau pr suppos
53. ns dites transcendantes comme l exponentielle et le logarithme ainsi que les fonctions trigonom triques fait appel des sous programmes qui effectuent un grand nombre de calculs et qui dans tous les cas rendent un r sultat approch Le lecteur est vivement encourag calculer 3 par cette m thode et tenter d estimer le temps de calcul et la pr cision du r sultat TP 1 3 1 Faire l exp rience calculer un million de fois 3 x 3 x 3 et exp 31n3 1 3 1 M thode naturelle Il s agit bien entendu de poser on suppose ici n gt 2 a ax xa o il y a n facteurs et donc n 1 symboles d op rations x Le calcul repr sente donc n 1 multiplications En admettant que le co t de ces multiplications est constant on en d duit co t du calcul de a O n Naturellement l unit de co t c est dire le co t unitaire de chaque multiplication d pend ici d autres facteurs Type du nombre a la multiplication de r els en criture flottante est plus ch re que la multiplication d entiers courts Algorithmes utilis s par les librairies num riques du langage du syst me d exploitation Vitesse du hardware Exercice 1 3 2 On admet que le co t de la multiplication est lin aire en le produit des tailles co t de la multiplication a a a x a Montrer que le co t de calcul de a est alors n 1 3 2 M thode dichotomique Cette m thode tr s ancienn
54. nt laquelle cette taille est calcul e Exercice 1 2 8 Si l on crit en base 2 un chiffre est un bit et K 1 Si l on crit en base 16 syst me hexad cimal on peut supposer qu un chiffre s crit sur quatre bits et K 4 Comparer les espaces m moire occup s par un m me entier dans ces deux repr sentations Le co t de l algorithme de codage en base b Ici et dans toute la suite de ce cours nous appellerons co t d un algorithme le temps d ex cu tion d un programme impl mentant cet algorithme Trois points tr s importants sont prendre en compte 1 Ce temps d pend presque toujours de la taille des donn es et nous le consid rerons donc comme une fonction de cette taille Par exemple le temps total de multiplication de deux entiers par la m thode apprise l cole primaire d pend du nombre de chiffres de ces entiers 2 Nous ne mesurons pas ce temps mais tentons de le pr dire partir d une analyse du compor tement dynamique de l algorithme Par exemple pour calculer a un algorithme simplet effectuera n 1 multiplications 3 Selon la machine utilis e le langage de programmation voire l environnement d ex cu tion les op rations lementaires op rations arithm tiques mais aussi comparaisons entre nombres lectures et critures affectations etc ne prennent pas le m me temps Nous n en tiendrons pas compte et remplacerons ces temps l mentaires par d
55. ode RSA de cryptographie cl publique a t invent e en 1978 par Ron Rivest Adi Shamir et Leonard Adleman du MIT Sa mise en oeuvre suppose le choix d un module n d une cl publique e n et d une cl secr te d n Les propri t s requises sont les suivantes 1 L entier naturel n est assez grand pour que l on puisse facilement coder voir la remarque ci dessous tout message sous la forme d une suite d entiers de 0 n 1 2 Les entiers naturels d et e v rifient la propri t VaeZ a a mod n Remarque 2 3 5 Nous distinguons ici le codage du cryptage Le codage est simplement la mise du texte sous une forme adapt e l algorithme Par exemple chaque caract re du message transmettre est repr sent par un octet et le message est tron onn en paquets d octets de tailles telles que l on puisse les repr senter par un entier M 0 n 1 Le probl me du cryptage est alors pour l metteur du message de remplacer M par un entier M C M 0 n 1 la lettre C est ici pour cryptage dont le commun des mortels ne saura que faire mais que le destinataire du message saura reconvertir en M D M la lettre D est ici pour d cryptage La cl publique e n et la cl secr te d n tant donn es le principe est le suivant Leur d tenteur diffuse publiquement la cl publique e n et garde par devers lui la cl secr te d n Chaque fois que q
56. oisit un repr sentant a Z de x et un repr sentant b Z de y Alors si c ab on pose xy C Cette d finition est coh rente en vertu du corollaire On a la r gle ab ab Voici titre d exemple les tables de multiplication modulo m pour m 2 3 4 5 6 x 01112 31415 nr lite 14 a AP AE 0100 0 0100 X 01 2 LL LL 1 F6100 01010 xoll LL 61001010 110111231415 Z olololo T0 121314 ololol H EEE EE En AS 2 0121410 214 To re NN Ne lo ee TOIT 210 2 0 2 3101310 31013 2 O2 TT EE A ae cale 30131211 4101412 0412 4101431211 5 l01S14 32 1 La multiplication dans Z mZ v rifie les propri t s suivantes Commutativit Pour tous x y Z mZ on a xy yx Associativit Pour tous x y z Z mZ on a xy z x yz El ment neutre Pour tout x Z mZ on a x1 1x x Distributivit Pour tous x y Z mZ on a x y z xy xz et y z x yx zx Ajoutons que 0 est un l ment absorbant pour tout x Z mZ on a x0 Ox 0 On r sume ces propri t s en disant que Z mZ muni de l addition et de la multiplication est un anneau commutatif Il y a cependant deux propri t s qui man
57. ordre lexicographique c est dire l ordre du dictionnaire s il s agit de chaines de caract res Supposons de plus que le tableau est tri autrement dit que l on ait T1 lt lt Tfn L algorithme ci dessus peut alors facilement tre modifi pour d tecter un chec avant la fin de la lecture compl te du tableau En effet d s que T i gt e on sait que l on n a pas besoin de chercher plus loin Voici la version am lior e le tableau est encore not tab Li 1 tant que tabli lt e et i lt n faire i i 1 fin tant que i lt n et tabli e alors rendre i sinon ECHEC fin si Il est facile de v rifier que le co t d une recherche avec succ s n est pas modifi par cette am lioration Quant au co t d une recherche avec chec on peut estimer en l absence d hypoth se particuli re sur les valeurs effectivement recherch es par les utilisateurs qu il est en moyenne di vis par deux C est une am lioration mais mineure 37 On peut faire beaucoup mieux pour exploiter le fait que le tableau est tri Une recherche dichotomique consiste regarder au milieu du tableau puis si l on n a pas trouv aller gauche ou droite selon le cas La taille du domaine de recherche est divis e par deux chaque tape ce qui garantit une terminaison beaucoup plus rapide Voici une fa on d crire l algorithme T 1 JC trouv f
58. pas tre trop diff rent de N m Enfin on peut g n raliser et tester la fr quence des r uples on tire rN fois on examine les r uples successifs X k Xrk 1 X k 1 1 on compte le nombre N i de fois qu apparait chacun des r uples possibles i1 1i 0 m 1 et l on v rifie que dans l ensemble les N ne sont pas trop diff rents de rN m Exercice 2 2 7 Serait il int ressant de calculer la somme des N N 1 m sans valeur absolue TP 2 2 8 Programmer la mise en oeuvre de ces tests Le test du chi deux Il s agit d une mani re scientifiquement fond e de quantifier le jugement les fr quences ne s cartent pas trop de la normale Que le lecteur se rassure nous n en exposerons pas la jus fication th orique De plus nous n en d crirons le fonctionnement que dans le cas du test de fr quence simple les N N s cartent ils de 1 m On calcule la variance m 1 V mN Y N N 1 m i 0 Puis on utilise la table ci dessous voir en haut de la page suivante L entier v d signe le nombre de degr s de libert dans notre cas m 1 en effet les N N ne sont pas ind pendants les uns des autres leur somme est n cessairement 1 Supposons que m 16 i e que l on ait tir des nombres entre 0 et 15 donc v 15 D apr s la table on a V lt 11 04 avec une probabilit voisine de 25 Pour que cette r gle soit valable il faut que
59. quent l appel l int grit et l existence d un in verse Par exemple dans Z 4Z l l ment 2 n est pas nul mais 2x2 0 De plus aucun l ment x Z AZ ne v rifie 2 x x 1 De m me dans Z 6Z les l ments 2 et 3 ne sont pas nuls mais 2 x 3 0 De plus aucun l ment x Z 6Z ne v rifie 2 x x 1 ni d ailleurs 3 x x 1 En revanche dans Z 2Z Z 3Z et Z 5Z on v rifie par simple examen des tables de multiplication que le produit de deux l ments non nuls est non nul on dit que ces anneaux sont int gres et 24 que tout l ment non nul x admet un inverse x c est dire que x x x x x x 1 on dit que ces anneaux sont des corps La diff rence la plus visible entre 4 6 d une part 2 3 5 d autre part est que chacun de ces derniers est premier i e il n admet pas d autre diviseur que lui m me et 1 Nous allons voir que c est bien la raison de cette diff rence de propri t s de la multiplication Nous dirons que x Z mZ est diviseur de z ro s il existe y 0 tel que xy 0 et que x est inversible s il existe x Z mZ tel que xx 1 Th or me 2 1 12 i Si m est premier l anneau Z mZ est int gre autrement dit O est le seul diviseur de z ro et c est un corps autrement dit tout x 0 est inversible ii Si m n est pas premier l anneau Z mZ n est ni int gre ni un corps Preuve C est en fait un cas particulier de la proposition 2 1 14 que no
60. ques s imposent ici 1 Nous ludons totalement la question de la repr sentation interne de a de b et des chiffres ci et donc galement de la mani re dont sont impl ment s les calculs de division eucli dienne 2 Nous avons mis part le cas de 0 qui quelle que soit la base s crit O 3 Nous avons d fini et calcul l criture propre de a On aura parfois besoin de ses critures impropres dans lesquelles on s autorise ajouter des chiffres O au del du chiffre de poids fort par exemple 00011111011011 2 au lieu de 11111011011 2 Lorsque l on autorise les critures impropres il n y a plus unicit de l criture Exercice 1 2 3 On propose un traitement math matique de l invariant de boucle On pose xo a et tant que x gt 0 xi41 c diveucl x b D montrer par r currence que pour tout i a cob cb xib TP 1 2 4 Programmer le calcul de l criture en base b d un entier a A d faut de savoir repr senter les tableaux on crira un programme qui affiche les chiffres de a puis l entier k Taille du codage d un entier en base b L criture en base b sert avant tout coder les entiers Le codage d un entier donn repr sente un certain espace dans la m moire d un ordinateur Nous estimerons cet espace m moire en sup posant pour simplifier notre mod le math matique qu il est enti rement occup par les chiffres Cette hypoth se simplificatrice est d ai
61. r i lt n qui donne un co t de n Et en moyenne quel est le co t Si nous supposons que l l ment e peut tre trouv dans chacune des positions T 1 T n avec la m me probabilit le co t moyen est 1 n n n 1 2_ 41 n K n 2 L hypoth se d quiprobabilit des positions signifie concr tement que lorsque l on effectue un tr s grand nombre N de recherches d l ments qui figurent effectivement dans le tableau on trouve la position T 1 approximativement N n fois et de m me pour T 2 T n Cette hypoth se est raisonnable si tous les l ments du tableau sont distincts Si ce n est pas le cas l analyse est l g rement plus compliqu e mais le r sultat n est pas substantiellement diff rent En conclusion le co t d une recherche avec chec est constant gal n le co t d une re n 1 Las le co t est donc lin aire cherche avec succ s est au pire gal n et en moyenne gal Remarque 4 1 1 Nous ludons compl tement la question des biais d utilisation du tableau par exemple les ph nom nes socioculturels qui font qu un utilisateur cherchera plus fr quemment la chaine de caract res Michael Jackson que la chaine de caract res Co t des algorithmes Cas d un tableau tri On suppose maintenant que le type des l ments du tableau est muni d une relation d ordre l ordre vident s il s agit de nombres et par exemple l
62. rcher la position du plus grand des l ments T 1 T n Bien entendu si le tableau est tri ce maximum est T n et le probl me est trivial En g n ral voici un algorithme simple 1 On admet implicitement ici que le tableau est constitu et tri une fois pour toutes ce qui est bien le cas pour un dictionnaire mais rarement pour une base de donn es Pour un ensemble de donn es qui volue d autres structures de donn es conviennent 39 i 1 Joi m tab 1 tant que i lt n faire i a si m lt tabli l alors m tablil j i fin si fin tant que rendre j m A toute tape de la boucle m T j est le maximum de T 1 T i Le nombre de comparaisons est toujours n 1 Comme crit re de co t nous prendrons plut t le nombre de fois o l on a d mettre jour j et m initialisations comprises Dans le meilleur des cas le maximum se trouve en j 1 et le co t est donc de 1 initialisa tions Dans le pire des cas le tableau est tri mais on ne le sait pas et j prend successivement toutes les valeurs de 1 n le co t est donc de n En g n ral le co t est gal au nombre de maxima stricts gauche droite c est dire au nombre des indices i tels que T fi gt max T 1 T i 1 On peut d montrer que si le tableau contient n l ments distincts et que les diff rents ordres pos 1 sibles de ces l ments sont quiprobables alors le co t moyen
63. seront expliqu s Tout d abord explicitons informellement la m thode Un algorithme pr cis sera crit plus loin Sin 2p calculer b a puis a b x b Sin 2p 1 calculer b a puis a b x b x a Notons c n le nombre de multiplications n cessaires pour calculer a Par exemple c 1 0 et de toute vidence c 2 1 De la description ci dessus on d duit les r gles c 2p c p 1 c 2p 1 c p 2 Cela permet d j de calculer les premi res valeurs de c n n 1 2 3 4 5 6 7 8 9 10 1 12 cno 1 2 2 3 3 4 3 4 4 5 4 n 13 14 15 16 17 18 19 20 21 22 23 24 cms 5 6 4 5 5 6 5 6 6 7 5 Nous allons maintenant trouver la formule g n rale donnant le co t c n Pour cela on prend en compte l criture binaire des expressions 2p et 2p 1 En effet si l criture binaire de p est bp bo alors L criture binaire de 2p est bp bo0 2 L criture binaire de 2p 1 est bg bol 2 Comme c 1 0 on en tire la r gle suivante Proposition 1 3 4 Soit ag ao 2 l criture binaire propre de n donc ag 1 Soient amp le nombre de 0 et B le nombre de 1 parmi les bits a ag 1 on ne prend donc pas en compte le bit de poids fort ag Alors c n a 2B k B Preuve En effet on peut reconstituer l criture binaire propre de n en partant du bit 1 criture binaire du nombre 1 correspondant au co t c 1 0 et en rajoutant s
64. suivant pour en tre s r Disons que l effort en ce sens peut tre consid r comme rentable si l on veut calculer souvent a On ne peut pas faire beaucoup mieux en g n ral Nous allons d montrer que l on ne peut pas esp rer calculer a en moins de log n multiplica tions La m thode de d monstration consiste prendre le probl me l envers et chercher la plus grande puissance de a que l on peut calculer en k multiplications On fixe les r gles comme suit On pose x9 a qui n a co t aucune multiplication On va calculer x1 x en utilisant chaque fois une seule multiplication De plus le calcul de chaque x ne peut faire intervenir que les valeurs d j calcul es xo x _1 A chaque tape on calcule donc une puissance x ai Bien entendu po 1 car xo a a et pi 2 car x a xa Ensuite tout ce que l on peut dire c est que x x x x donc pi pj p avec O lt j 1 lt i 1 Proposition 1 3 9 i On a p lt 2 pour tout i 0 k ii En particulier si l on peut calculer a en k multiplications alors n lt 24 Preuve i Se prouve par r currence forte C est clair pour i 0 1 Pour un i gt 2 fix supposons que c est vrai pour tout indice j lt i 1 On a vu que p pj p avec 0 lt j l lt i 1 Par hypoth se de r currence forte on a pj lt 2 et Pi lt 2 d o pi p pi lt 2 2 lt 2 42 oi ii en
65. t la p riode de cette suite Exemple 2 2 2 Prenons m 7 Tout a Z 7Z v rifie af donc la suite des a x o se repro duit coup s r avec une p riode 6 Mais si l on prend par exemple a 2 on a a 1 et la p riode tombe 3 Il vaut mieux prendre a 3 qui est tel que a 1 a 3 a 2 a 6 at 4 a 5 sont distincts et qui fournit donc une suite aussi longue que possible Dans tous les cas voici ce dont est s r quel que soit a Z mZ 1 Il existe un plus petit entier n gt 1 tel que a 1 2 Cet entier est un diviseur de m 1 27 3 La suite x est de p riode n elle admet n termes distincts L entier n est appel ordre de l l ment a Z mZ Et maintenant comme dans l exemple ci dessus il y a moyen de choisir un l ment d ordre optimal Th or me 2 2 3 Il existe un l ment a Z mZ d ordrem 1 Preuve Ce sera prouv dans le cours d alg bre de L2 Cas d un module primaire Supposons m primaire c est dire puissance d un nombre premier n p o p est premier etr gt 2 Dans ce cas il n est pas aussi facile d tudier une suite arithm tico g om trique g n rale aussi prendrons nous d embl e b 0 Et bien entendu on suppose toujours a 0 1 etxo 0 Si a est la classe d un multiple de p alors a est la classe d un multiple de p donc a 0 Dans ce cas la suite est sta
66. t rapide pour d terminer la d composition en facteurs premiers d un entier Il n est pas ques tion de justifier ici cette affirmation il faudra donc l admettre En revanche il existe des algo rithmes raisonnables pour calculer le pgcd 1 41 L algorithme de base Il s agit d un algorithme rudimentaire mais l gant qui remonte Euclide Il repose sur l id e suivante Lemme 1 4 1 SiO lt b lt a alorsa b a b Ab Preuve Si m divise a et b alors il divise leur diff rence d o D a N D b D a b D a N D b D a b N D b 2 Elle est li e la th orie de la complexit laquelle intervient dans l une des sept questions un million de dollars pos es par l institut Clay en l an 2000 Rappelons que l une des questions mais pas celle ci a t r solue r cemment par le russe Gregory Perelman 17 Si m divise a b et b alors il divise leur somme d o D a b ND b c D a D a b ND b c D a N D b On a donc D a N D b D a b N D b d o la conclusion Pour calculer le pgcd de a et b on peut donc si O lt b lt a les remplacer par a b et b donc par des nombres plus petits Si b 0 on a a Ab a Si b gt a on inverse les r les puisque a b bA a Voici l algorithme qui exprime cette description informelle tant que x gt 0 et y gt 0 si x lt y alors y 5 Y X sinon X X Y fin si
67. tant que rendre r On a not par p div 2 le quotient de la division de p par 2 Si p gt 0 le quotient de la division euclidienne par 2 v rifie p 2 lt p Dans l algorithme l entier p d croit donc strictement chaque tape ce qui garantit la terminaison L invariant de boucle qui permet de prouver la correction est le suivant apr s chaque tape on a a rx et p gt 0 Nous laissons au lecteur de v rifier que ces conditions sont conserv es En fin d it ration on n a plus p gt 0 donc p 0etr a 15 Exercice 1 3 7 L algorithme crit ci dessus effectue une multiplication inutile la fin Rectifier ce petit d faut qui affecte la performance mais pas la correction TP 1 3 8 Programmer cet algorithme 1 3 3 Questions d optimalit On peut faire un peu mieux au cas par cas Pour calculer a par la m thode dichotomique il faut c 15 6 multiplications Voici deux s quences de calcul qui donnent le r sultat en 5 multiplications La premi re revient crire a aa X1 54X4 X2 X1 X4 X3 X2XX2 X4 X3 X X3 X5 X4 X X2 La seconde revient crire a 5 a5 X1 54X4 X2 X1 XX X3i X2 X4 X4 X3 XX3 X5 X4 X X3 Ces calculs reposent directement sur une factorisation de n Il existe une m thode g n rale pour trouver de telles s quences optimales de calcul mais elle est compliqu e mettre en oeuvre et le gain n est pas norme voir le paragraphe
68. te criture binaire 11111011011 avec celle d un entier de l ordre de dix milliards on crira plut t 11111011011 2 Notons que dans les deux cas nous crivons les puissances de 10 ou de 2 par ordre d croissant d exposant le chiffre des unit s est droite Avant d noncer et de d montrer le th or me fondamental voici un r sultat pr liminaire qui sert beaucoup dans la pratique Lemme 1 2 1 Soient k gt 0 un entier et co cx 0 b 1 On suppose que cp 0 L entier a cb cob v rifie alors 1 2 1 1 b lt a lt b 1 Preuve Puisque c gt 0 et cg gt 1 un minorant de a est 1 64 0 0 0 b Puisque c lt b 1 un majorant de a est b 1 b b1 b 1 Th or me 1 2 2 Soita N un entier naturel non nul Il existe alors un unique entier k gt 0 et une unique suite finie co cx tels que a cb cb 1 2 2 1 O lt c lt b 1 pouri 0 k ck 0 On dit alors que cp co p est l criture de a en base b Les c sont les chiffres de cet criture On pr cise parfois que cette criture se fait poids forts gauche Preuve L unicit se prouve par r currence forte sur a Si a lt b 1 d apr s le lemme on a n cessairement k 0 d o l on d duit co a L unicit est donc bien d montr e dans ce cas Soit donc a gt b et supposons l unicit prouv e pour tout entier a tel que
69. te contient la derni re valeur de x qui a t rendue Dans notre approche l mentaire nous ne traiterons pas ce probl me nous consid rerons simplement des programmes qui calculent f x donc chaque nouveau terme en fonction du pr c dent Il existe deux types principaux de g n rateurs al atoires ceux qui rendent des nombres r els entre O et 1 et ceux qui rendent des entiers entre O et m 1 l entier m gt 2 ayant t pass en argument Nous ne nous occuperons que du deuxi me type Exercice 2 2 1 Comment utiliser un g n rateur de l un des deux types pour muler l autre 1 Quiconque envisage des m thodes arithm tiques pour produire des nombres al atoires est bien entendu en tat de p ch 26 2 2 1 G n rateurs lin aires congruentiels Nous supposons fix le module m gt 2 argument d appel Au lieu de consid rer une suite d entiers compris entre 0 et m 1 nous consid rerons une suite d l ments de Z mZ Le format g n ral de cette suite est donn par la relation de r currence VnEN xn 1 aXn b Il faut donc choisir a b xo Z mZ On ne prendra videmment pas a 0 car la suite serait constante partir du rang 1 et n aurait pas du tout l air al atoire On ne prendra pas non plus en g n ral a 1 car on aurait x xo nb et l on rep rerait trop facilement une r gularit Attention la notation nb d signe ici la somme de n termes gaux
70. tionnaire en 0 et donc tr s peu al atoire Nous supposons donc que a est la classe d un entier non multiple de p Mais un tel entier n a pas de diviseur commun avec p m donc a est inversible on a encore a Z mZ la situation est analogue celle d crite plus haut 1 Il existe un plus petit entier n gt 1 tel que a 1 2 Cet entier est un diviseur de m p p 3 La suite x est de p riode n elle admet n termes distincts On dit encore que n est l ordre de a En ce qui concerne le choix d un l ment d ordre optimal la situation est un tout petit peu plus compliqu e Th or me 2 2 4 i Si p est impair ou si m est gal 2 ou 4 il existe un l ment a Z mZ d ordre m ii Sim 2 r gt 3 on a m 2771 Il n existe pas d l ment d ordre 2 l l ordre optimal est 27 C est l ordre de l l ment 3 mais pas uniquement de ce dernier Exercice 2 2 5 D montrer que l ordre d un l ment de Z mZ divise m TP 2 2 6 Trouver dans Z mZ un l ment d ordre optimal 2 2 2 Quelques tests Le fait que le g n rateur pseudo al atoire ait une grande p riode n est pas un crit re suffisant de bonne qualit Par exemple pour m 2 un tel g n rateur peut tre assimil un simulateur de tirage pile ou face mettons que pile 1 et face 0 S il tire avec r gularit 10 1 fois pile et une fois face sa p riode sera 10 c
71. tout avoir essay avant de s en apercevoir En moyenne en cas de succ s on peut s attendre un co t moiti moindre donc de l ordre de n 2 Il s agit donc d un co t quadratique Exemple 4 1 7 Reprenant nos consid rations heuristiques bas es sur la loi de Moore Un algo rithme quadratique qui s ex cute en un dixi me de seconde sur un tableau de cinq cents l ments prendra un million de fois plus de temps pour un tableau de cinq cents mille l ments Il faudra 20 x 18 360 mois soit trente ans pour que l am lioration du mat riel informatique permette de compenser cette d gradation de performance Si l on suppose maintenant que le type des l ments du tableau est muni d une relation d ordre et que le tableau est tri Pour d celer d ventuelles duplications il suffit de consid rer des paires d l ments cons cutifs du tableau Voyez vous pourquoi On a donc besoin d au plus n 1 comparaisons Le co t est devenu lin aire ce qui est beaucoup mieux Nous verrons que l on peut trier un tableau de taille n avec un co t de l ordre de ninn donc m me pour chercher les duplications une seule fois cela vaut la peine de trier pr alablement le tableau Bien entendu cette affirmation ne concerne que des tableaux assez grands pour que le co t soit un probl me TP 4 1 8 Programmer la recherche de duplicata dans un tableau non tri et v rifier l estimation du co t moyen par exp
72. uccessivement droite des bits 0 et des bits 1 14 Chaque fois que l on rajoute un bit 0 le co t augmente de 1 cela se produit amp fois Chaque fois que l on rajoute un bit 1 le co t augmente de 2 cela se produit f fois On a donc bien la fin c n amp 2 D autre part le nombre total de bits que l on a ajout est a B k d o la deuxi me formule Corollaire 1 3 5 i Le cas le meilleur est celui o l on n a rajout que des 0 alors n 2 et c n k ii Le cas le pire est celui o l on n a rajout que des 1 alors n 2 1 et c n 2k iii Dans tous les cas on a k lt c n lt 2k Rappelons d autre part que k log n n 1 o l on d signe par n la taille de l criture de n en base 2 Corollaire 1 3 6 i Le co t c n v rifie Hogn lt e n lt 2 logzn ii On a c n O log n O n log n Comme lim 2er 0 on voit que pour de grandes valeurs de l exposant n le rapport du n gt Nn co t par la m thode dichotomique au co t par la m thode naturelle tend vers 0 c est le sens de la phrase on a une performance asymptotique infiniment meilleure que par la m thode naturelle L algorithme On traduit la m thode d crite informellement plus haut par l algorithme de calcul de r x r 1 x p n tant que p gt 0 si p impair alors Cry Ex fin si OR UE S p p div 2 fin
73. ue la toute derni re addition Il est vident que cet algorithme se termine apr s k 1 ex cutions de l instruction de boucle La correction se prouve l aide de l invariant de boucle co cib ch bi do dibi rbi On doit ajouter le fait que tout moment r 0 ou 1 donc que ci c r lt 2b 1 donc le di calcul est bien un chiffre un nombre entre 0 et b 1 Exercice 1 2 9 Quelle est la probabilit qu il n y ait aucune retenue TP 1 2 10 Programmer l addition en base b Co t de l algorithme d addition en base b Chaque tape de la boucle tant que contient une addition de deux chiffres une addition de la retenue un test peut tre une soustraction certainement une incr mentation En prenant en compte les instructions avant et apr s la boucle tant que on conclut qu il existe des constantes A A gt 0 et des constantes B B telles que le co t soit compris entre A k 1 B et A k 1 B7 autrement dit entre Amax a a B et A max Ja a B De mani re tr s informelle on peut encore dire que le co t de l addition est une fonction peu pr s lin aire de la taille des donn es On peut m me pr ciser cet peu pr s comme suit 10 1 L ordre de grandeur du co t n est pas pire qu un co t lin aire Plus pr cis ment lorsque la taille des donn es a a est de plus en plus grande le rapport co t de l
74. uelqu un veut lui envoyer un message secret M 0 n 1 1 Il crypte M selon la formule M C M M mod n 2 Le destinataire d crypte M selon la formule M D M M mod n Ici par abus de notation M mod n d signe le reste de la division de M par n et similairement pour M mod n En fait ces calculs peuvent s effectuer relativement vite par exponentiation rapide dans Z nZ La m thode RSA est correcte en vertu du calcul D C M M mod n M Il reste voir comment on d termine les cl s publique et secr te 1 On choisit deux grands nombres premiers distincts p et q et l on pose n pq 2 On choisit un entier e premier avec n p 1 q 1 ni trop grand ni trop petit 3 On d termine un entier d tel que de 1 mod n l aide de l algorithme d Euclide tendu Cette m thode est praticable parce qu il est plut t facile de trouver des grands nombres premiers Si l on savait aussi facilement factoriser n la m thode de cryptage serait facile casser Mais on ne sait pas factoriser facilement les grands nombres et depuis 1978 on n a pas trouv non plus d autres attaques efficaces contre RSA TP 2 3 6 Programmer la mise en oeuvre de l algorithme RSA On choisira p et q dans une table 2 4 Suppl ments facultatifs Recherche de la p riode m thode de Brent R solution de l quation ax b mod m R solution simultan e lemme ch
75. us prouverons au para graphe suivant L exemple le plus fondamental est celui o m 2 Le corps Z 2Z est parfois not F3 TP 2 1 13 Programmer le calcul dans l anneau Z m2Z y compris le calcul de l inverse d un l ment quand m est premier 2 14 Le groupe Z mZ x Proposition 2 1 14 Soit a 0 m 1 et soit d a m le pgcd de a et m i Sid gt 1 alors a est un diviseur de z ro et n est pas inversible dans Z mZ ii Si d 1 alors a n est pas un diviseur de z ro et a est inversible dans Z mZ Preuve i On crit a da et m dm Puisque d gt 1 on a 0 lt m lt m donc m 0 mod m donc m 0 Par ailleurs ml am 4 am da m a m 0 Comme m 0 on en d duit que est un diviseur de z ro D autre part si a tait inversible on pourrait crire ab 1 d o ab 1 km d o d a b km 1 ce qui est impossible puisque d gt l ii D apr s le th or me de B zout il existe k b Z tels que ab km 1 Alors ab 1 et a est bien inversible dans Z mZ Supposons alors que ax 0 En multipliant les deux membres de cette galit par b on trouve que x 0 ce qui montre que n est pas un diviseur de z ro On est conduit distinguer les l ments inversibles de Z mZ c est dire d apr s la propo sition les l ments de la forme o a 0 m 1 et o a Am 1 autrement dit a
76. utiles de valeur maximale la fin Ces l ments resteront leur place et la fin seuls les douze premiers l ments du r sultat nous int resseront Nous verrons que ce proc d de remplissage qui est souvent n cessaire dans les algorithmes dichotomiques n a pas d influence sur l ordre de grandeur du co t 4 Nous nous restreindrons donc des tableaux de n 2 l ments Pour simplifier la manipu lation des indices des l ments nous supposerons que ceux ci varient de 0 n 1 comme en C par exemple En effet dans ce cas les indices des deux sous tableaux varient respec tivement de 0 2 1 et de 271 2 1 les formules sont plus simples qu elles ne le seraient pour des indices variant de 1 n Dans la figure suivante on d taille le cas d un tableau de huit l ments Par exemple en fusionnant le sous tableau r duit l l ment T 0 avec le sous tableau r duit l l ment T 1 on obtient le sous tableau tri form des l ments T 0 T 1 et le co t de cette fusion est 2 pour le moment on admet qu il existe une telle m thode de fusion De m me en fusionnant le sous tableau tri form des l ments T 0 T 1 avec le sous tableau tri form des l ments T 2 T 3 on obtient le sous tableau tri form des l ments T 0 T 1 7 2 T 3 et le co t de cette fusion est 4 Le total des co ts est donc 4x 2 2 x4 1 x 8 24 45 01 co t 2 4 1 0123
77. x premi res classes l entier 2000 est un repr sentant de la troisi me Remarque 2 1 7 La notation est ambigue puisque l on ne pr cise pas le module Ainsi dans Z 2Z on a 0 2 alors que c est faux dans Z 3Z 2 1 2 Le groupe Z mZ Proposition 2 1 8 Soient a d b b Z On suppose a a mod m etb b mod m Alors a b a b mod m Preuve Si a a km et b b Im alors a b a b k l m Cette propri t est appel e compatibilit de la relation de congruence avec l addition On en d duit imm diatement Corollaire 2 1 9 Soient a a b b Z On suppose a a etb b Alors a b a 7 22 Ce corollaire permet de d finir une loi de composition interne en l occurrence une addition sur l ensemble Z mZ des classes de congruence modulo m On proc de de la fa on suivante Soient x et y deux l ments de Z mZ On choisit un repr sentant a Z de x et un repr sentant b Z de y Alors si c a b on pose x y T Cette d finition pose un probl me obtiendrait on le m me r sultat si l on avait choisi d autres repr sentants Pour chaque classe il y a une infinit de repr sentants Pour le savoir on choisit un autre repr sentant a Z de x et un autre repr sentant b Z de y et l on calcule c a b Logiquement l application de la d finition ci dessus donne tout aussi bien x y c Pour que ces

Download Pdf Manuals

Related Search

Related Contents

TracFone SM-S975L Samsung Galaxy S 4 User Manual  L75670WD - Voelkner  CFE400M Medical Power Supply Installation Manual - TDK  Akai AD50X  ENREGISTREMENT BIPISTE À L`AIDE D`UNE CARTE SON  

Copyright © All rights reserved. Failed to retrieve file