Home

Algorithmes et logique au lycée - IREM d`Aix

1. 2 Introduction la logique math matique 2 1 2 2 2 3 2 4 2 5 2 6 Bref survol historique naaa Un langage math matiquement d fini 2 2 1 Le calcul propositionnel 2 2 2 Le calcul des pr dicats 88 x o gt x Sg KR we Soe we La formalisation des d monstrations 2 3 1 Un peu de vocabulaire 2 3 2 R gles de la D duction Naturelle en calcul propositionnel 2 3 3 D duction Naturelle en calcul des pr dicats 2 3 4 Compl tude de la logique du premier ordre Illustration de quelques r gles La logique au quotidien en classe de math matiques 2 5 1 Le modus ponens omnipr sent un exemple en g om trie 2 5 2 La pratique du contre exemple 2 5 3 Les raisonnements par l absurde et par r currence 2 54 Utilisation de la contrapos e propos d un exercice de D FSD CUNE A Se us JA en Ses RAR 2 5 5 La d monstration par disjonction des cas Bibhograplie o s eos 4 oe ddr dub due a eR da Pr sentation Ce document a pour but d apporter un compl ment d information dans le do maine de l algorithmique et de la logique aux professeurs de math matiques Ces chapitres sont actuellement enseign s de mani re transversale dans la sp cialit math matique du cycle terminal de la s rie L Ce document peut aussi int resser les aut
2. en remarquant que la formule Vi D p q est quivalente la formule R q La formule P q est quivalente 4p P p A D p q c est l application de la proposition 34 du livre VII des l ments au nombre q la deuxi me partie de la d monstration peut alors se formaliser par Q Ip P p A D p q R p L Q dp P p A D p q F Ax P x A R x En regroupant les conclusions de ces deux parties on peut formaliser la fin de la d monstration par Q P q F da P x AR x Q gt P q F dx P x A R QF P g V P q 6 PaeP GAR 2 6 Bibliographie Article Logique math matique de l Encyclop dia Universalis Cori R Lascar D Logique math matique Cours et exercices corrig s Li cence Master Tomes 1 et 2 Dunod Dowek G La logique Coll Dominos Flammarion 1995 David R Nour K Raffalli C Introduction la logique Th orie de la d monstration Cours et exercices corrig s 2nd cycle Dunod 2001
3. D Nk Si on suppose qu au rang k rp Tk 1fk 2 gt alors N N 10x R 10 x N D Qx partie enti re r et dis ee Ni x Qk Tip Tones D D D Ne 10 p Qr 10 rk Tk41fkt2 t re 10x 0 rk4irk 2 t Tet Tkt N donc Qg partie enti re 2 fk41 Conclusion les Q sont les chiffres du d veloppement d cimal illimit asso 1 ci D Calcul de i et j D apr s la remarque a partir d un certain rang on va retrouver un des restes pr c dents Soit 7 et j les plus petits entiers tels que R R On a donc Qi j 1 Qiy et pj Titji Qij Qin Tit1 p Ce qui prouve que la p riode du d veloppement d cimal est 7 N Algorithme 24 D veloppement d cimal d un nombre rationnel p f N Entr e Un nombre rationnel sous la forme D N Sortie Le quotient entier e de la liste Non Periodique des chiffres de la partie non p riodique la liste Periodique des chiffres de la partie p riodique 26 Algorithmique num N den D Initialisation TabReste i indique la position o le reste i a t obtenu pour variant de 0 jusqu den 1 faire T abResteli 0 e num div den r num mod den nitialisation de la liste des quotients avec la liste vide ListeQuotient i 0 tant que T abRestelr 0 faire 1 i i TabRestelr i num 10xr q num div den ListeQuotient ListeQuotient q r
4. REMARQUE On peut noter que la r gle d limination du V permet de faire des raisonnements par disjonction de cas R gle relative au L Elimination du L Pek rrA Pour n importe quelle formule A Si de l ensemble de formules I on d duit l absurdit alors on peut en d duire n importe quelle formule D finition 20 Le syst me de d duction naturelle de la logique intuitionniste est l ensemble des arbres de d rivation construits partir des axiomes logiques TH A lorsque T et des r gles relatives aux connecteurs V et Les r gles classiques de NK L Axiome du tiers exclus T E est le fait que l on rajoute comme axiome logique le s quent suivant te F pV 7d 2 3 La formalisation des d monstrations 57 La R gle de l absurde A est la r gle suivante T p ll rF o La R gle de la double n gation est la r gle suivante Law rF o Les trois r gles T E A et sont quivalentes Elles permettent de faire des raisonnements par l absurde a4 D finition 21 Le Syst me de d duction naturelle NK C est le syst me NJ auquel on rajoute la r gle TE REMARQUE Comme on le fait usuellement en math matiques on a envie de r utiliser ce qu on a d montr sans pour autant refaire la d monstration chaque fois On pourra consid rer une r gle d riv e comme une bo te noire dont on ne conna t que les entr es sorties EXE
5. PP otis remplac es par un terme quelconque t R gles pour 3 R gle d introduction de Pedant eer oo T 0 2x x TH o t x P y a a Ji TE 3x d x Here y n est libre ni dans T ni dans 0 EXEMPLE d monstration formelle de la distributivit du V par rapport au A Va o x O a F Vx o x A A Va o x 8 x F Vr p x 6 x Va o x A A x F oly A Ay Va o A A x F olz A ale Vz o x O F oly a Va o A O F A z Vu o x A O x Vrd a Va d x A O x Vxr0 ax Ai Va o x A O x F Vro x A Vr x 2 4 Illustration de quelques r gles 59 2 3 4 Compl tude de la logique du premier ordre Pour le calcul propositionnel ce th or me de compl tude s nonce ais ment Th or me 2 Compl tude de la logique propositionnelle Soit F une formule propositionnelle F est une tautologie ssi le s quent F est d montrable Ce th or me peut tre vu comme un cas particulier du th or me de compl tude de la logique du premier ordre dont la d monstration est plus complexe Nous ne ferons ici que l noncer et nous renvoyons pour sa d monstration aux ouvrages de r f rence par exemple l Introduction la logique de David Nour et Raffali Th or me 3 Compl tude de la logique du premier ordre Soit 7 une th orie les formules closes appartenant T sont appel s axiomes de la th orie et F une formule close T F F ssi F est une cons quence
6. leur propre langage pris dans sa dimension formelle R sum grossi rement il s agissait de re traduire toutes les math matiques m me celles concernant l infini des nonc s l mentaires d une part on r duit les d mons trations des suites finies de symboles et on construit un algorithme qui permet de transformer une d monstration de la th orie des ensembles en une d monstration finitaire Ce projet sera d finitivement mis en chec par le th or me d incompl tude de G del Mais la tentative de Hilbert a quand m me permis un travail de formalisation des math matiques qui s est r v l fructueux et a donn naissance a une branche importante de la logique la th orie de la d monstration dont les applications notamment en informatique se sont r v l es tr s importantes le projet intuitionniste d une profonde r forme des math matiques consi d r es comme saisies d garement qui a donn naissance certaines branches marginales des math matiques le constructivisme et qui trouve galement des applications importantes en logique avec le d veloppement de informatique 2 1 Bref survol historique 43 Avec le th or me d incompl tude en 1931 une th orie axiomatisable suf fisamment d velopp e ne peut contenir la d monstration de sa propre coh rence G del ouvre deux voies le d veloppement de la th orie de la d monstration et la th orie des fonctions r cursiv
7. gaux n pour variant de 1 jusqu n faire t i vrai t 1 faux pour 7 variant de 2 jusqu n si ti alors On barre les multiples de k 2 tant que k i lt n faire t k x i faux k lt k 1 L On initialise la liste L avec la liste vide pour i variant de 2 jusqu n si t i alors L L i i est un nombre premier on l ajoute la liste L r sultat L On peut crire partir de cet algorithme une version un peu plus performante en tenant compte des remarques suivantes On peut passer d un multiple m de au multiple suivant en y ajoutant une addition est plus rapide qu une multiplication Il est inutile d examiner les multiples m de inf rieurs i7 car ils ont t d ja barr s Il est inutile de chercher barrer des nombres plus grands que y n car tous ceux qui ne sont pas premiers ont d j t En effet un nombre plus grand que y n qui n est pas premier a forc ment un facteur premier plus petit que y n donc il aura t barr lorsque les multiples de ce facteur I ont t Ce qui conduit crire l algorithme suivant Algorithme 14 Crible d Erathost ne version optimis e 1 5 Quelques algorithmes l mentaires en arithm tique 19 pour variant de 1 jusqu n faire t i vrai t 1 faux pour i variant de 2 jusqu yn si t i alors On barre les multiples de m i tant que m lt
8. grec que cette histoire se confond au moins jusqu une p riode r cente avec lhis toire des math matiques et de la philosophie La logique contemporaine math matique et symbolique appara t au cours de la seconde moiti du 19 si cle On peut rep rer cette naissance autour de trois moments G Boole r alise une alg brisation de la logique en d veloppant le calcul pro positionnel comme un calcul d pendant uniquement de la combinaison de sym boles et non de l interpr tation de ceux ci Les travaux contemporains de De Mor gan qui initient la logique des relations d velopp e ensuite par Pierce Schr der et Russel contribuent au d veloppement de cette nouvelle forme de logique La publication du Begriffsschrift de Frege en 1879 marque le d but de la 42 Introduction la logique math matique formalisation de la logique et du formalisme comme philosophie programmatique des math matiques Dans les travaux de Frege la logique s applique d abord et essentiellement d terminer les lois m mes de la d duction la logique joue un r le d cisif dans le vaste mouvement d axiomatisation des math matiques L analyse sera axiomatiquement ramen e l arithm tique gr ce Bolzano Weierstrass Dedekind M ray Cantor avec donc des grandes ques tions sur la nature des entiers des ensembles d entiers des ensembles Hilbert m nera bien l axiomatisation compl te de la g om trie euc
9. num mod den k TabReste r NonPeriodique ListeQuotient 0 k 1 Periodique ListeQuotient k i r sultat e Nonperiodique Periodique 1 6 Les algorithmes de la brochure avec Excel et VBA 27 1 6 Les algorithmes de la brochure avec Excel et VBA VBA Visual Basic for Applications fait partie int grante d Excel En tapant ALT F11 dans Excel vous acc dez VBA et il suffit d ajouter un module pour pouvoir crire des programmes et les tester dans Excel 1 6 1 Les formules avec Excel Le Une formule Excel commence toujours par le symbole Les r f rences A3 fait r f rence la cellule situ e la premi re colonne et troisi me ligne du tableau A3 B7 fait r f rence deux cellules du tableau num ration A3 B7 fait r f rence une r gion rectangulaire du tableau allant de la cel lule A3 la cellule B7 Par exemple A8 somme A3 B7 calcule dans A8 la somme de deux cellules A8 somme A3 B7 calcule dans A8 la somme de 2 x 5 10 cellules La recopie des formules Lorsqu une formule est recopi e d une cellule vers une autre et que la recopie correspond une translation de lignes et c colonnes dans la grille toutes les r f rences des cellules sont d cal es de lignes et c colonnes Par exemple si on a C3 C2 B3 et que l on recopie la cellule C3 dans la cellule DS ce qui correspond un d calage de deux lignes et d une colonne on
10. c est celui qui correspond la s mantique pr sent e ci dessus 3 Nous illustrerons les r gles de d duction pr sent es ci dessous dans la section suivante 2 3 La formalisation des d monstrations 55 2 3 1 Un peu de vocabulaire En D duction Naturelle ND on distingue deux types de r gles de d duction les r gles d introduction et les r gles d limination des connecteurs et quantifica teurs e le n est pas primitif mais d fini partir du connecteur et de la constante L symbole de l antilogie A A gt L e De m me pour amp En effet A amp B A gt B A B A D finition 19 Une d monstration formelle dans un syst me de d duction na turelle est un arbre fini Ses noeuds sont des expressions F o T est un en semble de formules et est une formule ces expressions sont appel es s quents on peut intuitivement comprendre un tel s quent par la formule est d duite de l ensemble d hypoth ses I La racine de l arbre est la conclusion de la d mons tration les feuilles sont soit des axiomes d une th orie soit des axiomes logiques c est dire des s quents T F A o A ET Les n uds p res se d duisent des n uds fils par l application d une des r gles de d duction du syst me Ces r gles sont qualifi es de r gles d introduction ou r gles d limination selon qu elles permettent d introduire un connecteur ou bien d liminer un c
11. la logique math matique 1 On suppose que AM 1cm Calculer la longueur OM En d duire le p rim tre du quadrilat re MON B Reprendre les calculs pr c dents en supposant que AM 6cm Le p rim tre du quadrilat re MON B est il constant On pose AM x Exprimer OM en fonction de x En d duire expression P x du p rim tre du quadrilat re MON B en fonction de x tudier laire du quadrilat re MON B pour diff rentes positions du point M sur AB Quelle conclusion peut on tirer de cette tude Des calculs simples montrent que si AM 1 OM 5 et le p rim tre du quadrilat re MON B mesure 18cm Si AM 6cm OM 2V5 et le p rimetre mesure 8 45 On peut donc en conclure que le p rim tre du quadrilat re MON B n est pas constant L tude du 2 montrera que P x 8 2Vx 8x 32 et que ce p rim tre est minimal lorsque AM 4 L tude pour plusieurs positions du point M sur AB montre que l aire cor respondante du quadrilat re MON B est de 16cm Cependant ce constat ne suffit pas pour en conclure que l aire est ind pendante de la position du point M sur AB A M B On montre en utilisant les cas d galit des triangles que OMA et ONB sont isom triques On d duit par d coupage et comparaison des aires que le quadri lat re MON B a une aire gale celle du triangle AO B et donc que celle ci est in d pendante de la position du point M sur
12. les relations les fonctions D finition 7 Langage du premier ordre Un langage du premier ordre est un ensemble de symboles qui se compose de deux parties 2 2 Un langage math matiquement d fini 49 La premi re commune tous les langages du premier ordre est constitu e des symboles logiques les variables les connecteurs les quantificateurs et les parenth ses soit Un ensemble V d nombrable dont les l ments sont appel s les variables not es x y Z N x L ensemble des connecteurs C V A gt Les quantificateurs V et Les parenth ses ouvrantes et fermantes La deuxi me partie contient des symboles non logiques et varie d un lan gage l autre Un ensemble de symboles fonctionnels Un symbole fonctionnel est consti tu par un couple f n o n est appel l arit de f x Un ensemble de constantes a b c que l on peut voir aussi comme des symboles fonctionnels d arit 0 Un ensemble de symboles relationnels Un symbole relationnel est consti tu par un couple R n o n est appel l arit de R Remarque La donn e d un langage du calcul des pr dicats se fera par la don n e des symboles non logiques EXEMPLE L f 2 g 2 c 0 U R 2 S 2 o f et g sont des sym boles de fonctions binaires c est un symbole de fonction 0 aire une constante R et S sont des symboles de relations binaires Nous allo
13. n faire tlm faux mem i L On initialise la liste L avec la liste vide pour i variant de 2 jusqu n si t i alors L L i i est un nombre premier on l ajoute la liste L r sultat L 1 5 2 D composition d un entier n en produit de facteurs pre miers On sait qu un nombre entier se d compose de mani re unique en un produit de facteurs premiers Le principe de la d composition est tr s simple Il consiste essayer de diviser n par les nombres premiers successifs Lorsqu un nombre premier p divise n il faut continuer diviser n par ce nombre tant que cela est possible afin de conna tre l exposant de p Voici l algorithme Algorithme 15 D composition d un entier n en produits de facteurs premiers Entr e un nombre entier naturel n Sortie la liste des nombres premiers p1 p2 pr et de leur exposant respectif 1 2 er tel que n soit gal pip pe P la liste des nombres premiers inf rieurs ou gaux an F On initialise la liste des facteurs F avec la liste vide E On initialise la liste des exposants E avec la liste vide 1 tant que n 1 faire si p ne divise pas n alors i 1 sinon k 0 tant que p divise n faire ne n p k k 1 F F p i p est un facteur premier on l ajoute la liste F r sultat F E E k On ajoute son exposant k la liste E des exposants 20 Algorithmi
14. Excel et VBA 31 End Function Public Function Quotient a As Integer b As Integer As Integer Quotient a a Mod b b End Function Public Function MultEgypt a As Integer b As Integer As Integer Dim r As Integer r 0 Do While b lt gt 0 If Reste b 2 1 Then r r a End If a 2 a b Quotient b 2 Loop MultEgypt r End Function 1 6 5 La multiplication d cimale Avec Excel A 1 A 2 40 3 400 4 4000 Formules A3 10 A2 correspond a 10 x a B3 quotient B2 10 correspond b b div 10 C3 C2 A2 reste B2 10 correspond ar r a x b mod 10 L algorithme se termine lorsque 0 appara t dans la colonne B Ces formules sont recopi es vers le bas dans les trois colonnes Programme en VBA Public Function MultDecimale a As Integer b As Integer As Integer Dim r As Integer r 0 Do While b lt gt 0 32 Algorithmique r r a Reste b 10 a 10 a b Quotient b 10 Loop MultDecimale r End Function 1 6 6 Algorithme d euclide Avec Excel Lo Formules A5 A2 B5 B2 C6 reste AS B5 correspond ar a mod b A6 B5 correspond a b B6 DS correspond a b r Lalgorithme se termine lorsque 0 appara t dans la colonne B Ces formules sont recopi es vers le bas dans les trois colonnes Programme en VBA Public Function PGCD a As Integer b As Integer Dim r As Integer q As Integer Do While b lt gt 0 q Quotient a b
15. M est une r alisation du langage et s est une assignation de variables Une r alisation valu e M s permet de d finir l interpr tation d un terme t par un l ment du domaine de la r alisation not s t puis ensuite de d termi ner la satisfaction des formules dans cette r alisation valu e Lemme 5 Interpr tation des formules Soit M s une r alisation valu e du langage Il existe une et une seule fonction bool enne s i e d finie sur l en semble des formules du premier ordre de valeur dans 0 1 qui v rifie les conditions ci dessous en notant M pour s 1 Si dest une formule atomique R t1 t alors ME R ssi s t1 s t R Si dest alors M H y ssi s y 0 Si est pA 8 alors s o 1 ssi s 4 1 et s1 9 1 De m me pour V lt on revient aux tables de v rit vues en calcul propositionnel lemme 1 Sidest dr alors M Ix y ssi il existe a M tel que s y 1 ou Sz a coincide avec s sauf en x pour laquelle 5 _ x a Si dest Vx w alors s 1 1 ssi quelque soit a M s Y 1 D finition 16 Formules synonymes F et G sont synonymes ssi quel que soit M s M E F ssi M H G On note alors F G 2 3 La formalisation des d monstrations 53 EXEMPLES 1 VaF de F 2 dak WaiFk 3 VaVyF VyVxF D finition 17 Cl ture universelle Soit F une formule ayant ses variables li
16. T Nombre As Integer NumDiv As Integer Diviseur As Integer Liste As String Const nmax 2500 fn gt nmax Then Exit Function T Array 2 8 5 7 11 13 17 19 23 29 31 37 41 43 47 Nombre n NumDiv 0 Diviseur T NumDiv Liste Do While Nombre lt gt 1 If Reste Nombre Diviseur lt gt 0 Then NumDiv NumDiv 1 Diviseur T NumDiv Else Liste Liste amp Diviseur amp Nombre Nombre Diviseur End If Loop decomposition Liste amp 1 End Function 38 Algorithmique 1 6 10 D composition en base b Avec Excel A B D E 1 Base lt 10 B 12 Dividende Chiffres 2 3 En base 10 4 5 6 Formules LerL E2 C 3 correspond l initialisation de a F3 reste E2 C 1 correspond r a mod b E3 quotient E2 C 1 correspond n a div b Ces formules sont ensuite recopi es vers le bas Lalgorithme s arr te lorsque n 0 La liste des chiffres peut tre lue dans la colonne F Programme en VBA Public Function VersBase b As Integer N As Integer As String Dim Mot As String Chiffre As String Dim T T Array 0 1 2 3 45 5 6 1 8 9 A B C D E F Mot Do While N lt gt 0 Chiffre Reste N b Mot T Chiffre amp Mot N Quotient N b Loop VersBase Mot End Function 1 6 Les algorithmes de la brochure avec Excel et VBA 39 1 6 11 Conversion en d cimal Avec Excel BL LRLE LE H J
17. dans les objets enseign s que dans la pratique des exer cices Ces notions sont illustr es et d clin es sur des exercices du programme de sp cia lit math matique en s rie L mais sont adaptables aux programmes venir Chapitre 1 Algorithmique Les algorithmes sont tr s souvent consid r s comme du domaine des math matiques et de l informatique leur champ d application est en r alit beaucoup plus vaste Les historiens s accordent pour dire que le mot algorithme vient du nom du grand math maticien persan Al Khowdrizmi an 825 environ qui intro duisit en Occident la num ration d cimale et les r gles de calculs s y rapportant La notion d algorithme est donc historiquement li e aux manipulations num riques mais ces derni res d cennies elle s est progressivement d velopp e sur des objets plus complexes graphes textes images son formules logiques robotique etc Le but de ce chapitre est de pr ciser ce qu on entend par algorithme de pr senter un langage dans lequel on pourra les exprimer d voquer et d illustrer les probl mes qui se posent dans leur laboration 1 1 Quelques id es en vrac Approche na ve C est une m thode i e une fa on syst matique de proc der pour faire quelque chose trier rechercher calculer Il r pond des questions du type comment faire ceci obtenir cela trouver telle information calcu ler tel nombre C est un concept prat
18. instruction2 instruction n La boucle pour Elle s crit pour variable variant de expr init jusqu a expr fin faire instruction ou encore pour variable variant de expr init jusqu a expr fin avec un pas de expr pas faire instruction L instruction qui suit faire est ex cut e pour les diff rentes valeurs de la va riable La variable est appel e variable de contr le de la boucle Si l expression pas n est pas pr cis e la variable de contr le est incr ment e de 1 apr s chaque tour de boucle Dans le cas o l on souhaiterait ex cuter non pas une mais plu sieurs instructions on crira ces instructions sur plusieurs lignes une instruction par ligne pr c d es par un trait vertical pour variable variant de expr init jusqu a expr fin faire instruction instruction2 instruction n En g n ral la variable de contr le l expression initiale l expression finale et l ex pression pas si elle est pr sente ont des valeurs enti res Ce sera toujours le cas dans les algorithmes tudi s Par ailleurs on interdit de modifier la variable de contr le l int rieur de la boucle 1 3 Illustration des notions de preuve et de terminaison d un algorithme 7 1 3 Illustration des notions de preuve et de termi naison d un algorithme Ces notions sont illustr es travers cinq exemples On pr sente tout d abord trois algorithmes qui permettent de calculer le pro
19. ou une machine m canique 1 2 Pr sentation d un langage d criture des algorithmes 3 Domaines o interviennent les algorithmes L algorithmique intervient dans des domaines divers et vari s Num riques Tri recherche de mots plus g n ralement recherche d information Algorithmes g om triques images de synth se Recherche de formes g nomes internet moteur de recherche Compression des donn es Cryptographie Malgr les normes progr s de la technologie les ordinateurs seront toujours sou mis a des limitations physiques nombre d op rations par seconde taille m moire Une part importante de la recherche en algorithmique consiste laborer des algorithmes de plus en plus efficaces Par exemple en 1950 on pouvait calcu ler quelques milliers de d cimales de IT et en 2002 on en tait plus d un trillion 1018 C est peu pr s part gale en raison des avanc es technologiques et al gorithmiques La recherche syst matique d efficacit passe aussi par la recherche de nouveaux types de repr sentation et d organisation des donn es classement des mots organisation arborescente D Knuth consid re les arbres comme la structure la plus fondamentale de toute l informatique 1 2 Pr sentation d un langage d criture des algo rithmes Certaines des instructions pr sent es ci dessous utilisent la notion d expres sion bool enne ces expre
20. p lt n p Q par hypoth se de r currence De plus n 160 sinon n 1 serait le plus petit l ment de Q Finalement Vp EN O0 lt p lt ntl p Q ce qu il fallait montrer D apr s le principe de r currence on en d duit que Vn N P n est vraie et en particulier Vn N n Q ce qui contredit l hypoth se Q est une partie non vide de N et am ne la contradiction cherch e La d monstration par r currence de la proposition Yn N P n peut tre formalis e par F P 0 kHVnP n P n 1 Vn P n axiome du principe de r currence Si l on note B la proposition Q a un plus petit l ment C la proposition 2 est vide la proposition Vn P n est quivalente la proposition C et on peut formaliser le raisonnement par l absurde par BEC FAC ABFCAA7AC B Ni 64 Introduction la logique math matique 2 5 4 Utilisation de la contrapos e propos d un exercice de perspective La photographie ci dessous montre la fa ade d un b timent du XVIII si cle La fa ade de ce b timent est elle situ e dans un plan frontal On peut supposer que la fa ade du b timent est situ e dans un plan vertical et que les bords horizontaux des corniches des chapiteaux des balustrades etc sont parall les entre eux Si la fa ade du b timent tait situ e dans un plan fron tal les repr sentations des bords horizontaux des diff re
21. pr c dente nous nous sommes appliqu s d une part d finir pr cis ment les formules d autre part v rifier parmi les formules bien d finies lesquelles taient vraies universellement valides Nous allons maintenant appro fondir cette d marche 1 Nous tendons notre effort de formalisation r alis jusqu ici sur les for mules aux d monstrations elle m mes 54 Introduction la logique math matique 2 Nous ne nous contentons plus de v rifier si une formule est vraie ou pas mais nous allons construire des formules vraies Nous allons donc donner un sens pr cis l expression la formule est d montrable Dans la mesure o est tablie par les th or mes de compl tude la correspondance entre formules vraies universellement valides et formules d montrables nous pourrons alors consid rer que nous savons en faisant des d monstrations formelles construire des formules vraies Il existe plusieurs syst mes dans lesquels on peut d finir les preuves formelles De tels syst mes s appellent des syst mes de d duction ou des syst mes for mels Historiquement les premiers syst mes formels par exemple les syst mes la Hilbert taient bas s sur des sch mas d axiomes les tautologies du calcul propositionnel ou du calcul des pr dicats une d monstration formelle est une suite de propositions qui appartiennent cette suite soit parce qu elles sont des axiomes soit qu elles p
22. quanti fi e L exemple ci dessus montre son utilisation pour calculer mentalement 992 2 5 La logique au quotidien en classe de math matiques 61 2 5 La logique au quotidien en classe de math ma tiques 2 5 1 Le modus ponens omnipr sent un exemple en g om trie Consid rons l exercice suivant Le triangle ABC est rectangle en et les c t s AB et AC mesurent respective ment 5 et 8 cm Quelle est la longueur du c t BC La r daction classique de la solution de cet exercice est le triangle ABC est rectangle en A donc d apr s le th or me de Pythagore on a BC AB AC d o BC 5 8 soit BC 89 On en d duit BC 89 Ce type de d monstration fr quent en math matiques utilise la r gle appel e modus ponens ou r gle d limination du Notons P la proposition le triangle ABC est rectangle en A Q la proposition BC AB AC L instanciation du th or me de Pythagore sur le triangle ABC peut tre formali s e par P Q et la d monstration ci dessus par FP H P gt Q FQ Le donc de la r daction ci dessus repr sente la mise en acte de la r gle d limination du gt e 2 5 2 La pratique du contre exemple A TM B On consid re un carr ABC D de 8 cm de c t et de centre O Soit M un point du segment AB et N le point du segment O BC tel que les droites OM et ON soient perpendiculaires 62 Introduction
23. r a b q a b b r 1 6 Les algorithmes de la brochure avec Excel et VBA 33 Loop PGCD a End Function 1 6 7 M thode de dichotomie Avec Excel A B C D E Calcul approch de la racine cubique de 2 par dichotomie Formules b C7 A6 B6 2 correspond c D7 C7 3 2 correspond y f c E7 B7 A7 correspond e b a A7 SI D7 lt 0 C7 A6 correspond si f c lt 0 alors a c B7 SI D7 lt 0 B6 C7 correspond si f c gt 0 alors b c et ces formules sont recopi es vers le bas Programme en VBA Public Function f x As Double As Double X x x 2 End Function Public Function Dichotomie a As Double b As Double epsi As Double As Double 34 Algorithmique Dim c As Double ya As Double ya f a Do While b a gt epsi c a b 2 If ya f c lt 0 Then b c Else a c End If Loop Dichotomie a End Function 1 6 8 Crible d Eratosth ne Avec Excel La pr sence d une double boucle fait que cet algorithme ne peut pas tre si mul directement avec Excel Programme en VBA Public Function Crible nmax As Integer As String Dim i As Integer j As Integer Liste As String Dim T 1 To 2000 As Boolean For i 1 To nmax T i True Next i T 1 False i 2 Liste Do While i i lt nmax If T i True Then j i i Liste Liste amp amp Str i Do While j lt nmax T j False j j i Loop End If 1 6 Les algorithm
24. r2 r et b 0 pipz pz on a alors Q a b x 107 x 10 Mira Ti j TS avec a ig e 107 x b pipo p PiPa Pj P1p2 t pj 6 d o b PRPs 107 1 donc Q PER x ie x 10 T eng ee ge a rire i x 10 1 pipe p 105 x 107 1 Il suffit maintenant de rendre cette fraction irr ductible Il n y a donc pas d algorithme de calcul de Q sous forme de fraction mais simplement une m thode math matique x 10 Obtention du d veloppement partir de la fraction N N N Q E D o F est la partie enti re de Q et D sa partie d cimale illimit e On aura donc 0 r2 ri DiDa P D r r2 P1p2 Pj Partie r guli re Partie p riodique Pour d terminer les suites de d cimales r et py ainsi que et 7 on construit les suites N Q4 et Ry de la fa on suivante Ry Nz mod D reste euclidien de N par D N R Qk a quotient euclidien de Ny par D Ney 10x Rk avec Ro N Remarques a Rx peut prendre D valeurs enti res comprises entre 0 et D 1 1 5 Quelques algorithmes l mentaires en arithm tique 25 b Si R 0 alors tous les restes suivants sont nuls c Il en d coule que 7 lt D Calcul des d cimales Il faut v rifier que les quotients calcul s sont bien les d cimales du d velop pement cherch Proc dons par r currence sur k N On a bien Ni 10 x N et Q partie enti re 5 r puisque 10 x N
25. retourne leur pgcd T a y b tant que y 0 faire rx mod y zy Y r sultat x Le principe de l algorithme d Euclide s appuie sur les deux propri t s suivantes Le pgcd a 0 est a Le pgcd a b est gal au pgcd b r o r est le reste de la division eucli dienne de a par b Cette derni re propri t est tr s facile tablir On d montre que l ensemble des diviseurs de a et b est le m me que l ensemble des diviseurs de b et r Il est vident que tout nombre divisant a et b divise r car r a b x q et r ciproquement tout nombre divisant b et r divise aussi a car a r x q Pour d montrer que cet algorithme calcule bien le pgcd de a et b il faut d montrer que cet algorithme fournit dans tous les cas une r ponse terminaison de 1 3 Illustration des notions de preuve et de terminaison d un algorithme 11 l algorithme et que cette r ponse est bien le pgcd de a et b validit de l algo rithme Terminaison chaque it ration y est affect avec le reste de la division eucli dienne de x par y On sait par d finition de la division euclidienne que ce reste r est strictement inf rieur au diviseur y Ainsi chaque it ration y entier naturel diminue strictement Il existe donc une tape o y recevra la valeur 0 permettant ainsi la boucle de se terminer Validit Il suffit d tablir que le pgcd x y reste en permanence gal au pgcd a b On dit que cette quant
26. s que l on manipule et ce de telle fa on que l on puisse les analyser relativement une notion de v rit Traditionnellement cette formalisation s effectue en deux tapes on s int resse dans un premier temps articulation logique des nonc s calcul propositionnel puis aux contenus des nonc s math matiques calcul des pr dicats L approche syntaxique permet de construire des formules correctes du point de vue du lan gage et de la prouvabilit l approche s mantique permet de v rifier la validit des formules en calculant leur valeur de v rit ou en se pla ant dans des mod les On utilise dans ce qui suit les notions de mots et d arbres qui permettent l agencement et la manipulation des symboles et sur lesquelles reposent les d fi nitions syntaxiques 2 2 1 Le calcul propositionnel Cette partie de la logique math matique ne s int resse pas au contenu des propositions mais seulement la mani re dont elles sont logiquement articul es L tude du calcul propositionnel est une premi re tape pour aborder tude com pl te des nonc s math matiques Les formules propositionnelles Dans un premier temps il s agit de d finir pr cis ment les objets d tude les propositions ou formules propositionnelles Ainsi nous allons manipuler des symboles de variables propositionnelles ou atomes A B C et des symboles de combinateurs ou op rations logiques les connecteurs O
27. sin valeur absolue binaires comme x ou des relations ou pr dicats lt Wa tre pair des variables x y n m des constantes 0 Ainsi comme pour le calcul propositionnel les formules seront des suites de symboles prises dans un alphabet Toutefois il n y aura pas un alphabet unique mais un alphabet appropri appel souvent langage pour chaque type de struc ture envisag e Certains symboles sont communs tous les alphabets les connec teurs les parenth ses les quantificateurs et les variables Les autres symboles d pendent du type de structure que l on a en vue Par exemple si on veut tudier des structures alg briques et plus pr cis ment les groupes on a besoin d un sym bole de constante pour l l ment neutre d un symbole de fonction binaire pour l op ration interne et d un symbole de relation binaire pour l galit Pour tu dier les ensembles ordonn s on a seulement besoin de deux symboles de relation binaire pour la relation d ordre et pour l galit Les formules que l on va tudier ici s appellent les formules du premier ordre Ceci est justifi par le fait que l on quantifie sur les l ments de la structure Mais il y a de nombreuses propri t s que l on ne peut pas exprimer ainsi par exemple la notion de bon ordre il faut alors se permettre de quantifier sur d autres objets que les variables du premier ordre
28. 1 Base B T 2 3 5 6 7 En base 10 N 131909 Le nombre en base b est crit l envers dans la ligne 3 Le r sultat est le plus grand des nombres crits dans la ligne 5 Le cas des bases sup rieures 10 n est pas trait avec Excel Formules C5 C3 D5 SI D3 C5 C 1 D3 correspond l instruction s s x b a o a correspond au chiffre de la cellule D3 Le test permet l arr t de l algorithme lorsqu il n y a plus de chiffres traiter Cette formule est ensuite recopi e vers la droite Programme en VBA Public Function EnDecimal N As String b As Integer As Long Dim i As Integer c As Integer Chiffre As String Dim Resultat As Long Dim T T Array 0 1 2 3 4 5 6 7 8 9 A B C D E F Resultat 0 For i 1 To Len N Chiffre Mid N i 1 on extrait le chiffre N i on recherche le chiffre dans la table For j 0 To 15 If T j Chiffre Then c End If Next j Resultat Resultat b c algorithme de H rner 40 Algorithmique Next i EnDecimal Resultat End Function Chapitre 2 Introduction la logique math matique Je confesse bien comme vous Que tous les po tes sont fous Mais puisque po tes vous n tes Tous les fous ne sont pas po tes Sc vole de Sainte Marthe 1536 1623 2 1 Bref survol historique On fait remonter traditionnellement l histoire de la logique l antiquit
29. 47 ap mht tid A ee Gr eee eae 15 Quelques algorithmes l mentaires en arithm tique 17 1 5 1 Construction de la liste des nombres premiers par la m thode du crible d Erathost ne 17 1 5 2 D composition d un entier n en produit de facteurs premiers 19 1 5 3 D composition en base b d un entier a 20 1 5 4 Conversion d un nombre crit en base ben d cimal 21 1 5 5 Lalgorithme de Homer 22 54 65 4 ee Ge aura 22 1 5 6 Construction d un nombre d cimal n inf rieur 1 partir de la liste a de ses chiffres sw oes a sens ds 23 1 5 7 G n ration d un nombre entier al atoire n dont la d com position binaire comporte exactement k bits 23 1 5 8 D veloppements d cimaux illimit s 24 ill iv TABLE DES MATI RES 1 6 Les algorithmes de la brochure avec Excel et VBA 1 6 1 Les formules avec Excel exer ana do be Heda gt 4 1 6 2 Le langage Visual Basic for Applications 1 6 3 La multiplication simple 1 6 4 La multiplication gyptienne 1 6 5 La multiplication d cimale 1 6 6 Algorithme d euclide 1 6 7 M thode de dichotomie 1 6 8 Crible d Eratosth ne 4256 20 4s guise gi wt ART Wee oh Gee 1 6 9 D composition en produit de facteurs premiers 1 6 10 D composition en base b 1 6 11 Conversion en d cimal
30. A F F idempotence du A 10 F V F F idempotence du V 11 F G G F contrapos e D duction s mantique D finition 6 Soit un ensemble de formules et une formule On dit que valide si toute valuation qui satisfait satisfait On note REMARQUE Si est une tautologie on a ce que l on notera Lemme 4 Quelques tautologies bien connues Soit F et G des formules propo sitionnelles les formules suivantes sont des tautologies F G F F gt FVG G gt FVG FAGSF FAG G F gt F G FV F mele MONE ENTORSES gs Rc 48 Introduction la logique math matique 2 2 2 Le calcul des pr dicats Le calcul des pr dicats comporte deux volets Tout d abord on se donne les outils ad quats pour nommer les objets les termes et d crire leurs propri t s les formules On tudie ensuite la satisfaction des formules dans telle ou telle structure Le langage du premier ordre L objectif est de d finir les mots que nous appellerons formules Il s agit de trouver un alphabet et une grammaire permettant d exprimer les nonc s math matiques tels que Ve IN Yn n gt N gt lu al lt e Vnam m gt n Vn P n x n 1 est pair Yn Ak k lt n V n 0 Vy Ax sin x 2 y Dans ces nonc s on distingue des connecteurs V des quantificateurs V 3 les parenth ses ouvrantes et fermantes des fonctions unaires comme
31. Algorithmes et logique au lyc e Octobre 2009 A Publication de l IREM de l Acad mie d Aix Marseille IREM Campus de Luminy case 901 163 avenue de Luminy 13288 Marseille cedex 9 T l 04 91 82 94 87 90 91 T l copie 04 91 82 93 43 e mail dir irem univ mrs fr http www irem univ mrs fr Algorithmes et logique au lyc e P Bouttier A Crumi re F Didier J M Fillia M Quatrini H Roland IREM Campus de Luminy Table des mati res Pr sentation v 1 Algorithmique 1 1 1 Quelques id es en vrac oaoa 1 1 2 Pr sentation d un langage d criture des algorithmes 3 1 2 1 L instruction d affectation 4 1 2 2 Les instructions conditionnelles 4 1 2 3 Les instructions 1 ratives 2 24044 4 gare gars de a 6 1 3 Illustration des notions de preuve et de terminaison d un algorithme 1 4 1 5 7 1 3 1 Algorithme de multiplication Un premier algorithme 7 1 3 2 Algorithme de multiplication Un deuxi me algorithme 8 1 3 3 Algorithme de multiplication Un troisi me algorithme 9 1 3 4 Algorithme Euclide pour le calcul du PGCD de nombres CNUELS 4 ei e Date does a Behn e e pa het 10 1 3 5 Algorithme d Euclide tendu 12 1 3 6 Division euclidienne 13 Un principe fondamental la dichotomie 14 1 4 1 M thode de dichotomie pour le calcul d un z ro d une JONCTION
32. DF f auoir vn nombre l vnit Cequi eftabfurde Don G eftautre nombre premier que pasvn des propolez Eten celte fa on o eu peuttrouuer infiny autres Parquoy quel que or titud de riombres premiers qu on propofe amp c Ce qu il falloit emonftrer Soit p1 P2 Pn n nombres premiers distincts Alors il existe un nombre pre mier p diff rent de p1 po Pn Soit l entier q d fini par q p X p2 X X Pn 1 Ou bien q est premier et il est de fa on vidente diff rent de chacun des p ce qu il fallait montrer Ou bien q n est pas premier et il admet un diviseur premier p proposition 34 du livre VID Si ce nombre p est l un des p alors il divise la fois py X po X X Pn et p X Pa X X Pn 1 donc il divise leur diff rence c est dire 1 ce qui est absurde Donc il est diff rent de chacun des p On peut formaliser cette d monstration de la mani re suivante Pis Pns q p sont des constantes Q d signe la proposition les constantes 7 Pn repr sentent des nombres premiers distincts P x d signe la proposition le nombre x est premier R x d signe la proposition le nombre x est diff rent de chacune des constantes p et D x y d signe la proposition le nombre x divise le nombre y La premi re partie de la d monstration peut se formaliser par Q P g F aD pe 0 Q P q F Vi D p q Q Pig F 3x P x A R x Vi Ji 2 6 Bibliographie 67
33. MPLES 1 On peut d river la r gle suivante qui permet de faire des raisonnements par contrapos e FASB B A En effet en prenant A B comme hypoth se on peut faire la d rivation suivante FA gt B AFA AFB BolBst A B gt LFl Bea aL B SL A 2 En logique classique NK les formules A V B et A B sont qui valentes Nous tablissons ici comme exemple la formule A V B gt A B qui ne n cessite pas l utilisation de la r gle TE et qui est par cons quent d montrable dans N J On fait d abord les deux d rivations suivantes o I d signe l ensemble de formules A V B A B T AHA F At A A l L B FB T B B B 1 P A DB EL 58 Introduction la logique math matique puis la d rivation r H AV B F AHL r B FHL Ve LE AV B A AB AV B A B H AV B A B 2 3 3 D duction Naturelle en calcul des pr dicats Le syst me de D duction Naturelle N K pour le calcul des pr dicats est consti tu par les axiomes et r gles du calcul propositionnel auxquels on rajoute des r gles d introduction et d limination pour les quantificateurs V et 3 R gles pour V R gle d introduction de V Pr gly Vi TF Va x y n est pas libre dans T R gle d limination de VY DE Va x o t x d signe la formule dans laquelle Ve toutes les occurences libres de x ont t
34. aque tape l intervalle de moiti en consid rant le milieu c de trouver une valeur approch e d une racine de f e pr s Pour atteindre la pr cision arbitrairement petite il suffit d it rer n ja b r ce processus n fois o n est le plus petit entier tel lt On peut aussi dire ER que n est le plus petit entier sup rieur ou gal log2 chaque tape il faut veiller ce que la fonction f ait une racine sur le nouvel intervalle Cette condition indispensable pour la validit de l algorithme n est pas toujours respect e et bon nombre de versions que l on peut rencontrer dans la litt rature peuvent dans certains cas donner des r sultats erron s On ren contre aussi tr s souvent une erreur dans la condition d arr t le test n est pas fait sur la comparaison de la longueur de l intervalle avec mais sur la compa raison f c lt o c est un point de l intervalle qui contient une racine exacte Clairement f c lt n implique pas 20 c lt Un premier algorithme Algorithme 8 Recherche d une racine par dichotomie Entr es a r el b r el a lt b f fonction continue sur a b telle que f a x f b lt 0 un nombre r el arbitrairement petit Sorties un nombre r el qui approche une racine x de f e pr s Invariant f a x f b lt 0 ou a bet f a 0 16 Algorithmique tant que b a
35. arrt apart 4 a3 x a2 amp 1 t ao p x ax t ax_1 t a2 amp 1 t a Ainsi pour calculer p x on organise les calculs de mani re calculer successi vement les valeurs bz bk 1 bo d finies par bk Ak by bk ax bi bite bo bix ao On a donc by p x c est ce proc d qui est parfois appel sch ma de H rner Algorithme 21 Sch ma de H rner Entr es Un tableau a de k 1 coefficients index s de 0 k et un nombre r el x Sortie Le nombre s X p aja s 0 pour variant de k jusqu 0 avec un pas de 1 faire S SXT G r sultat s 1 5 Quelques algorithmes l mentaires en arithm tique 23 1 5 6 Construction d un nombre d cimal n inf rieur 1 par tir de la liste a de ses chiffres Cet algorithme est encore une application directe de l algorithme de H rner En effet si la liste a est a1 a2 4 1 le nombre n corrrespondant est n anlO ag 1107 ED a11071 Ce qui conduit crire l algorithme suivant Algorithme 22 Sch ma de Horner appliqu la construction d un nombre d ci mal plus petit que 1 Entr e un tableau de chiffres a index de 1 k Sortie un nombre d cimal n ae a 10 inf rieur 1 n 0 pour variant de k jusqu 1 avec un pas de 1 faire no ta r sultat n 1 5 7 G n ration d un nombre entier al atoire n dont la d composition binaire comp
36. at a 1 5 Quelques algorithmes l mentaires en arithm tique 17 En effet invariant n est plus satisfait dans le cas o le milieu de l intervalle c est par malchance une racine de la fonction f Ce cas peu fr quent comme on l a d j dit peut n anmoins se produire et l algorithme ci dessus fournit alors un r sultat faux Dans cette configuration le produit f a f c est nul a prend donc la valeur c et par la suite le produit f a x f c n tant jamais n gatif on trouve comme valeur approch e de la racine un point proche de b e pr s chaque it ration les algorithmes pr c dents valuent deux fois la fonction f et effectuent un produit on peut tre plus efficace en crivant les choses diff remment Un troisi me algorithme Algorithme 12 Recherche d une racine par dichotomie 3 version Entr es a r el b r el f fonction continue sur a b telle que f a lt Oet f b gt 0 un nombre r el arbitrairement petit Sortie un nombre r el qui approche une racine de f pr s Invariant f a lt 0 et f b gt 0 tant que b a gt faire a b Cc si f c lt 0 alors a c sinon b c r sultat a 1 5 Quelques algorithmes l mentaires en arithm tique Nous allons pr senter ici quelques algorithmes l mentaires en arithm tique comme cr ation de la liste des nombres premiers d composition d un nombre entier en facteurs premiers liste des divi
37. bres parmi x1 On appelle cl ture universelle de F la formule Vx Vx F REMARQUE Une formule F et sa cl ture universelle ne sont pas n cessairement synonymes EXEMPLE Les formules x y et VrVy x y ne sont pas synonymes Dans une r alisation dont le domaine contient plus d un l ment la formule x y sera satisfaite pour certaines valuations alors que la formule VrVy x y ne le sera jamais D finition 18 Une formule close est dite universellement valide ou valide si elle est satisfaite dans toute r alisation de Une formule comportant des variables libres est dite universellement va lide si sa cl ture universelle l est Etant donn deux formules F et G on dit que ces formules sont universel lement quivalentes ou logiquement quivalentes ou quivalentes si la formule F lt 4 G est universellement valide On appelle th orie de tout ensemble de formules closes de Soit une th orie T de et une r alisation M de On dit que M est un mod le de T si M satisfait toutes les formules de T On note M T Une th orie est consistante si elle poss de au moins un mod le Une th orie qui n est pas consistante est dite contradictoire Etant donn une th orie T et une formule close F de on dit que F est une cons quence s mantique ou cons quence de T si tout mod le de T est aussi mod le de F 2 3 La formalisation des d monstrations Dans la partie
38. d une formule EXEMPLE La table de v rit du A B A B8B 1 1 1 11 0 0 011 1 010 1 Tautologie formules logiquement quivalentes D finition 4 Soit F une formule v une valuation et un ensemble de formules v satisfait F ssi v F 1 v satisfait X ssi v satisfait toutes les formules de X F est satisfaisable ssi il existe une valuation v qui satisfait F i e telle que v F 1 F est une tautologie ssi elle est satisfaite par toutes les valuations F est une antilogie ou une contradiction ssi elle n est satisfaite par aucune valuation Lest satisfaisable ssi il existe une valuation qui satifait Y est insatisfaisable ou inconsistante ou contradictoire ssi il n existe pas de valuation qui satisfasse simultan ment toutes les formules de X 2 2 Un langage math matiquement d fini 47 D finition 5 Soit F et G deux formules sur P F et G sont logiquement quiva lentes ssi pour toute valuation v v F v G On notera alors F G Lemme 3 Quelques quivalences bien connues Soit F G et H des formules propositionnelles on a l1FsSsG FVG 2 Fv VH Fv GV H associativit du V 3 FAG AH F GA H associativit du A 4 FV G G V F commutativit du V 5 FAG GA F commutativit du 6 F A G aF V 7G n gation d une conjonction 7 FV G F A G n gation d une disjonction 8 1 F double n gation 9 F
39. duit a x b de nombres entiers naturels a et b puis le tr s connu algorithme d Euclide pour calculer le PGCD de deux nombres entiers et enfin un algorithme un peu moins connu permettant de calculer le quotient et le reste de la division euclidienne de deux nombres entiers 1 3 1 Algorithme de multiplication Un premier algorithme Algorithme 1 Ce premier algorithme calcule le produit de deux nombres entiers a x b en n effectuant que des additions ra y b z 0 tant que y O faire Z 2 4 2 yey r sultat z Terminaison y tant d cr ment de 1 chaque it ration il deviendra n ces sairement nul au bout de b it rations Validit Il suffit d tablir que z x x y reste en permanence gal a x b On dit que cette quantit est invariante C est l invariant qui caract rise la boucle Cet invariant joint la condition d arr t y 0 prouve que la variable z vaut a x ba la sortie de la boucle C est trivialement vrai avant la boucle Montrons que cette propri t reste vraie la fin de chaque it ration Pour cela nous noterons x y et z les valeurs respectives de x y et z la fin d une it ration Bien videmment ces valeurs deviendront les nouvelles va leurs de x y et z pour l it ration suivante On a 2 x y y 1et z 2 x z x xy 2 xr xx y 1 Zz uxXxy a x b par hypoth se de r currence 8 Algorithmique 1 3 2 Algorithme de multiplicatio
40. e calcule leur pgcd ainsi que deux entiers u et v tels que a x u b x v pgcd a b A la fin de cet algorithme x est le pgcd de a et b car si l on examine les lignes qui ne concernent que x et y en gras on retrouve exactement l algorithme d Euclide x a y b uel v 0 uy lt 0 vu 1 tant que y 0 faire q x div y r x mod y x y yer auz V V Vi Vi AUX r sultat x u v QUE U U U1 Uy AUX q X u qxv L invariant de la boucle est la conjonction des deux galit s aXu bXv x et a X u b X V1 y Ceci est trivialement vrai avant la boucle Notons x y u v u4 vi les valeurs respectives de x y u v u1 v1 la fin d une it ration Les valeurs ayant un prime devenant les nouvelles valeurs au d but de l it ration suivante Ainsi par hypoth se de r currence on aa x u b x v x et a X ui b x v y Montrons qu la fin d une it ration les galit s axu et bxv r 1 Paal a xui tbxv y sont encore satisfaites l axu bxv r Dans la boucle on a les affectations u u v v vey 1 1 1 2 Ainsi a x u b x v a xX u b x v qui vaut y par hypoth se donc 2 1 3 Illustration des notions de preuve et de terminaison d un algorithme 13 2 axul b x vi y Dans la boucle on a les affectations uji u qx u v v qx y r q etr sont respectivement le quotient et le r
41. es la m me poque Tarsky cr e la s mantique scientifique Ce qui importe ce n est pas la notion d interpr tation d un langage formel dans un domaine d objets notion parfaitement claire depuis le 19 si cle mais un traitement math ma tique de la question Il ouvre la voie la th orie des mod les La logique notamment les branches que nous avons soulign es se d veloppe alors gagnant peu peu le statut de discipline math matique part enti re Un change fructueux s est tabli avec d autres branches des math matiques l al g bre mais aussi diverses parties de l analyse de la topologie de la th orie des nombres de la th orie des cat gories De plus l informatique th orique a repris son compte de vastes fragments de la logique fournissant en change la mati re de nouvelles investigations Soulignons pour conclure ce bref survol historique l importance du r le jou par l irruption et l explosion de l informatique dans tous les domaines de la vie conomique et scientifique sur les d veloppement r cents de la logique En effet les bases th oriques de cette nouvelle science sont justement la logique math matique Tout d abord les mod les th oriques des premiers ordinateurs sont les machines de T ring Rappelons ensuite quelques unes des interactions entre la logique et l informatique le calcul bool en pour la conception et l tude des circuits la r cursivi
42. es de la brochure avec Excel et VBA 35 i i 1 Loop il faut maintenant ajouter la liste les nombres premiers restants For j i To nmax If T j Then Liste Liste amp amp Str j End If Next j Crible Liste End Function 1 6 9 D composition en produit de facteurs premiers Avec Excel wle l mlml laa Nous avons vu que nous ne pouvions pas simuler dans Excel la double boucle de la recherche des nombres premiers donc pour r aliser avec Excel la d com position en produit de facteurs premiers nous devons disposer d une liste de nombres premiers Cette liste est crite dans la colonne G Formules B2 1 correspond l initialisation 7 1 C2 INDEX G G B2 1 correspond c p car INDEX renvoie la valeur situ e dans la colonne G la ligne dont l indice est donn par B2 ici il renvoie donc la valeur de la cellule G1 D3 RESTE A2 C2 correspond ar n mod p A3 SI D3 0 A2 C2 A2 correspond si r 0 alors n n p B3 SI D3 lt gt 0 B2 1 B2 correspond sir 4 0 alors i i 1 a j on tu ha 11 17 19 36 Algorithmique C3 INDEX G G B3 1 Calcule la valeur de p E3 SI D3 0 C2 1 sir 0 alors on ajoute p la liste des diviseurs Ces formules sont ensuite recopi es vers le bas 1 6 Les algorithmes de la brochure avec Excel et VBA 37 Programme en VBA Public Function decomposition n As Integer As String Dim
43. este de la division euclidienne de x par y axu bxvu ax u qx um 0x vqx v axutbxvu qx axu bx uw x q X y par hypoth se de r currence r par d finition du reste y Ainsi lorsque l algorithme se termine on a bien a x u b x v x pgcd a b 1 3 6 Division euclidienne Algorithme 7 Division euclidienne Cet algorithme effectue la division eucli dienne de deux nombres entiers a et b en calculant le quotient q et le reste r Les op rations utilis es sont la soustraction la multiplication par 2 et la division par 2 q 0 w b T a tant que w lt r faire w 2 xw tant que w b faire q 2xq w w div 2 si w lt r alors rr w q q 1 r sultat q r Cet algorithme est tr s performant lorsque la base est une puissance de 2 car multiplications et divisions consistent alors en des d calages L invariant de la seconde boucle est la conjonction des deux propri t s qx w r aet0 lt r lt w Terminaison w est de la forme 2 b au d part et est divis par 2 chaque it ration Il deviendra n cessairement gal b apr s p it rations 14 Algorithmique Validit Il suffit d tablir que q x w r aet0 lt r lt w reste vrai chaque tape Cet invariant joint la condition d arr t w b prouve ici encore que l on a bien calcul le quotient et le reste de la division euclidienne de a par b C est trivialement vrai avant la boucle Montrons que cet
44. euvent se d duire de propositions pr c dentes par appli cation d une r gle Par exemple pour le calcul propositionnel on utilise une seule r gle appel e Modus ponens Si A et A B sont deux propositions qui appartiennent une d monstration formelle D alors la suite de pro positions constitu e de D suivie de B est une d mon stration formelle Gerhard Gentzen est le premier avoir d velopp des formalismes qui re donnent la logique le caract re d un cheminement naturel La principale id e de d part de Gentzen tait simple pas d axiomes logiques que des r gles de d duction et autant qu il en faut pour reproduire toutes les formes l mentaires et naturelles de raisonnement Pour r aliser cette id e Gentzen a d velopp un for malisme o les d ductions ne sont pas des suites d nonc s mais des arbres faits de colonnes d nonc s qui se rejoignent via des r gles de d duction jusqu la conclusion G Gentzen a propos en 1934 plusieurs syst mes d inf rence dont les sys t mes de d duction naturelle N K pour la logique classique et N J pour la logique intuitionniste Le choix de graduer les r gles de d duction provient d un souci philosophique que nous n abordons pas ici bien qu il soit du plus grand int r t Le syst me utilis dans les cours de math matique qu ils soient de l enseignement secondaire ou de l enseignement universitaire est le syst me N K
45. ge machine compilation Ex cution Points importants de la conception d un algorithme Une des difficult s dans l laboration d un algorithme est de contr ler son aspect dynamique ex cution partir de son criture statique suite finie d instructions Un algorithme de tri peut s crire en quelques lignes et peut trier aussi bien une suite de 10 l ments qu une suite de 100 000 l ments Les probl mes importants qui se posent dans la conception d un algorithme sont La preuve prouver que l algorithme r sout la classe de probl mes pour laquelle il a t crit L arr t prouver que quelles que soient les donn es fournies en entr e Valgorithme s arr te toujours Le choix des structures des donn es il est fondamental que les donn es manipul es soient sous un format bien pr cis et structur es Par exemple dans un dictionnaire mots fran ais crits en lettres latines et surtout class s par ordre alphab tique L essentiel dans l laboration d un algorithme est de percevoir les l ments cl s d un processus quelconque et d imaginer la suite d op rations logiques les plus astucieuses et les plus efficaces pour le mettre en uvre de mani re automatique et performante Un algorithme peut tre vu comme le squelette abstrait du programme infor matique sa substantifique moelle ind pendant du codage particulier qui permettra sa mise en oeuvre avec un ordinateur
46. gt faire a b GCG si f c 0 alors a cC bee sinon si f a f c lt 0 alors b c sinon a c r sultat a Dans la pratique il est peu probable que la variable c prenne pour valeur une des racines de la fonction f ainsi le test f c 0 devient inutile et nuit l effi cacit de ce premier algorithme En effet les valeurs donn es aux bornes de l in tervalle de d part sont tr s souvent des nombres entiers alors que les racines de f sont g n ralement des nombres irrationnels Un deuxi me algorithme Algorithme 9 Recherche d une racine par dichotomie 2 me version Entr es a r el b r el a lt b f fonction continue sur a b telle que f a x f b lt 0 un nombre r el arbitrairement petit Sortie un nombre r el qui approche une racine de f pr s Invariant f a x f b lt 0 tant que b a gt faire a b C lt si f a x f c lt 0 alors b c sinon a c r sultat a On aurait pu aussi crire autrement le corps de la boucle en gardant le m me invariant Algorithme 10 Autre version de l algorithme 9 tant que b a gt faire a b C si f a x f c gt 0 alors a c sinon b c r sultat a Mais la version qui suit bien que tr s proche peut s av rer erron e Algorithme 11 Version erron e de algorithme 9 tant que b a gt faire a b lt si f a x f c lt 0 alors b c sinon a c r sult
47. i me algorithme est celui que l on apprend l cole pri maire il utilise des multiplications et divisions par 10 syst me d cimal et l al gorithme de multiplication d un nombre entier quelconque par un nombre ayant un seul chiffre utilisation des tables de multiplication Lea y b z0 tant que y 0 faire z z x x y mod 10 x 1l0xzr y y div 10 r sultat z 10 Algorithmique Terminaison y tant divis par 10 chaque it ration il deviendra n cessaire ment nul apr s un nombre fini d it rations Validit Il suffit d tablir que z x x y reste en permanence gal a x b Cet invariant joint la condition d arr t y 0 prouve ici encore que la variable z vaut a X b la sortie de la boucle C est trivialement vrai avant la boucle Montrons que cette propri t reste vraie la fin de chaque it ration Pour cela nous noterons x y et z les valeurs respectives de x y et z la fin d une it ration Bien videmment ces valeurs deviendront les nouvelles va leurs de x y et z pour l it ration suivante On a x 10 x x y y div 10 etz z x x y mod 10 2 a x y z z x y mod 10 10 x x x y div 10 z x x y mod 10 10 x y div 10 ztaxy a x b par hypoth se de r currence 1 3 4 Algorithme d Euclide pour le calcul du PGCD de nombres entiers Algorithme 4 Euclide Cet algorithme prend deux entiers naturels en entr e a et b et
48. id re l occurence de x appartient une branche o la r gle de formation 2x ou Vz a t appliqu e Autrement dit cette occurence de x dans est dans une sous formule de qui est de la forme Vw ou 2x Une occurrence de x dans est libre ssi la feuille dans laquelle on consid re l occurence de x n appartient pas une branche o la r gle de formation Vx ou dx a t appliqu e EXEMPLE Dans la formule f x y a Vy R y x les occurrences de x sont libres y a une occurrence libre et une occurrence li e D finition 12 Variables libres Une variable x est une variable libre de ssi x poss de au moins une occurrence libre dans On note Y l ensemble des variables libres de EXEMPLE Dans l exemple ci dessus x et y sont des variables libres D finition 13 Formule close Une formule est une formule close lorsque V d 0 ouverte si elle poss de des variables libres EXEMPLE La formule Vx SyR z y gt f a x a est close La formule Vz R x y gt f a x z est ouverte Interpr tation Il s agit de donner un sens aux symboles de pr dicats et de fonctions aux va riables et aux termes et une valeur de v rit aux formules Pour cela on va d abord fixer l univers du discours c est dire l ensemble des objets que l on tudie les termes seront interpr t s par des l ments de cet ensemble On peut alors asso cier chaque symbole fonct
49. ionnel une fonction sur cet ensemble fonction au sens math matique habituel de m me les symboles relationnels seront interpr t s par des relations sur cet ensemble Ensuite on donnera une valeur de v rit aux formules en tenant compte de leurs variables libres par le biais des assignations D finition 14 R alisation d un langage Soit L fi ni i I U R n j J Une r alisation M du langage est la donn e 52 Introduction la logique math matique d un ensemble non vide E appel le domaine de la r alisation not parfois M D pour chaque symbole fonctionnel f n de d une fonction f E gt E pour chaque symbole relationnel R n de d une relation n aire R R cC E EXEMPLE Avec L f 2 g 2 h 1 c 0 U R 2 1 M N x succ 0 lt 2 M Le plan euclidien E d origine O gt gt f EP E d finie par f A B C tel que OA OB OC g E E d finie par g A B C milieu de AB h E E d finie par h A C sym trique de A par rapport O c est l origine O R A B A B 0 sont align s Une assignation de variables s est une application s V E Lorsque V est fini i e V x1 2 s sera plut t not x1 1 Tn Gn D finition 15 R alisation valu e Une r alisation valu e une interpr tation d un langage est la donn e d un couple M s o
50. ions et divisions par 2 consistent en des d calages et ces 1 3 Illustration des notions de preuve et de terminaison d un algorithme 9 op rations l mentaires dans tout langage machine sont effectu es tr s rapide ment On peut donner une justification de sa validit autre que celle utilisant la notion d invariant Il suffit de consid rer l criture binaire de y y ye y i 2 o les coefficients yfi valent 0 ou 1 Le produit x x y est donc gal ne y t x x x 2 Tous les termes intervenant dans la somme sont de la forme x x 2 et correspondent des coefficients yfi non nuls i e aux valeurs impaires que prend la variable y dans l algorithme 2 Dans la pratique on organise les calculs en faisant deux colonnes une contenant respectivement les valeurs des quotients successifs de y par 2 et l autre les valeurs de la forme x x 2 Il suffit alors de sommer les l ments de la deuxi me colonne en gras dans l exemple ci dessous qui sont en face d l ments impairs de la pre mi re colonne Exemple soit calculer le produit de x 12 par y 22 Calcul en d cimal Calcul en binaire y x y x 22 12 10110 1100 11 24 1011 11000 5 48 101 110000 2 96 10 1100000 1 192 1 11000000 On trouve que le r sultat de 12 x 22 est gal 24 48 192 264 En binaire 11000 110000 11000000 100001000 1 3 3 Algorithme de multiplication Un troisi me algorithme Algorithme 3 Ce trois
51. ique qui traduit la notion intuitive de proc d syst matique applicable m caniquement sans r fl chir en suivant sim plement un mode d emploi pr cis Tentative de d finition Suite d ordres pr cis compr hensibles et ex cutables de mani re non ambig e par un automate devant tre ex cut s suivant un ordre parfaitement d termin en vue de r soudre une classe de probl mes Par exemple classer des suites de nombres chercher des mots dans un dictionnaire sont des exemples de classe de probl mes que des algorithmes sont capables de r soudre 2 Algorithmique On vitera de prendre des exemples de la vie courante pour illustrer le concept d algorithme une recette de cuisine est un mauvais exemple d algorithme car elle est toujours trop impr cise une pinc e de sel combien de grammes faire bouillir dix minutes la temp rature d bulition d pend entre autre de l altitude laquelle on se trouve En g n ral automate est une machine et tr s souvent un ordinateur L activit principale en algorithmique est de concevoir et d exprimer puis de coder dans un langage de programmation un algorithme En g n ral on l exprime dans un langage proche de la langue naturelle en utilisant des expressions dont on sait qu elles seront facilement transcrites dans un langage de programmation Algorithme en fran ais Codage dans un langage de programmation Traduction automatique en langa
52. ira ces instructions sur plusieurs lignes une instruction par ligne pr c d es par un trait vertical qui englobe toutes ces instructions si expression bool enne alors instruction instruction2 instruction n L instruction si alors sinon Elle s crit si expression bool enne alors instruction 1 sinon instruction 2 Si l valuation de l expression donne la valeur vrai c est l instruction 1 qui suit imm diatement le alors qui est ex cut e sinon c est l instruction 2 qui suit le sinon qui est ex cut e Dans le cas o l on souhaiterait ex cuter non pas une mais plusieurs instructions on crira ces instructions sur plusieurs lignes une instruction par ligne pr c d es par un trait vertical si expression bool enne alors instruction instructionZ instruction n sinon instruction instructionZ instruction p 6 Algorithmique 1 2 3 Les instructions it ratives La boucle fant que Elle s crit tant que expression bool enne faire instruction Tant que l expression bool enne est vraie on ex cute l instruction qui suit faire d s qu elle devient fausse on passe a l instruction suivante Dans le cas o l on souhaiterait ex cuter non pas une mais plusieurs instructions on crira ces ins tructions sur plusieurs lignes une instruction par ligne pr c d es par un trait vertical tant que expression bool enne faire instruction
53. it est invariante C est l invariant qui caract rise la boucle Plus pr cis ment l invariant est la proposition logique pgcd x y pgcd a b C est trivialement vrai avant la boucle Montrons que cette propri t reste vraie la fin de chaque it ration Pour cela nous noterons x et y les valeurs de x et y la fin d une it ration Bien videmment ces valeurs deviendront les nouvelles valeurs de x et y pour l it ration suivante On a x qui est gal y et y qui est gal r r reste de la division eucli dienne de x par y ainsi le pgcd x y est gal au pgcd y r qui est gal au pgcd x y propri t 2 ci dessus or par hypoth se de r currence on a pgcd x y pgcd a b Ainsi pgcd x y pgcd a b L invariant joint la condition d arr t y 0 prouve qu la sortie de la boucle x est gal au pgcd a b Cette fa on d tablir la validit de l algorithme d Euclide para t pour le moins aussi simple que la d monstration qui introduit des suites index es Peut tre pour un public non initi est il pr f rable d crire l algorithme sous la forme suivante Algorithme 5 Algorithme d Euclide 2 version Ta y b tant que y 0 faire r x mod y vey y r rr y y r sultat x 12 Algorithmique 1 3 5 Algorithme d Euclide tendu Algorithme 6 Euclide tendu Etant donn s deux entiers naturels a et b cet algorithm
54. le segment AB D C Si l on note x y des r els appartenant 0 8 et P x le p rim tre du quadri lat re MON B lorsque AM x la proposition le p rim tre du quadrilat re MON B est constant se formalise par Va Vy P x P y Montrer que cette proposition est fausse revient v rifier que sa n gation est vraie x Jy P x P y La v rification se fait en exhibant deux valeurs x y pour lesquelles on a P x 7 P y 2 5 La logique au quotidien en classe de math matiques 63 Pour d montrer que l aire du quadrilat re est constante on est amen com parer laire du quadrilat re MON B celle du triangle AOB pour une position quelconque du point M sur AB et constater que ces deux aires sont gales La r gle d introduction du V permet de conclure 2 5 3 Le raisonnement par l absurde et le raisonnement par r currence S1 l on admet comme axiome le principe de raisonnement par r currence on peut d montrer le r sultat suivant Toute partie non vide de N admet un plus petit l ment Soit Q une partie non vide de N Raisonnons par l absurde et supposons donc que Q n admet pas de plus petit l ment Soit n N Notons P n la proposition P n VpeN 0 lt p lt n p Q P 0 est vraie car dans le cas contraire 0 serait le plus petit l ment de 2 Soit n un entier tel que P n soit vraie alors P n 1 est vraie En effet Vp N 0 lt
55. lidienne Les principaux acquis de cette p riode ne vont pas tarder tre remis en cause par une profonde crise au tournant du 20 si cle connue sous le nom de crise des fondements La th orie des ensembles a provoqu beaucoup de r sistance chez de nombreux math maticiens Elle s est labor e comme tentative de fonder les math matiques partir d ingr dients de base bien d finis les ensembles et de tout reconstruire partir de l Mais vite sont apparus de nombreux paradoxes Par exemple le paradoxe de Russel soit a l ensemble des ensembles ne se contenant pas eux m mes il est facile de montrer que a a ssi a a ce qui est manifes tement contradictoire Il tait alors n cessaire de mettre de l ordre dans tout cela Il s agissait de pr ciser quels taient les raisonnements fiables qui mettraient labri de toute contradiction cette crise on distingue trois r ponses le projet logistique d une r duction des math matiques une logique coh rente et suffisamment d velopp e Projet illustr par la Th orie des Types de Russel qui cesse vite d avoir une influence directe en logique math matique mais qui tient aujourd hui une place importante dans certaines recherches en informa tique th orique le projet formaliste nonc par Hilbert au d but du 20 si cle est celui d une solution d finitive tous les probl mes de fondement par l application des math matiques
56. lle F est l arbre r duit la racine F si F G alors F est l arbre de racine et de fils G si F GaH o a est un connecteur binaire alors F est l arbre de racine a avec comme fils gauche G et comme fils droit H Distribution de valeurs de v rit valuation D finition 3 Une distribution de valeurs de v rit ou valuation est une fonction de l ensemble P des variables propositionnelles dans Q 0 1 46 Introduction la logique math matique Lemme 1 Une valuation v se prolonge de mani re unique en une fonction v de F dans Q satisfaisant v A v A lorsque A P F 1 ssi v F 0 v F AG 1 ssi v F v G 1 F Gis WF gt G 0 ssi v F 1etu G 0 CA v U F V G 0 ssi v F v F amp G 1 ssi v F o G La d monstration se fait par induction sur F Par abus de notation on note v pour v Soit F une formule la d finition de v sur F nous donne une m thode pour calculer v F on commence par calculer les valeurs prises par v sur les sous formules de F de hauteur 1 et on applique autant de fois que n cessaire les fonc tions asssoci es aux connecteurs Lemme 2 La valeur de v rit d une formule ne d pend que des atomes figurant dans cette formule Ce lemme permet de repr senter par un tableau la valeur de v rit d une for mule F en fonction de toutes les distributions de v rit possibles la table de v rit
57. mbre entier divisible par 6 A l entier n est divisible par 2 B l entier n est divisible par 3 e Elimination de V PAP DD T BFD T CFD ThAVBEVC TED Ve st un nombre entier naturel 0 mod 3 1 mod 3 2 mod 3 nest divisible par 3 P A B C D Cette r gle formalise la m thode de d monstration par disjonction des cas Ainsi on peut lire la formalisation ci dessus comme A partir des hypoth ses n est un entier T et n 0 modulo 3 A on d montre que n n est divisible par 3 D partir des hypoth ses n est un entier T et n 1 modulo 3 B on d montre que n n est divisible par 3 D A partir des hypoth ses n est un entier T et n 2 modulo 3 C on d montre que n n est divisible par 3 D partir de l hypoth se n est un entier T on d montre que n 0 modulo 3 ou n 1 modulo 3 ou n 2 modulo 3 T H AV BVC On d duit que sous l hypoth se n est un entier T la formule n n est divisible par 3 T D est vraie R gle d limination de V TF Yzr olx Ve I x est un nombre r el TE t x olx a 1 2 2r 1 o t x d signe la formule dans laquelle t le nombre entier 100 toutes les occurences libres de x ont t remplac es par un terme quelconque t Cette r gle repr sente l instanciation d une variable universellement
58. me 19 Conversion en d cimal d un nombre crit en base b Entr e Un nombre a a _1 a1 o p crit en base b Sortie Le nombre n qui correspond la conversion de az ax_1 a1a0 en base 10 Js d n 0 pour 7 variant de 0 jusqu k faire n n a x f f lt f xb r sultat n On peut encore diminuer le nombre de multiplications en utilisant l algorithme de Horner pr sent dans la section suivante pour valuer l expression polynomiale apb apb ab ao Algorithme 20 Conversion en d cimal d un nombre crit en base b Entr e Un nombre a a _1 1 0 p crit en base b Sortie Le nombre n qui correspond sa conversion en base 10 22 Algorithmique n 0 pour variant de k jusqu 0 avec un pas de 1 faire n nxb a r sultat n Cet algorithme n effectue plus que k 1 multiplications pour valuer l ex pression on ne peut pas faire mieux Les trois algorithmes pr c dents effectuent le m me nombre k d additions 1 5 5 L algorithme de H rner L algorithme de H rner est tr s connu et tr s facile mettre en oeuvre Soit x un nombre r el et p x apx ap 1 7 a1x a9 un polyn me de degr k dont les coefficients sont aussi des r els a distinct de 0 En remarquant qu on peut crire le polyn me sous la forme suivante p x apx apart 2 age amp 1 t ao p x arf ag_12 8 az a1 ao p x
59. n Un deuxi me algorithme Algorithme 2 Ce second algorithme calcule le produit de deux nombres entiers en n effectuant que des multiplications et divisions par 2 T a yb z 0 tant que y 0 faire si y impair alors z z x eH 2XxXr y y div 2 r sultat z Terminaison y tant divis par 2 chaque it ration il deviendra n cessaire ment nul apr s un nombre fini d it rations Validit Il suffit d tablir que z x x y reste en permanence gal a x b Cet invariant joint la condition d arr t y 0 prouve ici encore que la variable z vaut a X b la sortie de la boucle C est trivialement vrai avant la boucle Montrons que cette propri t reste vraie la fin de chaque it ration Pour cela nous noterons x y et z les valeurs respectives de x y et z la fin d une it ration Bien videmment ces valeurs deviendront les nouvelles va leurs de x y et z pour l it ration suivante Deux cas sont envisager y pair Onar 2 xa y y 2 etz z z x x y z 2x x x y 2 z uxy a x b par hypoth se de r currence y impair Onaz 2x2 y y 1 2et2 z x z x xy z 2 2x x x y 1 2 z 2 2x y 1 z xy a x b par hypoth se de r currence Cet algorithme est connu sous divers noms multiplication russe multiplication gyptienne Notons que son codage en informatique donne un algorithme tr s efficace car multiplicat
60. n en retient tradition nellement cinq un connecteur unaire pour la n gation not et lu non quatre connecteurs binaires celui de conjonction not et lu et de disjonction not V et lu ou celui de l implication not et lu implique et celui d quivalence not et lu si et seulement si On se donne un ensemble P fini ou d nombrable de variables proposition nelles P A B X Y Z On consid re l alphabet A PU gt V A 7 4 U Les formules vont tre certains mots sur A D finition 1 L ensemble F des formules propositionnelles est le plus petit en semble de mots sur A tels que F contient P si F contient F alors F contient F 2 2 Un langage math matiquement d fini 45 si F contient F et G alors F contient F V G F AG F G et F amp G C est dire que si F et G sont des formules alors F F V G F AG F G F amp G sont des formules Une formule contient par d finition un assez grand nombre de parenth ses qui parfois semblent inutiles Aussi pour ne pas alourdir l criture on convient de se donner la possibilit de suppri mer certaines parenth ses La r gle tant que les suppressions faites n apportent pas d ambiguit s c est dire que l on peut toujours reconstituer la vraie criture avec toutes les parenth ses Ainsi on supprime les parenth ses les plus ext rieures encadrant une formule on supprime les pa
61. ns construire des mots bien form s appel s des termes Les sym boles qui servent d ingr dients pour la fabrication des termes sont les variables les constantes et les symboles de fonctions EXEMPLE Dans le langage L x fy gc sera un terme On crira aussi ce terme en notation pr fix e g f x y c D finition 8 Termes d un langage L Un terme t est un mot fini sur d fini par induction par les variables et les constantes sont des termes si t1 tn Sont des termes si f est un symbole fonctionnel d arit n alors f ti tn est un terme REMARQUE On peut d finir un terme comme tant un arbre fini dont les feuilles sont des variables ou des constantes et dont chaque n ud qui n est pas une feuille v rifie la r gle de construction suivante le n ud est tiquet par un symbole de fonction n aire et poss de n fils qui sont des termes 2 le nombre d arguments de la fonction ou de la relation 50 Introduction la logique math matique D finition 9 1 Un sous terme u d un terme est un mot situ un n ud de l arbre de construction de t EXEMPLE h x y a est un sous terme de f g a h x y a 2 Les variables de t sont les variables situ es aux feuilles de l arbre de construc tion de t On note V t l ensemble des variables de t 3 t est un terme clos si V t est 0 REMARQUE Un langage sans symbole de constante n a pas de terme clos D fini
62. nstruction Dim ne seront visibles et utilisables qu l int rieur de la fonction variables locales La derni re instruction de la fonction doit tre de la forme nom de la fonction valeur retourner Cette instruction d termine quel sera le r sultat de la fonction lorsqu elle sera utilis e 1 6 3 La multiplication simple Avec Excel Formules A3 A2 B3 SI B2 lt gt 0 B2 1 0 correspond y y 1 C3 SI B2 0 C2 C2 A2 correspond z z x et ces formules contiennent le test d arr t tant que y 0 faire 30 Algorithmique Ces formules sont ensuite recopi es vers le bas dans les trois colonnes Programme en VBA Public Function MultSimple a As Integer b As Integer As Integer Dim r As Integer r 0 Do While b lt gt 0 r r a b b 1 Loop MultSimple r End Function 1 6 4 La multiplication gyptienne Avec Excel Formules A3 2 A2 correspond a 2 x a B3 quotient B2 2 correspond b b div 2 C3 SI reste B2 2 0 C2 C2 A2 correspond si b impair alors r r a Lalgorithme se termine lorsque 0 appara t dans la colonne B Ces formules sont recopi es vers le bas dans les trois colonnes Remarque quotient et reste sont des fonctions crites en VBA qui corres pondent a la division euclidienne Programme en VBA Public Function Reste a As Integer b As Integer As Integer Reste a Mod b 1 6 Les algorithmes de la brochure avec
63. nts l ments de la fa ade devraient tre parall les entre eux 4 Dans une projection centrale un plan frontal est un plan parall le au plan de projection ne passant pas par le centre de la projection dit aussi point de vue 2 5 La logique au quotidien en classe de math matiques 65 Or ils ne le sont pas ce que montre une v rification graphique sur la photogra phie donc la fa ade du b timent n est pas situ e dans un plan frontal La d monstration repose sur le r sultat de cours suivant Dans une projection centrale ou dans une repr sentation en perspective cen trale si des droites coplanaires sont parall les entre elles et si le plan qu elles d finissent est un plan frontal alors leurs projections leurs repr sentations sont des droites parall les Consid rons les propositions suivantes o D et D sont des droites copla naires A les droites D et D sont parall les B le plan d fini par les droites D et D est un plan frontal C les projections des droites D et D sont parall les Le r sultat de cours peut se formaliser par AA B C Le raisonnement utilis pour r soudre l exercice s appuie sur la contrapos e de cet nonc C A AB ou encore C gt AV B Il se formalise par PAC PAGS GAR f he RS eee LA PA Soe Lae i 2 5 5 La d monstration par disjonction des cas Au IF si cle avant JC Euclide d montrait dan
64. ombreux types Les fonctions cr es dans VBA sont utilisables dans Excel de la m me fa on que les fonctions Excel de base qui sont elles aussi crites en VBA Les types de variables Les variables utilis es dans le cadre des math matiques seront de type Integer ou long si elles doivent contenir des entiers Single ou Double si elles doivent contenir des nombres 4a virgule String si elles correspondent a des chaines de caract res Variant pour des variables pouvant contenir n importe quel type de donn es Array si ce sont des tableaux 1 6 Les algorithmes de la brochure avec Excel et VBA 29 Les instructions d signe aussi bien l affectation que le test d galit c est le contexte qui d cide If Then Else Endif ou If Then Endif est l instruction condi tionnelle Do Loop indique le d but et la fin d une boucle While est synonyme de Tant que For to Next indique un groupe d instructions r p ter un certain nombre de fois Les fonctions Function End Function indique le d but et la fin d une d claration de fonction Le mot Function est suivi sur la m me ligne du nom de la fonction et des pa ram tres de la fonction entre parenth ses Ces param tres servent fournir la fonction les donn es dont elle a besoin pour fonctionner Les variables d clar es dans la fonction apr s l i
65. onnecteur 2 3 2 R gles de la D duction Naturelle en calcul propositionnel Les r gles de la logique intuitionniste N J 1 Axiomes logiques TEA Lorsque appartient l ensemble de formules T 2 R gles relatives l implication Introduction de gt Elimination de r AFB AFA gt B GHA TEAS 2 A QF B REMARQUE Consid rons la r gle que l on a appel e limination de pour commenter la lecture des r gles de d duction Dans une telle r gle on distingue un ou deux s quents pr misses ceux qui sont au dessus ici AF A BetQ F A et un s quent conclusion celui qui est au dessous ici A Q F B Et la r gle peut tre lue de la fa on suivante on sait que sous les hypoth ses A on peut d duire la formule A B et que sous les hypoth ses Q on peut d duire la formule A on peut alors affirmer que la r union des hypoth ses A et Q permet de d duire la formule B 56 Introduction la logique math matique Ainsi une r gle de d duction permet de formuler une nouvelle conclusion ici la formule B la formule conclusion du s quent conclusion en contr lant la gestion des hypoth ses R gles relatives au connecteur A Introduction de A THA AFB TAK AAB Elimination de A AFAAB AFAAB Ael e2 AFA AFB At R gles relatives au connecteur V Introduction de V AFA AFB vil vi2 AtAVB AFAVB Elimination de V PARP G BEC THRFAVB Ve Pee
66. orte exactement k bits Cet algorithme est encore une application directe de l algorithme de H rner En effet il suffit que le bit de poids fort soit gal 1 et de choisir al atoirement entre 0 et 1 pour les k 1 autres bits On valuera au fur et mesure l entier d cimal correspondant exactement comme dans l algorithme H rner dans le cas o la base est 2 Voici l algorithme correspondant Algorithme 23 G n ration d un nombre entier al atoire n dont la d composition binaire comporte exactement k bits Entr e k un nombre entier Sortie un nombre entier al atoire n crit en d cimal dont la d composition bi naire comporte exactement k bits n 1 pour variant de 1 jusqu k faire n 2 x n hasard 2 r sultat n o hasard est la fonction qui renvoie pour r sultat un nombre al atoire sup rieur ou gal 0 et strictement plus petit que son argument 24 Algorithmique 1 5 8 D veloppements d cimaux illimit s Pr sentation Un nombre rationnel peut tre repr sent soit par son criture fractionnaire N l Q o N est un entier relatif et D un entier naturel non nul ou par un d ve loppement d cimal illimit p riodique de la forme Q 0 r r2 r P p2 P X 10 o les r et les p sont des chiffres du Partie r guli re Partie p riodique syst me d cimal et n un entier naturel Obtention de la fraction partir du d veloppement Si on pose a 0 r
67. pourra lire dans la cellule DS D4 C5 Cette fonctionnalit sera tr s utile pour recopier une formule dans une ligne ou une colonne Le Lors d une recopie il est parfois n cessaire qu une r f rence ne soit pas d ca l e Pour cela il suffit de mettre un devant la r f rence de ligne ou de colonne pour figer cette r f rence Par exemple si on a C3 C2 B 3 et que l on recopie la cellule C3 dans la cellule DS on pourra lire dans la cellule DS C4 C 3 28 Algorithmique Dans la premi re r f rence on a fig le num ro de ligne mais pas l indice de colonne et dans la seconde c est le contraire Le SI ALORS SINON Cette formule correspond a une affectation conditionnelle Par exemple la formule suivante C3 SI C2 gt 0 C2 B3 B3 correspond l instruction suivante Si C2 gt 0 alors C3 C2 B3 sinon C3 B3 la syntaxe g n rale est SI lt condition gt lt valeur si vrai gt ou SI lt condition gt lt valeur si vrai gt lt valeur si faux gt Les fonctions Excel Excel dispose de nombreuses fonctions math matiques statistiques etc Pour en voir la liste il suffit de cliquer sur l ic ne fy 1 6 2 Le langage Visual Basic for Applications Pr sentation C est un langage de programmation avec des sous programmes Sub et des fonctions Function et qui permet aussi la programmation objet Les variables sont r parties dans de n
68. que 1 5 3 D composition en base b d un entier a De fa on g n rale l criture d un nombre a en base b est d finie par la formule akak a1ao b apb ap 1b a1b ao 1 3 o les coefficients a sont des nombres entiers v rifiant 0 lt a lt b Le syst me d cimal tant le cas particulier o b est gal 10 les coefficients a prenant pour valeur un des dix chiffres 0 1 2 9 D composer un nombre a en base b revient trouver les k 1 coefficients a 0 lt a lt b tels que a apb ap 1b 7 a b ao Pour cela il suffit de savoir faire la division euclidienne de a par b dans le syst me d cimal En effet on obtient facilement le coefficient de poids le plus faible a en calculant le reste de la division de a par b puis on consid re le nombre entier a quotient de a par b a a div b apb ap 1b azb a 1 4 Le reste de la division euclidienne de a par b nous donne aj et ainsi de suite pour obtenir les autres coefficients de l criture binaire de a On peut choisir de ranger les coefficients soit dans une liste soit dans une table Algorithme 16 D composition d un entier n en base b avec une liste Entr e Un nombre n crit en base 10 Sortie La liste L des coefficients a de l criture de n en base b asn Le tant que a 0 faire r lt a mod b LerL a a div b r sultat L ay ay 1 a1 do Algorithme 17 Conversion d
69. renth ses s parant des connecteurs successifs identiques s il s agit du V du A ou de amp on supprime les parenth ses s parant des successifs group s par la droite A B gt C la place de A gt B C On peut donner de l ensemble F une description plus explicite on d finit par r currence une suite F d ensembles de mots sur A On pose Fo P Fn41 Fn U gt F F E Fa U FaG F G E Faa E V A gt Sh Th or me 1 F en Fn D finition 2 Soit F F une formule propositionnelle La hauteur de F not e h F est le plus petit entier n tel que F Fan Lorsqu il s agit de d montrer une propri t sur toutes les formules on peut soit faire une d monstration par r currence sur la hauteur des formules soit revenir la d finition pr c dente des formules et montrer que la propri t consid r e est vraie pour les formules atomiques et qu elle se pr serve par les op rations de n gation et par les connecteurs binaires Dans ce dernier cas on dit qu on fait une d monstration par induction sur l ensemble des formules De la m me fa on on peut faire des d finitions par induction sur l ensemble des formules par exemple On peut d finir par induction l ensemble des sous formules d une formule On peut associer une formule F son arbre de d composition F On pro c de de la fa on suivante par induction sur F si Fest une variable propositionne
70. res enseignants de lyc e notamment ceux de la classe de seconde puisque les nouveaux programmes int grent ces deux domaines La premi re partie aborde la partie algorithmique de ce programme Apr s avoir introduit succintement et naivement la notion d algorithme suit une des cription du langage dans lequel les algorithmes seront d crits Les instructions de ce langage sont communes la plupart des langages de programmation ainsi ils pourront tre facilement transcriptibles dans n importe lequel de ces langages en vue d tre test s La notion de preuve de la validit d un algorithme est abord e par la notion d invariant de boucle Elle donne un autre clairage du raisonnement par r currence raisonnement que les l ves ont souvent du mal ma triser Les exemples pr sent s sont principalement issus du domaine des math matiques et plus particuli rement de l arithm tique Deux algorithmes fondamentaux qui ont la particularit d tre utilis s dans de nombreux domaines de par leur effica cit sont pr sent s la m thode de dichotomie et l algorithme de H rner La deuxi me partie propose une introduction la partie de la logique ma th matique qui d finit les formules math matiques formelles Cette pr sentation est destination des professeurs souhaitant compl ter leurs connaissances en ce domaine afin de mieux dominer les savoirs logiques implicites dans les math ma tiques de la classe tant
71. s mantique de T o la notation T H F signifie qu il existe un sous ensemble fini 7 de formules de T tel que T F Ce th or me signifie intuitivement qu une formule est vraie quelque soit le sens que l on donne aux symboles propres au langage du premier ordre si et seulement si elle est d montrable Le second sens de l quivalence si une formule est d montrable alors elle est vraie assure que les r gles de d monstration que l on s est donn sont cor rectes L autre sens si une formule est vraie alors elle est d montrable assure que l on s est donn suffisament de r gles que le syst me de r gles est complet pour d montrer tout ce qui est vrai 2 4 Illustration de quelques r gles 1 Introduction de gt T AFB I n est un nombre entier naturel A l entier n est divisible par 6 rrFASB B l entier n est divisible par 3 La r gle d introduction du formalise la d monstration d un th or me de la forme Si alors La formalisation ci dessus peut tre lue comme partir des hypoth ses n est un entier T et n est divisible par 6 A 60 Introduction la logique math matique on d montre n est divisible par 3 B On d duit que sous l hypoth se n est un entier IT la formule si n est divisible par 6 alors n est divisible par 3 A B est vraie Elimination de A AFANB AFA nest un no
72. s le livre IX de ses El ments la proposition 20 suivante Les nombres premiers sont en plus grande quantit que toute quantit propos e de nombres premiers que l on nonce maintenant sous la forme Il existe une infinit de nombres premiers La d monstration d Euclide 5 7 d signe la d monstration de l implication A V B gt A B Cf Section 2 3 2 exemple 2 page 57 6 extraite de LES QUINZE LIVRES DES ELEMENTS GEOMETRIQVES D EVCLIDE traduicts du Fran ois par D HENRION A PARIS MDCX XXII 66 Introduction la logique math matique _ THEOR 18 PROP XX Quelque multitude de nombres premiers qu on propofe il s en trouuera encores d autres Soit quelconque multirude de nombres premiers A B C Te dis qu il s entrouueraencores d autres Car fiontronucle nombre D le plus nemem eiename petit de tous ceux qui peuuent efre mefu Ast Bt Crow 5 rez par les trois nombres A B C par ta 37 De 30 E F rop 7 amp icel y D E on adioutte l vnit mn F le rout D F fera premier ou non S il eft premier onayn nombre premier autre que pas vn des propofez Mais fi DF n eft premier il fera mef ri parquel que nombre premier par la 34 prop 7 Soit donc mefur par G il eft uidenc ue G ne peut paseftre vn des trois A B C car s il eftoit quelqu vnd iceux h prial comme eux DE DoncG mefurant le roue DF amp le retranch DE p la12 comm fent il mefureroit auf le refte
73. s qui ont l habitude de manipuler ces mat riels ont tendance inverser le sens de l af fectation lorsqu ils se mettent programmer sur ordinateurs Nous choisirons comme symbole car il est coh rent avec les notions de partie gauche et par tie droite qui se retrouvent dans tous les langages utilis s par les ordinateurs et il ne comporte pas le symbole qui perturbe les l ves car il a pour eux une autre signification l galit En r sum notre instruction d affectation sera expression partie gauche expression partie droite et se lit L expression partie gauche re oit la valeur de l expression partie droite Exemples k lt 0 la variable k re oit la valeur 0 k k l la variable k re oit la valeur de l expression k 1 k a 10 b n la variable k re oit la valeur de Il expression a b 10 n 1 2 2 Les instructions conditionnelles Ces instructions sont le si alors et le si alors sinon L instruction si alors Elle s crit 1 2 Pr sentation d un langage d criture des algorithmes 5 si expression bool enne alors instruction Si l valuation de l expression donne la valeur vrai c est l instruction qui suit imm diatement le alors qui est ex cut e sinon c est I instruction suivante celle qui suit le si alors qui est ex cut e Dans le cas o l on souhaiterait ex cuter apr s le alors non pas une mais plusieurs instructions on cr
74. seurs d un nombre entier changement de base 1 5 1 Construction de la liste des nombres premiers par la m thode du crible d Erathost ne Cette m thode permet d tablir la liste de nombres premiers inf rieurs un nombre entier n donn Son principe est tr s simple On crit la s quence de tous les nombres entiers de 1 jusqu n on barre 1 qui n est pas premier on garde 2 qui est premier et on barre tous les nombres multiples de 2 on garde 3 et on barre tous ses multiples puis on recherche a partir de 3 le premier nombre non barr on le garde et on limine en les barrant tous les multiples de ce nombre et on continue ainsi jusqu puiser toute la liste Les nombres non barr s constituent la liste 18 Algorithmique des nombres premiers inf rieurs ou gaux n Avant d crire plus pr cis ment cet algorithme il nous faut choisir une repr sentation informatique qui traduit le fait qu un nombre soit barr ou non Pour cela on peut utiliser un tableau de n l ments index s de 1 jusqu n Les composantes de ce tableau pouvant avoir soit une valeur bool enne vrai faux soit une des deux valeurs 0 ou 1 Ainsi la valeur de la composante de rang nous indiquera si le nombre 2 est premier ou non la valeur vrai ou 1 signifie oui la valeur faux ou 0 signifiant non Algorithme 13 Crible d Erathost ne Entr e un nombre entier n Sortie la liste des nombres premiers inf rieurs ou
75. ssions ne peuvent avoir que deux valeurs possibles vrai et faux On peut dire simplement qu elles sont obtenues en comparant entre elles deux ex pressions dont la comparaison est possible l aide des op rateurs classiques de comparaison lt lt gt gt Des expressions plus complexes pouvant tre construites en utilisant les op ra teurs logiques classiques ou et non qui d notent respectivement la disjonction la conjonction et la n gation 1 informaticien c l bre pour ses travaux en algorithmique cr ateur de TEX 4 Algorithmique 1 2 1 L instruction d affectation La syntaxe de cette instruction varie suivant les langages utilis s Elle a pour but d affecter une variable la valeur d une expression En g n ral dans les langages de programmation sa forme est wo wo expression partie gauche symbole expression partie droite L expression en partie gauche doit imp rativement d signer une adresse et une valeur est associ e l expression de la partie droite Elle a pour but de ranger la valeur de l expression l adresse indiqu e par la partie gauche Comme il a t dit le symbole varie suivant les langages de programmation en Algol Pascal Maple en Basic C CAML en LSE Signalons que sur certaines calculatrices de poche TI Texas Instrument le sym bole utilis e pour l affectation est Cela est tr s ennuyeux car les l ve
76. t qui est la th orie des fonctions calculables sur machines L approche logique s av re galement pertinente pour le d veloppement des lan gages de programmation Par exemple la programmation logique n e en 1973 Luminy PROLOG quipe d A Colmerauer est un langage informatique dans lequel on peut consid rer un programme comme une recherche de preuve bas e sur des m thodes de d monstration automatique Autre exemple les langages de programmation fonctionnelle Le paradigme connu sous le nom d isomorphisme de Curry Howard tablit une parfaite correspondance entre programmes et d monstrations formelles on identifie une t che avec une formule math matique et on identifie un programme satisfaisant cette t che avec une preuve de l nonc Notons que ces m thodes permettent d obtenir des programmes s rs i e qui font bien ce que l on attend d eux Enfin le cadre th orique pour tudier certains aspects de la complexit des programmes se situe dans le champ de la Logique 1 Il n est pas suffisant de savoir que l on dispose d un algorithme d un programme pour r soudre un probl me encore faut il que la r ponse rendue par l ordinateur arrive en temps rai sonnable 44 Introduction la logique math matique 2 2 Un langage math matiquement d fini Un des premiers objets de la logique math matique est la formalisation du langage math matique Il s agit de d finir les nonc
77. te propri t reste vraie la fin de chaque it ration On commence par modifier q et w q 2 x qet w w tant divible par 2 Deux cas sont envisager r lt w Onag 2 xq w etr r qxw r 2xqx r qxXxwtr a par hypoth se de r currence Par ailleurs on a 0 lt r lt w w lt r Ona d 2xq 1 w etr r w g xw r 2xqg 1 x r q Xv Pri qxw r a par hypoth se de r currence On est dans le cas o w lt retr r w ainsi on a 0 lt r D autre part par hypoth se de r currence r lt w donc r 5 lt w 3 7 ainsi r lt w Ainsi la fin d une tape on a encore les in galit s 0 lt r lt w 1 4 Un principe fondamental la dichotomie Le mot dichotomie provient du grec di deux et tomein couper ce qui signi fie litt ralement couper en deux Ce principe tr s efficace et relativement facile mettre en uvre intervient dans de nombreux algorithmes Calcul des z ros d une fonction Algorithmes de recherche Algorithmes de classement Sa mise en uvre permet d aborder et d illustrer les probl mes fondamentaux que nous avons voqu s pr c demment 1 4 Un principe fondamental la dichotomie 15 1 4 1 M thode de dichotomie pour le calcul d un z ro d une fonction Soit f une fonction continue sur un intervalle a b qui change de signe entre a et b Le principe de dichotomie permet en divisant ch
78. tion 10 Formules du premier ordre sur Soit un langage du premier ordre On d finit par induction l ensemble des formules sur Si R est un symbole relationnel d arit n et si t1 t sont n termes alors D R t1 t est une formule atomique Si det w sont des formules alors o daw o V A gt sont des formules Si est une formule et x est une variable alors Vx et 4xz sont des formules On peut d finir comme pr c demment l arbre de d composition d une for mule sur les feuilles sont toujours les formules atomiques EXEMPLE Consid rons la formule R x y V Ge fla x y AyG2 g x A x y son arbre de d composition est gt we co wee Ay See R x y IT Jr aS flas y gla z T Y On s attarde ensuite sur la notion d occurrence et surtout de variable libre qui est importante pour l interpr tation des formules quantifi es 2 2 Un langage math matiquement d fini 51 D finition 11 occurrence Une occurrence de x dans d signe une place particuli re de cet x dans On peut rep rer cette place dans la feuille de l arbre de construction de dans laquelle x est produit Il peut y avoir plusieurs occurrences de x dans une m me feuille ex dans R x x y ou plus g n ralement dans une m me formule Une occurrence de x dans est li e ssi la feuille dans laquelle on cons
79. un entier n en base b avec une table Entr e Un nombre n crit en base 10 Sortie La table T des coefficients a de l criture de n en base b aen 1 0 tant que a 0 faire r a mod b Tir i i 1 a a div b r sultat T ao a1 ax_1 4x 1 5 Quelques algorithmes l mentaires en arithm tique 21 1 5 4 Conversion d un nombre crit en base b en d cimal Soit axax_1 a1ao l criture en base b du nombre que l on veut conver tir en criture d cimale Pour obtenir cette conversion il suffit d valuer apb ag108 a b ao en effectuant les calculs en base 10 On suppose dans les algorithmes pr sent s ci dessous que les coefficients de l cri ture en base b sont rang s dans une table Algorithme 18 Conversion en d cimal d un nombre crit en base b Entr e Un nombre a a _1 1d9 crit en base b Sortie Le nombre n qui correspond la conversion de azax _1 a1 ao p en base 10 n 0 pour 7 variant de 0 jusqu k faire nn a x b r sultat n L algorithme pr c dent n est pas performant car il effectue un trop grand nombre de multiplications En effet pour calculer b il est n cessaire de faire i 1 multipli cations ainsi l tape 2 on effectue 2 multiplications soit au total 1 2 k EXD multiplications C est beaucoup trop Voici un algorithme qui n en effectue plus que 2 k 1 pour calculer la m me expression Algorith

Algorithmes et logique au lycée - IREM d`Aix

Contents

Download Pdf Manuals

Related Search

Related Contents

Algorithmes et logique au lyc&eacute;e - IREM d`Aix

Contents

Download Pdf Manuals

Related Search

Related Contents

Algorithmes et logique au lycée - IREM d`Aix