25-12-2008, 09:23 PM
  #1
achraf.mouni



   achraf.mouni
 
: 08-09-2008
:
: 2,439
achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni   achraf.mouni
04




:

Un algorithme, cest une suite dinstructions, qui une fois excute correctement, conduit un rsultat donn


Partie 1
Les Variables
Nattribuez jamais la malveillance ce qui sexplique trs bien par lincomptence. - Napolon Bonaparte

A lorigine de toute erreur attribue lordinateur, vous trouverez au moins deux erreurs humaines. Dont celle consistant attribuer lerreur lordinateur. - Anonyme



1. A quoi servent les variables ?
Dans un programme informatique, on va avoir en permanence besoin de stocker provisoirement des valeurs. Il peut sagir de donnes issues du disque dur, fournies par lutilisateur (frappes au clavier), ou que sais-je encore. Il peut aussi sagir de rsultats obtenus par le programme, intermdiaires ou dfinitifs. Ces donnes peuvent tre de plusieurs types (on en reparlera) : elles peuvent tre des nombres, du texte, etc. Toujours est-il que ds que lon a besoin de stocker une information au cours dun programme, on utilise une variable.
Pour employer une image, une variable est une bote, que le programme (lordinateur) va reprer par une tiquette. Pour avoir accs au contenu de la bote, il suffit de la dsigner par son tiquette.
En ralit, dans la mmoire vive de lordinateur, il ny a bien sr pas une vraie bote, et pas davantage de vraie tiquette colle dessus (javais bien prvenu que la bote et ltiquette, ctait une image). Dans lordinateur, physiquement, il y a un emplacement de mmoire, repr par une adresse binaire. Si on programmait dans un langage directement comprhensible par la machine, on devrait se fader de dsigner nos donnes par de superbes 10011001 et autres 01001001 (enchant !). Mauvaise nouvelle : de tels langages existent ! Ils portent le doux nom dassembleur. Bonne nouvelle : ce ne sont pas les seuls langages disponibles.
Les langages informatiques plus volus (ce sont ceux que presque tout le monde emploie) se chargent prcisment, entre autres rles, dpargner au programmeur la gestion fastidieuse des emplacements mmoire et de leurs adresses. Et, comme vous commencez le comprendre, il est beaucoup plus facile demployer les tiquettes de son choix, que de devoir manier des adresses binaires.

Retour Haut de Page
2. Dclaration des variables
La premire chose faire avant de pouvoir utiliser une variable est de crer la bote et de lui coller une tiquette. Ceci se fait tout au dbut de lalgorithme, avant mme les instructions proprement dites. Cest ce quon appelle la dclaration des variables. Cest un genre de dclaration certes moins romantique quune dclaration damour, mais dun autre ct moins dsagrable quune dclaration dimpts.
Le nom de la variable (ltiquette de la bote) obit des impratifs changeant selon les langages. Toutefois, une rgle absolue est quun nom de variable peut comporter des lettres et des chiffres, mais quil exclut la plupart des signes de ponctuation, en particulier les espaces. Un nom de variable correct commence galement imprativement par une lettre. Quant au nombre maximal de signes pour un nom de variable, il dpend du langage utilis.
En pseudo-code algorithmique, on est bien sr libre du nombre de signes pour un nom de variable, mme si pour des raisons purement pratiques, et au grand dsespoir de Stphane Bern, on vite gnralement les noms rallonge.
Lorsquon dclare une variable, il ne suffit pas de crer une bote (rserver un emplacement mmoire) ; encore doit-on prciser ce que lon voudra mettre dedans, car de cela dpendent la taille de la bote (de lemplacement mmoire) et le type de codage utilis.

2.1 Types numriques classiques
Commenons par le cas trs frquent, celui dune variable destine recevoir des nombres.
Si lon rserve un octet pour coder un nombre, je rappelle pour ceux qui dormaient en lisant le chapitre prcdent quon ne pourra coder que 28 = 256 valeurs diffrentes. Cela peut signifier par exemple les nombres entiers de 1 256, ou de 0 255, ou de 127 +128 Si lon rserve deux octets, on a droit 65 536 valeurs ; avec trois octets, 16 777 216, etc. Et l se pose un autre problme : ce codage doit-il reprsenter des nombres dcimaux ? des nombres ngatifs ?
Bref, le type de codage (autrement dit, le type de variable) choisi pour un nombre va dterminer :
les valeurs maximales et minimales des nombres pouvant tre stocks dans la variable
la prcision de ces nombres (dans le cas de nombres dcimaux).
Tous les langages, quels quils soient offrent un bouquet de types numriques, dont le dtail est susceptible de varier lgrement dun langage lautre. Grosso modo, on retrouve cependant les types suivants :

Type Numrique Plage
Byte (octet) 0 255
Entier simple -32 768 32 767
Entier long -2 147 483 648 2 147 483 647
Rel simple -3,40x1038 -1,40x1045 pour les valeurs ngatives
1,40x10-45 3,40x1038 pour les valeurs positives
Rel double 1,79x10308 -4,94x10-324 pour les valeurs ngatives
4,94x10-324 1,79x10308 pour les valeurs positives

Pourquoi ne pas dclarer toutes les variables numriques en rel double, histoire de btonner et dtre certain quil ny aura pas de problme ? En vertu du principe de lconomie de moyens. Un bon algorithme ne se contente pas de marcher ; il marche en vitant de gaspiller les ressources de la machine. Sur certains programmes de grande taille, labus de variables surdimensionnes peut entraner des ralentissements notables lexcution, voire un plantage pur et simple de lordinateur. Alors, autant prendre ds le dbut de bonnes habitudes dhygine.
En algorithmique, on ne se tracassera pas trop avec les sous-types de variables numriques (sachant qu'on aura toujours assez de soucis comme a, allez). On se contentera donc de prciser qu'il s'agit d'un nombre, en gardant en tte que dans un vrai langage, il faudra tre plus prcis.
En pseudo-code, une dclaration de variables aura ainsi cette tte :
Variable g en Numrique
ou encore
Variables PrixHT, TauxTVA, PrixTTC en Numrique
2.2 Autres types numriques
Certains langages autorisent dautres types numriques, notamment :
le type montaire (avec strictement deux chiffres aprs la virgule)
le type date (jour/mois/anne).
Nous nemploierons pas ces types dans ce cours ; mais je les signale, car vous ne manquerez pas de les rencontrer en programmation proprement dite.

2.3 Type alphanumrique
Fort heureusement, les botes que sont les variables peuvent contenir bien dautres informations que des nombres. Sans cela, on serait un peu embt ds que lon devrait stocker un nom de famille, par exemple.
On dispose donc galement du type alphanumrique (galement appel type caractre, type chane ou en anglais, le type string mais ne fantasmez pas trop vite, les string, cest loin dtre aussi excitant que le nom le suggre. Une tudiante qui se reconnatra si elle lit ces lignes a d'ailleurs mis le doigt - si j'ose m'exprimer ainsi - sur le fait qu'il en va de mme en ce qui concerne les bytes).
Dans une variable de ce type, on stocke des caractres, quil sagisse de lettres, de signes de ponctuation, despaces, ou mme de chiffres. Le nombre maximal de caractres pouvant tre stocks dans une seule variable string dpend du langage utilis.
Un groupe de caractres (y compris un groupe de un, ou de zro caractres), quil soit ou non stock dans une variable, dailleurs, est donc souvent appel chane de caractres.
En pseudo-code, une chane de caractres est toujours note entre guillemets
Pourquoi diable ? Pour viter deux sources principales de possibles confusions :
la confusion entre des nombres et des suites de chiffres. Par exemple, 423 peut reprsenter le nombre 423 (quatre cent vingt-trois), ou la suite de caractres 4, 2, et 3. Et ce nest pas du tout la mme chose ! Avec le premier, on peut faire des calculs, avec le second, point du tout. Ds lors, les guillemets permettent dviter toute ambigut : sil ny en a pas, 423 est quatre cent vingt trois. Sil y en a, "423" reprsente la suite des chiffres 4, 2, 3.
Mais ce n'est pas le pire. L'autre confusion, bien plus grave - et bien plus frquente consiste se mlanger les pinceaux entre le nom d'une variable et son contenu. Pour parler simplement, cela consiste confondre l'tiquette d'une bote et ce qu'il y a l'intrieur On reviendra sur ce point crucial dans quelques instants.

2.4 Type boolen
Le dernier type de variables est le type boolen : on y stocke uniquement les valeurs logiques VRAI et FAUX.
On peut reprsenter ces notions abstraites de VRAI et de FAUX par tout ce qu'on veut : de l'anglais (TRUE et FALSE) ou des nombres (0 et 1). Peu importe. Ce qui compte, c'est de comprendre que le type boolen est trs conomique en termes de place mmoire occupe, puisque pour stocker une telle information binaire, un seul bit suffit.
Le type boolen est trs souvent nglig par les programmeurs, tort.

Il est vrai qu'il n'est pas proprement parler indispensable, et qu'on pourrait crire peu prs nimporte quel programme en l'ignorant compltement. Pourtant, si le type boolen est mis disposition des programmeurs dans tous les langages, ce n'est pas pour rien. Le recours aux variables boolennes s'avre trs souvent un puissant instrument de lisibilit des algorithmes : il peut faciliter la vie de celui qui crit l'algorithme, comme de celui qui le relit pour le corriger.

Alors, maintenant, c'est certain, en algorithmique, il y a une question de style : c'est exactement comme dans le langage courant, il y a plusieurs manires de s'exprimer pour dire sur le fond la mme chose. Nous verrons plus loin diffrents exemples de variations stylistiques autour d'une mme solution. En attendant, vous tes prvenus : l'auteur de ce cours est un adepte fervent (mais pas irraisonn) de l'utilisation des variables boolennes.

Retour Haut de Page
3. Linstruction daffectation
3.1 Syntaxe et signification
Ouf, aprs tout ce baratin prliminaire, on aborde enfin nos premires vritables manipulations dalgorithmique. Pas trop tt, certes, mais pas moyen de faire autrement !
En fait, la variable (la bote) n'est pas un outil bien sorcier manipuler. A la diffrence du couteau suisse ou du superbe robot mnager vendu sur Tl Boutique Achat, on ne peut pas faire trente-six mille choses avec une variable, mais seulement une et une seule.
Cette seule chose quon puisse faire avec une variable, cest laffecter, cest--dire lui attribuer une valeur. Pour poursuivre la superbe mtaphore file dj employe, on peut remplir la bote.
En pseudo-code, l'instruction d'affectation se note avec le signe ←
Ainsi :
Toto ← 24
Attribue la valeur 24 la variable Toto.
Ceci, soit dit en passant, sous-entend imprativement que Toto soit une variable de type numrique. Si Toto a t dfini dans un autre type, il faut bien comprendre que cette instruction provoquera une erreur. Cest un peu comme si, en donnant un ordre quelquun, on accolait un verbe et un complment incompatibles, du genre Epluchez la casserole . Mme dote de la meilleure volont du monde, la mnagre lisant cette phrase ne pourrait quinterrompre dubitativement sa tche. Alors, un ordinateur, vous pensez bien
On peut en revanche sans aucun problme attribuer une variable la valeur dune autre variable, telle quelle ou modifie. Par exemple :
Tutu ← Toto
Signifie que la valeur de Tutu est maintenant celle de Toto.
Notez bien que cette instruction na en rien modifi la valeur de Toto : une instruction daffectation ne modifie que ce qui est situ gauche de la flche.
Tutu ← Toto + 4
Si Toto contenait 12, Tutu vaut maintenant 16. De mme que prcdemment, Toto vaut toujours 12.
Tutu ← Tutu + 1
Si Tutu valait 6, il vaut maintenant 7. La valeur de Tutu est modifie, puisque Tutu est la variable situe gauche de la flche.
Pour revenir prsent sur le rle des guillemets dans les chanes de caractres et sur la confusion numro 2 signale plus haut, comparons maintenant deux algorithmes suivants :
Exemple n1
Dbut
Riri ← "Loulou"
Fifi ← "Riri"
Fin

Exemple n2
Dbut
Riri ← "Loulou"
Fifi ← Riri
Fin
La seule diffrence entre les deux algorithmes consiste dans la prsence ou dans labsence des guillemets lors de la seconde affectation. Et l'on voit que cela change tout !
Dans l'exemple n1, ce que l'on affecte la variable Fifi, c'est la suite de caractres R i r - i. Et la fin de lalgorithme, le contenu de la variable Fifi est donc Riri .
Dans l'exemple n2, en revanche, Riri tant dpourvu de guillemets, n'est pas considr comme une suite de caractres, mais comme un nom de variable. Le sens de la ligne devient donc : affecte la variable Fifi le contenu de la variable Riri . A la fin de lalgorithme n2, la valeur de la variable Fifi est donc Loulou . Ici, loubli des guillemets conduit certes un rsultat, mais un rsultat diffrent.
A noter, car cest un cas trs frquent, que gnralement, lorsquon oublie les guillemets lors dune affectation de chane, ce qui se trouve droite du signe daffectation ne correspond aucune variable prcdemment dclare et affecte. Dans ce cas, loubli des guillemets se solde immdiatement par une erreur dexcution.
Ceci est une simple illustration. Mais elle rsume lensemble des problmes qui surviennent lorsquon oublie la rgle des guillemets aux chanes de caractres.

3.2 Ordre des instructions
Il va de soi que lordre dans lequel les instructions sont crites va jouer un rle essentiel dans le rsultat final. Considrons les deux algorithmes suivants :
Exemple 1
Variable A en Numrique
Dbut
A ← 34
A ← 12
Fin

Exemple 2
Variable A en Numrique
Dbut
A ← 12
A ← 34
Fin
Il est clair que dans le premier cas la valeur finale de A est 12, dans lautre elle est 34 .
Il est tout aussi clair que ceci ne doit pas nous tonner. Lorsquon indique le chemin quelquun, dire prenez tout droit sur 1km, puis droite nenvoie pas les gens au mme endroit que si lon dit prenez droite puis tout droit pendant 1 km .
Enfin, il est galement clair que si lon met de ct leur vertu pdagogique, les deux algorithmes ci-dessus sont parfaitement idiots ; tout le moins ils contiennent une incohrence. Il ny a aucun intrt affecter une variable pour laffecter diffremment juste aprs. En loccurrence, on aurait tout aussi bien atteint le mme rsultat en crivant simplement :
Exemple 1
Variable A en Numrique
Dbut
A ← 12
Fin

Exemple 2
Variable A en Numrique
Dbut
A ← 34
Fin
Tous les lments sont maintenant en votre possession pour que ce soit vous de jouer !
Exercice 1.1
Exercice 1.2
Exercice 1.3
Exercice 1.4
Exercice 1.5
Exercice 1.6
Exercice 1.7

Retour Haut de Page
4. Expressions et oprateurs
Si on fait le point, on saperoit que dans une instruction daffectation, on trouve :
gauche de la flche, un nom de variable, et uniquement cela. En ce monde empli de doutes quest celui de lalgorithmique, cest une des rares rgles dor qui marche tous les coups : si on voit gauche dune flche daffectation autre chose quun nom de variable, on peut tre certain 100% quil sagit dune erreur.
droite de la flche, ce quon appelle une expression. Voil encore un mot qui est trompeur ; en effet, ce mot existe dans le langage courant, o il revt bien des significations. Mais en informatique, le terme dexpression ne dsigne quune seule chose, et qui plus est une chose trs prcise :
Une expression est un ensemble de valeurs, relies par des oprateurs, et quivalent une seule valeur
Cette dfinition vous parat peut-tre obscure. Mais rflchissez-y quelques minutes, et vous verrez quelle recouvre quelque chose dassez simple sur le fond. Par exemple, voyons quelques expressions de type numrique. Ainsi :
7
5+4
123-45+844
Toto-12+5-Riri
sont toutes des expressions valides, pour peu que Toto et Riri soient bien des nombres. Car dans le cas contraire, la quatrime expression na pas de sens. En loccurrence, les oprateurs que jai employs sont laddition (+) et la soustraction (-).
Revenons pour le moment sur laffectation. Une condition supplmentaire (en plus des deux prcdentes) de validit dune instruction daffectation est que :
lexpression situe droite de la flche soit du mme type que la variable situe gauche. Cest trs logique : on ne peut pas ranger convenablement des outils dans un sac provision, ni des lgumes dans une trousse outils sauf provoquer un rsultat catastrophique.
Si lun des trois points numrs ci-dessus nest pas respect, la machine sera incapable dexcuter laffectation, et dclenchera une erreur (est-il besoin de dire que si aucun de ces points nest respect, il y aura aussi erreur !)
On va maintenant dtailler ce que lon entend par le terme d oprateur.
Un oprateur est un signe qui relie deux valeurs, pour produire un rsultat.
Les oprateurs possibles dpendent du type des valeurs qui sont en jeu. Allons-y, faisons le tour, cest un peu fastidieux, mais comme dit le sage au petit scarabe, quand cest fait, cest plus faire.

4.1 Oprateurs numriques :
Ce sont les quatre oprations arithmtiques tout ce quil y a de classique.
+ : addition
- : soustraction
* : multiplication
/ : division
Mentionnons galement le ^ qui signifie puissance . 45 au carr scrira donc 45 ^ 2.
Enfin, on a le droit dutiliser les parenthses, avec les mmes rgles quen mathmatiques. La multiplication et la division ont naturellement priorit sur laddition et la soustraction. Les parenthses ne sont ainsi utiles que pour modifier cette priorit naturelle.
Cela signifie quen informatique, 12 * 3 + 5 et (12 * 3) + 5 valent strictement la mme chose, savoir 41. Pourquoi ds lors se fatiguer mettre des parenthses inutiles ?
En revanche, 12 * (3 + 5) vaut 12 * 8 soit 96. Rien de difficile l-dedans, que du normal.

4.2 Oprateur alphanumrique : &
Cet oprateur permet de concatner, autrement dit dagglomrer, deux chanes de caractres. Par exemple :
Variables A, B, C en Caractre
Dbut
A ← "Gloubi"
B ← "Boulga"
C ← A & B
Fin
La valeur de C la fin de lalgorithme est "GloubiBoulga"

4.3 Oprateurs logiques (ou boolens) :
Il sagit du ET, du OU, du NON et du mystrieux (mais rarissime XOR). Nous les laisserons de ct provisoirement, soyez-en srs.
Exercice 1.8
Exercice 1.9

Retour Haut de Page
5. Deux remarques pour terminer
Maintenant que nous sommes familiers des variables et que nous les manipulons les yeux ferms (mais les neurones en veil, toutefois), jattire votre attention sur la trompeuse similitude de vocabulaire entre les mathmatiques et linformatique. En mathmatiques, une variable est gnralement une inconnue, qui recouvre un nombre non prcis de valeurs. Lorsque jcris :
y = 3 x + 2
les variables x et y satisfaisant lquation existent en nombre infini (graphiquement, lensemble des solutions cette quation dessine une droite). Lorsque jcris :
ax + bx + c = 0
la variable x dsigne les solutions cette quation, cest--dire zro, une ou deux valeurs la fois
En informatique, une variable possde un moment donn une valeur et une seule. A la rigueur, elle peut ne pas avoir de valeur du tout (une fois quelle a t dclare, et tant quon ne la pas affecte. A signaler que dans certains langages, les variables non encore affectes sont considres comme valant automatiquement zro). Mais ce qui est important, cest que cette valeur justement, ne varie pas proprement parler. Du moins ne varie-t-elle que lorsquelle est lobjet dune instruction daffectation.
La deuxime remarque concerne le signe de laffectation. En algorithmique, comme on la vu, cest le signe ←. Mais en pratique, la quasi totalit des langages emploient le signe gal. Et l, pour les dbutants, la confusion avec les maths est galement facile. En maths, A = B et B = A sont deux propositions strictement quivalentes. En informatique, absolument pas, puisque cela revient crire A ← B et B ← A, deux choses bien diffrentes. De mme, A = A + 1, qui en mathmatiques, constitue une quation sans solution, reprsente en programmation une action tout fait licite (et de surcrot extrmement courante). Donc, attention ! ! ! La meilleure des vaccinations contre cette confusion consiste bien employer le signe ← en pseudo-code, signe qui a le mrite de ne pas laisser place lambigut. Une fois acquis les bons rflexes avec ce signe, vous naurez plus aucune difficult passer au = des langages de programmation.


:

http://www.grappa.univ-lille3.fr/polys/reseaux-2004/reseaux023.html

http://www-verimag.imag.fr/~perin/enseignement/L3/LSF/td/td4/algorithme-de-Davis-Putnam.html

http://www.techno-science.net/?onglet=ouvrages&ID=2100056433

http://perso.citi.insa-lyon.fr/afraboul/imsi/algo-imsi-tdc.pdf

http://deptinfo.cnam.fr/Enseignement/CycleProbatoire/Vari/EDs/ed1-exo1-corrige.html

http://www.cppfrance.com/r/global.aspx?r=exercices+corrig es+d+algorithme

http://casteyde.christian.free.fr/index.html

http://www.dacodoc.fr/10-informatique/85-programmation/5287-algorithmes-exercice



achraf.mouni ; 25-12-2008 10:04 PM
achraf.mouni    

(Tags)
, ,

« | »



bd lila88 11 10-07-2012 03:51 PM
radhwane 1 28-11-2009 06:50 PM
mimik 2 12-05-2009 06:46 PM
-- achraf.mouni 5 23-03-2009 09:21 PM
achraf.mouni c c++ c# 1 21-03-2009 04:42 PM


03:20 PM.