educAlgoManuel
Contents
1. ducAlgo Manuel d utilisation 26 juin 2011 Table des mati res 1 T che effectuer crire un algorithme 2 Comment crire un algorithme 2 1 Avec quoi crit on Avec les boutons criture 2 2 O crit on A la position du curseur 2 3 Affichage des r sultats 24 Commentaire 3 Comment corriger 3 1 Comment d placer le curseur Avec les touches T et L 3 2 Comment modifier variable expression ou condition 3 3 Comment effacer une instruction Clic dans une zone rouge 3 4 R sum des actions disponibles sur l interface 4 Ex cution et Trace 4 1 Ex cution de l algorithme 4 2 Trace de l ex cution 4 5 Aide 6 Comment concevoir un algorithme 6 1 Il n existe pas de proc d g n ral 6 2 Concevoir et analyser un programme avec des assertions 6 3 Exemple algorithme complet 10 10 10 11 12 12 12 1 T che effectuer crire un algorithme Le logiciel ducAlgo propose une liste d exercices dans un menu en haut de la page L utilisateur doit commencer par en choisir un par d faut aucun exercice n est s lectionn Chaque exercice demande d crire un algorithme c est dire un pro gramme qui partir de certaines donn es d entr e permet d obtenir des r sultats de sortie L criture d2. n ral les variables les expressions et les conditions n ont pas tre cr es de toutes pi ces partir de concepts g n raux plus l mentaires Ici pour chaque exercice le logiciel propose seulement un petit nombre de variables expressions et conditions pr d finies permettant de construire un algorithme solution et ventuelle ment plusieurs Cela all ge les probl mes de syntaxe et fournit des indica tions sur des solutions possibles Cela vite aussi de parcourir les 1000 pages d un manuel d un langage pour se demander quelle vont tre les quelques 5 ou 6 instructions qu on va utiliser parmi les centaines qui existent Cependant les structures de contr le de l algorithme sont mettre en place sans indications 2 2 O crit on A la position du curseur Le fait de cliquer sur un bouton d criture provoque l criture d un texte dans la zone de texte D une mani re un peu analogue un traitement de texte cette criture se produit l endroit o est plac le curseur mat rialis par une marque Dans un traitement de texte cette marque est souvent un trait vertical clignotant du type Ce n est pas le cas ici parce que l criture est soumise certaines r gles de syntaxe que le logiciel conna t et qui sont indiqu es dans le curseur pour aider l utilisateur Le curseur est mat rialis par un rectangle jaune contenant une indication sur la nature de ce qui est attendu cet
3. de l in terface des messages d aide apparaissent en haut droite de l cran Il est utile de les lire avec attention lors de la prise en main de l application De plus un clic dans cette zone d aide quand elle contient un point d in terrogation affiche un mode d emploi Si l criture de l algorithme vous pose des probl mes ducAlgo propose selon les exercices soit un bouton qui fournit une solution Tests Pour certains algorithmes il peut arriver que des jeux de valeurs parti culi res pour les donn es en entr es provoquent des situations critiques Pour aider la mise au point de ces algorithmes on trouve parfois dans le menu d aide un item Tests propos s par le syst me Aides Commentaires et Solution 1 Tests propos s par le syst me Solution du syst me Ces tests provoquent une ex cution automatique de l algorithme avec diff rents jeux de donn es critiques Ainsi il est facile de v rifier pour chaque cas que le r sultat obtenu est bien le r sultat attendu 11 6 Comment concevoir un algorithme Ce qui pr c de s est content de d crire les outils pour crire un algo rithme mais ne dit rien sur la fa on de concevoir un algorithme 6 1 Il n existe pas de proc d g n ral D abord il faut bien comprendre qu il n existe pas de m thode m canique et infaillible pour concevoir un algorithme quelconque cette affirm
4. endroit Lorsque le curseur est on attend une instruction ou un contr le ou rien C est un endroit o on peut ins rer une instruction ou un contr le mais 4 on peut aussi ne rien crire et passer la ligne suivante en cliquant sur le curseur qui prend la forme d une fl che E gt lorsque la sourit le survole Le curseur kdi aussi se transformer en s lection et ea les indications suivantes 4 FariableF gt Condition Dans ce Cas on Pr ge un l ment de la nature indiqu e SET est obligatoire et doit tre fourni l aide des boutons de droite correspondants Une fois qu on a crit quelque chose le curseur passe la prochaine position d criture en indiquant ce qu on attend cet endroit Par exemple si on veut crire Poser V X il faut cliquer d abord sur le bouton Affectation puis sur la variable V puis sur l expression X Attention une erreur fr quente il se peut qu une m me lettre comme X apparaisse la fois comme variable et comme expression Quand on crit Poser X 1 il s agit de la variable X alors que dans Poser N X il s agit de l expression X C est la m me lettre mais elle n est pas interpr t e de la m me fa on Dans le premier cas variable X elle d signe un contenant la case m moire qui s appelle X alors que dans le second expression X elle d signe un contenu la valeur qui est contenue dans
5. la variable et X une expression qui d signe une valeur La variable est crite gauche et la valeur droite Le symbole d galit est utilis mais ce n est pas l galit au sens math matique On peut trouver cela regrettable mais c est l usage dans de tr s nombreux langages depuis des dizaines d ann es et il vaut mieux s habituer cette notation Dans le logiciel nous proposons la formulation Poser V X les Contr les indiquent l ordinateur dans quel ordre et quelles condi tions il doit effectuer les instructions on dit aussi souvent instructions de contr le ou structures de contr le 3 Par exemple pour calculer V la valeur absolue de N Si N gt O faire Poser V N sinon faire Poser V N Le logiciel crit les instructions avec des retours la ligne et des d calages on dit des indentations pour mettre en vidence la structure Le mot faire rappelle qu il s agit bien d actions qui modifient l tat physique d une machine le contenu de la m moire V change les Expressions permettent de calculer et de d signer des valeurs Par exemple 2N 1 les Conditions permettent d exprimer des propri t s concernant les va leurs et de savoir si ces propri t s sont vraies ou fausses l instant o on les value Par exemple N gt 0 est une condition vraie si N est strictement positif et fausse sinon Contrairement un langage de programmation g
6. Il est quasiment in vitable d avoir modifier ce qu on a crit pour corriger ou compl ter l algorithme 3 1 Comment d placer le curseur Avec les touches et T du clavier La touche d place le curseur vers le bas la ligne suivante Quand le curseur atteint la fin du texte de l algorithme il continue en revenant au d but de l algorithme La touche T gt d place le curseur vers le haut la ligne pr c dente Quand le curseur atteint le d but du texte de l algorithme il continue en revenant la fin de l algorithme On peut aussi faire descendre le curseur en cliquant dessus Remarque Parfois sur certains navigateurs les touches fl ches du clavier ne fonctionnent pas ou sur certains claviers d ordinateurs elles ne sont pas disponibles Une alternative consiste utiliser la touche A pour monter et la touche Z pour descendre 3 2 Comment modifier une variable une expression ou une condition Il suffit de la s lectionner dans le texte de l algorithme puis de cliquer sur une autre variable expression ou condition parmi les boutons d criture 3 3 Comment effacer une instruction ou un contr le Clic dans une zone encadr e en rouge Lorsque la souris survole les mots cl s d une instruction celle ci est en cadr e de rouge On peut ainsi visualiser facilement les instructions simples mais aussi l imbrications ventuelles des listes d instructions
7. ation est m me un th or me de logique formelle La conception d un algorithme est une activit de construction progressive souvent par essais et erreurs Les tapes de l algorithme ne sont pas forc ment con ues dans l ordre o elles sont finalement crites Il ne faut pas rester paralys par cette situation Il faut essayer quelque chose observer ventuellement la trace pour comprendre ce qui se passe compl ter rectifier effacer recommencer Bien s r il ne faut pas faire tout fait n importe quoi et l exp rience permet petit petit d acqu rir certains r flexes et de reconna tre certains cas classiques mais encore une fois ce serait une id e fausse de croire qu on peut concevoir un algorithme du d but la fin en pr voyant toutes les tapes correctes dans le bon ordre D autre part il existe souvent plusieurs algorithmes possibles pour r soudre un exercice donn Le logiciel permet d en crire certains par le choix des variables et des expressions qu il propose mais pas forc ment tous Quand vous pensez ne pas pouvoir crire l algorithme que vous imaginez essayez en un autre Il y a toujours au moins une solution 6 2 Concevoir et analyser un programme avec des assertions La m thode de base pour r fl chir un algorithme est celle dite des assertions Elle consiste se poser la question suivante pour chaque instruction crite dans le texte quand le progra
8. bles lire dans la partie Entr e le dialogue de lecture affiche un rappel des valeurs des variables lues pr c demment Lorsque les calculs sont termin s une zone de r sultats s ouvre pour mon trer ce qui a t lu et ce qui a t affich par l algorithme de l utilisateur Puis la solution correcte attendue pour les donn es qui ont t fournies est ensuite affich e 4 2 Trace de l ex cution Si le r sultat obtenu par l utilisateur est diff rent de celui attendu il est alors possible pour obtenir le d tail des calculs effectu s chaque tape par l algorithme de cliquer sur l un des deux boutons de trace fon rer les valeurs des variables Le premier bouton affiche une description du d roulement de l algorithme sous forme d un tableau dont les colonnes d crivent pour chaque instruction le Calcul effectuer le R sultat de ce calcul l Action effectu e pour modifier l tat des variables de l algorithme Le second bouton affiche un tableau qui montre les valeurs des variables pendant le d roulement de l algorithme sur chaque ligne figure l instruction ex cut e suivie des valeurs de chaque variable juste apr s son ex cution Ces tableaux permettent d analyser le fonctionnement de l algorithme et de v rifier s il correspond bien ce qui est attendu 10 5 Aide Quand l utilisateur survole avec la souris des diff rents l ments
9. dans les contr les Lorsque l utilisateur clique une zone encadr e en rouge un dialogue est ouvert qui demande l utilisateur de confirmer s il a vraiment l intention de supprimer l instruction affich e comme dans l exemple ci dessous Entr e tant que K lt N faire Poser K KkK 1 Poser 5 5 K Afficher 5 Si la suppression est confirm e l instruction est effac e et le curseur se place l endroit o tait l instruction 3 4 R sum des actions disponibles sur l interface Les boutons d criture ins rent les l ments correspondant la position du curseur selon les r gles d criture De nombreuses autres actions de la souris sont possibles dans la zone d dition de l algorithme D placements du curseur On peut d placer le curseur avec les touches du clavier T ou A pour faire monter le curseur et ou Z pour faire descendre le curseur On peut cliquer sur une fin de ligne pour provoquer le d placement du curseur la ligne suivante Poser K kK 1 Poser K K E Poser EKE K 1 Poser 5 5 K Poser S S K L On peut cliquer sur le curseur pour le faire descendre la ligne suivante Poser K KkK 1 Poser K kK 1 Poser K kK 1 h CA Poser S S K Poser 5 5 K Poser 5 5 K E S lections Effacement On peut s lectionner variables expressions ou conditions pour effectuer ventuellement ensuite une modification avec les bo
10. inale de S qui sera affich e sera bien 1 N Voici nouveau l algorithme complet avec les assertions utilis es en bleu Soit un entier N gt 0 N est un entier gt QO Poser K 1 Poser S 1 S 1 K et K est inf rieur ou gal N Tant que K lt N faire S 1 K et ESN Poser K K 1 Poser S S K S 1 K et K est inf rieur ou gal N de plus K a augment strictement Apr s la boucle S 1 KetK N doncS 1 N Afficher S Le raisonnement global est un raisonnement par r currence L initialisation se fait avant la boucle et la boucle assure l h r dit 14
11. la case m moire de nom X Contrairement au langage math matique le symbole employ ici n est pas sym trique C est regrettable mais c est un usage tellement r pandu en informatique qu il vaut mieux s y habituer Il s agit d un autre langage avec ses conventions propres 2 3 Affichage des r sultats Le bouton Affichage permet d ins rer dans l algorithme une instruc tion qui affiche la valeur de l expression qui suit Pour permettre une pr sentation plus lisible des r sultats la valeur de l expression peut tre pr c d e d un texte facultatif Afficher 5 Par d faut il n y a pas de texte mais simplement un deux points Un clic sur le gt ouvre un dialogue qui permet ventuellement de mo difier le texte qui pr c de l expression Par exemple Afficher Somme En cas d erreur on peut nouveau cliquer sur le texte pour le modifier 2 4 Commentaire Le bouton Commentaire gt permet d ins rer dans l algorithme un com mentaire c est dire une instruction qui ne fait rien On clic sur le bouton Commentaire ouvre un dialogue de saisie de texte qui contient par d faut le commentaire suivant Rien On peut ensuite modifier le texte du commentaire avec un clic sur le texte affich pour ouvrir nouveau le dialogue qui permet de modifier le texte du commentaire Par exemple f Bla Bla 3 Comment corriger
12. ls sont les outils disponibles ici et ce qu ils permettent Remarque La version la plus r cente de ducAlgo propose dans le panneau crire des expressions suppl mentaires qui permettent de r soudre le probl me par la d finition d algorithmes diff rents On ne d crit dans ce document qu une seule solution et on laisse l utilisateur d couvrir les autres 2 Comment crire un algorithme 2 1 Avec quoi crit on Avec les boutons d criture Le logiciel fonctionne un peu comme un traitement de textes mais il n utilise pas le clavier de l ordinateur Pour crire quelque chose on doit cliquer sur un des boutons d criture affich s l cran dans le cadre libell crire qui sont class s par cat gories Instructions Contr les Variables Expressions Conditions Affectation Affichage Commentaire s o opo 1 EO EE Ces cat gories correspondent des concepts d algorithmique les Variables contiennent des valeurs et leur contenu peut tre chang au cours du temps Ce sont des m moires de travail les Instructions disent l ordinateur quelles actions il doit effectuer Par exemple une Affectation consiste changer la valeur d une va riable La formulation en fran ais serait affecter une valeur une variable gt ou mettre une valeur dans une variable Les formulations usuelles dans les langages informatiques ressemblent V X o V est le nom de
13. mme s ex cutera et commencera ex cuter cette instruction quelles propri t s poss deront les variables ce moment l ce sont les pr assertions De m me quand le programme terminera d ex cuter cette instruction les propri t s sont les post assertions On peut galement consid rer des assertions d volution qui indiquent comment voluent les variables entre le d but d une instruction et la fin d une instruction par exemple telle variable a une valeur qui augmente 2 Exemple affectation Poser K K 1 Si une pr assertion est K est un entier avec K lt N alors une post assertion est K est un entier avec lt N Une assertion d volution est La valeur finale de K est strictement sup rieure sa valeur initiale Exemple test Si N gt O faire Poser V N 1 sinon faire Poser V 0 Si une pr assertion est N contient un nombre entier relatif alors une post assertion est V contient un nombre entier naturel gt ce qu on peut prouver avec un raisonnement par cas simple Si une pr assertion est N contient un entier naturel alors une post assertion est V contient un entier naturel inf rieur ou gal N Exemple assertion invariante Poser K K 1 Poser S S K Si une pr assertion est S 1 K alors apr s les deux ins tructions une post assertion est S 1 K gt c est dire la m me assertion q
14. oit s effectuer uniquement partir des outils propos s l cran en respectant une certaine syntaxe Exemple Par exemple choisissons l exercice dont le titre est Somme des N premiers entiers Ce choix s effectue dans le menu des exercices L nonc appara t Soit un nombre entier N gt 1 Calculer et afficher S la somme des nombres entiers de 1 N S 1 2 N La premi re difficult est de bien comprendre cet nonc Pour cela il est recommand d imaginer d abord des exemples simples Lorsque N vaut 3 par exemple les N premiers nombres entiers non nuls sont 1 2 et 3 et leur somme S vaut 6 car c est le r sultat de l op ration 1 2 3 La formule g n rale de S est en fait S 1 2 N Le plus pra tique serait bien s r de pouvoir crire cette formule directement et ce serait termin Mais les outils propos s ici ne le permettent pas parce que avec les contraintes de l informatique il est difficile d obtenir la g n ralit la sou plesse et l abstraction du langage math matique D autre part il s agit d un environnement de d couverte et d initiation qui se concentre sur les notions de base de l algorithmique Dans ce cas des connaissances math matiques pourraient tre utiles NxX N 1 On peut d montrer en effet que S Mais les expressions offertes par le logiciel pour cet algorithme ne permettent pas d crire cela Nous allons voir dans la suite que
15. ui est donc invariante Cela ne veut pas dire que l tat n a pas volu cela veut dire que la rela tion entre S et K est la m me K et S ont augment assertion d volution mais on a toujours S 1 K Si K vaut 2 au d but et S 1 2 3 alors la fin K 3 et S 1 2 3 0 Cela est analogue l h r dit dans un raisonnement par r currence Soit u une suite v rifiant Un Un n 1 alors on peut d montrer que la propri t un 1 n est h r ditaire Exemple boucle Tant que K lt N faire Poser K K 1 Poser S S K 15 Si une pr assertion est K et N sont deux nombres entiers avec K lt N gt alors une post assertion est K N En effet K augmente strictement chaque tour de boucle cause de l instruction Poser K K 1 assertion d volution et comme au d part on avait K lt N K se rapproche de N chaque tour de boucle On sait qu avec des nombres entiers cela ne peut pas continuer ind finiment et il arrivera un moment o K deviendra gal N Alors la condition de continuation K lt N sera fausse et la boucle s arr tera En sortant de la boucle on aura donc K N 6 3 Exemple algorithme complet Soit un entier N gt O Poser K 1 Poser S 1 Tant que K lt N faire Poser K K Poser 5 S K Afficher S En combinant les diff rents raisonnements sur les assertions vus pr c demment on peut d montrer que la valeur f
16. utons d criture Poser 5 5 ut z Poser 5 SX i On peut cliquer sur un commentaire une instruction ou un contr le en cadr en rouge pour ventuellement l effacer apr s confirmation Tant que K lt N faire Tant que K lt N faire k K 1 Poser K K 1 S Kk Poser 5 5 K Poser K Poser 5 On peut aussi cliquer sur le symbole situ la suite du menu de s lection d exercice pour effacer toute la partie Traitement de l algorithme La touche d effacement du clavier peut aussi tre utilis e Modifications des textes On peut modifier le message de l tiquette d une instruction d affichage avec un clic sur le ou sur l tiquette Afficher S Afficher S Vous pouvez modifier le texte de cette instruction I Annuler Afficher Somme On peut modifier le texte d un commentaire avec un clic sur le texte CRign Rien Vous pouvez modifier le texte de ce commentaire Bla Bla Annuler 4 Ex cution et Trace 4 1 Ex cution de l algorithme Une fois l algorithme r dig on peut cliquer sur le bouton Ex cuter Pour chaque instruction de lecture ex cut e un dialogue s ouvre pour demander l utilisateur de taper une valeur Cette valeur doit tre coh rente avec ce qui est attendu pour la variable correspondante et qui est sp cifi dans l nonc et dans l instruction de lecture elle m me S il y a plusieurs varia
Download Pdf Manuals
Related Search
educAlgoManuel