illustration en arithmetique des
Contents
1. 5 6 7 1 8 0 1 Sur ordinateur idem mais en base 2 Complexit de l addition de 2 nombres a n chiffres O n op rations sur des chiffres APMEP Lyon 16 avril 2003 8 N Revol INRIA Syst mes redondants de num ration Avizienis 1961 En base 8 chiffres a a avec a entier et 2a gt 6 1leta lt G 1 Le nombre x est repr sent par h_1 n_2 T2 1T0 Si SE xiP Si 2a 1 gt 8 alors on peut repr senter tous les entiers Si 2a 1 gt 8 alors un nombre peut avoir plusieurs repr sentations le syst me est dit redondant Exemple en base 3 10 avec a 6 1546 s crit 1546 2 5 46 not 2546 2 4 6 6 not 2466 2454 1666 1654 APMEP Lyon 16 avril 2003 9 N Revol INRIA Addition sans propagation de retenue En base 5 avec des chiffres compris entre a et a calcul de Sys SO Oi 2842p Yn 1 YO 1 Calculer pour 2 0 n 1 si Le Ue eo Lis 0 st atl lt a y lt a l1 1 si titza wi tit Yyi Pti 2 Calculer pour i 0 n 8 W avec Wy to v APMEP Lyon 16 avril 2003 10 N Revol INRIA Exemple 6 10 a 6 criture usuelle x 12535 8525 y 35156 35044 Somme 43569 APMEP Lyon 16 avril 2003 11 N Revol INRIA Addition dans un syst me redondant de num ration Les t retenues de l addition usuelle mais pas de d pendance entre t et t 11 le calcul de chaque chiffre peut se faire e2. nombre 64 bits U R sultat d une op ration arrondi du r sultat exact si op ration X ou J Avantages reproductibilit des calculs d une machine l autre algorithmes avec des erreurs optimales ou des majorations fines des erreurs preuves APMEP Lyon 16 avril 2003 28 N Revol INRIA Les flottants problemes Propriet s alg briques perdues les op rations ne sont plus associatives x n est plus distributive par rapport Exemple programme de Gentleman A 1 0 B 1 0 while A 1 0 A 1 0 0 0 do A 2 0 A while A B A B lt gt 0 0 do B Bt 1 0 result round B Que calcule ce programme APMEP Lyon 16 avril 2003 29 N Revol INRIA Les flottants encore de la recherche en cours Algorithmes mat riels de division avec une notation redondante on regarde seulement les 4 premiers bits du dividende courant Bug du Pentium 4195835 0 3145727 0 1 333739068 au lieu de 1 33382044 APMEP Lyon 16 avril 2003 30 N Revol INRIA Les flottants encore de la recherche en cours Algorithmes mat riels de division avec l it ration de Newton pour calculer 1 x la solution de l quation 1 z x Oest z 1 z Newton 2 41 Zk f zk J ze Avec f z 1 z x on obtient l it ration 1 Ze x Dr zy EF ay 1 249 k Si on part d une bonne approximation de 1 x lue dans une table on
3. x mod N facile 3 envoie y Alice calcule y eSa V an AN gna y mod N APMEP Lyon 16 avril 2003 24 N Revol INRIA Les rationnels X on sait faire beaucoup de calculs de pgcd Exemples de logiciels Maple Mathematica certaines calculatrices T1 Avantage calcul exact Inconv nients Nombres grossissent Complexit d pend de la taille des nombres gt exp sin on ne sait pas faire APMEP Lyon 16 avril 2003 25 N Revol INRIA Plan de l expos e Algorithmes pour l arithm tique exacte cole primaire e Algorithmes pour l arithm tique flottante notation scientifique e Arithm tique par intervalles e Complexit APMEP Lyon 16 avril 2003 26 N Revol INRIA Les nombres en notation scientifique les flottants Repr sentation m 3 14 x 10 0 314 x 10 0 031 x 10 314 x 107 Nombre de chiffres utilis s dans la repr sentation constant Calculs X en temps constant exp Sin en temps constant Arrondis 3 14 x 10 5 36 x 107 3 676 x 10 sa repr sentation ne doit prendre que 3 chiffres 3 14 x 10 5 36 x 107 3 68 x 10 APMEP Lyon 16 avril 2003 27 N Revol INRIA Les nombres en notation scientifique la norme IEEE 754 pour l arithm tique flottante Formats de repr sentation des nombres signe exp mantisse Ex nombre 32 bits i 8 signe exp mantisse Ex
4. 2xX3x3xX 5x llet252 2X2X3X 3 X 7 Complexit difficile certains algorithmes de cryptographie cl publique dont RSA APMEP Lyon 16 avril 2003 20 N Revol INRIA Cryptographie a cl publique texte clair m canal non s curis C EVE texte chiffr VAINRIA APMEP Lyon 16 avril 2003 21 N Revol INRIA Algorithme RSA Alice Bob et la m chante Eve ALICE BOB d crypte le message encrypte le message avec sa cl priv e avec la cl publique d Alice EVE communication non s curis e APMEP Lyon 16 avril 2003 22 N Revol INRIA Algorithme RSA Alice Bob et la m chante Eve Alice 1 choisit 2 grands nombres premiers p et q facile 2 calcule N p x q N doit avoir au moins 150 chiffres 3 choisit e 2 y N 2 premier avec y N o y est la fonction d Euler p N p 1 x q 1 4 calcule d tel que ed 1 mod amp N B zout d d v ed v y N 1 5 publie NV e sa cl publique et cache N d sa cl secr te Euler Ve 0 N 1 six AN 1 alors x N 1 mod N cad x N H1 mod N APMEP Lyon 16 avril 2003 23 N Revol INRIA Alice Bob et la m chante Eve Alice publie NV e sa cl publique et cache N d sa cl secr te B zout A d v ed v y N 1 Euler Vx 0 N 1 sitAN 1alors x NH g mod N Bob 1 crit son message sous la forme d un entier x 0 N 1 2 calcule y
5. 16 avril 2003 55 N Revol INRIA _ R f rences Vulgarisation e Histoire d algorithmes Du caillou la puce J L Chabert et al Belin 1994 e Logique informatique et paradoxes J P Delahaye Belin 1995 e Histoire des codes secrets S Singh Le livre de poche 2001 Mod r ment sp cialis s e Qualit des calculs sur ordinateurs Vers des arithm tiques plus fiables coordonn par M Daumas et J M Muller Masson 1997 e La cryptologie moderne A Canteau et F L vy dit V hel Revue Armements 2001 http www rocq inria fr codes Anne Canteau crypto moderne pdf e Arithm tique en pr cision arbitraire P Zimmermann R seaux et syst mes r partis vol 13 no 4 5 2001 http www inria fr rrrt rr 4272 html e Arithm tique par intervalles N Revol R seaux et syst mes r partis vol 13 no 4 5 2001 http www inria fr rrrt rr 4297 html Sp cialis s Modern computer algebra J von zur Gathen and J Gerhard CUP 1999 Arithm tique des ordinateurs J M Muller Masson 1989 Elementary functions J M Muller Birkhauser 1997 Interval methods for systems of equations A Neumaier CUP 1990 Computational complexity C Papadimitriou Addison Wesley 1994 APMEP Lyon 16 avril 2003 56 N Revol INRIA
6. 22 APMEP Lyon 16 avril 2003 16 N Revol INRIA Multiplication on peut aller encore plus vite Multiplication rapide Multiplication bas e sur la transform e de Fourier rapide FFT ou plut t discr te DFT la complexit asymptotique de la multiplication est O n log n log log n mais elle est difficile implanter et ne bat d autres m thodes plus simples qu partir d environ 57 000 chiffres d cimaux APMEP Lyon 16 avril 2003 17 N Revol INRIA Exponentiation 315 1594 323 3 13 9 6 81 3 6561 1 puis multiplication 3 x 81 6561 1 594 323 Autre fa on de l crire 13 8 4 1 1101 318 38 x 34 x 3 avec 34 32 et 38 34 On proc de par l vations au carr successives et multiplications finales il y en a O log n si n est l exposant APMEP Lyon 16 avril 2003 18 N Revol INRIA Calculer l cole primaire division 990 252 252 234 7560 3 234 234 18 les entiers N 234 18 18 54 54 Complexit de la division de 2 nombres n chiffres O M n o M n est la complexit de la multiplication APMEP Lyon 16 avril 2003 19 N Revol INRIA Calculer a l cole primaire les entiers pgcd Rappel pgcd a b pgcd b r avec a bq r si r 0 Algorithme d Euclide pgcd 990 252 pgcd 252 234 pgcd 234 18 18 Complexit du pgcd de 2 nombres a n chiffres O M n log n factorisation 990
7. 1992 Ratschek and Rokne 1988 Baker Kearfott 1996 F X1 J IS lt lt gt lt gt XI X2 X3 f trop haute F X1 gt f fnon convexe sur X3 0 n est pas dans G X2 APMEP Lyon 16 avril 2003 43 N Revol INRIA Arithm tique par intervalles algorithme de Hansen liste des pav s en attente Xo tant que OQ faire sortir X de rejeter X oui si F X gt f oui si GradF X Z oui si HF X Sovak non gt 0 r duire X Newton sur le gradient r soudre Y C X tel que F Y lt f couper Y en 2 Y et Y ranger Y et Y dans APMEP Lyon 16 avril 2003 N Revol INRIA Arithm tique par intervalles problemes D corr lation des variables ou variable dependency Txl x xy xel yel F x xel Effet enveloppant ou wrapping effect me f x F X APMEP Lyon 16 avril 2003 45 N Revol INRIA Arithm tique par intervalles plus de pr cision Aspirateur autonome e par intervalles ne casse rien mais passe loin du vase en porcelaine de Chine e en pr cision arbitraire passe pr s du vase en porcelaine de Chine et le casse peut tre e par intervalles en pr cision arbitraire passe pr s du vase en porcelaine de Chine et ne le casse pas APMEP Lyon 16 avril 2003 46 N Revol INRIA Choix d arithm tique Arithm tiques exacte enti re et rationnelle flottante en pr cision fixe flottante en pr cision arbitraire intervalles e
8. Algorithmes et complexite illustration en arithm tique des ordinateurs Nathalie Revol INRIA projet Ar naire LIP ENS Lyon Nathalie Revol ens lyon fr APMEP Lyon 16 avril 2003 Algorithme suite d instructions effectuer pour accomplir une t che Syntaxe rigide quand on s adresse un ordinateur APMEP Lyon 16 avril 2003 1 N Revol INRIA Exemple conduite de r union D marrage e rappeler l ordre du jour e d finir les r gles du jeu Premier th me rappeler les objectifs e lancer la discussion l orateur e animer technique des questions e d l guer la gestion du temps le compte rendu e conclure rappeler les objectifs et les r sultats obtenus Idem pour les th mes suivants Conclusion e conclusion g n rale pour tous les th mes e remercier les participants APMEP Lyon 16 avril 2003 2 N Revol INRIA Algorithme conduite de r union Initialisations e cr er la liste des sujets de l ordre du jour Faire en parall le e pour chaque th me dans la liste faire rappeler les objectifs lancer la discussion l orateur si groupe apathique alors poser des questions sinon si groupe emball alors rappeler les r gles du jeu conclure sur ce th me le supprimer de la liste e gestion du temps e prise de notes pour le compte rendu e gestion des moyens techniques Conclusion animer APMEP Lyon 16 avril 2003 3 N Revol INRIA Assembleu
9. X 0 Si on veut le reste R A BxQ Newton modifi pour calculer X Xok X48 Xr BF Bor x Xr B B avec X entier k chiffres B l entier constitu a partir des k chiffres de gauche de B Arr t au bout de log n tapes APMEP Lyon 16 avril 2003 51 N Revol INRIA R duction d un probleme un autre Complexit e l tape k deux multiplications de 2 nombres k chiffres et deux complexit 2M k 2k e au total logn D lt CM n puisque M n lt D n on a SE M i lt 2M 2n APMEP Lyon 16 avril 2003 52 N Revol INRIA La classe NP D finition NP probl mes pour lesquels il existe un algorithme de v rification de la solution en temps polynomial en la longueur des entr es Exemples factorisation d entiers il est facile de v rifier une d composition isomorphisme de graphes si la bijection candidate est donn e facile APMEP Lyon 16 avril 2003 53 N Revol INRIA Hierarchies APMEP Lyon 16 avril 2003 54 N Revol INRIA Conclusions On sait faire les op rations arithm tiques exactes et flottantes l alg bre lin aire On ne sait pas faire la factorisation d entiers 7 l isomorphisme de graphes On essaie de classer les probl mes les uns par rapport aux autres P versus NP P P complet P dur NP NP complet NP dur pour justifier pourquoi on ne sait pas faire sauf si P NP APMEP Lyon
10. double le nombre de chiffres corrects chaque tape gt 3 ou 4 tapes suffisent APMEP Lyon 16 avril 2003 31 N Revol INRIA Les flottants encore de la recherche faire Fonctions l mentaires fonctions l mentaires les calculer vite et bien APMEP Lyon 16 avril 2003 syst me valeur exacte HP 48 GX HP 700 IBM 3090 600S VF AIX 370 Matlab 4 2c 1 Sparc Matlab 4 2c 1 Macintosh SG Indy Sharp EL5806 DEC Station 3100 32 sin 10 Ng 0 852200849767 0 852200849767 0 0 0 0 0 8522 0 8740 0 87402806 0 090748172 NaN N Revol INRIA c rithmetiqu 8 dottante attention pr cision limit e Aml 1 2 o 3 0 x tan atan 10000000 0 10000000 0 VVD 20 fois 5 ET m yal 1 e 100 _4 ince 1000 APMEP Lyon 16 avril 2003 33 N Revol INRIA c rithmetiqu 8 dottante attention pr cision limit e 2 1 1 0000000000000000 2 ma 2 0000000000001106 3 0 x tan atan 10000000 0 10000000 0 _ 3 0000000030728171 2 Ce V V2 20 fois 4 0000000006294343 Gite 1 D e 100 1 NaN mice 1000 00 APMEP Lyon 16 avril 2003 34 N Revol INRIA Arithm tique flottante attention aux arrondis Les faits e 1982 the Vancouver stock exchange introduced an index with nominal value 1000 000 e after each transaction it was recomputed and truncated to the third place to the right of the decimal point e after 22 mont
11. hs the index was 524 881 e the correct value was 1098 811 L explication toutes les erreurs d arrondis sont dans le m me sens truncation d apr s la page Web de Pete Stewart APMEP Lyon 16 avril 2003 35 N Revol INRIA Flottants en pr cision multiple plus de chiffres Principe utiliser des repr sentations de longueur fix e le produit de 2 nombres a la m me longueur que les multiplicandes mais plus longues que celles des flottants machine Complexit lt celle du calcul sur des entiers de m me longueur Avantage plus de pr cision Inconvenient toujours aucune garantie sur les r sultats APMEP Lyon 16 avril 2003 36 N Revol INRIA Plan de l expos e Algorithmes pour l arithm tique exacte cole primaire e Algorithmes pour l arithm tique flottante notation scientifique e Arithm tique par intervalles e Complexit APMEP Lyon 16 avril 2003 37 N Revol INRIA Calcul garanti avec les flottants arithm tique par intervalles Moore 1966 Kulisch 1983 Neumaier 1990 Rump 1994 Alefeld and Mayer 2000 Principe Nombres remplac s par des intervalles m remplac par 3 14159 3 14160 Vecteurs remplac s par des vecteurs d intervalles Matrices remplac es par des matrices d intervalles Int r t incertitudes sur les donn es de mesure prises en compte APMEP Lyon 16 avril 2003 38 N Revol INRIA Calcul garanti avec
12. les flottants arithm tique par intervalles 3 2 x 3 2 6 9 est diff rent de 3 2 0 9 3 2 0 5 1 6 4 XoY xoy xex yeY exp 2 3 exp 2 exp 3 car exp est une fonction croissante Calculs sin 7 3 7 0 1 attention sin n est pas monotone Sur ordinateur utiliser les arrondis dirig s pr vus par la norme IEEE 754 APMEP Lyon 16 avril 2003 39 N Revol INRIA Arithm tique par intervalles avantages Calcul garanti le r sultat cherch appartient l intervalle calcul Information globale on sait encadrer l image d une fonction sur tout un intervalle Th or me de Brouwer Schauder si f T C J alors f admet un point fixe dans J Application a Newton Algorithme de Hansen pour l optimisation globale APMEP Lyon 16 avril 2003 40 N Revol INRIA Arithmetique par intervalles exemple d algorithme Algorithme de Newton par intervalles Hansen amp Greenberg 1983 Mayer 1995 van Hentenryck et al 1997 tangente de plus faible pente tangente de plus grande pente tangente de plus grande pente tangente de plus faibl pente X k 1 X k X k X k 1 APMEP Lyon 16 avril 2003 41 N Revol INRIA Arithm tique par intervalles optimisation globale d une fonction continue APMEP Lyon 16 avril 2003 42 N Revol INRIA Arithm tique par intervalles algorithme de Hansen Hansen
13. n parall le Complexit O 1 si on a assez de ressources de calcul Remarque si 5 2 les conditions 2a gt b 1 et a lt b 1 ne peuvent pas tre satisfaites simultan ment Autres algorithmes avec les chiffres 1 0 et 1 pour la base 2 APMEP Lyon 16 avril 2003 12 N Revol INRIA Calculer a l cole primaire les entiers Multiplication 9 NI O e r CO N N N Orv O1 OF 1 8 3 N O1 9 8 4 Complexit de cette multiplication de 2 nombres n chiffres O n APMEP Lyon 16 avril 2003 13 N Revol INRIA Multiplication des paysans russes ou comment viter d apprendre ses tables of 86 4902 5 56 114 43 228 21 450 10 912 5 1824 2 3048 1 APMEP Lyon 16 avril 2003 14 N Revol INRIA Multiplication des paysans russes ou comment viter d apprendre ses tables of 86 4902 5 56 114 43 228 21 450 10 912 5 1824 2 3048 1 4902 APMEP Lyon 16 avril 2003 15 N Revol INRIA Multiplication on peut aller plus vite Si A et B s crivent chacun avec 2n chiffres en base ax0 ax B by by A x B agyby8 agb abg arbr soit 4 multiplications de nombres 2 fois plus court Multiplication de Karatsuba On peut aussi crire le produit comme AXB apby G7 ax ar by br apnbr arb 8 azbr avec 3 multiplications de nombres 2 fois plus court on multiplie 2 nombres de n chiffres en O n
14. n pr cision fixe intervalles en pr cision arbitraire Comment choisir selon ses besoins e rapidit e pr cision e garantie APMEP Lyon 16 avril 2003 47 mais aussi en ligne stochastique paresseuse N Revol INRIA Plan de l expos e Algorithmes pour l arithm tique exacte cole primaire e Algorithmes pour l arithm tique flottante notation scientifique e Arithm tique par intervalles e Complexit APMEP Lyon 16 avril 2003 48 N Revol INRIA La classe P D finition P probl mes pour lesquels il existe un algorithme de r solution en temps polynomial en la longueur des entr es Exemples addition O n pour 2 entiers n chiffres multiplication O n log n log log n pour 2 entiers n chiffres division O M n pour 2 entiers n chiffres pgcd O M n logn pour 2 entiers n chiffres tester la primalit d un entier n chiffres ao t 2002 Sur quel ordinateur sur un mod le th orique de machine appel machine de Turing cest la m me sur tout ordinateur r el et avec tout langage de program mation APMEP Lyon 16 avril 2003 49 N Revol INRIA Machine de Turing APMEP Lyon 16 avril 2003 50 N Revol INRIA R duction d un probleme un autre Ex la division se ram ne la multiplication Pour calculer A B avec et B deux entiers n chiffres on cal cule X 5 B un inverse approch de B multipli par 8 puis Q Ax
15. r g rer le temps Mode d emploi du chronom tre e presser sur le bouton A pour s lectionner le mode chronom tre e presser sur le bouton C pour d marrer arr ter le chronom tre e presser sur C pendant 3 secondes pour remettre le chrono z ro Assembleur langage de tr s bas niveau compr hensible par le chrono l ordinateur APMEP Lyon 16 avril 2003 4 N Revol INRIA Complexit _ Oc an glacial _ We P Etats d Europe gt S j N y pe x VA 7 S mgee ODO M diterran e K carte http www cfdp ch geofri APMEP Lyon 16 avril 2003 5 N Revol INRIA Complexit Reachability Sur une carte routi re avec n villes peut on aller de Paris Copenhague de Berlin Dublin Algorithme pour trouver la r ponse en O n Probleme du voyageur de commerce Sur une carte de France m tropolitaine avec n villes comment tablir une tourn e la plus courte possible qui passe une fois et une seule par chacune des n villes Aucun algorithme pour trouver la r ponse en O n 7 APMEP Lyon 16 avril 2003 6 N Revol INRIA Plan de l expos e Algorithmes pour I arithm tique exacte cole primaire e Algorithmes pour l arithm tique flottante notation scientifique e Arithm tique par intervalles e Complexit APMEP Lyon 16 avril 2003 T N Revol INRIA Calculer a l cole primaire les entiers Addition la main 1 1 1 2 3 4
Download Pdf Manuals
Related Search