Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

T Zf'civen-fcure matrTiémaùique Les algorit Au cœur du raisonnement ËDiTiONS PO

T Zf'civen-fcure matrTiémaùique Les algorit Au cœur du raisonnement ËDiTiONS POLE HSn'^ai ISSN 0987-0806 Bibliothèaue Ij'avGTvtut'e mathématrîq.ue Tangente Hors-série n" 37 Les algorithmes Au cour du ralsonuement ËDiTiONS POLE © Éditions POLE - Paris 2009 Toute représentation, traduction, adaptation, publication ou reproduction, même partielle, par tous procédés et sur tous supports, en tous pays, faite sans autorisation préalable, est illicite et exposerait le contrevenant à des poursuites judiciaires. Référence : loi du II mars 1957. ISBN : 9782848841069 ISSN ; 0987-0806 Commission paritaire : 1011 K 80883 î? !/i Prochainement dans la Bibliothèque Tangente 1)] EDITIONS Les algorithmes Sommaire DOSSIER Les algorithmes dans l'histoire Les algorithmes ne sont pas nés avec l'informatique. Par exemple, l'algorithme d'Euclide est vieux de plus de 2 GOO ans ! On trouve également des descriptions précises d'algorithmes dans la Chine ancienne. Avant d'être des programmes informatiques, les algorithmes sont des objets mathématiques. Mohammed al-Khwarizmi et son temps Aux racines de l'algorithme Les algorithmes du secret : la cryptographie Alan Turing et sa machine Lady Augusta Ada King, comtesse de Lovelace Algorithmes élémentaires et programmation On rencontre de nombreux algorithmes dans l'histoi re des mathématiques. De nos jours, les opérations manuelles auxquelles les algorithmes donnaient lieu ont laissé la place aux programmes informatiques. De l'algorithme au langage de programmation Les bases de la programmation Les tests de primalité Calcul de racines carrées : l'algorithme de Bahylone Des algorithmes pour créer le hasard Les fractions égyptiennes Les mariages stables existent Sous l'ordinateur, les booléens N'abusons pas des organigrammes ! Programmer l'algorithme d'Euclide (suite du sommaire au verso) Hors série n" 37. Les alg m DOSSIER nigorithmes classiques et jeux Les mathématiques ont donné naissance à une multi tude d'algorithmes, dans tous les domaines : théorie des nombres, topologie, mathématiques financières, recherche opérationnelle, théorie des graphes, mathématiques récréatives... Équations récurrentes en finance La programmation fonctionnelle Gagner au jeu grâce au noyau d'un graphe Le pivot de Gauss L'algorithme du simplexe La tour d'Hanoï Comment explorer un lahjrinthe ? DOSSIER Limites et performances Ce n'est pas tout de savoir structurer un raisonnement répétitif à l'aide d'un algorithme. Il faut aussi prouver son efficacité et chercher à minimiser le nombre d'opé rations qui vont intervenir dans son exécution, même si c'est l'ordinateur qui doit les effectuer. Complexité et temps d'exécution Veni, divisi, vici Les algorithmes de tri La programmation structurée La magie de la récursivité Itération et point fixe La gloutonnerie appliquée à la compression Codes correcteurs d'erreurs La multiplication rapide Problèmes Solutions En bref Des algorithmes à la folie 59, 63, 68, 74, 75, 83, 84, 85, 88, 89, 95, 98, 99, 102, 103, 104, 105, 106, 111, 121, 125, 129, 135, 141 Tangente Hors série n° 37. Les algorithmes 9, 22, 27, 32, 33, 53, 149 Mohammed al-Khwarizmi et son temps Ifistoire de la cryptographie P-14 Alan Turing et sa machine p. 16 Lady Augusta Ada King, comtesse de LoVelace p. 20 L' ' \ ' Les algorithmes ne sont pas nés avec rinfprmatique. Par exemple, l'algorithme d'Euclide est^eux de plus de 2 Goo ans ! On trouve également des descriptions précises d'algorithmes dans la Chine ancienne. Avant d'être des programmes informatiques, les algorithmes sont des objets mathématiques. Hors-série n° 37. Les algorithmes Tangente HISTOIRES par Bertrand Hauchecorne mohammed al-Khuiarizmi et son temps Le mot français « algorithme » provient du nom d'un savant arabe du IX® siècle. On lui doit plusieurs méthodes pour le calcul effectif de racines d'une équation du second degré. C'est également grâce à lui que se diffuseront les chiffres arabes en Occident. Couverture d'une copie du premier livre d'al-Khwarizmi. jLJi W ir •S ! », •' •* h fli f-'t t.- gfigg*>gEi83£3iaê^^ Cinquante ans après son installa tion à Bagdad (capitale de l'ac tuel Irak) en 762, le califat abbasside était au summum de sa splen deur. Haroun al-Rachîd, lettré éclairé, fut très occupé à mater les oppositions intérieures et extérieures qui mena çaient la stabilité du califat. La maison de la sagesse Après un début de règne agité, son fils et successeur al-Mamûn, après avoir fait disparaître son frère, se consacra au développement des arts et de la cul ture, en particulier scientifique. Il ouvrit la bibliothèque personnelle de son père pour créer la Bayt al-Hikma, c'est-à-dire la Maison de la sagesse. Les savants s'y retrouvaient pour consulter des ouvrages. C'est là que furent traduits en arabe de nombreux textes scientifiques grecs, permettant ainsi la conservation d'un grand nombre d'entre eux. C'est à cette époque que Muhammad ibn Musa, né en 788 probablement à Khiva, vint se fixer à Bagdad. Dans la capitale abbasside, il est connu sous le nom de Muhammad al-Khwarizmi, d'après le nom de sa contrée natale, le Khwarezm, correspondant à l'ouest de l'Ouzbékistan actuel. On sait peu de choses de sa vie sinon qu'il fréquenta assidûment la Bayt al-Hikma où la Tangente Hors-série n°37. Les algorithmes convergence des cultures grecques et indiennes lui permit de construire une œuvre fondamentale en mathéma tiques, présentée en deux ouvrages écrits vers 830. La résolution des équations Le premier ouvrage al-Kitâb al-mukh- tasar fâ hisâb al-jabr w'al-muqâbala, le Livre de l'explication du calcul de la remise en place et de la simplifica tion, a donné son nom à l'algèbre. Contrairement aux mathématicien grecs, al-Khwarizmi détaille des méthodes effectives de résolution d'équations. Il les traite avec des exemples tirés d'expériences pra tiques. Cependant, sachant son lecteur peu familiarisé aux nombres négatifs, il transfert toute quantité négative de l'autre côté du signe égal pour le rendre positif : c'est al-jabr, la remise en place. Par exemple, l'équation en notations actuelles x' - 23 = 16 - lOx devient x' H- lOx = 16 -(- 23. Al-muqâbala est la simplification ; ainsi, l'équation précédente devient alors X- H- lOx = 39 (voir l'encadré). Al-Khwarizmi nous présente une exposition complète de la résolution des équations du premier et du second degré. L'inconnue, que nous notons x dans cet article, s'appelle la racine et, comme il a éliminé tout nombre néga tif, il distingue six cas et les traite sur des exemples qui se généralisent sans difficulté pour toute équation de même type. 11 considère ainsi : - Carrés égaux aux racines, c'est-à-dire de la forme ax^ = bx ; - Carrés égaux à un nombre, soit ax^ = c ; - Racines égales à un nombre, soit bx = c \ - Carrés et racines égaux à un nombre, soit ax^ + bx = c ; LES ALGORITHMES... D'al-Khwaiizmi à algoriOime Le deuxième ouvrage n'est connu que par sa traduction latine, effec tuée probablement par Adélard de Bath dans la première moitié du XIL siècle. Le manuscrit était alors connu sous le nom de dixit Algorizmi - ainsi disait al-Khwarizmi- ou de Algoritmi de numéro Indorum - al- Khwarizmi, au sujet des nombres indiens. Comme son nom l'indique, celui-ci présentait le maniement des chiffres arabes, en fait introduits par les Indiens au VIP siècle de notre ère. Algoritmi est une latinisation du nom du mathématicien arabe. A par tir du XIIP siècle, on appelle algoris- me le calcul utilisant les chiffres arabes et algoristes ceux qui s'y adonnent. Influencé par le grec arithmos qui signifie nombre, ce mot devient algorithme et semble alors presque le jumeau du mot logarith me, créé sur le grec par John Neper au début du XVIP siècle. Il ne prend son sens actuel qu'au XIX" siècle, et devient d'utilisation courante grâce au développement de l'informatique depuis la Seconde Guerre mondiale. Hors-série n° 37. Les algorithmes Tangente HISTOIRES Mohammed al-Khwarizmi Résoudre +I0;r= 39 avec al-Khwarizmi Un carré et lo racines sont égaux à 39 unités, quevautla racine ? Rappel : la racine correspond à ceque nous appelons l'inconnue. Méthode algébrique : Onprend la moitiédes racines (c'est-à-dire5) ; on la met au carré, soit 25, que l'on additionne à 39, soit 64. Prenons alors la racine carrée de ce nombre, soit 8, et ôtons-lui la moitié des racines : la solution est donc 8-5 = 3. C'est magique, direz-vous ! Pas plus que la méthode classique avec le discriminant; c'est un algorithme efficace pour toutes les équations du type + bx = c, où b et c sont des réels positifs. Méthode géométrique : Tracer un carré de côtéx unités de mesure. Répartir les lox en quatre rectangles de côtésx et 10/4 apposés aux quatre côtés du rectangle. La surface totale de la figure est donc x^ H- lox, soit 39. Compléter cette figure en un carré en y ajoutantauxquatrecoinsdescarrésde côté5/2. Lenouveau carréobtenu a doncpour surface39 +4.(5/2)^= 64 = 8^. Or le côtédu carréinitialest x alorsque celuidu nouveaucarré est 8, donc x = 8 - 2 . 5/2 = 8-5 = 3. 2,5 2,5 2,5 2,5 X je X je X X 2,5 2,5 2.5 2,5 Méthode actuelle : x^ 4- lox=(x+5)^ -5" =39,donc (x+5)^ =39+25=64=8% donc x+5 =8oux+5 =-8, soitx =3oux=-13.Reprenez laméthode algébrique : vous voyez bienpourquoi onprend la moitiédesracines !Biensûr, à son époque, al-Khwarizmi ne pouvaitconsidérerquelesracinespositives(ilne trouvait pas -13). De nos jours, on effectue l'algorithme suivant : A = 10^ - uploads/Science et Technologie/ les-algorithmes-au-coeur-du-raisonnement.pdf