Algorithmique - Raisonner Pour Concevoir

AlgorithmiqueRaisonner pour concevoir

ChristopheHARO

RsumCe livre sur lalgorithmique est destin toute personne qui sintresse au dveloppement dapplications informatiques et qui souhaite sinitier ou retrouver les bases fondamentales de la programmation. Il ne sagit pas ici de programmer avec un langage ou un autre, mais bien de raisonner sur un problme pour concevoir une solution abstraite. Ce travail de rflexion et de conception prpare le stade ultime de limplmentation et du cycle de vie du programme concret. Le lecteur ne trouvera pas dans ce livre un recueil dalgorithmes quil devra ensuite adapter pour rsoudre des problmes mais au contraire une introduction originale et efficace lalgorithmique pour apprendre analyser un problme. Le livre est divis en deux parties. Dans la premire partie sont dtailles les notions dalgorithmique de base et la mthode de construction raisonne dun algorithme impratif : lauteur y prcise notamment la distinction entre la spcification et la ralisation dun algorithme et montre que lalgorithmique proprement dite sarrte l o commence la programmation. Dans la deuxime partie lauteur propose cette fois des solutions des problmes plus labors dans divers domaines du calcul automatique, comme la simulation de phnomnes alatoires ou le cryptage des donnes. Toutes les activits proposes restent lmentaires avec le souci constant de privilgier le raisonnement qui conduit llaboration des algorithmes.

L'auteurIngnieur et docteur en informatique, Christophe Haro a enseign l'informatique l'universit et en cole d'ingnieurs pendant 22 ans. Depuis prs de 10 ans il enseigne le gnie logiciel, le dveloppement d'applications informatiques et les architectures logicielles en BTS Informatique de Gestion. C'est toute cette exprience pdagogique qui donne ce livre son efficacit pour aborder l'algorithmique.

Ce livre numrique a t conu et est diffus dans le respect des droits dauteur. Toutes les marques cites ont t dposes par leur diteur respectif. La loi du 11 Mars 1957 nautorisant aux termes des alinas 2 et 3 de larticle 41, dune part, que les copies ou reproductions strictement rserves lusage priv du copiste et non destines une utilisation collective, et, dautre part, que les analyses et les courtes citations dans un but dexemple et dillustration, toute reprsentation ou reproduction intgrale, ou partielle, faite sans le consentement de lauteur ou de ses ayants droit ou ayant cause, est illicite (alina 1er de larticle 40). Cette reprsentation ou reproduction, par quelque procd que ce soit, constituerait donc une contrefaon sanctionne par les articles 425 et suivants du Code Pnal. Copyright Editions ENI

ENI Editions - All rigths reserved - Jonifar lina

- 1-

1

Questcequelalgorithmique?On sintresse lactivit de programmation dun ordinateur qui permet de rsoudre des problmes dune faon automatique. On se place un niveau conceptuel dans lequel un problme quelconque, informatique ou non, est caractris par un ensemble de donnes dentre et des rsultats attendus. On peut donc reprsenter ce niveau danalyseparleschmadelafigurecidessous.

Exemple Ondonnelesingrdientssuivants : Thym laurier persil ail huile vinaigre sel poivre citron et un brochet de trois livres. Prparer une marinade de brochet. Dans cet exemple, le problme est reprsent par les donnes : le thym, le laurier, ..., le brochet dont on connat le poids et par le rsultat attendu qui est un plat cuisin : une marinade de brochet. Ce nest pas (pas encore) un problmequiseposehabituellementeninformatique,maisilseposedanslesmmestermes. Exemple Ondemandedecalculer,pouruneannedontondonnelemillsime,lejourdelasemaineotombelepremiermai. Ici, les donnes sont constitues dun millsime, comme 2005 par exemple. Le rsultat attendu est un jour de la semaine,commedimancheparexemple. Dans ces exemples, le problme est constitu dun jeu de donnes. Le rsultat attendu doit tre obtenu par des transformationsfairesubirauxdonnes cestcequereprsentelafigurecidessus. Lesproblmesauxquelsonsintressedanscelivresontrsoluslaidedunordinateur.Unordinateurestconstitu dune machine matrielle complte dun ensemble de composants priphriques, comme un clavier, une souris, une table traante... La machine matrielle est constitue, en premire approximation, dune unit centrale, charge deffectuer les calculs, complte dune mmoire, permettant denregistrer les donnes, les rsultats des calculs intermdiairesetlesrsultatsattendus.Pourrsoudreunproblmeaveclaidedunordinateur,ilfautenregistrerdans sa mmoire, dune part les donnes du problme, quil devra transformer pour obtenir le rsultat attendu et, dautre part,lasuitedesinstructionsquelunitcentraleducalculateurdevraexcuterpoureffectuerlestransformationsdes donnes.Lersultattantobtenu,ilseradabordenregistr,commelesdonnes,danslammoire.Lafiguresuivante reprsenteceslments.


- 1-

2

Unpriphriquedentrepermetdecommuniquerauprogrammelesdonnestransformer.Unprogramme,constitu dinstructions en langage machine excutes par lunit centrale, les transforme et produit des rsultats qui sont envoysaupriphriquedesortie. Un premier lment, remarquable ici, est larchitecture mise en uvre. Les instructions machine excutes par lunit centraleetlesdonnessurlesquellesellesagissentsontrangesetcohabitentdanslammemmoirecentrale.Une tellearchitectureestcelledesordinateursdepuisleurtoutdbut,danslapremiremoitiduvingtimesicle.Elleat invente et thorise par John VON NEUMANN et Alan THRING. Dans cette architecture, lunit centrale nexcute quuneseuleinstructionlafoisetcesinstructionssontexcutessquentiellement,luneaprslautre,dansunordre prtabli et dfinitivement fix. On dit quil sagitdune machinesquentielle pour caractriser un tel comportement. Il existedautrestypesdemachinesquinenousintressentpasdanscelivre. Une deuxime proprit importante de telles machines est que les mmes donnes, communiques au mme programme, produisent les mmes rsultats, indpendamment de lenvironnement et du moment de lexcution des instructions. On dit alors que ce type de machine est dterministe. L encore, ce nest pas la seule architecture matriellepossible,maiscelivreserestreintcecas. Pour obtenir un programme et les instructions qui le composent, on le prpare en utilisant un langage de programmationlaideduqueloncritlesinstructionsquitransformentlesdonnes.Ilexistedenombreuxlangagesde programmation de haut niveau, certains ddis des tches spcifiques, comme les tableurs par exemple, dautres destinscriredesprogrammesplusgnraux,commeJAVA,PHP,C...Lafigurecidessousreprsentelesrelations entreunprogrammedehautniveauetlecalculateurauquelilestdestin.

- 2-


3

Pourpasserdesdonnesdunproblmeauxrsultatsattendus,onconsidreunemachinefictivecaractriseparun comportementquiluipermetderaliserlesoprations.Cettemachinefictive,commesonmodle,lordinateurdeVON NEUMANN, neffectue quune seule opration la fois pour raliser un traitement prcisment dfini. Les oprations sorganisent en une suite ordonnes dinstructions qui oprent sur de linformation symbolique, cestdire sur une suitedesignesalphabtiques,numriques,lexicaux.Cettemachinefictiveestdoncunemachinesquentielle,comme sonmodle.Onappellecalculunesuitedetraitementsralissparcettemachine,machineabstraitelecalculateurfictif etprogramme abstraitlasuitedinstructionsprparespourunetellemachine.Cependant,alorsquelesprogrammes critsdansunlangagedeprogrammationetdestinsuncalculateurconcretdoiventrespecterunesyntaxeprciseet rigide,lesprogrammesabstraitsnesontcontraintsparaucunerglede grammaire ,aucunesyntaxeimpose.Ence sens, un programme abstrait nest pas un programme et nutilise pas un langage diffrent du langage naturel. On appellealgorithmeunprogrammecritpourlamachineabstraite.Lafigurecidessousreprsentelesrelationsentrela machineabstraiteetsonmodle,lecalculateurconcret.


- 3-

4

Toutordinateuretsonlangagesontdonclaralisationparticuliredune machine abstraite. Cependant, alors que le programmeconcret,destinuncalculateurconcret,appartientlespacedelasolutionduproblmequenousvoulons rsoudre,lamachineabstraiteetsonlangage,lalgorithme,appartiennentlespaceduproblmersoudre.Lafigure cidessus montre les diffrents espaces dintervention. Lalgorithme est le langage de la machine fictive. On y reconnatdeuxdomainesindpendantsetbiendistincts :q

la spcification du problme qui le dfinit entirement et dune faon non ambigu. Cest le domaine des Mathmatiquesetdelalogique. Lesinstructionsdelamachinefictiveestundomainequiassurelatransitionverslesinstructionsenlangagede hautniveaudestineslamachineeffective.

q

Danslespacedelasolution,lelangagedehautniveauetlelangagemachineralisentlesinstructionsdelamachine effective. Pour tre plus prcis, il faudrait considrer que le langage de haut niveau introduit une machine fictive intermdiaire,maiscelaneserapasfaiticipoursimplifier.

- 4-


5

StructuredulivreCelivrenesintressequlamachineabstraite,danslespaceduproblme,pourlaquelleiltudieunealgorithmique particulire : lalgorithmique imprative ou procdurale. Il est divis en deux parties. La premire regroupe les chapitres 2 7. Cest dans cette partie que sont abordes les notions dalgorithmique de base et la mthode de constructionraisonnedunalgorithmeimpratif.Ladeuximepartiestenddeschapitres812.Onycherche,cette fois,dessolutionsdesproblmespluslaborsdansdiversdomainesducalculautomatique. Le chapitre 2, Programmes directs montre quelques exemples dalgorithmes, emprunts au quotidien, et tente de dfinir la nature des algorithmes tudis dans cet ouvrage. On y prcise, notamment, la distinction entre la spcificationetlaralisationdunalgorithmeetonmontrequelalgorithmiqueproprementditesarrtelocommence laprogrammation.Enparticulier,rsoudreunproblmeconsistepasserdesdonnesauxrsultatsattendusparla suite squentielle des transformations faire subir aux donnes. Cependant, la description de ces oprations peut sexprimerdediffrentesfaonset,encesens,lalgorithmiquenest pas la programmation. On aborde les notations quiserontutilisespourexprimerdestransformationssanscontrleduflotdinstructions. Lechapitre 3,Lalternative tudie lunedesconstructionsfondamentalesdelalgorithmique :lalternative.Ellepermet dechoisirlestraitementsraliserenfonctiondeconditionssurlesdonnes,exprimeslaide de prdicats de la logique boolenne. Cest la premire structure tudie pour contrler le flot dinstructions. De nombreux exercices permettentdelamettreenpratique. Le chapitre 4 Structures lmentaires dbute ltude des chanes de caractres et des tableaux statiques simples (vecteurs).Oncommenceprpareretutiliserquelquesdfinitionsdalgorithmeslaborsquiinterviennentsurces structuresdedonnes.Lechapitremontreensuitecommentdfinirdenouveauxtypesdedonnespartirdestypes debaseetproposequelquesexercicesdapplication.Cependant,celivrenetraitepasdesstructuresdedonnes.On ny trouve pas dtude des listes, files, arbres... De nombreux livres, certains excellents, tudient ces domaines en dtail.Ici,seulsleschanesdecaractresetlestableauxstatiquessontutiliss,maiscommesupport,commeprtexte ladfinitionraisonnedalgorithmeslmentaires.Lobjectifdulivreestleraisonnementlabasedelaconstruction dalgorithmesetnonpaslasolutionauxproblmesgnriquesdelaprogrammationinformatique. Nous verrons dans le chapitre 5 Rcursivit que lon peut ainsi spcifier un algorithme dune faon opratoire, sans formalismemathmatiqueexcessif.Deplus,onpeutalorsdistinguerplusclairementspcificationetralisation. Lechapitre 6Itrationestfondamental.Onyapprendunemthodesystmatiquedeconstructiondesitrations.On montre laide dexemples varis quune itration est lexpression algorithmique dune rcurrence mathmatique. Lhypothse de rcurrence permet de construire le corps de litration et de dfinir sa proprit invariante. La rcursivitestutilisepourlaspcificationdesalgorithmesitratifs. Lechapitre 7RcursivitouItration?complteleschapitresRcursivitetItration. Lechapitre 8Trierabordeunvastesujet,letridedonnescomparables,parquelquesexemplesusuelsdudomaine. Ontudieavecsoinlaspcificationduntri.Cestunproblmegnraldifficile,maislesalgorithmesdetriprsents sontceuxhabituellementtudisdansuneinitiationlalgorithmique. Leschapitresprcdentsontintroduitplusieursreprisesleproblmedelditiondunnombrequiconsisteobtenir unechanedecaractresreprsentantsavaleurdansunebasequelconque.Lechapitre 9ditiondunnombreralise une synthse de ce sujet en rsolvant entirement les problmes dj rencontrs dans les chapitres prcdents. Il tudie galement un petit cas de gestion concernant lidentification des entreprises et de leurs tablissements. Il proposeaussilarsolutiondeproblmesdemmenature,commelidentificationISBNpourleslivresparexemple. Les premires notions sur les fichiers sont abordes au chapitre 10 Introduction aux fichiers. Ltude reste lmentaire.Elleprsentelesorganisationssquentiellesetadressablespuislesmodesdaccsassocis.Laccentest missurlestraitementsdesfichiersaccssquentiel. Le chapitre 11 Simuler montre comment simuler le hasard . Des exemples simples permettent dintroduire la simulationdephnomnesdterministesaussibienqualatoires. Lechapitre 12Crypterestencoreunprtextelcrituredalgorithmessimples,maissurdesexemplesempruntsla cryptographiecettefois.Lencore,lesujetconcernelesraisonnementstudisdansleschapitresprcdentsetles notionsabordesrestenttriviales. Onnetrouveraquasimentjamais,danscelivre,decodecritdansunlangagedeprogrammation.Encoreunefois,il ne sagit pas ici de programmer, mais bien de raisonner sur un problme pour en concevoir une solution abstraite. Cependant,ilconvientdenejamaisperdredevuequelobjectifestbiendobtenir,infine,unprogrammeexcutable suruncalculateurconcret.Mmesi,danscelivre,onsarrtelocommencelaprogrammation,cetravailderflexion etdeconceptionprparelestadeultimedelimplmentationetducycledevieduprogrammeconcret.Redescendre ainsi surTerre imposeraparfoisdesajustementspouradapterlalgorithme,cestdireleprogrammequiciblela machineabstraite,auxcontingencesmatriellesdesmachinesconcrtesetdeslangagesdeprogrammationconcrets quisontladispositiondudveloppeur.Anticiponsdoncpourillustrercepointdunexemplesimple. Enalgorithmique,lecalculdelamoyennearithmtiquemdedeuxentiersaetbscritcommeenMathmatique :mqd =>nerienfaire.

q

Lestapesprcdentesdcriventleprocddecalculdeq d .Ellesconstituentunalgorithmepourlecalculduniveaude

dclenchement du rapprovisionnement. partir des donnes du problme, ici qs , dr et v1 , v2 , ..., v12 , des rgles opratoires permettent dobtenir un rsultat dfini. Mais pour accder ce rsultat, il faut passer par un ensemble dtapesintermdiaires :rcuprerlesdonnes,calculerunemoyenne... delammefaonquilfallaitprparerdabord une crme Chantilly pour raliser un SaintHonor. Ces tapes intermdiaires ne sont pas dcrites : on ne dit pas commentcalculerunemoyenne,commentcalculerleniveaudedclenchementqd laidedecettemoyenne,comment

prparer une crme Chantilly... Ces calculs intermdiaires, indispensables lobtention du rsultat, ne sont pas explicits. Lapprenti cuisinier sait prparer une crme Chantilly, car cest un pralable la ralisation dun Saint Honor alors,ildisposedetousleslmentspourraliserlarecettecomplte.Linformaticien,oulechefmagasinier, sait calculer la moyenne ncessaire et qd pour dterminer quand rapprovisionner. Dans le cas contraire, il faudra tudier lalgorithme de calcul de la moyenne. Le cuisinier se reportera la page 267 du livre de cuisine qui donne la recettequilnesaitpasencoreprparer.Danstouslescas,leproblmeestrsolugrceunsousalgorithmequiest unesolutionunsousproblmeduproblmeinitial. Exercice1:tapesdetchesquotidiennes numrerlestapeslmentairesordonnespourraliserlestchesquotidiennessuivantes : 1.prparerducaf 2.sortirlavoituredugarage.

- 2-


12

DfinitioninformelledunalgorithmeUn algorithme est la description dun procd. Il dcrit une succession doprations lmentaires, exprimes dans un langage donn, excuter dans un certain ordre. Lexcution nest possible que lorsque certaines conditions sont remplies.Lailnestajoutquelorsquilathach onnepeutcalculerleniveaudedclenchementqd quelorsquela moyennemvdesventesquotidiennesatobtenue.Lexcutiondesoprationslmentairesdontilsagitpermetde fairepasserlesystmeconsidr,duntatinitialI,reprsentparlesvaleursdesattributsdonns,untatfinalF, reprsentparlesnouvellesvaleursdesattributsetlesrsultatsobtenir.Pourladdition,lesattributsdonnssont les deux entiers a et b dont les valeurs sont respectivement 127 et 35. Ltat initial est reprsent par ces deux valeurs. Le rsultat est 162 et ltat final est reprsent par les trois valeurs 127, 35 et 162. La figure cidessous reprsentelesdeuxtatsetlatransitionquifaitpasserdelunlautre.

Ltat initial I ou e1 est caractris par les valeurs 127 et 35 de a et b, respectivement. Ltat final F ou e 2 est caractrisparcesmmesvaleurs127et35etparlavaleur162delasommedeaetb. Demme,ltatinitialIdelexempledegestiondestockestconstitudesattributsq s ,dretv1 ,v2 ,...,v12 .LtatfinalF estreprsentparlesvaleursdeq s ,v1 ,v2 ,...,v12 etlavaleurdunattributrsultat,disonsr,dontlavaleurVRAIou FAUXindiquesilyalieuderapprovisionnerounon.

Unalgorithmecorresponddoncunprocessusdcomposentapesdontlenchanement permet datteindre un but fix.Dounedfinitioninformelledunalgorithme : Dfinition On appelle algorithme un ensemble de rgles opratoires et de procds dfinis en vue dobtenir un rsultat dtermin au moyendunnombrefinidoprationssquentiellementordonnes. Lesexemplesdesparagraphesprcdentsmontrentquetoutalgorithmeestcaractrisparleslmentssuivants :q

lesoprationsraliserchaquetape lordredesuccessiondesdiffrentestapes lexistencedeconditionsdterminantounoncertainestapes undbutetunefin.

q

q

q

Lesoprationsdontilsagitsontdestinestreexcutesparunemachinefictiveafinderaliserlestransformations desdonnesquiproduirontlesrsultatsattendus.Onpeutschmatisercepointcommesurlafiguresuivante :

Commenousavonscommenclevoirsurlexempledeladditioncidessus,lestransformationssubiesparlesdonnes font voyager le systme logiciel entre des tats caractriss par les valeurs de certaines donnes. Nous y reviendrons. Cependant, il nexiste pas dalgorithmeausensproprequandonutiliseun langage suffisamment expressif. Ainsi, considronslexemplesuivant :


- 1-

13

Exemple5 Ondonnedeuxentiersaetb.Calculerleursomme. Cestleproblmedeladdition,djabordcidessus,maiscettefois,supposonsquenousdisposionsdunlangagequi connat laddition.Autrementdit,lesimplefaitdedemanderladdition,enexhibantlesnombresaetbadditionner, suffit produire le rsultat attendu. La situation est alors schmatise par le dessin de la figure cidessous, dans laquelleleblocdestransformationsfairesubirauxdonnesestvide.

Le langage utilisesthabituellementsuffisammentexpressif.Ilsuffitdexprimerlersultatpourobtenirlasolution. Ici, le rsultat est la somme de deux entiers. Il ny a pas dalgorithme dfinir quand il est possible dadditionneret dcriredirectement : Le R s u l t a t est a+b PourlarecetteduSaintHonor,silaprparationdelacrmeChantillyfaitpartiedescomptencesducuisinier,ilesten mesurederaliserlesobjectifsdelarecetteetilestinutilededtaillerlesoprationsncessairespourobtenircette crme.Demmelorsquelecalculdelamoyennearithmtiquefaitpartiedesoprationsdebasedelenvironnement,il estpossibledefaireappelcecalculpourobtenirleniveaudedclenchementpuisendduireladcisionprendreen cequiconcernelerapprovisionnement. Cependant,imaginonslasituationsuivante,danslaquelleonnedisposepas,dansltatactueldenosconnaissances, de lopration dadditions des entiers. On fait lhypothse que la seule opration connue est lincrmentation, par laquelle on ne sait quajouter 1 un entier. Comment alors additionner deux entiers ? Cette fois, le cadre des transformationsdelafigureprcdentenestplusvide.Ildevientncessairedeprciserlestapesdestransformations pourfairepasserlesystmedeltatinitialI,danslequelondonnelesvaleursdedeuxentiersaetb,ltatfinalF danslequelonobtientlasommea+b. Les deux figures prcdentes ne dcrivent pas compltement la ralit de lenvironnement dans lequel on tudie la rsolution dun problme par un algorithme. Les donnes sont habituellement accompagnes dunrpertoire dactions conditionn par lexpressivitdulangageutilispourtudieretexprimerlalgorithme.Danslexempleprcdent,sice rpertoirecontientladditiondesentiers,ilnestpasncessairedtudierunalgorithmepourrsoudreleproblme.Si, aucontraire,ladditionnestpasuneoprationdecerpertoire,ltudealgorithmiqueduproblmedevientncessaire. Ctait le cas, par exemple, pour la multiplication des entiers sur les premiers microprocesseurs. Le rpertoire des instructionsmicroprogrammesdecescomposantsnedisposaitpasdelamultiplicationetcellecidevaittretudieet implmentepartir,parexemple,deladdition. Ainsi, si le rpertoire dactions du langage utilis dispose du calcul de la moyenne arithmtique, on lutilise comme oprateurdebase sinon,ildevientncessairedtudierlesousalgorithmequicalculeracettemoyenne. Exemple6 Dansuneentreprise,deuxservicesemploientchacununequipedereprsentants.Certainsreprsentantsappartiennentaux deux services, mais pas tous. On veut attribuer une prime au seul reprsentant appartenant aux deux quipes et ayant ralislemeilleurchiffredaffairessurlanne.Leproblmeconsistedterminerlereprsentantquiseraprim. Ilestpossibledereprsenterlasituationcommesurlafigurecidessous.

- 2-


14

Lalgorithme consiste donc calculer lintersection des deux ensembles de reprsentants, puis dterminer, dans lensemble rsultat, celui des reprsentants qui a le meilleur chiffre daffaires sur lanne. Un langage qui dispose de loprationdintersectiondedeuxensemblesdedonnes,commeSQLparexemple,nencessitepasdautrepralable ce calcul et permet dobtenir immdiatement le meilleur commun aux deux ensembles sinon, il faudra tudier un algorithmeducalculdecetteintersection.


- 3-

15

SpcificationsUnetcheimportante,quandoncherchecrireunalgorithme,consistele spcifier.Ilsagitdedire,delafaonla plus prcise possible, ce que fait lalgorithme et, cela, sans exprimer comment il le fait. En ce sens, spcifier un algorithme,cestposerformellementleproblmequilrsout,commelamontrlechapitreprcdent.Cestunetape difficile, mais indispensable pour clairement dfinir lalgorithme et ses effets. Cette section introduit, par quelques exemplesetexercicesrsolus,cettetapedespcification.Elleestcompltedanslasuitedulivre,mesurequenous construironslesoutilsncessaires. Exercicersolu1:Feuxdecirculation Onconsidreunfeuquirglelacirculationuncarrefour. crirelalgorithmequidterminelacouleurdufeulorsduprochainchangement. Solution Untelfeusignaleltatdelacirculationquilrglepartroiscouleurs :vert,orangeetrouge.Lescouleurssenchanent dans cet ordre une cadence fixe. Lorsque la couleur est rouge, le changement refait passer le feu au vert. On ne sintresse quau changement de couleur, autrement dit, lopration qui fait passer de lune lautre, dans lordre prcis. Supposons que nous disposons dune opration, dsigne par successeur, qui prend en entre une couleur de lensembleC={rougevertorange}etquiretournesonsuccesseurdanslasuiteordonne(vertorangerouge). Avecceshypothses,lalgorithmescrit: Algorithme1:Changementdelacouleurdunfeuuncarrefour:version0.1

algorithme : changer la couleur Entre c : une COULEUR de lensemble {vert ; orange ; rouge} Effet c = successeur de ancienne valeur de c Cette notation prcise le nom de lalgorithme :changer la couleur. Elle indique aussi que cet algorithme utilise une donne,dontletypeestCOULEURetdsigneparlalettrec,pourralisersoncalcul.Cestlobjetduparagraphequi dbuteaveclemotEntrequededonnercetteprcision.Ledomainedesvaleursdecestclairementprcis:cest lensemble{vert orange rouge}.Cequiprcdedtaillelesprrequispourlefonctionnementdelalgorithme. Lorsquelalgorithmesetermineetproduitlesrsultatsdesontravail,onobtientunnouveltatdufeudecirculation. Ce nouvel tat est entirement dcrit, au moins pour cet exercice simplifi, par la couleur du feu cest ce que dit le paragrapheEffet.Onylitquelanouvellevaleurdec,cestdirelanouvellecouleurdufeu,estlavaleurquisuccde lancienne valeur de cette couleur. La construction ancienne valeur de c est mise pour indiquer que la valeur de c avant modification par lalgorithme est utilise. On voit donc que deux valeurs distinctes dec sont concernes : celle avant lexcution de lalgorithme, reprsente par la construction ancienne valeur de c, et la nouvelle valeur, celle calculeparlalgorithme,dsigneparc.Ilconvientdenoterquelanciennevaleurdecdisparatlorsquelalgorithmese termine.Ainsi,cettevaleurestmodifieparlalgorithme.Cestlaresponsabilitdechangerlacouleurdemodifiercette valeur.Commelavaleurdeccaptureltatdusystmelogiciel,lamodificationdecettevaleurmodifiecettat. Pourspcifierleffetdelalgorithme,onutiliselaconstructionc = successeur de ancienne valeur de c.Ilfautencore direcequefait successeur,autrementdit,lersultatqueproduitcetoprateur.Ceserafaitplusbas.Pourlinstant, restonsenlideintuitivesousjacente. Cette faon dcrirelalgorithmenestpasobligatoire.Ainsi,parexemple,onauraitpuutiliserdautres notations pour exprimerlammeide.Envoiciuneautre : Algorithme2:Changementdelacouleurdunfeuuncarrefour:version0.2

changer la couleur Donne c : une COULEUR de lensemble {vert ; orange ; rouge} Effet (ancien c = vert => c = orange) ou sinon (ancien c = orange => c = rouge) ou sinon


- 1-

16

(ancien c = rouge

=> c = vert)

Lesexpressionsutilisesexprimentlammeconditionqueprcdemment :lacouleurorangesuccdeauvert,rouge succde orange et vert succde rouge. Accessoirement, il nest plus indiqu sur la premire ligne quil sagitdun algorithme : cest vident. Entre a t remplac par Donne. Toute autre mthode pour prciser les donnes sur lesquellestravaillelalgorithmeauraittlgitime. La diffrence essentielle qui distingue cette description de la prcdente est la faon dont elle exprime leffet de lalgorithme.Aulieudefaireappelunsousalgorithmesuccesseurquilfaudraplustarddfinir,icilalgorithmeprcise, pourchacunedesvaleurspossiblesdeladonnedentre,lavaleurqueprendracensortie.Cestuneexpressionqui estunedisjonctiondeclausesboolennes.Lanotation : a n c i e n c = vert => c = orange exprimeque,lorsquelavaleurdecenentreestvert,elleestorangeensortie.Autrementdit,lecalculdelalgorithme consiste remplacer la couleur vert par la couleur orange. Le symbole = > est le symbole de limplication en Mathmatique. Prcisonsdavantage.Aulieudutiliserdesnombres,nousutilisonsdesdonnesduntypeparticulier:desCOULEURs dontlesvaleurssontassujettiesvoluerdansunensembledonn.Cetensembleestdfiniiciparnumration.Ilest possibleaussidedonnerunedfinitiondecetype,pourprciserentirementlesdonnesquienrelvent. type COULEUR contrainte de domaine {vert ; orange ; rouge} fin COULEUR Lexpression contraintededomaine exprimequetoutedonnedetypeCOULEURestassujettieprendresavaleur danslensembleprcis.Lencore,cenestpaslaseulefaondedfinircetype.Envoiciuneautre : type COULEUR dfini par lnumration {vert ; orange ; rouge} fin COULEUR Ayantposcettedfinition,onconsidrequenousdisposonsduntypeCOULEURcommeilexistedesnombresentiers oudesnombresdcimaux.Onpeutalorssimplifierlexpressiondelalgorithme1aveclesconventionssuivantes.Lenom de lalgorithme est fait dune chane de caractres unique : changer_couleur, ou changerCouleur, ou ce que lon voudra comme convention, pourvu quelle soit claire, sans ambigut. On prcise ensuite le type des donnes sur lesquelles il travaille en entre, cestdire les donnes quil doit recevoir et sur lesquelles il opre pour raliser lobjectifquiluiestassign :Entre c : COULEUR.Onindiquegalementquecetalgorithmeapourobjectifdemodifier la donne quil reoit en entre et que cette modification est sa raison dtre, sa responsabilit. Il sagit donc de prciser clairement que la donne c est la fois une donne dentre, partir de laquelle lalgorithmevatablirson calcul, mais aussi une donne de sortie, dont la nouvelle valeur est le but du calcul effectu. Il existe diffrentes conventionsquipeuventtreadoptespourprcisersimplementcespoints.Envoiciune : Entre Sortie c : COULEUR Laconventionquiserautilisedanscelivreestunementionpardfaut.Lorsquelalgorithmemodifiecertainesdonnes quil reoit en entre, on ne prcise rien de particulier. Ainsi donc, cest lorsquil nen modifie aucune quune mention expliciteserautilise.Ceserafaitplusbas.Pourcequiconcernelalgorithmeparticulierdechangementdecouleur,le lecteursaitquilmodifieladonneenentreparcequeriennevientinfirmercefait.Cependant,unautresigneindique cetteparticularit. Lalgorithme retient la valeur de la donne dentre. Il restitue cette valeur lorsquil sagit de prciser leffet de lalgorithme.Pourobtenircettevaleur,laconstructionancienne valeur de couancien catutiliseprcdemment. Cette construction signifie que lalgorithme utilise un oprateur, not ici ancien par exemple, et que cet oprateur permet de dterminer la valeur de c avant lexcution du calcul. Ainsi donc, dune valeur c donne, cet oprateur en dtermine une autre. Pour cette raison, la notation fonctionnelle sera utilise dans la suite et justifie plus tard. Par consquent,lavaleurdecavantlexcutiondelalgorithmeseraobtenueparancien(c). Il reste dire clairement ce que fait lalgorithme.Cest le paragraphe introduit parEffet qui lexprime. Au lieu du mot effet,cestlemotpostconditionquiserautilis : postcondition c = s u c c e s s e u r (a n c i e n (c)) Cette clause exprime que la nouvelle valeur de c calcule par lalgorithme est gale au successeur de la valeur que possdaitcavantlexcutiondelalgorithme.Onneditpascommentcersultatestcalcul,maisseulementcequefait lalgorithme :ilcalculelesuccesseurdec et lutilisepourmodifierc.Ainsi,lexpressiondsigneparpostconditionest uneexpressionquiestsoitVRAIEsichanger_couleurfaitcorrectementsontravail,soitFAUSSEsinon.Cestdoncune

- 2-


17

expressiondontlersultatestBOOLEN.Onparledanscecasdeprdicat. Onpeutdoncprsentdonnerunedfinitiondechanger_couleurutilisantcesconventions : Algorithme3:Changementdelacouleurdunfeuuncarrefourversion1.0

algorithme : changer_couleur Entre c : COULEUR postcondition c = successeur ( ancien ( c ) ) fin changer_couleur LorsqueloprateursuccesseurfaitpartiedurpertoiredebasedulangageetqueletypeCOULEURatdfini,cet algorithme est entirement spcifi. Cependant, le type COULEUR ayant t construit pour les besoins du problme particulierrsoudre,loprateursuccesseurnestpasencoredfini.Parconsquent,lalgorithmechanger_couleurne prendratoutsonsensquelorsqueloprateurseracompltementspcifi.Ceserafaitplusbas. Cette dfinition de changer_couleur peut encore scrire de plusieurs faons quivalentes, utilisant des conventions lgrementdiffrentes.Envoicidautres. Algorithme4:Changementdelacouleurdunfeuuncarrefourversion1.0

changer_couleur(c : COULEUR) postcondition c = successeur ( ancien ( c ) ) fin changer_couleur Cettefois,lesdonnesdentre,cellespartirdesquelleslalgorithmeralisesoncalcul,sontprcisesderrirelenom de lalgorithme. Cest cette notation quutilisent tous les langages impratifs, avec parfois quelques variations syntaxiquesdanslapositiondeslments.Lapremireligneestalorsappelelasignaturedelalgorithme. Revenonsaufonctionnement.changer_couleurfaitpasserlesystmeduntatinitialIdanslequellefeuaunecouleur cquelconquedudomainedutypeCOULEUR,untatfinalFdanslequellacouleurcdufeuestdevenuelesuccesseur delanciennecouleur.Lafigurecidessousreprsentelvolutiondelasituationparundiagrammedtats.

La transition de ltat initial ltat final est assure par lopration changer_couleur. Finalement, le calcul du changementdecouleurpeutscrirecommecidessous : Algorithme5:Changementdelacouleurdunfeuuncarrefourversion2.0

changer_couleur(c : COULEUR) # Modifier la couleur du feu qui rgle la circulation dun # carrefour. prcondition aucune postcondition c = successeur ( ancien ( c ) ) fin changer_couleur Leslignes : # Modifier la couleur du feu qui r le la circulation dun g # carrefour. formentuncommentaire.Ilnintervientpasdanslalogiquedesoprationsdelalgorithme.Sonbutestdeclarifierune situationenapportantuneprcisionsupplmentaireparrapportauxinstructionsoprationnelles.Laclauseintroduite parprconditionindiquelesconditionsquedoiventsatisfairelesdonnespourquelalgorithmefassecorrectementson


- 3-

18

travail.Ici,aucuneconditionparticulirenestimposeauxdonnesdentre. Il est important de bien se convaincre que cet algorithme ne dit rien sur la faon dont il calcule la couleur que doit prendrelefeu.Ilneditpascommentilralisececalcul.Ilneditquecequilfait :calculerlaprochainecouleurdufeuen utilisantlesuccesseurdelacouleuractuellecquilareueenentre.Cestlanouvellecouleur,quiremplacelancienne dansc,quirsulteducalculdechanger_couleur. Pour que cette dfinition soit complte, il sagit, prsent, de prciser ce que fait lopration successeur. Cette prcisionnestncessairequesilnestpasunoprateurdurpertoiredinstructionsdenotre langage .Ainsi,siune COULEURtaitunnombreentierparexemple,ilneseraitpeuttrepasncessairededfinircetoprateur. Pour le dfinir, il suffit de prciser sa signature et la valeur du rsultat quil calcule cest ce que fait lalgorithme ci dessous. Algorithme6:Oprateursuccesseurversion1.0

Algorithme successeur # Le successeur de c dans la liste (rouge ; vert ; orange). Entre c : COULEUR Rsultat : COULEUR prcondition aucune postcondition # c nest pas modifi. ancien(c) = c # Dfinition du rsultat calcul. (c = vert => Rsultat = orange) ou sinon (c = orange => Rsultat = rouge) ou sinon (c = rouge => Rsultat = vert) fin successeur Lapostconditionestconstituededeuxclauses.Lapremireprcisequelacouleurcreueenentreparlalgorithme successeurnestpasmodifie.Lasecondeexprimecequefaitlalgorithme. Il existe une diffrence essentielle, fondamentale, entre cette opration et lalgorithme prcdent. Lalgorithme changer_couleurapourbutdemodifierltatdusystme.Ilprendunecouleur,valeurdec,etillamodifie.Lavaleur decnestpluslammequecellequelleavaitenentrelorsquelalgorithmesetermine.Aucontraire,successeurne modifierien cestcequexprimelapremireclausedelapostcondition : a n c i e n (c) = c La valeur de c la fin de lexcution de lalgorithme est la mme que celle de c lorsque lalgorithme commence son calcul.Ilnefaitquecalculerunenouvellevaleurpartirdunedonnecquirestecequelleest,immuable.Loprateur successeurestdelammenaturequuneopration,comme2+3parexemple.Cetteoprationprenddeuxnombresen entre,2et3etcalculeunrsultat,5,sansmodifierlesnombres2et3.Cestcequefaitloprationsuccesseur :elle prendunecouleurcetcalculeunrsultat,lesuccesseurdec,sansmodifierc.Cestaussicequexprimelanotation : Rsultat : COULEUR EllesignifiequesuccesseurretourneunrsultatdetypeCOULEUR,comme2+3retourneunrsultatdetypeENTIER, sansmodifierloprande,cestdireladonnedentrec,ellemmedetypeCOULEUR.Leffetdelalgorithme,prcis parlesclausesdelapostcondition,utiliseencoreletermeRsultat,quiexprimebienquunenouvellevaleurvientdtre obtenue. Lanotationfonctionnelleintroduiteplushautmontremieuxencorecettediffrencedenatureentrechanger_couleuret successeur: Algorithme7:Changementdelacouleurdunfeuuncarrefourversion2.1

successeur(c : COULEUR) : COULEUR # Le successeur de c dans la liste (rouge ; vert ; orange). prcondition aucune postcondition # c nest pas modifi.

- 4-


19

ancien(c) = c # Dfinition du rsultat calcul. (c = vert => Rsultat = orange) ou sinon (c = orange => Rsultat = rouge) ou sinon (c = rouge => Rsultat = vert) fin successeur Cettefois,lesdonnesdentressontprcisesdanslasignature.Lamentioncomplmentaireindiquequelalgorithme calculeunrsultatetquecersultatestdetypeCOULEUR.Ainsi,troislmentsdelanotationdecetypedalgorithme concourentindiquerquilnemodifiepaslesdonnesquilreoitenentrepoureffectuersescalculs :q

lasignatureportementiondutypedursultatcalculet retourn lutilisateurlogicieldesesservices une pseudovariable note Rsultat reoit la valeur calcule par lalgorithme. Cest cette valeur qui est retourne au client logiciel lorsque lalgorithme se termine. Ainsi, la valeur rendue au client est celle que possdecettepseudovariablelorsquelinstructionfinestatteinte lapostconditioncontientuneclausequiindiquequelavaleurdechacunedesdonnesdentreresteconstante pendantlescalculsdelalgorithme.

q

q

Letypedursultat,indiqudanslasignaturedelalgorithme,estletypedelapseudovariableRsultatquinestdonc pasdclareentantquetelle. On peut remarquer, cependant, que la conjonction de ces trois conventions est redondante. En effet, les deux premiressuffisentqualifierlalgorithmepourlequelonpeutaccepterimplicitementquilnemodifiepaslesdonnes en entre, ds lors que la pseudovariable Rsultat apparat. Le simple fait de donner la signature de lalgorithme montrequilestdelaclassedesoprationsquicalculentunrsultatsansmodifierlesdonnessurlesquellesilopre, commeuneadditionnemodifiepaslesoprandespourcalculerleursomme.Ainsi,lamentionancien(c) = cnestpas ncessaireet,pourlalgorithmedeloprationsuccesseur,onpeutaffirmerquecestunprdicatimplicitequiparticipe sapostcondition.Onsautoriseradoncnepasleprciserlorsquaucuneambigutnestcraindre. Enfin,iciencore,onneditquecequefaitlalgorithme,sansdirecommentillefait.Cestquedirecommentilfaitson travailestplusdifficile.Ceseratudiplustard. Finalement,nouspouvonsrsumercequenousavonsapprisdanscetexemple. Unalgorithmeestcritsanscontraintedesyntaxeautrequecellequipermetdelexprimersansambigut.Ainsi,les conventionsdcritureexposesdanscettesectionnesontpasobligatoires.Ilestpossibledenadopterdautresetle seulcritrequidoitguiderlauteurdelalgorithmeestsacorrectionetsalisibilit. Nous avons mis en vidence deux classes dalgorithmes. Les uns prennent des donnes en entre pour calculer un nouveau rsultat et ce calcul ne modifie pas les donnes utilises. La signature dun tel algorithme fait apparatre le typedursultatcalcul.Deplus,cersultatestsymbolisparlexpressionRsultatquiestdonclavaleurproduitepar lalgorithme au bnfice des logiciels clients de ses services. Ce rsultat devient disponible ds que lalgorithme se termine, cestdire juste avant lexpression de la fin annonce. Un tel algorithme sera appel une fonction dans la suitedulivre.Ilressembleunefonctionmathmatiquequicalculeunrsultatpartirdeparamtressanslesmodifier. Iladonclestatutdune requtequi interroge lesystmelogicielpourobteniruneinformationquidpenddeson tatsansmodifiercettat. Dfinition Unefonction(requte)estunalgorithmequirendunrsultatsansmodifierltatdusystmelogiciel. Lautre classe dalgorithmesregroupeceuxquinecalculentpasunrsultat,maisquimodifientcertainesdonnesqui leur sont communiques. Ils modifient donc ltat du systme logiciel. Un tel algorithme ressemble une commande envoye au systme logiciel pour lui demander de modifier son tat actuel : cest une procdure. La signature dune procdure prcise quelles sont les donnes en entre et, parmi ces donnes, celles qui sont modifies, cestdire celles destines recevoir de nouvelles valeurs ralisant ainsi un nouvel tat du systme. Lorsquune donne en entre voit sa valeur modifie par lalgorithme, celuici retient la valeur initiale et cette valeur initiale peut tre utilisedanslapostconditionlaidedelaconstructionancien. Dfinition Uneprocdure(commande)estunalgorithmedontlecalculmodifieltatdusystmelogiciel. Lasuitedecettesectiontudiedesexemplesmoinstriviaux. Exercicersolu2:Divisioneuclidiennededeuxentiers ENI Editions - All rigths reserved - Jonifar lina - 5-

20

On suppose que la division euclidienne de deux entiers nest pas une opration du rpertoire de notre langage dimplmentation. 1.Donnerlesspcificationsdelalgorithmequicalculelequotiententierdedeuxentierspositifs. 2.Donnerlesspcificationsdelalgorithmequicalculelerestedeladivisionentirededeuxentierspositifs. Solution Letextedelnoncestclair :ondemandelesspcificationsdesalgorithmes,autrementditcequefontcesalgorithmes etnonpascommentilsfontleurscalculs.Danscecas,leproblmeestsimple. Soientaetbdeuxentiers,positifounulpouraquiseraledividende,strictementpositifpourbquiseralediviseur.Le quotiententieretlerestedeladivisioneuclidiennedeaparbsontrespectivementlesentiersqetrtelsque : a = b x q + r avec 0 r < b Lequotientest,pardfinition,luniqueentierqtelque : b x q a < b x (q+1) (quation 1)

Deplus,tantdonnsa,betq,onobtientrpar : r = a - b x q (quation 2)

Onendduitlesspcificationsdemandes. Algorithme8:Calculduquotienteuclidiendedeuxentiers

Algorithme quotient # Le quotient euclidien de a par b. Entre : a, b : ENTIER Rsultat : ENTIER prcondition a0 b>0 postcondition bxRsultata0 postcondition Rsultat=abxquotient(a,b) fin reste Remarquez que ce dernier algorithme utilise le rsultat calcul par le prcdent pour exprimer ce quil fait. Cela ne signifie pas quil utilisequotient pour calculer son propre rsultat. En effet, cette spcification ne dit rien sur la faon dont reste calcule son rsultat. Il dit seulement que son calcul consiste tablir un rsultat gal ce quannoncela postcondition.Encesens,cettespcificationnefaitquedonnerunedfinitiondurestedeladivision. Exercicersolu3:Calculdunemoyennearithmtique Vous tes professeur et vous voulez calculer la moyenne arithmtique des notes obtenues dans votre matire par Alain DUPONT. 1.Quelslmentssontncessairespourcecalcul? 2.Commentspcifiercecalcullaidedeslmentsrecensslaquestionprcdente? Solution La moyenne arithmtique est le rsultat du quotient de la somme des notes par le nombre de notes. Les lments ncessairescecalculsontlenombredenotesetlesnotesproprementdites.Posonsk > 0lenombredenotesetn 1 , n 2 ,...,nk lesnotes. Laspcificationducalculpeutscrirealors: Entre n1,n2,...,nk:REL # Les notes dont on veut la moyenne. k:ENTIER # Rsultat : REL # prcondition # Une note est comprise ( 1 i k) (0 n i i, Le nombre de notes. La moyenne arithmtique des notes. entre 0 et 20. 20)

# Le nombre de notes nest pas nul. k 1 postcondition

La spcification de ce problme met en uvre avantageusement le symbolisme mathmatique dont la prcision et la concisionsontincomparables.Cependant,cettenotationnestpasobligatoireettoutenotation,quidfinitclairementet sansambigutleproblmersoudre,estacceptable.Ainsi,parexemple,lexpressiondelapostconditionpeuttre : postcondition Le quotient par k de la somme des notes n 1 , n 2 , ..., n k

Exercicersolu4:Calculdesintrtsduncomptedpargne MonsieurJeanPaulDURANDpossdeunlivretlaCaissedpargne.Enfindanne,ilsouhaitecalculerluimmelemontant desintrtsrapportsenunanparsoncapital. 1.Quelssontleslmentsncessairescecalcul? 2.Spcifierlecalculdumontantdesintrts. Solution Lemontantdesintrtsannuelsestobtenuenmultipliantlemontantducapitalparletauxdeplacementetendivisant leproduitpar100.Lesdonnesenentresontdonclemontantducapitalplacetletauxdeplacement. Entre c a p i t a l : REL # Montant du capital.


- 7-

22

taux : REL # Taux de placement. Rsultat : REL prcondition capital 0 taux > 0 postcondition Rsultat = capital x taux x 0,01 Lasectionsuivantecommencetudierdesalgorithmescomplets.

- 8-


23

PremiersalgorithmesCette section complte la prcdente en montrant, sur quelques exemples lmentaires, les notations utilises pour direcomment un algorithme effectue son calcul, autrement dit, comment assurer la transition de ltatinitialIltat final F du systme logiciel. On en reste encore, comme dans tout ce chapitre, des ides intuitives, non formalises, maispourtantrigoureuses.Iciaussi,lamthodeestexposepartirdexercicesrsolus. Exercicersolu5:Rapprovisionnementdestock Cetexercicereprendltudedelexemple4commenceaudbutdelasectionPremiersexemples. crirelesinstructionsquirsolventleproblmepos. IlsagitdoncdtudierquellessontlestransitionsquiferontpasserlesystmelogicieldesontatinitialI,danslequel sontconnueslesvaleursdesdonnesdentreduproblme,ltatfinalFdanslequelonsaitsilfautounonlancerun rapprovisionnement.Nousavonsvu,lorsdeltudeprliminairedecetexemple,quelestapesducalculsorganisent selonleplansuivant : q

rcuprerlesdonnesqs,dretv1,v2,...,v12 calculerlamoyennearithmtiquemvdesventesquotidiennesdeceproduit calculerleniveaudedclenchementqd comparerqsqd : q

q

q

q

qsqd=>proposerderapprovisionner qsnerienfaire.

q

Cetalgorithmersoutleproblmeetilestcompletsionsaitcalculerunemoyenne.Pourrussirprsenterlasolution deproblmespluscomplexes,pourlesquelscetteformesimpledcritureenlangagenaturelnestpasadapte,nous allonscrirelasolutiontrouveenutilisantunformalismeunpeuplusrestrictifquelelangagenaturel. Ilsagitdonc,prsent,dedirecommentsonteffectuslescalculsdechaquetapepourprendreladcision. Onobtientlamoyenne mvdesventesquotidiennesendivisantletotaldesventessurlanneparlenombredejours ouvrables.Sionadmet25joursouvrablesparmois,ona:

Leniveaudedclenchementqdestleproduitdecettemoyenneparledlaidrderapprovisionnement :qd = mv x dr

Commelesvi,dretq s sontdesdonnesduproblme,nousdisposonsdetoutcequiestncessairepourorganiserle

calculcomplet.Unepremireversionestdonnecidessousendeuxparties.Lapremirereprendlesspcificationsdu problme. La seconde dtaille les oprations raliser pour obtenir un rsultat qui exprime sil convient ou non de rapprovisionner. Algorithme9.1:Spcificationsduproblmederapprovisionnement

Algorithme dclenchement # Faut-il rapprovisionner ? Entre v1, v2, ..., v12 : ENTIER # Volumes des ventes mensuelles. dr : ENTIER # Dlai de rapprovisionnement. qs : ENTIER # Seuil de dclenchement. Rsultat : BOOLEN prcondition toutes les donnes en entre sont positives ou nulles.


- 1-

24

Postcondition Rsultat = fin dclenchement LasignatureexprimequelecalculproduitunrsultatBOOLEN.Autrementdit,lalgorithmecalculeunrsultatgal soit VRAI, soit FAUX, sans modifier les donnes utilises pour raliser ce calcul. Ces donnes sont des ENTIERsdj prsentsprcdemmentetellesnesontsoumisesaucuneconditionparticulire,sicenestquelalgorithmeattend en entre des entiers non ngatifs. Cette condition est exprime ici en franais, mais elle aurait pu tout aussi simplementutiliserlessymbolesmathmatiquesusuelsdanscecas. Lapostconditionestunpeudlicateetellemritequelquesexplications.Elleestexprimesouslaformedunegalit. gauche,ontrouvelapseudovariableRsultatdontlavaleurestcellerendueparlalgorithmelorsquilsetermine. droitedusignegal,ontrouveuneexpressionboolenne.ElleprendlavaleurVRAIlorsqueq s estinfrieurougalau

membrededroitedelacomparaison.ElleprendlavaleurFAUXsinon.Danstouslescas,cestcettevaleur,soitVRAI, soit FAUX, que doit prendre Rsultat et que vrifie la postcondition. Il faut bien comprendre que le rsultat de lvaluation du membre de droite de lgalit est une valeur dans lensemble {VRAI FAUX} et que cest lgalit de Rsultataveccettevaleurquexprimelapostcondition. Passons la deuxime partie de cette analyse. Il sagit de dire comment passer de ltat dans lequel les donnes dentre vrifient la prcondition ltat qui vrifie la postcondition. Cest lalgorithme suivant qui exprime cette ralisation. Algorithme9.2:Calculdeladcisionderapprovisionner(versionprovisoire)

Algorithme dclenchement Ralisation # Calcul de la moyenne quotidienne des ventes. mv = (v1 + v2 + ... + v12) / 300 # Calcul du niveau de dclenchement. qd Le fichier echanger.php est un lien sur le fichier echanger1.php qui contient la dfinition dune premire version de la procdure : Remarquezque,pourPHP,toutestfonction.Cetteprocdureestdoncdclarelaidedumotfunction. Lexcutionduscriptprincipalquiappellecetteprocdureetlaprocdureecriredonnelesrsultatssuivants : Principal avant change : A = 17 Principal aprs change : A = 17 B = 21 B = 21

; ;

ce qui, manifestement, nest pas ce qui est attendu. Pour comprendre ce qui se passe, ajoutons dans la procdure echangerlesmmesinstructionsdetrace : function echanger($a, $b) { ecrire(changer , $a, $b) ; $temp = $a ; $a = $b ; $b = $temp ; ecrire(changer , $a, $b) ; } Cettefois,lersultatdelexcutionest :

- 4-


31

Principal changer changer Principal

avant avant aprs aprs

change change change change

: : : :

A A A A

= = = =

17 17 21 17

B B B B

= = = =

21 21 17 21

Ainsi,onconstatequelaprocduredchangesacquittecorrectementdesatcheetralisebiencequiatprouv plus haut. Par contre, le script principal ne reporte pas les changements. Pour le script principal, les deux variables gardentlesmmesvaleursetlestransformationsralisesparlaprocdurenontaucuneinfluencesurlesvaleursdes variablesdanslescriptprincipal. Laprocdureechangertravaillesurdescopieslocalesdesparamtres$aet$b.Lesnomsdesvariablesnechangent rienlaffaire.Danslescriptprincipal,lutilisationdelaprocduresefaitparlinstructionechanger($a, $b)parlaquelle ondemandechangerlesvaleursdesvariables$aet$b.Ici,$aet$bsontlesparamtreseffectifsdelappel.Dansla procdure, $a et $b sont des paramtres formels, cestdire des marqueplaces qui indiquent simplement que la procdurereoitenentredeuxparamtres,lepremiertantdsignpar$aetlesecondpar$b.Ilauraittlgitime de les appeler $x et $y ou $premier et $second par exemple. De plus, la rgle essentielle ici est que, partout o apparat $a ou $b, cest une copielocale quutilisera la procdure et non le paramtre effectif. Ainsi, la sortie de la procdure, le contexte du script principal est restaur et $a et $b retrouvent les valeurs quelles avaient dans ce contexte. Poursortirdecettesituation,ilfautunmoyendeforcerlaprocdureutiliserlesvariableseffectivesetnonpasdes copies locales. C et les langages drivs adoptent pour cela une convention syntaxique qui consiste, par exemple, faireprcderdun&chacundesparamtresformelsdelaprocdure.Lasignaturedelaprocduredevientainsi : f u n c t i o n e c h a n g e r (&$a, &$b) ; Aprs cette modification dune copie de la procdure dans un nouveau fichier echanger2.php et la redfinition du lien echanger.phpverscettecopie,onobtientlexcutionduscriptprincipal: Principal changer changer Principal avant avant aprs aprs change change change change : : : : A A A A = = = = 17 17 21 21 B B B B = = = = 21 21 17 17

cequiestexactementcequenousattendons. Cette tude montre que, mme aprs une tude soigne dun problme, il est encore ncessaire de procder ladaptationdelalgorithmeauxparticularitsdeslangagesdeprogrammation.Laconventionmiseenvidencepourle langagePHPneluiestpasparticulire.Toutmodulelogiciel,procdureoufonction,utilisedescopieslocalesdesvaleurs des paramtres effectifs. Cest une convention syntaxique particulire qui contraindra le module utiliser les valeurs desparamtreseffectifsaulieudecopieslocales.Bienentendu,lalgorithmiquenapassesoucierdecesrglesde syntaxe.Lesspcificationssontlpourdfinirprcismentlecontexte,lesconditionsdusageetleseffetsdumoduleet ilnyapaslieudintroduiredesrglesdegrammairesupplmentairespourprciserdavantage. Envisageons,prsent,limplmentationdansunlangageparticulierdelasecondeversiondelalgorithmedchange. Laprconditionimposeauxvaleurschangerdtreduntypesurlequelestdfinieladdition.Pourlasuitedecette tude, supposons que ce type est le type ENTIER et que le langage de programmation est C. En langage C, comme danstoutlangagedeprogrammationdailleurs,ledomainedesvaleursdunentierestcontraintparlareprsentation desnombresenmachine.Ainsi,parexemplesurtelordinateurcourant,celuiutilispourcrirecetexte,unentierest reprsent sur 32 chiffres binaires (bits), cestdire sur 4 octets. Ainsi, sa valeur, lorsquil est positif, est limite INT_MAX=231 1soit2147483647.Toutdpassementdecettelimiteengendreuneerreurdecalculetparfoismme une erreur ds la phase de compilation du programme. Considrons alors notre version de changer. La premire instructiondelaralisationcalculelasommea+betrangelersultatdansa.Supposonsalorsdesvaleurstellesque a > INT_MAX / 2etb > INT_MAX / 2.Leursommeestalorsa+b > INT_MAXetlersultatnepeuttrecalcul.Entoute rigueur,laprconditiondevraitdoncimposerlescontraintesassociessurledomainedesvaleursdeaetb : prcondition aINT_MAX bINT_MAX aINT_MAXb IlnestpasdifficilededmontrerquecetteprconditionassurequelasommeresteinfrieureougaleINT_MAX.Il restecomplterpourimposerlasommederestersuprieureougaleINT_MINdelammefaon. Ces considrations dimplmentation concernentelleslalgorithmique ? Ce livre prtend que non. Lalgorithme restedanslespaceduproblme.LadditionetlasoustractiondesENTIERssontbiendfinies,leursproprits sont connues et il ne semble pas ncessaire de sattarder sur des particularits qui viennent nier ou amender ces proprits.Bienentendu,programmerimposedautrescontraintesquiviennentmodulerlanalysepralable.Ilfaudra bienentenircomptepourprogrammer,maisonseraalorsdanslespacedelasolutionetlescontraintesdedomaine neserontpaslesplusdifficilessatisfaire.Parconsquent,lasuitedecelivrenetiendrapascomptedescontraintes imposesparleslangagesdeprogrammation.Certainesdifficultsserontsignalesparfoislorsquelasolutionnest pastriviale,maisnousenresteronshabituellementdesproblmessimples. ENI Editions - All rigths reserved - Jonifar lina - 5-

32

Les rudiments tudis dans les sections prcdentes sont insuffisants pour tudier des problmes plus complexes. Il nous faut encore prciser quelques rgles fondamentales sur lutilisation des mots du langage qui nous servent reprerlesdonnesetlesrsultats. Chaquedonneoursultatestreprsentparunevariabledontonsupposequelleoccupeunensembledepositions dans la mmoire du calculateur utilis pour coder la solution du problme. Appelons une case lensemble des positionsoccupesparunevariable.Ainsi,lavaleurdeaoccupeunecase,lavaleurplacedanstempenoccupeune autre...LutilisationdelammoiredunemachinedeVONNEUMANNestrgleparlestroisaxiomessuivants : (A1) :onnepeutplacerquuneseuledonnelafoisdansunecase (A2) :onpeututilisertoutmomentlecontenudunecasesansledtruire (A3) :onpeuttoujoursremplacerlecontenudunecaseparunenouvelledonnedummetype. Laxiome(A3)seradornavantunaxiomedela thorie decelivre,maisnestpasunaxiomedetousleslangages de programmation. Ainsi, par exemple pour un langage comme PHP, il est possible dcrire $a = 55 puis, plus tard, $a = Bonjour ce qui fait que lentier 55 a t remplac par une chane de caractres, qui nest trivialement pas du mmetype.Cetaxiomeditaussiquunedonneplacedansunecasenestjamaisdfinitivementprsenteetquilest toujourspossibledelaremplacerparuneautrevaleur. Laxiome(A2)estlaxiomedecopie.Ilditquelacopieducontenudunecaseversuneautrecase,lorsduneaffectation parexemple,nedtruitpaslecontenudelacasesource. Maisquestcequunevariableprcisment ? Dfinition Onappellevariableuneinstanceduntypededonnes. Untypeprciseledomainedesvaleursdelavariable,cestdirelensembledesvaleurspossiblespourcettevariable, et les oprations applicables des donnes de ce type. Ainsi, par exemple, le type ENTIER dfinit les donnes de lensemble des entiers sur lesquels on peut effectuer les oprations usuelles daddition, multiplication... Le type COULEUR dfinit les valeurs possibles des instances de couleurs : ctait rouge, orange et vert. La seule opration actuellementdfiniesurlesdonnesdecetypeestsuccesseur.Dfinirunevariablecest,enalgorithmique,luidonner un nom et dire quel type elle appartient, cestdire de quel type elle est une instance. Cette seule mention suffit pour prciser les valeurs quelle peut prendre et les oprations qui lui sont applicables. On peut toujours dfinir un nouveau type de donnes. Cette dfinition devra clairement prciser les valeurs possibles de ses instances et les oprationsapplicables. Lexercice suivant illustre la cration et lutilisation dun nouveau type de donnes. Il est instructif dans la faon de rutiliserdesalgorithmespourendfinirdautres. Exercicersolu12:Rservoirs Unrservoirestunconteneurdeliquide.Onpeutraliserdiffrentesoprationssurunrservoir,commeleremplir,levider, ajouterduliquidesoncontenu... 1.tablirlalistedesoprationspertinentesapplicablesunrservoir.Distinguerclairementlesfonctionsdesprocdures. 2.crirelesspcificationspuislesdfinitionsdesalgorithmesdechacunedecesoprations. Solution Les oprations pertinentes sur un rservoir, comme dailleurs sur tout objet informatique, se rpartissent en deux familles,commenousavonscommenclevoirprcdemment.q

Les requtes permettent dinterrogerlobjet sur son tat : ce rservoir estil vide ? Estil plein ? Quelle est sa capacit ?... lescommandespermettentdemodifiercettat :remplircerservoir,levider,luiajouterunequantitdonne deliquide...

q

Une requte est implmente par une fonction : elle calcule un rsultat quelle retourne au client du service quelle reprsente. Une commande est ralise par une procdure qui va modifier les valeurs de certaines variables dtat. Dtaillonslesmembresdechaquefamillepourunrservoir. Lesrequtessurunrservoirsont :q

estVidequidterminesiunrservoirestvide

- 6-


33

q

estPleinquidterminesilestplein.

Lescommandessont :q

viderpourramenersacontenance0 remplirpourajustersacontenancesacapacit ajouterunequantitdonnedeliquidepouraugmentersacontenanceactuelle enleverunequantitdonnedeliquide.

q

q

q

Ltatdunrservoirestentirementcaractrispardeuxnombres.Sacapacitdonneenlitreslaquantitdeliquide quilpeutcontenir.Cestunnombredcimalpositif,ventuellementnulpourunrservoirquinepeutriencontenir.Sa contenance donne en litres la quantit actuelle de liquide que contient le rservoir. Cest aussi un nombre dcimal positif, ventuellement nul si le rservoir ne contient rien. Par consquent, un RSERVOIR informatique est une structure de donnes qui rassemble indissociablement ces deux nombres pour en faire un rservoir. Elle est dfinie ainsi : type RSERVOIR structure capacit:REL contenance:REL fin RSERVOIR LorsquenousauronsbesoindedfinirunevariabledetypeRSERVOIR,nouscrirons : # D laration dun variable de type R E R V O I R. c S r : RSERVOIR cequiauralemmeeffetquunedclarationusuellepourunnombreentierouunnombrerel.Ildevientalorspossible dinitialiserlacapacitetlacontenancedurservoirr : r.capacit 0=>Rsultat=+1 Lexpression de la postcondition dans lalgorithme prcdent est droutante au premier abord et il nest pas immdiatement clair quuneconjonctiondestroisclausesexprimecequefaitcetalgorithme.Lajustificationfaitappel aux Mathmatiques et lalgbre de Boole. Les lecteurs qui ne seraient pas intresss par la justification de cette postconditionpeuventpasserdirectementlasuitedeladescriptiondelalgorithme. Lapremireclauseestuneimplication:nRsultat=1.Limplication(a=>b)estdfiniepar(nonaoub).La clause(nRsultat=1)estdoncquivalente(n0ouRsultat=1).Parconsquent,cettepremire clauserendtoujourslersultatVRAI,sauflorsque(n0etRsultat+1).Ainsi,pourles12combinaisonspossiblesdevaleurs surlesignedenetdeRsultat,seuleladisjonctiondestroisclausesexhibesicirendunrsultatFAUX.Autrement dit,lapostconditionprendlavaleurFAUXlorsque : (n0etRsultat+1)


- 3-

49

etelleprendlavaleurVRAIdanstouslesautrescas : (nRsultat=1)et(n=0=>Rsultat=0)et(n>0=>Rsultat=+1) Revenons lalgorithme. Le rsultat sera obtenu en comparant n 0. Lalgorithme consiste donc comparer deux nombres,icinet0.Onobtientunalgorithmeplusgnralencomparantdeuxdonnescomparablesquelconquesnetm. Algorithme5:Spcificationdelacomparaisondedeuxdonnescomparablesversion1.0 Algorithmecomparer #Comparernm. Entre n,m:T>COMPARABLE Rsultat : ENTIER prcondition aucune postcondition nRsultat=1 n=m=>Rsultat=0 n>m=>Rsultat=+1 fin comparer Obtenir le signe dun nombre selon signe1 consistera utiliser comparer avec m = 0. Il est donc possible dcrire compltementlafonctionsigne : Algorithme6:Signedunnombreversion2.0 Algorithmesigne #Calculelesigneden. Entre n:REL Rsultat : ENTIER prcondition aucune ralisation RsultatRsultat=0 n>0=>Rsultat=+1 fin signe Cetteversiondusignedunnombreutiliselalgorithmecompareretilrestelcrire.Unepremireversionestcellede lalgorithmesuivant : Algorithme7:Ralisationdelacomparaisondedeuxdonnescomparablesversion1.0

ralisation si nc alors #abetcbalors changer(a,b)fin si#ab,cresteplacer. sib>calors changer(b,c)fin si#ac,bc. sia>balors changer(a,b)fin si#abc. postcondition abc fin classer3 Insistonsencoresurunpointfondamentalquiestlathsedecelivre.Cestledtaildestatsatteintsaprschaque instruction qui permet de dterminer les actions entreprendre et de sassurer de la correction de lalgorithme. Ce dtailestexplicitpardescommentairesquidcriventlestatspardesprdicatssurlesvariablesquilescapturent. Nousprocderonsautrementdansleschapitressuivants.Lediagrammedelafigurecidessousreprsentecestats etlestransitionsquipermettentdelesparcourir.

- 2-


54

Dans cette version, certains tests sont inutiles pour certaines configurations de valeurs des variables a, b et c. Cependant,ongagnebeaucoupenlisibilitcequelonperdraventuellementenefficacit,plustard,lexcutionde limplmentation. Cest souvent le cas en algorithmique et en programmation : il faut faire des choix qui sont des compromis entre lisibilit, efficacit, cot en ressources... Quoi quil en soit, le premier objectif de lanalyse algorithmiquerestelacorrection.Ilserabientempsdeprogrammerefficacementlorsquunesolutioncorrecteaurat obtenue. Exercicersolu2:Reconnatreuneannebissextile Dfinirunalgorithmequireconnatsiunmillsimeestceluiduneannebissextile. Solution Reconnatre une anne bissextile cest, par exemple, produire le rsultat VRAI si le millsime donn est celui dune anne bissextile, ou FAUX sinon. Il sagitdoncdcrire un prdicat estBissextilequirendVRAIouFAUXselonquele millsime,quilreoitenparamtreformel,estceluiduneannebissextileounon maisilfautprciserdavantage. Ceprdicatreoitenentreunmillsime.Quelestledomainedesvaleursdecenombre ?Cestvidemmentunnombre entier naturel, mais nous savons que le calendrier que nous connaissons date du 16me sicle. Considrons, cependant, que parler dune anne bissextile a un sens depuis lanne 1500 et pour tout millsime jusquen 2100. Avant,celanapasdesens.Aprs,ilpourraityavoirdesperturbationsdanslasuccessiondesannesbissextilesdues larotationdelaTerreautourduSoleil. Onadjvuauchapitreprcdentcommentreconnatreuneannebissextile.Cestuneannedontlemillsimeest divisiblepar4, quelquechoseprs .Leslimitesdesiclenesontpasbissextiles,saufcellesdontlemillsimeest divisiblepar400,comme2000parexemple.Ainsi,1984et2000sontdesannesbissextiles,alorsque1983,2005et 2100nensontpas.Lecalculconsistedoncdterminerdabordsiuneanneestunelimitedesicle.Cestlecassi lesdeuxdernierschiffresdumillsimesontnuls.Onobtientlenombreconstitudesdeuxdernierschiffres,encalculant lerestedeladivisiondumillsimepar100.Ainsi,parexemple,reste(1983,100)=83.Onobtientdonc : si reste(millsime,100)=0 alors millsimeestunefrontiredesicle sinon millsimeestuneannenormale fin si Lorsque millsime est celui dune frontire de sicle, on calcule le nombre form des deux premiers chiffres. Cest le ENI Editions - All rigths reserved - Jonifar lina - 3-

55

quotientdemillsimepar100.Cemillsimeestceluiduneannebissextilelorsquelequotientobtenuestdivisiblepar 4,cestdirelorsquelerestedeladivisiondecenombrepar4estnul.Ainsi : reste(quotient(1900,100),4)=3#=>1900nestpasbissextile. reste(quotient(2000,100),4)=0#=>2000estbissextile. Onobtientdonc : si reste(millsime,100)=0 alors #Millsimeestunefrontiredesicle. #Estceuneannebissextile? Rsultat

Documents

Algorithmique - Raisonner Pour Concevoir