Algorithmique au Lycée
Contents
1. 5000 Il importe d abord de noter que la progression de pr cision si elle est attendue en g n ral n a rien d obligatoire Ainsi l une des simulation de la Figure 11 avec n 100 donne t elle la valeur approch e n 3 0303 qui est meilleure que l une des simulations obtenue avec n 1000 pour laquelle n 3 0120 L observation de l ensemble des quatre simulations pour n 100 1000 5000 montre n anmoins une tendance l am lioration r sum e par le tableau suivant moyenne Crau Qualitativement l erreur appara t ici comme d croissant d un facteur 3 environ quand on passe de n 100 n 1000 puis d un autre facteur d environ 2 en passant de n 1000 n 5000 Si le signe de l erreur est impr visible la d croissance de l erreur attendue ob it elle des principes bien connus depuis plus de deux si cles gr ce De Moivre Gauss et Laplace LASER ET O 1000 2000 3000 4000 5000 F s 12 L volution au cours du temps de cinq simulations n 5000 s 2 z 3 L estimation de est obtenue en comptant la proportion de succ s c est dire T le nombre de fois o l aiguille intersecte une parall le lors de n essais rapport n On constate facilement que ce nombre de fois est une variable al atoire binomiale quivalente au lancer n fois d une pi ce biais e la probabilit tant de tirer face T par exemple Soit X c2. l ment de la forme p4 avec k entier naturel tel que U uU E _ gk JG flu B Pa lt f u En particulier si k 0 on retrouve la m thode de Newton 5 4 Suites s ries On peut exp rimenter Proc dure S rie harmonique Entr es n entier Sorties s r el Initialisation u 0 3 1 Pour ide 1 n faire u e u i partir de cet algorithme peut on conclure que la s rie harmonique diverge On pourra comparer avec la s rie suivante Proc dure S rie divergente Entr es n entier Sorties s r el Initialisation u 0 i Pour de 1 n faire u lt u 100 Syst mes dynamiques 1 tudier de mani re exp rimentale les bassins d attraction des points fixes du syst me dynamique u lt f u f est par exemple la fonction polyn me 2 ca x4s 2 On donne la m thode de calcul suivante Proc dure Syracuse ou Collatz Entr es n gt 0 entier Initialisation u n Tant que u 1 faire si u pair faire u lt u 2 3u 1 sinon faire u lt La question est encore ouverte de savoir si pour toute donn e de d part n la proc dure Syracuse s arr te On peut donc exp rimenter librement Par exemple on peut crire un programme qui a pour valeur le maximum des termes atteint partir du point de d part n ou le nombre d it rations n cessaires pour revenir 1 ou le nombre de changements de sens de variation i e de parit et
3. donc avec 3 h 1 le SLM dt LM 0 2 L erreur au bout d un pas de temps est donc de l ordre de 2 Par une variante de l argument pr c dent on peut montrer que l erreur augmente chaque pas de temps d au plus O A2 Pour t fix il faut O 1 h pas de temps d o finalement une erreur en O h Note historique Euler a utilis ce proc d pour l tude de probl mes de calcul de courbes optimales du type inf LOO O4 PO yo I yi avec L R x R R On a ensuite appel cette classe de probl mes le calcul des variations en r f rence une approche de Lagrange plus simple car elle vite tout argument de discr tisation Cependant la m thode d Euler reste la base des proc d s d approximation num rique de la solution de 1 dont on ne conna t pas de solution explicite dans la plupart des applications 5 1 1 Fonction exponentielle On peut tre un peu plus pr cis dans le cas de l quation diff rentielle y y pour laquelle le sch ma d Euler s crit Ven Yet A y 1 Montrer que la convergence de l approximation que nous admettons implique la formule TY eT lim fui n 0 n N B On peut ventuellement justifier la formule en prenant le logarithme de chaque membre puis en effectuant un d veloppement limit au premier ordre 2 Soit y la fonction obtenue par interpolation lin aire entre les points kh y k 1 Supposons par exemple y
4. 10 2 1 5 0 0 2 0 4 0 6 0 8 1 1 2 1 4 t F1G 10 Buffon Fronti res des domaines du plan t y pour a 1 b 1 5 On suppose b lt a Les deux v nements y b sin f 2 2a et y b sin f lt 0 sont disjoints un ensemble de probabilit nulle pr s La probabilit pour qu il y ait intersection est donc gale au rapport de l aire T T e Ra Qa bsint dt bsintdt 2b Paire du rectangle 0 7 2 x 0 2a La probabilit cherch e est donc p 2b Ta Dans le cas particulier a b la longueur de l aiguille est gale la largeur des lames du parquet on obtient p T Si b gt a les deux v nements y b sin f 2 2a et y b sin f lt 0 ne sont plus disjoints la probabilit de v nement y b sin f gt 2a ou y b sin f lt 0 n est plus la somme des deux probabilit s Application En simulant le lanc de n aiguilles de longueur gale la largeur du parquet la fr quence observ e f des cas d intersections est une approximation de 2 VEREN T En comparant les approximations d cimales de m que nous connaissons avec le T 2 O quotient 4 on peut observer l influence de n sur la pr cision obtenue Proc dure Calcul de n Entr es n entier Sorties p r el positif Initialisation i j t y p 0 0 0 0 0 Tant que j lt n faire nombre al atoire compris entre 0 et z gt t nombre al atoire compris entre 0 et 2 y Si y
5. cision donn e en temps d x cution sur calculatrice ou ordinateur Pourquoi 7 Graphes recherche de la distance entre deux sommets Des exemples d utilisation des graphes sont vus en classe terminale On consid re un graphe avec n sommets certains de ces sommets tant reli s par des ar tes de longueur donn e On fixe deux de ces sommets et l on cherche la longueur d un chemin de distance minimale qui les joigne C est un probl me pratique tr s courant que chacun a rencontr toute carte routi re est un graphe de ce type D s que le graphe a plus d une dizaine de sommets il n est pas vident de trouver le plus court chemin L algorithme le plus imm diat est de consid rer tous les chemins joignant les deux sommets fix s et de chercher le plus court Cet algorithme est tr s inefficace on peut bien s r se limiter aux chemins sans cycles donc de longueur born e par le nombre de sommets mais m me comme cela le nombre de chemins possibles reste tr s grand en g n ral exponentiel en le nombre de sommets Une m thode plus efficace consiste proc der de proche en proche si l on trouve un plus court chemin entre les deux sommets qui passe par S4 S Sp alors son d but est aussi un plus court chemin du premier sommet S puis S etc On va donc commencer par chercher un plus court chemin du premier sommet un sommet quelconque puis ajouter un nouveau sommet chaque tape de l
6. gt 0 Montrer par r currence que y x a une d riv e toujours inf rieure e et donc est toujours inf rieure e 3 tude exp rimentale de l ordre d erreur Prenons y 0 1 v rifier que y 1 e est d ordre 1 en A soit y 1 e Ch o h Pour cette tude on recommande de tracer In y 1 e en fonction de In h pourquoi Comment obtenir une estimation de C avec ce graphique Combien de points faut il pour avoir une estimation de cette constante Que se passe t il si A est trop petit ou trop grand Pour ce dernier point si A est trop petit erreurs num riques excessives si h est trop grand effets du second ordre Sur cet exemple l mentaire on peut aussi tudier la m thode du point milieu 1 ru Yk 1 501 k 1 1 Montrer que si f x x ce sch ma se ram ne encore une r currence lin aire sur y de la forme oh Yk l Yk 1 h 2 2 Par une tude exp rimentale montrer que l erreur est cette fois proportionnelle A2 3 Avec la formule montrer que 1 Va rise ya O 4 Comparer la m thode d Euler la m thode du point milieu simplicit de programmation pr cision quelle est la plus efficace au total T FE F3 F4 Fev y F v F7 FE ad paa Zoom Trace Regraph Math Draw A ii FIG 7 Solutions exactes et approch es avec des pas de 0 2 et 0 05 5 1 2 Oscillateur harmonique Soit l quation diff
7. il y a une quantit suffisante de poissons On suppose e t 0 et on pr l ve le plus possible si la population d passe une quantit donn e 0 siy lt y iJOS ya CM Sinon o y gt 0 et ay lt Cy pour assurer le r gime asymptotique Le second membre tant discontinu l quation diff rentielle n a pas de solution d riv e continue en g n ral Nous n essaierons pas de donner un sens math matique pr cis l quation diff rentielle on peut par exemple invoquer la th orie des op rateurs maximaux monotones D Signalons cependant la possibilit de d finir une solution comme limite de l approximation obtenue avec le sch ma d Euler si cette limite existe on peut en faire une tude num rique 1 Construire une solution explicite par raccordement des intervalles sur lesquels y lt y et y y On admet pour l instant et on le retrouvera dans les exp riences num riques que si y f y alors y f y pour tout t gt t 2 Montrer que le syst me dynamique est bien pos au sens de Hadamard y f d pend de fa on continue de y 0 3 On consid re l approximation obtenue avec le sch ma d Euler Montrer que le r gime asymptotique est une oscillation autour de x y avec une amplitude en O h 4 Enfin on pourra aborder la m thode d Euler implicite d finie par Yra Yk AAY ky y 5 qui s crit ici Veau Ve HACAYpy yen k l pour laquelle
8. la valeur de x donn e par la i me quation Pour r soudre le syst me il suffit de r p ter la proc dure Pivot de Gauss essai avec le syst me S Pour le faire convenablement on modifie l g rement cette proc dure pour pouvoir la composer avec elle m me Proc dure Pivot de Gauss Entr es T Tableau n x p d l ments du corps k L liste de couples d entiers Sorties S Tableau 7 x p d l ments du corps k Liste des pivots liste de couples d entiers Initialisation E T s num ro de la ligne du dernier l ment de L t num ro de la colonne du dernier l ment de L Pour j de 1 p faire Pour de s 1 n faire si a L 0 alors faire Pivot ij et K L ij E lt Li aij pour lt n et i faire E amp E a jE retourner T K et sortir retourner Pivot fin On obtient donc Proc dure R solution Entr es T Tableau n x p d l ments du corps k Sorties R Tableau n x p d l ments du corps k Liste des pivots liste de couples d entiers Initialisation U T listevide P 0 0 Tant que Pivot fin faire U Pivot de Gauss U Variantes Il existe de nombreuses variantes de cet algorithme Celle que nous venons d expliciter tient pour connues les proc dures de calcul dans le corps k des coefficients du syst me de d part Cependant on sait que ces proc dures de calcul ne sont pas aussi simples qu il y para t Par exemple pour des
9. point la parall le une droite Marquer le point d intersection de deux droites que l on suppose d j crites ou donn es On remarque que la premi re de ces proc dures n est pas d terministe F1G 6 Conjugu harmonique construction On d montre ensuite Thal s que le r sultat convient et que l algorithme propos s arr te au bout d un nombre fini de pas pour toute donn e convenable Reste v rifier que le point N trouv est le seul point de la droite D diff rent de M qui convient Si on permet l utilisation d un instrument de mesure des longueurs et les multiplications et divisions de r els il existe un autre proc d mesurer MA et MB calculer Ma et en d duire par exemple une mesure de NA Cette d marche est tr s proche de la preuve de l unicit de la solution 1 Les proc dures l mentaires voqu es au cours de l exemple pr c dent sont toutes int ressantes programmer de m me que les constructions de la m diatrice d un segment de la projection orthogonale d un point sur une droite du cercle circonscrit un triangle Les fonctions primitives sont celles de la r gle et du compas c est dire Choisir un point dans le plan Tracer la droite par deux points Tracer le cercle de centre donn passant par un point donn Marquer le point d intersection de deux droites d une droite et d un cercle 2 On note que les objets manipul
10. pour f uniforme sur 0 7 2 revient choisir uniform ment un point sur le cercle unit et en extraire la seconde coordonn e Choisir un tel point peut se faire en choisissant un point P x y uniform ment et au hasard l int rieur du cercle unit puis prendre l intersection du rayon vecteur OP avec le cercle unit Tirer P lui m me s effectue en tirant au hasard une paire x y o x y sont uniformes et ind pendants dans le carr 0 1 x 0 1 et en rejetant les points qui ne conviennent pas Le programme est alors Proc dure Tirage de sin f pour t uniforme dans 0 x 2 r p ter tirer x y uniform ment dans 0 1 jusqu x y lt 1 et x y 0 retourner ____ 2 2 x y EXERCICE crire une proc dure compl te d estimation de m par simulation de l aiguille de Buffon qui n utilise que les op rations X d Ces m thodes de rejet s av rent utiles pour le calcul d int grales ou de volumes de corps dans des espaces un grand nombre de dimensions Elles sont alors connues sous le nom de m thodes de Monte Carlo en l honneur de son casino EXERCICE valuer l aire sous le quart de cercle en adaptant la proc dure de tirage de sin f Pour 1000 appels au g n rateur uniforme quelle m thode donne la meilleure estimation de 7 l aiguille de Buffon ou l estimation de l aire sous le quart de cercle Qu est ce qui para t le plus rapide pr
11. sin f gt 2a ou y sin f lt 0 faire i 1 i 2n faire p gt i Affichage des rationnels obtenus et d une approximation d cimale Une observation s impose ici les langages de programmations usuels offrent une primitive souvent appel e random de g n ration pseudo al atoire qui approxime efficacement un al a v ritable par une succession de transformations d terministes bien con ues initialis e par par un v nement ext rieur impr visible comme un temps d horloge mesur en microsecondes Ces g n rateurs pour peu qu ils soient convenablement r alis s suffisent pour des simulations mettant comme ici seulement en jeu quelques millions ou quelques milliards d appels Au del on pourra puiser dans la tr s vaste litt rature sur le sujet notamment Knuth Chapitre 3 Cet exemple jouet pose deux types de questions L une est de nature statistique Quel sens peut on donner un r sultat de simulation L autre est de nature logique et algorithmique l algorithme de simulation calcule le nombre x par simulation mais il poss de le d faut d utiliser une fonction trigonom trique et la valeur de x elle m me Peut on donner un algorithme de calcul de T par simulation qui n utilise que les op rations arithm tiques usuelles 1 F2 F3 F4 FS F6 1 F2 F3 F4 FS F6 ET contro1 1 0 Var F ind Mode F lcontror lier node sEuffon n 5 ip approx p Func EndFunc iLocal i j t
12. test avec 2 puis les entiers impairs inf rieurs yN par recherche de a et b entiers tels que N a b ou encore par recherche de a pour que a N soit un carr parfait am lioration algorithme de Fermat 8 Recherche de nombres amicaux 9 Recherches de nombres parfaits abondants d ficients 10 Recherche de triplets pythagoriciens entiers quelconques avec la contrainte un des 3 entiers est fix ou le plus petit des 3 entiers est fix 8 2 Analyse 8 2 1 Suites num riques 1 Calcul des termes d une suite r currente 2 Vitesse de convergence d une suite r currente monotone convergente 8 2 2 Approximation de r els 1 Calcul d une approximation d une fonction par une fonction affine 2 Recherche approch e d une solution d une quation diff rentielle du type y ay b par la m thode d Euler 3 Recherche d une aire sous une courbe par la m thode des rectangles ou des trap zes 4 R gression affine 8 3 Statistique 1 Calculs de param tres statistiques moyenne cart type m diane quartiles d ciles 2 Algorithmes de simulation Lancements r p t s d une pi ce ou d un d comptage des occurrences Lancements r p t s d une pi ce ou d un d truqu s comptage des occurrences Lancements r p t s de 2 ou 3 d s calcul de la somme des faces comptage des occurrences Lancements r p t s d un d comptage du nombre d
13. 4 p 0 gt i For 0 n randt 4n 23t spand tzau 7 If ytsintt 2 or y sin t lt 0 Then i 1 gt i ndIF EndFor 12 n i3p PIN RAD AD DE MN RAD AUTO DE 1 F2 F3 F4 FS F6 4 F2 F3 F4 FS F6 ui Rigebra c31c other Pron1o Clean up SET fnis bralcsic bther Pranto Ciean up a buffoni TFT buf Fon 1000 27 3 05343511450 buffon 180 2 3 27868852459 u puffon 1000 258 301204819277 z buffon 100 caor 2 857142857143 y puffon 1000 2500 3 129890453283 buffont100 Sn 3 03030303030 Es buf font 100 50 17 2 94117647059 gt buffon 1000 E 3 21027287519 buf fon 1000 MAIN DEG AUTO FUNC 4930 MAIN DEG AUTO FUNC 4730 4 F2 F3 F4 FS F6 SET fnis bralcsic bther Pranto Clean up buffon 5000 E 3 18775900542 buffon 5000 E 3 13577924114 buffon 5000 LE 3 21336760925 buf font 5000 E 3 094059405394 buf fon 5000 MAIN DEG AUTO FUNC 4930 FIG 11 Un exemple d implantation sur une calculatrice du commerce et quelques essais avec 100 1000 et 5000 lancers d aiguilles 6 1 Statistiques et fluctuations L observation des r sultats montre quelques ph nom nes statistiques simples Clairement les r sultats de simulation fluctuent Clairement aussi augmenter le nombre de simulations end augmenter la pr cision du r sultat Ces deux ph nom nes sont illustr s par la figure 12 qui montre l volution de l estimation de T au cours du temps lors de 5 simulations avec n allant jusqu
14. Algorithmique au Lyc e Commission de R flexion sur l Enseignement des Math matiques suite du num ro 445 4 Alg bre et g om trie 4 1 Constructions Dans les probl mes de construction on demande de d terminer un algorithme qui partir des donn es fournit le r sultat escompt en utilisant seulement des fonctions pr cis es Les fonctions utilis es sont g n ralement d crites par l expression la r gle et au compas On peut imaginer d autres fonctions permises par exemple travers l usage d autres instruments L usage du double d cim tre est g n ralement proscrit Les entr es et les sorties ont n cessairement une forme particuli re qui exclut souvent les nombres Donnons quelques exemples Proc dure Conjugu harmonique Entr es A B M points du plan distincts deux deux et align s sur une droite D Sorties N point de la droite D tel que z E MB Choisir un point w en dehors de D Tracer la droite A passant par M et w Mener la parall le 6 A par A Mener la parall le A par B Tracer la droite D par A et w Tracer la droite D par B et w Marquer le point d intersection AA des droites et D Marquer le point d intersection BB des droites et D Tracer la droite DD par AA et BB Marquer le point d intersection N des droites D et DD On a utilis ici les proc dures Choisir un point dans le plan Tracer la droite par deux points Mener par un
15. Examinons maintenant des mod les simples du premier ordre mais o apparaissent des termes non lin aires et une variable dite de commande qui peut varier dans un certain domaine On consid re le syst me dynamique ay e r clt dans lequel y f repr sente la population de poissons d une lagune a gt 0 est le taux de reproduction e f un terme de perturbation apports de l oc an suppos connu et c t le pr l vement de p che la commande 5 2 1 Mod le lin aire avec saturation On suppose la commande c f proportionnelle la population de poissons mais avec une saturation limitation des moyens de p che c t min by cu o b gt 0 On suppose e t constant 1 Dans le cas o e f est nul sait on calculer la solution de l quation diff rentielle On distinguera suivant les valeurs de a b et y 0 2 M me question quand e t est constant strictement positif ce qu on supposera dans la suite 3 On suppose e t constant strictement positif et a gt b Discuter l application de la m thode d Euler et donner une estimation d erreur 4 On suppose dans cette question c f proportionnel au carr de la population de poissons e t b OOF o b gt 0 On notera la diff rence concernant le r gime asymptotique et on tudiera si le mod le discret a le m me r gime asymptotique 5 2 2 R action tout on rien Dans ce mod le le p cheur ne sort le bateau que s
16. algorithme Si l on conna t d j un ensemble S de sommets pour lesquels on a trouv un plus court chemin l id e de l algorithme qui suit est de regarder tous les sommets li s par une ar te un sommet de S et de prendre parmi ces sommets le plus proche du sommet de d part On r sout ainsi l exercice de proche en proche Pour crire un programme il faut choisir une structure de donn es On supposera que les sommets sont num rot s de 1 n et que le graphe est repr sent par une matrice A de taille n X n o A i j est un r el positif qui donne la longueur de l ar te reliant i j Sil n y a pas d ar te reliant les deux sommets on posera par convention A i j c On va chercher le plus court chemin reliant 1 n On fait l hypoth se que le graphe est connexe sans cela si 1 et n ne peuvent pas tre joints la proc dure ne termine pas Il serait facile d ajouter un test suppl mentaire pour d tecter ce cas On peut d crire informellement l algorithme ainsi On initialise l algorithme en prenant 1 comme sommet courant en initialisant un vecteur des distances D par les valeurs provisoires D 1 0 et D i pour tous les autres Comme la valeur D 1 est videmment minimale on peut la marquer d finitivement l encre On r p te la suite d op rations suivante jusqu ce qu on ait marqu d finitivement le sommet n On note SC Sommet Courant le dernier sommet
17. c 6 Statistique et probabilit s les aiguilles de Buffon Le comte de Buffon 1707 1788 essentiellement connu comme naturaliste fut galement philosophe et math maticien Dans son Essai d arithm tique morale 1777 on trouve le fameux probl me de l aiguille Voici l nonc qu il donne Je suppose que dans une chambre dont le parquet est simplement divise par des joints parall les on jette en l air une baguette et que l un des joueurs parie que la baguette ne cro sera aucune des parall les du parquet et que l autre au contraire parie que la baguette croisera quelques unes de ces parall les On demande le sort de ces deux joueurs On peut jouer ce jeu sur un damier avec une aiguille coudre ou une pingle sans t te En notant 2a la distance entre deux parall les 2b la longueur de l aiguille t l angle de l aiguille avec la direction des parall les et y la distance du milieu de l aiguille la parall le la plus proche il y aura intersection si et seulement si y b sin f 2 2a ou y b sin lt 0 La valeur al atoire de y dans 0 2a est distribu e de fa on uniforme ainsi que celle de t sur 0 7 2 Les v nements possibles sont donc param tr s par le rectangle 0 x 2 x 0 2a muni de la loi de probabilit uniforme L v nement intersection avec l une des parall les est param tr par la r gion du rectangle y y 2 2a b sin t ou y lt b sin t cf la figure
18. c une d riv e seconde de signe constant on peut am liorer la fiabilit du r sultat en perfectionnant l algorithme 5 Il est cependant int ressant d observer le comportement du syst me dynamique fu f o u lt u d fini par une fonction polyn me par exemple coefficients entiers et d un point a de d part Quelles racines trouve t on Quel est leur bassin d attraction T F F3 Fi F5 F6 Ch bralce other Prano 1e ve mneuton 2 x4 5 x 2 1 10 SJ Done a 6073 7182 anewtonl2 xt 5 x3 2 1 103 Done sx 245586197691 MAIN EG AUTO FUNC 493 mneuton 2 x4 5 x5 2 3 10 7 Done ag 2 43034373303 MAIN EG AUTO FUNC 2 3 x4 5 x5 2 2 10 5 Done s neuton 2 ag 2 43033977318 neuton 2 x4 5 x3 2 1 5 10 Done so 845496517945 mneuton 2 x 5 x 2 1 8 10 Done ag 2 430340978 MATN EG AUTT FINC 575 F1G 9 Un exemple f x 2x4 5x3 2 Remarque Dans le cas o la m thode de Newton ne converge pas on peut la modifier de la mani re suivante Notons d x f 1f x le d placement de Newton en un point x On observe que pour gt 0 on a im OCTO Pada gt 0 E est de signe oppos f x un petit d placement dans la direction de Newton permet donc de trouver un point meilleur On peut proposer une m thode de Newton avec r glage du pas f J amp L id e la plus simple est de choisir comme le plus grand
19. calculs exacts sur Q les divisions peuvent faire cro tre les d nominateurs successifs par ailleurs pour le cas de calculs approch s la diff rence entre deux l ments tr s proches peut avoir comme r sultat un nombre dont l ordre de grandeur est tr s loign de celui des op randes et rendre tr s sensible le recours aux arrondis Les fa ons de rem dier ces difficult s sont diverses On peut effectuer une meilleure recherche du pivot pour laquelle le coefficient pivot sera par exemple le plus grand possible et pas le premier venu non nul Les questions effleur es ici conduisent la consid ration du conditionnement du syst me qui d passe nos objectifs On peut galement ne jamais diviser donc rester dans l anneau engendr par les coefficients du syst me de d part et consid rer la variante suivante de la proc dure Pivot de Gauss essai crite pour des coefficients entiers Proc dure Pivot de Gauss essai coefficients entiers Entr es T Tableau n x p d l ments d l ments de Z Sorties S Tableau 7 X p d l ments d l ments de Z Pour de 1 p faire Pour i de 1 n faire si a 0 alors faire Pivot ij pour de 1 n faire pecd a pa m b a 6 c a 8 E lt bE cE sortir Rang Si Liste des pivots i jl i j fin alors j j est la liste des indices des variables dites principales dans le processus de r solution choisi Pou
20. dissement 5 1 quations diff rentielles m thode d Euler Soit f une fonction de R vers R On consid re l quation diff rentielle YO V x20 x0 yo D La m thode d Euler consiste approcher la solution de 1 par la r currence Yai Mt AO k l Ici h gt 0 est le pas de temps destin tendre vers 0 et y repr sente une approximation de y kh On a pris la m me notation y pour la solution de l quation diff rentielle et son approximation sans risque de confusion On peut associer au pas A la fonction y d finie en interpolant lin airement entre les points kh et k 1 h y Gh y k 1 y t affine sur kh k DA On peut v rifier que si f est localement lipschitzienne on a une estimation du type D O x lt Crh te 0 T au moins si T est assez petit Nous admettons ce r sultat Remarque On peut tout de m me analyser ce qui se passe pour t 0 A Puisque y t est primitive de sa d riv e on a 0 FO dt 2 et aussi y y 0 f y 0 df donc l erreur e y h t v rifie le lt IFO fo ldr SOOD for Soient L gt 0 et e gt 0 telles que f est lipschitzien de constante L sur la boule B y Si h est assez petit alors pour tout fe 0 A on a y f B y et donc ll FILO Olds Lf IO yo ldt 6 De plus 2 implique y 9 y lt Mt o M sup f y B noter que M lt fVol EL est bien finie
21. e lancers jusqu l apparition du 6 R alisation d un sondage sur un chantillon al atoire Marche al atoire dans le plan ou dans l espace 8 4 Math matiques discr tes graphes 1 Coloration d un graphe 2 Recherche de la plus courte cha ne entre deux sommets 8 5 Divers 1 G n ration du triangle de Pascal 2 Rangement d une liste par ordre croissant 3 M lange d une liste de fa on al atoire 4 R solution d un syst me lin aire par la m thode de Gauss
22. e marchandises de r seaux de distribution d allocation optimale de ressources probl mes d emploi du temps penser l affectation des quipages dans une compagnie a rienne etc Sur ces sujets voir par exemple le livre Graphes et algorithmes par M Gondran et M Minou Eyrolles 1979 8 Quelques algorithmes abordables au Lyc e On a dress ici une premi re liste de quelques algorithmes qui peuvent tre envisag s partir du programme actuel du Lyc e 12 8 1 Arithm tique 1 G n ration de la liste des nombres premiers inf rieurs un entier par le crible d ratosth ne 2 Recherche du PGCD de deux entiers par l algorithme d Euclide 12 On pourra consulter J Chabert et al Histoire d algorithmes Du caillou la puce Belin 1994 ainsi que Algorithmique et traduction pour calculatrice IREM de Grenoble 2000 Recherche du PPCM de deux entiers R solution de l identit de B zout par l algorithme d Euclide Test de primalit A A U Conversion du syst me d cimal au syst me binaire avec un test syst matique des entiers inf rieurs yN am lioration test avec 2 puis les entiers impairs inf rieurs yN am lioration test avec 2 puis 3 puis les entiers de la forme 6p 1 ou 6p 1 inf rieurs 4N 7 Factorisation d un entier en produit de facteurs premiers avec un test syst matique des entiers inf rieurs yN am lioration
23. e pour le probl me que l on cherche r soudre Il est utile d estimer le nombre d tapes qu il comporte pour pouvoir comparer avec d autres algorithmes Il est clair qu chaque grande tape on marque d finitivement un sommet il y a donc au plus n grandes tapes si n est le nombre de sommets Combien y a t il d op rations l mentaires dans une tape On se contente de recalculer D pour les sommets adjacents au sommet courant donc au pire n sommets puis de comparer les sommets non encore marqu s pour trouver le plus petit encore au maximum n op rations On voit que l algorithme se termine en au plus 2n op rations on peut raffiner l estimation n n 1 et m me mieux si le degr maximum d un sommet est major par d lt n On a donc un nombre d tapes qui est de l ordre du carr de n si l on compare avec l algorithme na f qui consiste comparer tous les chemins on voit que celui ci est en g n ral exponentiel en n donc beaucoup plus long d j pour des graphes de 50 sommets ce deuxi me algorithme est compl tement inutilisable alors que l algorithme de Dijkstra est quasi instantan pour un ordinateur Le probl me des plus courts chemins appartient au domaine de l optimisation combinatoire appel aussi recherche op rationnelle Les algorithmes de graphe y jouent un r le important Des exemples se rencontrent dans les probl mes de transport d lectricit d
24. ette variable al atoire on a tout d abord le fait que la variance de X est proportionnelle n De mani re quivalente l cart type de X est de l ordre de Jn et celui de a est de l ordre de L C est cet cart type qui n r mesure la dispersion des r sultats la pr cision de l estimation de lors de n essais T est tr s probablement de l ordre de T Ceci explique bien les donn es n num riques de la figure 11 ainsi que le diagramme de la figure 12 o les deux courbes continues repr sentant les fonctions 4 4 f x r gt f x n gt T ir r sument la tendance g n rale des estim es converger au cours d une simulation Plus finement la distribution de probabilit s de X est connue 0 08 ni N 300 250 0 06 200 0 04 150 100 0 02 50 0 55 60 65 70 75 80 o 0 5 0 55 0 6 0 65 0 7 0 75 0 8 F s 13 La loi binomiale pour n 100 et son approximation normale gauche les fr quences observ es des estimations pour 1000 simulations correspondant n 100 droite Cette loi de X lorsque n devient grand approche la loi de Gauss Ainsi un tirage de X fluctue t il al atoirement certes mais selon une r gle bien d finie La figure 13 montre l histogramme de la loi de X compar la loi de Gauss ainsi que ce que l on observe en effectuant un l
25. marqu l encre Pour tout sommet non encore marqu l encre et reli SC par une ar te on calcule la somme de la distance de SC et de la longueur de l ar te qui relie SC i On remplace l ancienne distance D i de 1 par la nouvelle distance si celle ci est plus petite sinon on laisse l ancienne distance Parmi tous les sommets non encore marqu s l encre on en choisit un de distance minimale et on le marque l encre On continue ainsi jusqu avoir marqu n l encre La distance calcul e de 1 n est alors la distance minimale cherch e De fa on plus formelle en utilisant une primitive marquer qu il est facile d implanter on obtient le programme qui suit Proc dure Plus court chemin algorithme de Dijkstra Entr es n entier matrice n X n valeurs r elles strictement positives ou o Sorties L r el Initialisation SC 1 D 1 0 Pour i de 2 n faire D i Marquer 1 R p ter calcul des nouvelles distances Pour i de 1 n faire Si non marqu D i inf D i D SC A SC i recherche du plus proche parmi les points non encore marqu s L SC 0 Pour i de 2 n faire si i non marqu et D i lt L faire L D i SC i Marquer SC Jusqu ce que n soit marqu Quand n est marqu L est la longueur d un plus court chemin joignant 0 n Cet algorithme est il efficace Cet algorithme peut sembler bien complex
26. ons enfin que Gauss qui est l origine de nombreuses m thodes de calcul matriciel effectif tait motiv par des consid rations tr s pratiques de m canique c leste l orbite de Pallas et de g od sie la triangulation de l tat du Hanovre voir les notes historiques du livre Histoire d algorithmes d j cit De nos jours ces m thodes interviennent via la discr tisation et les m thodes d l ments finis dans la plupart des r solutions num riques sur ordinateur bien s r d quations diff rentielles en m t orologie simulation d coulements fluides analyse num rique des syst mes m caniques etc 10 Ces questions de calcul effectif sont excellemment trait es dans les ouvrages suivants C Gomez B Salvy P Zimmermann Calcul formel Mode d emploi Exemples en Maple Masson 1995 P Dumas X Gourdon Maple Son bon usage en math matiques Springer 1997 5 Analyse int gration num rique La discussion de mod les dynamiques simples et motiv s pose assez vite des questions math matiques pour lesquelles l exp rimentation num rique peut tre source de compr hension L implantation de ces m thodes permet d aborder d une mani re simple et illustr e les concepts fondamentaux de la programmation boucles tests gestion de fichiers graphes Mais elle permet aussi d explorer des questions d analyse math matique sortant du programme dans l esprit de travaux d approfon
27. ot de 1000 simulations correspondant n 100 Noter que 2s 0 63661 et que le passage de a qui estime qui estime T et n T T est aussi asymptotiquement normal d borde sensiblement du cadre du programme n EXERCICE r aliser par simulation et discuter analytiquement On consid re une lection entre deux candidats A et B o l un des candidats b n ficie de 48 d intentions de vote l autre de 52 mais on ignore ces faits et l on ne sait pas qui a l avantage Quelle taille d chantillon un institut de sondage doit il prendre pour avoir environ 9 chances sur 10 de pr dire correctement le gagnant 6 2 Algorithmique de la simulation Les m thodes de simulation sont importantes dans diverses activit s des sciences de l ing nieur simulation de ph nom nes physiques de trafic routier de r partition de t ches dans les syst mes informatiques de calculs d int grales en dimension lev e de probl mes d optimisation combinatoire difficiles etc Ce domaine donne lieu une algorithmique riche On examinera simplement ici un probl me suscit par l aiguille de Buffon comment tirer y sin f lorsque f est uniforme dans 0 x 2 ce sans faire appel la valeur de x ni aux fonction trigonom triques Le r sultat est un programme de pur calcul de m par simulation partir des op rations arithm tiques de base compl t es par la racine carr e Il est clair que tirer sin f
28. r toute valeur donn e aux variables X j Up J l quation E a lt k lt r donne une unique valeur de x C est en cela que le syst me obtenu est dit r solu Lentier r est le rang du syst me Jusque l il n est pas clair que c est un invariant du syst me tudi Cela ne d coule pas simplement de l algorithme de r solution Le montrer revient tudier la notion de dimension En revanche on a construit explicitement une pr sentation de l espace des solutions muni d une projection sur k qui est aussi un isomorphisme lin aire Ind pendance lin aire relations Il est facile partir de la proc dure Pivot de Gauss d crire un algorithme qui partant d un syst me de vecteurs v v et d un vecteur v tous dans k d cide si v est combinaison lin aire des v v et si Oui donne les coefficients d une telle combinaison De m me il est facile d crire toujours partir de la proc dure Pivot de Gauss un algorithme d inversion d une matrice carr e n X n ou de calcul de son d terminant On montre que la complexit de ces algorithmes est en O n la mesure de co t tant le nombre des additions et des multiplications effectu es dans le corps de base Les consid rations pr c dentes montrent qu on doit parfois utiliser des mesures plus fines notamment si l on doit faire des calculs exacts avec des entiers des rationnels ou des polyn mes l par exemple Signal
29. rentielle F 1 Z y Z dont les courbes int grales sont les cercles centr s en 0 parcourus dans le sens trigonom trique On peut liminer y en crivant z z o 1 Interpr tation m canique ressort de masse unit une extr mit fix e en 0 longueur au repos n gligeable force de rappel proportionnelle et oppos e l allongement 2 Montrer la conservation de l nergie F 2 somme d une nergie de d formation et de l nergie cin tique 3 Montrer que la m thode d Euler tendue au cas d quations diff rentielles du second ordre conduit au sch ma Zu 2x hYes Ven Vk they Montrer que l nergie du syst me discret augmente par on note la norme euclidienne Grave P 4 Ge 70 P a Go 0 Interpr tation g om trique les tangentes au cercle sont ext rieures ce cercle 4 Montrer qu on a la relation de r currence suivante portant seulement sur z Zk 1 T 2Zk tZk h 2x1 qu on interpr tera comme une discr tisation de 4 5 Lien avec les suite r currentes comparer les solutions analytiques des syst mes continus et discrets 5 2 Un probl me de commande Dans les exemples pr c dents on a examin le comportement de la discr tisation par la m thode d Euler dans des cas o la solution analytique est connue ceci permet une estimation num rique des erreurs De plus la solution tait r guli re infiniment diff rentiable
30. s sont des points des droites des cercles du plan qui peuvent tre soit des primitives du langage soit recouvrir une repr sentation adapt e expression l aide de coordonn es trac l cran etc Les algorithmes en d pendent penser par exemple l intersection de deux droites 4 2 R duction d un syst me lin aire pivot de Gauss La r solution d un syst me lin aire est abord e au Lyc e de mani re exp rimentale sur des exemples Cette m thode de calcul conduit en fait un algorithme qui a de nombreuses variantes L tude de la complexit de ces algorithmes est int ressante tant donn e l importance des calculs lin aires dans les calculs effectifs On part d un syst me de n quations lin aires homog nes E E p inconnues Xi X Pour 1 lt i lt n l quation d indice i a pour coefficients a a Ce sont des l ments du corps k qui peut tre celui des r els des complexes mais aussi celui des rationnels celui des entiers modulo un nombre premier p ou pire encore on veut juste pointer ici que les calculs effectu s ne sortiront jamais du corps de d part On agence ces coefficients en un tableau n X p i e une matrice dont la ligne d indice i a pour l ments les coefficients de la i me quation Dans la suite on parlera indiff remment de la ligne du tableau ou de l quation correspondante On dispose des deux proc dures P1 Multiplier
31. si la perturbation reste petite et si y est proche de y la suite y reste gale y La r solution de l quation 5 est en soi un objet d tude Le grand avantage de la m thode implicite est qu elle vite les oscillations de la m thode d Euler explicite 5 3 M thode de Newton On part de la proc dure suivante Proc dure Newton Entr es f fonction a r el r el positif Sorties amp r el Initialisation u a fu Aa u fa gt faire u u Tant que f o 1 F2 F3 F4 FS F6 PT lcontroi 1 oluar Fina Mode shewton 3 Prgm av illhile sbscflx e cacf x Ix 0 gt E sa if x CCF x x Endlhile EndPram MAIN RAD AUTO DE FIG 8 Implantation de la m thode de Newton sur une calculatrice du commerce 1 Cette m thode des tangentes qui peut tre illustr e graphiquement conduit en principe une approximation d une racine de f 2 Quelles sont les fonctions conna tre pour mettre en uvre l algorithme valuer f et sa d riv e en un point faire le quotient le comparer et soustraire Comme il s agit chaque fois de valeurs approch es sauf cas particulier il est crucial de les avoir avec une pr cision largement sup rieure 3 Le test d arr t est il convenable Il m rite d tre discut 4 Dans chaque cas particulier par exemple si on dispose d un intervalle o f est deux fois d rivable ave
32. tous les l ments d une ligne d un tableau par un l ment inversible du corps P2 Soustraire d une ligne du tableau un multiple d une autre ligne Ces deux proc dures ont une propri t fondamentale leur r sultat i e le syst me obtenu a les m mes solutions que le syst me de d part En utilisant ces deux proc dures appel es parfois l mentaires on crit la proc dure suivante Proc dure Pivot de Gauss essai Entr es T Tableau n x p d l ments du corps k Sorties S Tableau n x p d l ments du corps k Pour j de 1 p faire Pour i de 1 n faire si a j 0 alors faire Pivot ij 1 E E a pour de i 1 n faire E E a E On remarque que cette proc dure compos e des proc dures l mentaires P1 et P2 ne change pas non plus l ensemble des solutions Le pivot existe si l un au moins des coefficients du tableau est non nul Sauf dans le cas o les tableaux d entr e et de sortie sont nuls le r sultat de la proc dure Pivot de Gauss essai est un syst me S r solu en x ce qui signifie il ne d pend pas des inconnues x Xp la seule quation qui contient x est la i me le tableau obtenu en conservant les colonnes d indice k gt j et les lignes d indice L i est associ un syst me lin aire S o ne figurent plus les inconnues Xi x Toute solution du syst me S est obtenue partir d une solution de S et de
Download Pdf Manuals
Related Search