Algorithmique Techniques Fond Amen Tales de Program Mat Ion com

8/3/2019 Algorithmique Techniques Fond Amen Tales de Program Mat Ion com

1/221


2/221

Ce livre sadresse toute personne dsireuse de matriser les bases essentielles de la programmation. Pour apprendre programmer, il

faut dabord comprendre ce quest vraiment un ordinateur, comment il fonctionne et surtout comment il peut faire fonctionner des programmes,

comment il manipule et stocke les donnes et les instructions, quelle est sa logique. Alors, au fur et mesure, le reste devient vidence :

variables, tests, conditions, boucles, tableaux, fonctions, fichiers, jusquaux notions avances comme les pointeurs et les objets.Dans ce livre, le langage algorithmique (ou la syntaxe du pseudo-code des algorithmes) reprend celui couramment utilis dans les coles

dinformatique et dans les formations comme les BTS, DUT, premires annes dingnierie qui ce livre est en partie destin et

conseill. Une fois les notions de base acquises, le lecteur trouvera dans ce livre de quoi voluer vers des notions plus avances : deux

chapitres, lun sur les pointeurs et les rfrences, lautre sur les objets, ouvrent les portes de la programmation dans des langages volus et

puissants comme le C, le C++ et surtout Java.

Une grande partie des algorithmes de ce livre sont rcrits en Java et les sources, directement utilisables, sont disponibles en tlchargement

sur le site de lditeur (www.eni-livres.com).

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

Algorithmique

Techniques fondamentales de programmation

Sbastien ROHAUT

Rsum

L'auteur

Sbastien ROHAUT a dbut comme Ingnieur de dveloppement en C++. Aujourdhui Ingnieur Systme il intervient sur des missions

rgulires pour de grands comptes et continue denseigner le dveloppement des classes dingnieur et masters MTIC.

ENI Editions - All rigths reserved


3/221

Introduction

Pourquoi apprendre programmer ? Avez-vous, comme lauteur, dispos au dbut de la micro-informatique dunordinateur o il fallait programmer soi-mme des jeux ou outils, ou saisir des dizaines de pages de lignes deprogrammation ? Avez-vous besoin, durant vos tudes, de matriser les techniques fondamentales de programmationpour passer votre diplme? tes-vous un professionnel ou un autodidacte passionn qui veut encore en savoirdavantage ? Est-ce une nouvelle tape de votre carrire professionnelle o n tant pas informaticien vous tes amen programmer des macros ou des scripts complexes ? Quelle raison encore trouver ? Si vous rpondez oui l une des cesquestions, mais aussi aux dizaines d autres quil serait possible de poser, alors oui, vous devez apprendre programmer. Apprendre programmer, cest enfin savoir comment font les autres pour crer de superbes logiciels, c estsavoir terme comment les crer soi-mme, et les dvelopper.

Comment apprendre programmer ? On ne s improvise pas programmeur. Cest un mtier, et comme tout mtier, celasapprend. Dans les coles, des professeurs enseignants pour des classes de BTS, DUT, DEUG, classes prparatoires,etc., sont spcialiss dans lapprentissage des notions fondamentales de programmation. Les autodidactes se plongentdans des livres, des sites Internet, dans la documentation en ligne des langages, pour apprendre ces notions.Lensemble de ces notions cest lalgorithmique.

Ce livre reprend les notions essentielles, fondamentales, de la programmation. Pour apprendre programmer, il fautdabord comprendre ce quest vraiment un ordinateur, comment il fonctionne et surtout comment il peut faire fonctionnerdes programmes, comment il manipule et stocke les donnes et les instructions, quelle est sa logique. Alors, au fur et mesure, le reste coule de source comme une vidence: variables, tests, conditions, boucles, tableaux, fonctions, fichiers,

jusquaux notions avances comme les pointeurs et les objets.

Le formalisme algorithmique, (la syntaxe du langage algorithmique ou pseudocode) reprend celui couramment utilisdans les coles dinformatique et dans les formations comme les BTS, DUT, premires annes d ingnierie, qui ce livreest en partie destin et conseill. Il existe plusieurs variantes utilises, selon le professeur, le langage d origine. Celui

prsent ici a lavantage d

tre dans un franais trs explicite "tantque, jusqu

, pour chaque, afficher, saisir, etc.". Leurlecture ne ncessite aucune connaissance pralable de termes trop techniques.

Ce livre ne fait pas quaborder les notions basiques. Deux chapitres, l un sur les pointeurs et les rfrences, l autre surles objets, ouvrent les portes de la programmation dans des langages volus et puissants comme le C, le C++ etsurtout Java. Dailleurs, presque tous les algorithmes de ce livre sont rcrits en Java. Les sources directementutilisables sont disponibles en tlchargement sur le site des ditions ENI.

Lauteur tient particulirement remercier ses anciens professeurs de BTS du lyce de Montmorency, ses anciensprofesseurs et aujourdhui collgues de lESGI, notamment ceux dalgorithmique et de programmation C, C++ et Java quise reconnaitront, pour lui avoir transmis encore un peu plus le plaisir du mtier d informaticien et du travail bien fait.



4/221

Les fondements de linformatique

1. Architecture de Von Neumann

Un ordinateur est un ensemble de circuits lectroniques permettant de manipuler des informations qu on appelle desdonnes et capable de faire "tourner" des programmes, cest--dire une suite ou squence dinstructionsprogrammes lavance et quil va drouler du dbut la fin dans le but d obtenir des rsultats. Pour comprendrecomment un ordinateur peut drouler un programme, il faut tudier un peu plus en dtail son fonctionnement.

Cest Von Neumann qui a dfini en 1944 larchitecture des ordinateurs modernes encore largement utilise aujourdhui(avec des variantes cependant). L architecture de Von Neumann (issue des travaux de Turing dont il sera question plusloin) dcompose lordinateur en quatre parties distinctes :

Les instructions du programme sont prsentes dans la mmoire. L unit de contrle va prendre la premire instructiondu programme et lexcuter. Si linstruction est par exemple dadditionner deux nombres, elle va demander lUAL deprendre ces deux nombres en mmoire et de les additionner et ventuellement de placer le rsultat dans une nouvellecase. Puis lUC passe linstruction suivante. Si elle consiste afficher ce rsultat, alors l UC va lire le contenu de lammoire ladresse o est plac le rsultat, puis va envoyer le rsultat via le composant dE/S adquat. Et ainsi desuite. Au final le droulement dun programme au sein de l ordinateur est le suivant :

q lUC extrait une instruction de la mmoire,

q analyse linstruction,

q recherche en mmoire les donnes concernes par linstruction,

q dclenche lopration adquate sur lALU ou lE/S,

q range le rsultat dans la mmoire.

1. LUnit Arithmtique et Logique UAL (ALU en anglais) est lorgane de lordinateur quiexcute les calculs : additions, soustractions, multiplications, divisions, modulos, gestion dessignes (positif, ngatif), oprations logiques (boolenne), comparaisons, parfois rotations etdcalages de valeurs (toujours dans le cadre d une logique boolenne). Il existe des UALspcialises dans les nombres virgule flottante, d autres dans des traitements complexescomme les logarithmes, les inversions, les racines, les vecteurs, les calculs trigonomtriques,etc. Certaines documentations lui rajoutent quelques registres (petites cases mmoiresintgres lUAL) et lui donnent le nom de processeur (CPU).

2. LUnit de ContrleUC (CU en anglais), ne pas confondre avec Unit Centrale, contrle lesquenage des oprations, autrement dit le droulement du programme. Elle prend ses

instructions dans la mmoire et donne ses ordres l UAL. Les rsultats retourns peuventinfluer sur le squenage. LUC passe alors linstruction suivante ou une autre instructiontelle que le programme lui ordonne deffectuer.

3. La mmoire peut tre dcrite comme une suite de petites cases numrotes, chaque casepouvant contenir une petite information (petite dans le sens o la taille de chaque case estfixe). Cette information peut tre une instruction ou un morceau d instruction du programme(une instruction peut occuper plusieurs cases) ou une donne (nombre, caractre, oumorceau de ceux-ci). Cest lUC qui a comme rle central de contrler laccs la mmoirepour le programme et les donnes. Chaque numro de case est appel une adresse. Pouraccder la mmoire, il suffit de connatre son adresse. Les instructions du programme pourlUC et les donnes pour lUAL sont places dans des zones diffrentes de la mme mmoirephysique.

4. Les Entres/Sorties E/S (I/O en anglais) permettent de communiquer avec le monde

extrieur et donc vous : ce peut tre un clavier pour entrer les donnes, et un cran pourafficher les rsultats. Il permet lordinateur dtre interactif.



5/221

Von Neumann, pre des ordinateurs actuels

Si vous ouvrez le capot de votre ordinateur, vous y verrez une grande quantit de cartes, composants, cbles, et

mme des organes mcaniques (lecteurs de disques durs, cd et disquette). Un programme que vous allez crire etdrouler ne sexcute pourtant que dans un seul endroit : le microprocesseur. Le microprocesseur de votre ordinateurest une puce facilement reconnaissable car c est souvent la plus grosse, celle qui dispose du plus de pattes et estgnralement surmonte dun gros bloc daluminium ou de cuivre accompagn dun ventilateur pour le refroidir. Ilcontient lUAL, lUC et divers autres organes : des registres spcialiss (donnes, compteurs, adresses, tats, etc), unsquenceur qui synchronise tous les composants, une horloge interne, une unit dentre-sortie qui gre lacommunication avec la mmoire ( ne pas confondre avec lE/S des priphriques clavier, cran, etc). Lemicroprocesseur dispose selon son modle dun jeu (ensemble) dinstructions prdfini.

Sil tait tout seul, le microprocesseur ne pourrait pas faire grand chose. Au sein de l architecture de Von Neumannseuls sont reprsents les composants logiques de base. Autour de ce schma logique se raccordent bien d autresorganes lectroniques comme les contrleurs. Ces puces lectroniques quon appelle aussi parfois chipsets sont aussides sortes de microprocesseurs qui disposent souvent d un jeu dinstructions pour les contrler, justement. Cesinstructions sont souvent moins nombreuses et pas gnralistes. Les contrleurs ont un rle prcis, selon leur genre:grer un certain type de priphrique (ex : un contrleur de carte graphique, un contrleur pour les disques durs, etc),ou de transfert de donnes (ex : les contrleurs des bus de mmoire et de donnes, les contrleurs USB, PCI, etc).

Tous ces composants sont intgrs sur un circuit imprim principal appel la carte mre.

Architecture de Von Neumann

Pour rsumer : larchitecture de Von Neumann est simple comprendre et rpartit les fonctionnalits d un ordinateuren quatre entits logiques. Ces entits logiques se retrouvent pour deux dentre elles (UC et UAL) dans lemicroprocesseur. Les autres et les composants additionnels se retrouvent sur la carte mre ou sur les cartesdextension (la mmoire nest plus soude sur une carte mre mais fournie sous forme de carte additionnelle appelebarrette, le contrleur E/S graphique est sur une carte graphique additionnelle relie un bus PCI, AGP ou PCI/E). Lesprogrammes sont excuts par le microprocesseur qui est aid (dans le sens o celui -ci accde aux fonctionsproposes) par divers contrleurs.

2 - ENI Editions - All rigths reserved


6/221

Note : les microprocesseurs actuels sont trs complexes. Il n est pas rare de trouver au sein de ceux -ci plusieursUAL pour acclrer les traitements. De mme on trouve souvent une mmoire intermdiaire appele mmoire

cache ou antmmoire, celle-ci tant souvent spcialise : une mmoire cache pour les instructions et une autrepour les donnes.

2. La machine de Turing

Avant mme lapparition des premiers vrais ordinateurs programmables, Alan Turing avait dfini en 1936 (le 28 mai

exactement) ce quon appelle la Machine de Turing. Cette machine abstraite (qui nexiste pas rellement) est en faitune mthode de modlisation du fonctionnement dun ordinateur ou plutt lorigine dun calculateur mcanique.Comment faire pour, depuis un postulat de base, arriver un rsultat donn ? En respectant des procdures donnes.Cest lun des principes de lalgorithmique.

Une machine de Turing ntant pas une vraie machine (au sens matriel), il suffit pour s en servir soit de se servir de satte (rflexion et mmoire), soit dun crayon qui fera office de tte de lecture, dune longue bande de papierdcompose en cases qu on appelle ruban, et dune table de symboles et de procdures lie l tat de la case respecter quand on tombe sur une case contenant un symbole donn. On se place sur la premire case, on vrifie sonsymbole et son tat associs, on excute la procdure associe (changement de valeur/symbole, avancer, reculer) eton continue drouler ce programme jusqu ce que la procdure vrifiant quon a obtenu le rsultat final soitvrifie. On vient de drouler un programme, et lensemble symboles/procdure dcrit ce programme. Cest lanctre delalgorithme.

Alan Turing, crateur de la machine abstraite du mme nom

Il existe des livres complets sur la machine de Turing, notamment un de Alan Turing lui -mme et de Jean-Yves Girard,aux ditions Seuil, Collection Points Sciences. Linformatique nest pas le seul domaine dapplication de la machine. Ellepermet de dterminer la complexit dun algorithme, si quelque chose peut vraiment tre calcul, a des domainesdapplications dans la physique et notamment l optique, etc. Vous pouvez simuler une machine de Turing sur votreordinateur via plusieurs langages dont un appel Brainf*ck.

Exemple de machine de Turing

3. Reprsentation interne des instructions et des donnes

a. Le binaire

quoi ressemblent les instructions et les donnes (valeurs) utilises rellement par l ordinateur ? Celui-ci necomprend quune chose : des chiffres. Si ltre humain a invent des reprsentations pratiques des chiffres avec le



7/221

systme dcimal (soit une notation en base 10 en allant de zro neuf), un ordinateur ne manipule que deuxvaleurs : 0 ou 1. En effet si vous pouviez trs fortement agrandir un circuit intgr, vous verriez que celui -ci estcompos de nombreuses pistes dans lesquelles passe un courant lectrique.

Dans ces circuits il ny a que deux possibilits : soit le courant passe et dans ce cas cela quivaut une valeur de un(1), soit le courant ne passe pas, et dans ce cas cest la valeur zro (0) qui est retenue. C est du binaire (qui neprend que deux valeurs). Une unit binaire s appelle un bit (binary digit).Ce mot a t invent par Claude Shannonen 1948.

Comme il y a plusieurs pistes sur les circuits, plusieurs valeurs 0 et 1, donc plusieurs bits, circulent en mme temps.En associant ces valeurs, on obtient des valeurs plus grandes. En passant des donnes sur un fil, la valeur maximaleest de 1. Si on prend deux fils, soit deux bits, la valeur maximale en binaire est 11, soit 3 en dcimal. Pourquoi ? Voiciune dmonstration par tapes:

Une analogie fort ancienne (en informatique, ancien peut signifier un laps de temps trs court), des annes 1980,expliquait le fonctionnement des nombres binaires en associant des fils transportant du courant des ampouleslectriques. Chaque ampoule reprsente une valeur. Si le courant passe, l ampoule sallume et prend la valeur

associe.Le binaire, comme son nom lindique, utilise une base deux (2) tout comme le dcimal utilise une base dix (10). Endcimal, tous les nombres peuvent tre reprsents laide de puissances de 10. Prenez le nombre 1234 :

1*103+2*102+3*101+4*10 0=1234

Lunit est reprsente par 100, la dizaine par 101, la centaine par 102, et ainsi de suite. Pour convertir le binaire enune valeur dcimale plus lisible, il faut utiliser les puissances de 2, la plus petite valeur tant la plus droite et estappele bit de poids faible, la plus grande la plus gauche et est appele bit de poids fort. Dans lexempleprcdent, la valeur binaire 11 peut tre convertie ainsi :

1*21+1*20=21+20=2+1=3

Les informaticiens et mathmaticiens utilisent une notation particulire en indice (nombres en retrait bas) pourindiquer des conversions :

11(2) =3(10)

Voici un dernier exemple avec une valeur binaire code sur 8 bits. Quelle est la plus grande valeur dcimale qui peuttre code avec 8 bits ?

27+26+25+24+23+22+21+20=128+64+32+16+8+4+2+1=255

Donc

11111111(2) =255(10)

Soit 256 valeurs possibles de 0 (zro) 255, ce qui peut tre plus simplement calcul par 2 n, soit deux puissance n, ntant le nombre de bits contenus dans la valeur binaire. La plus grande valeur convertie en dcimal est donc :

2n-1

Il est possible de convertir du dcimal en binaire avec des divisions successives : on divise les rsultats sans lavirgule successivement par deux. Le rsultat binaire sera la juxtaposition des restes (0 ou 1) sauf pour le dernier. Parexemple avec le nombre 183:

q 183/2=91, reste 1

q 91/2=45, reste 1

q 45/2=22, reste 1

q 22/2=11, reste 0

Courant Fil 1 Courant Fil 2 Binaire Dcimal

Ne passe pas Ne passe pas 00 0

Ne passe pas Passe 01 1

Passe Ne passe pas 10 2

Passe Passe 11 3



8/221

q 11/2=5, reste 1

q 5/2=2, reste 1

q 2/2=1, reste 0

q On remonte du dernier : 10110111

Conversion dcimale en binaire

Cest donc en binaire que sont reprsentes toutes les valeurs qu un ordinateur manipule. Cest valable tant pour lesdonnes (numriques ou texte) que pour les instructions destination du microprocesseur. Un nombre binairecorrespondra une instruction. Par exemple sur un microprocesseur x86 (Intel ou AMD), 01110100 est linstructionje(jump if equal), ou encore la ligne 10110000 01100001 qui signifie mov $0x61, %al (placer la valeur hexadcimale0x61 dans le registre AL).

Les ordinateurs du dbut des annes 2000 savent manipuler des nombres sur 64bits or 2 64 est gal 18 446 744073 709 551 616 soit plus de 18 milliards de milliards !

Lide dutiliser deux valeurs pour encoder dautres valeurs remonte Francis Bacon. En 1623, il cherche unemthode stganographique pour pouvoir crypter un texte compos des lettres de lalphabet. Il remarque quunassemblage de deux lettres groupes par cinq permet de coder l ensemble de lalphabet. Il appelle cet alphabet"bilitre". Le "a" tait reprsent par "AAAAA", le "B" par "AAAAB", jusquau "Z", "BABBB". Lalphabet de lpoque, lelatin, contenait vingt-quatre lettres, le "j" se confondant avec le "i" et le "u" avec le "v".

b. Les octets et les mots

Un ordinateur sait manipuler individuellement chaque bit dune valeur. Mais les bits ne sont pas stocksindividuellement dans une case mmoire. Ils sont regroups, gnralement par multiples de huit (8). Ainsi unensemble de 8 bits est appel un octet. Lavantage de loctet est quil suffit (ou en tout cas a longtemps suffi) pourreprsenter tous les chiffres, lettres et symboles des alphabets occidentaux. Un octet reprsente les valeurs de 0 255.

Avec laugmentation des espaces de stockages, de la quantit de mmoire, du besoin de reprsentation de nombresde plus en plus grands, dun accs plus rapide la mmoire ou encore de plus d instructions, il a fallu augmenter lataille des valeurs manipuler. De 8, puis 16, puis 32, certains microprocesseurs peuvent manipuler des valeurs de 64voire 128 bits, parfois plus.. Ces valeurs deviennent difficiles dcrire et reprsenter. Pour ces valeurs, on parle demot mmoire (word en anglais). Certains microprocesseurs font une diffrence entre divers types de mots. Ceux deMotorola comme les 68000 (qui quipaient ls ordinateurs Atari ST, Amiga, les consoles Sega Megadrive et plusrcemment les Palm Pilot) utilisent des mots de 16 bits, et des mots longs (long word) de 32bits.

Les instructions et les donnes sont donc codes sous forme de nombres binaires qu on appelle des mots.Cependant suivant le type de microprocesseur l ordre des mots est diffrent entre la ralit et son stockage enmmoire. Avec un microprocesseur x86 en mode rel (16 bits) le nombre dcimal 38457 ncessite 16 bits soit deuxoctets ou un mot de seize octets pour tre reprsent :

38457(10)=1001011000111001(2)

Pour stocker cette valeur en mmoire, les 8 premiers bits de poids faible, soit l octet de poids faible, seront placsdans la premire case mmoire, et les 8derniers bits de poids fort, soit l octet de poids fort, seront placs dans lacase suivante. La dmarche serait la mme en 32 bits ou 64 bits.

Case mmoire 1 Case mmoire 2

00111001 10010110



9/221

c. Lhexadcimal

Si vous reprenez lexemple dune valeur binaire code sur 64 bits, il faut 64 0 ou 1 pour la dcrire:

1111111111111111111111111111111111111111111111111111111111111111

En dcimal il faut vingt chiffres : 18 446 744 073 709 551 616

a prend beaucoup de place et c est difficile manipuler. Puisquil existe une base 10 (dcimal) et une base 2(binaire), pourquoi ne pas prendre une base plus leve, multiple de 2, pour rduire la longueur et la manipulation deces nombres? Cest ainsi quen informatique il est dusage dutiliser la base 16, appele hexadcimale.

Une base hexadcimale permet de coder les valeurs de 0 15. Si de 0 9 on utilise les valeurs dcimalescorrespondantes, au-dessus il faut utiliser des lettres de lalphabet, de A (10) F (15).

Comment passer du binaire lhexadcimal ? Ceci revient rpondre la question "Combien faut -il de bits dans unnombre binaire pour coder 16 valeurs ?" 24=16. Il faut donc 4 bits. Le tableau suivant rsume les conversions.

Si vous reprenez le nombre 183 qui ncessite 8 bits soit un octet, sa conversion donne B7 en hexadcimal. On ditdonc que :

183(10)=B7(16)

du dcimal lhexadcimal

Si vous prenez la valeur maximale en 64 bits, cela donne FFFFFFFFFFFFFFFF soit 16 caractres. Un informaticienexerc est quasiment capable de convertir la vole de lhexadcimal en dcimal. Prenez la valeur 8C soit 10001100en binaire. Le C vaut 12.

8*16+12=140

Sans aller plus loin, sachez que les bases 2, 10 et 16 ne sont pas les seules. Sur certaines machines et certainssystmes dexploitation, il est courant dutiliser une base 8 pour des valeurs ne ncessitant que trois bits pour trereprsente. Somme toute, tant quil reste assez de symboles, rien n empcherait davoir une base 30 !

Dcimal 0 1 2 3 4 5 6 7 8 9 10

Hexa 0 1 2 3 4 5 6 7 8 9 A

Binaire 0 1 10 11 100 101 110 111 1000 1001 1010

Dcimal 11 12 13 14 15

Hexa B C D E F

Binaire 1011 1100 1101 1110 1111



10/221

Lalgorithmique

1. Programmer, cest un art

Pour obtenir un rsultat donn, il faut gnralement suivre une mthode, une certaine logique. Sauf tre un grandptissier dont la science des mlanges des ingrdients est inne (ou le fruit d une longue pratique), vous nobtiendrez

jamais un dlicieux gteau au chocolat mme si vous disposez des meilleurs ingrdients et accessoires de cuisson, sivous ne connaissez pas les bonnes proportions, l ordre dans lesquels ajouter les ingrdients, le temps de cuisson, latemprature : bref, la recette. De mme, sans formation de mcanicien ou sans la documentation technique du moteurde votre vhicule, inutile de vous lancer dans un changement de joint de culasse : c est la casse assure.

Il en est de mme de la programmation. Il existe plusieurs langages de programmation trs simples, extrmementsimples parfois, qui peuvent donner un temps lillusion que vous savez programmer. En entreprise mme, certainsemploys sont bombards dveloppeurs pour leurs quelques connaissances confuses de Visual Basic, de Delphi ou deWindev. Le rsultat risque dtre catastrophique. Les publicits sont allchantes mais trompeuses. Les bonsprogrammeurs, y compris les autodidactes, ont tous un moment ou un autre eu affaire avec les algorithmes, car ilexiste en programmation une multitude de moyens d arriver un rsultat, mais trs peu pour obtenir le meilleurrsultat possible, ce qui explique pourquoi beaucoup de programmes ayant la mme fonction, se ressemblent (auniveau de la programmation) alors que ce ne sont pas les mmes programmeurs qui les ont dvelopps. Les dbutantsqui se lancent dans des projets de programmation audacieux se retrouvent parfois bloqus, ne matrisant pas unetechnique particulire de logique de programmation. Certains abandonnent, d autres trouvent un moyen decontournement (souvent peu reluisant). Les derniers liront peut-tre un livre dalgorithmique comme celui-ci, qui dfaut de donner une solution complte leur problme, leur fournira les bases et les techniques pour avancer.

Les ordinateurs personnels du dbut des annes 1980 taient tous livrs soit avec un langage BASIC inclus

directement dans la machine (en ROM), soit sur une cartouche, cassette ou disquette annexe. Le Basic de Microsoft(Qbasic, Quickbasic) tait livr avec le DOS du PC. Les Amstrad avaient le basic Locomotive, les Atari ST lAtari Basic etsurtout le GFA Basic, un langage de grande classe, etc. Une gnration complte d utilisateurs sest lance dans laprogrammation laide de ces langages et de la documentation fournie qui bien souvent fournissait non seulement lesrfrences du langage mais aussi les mthodes de base de programmation. Avec plus ou moins de succs. Le rsultattait souvent un infme bidouillage, mais qui marchait.

Or le but nest pas que le programme fonctionne, mais quil fonctionne vite et bien, bref le mieux possible. Le meilleurordinateur au monde et le meilleur langage au monde ne vous y aideront pas.

2. Dfinition : Lalgorithme est une recette

Avez-vous dj eu loccasion de programmer un magntoscope (en voie de disparition) ou un enregistreur de dvd ?

Quavez-vous fait la premire fois que vous avez allum votre poste de tlvision pour rgler la rception des chanes ?Nul doute que vous avez ouvert le mode d emploi et suivi la squence dinstructions indique: appuyer sur la toucheMenu de la tlcommande, se dplacer sur Enregistrement et appuyer sur OK, se dplacer sur une ligne puis indiquerla chane, lheure, etc.

Avez-vous dj eu loccasion de faire la cuisine ? Pour un gteau, vous tes -vous lanc directement ou avez-vousouvert un livre pour rcuprer la liste et la quantit de chaque ingrdient, pour suivre la recette : faites fondre lechocolat et le beurre dans une casserole feu doux, retirez la casserole du feu, incorporez les jaunes d oeuf, puis lesucre et la farine, battez les oeufs en neige puis incorporez doucement dans le mlange, etc.

Dans les deux cas, flicitations ! Vous avez droul votre premier algorithme !

Une dfinition simple dun algorithme : cest une suite dinstructions qui, quand elles sont excutes correctementaboutissent au rsultat attendu. Cest un nonc dans un langage clair, bien dfini et ordonn qui permet de rsoudreun problme, le plus souvent par calcul. Cette dfinition est rapprocher du fonctionnement de la machine de Turingqui avant lapparition de lordinateur utilisait cette dmarche pour rsoudre de nombreux problmes. L algorithme estdonc une recette pour qu un ordinateur puisse donner un rsultat donn.

Le mot algorithme vient du nom du mathmaticien Al Khuwarizmi (Muhammad ibn Ms al-Khuwrizm), savant persan

du IX me sicle, auteur dun ouvrage appel "La transposition et la rduction", Al- jabr wal-muqbalah. Le mot Al-jabrdeviendra algbre, le nom de lauteur sera latinis en Algoritmi, qui sera la base du mot algorithme.

3. Pourquoi utiliser un algorithme ?

Lalgorithme dcrit formellement ce que doit faire l ordinateur pour arriver un but bien prcis. Ce sont les instructionsquon doit lui donner. Ces instructions sont souvent dcrites dans un langage clair et comprhensible par l trehumain : faire ceci, faire cela si le rsultat a telle valeur, et ainsi de suite.

Un algorithme bien tabli et qui fonctionne (tout au moins en thorie) pourra tre directement rcrit dans un langage



11/221

de programmation volu comme le C, Java ou PHP. Malheureusement, en programmation c est souvent lhomme dese mettre au niveau de la machine.

De la rflexion la programmation

Plus que cela, un algorithme dcrit une mthode de rsolution de problmes courants. Un algorithme est doncrutilisable, sauf cas ponctuel ou trs prcis. Il existe plusieurs moyens d obtenir un mme rsultat, mais certains sontmeilleurs que dautres. Cest le cas par exemple des mthodes de tris de donnes par ordre alphabtique. Il existedivers algorithmes dcrivant ces mthodes, certaines tant adaptes des quantits plus ou moins importantes dedonnes.

La matrise de lalgorithmique et lapprentissage des algorithmes de base sont une des conditions de la russite d unprojet en programmation, quil soit personnel ou professionnel. Lexprience aidant, vous allez acqurir au fur et mesure des mcanismes de pense qui vous permettront d optimiser les traitements que vous devez programmer, tanten vitesse quen occupation mmoire ou mme en quantit de lignes de programmation. Sur ce dernier point, il existe

de nombreux cas o des algorithmes longs et complexes sont plus performants que d autres semblant plus pratiquesau premier abord.

Apprendre lalgorithmique (ou lalgorithmie, les deux sont autoriss) c est donc apprendre programmer dans lesrgles de lart. Tout au long de cet ouvrage, vous allez dcouvrir les notions lmentaires qui vous permettront tant decomprendre le fonctionnement interne dun programme que de le concevoir, laide dune progression simple etconstante et dexemples pratiques et comprhensibles.

4. Le formalisme

Le but dun algorithme tant de dcrire un traitement informatique dans quelque chose de comprhensible par l humain(et facilement transposable vers la machine), pour qu un algorithme soit comprhensible, il faut quil soit clair et lisible.Dans ce cas il existe deux moyens efficaces:

q soit dcrire lalgorithme sous forme de texte simple et vident (faire ceci, faire cela),

q soit de faire un schma explicatif avec des symboles.

Dans la pratique, les deux formes sont possibles. Mais un dessin ne vaut-il pas un long discours ? Il est d ailleurscourant de commencer par un schma, puis quand celui-ci devient trop complexe, de passer un texte explicatif (larecette).

Dans les deux cas, la syntaxe pour le texte ou les symboles pour les schmas doivent rpondre des rgles strictes,voire normalises. Il faut que chacun connaisse leur signification et sache donc les interprter. C est pour a que toutesles reprsentations algorithmiques suivent peu de choses prs le mme formalisme. Si les schmas sont possibles, ilssont cependant moins utiliss que les algorithmes sous forme textuelle. Cest que si vous construisez un algorithme, ilest plus facile de le corriger quand il est saisi au clavier sous forme de texte que lorsqu il est dessin sous formedorganigramme dans un logiciel de dessin vectoriel ou de prsentation.

a. La reprsentation graphique

Les algorithmes peuvent tre construits laide de symboles dorganigrammes. Les tudiants en informatique (BTS,DUT) connaissent bien cette tablette en plastique permettant de dessiner des organigrammes. Ils lutilisent enalgorithmique, en base de donnes, en mthode Merise, etc (dans chaque cas la signification est diffrente). Voici unexemple dalgorithme sous forme dorganigramme qui simule un lanc de d et qui demande une personne dedeviner la valeur.



12/221

Un formalisme qui occupe trop de place

Dans cet exemple simplifi, les traitements sont dans des rectangles, les prises de dcision dans des losanges, et lesflches reprsentent lordre du droulement du programme. Si une valeur est prsente ct de la flche, l actiondpend du rsultat de la question pose dans le losange. Les dcisions et les flches peuvent dcrire des boucles.Dans le schma, tant que l utilisateur na pas saisi la bonne valeur, la question lui est de nouveau pose.

Cet algorithme est trs simple, lorganigramme aussi. Cependant voyez dj la taille de celui-ci (la place quil prend)par rapport ce quil fait. Imaginez maintenant un algorithme plus complexe qui doit par exemple dcrire tous les casde figure dans la gestion d une communication entre deux machines (description dun protocole de communication) :le schma ncessitera une feuille dune grande dimension et sera difficile tudier.

b. Lalgorithme sous forme de texte

Prenez le mme nonc du lanc de d. Celui -ci pourrait tre crit ainsi en franais correct :

q 1re tape : lancer le d

q 2me tape : saisir une valeur

q 3me tape : si la valeur saisie est diffrente de la valeur du d, retourner la troisime tape, sinon

continuer

q 4me tape : afficher "bravo".

Vu ainsi, cest trs simple. De cette manire, il est vident que tout le monde, mme un non -informaticien, comprend



13/221

ce que lalgorithme est cens faire. Cependant, si les algorithmes complexes devaient tre crits ainsi, ce seraitencore une fois bien trop long et vous finiriez soit par vous lasser dune criture trop complexe, soit cela prendraittrop de place. Cest pourquoi il faut utiliser une syntaxe prcise et concise.

/* Commentaires : ce programme affiche bonjour */

PROGRAMME HelloWorld

/* Dclarations : variables, constantes, types, etc */

VAR

de:entier,

valeur:entier

/* Dbut du programme */

DEBUT

dealatoire(6)valeur0

Tant que valeurde FaireLire valeur

FinTantQueAfficher "Bravo"

FIN

Si vous comprenez dj le programme ci-dessus alors cet ouvrage vous sera encore plus agrable lire. Sinon, lasuite vous donnera de toute faon toutes les explications ncessaires la comprhension de chaque ligne de cetalgorithme. Il reprend de manire trs dtaille toutes les tapes suivre. Sous cette forme, il est presque possibledimplmenter lalgorithme ligne ligne dans un langage de programmation volu.

Cest sous cette forme textuelle que les algorithmes seront reprsents dans ce livre. Ce texte, programme oupseudo-code algorithmique, est dcompos en plusieurs parties:

q Le nom du programme, qui namne pas de commentaires particuliers, situ aprs le mot " PROGRAMME".

q Une zone de dclaration des donnes utilises par le programmes: variables, constantes, types, structures,

tableaux, etc. Si la signification de ces mots vous chappe, ceux -ci seront expliqus au fur et mesure desdiffrents chapitres. Cette zone commence par le mot "VAR".

q Le programme lui-mme, cest --dire les divers traitements. Les instructions du programme sont encadres

par les mots "DEBUT" et "FIN". Il vous est conseill, pour plus de clart et de lisibilit, dindenter les diverseslignes (de les dcaler les unes par rapport aux autres) l aide des touches de tabulation. Le programme peuttre de nimporte quelle longueur: une ligne ou 10000 lignes, ceci n a pas dimportance.

q Les commentaires: cest un texte libre qui peut tre tendu sur plusieurs lignes et encadr par les squences

de caractres "/*" et "*/". Si votre commentaire tient sur une seule ligne, vous pouvez uniquement lacommencer par les caractres "//".

q Une dernire partie, ou plutt premire car lorsquelle est prsente elle se situe avant toutes les autres, peut

tre constitue des sous-programmes, semblants de programmes complets appels par le programmeprincipal. Ces sous- programmes, appels procdures ou fonctions, font l objet dun chapitre complet.

5. La complexit

Lexemple du lanc de d est un algorithme trs simple, court, concis et rapide. Ce n est pas le cas de tous les

algorithmes. Certains sont complexes et le traitement rsultant peut ncessiter beaucoup de temps et de ressourcesde la machine. Cest ce quon appelle le "cot" de lalgorithme, et il est calculable. Si un algorithme est "gourmand" soncot sera plus lev. Il existe certains cas o il est possible dutiliser plusieurs algorithmes pour effectuer une mmetche, comme pour trier les lments dun tableau de valeurs. Certains algorithmes se rvlent tre plus coteux quedautres, pass un certain nombre dlments trier. Le cot dun algorithme reflte sa complexit ou en terme plussimple son efficacit. Les mots "cot", "complexit" et "efficacit" refltent ici la mme dfinition. Plus un algorithme estcomplexe, plus il est coteux et moins il est efficace. Le calcul de cette complexit a comme rsultat une quationmathmatique quon rduit gnralement ensuite une notion d ordre gnral.

La complexit est not O(f(n)) o le O (grand O) veut dire "d ordre" et f est la fonction mathmatique de n qui est laquantit dinformations manipule dans lalgorithme. Voici un exemple pour mieux comprendre : soit un algorithme quicompte de 1 n et qui affiche les valeurs correspondantes. Dans la pratique, vous allez utiliser une boucle (voirchapitre correspondant) allant de 1 n. Il faudra faire n passages pour tout afficher et donc vous aller manipuler n foislinformation. La fonction mathmatique donnant le cot sera alors f(n)=n. La complexit est alors linaire et vous lanoterez O(n).



14/221

Si dans le mme algorithme vous dcidez de faire une seconde boucle dans la premire, pour afficher par exemple unetable de multiplications : la premire boucle va toujours de 1 n, la seconde va aussi de 1 n. Au total vous obtenez n

fois n boucles, donc n2 boucles. La complexit est donc f(n)=n2, et vous la noterez O(n2). Le cot de lalgorithmeaugmente au carr du nombre dinformations.

Si vous rajoutez en plus une quelconque opration dans la premire boucle, cette opration a aussi un cot que vouspouvez tenter de prendre en compte. Si vous ajoutez une multiplication et que celle -ci a un cot de 1, alors la

complexit finale est de n*(n+1) soit n2+n. Cependant si vous faites une courbe pour de grandes valeurs de n et que

vous comparez avec la courbe simple n2, vous remarquerez que le rajout devient ngligeable. Au final, lalgorithme

conserve une complexit O(n2).

Si la complexit peut parfois tre calcule assez finement, il en existe plusieurs "prdfinies":

q O(1): complexit constante

q O(log(n)): complexit logarithmique

q O(n): complexit linaire

q O(n.log(n)): complexit quasi-linaire

q O(n2): complexit quadratique

q

O(n

3

): complexit cubique

q O(np) : complexit polynomiale

q O(nlog(n)): complexit quasi-polynomiale

q O(2n): complexit exponentielle

q O(n!): complexit factorielle

Ces complexits ne sont pas forcment faciles apprhender, aussi voici un graphique reprsentant quelques unes decelles-ci. En abscisse est indiqu le nombre de donnes traiter et en ordonne la complexit associe: le nombre

doprations effectues pour n donnes. Pour des complexits d ordre O(2n) lalgorithme effectue dj 1024oprations, et plus de 3,5 millions pour O(n!)!



15/221

Courbes de complexit

Comment se reprsenter rellement une complexit en terme de temps pass par l ordinateur traiter les donnes?Chaque microprocesseur est capable de traiter un certain nombre doprations par seconde. Le plus long tantgnralement les calculs sur les rels (flottants), le critre souvent retenu pour dterminer la puissance brute dunprocesseur est le FLOPS : Floating Point Operations Per Second. Un Intel Pentium 4 3.2GHz tourne une moyenne

de 3,1 GFLOPS (GigaFlops) soit 109 FLOPS, ou encore un milliard doprations sur rels par seconde. Si vous traitez 20donnes dans un algorithme de complexit O(n), la vitesse de calcul se chiffre en millionimes de seconde. Le mmenombre de donnes dans un algorithme de complexit O(n!) doit effectuer 2432902008176640000 oprations ce quiprendra 784807099 secondes, ou encore une fois converti autour de 25 ans! Bien entendu, une complexit O(n!) est la

pire qui puisse exister. Avec une complexit infrieure O(2n), le traitement prendrait un dixime de seconde tout demme, ce qui est norme et relativise fortement la puissance des processeurs

Vous comprenez maintenant lutilit de connatre la complexit des algorithmes et doptimiser ceux-ci

Dans la suite, les complexits ne seront fournies que dans les cas o les traitements, plus compliqus que dhabitude,sont en concurrence avec diverses mthodes. C est le cas par exemple des mthodes de tris sur des tableaux. Cecidans lunique but de vous donner un simple ordre d ide.



16/221

Les langages dimplmentation

1. Quel langage?

Il existe plusieurs centaines de langages de programmation si on tient compte de toutes les variantes possibles d unmme langage. Comme vous avez pu le lire au dbut de ce chapitre, l ordinateur ne comprend nativement quun seullangage, le langage machine. Croyez-vous vraiment que vous allez implmenter le programme de lancer de ddirectement en binaire (ou mme en hexadcimal) ? Le choix du langage mrite une petite dmonstration. On acoutume dans le milieu de linformatique, de tester un langage en lui faisant afficher un message pour dire bonjour, enloccurrence le fameux Hello world!. Voici comment afficher ce texte dans divers langages :

Cseg segment

assume cs:cseg, ds:cseg

org 100h

main proc

jmp debut

mess db Hello world!$

debut:

mov dx, offset mess

mov ah, 9

int 21h

ret

main endp

cseg ends

end main

echo "Hello world!"

10 PRINT "Hello world!"

20 END

IDENTIFICATION DIVISION.

PROGRAM-ID. HELLO-WORLD.

ENVIRONMENT DIVISION.

DATA DIVISION.

PROCEDURE DIVISION.

DISPLAY "Hello world!".

STOP RUN.

#include

int main(int argc, char **argv)

{

printf("Hello world!\n");

return 0;

}

#include

En assembleur x86 sous DOS

En shell Unix

En Basic originel

En COBOL

En langage C

En langage C++



17/221

int main()

{

std::cout < "Hello world!" < std::endl;

return 0;

}

public class HelloWorld {

public static void main(String[] args) {

System.out.println("Hello world!");

}

}

Sub Main()MsgBox("Hello world!")

End Sub

program Bonjour;

begin

WriteLn(Hello world!);

end.

2. Classifications des langages

Que remarquez-vous ? Il y a autant de syntaxes diffrentes qu il existe de langages. Cependant vous constatez queles langages C, C++, Java ou PHP ont de nombreuses ressemblances, alors que l assembleur ou le COBOL semblentsortis douvrages de Science-Fiction. Cest que les premiers ont quelques liens familiaux tandis que les autres sontradicalement opposs.

a. Haut niveau, bas niveau

Puisquil existe des centaines de langages de programmation, lequel choisir pour implmenter vos algorithmes ? Il n ya pas de rponse simple cette question. Chaque langage a t gnralement conu pour des usages diffrents etsouvent spcifiques, bien quen voluant la plupart des langages dits de haut niveau soient devenus de plus en plusgnralistes. Il existe plusieurs classifications des langages. La plus ancienne dpend de l affinit du langage parrapport la machine. On parle alors du niveau du langage. Il est courant de parler dun langage de bas niveau ou de

niveau zro (0) quand celui-ci ncessite des connaissances approfondies du fonctionnement de votre ordinateur :mcanismes de gestion de la mmoire, instructions du microprocesseur, etc. Un exemple de langage de trs basniveau est le langage machine sous sa forme binaire, ou de le la programmation en assembleur o ces mmesvaleurs binaires sont reprsentes par des mots (mnmoniques) en anglais. Vu que les programmes sontdirectement comprhensibles par le matriel, vos programmes seraient alors les plus rapides. Il est tout faitpossible de programmer de grosses applications en assembleur (et notamment des jeux), ctait dailleurs trscourant jusqu lapparition des machines trs rapides o leur vitesse a compens une plus faible vitesse d excutiondun langage plus volu comme le C, mais avec l avantage dune programmation plus simple.

loppos des langages de bas niveau se trouvent les langages de haut niveau. Il n y a pas d chelle prcise. Vouspourrez trouver dans quelques sources des niveaux allant de 0 4, mais les langages voluant tellement vite,certains langages qui taient considrs de haut niveau comme le C se sont vus dclasss vers le bas ! Un langagede haut niveau permet de faire une abstraction presque complte du fonctionnement interne de votre ordinateur. Lelangage (ou plutt son compilateur ou son interprteur) se chargera de convertir vos ordres simples (en apparence)en langage de bas niveau (en langage machine). Ne vous fiez pas aux apparences : l affichage dune bote de

En PHP

En Java

En Visual Basic

En Pascal



18/221

dialogue prend une ligne de langage de haut niveau, mais des centaines en assembleur ! Parmi les langages de trshaut niveau se trouvent Java, C#, le PHP, ou mme le C (en faisant abstraction de certains mcanismes).Linconvnient dun langage de haut niveau est qu il n est pas toujours possible d aller dans les dtails les plus fins.

b. Diverses classifications

ct des niveaux, tous les langages nont pas le mme but. Il n est pas possible de comparer le langage HTML dontle rle est de formater des pages web et le Visual Basic qui permet un dveloppement rapide d applicationsgraphiques. Cest pourquoi il existe dautres classifications dont voici un bref chantillon :

q gnraliste ou spcialis

q objet ou procdural

q typ ou non typ (cf chapitre sur les variables)

q interprt ou compil

q etc

Certains langages sont spcialiss. Le HTML est spcialis dans la conception de pages web statiques : sonexcution a comme rsultat direct laffichage dune page HTML quil a mis en forme. Le SQL est un langage de base dedonnes : il permet de grer des enregistrements de donnes. Le Javascript est un langage qui permet de

programmer des pages web dynamiques du ct du navigateur web, tandis que le PHP (bien que devenugnraliste) ou ASP permettent de programmer des sites web dynamiques mais cette fois du ct du serveur.Certains langages peuvent faire appel d autres langages. Vous pouvez parfaitement faire du SQL dans du PHP, sivotre site doit accder une base de donnes...

c. Compil ou interprt

Une autre distinction prendre en compte est la diffrence entre un langage interprt et un langage compil. Unlangage est dit compil quand le programme source sous forme de texte est tout d abord lu et trait par un autreprogramme appel compilateur qui le convertit en langage machine directement comprhensible par l ordinateur.Vous tapez votre programme, vous lancez la commande de compilation et enfin vous obtenez un fichier excutable(un .exe sous Windows par exemple) que vous pouvez le cas chant lancer comme n importe quel autre programmeen langage machine. Un programme en langage interprt ncessite pour fonctionner un interprte (ou interprteur)qui est un autre programme qui va traduire directement, au fur et mesure de son excution, votre programme en

langage machine, un peu comme un vrai interprte qui dans un interview traduit simultanment langlais en franais.Le programme est souvent un fichier texte, et linterprte analyse la syntaxe de celui-ci avant de le droulerdynamiquement. Un programme interprt sera plus lent qu un langage compil cause de la conversion dynamiquedu programme, alors que cette tape est dj effectu l avance avec un langage compil. Au contraire, la correctiondes erreurs est plus simple avec un langage interprt. L interprte va vite vous indiquer au cours de lexcution ose trouve lerreur de syntaxe (mais pas de logique) lorsquil va la rencontrer, quelle ligne, linstruction en cause,ventuellement une aide supplmentaire. Alors qu avec un compilateur, cest au moment de la compilation, souventlongue, quapparaissent les erreurs. Une fois compil, d autres erreurs plus complexes comme les fuites mmoirepeuvent apparatre mais il devient difficile den dterminer lorigine (il faut alors faire appel d autres programmesspciaux appels dbuggers).



19/221

tapes de compilation et ddition des liens en C

3. La machine virtuelle

Il existe une tape intermdiaire entre linterprt et le compil: la machine virtuelle applicative. La machine virtuelle

est un programme, gnralement un interprteur, qui permet d isoler lapplication quil doit faire tourner du matriel etmme du systme dexploitation. Le programme na thoriquement aucun accs aux spcificits du matriel, lensemblede ses besoins lui tant fourni par la machine vituelle. Ainsi, tout programme conu pour cette machine virtuelle pourrafonctionner sur nimporte quel ordinateur, du moment que la dite machine virtuelle existe pour cet ordinateur. C est enquelque sorte une couche dabstraction ultime. Gnralement, le programme fonctionnant depuis la machine virtuelle adj subi une premire phase de compilation pour le transformer non pas en langage machine propre l ordinateur,mais dans un langage "machine virtuelle" pour ainsi dire, que l on nomme bytecode. Ce bytecode pourra treinterprt par la machine virtuelle, ou plutt, et ceci de plus en plus rgulirement, compil la vole juste au momentde son utilisation (technologie JIT,Just in Time).

Ainsi dans certaines circonstances le programme fonctionne presque aussi vite qu un programme compil pour unemachine cible ! Un exemple de langage utilisant une machine virtuelle est Java.



20/221

Gnration et excution de bytecode Java

Pour implmenter vos algorithmes, il vous faut trouver un langage simple, de haut niveau, gnraliste mais vouspermettant par la suite dvoluer vers des applications plus complexes et compltes. Dans un esprit d ouverture et decompatibilit, il serait intressant que ce langage ne soit pas disponible uniquement sous Windows, et que si possiblele programme rsultant puisse fonctionner sur plusieurs systmes d exploitation sans avoir le modifier, ni lerecompiler. Parmi les langages qui pourraient convenir, il y a C# (prononcer C Sharp) et Java. Le premier, issu de la

technologie .NET de Microsoft, tait lorigine destin uniquement aux plateformes Windows (.NET tait dcritmultiplateforme, ce qui selon Microsoft signifiait compatible avec la plupart des versions de Windows, pas les autressystmes comme MacOS ou Unix). Une implmentation libre et fonctionnant sur un grand nombre d architecturesmatrielles et de systmes dexploitation est disponible sous la forme de Mono qui propose la plupart des lmentsde .NET. Mais certains de ceux-ci sont protgs par des brevets (les brevets logiciels ne sont pas valides en Europe) etny sont pas tous intgrs. Aussi il existe les programmes en C# qui pourraient ne pas fonctionner avec Mono. Il fautdonc temporairement mettre ce langage l cart.

4. Java

a. Les avantages

Java, cependant, dispose de toutes les qualits ncessaires. Bas sur une machine virtuelle (tout comme Mono,dailleurs), il suffit que celle-ci soit intgralement disponible pour la plupart des environnements matriels et dessystmes dexploitation pour que tout programme Java fonctionne sans aucune modification. C est le cas. Dvelopporiginellement par Sun Microsystems, le langage Java, sa machine virtuelle et tout son environnement (ce qu onrsume par la "Technologie Java") sont disponibles pour Windows mais aussi pour MacOS, Linux et la plupart desautres Unix (Solaris, AIX, HPUX, Tru64, etc). Tout programme en Java fonctionnera sur tous ces systmes ! Mieux, sivous tes amateur de libert et de logiciels libres, sachez que la version 7 (prvue en 2008) sera la premire versiondisponible sous licence GPL.

Il existe plusieurs versions de Java. Celle qui vous intresse en priorit dans le cadre de ce livre est la versionstandard, ou SE (Standard Edition). Vous pouvez tlcharger Java depuis le site de Sun Microsystems l adressehttp://java.sun.com/javase/downloads/index.jsp. Quand cela sera possible, chaque algorithme prsent par la suitesera implment (programm) en Java. Pourquoi ce langage est-il intressant pour les dbutants ?



21/221

q Il est gratuit.

q Il est disponible pour beaucoup de machines et de matriels.

q Tout programme Java fonctionnera sur toutes les machines virtuelles, sans modification. Il est indpendant dela plate-forme.

q Il existe de nombreux diteurs et IDE (Integrated Development Environment) supportant ou tant spcialisspour Java.

q Il est utilis par des millions de personnes.

q Il est rput sr, ne pouvant thoriquement pas accder au systme d exploitation ou la machine elle-mme sans autorisation explicite.

q Il dispose dune immense collection de bibliothques, rpondant presque tous les besoins. Il est mmepossible de programmer des jeux en 3D de type commercial.

q Il est lun des piliers du web grce aux fameuses applets, aux servlets mais permet la programmationdapplications trs compltes.

q Il fait totalement abstraction du matriel pour se concentrer sur la program - mation fonctionnelle. Parexemple, vous navez absolument pas vous proccuper de la gestion de la mmoire (la plaie desprogrammeurs), Java le fait pour vous.

q Il est driv du langage C++, sans ses complications. Un programmeur C et C++ peut facilement comprendreJava, de mme quun programmeur Java pourra apprendre plus facilement le C++.

q Il est objet, notion qui sera sommairement tudie en fin douvrage.

q Il peut fonctionner tant en mode texte (depuis une console MSDOS ou un shell MacOS/Unix) quen modegraphique.

q Il est rapide, grce au principe du JIT ou de compilation la vole.

Sil faut citer un seul dfaut de Java (mais pas forcment le seul, rien n est parfait), cest quil est plutt gourmand enressources de la machine, surtout la mmoire. Pour les exemples de ce livre, videmment cela ne se ressentira pas.Mais si vous commencez dvelopper de trs gros programmes, alors un excs de mmoire ne sera pas inutile.

Comme les algorithmes de ce livre seront aussi rimplments en Java vous devez disposer du minimum vouspermettant de taper le code (texte), cest--dire dun diteur. Lditeur de texte de base de votre systmedexploitation suffira, comme notepad sous Windows, gedit/kedit sous Linux, etc. Il existe cependant un trs bonditeur dvelopp en Java, destin aux programmeurs. Vous le trouverez l adresse http://www.jedit.org/.

videmment, il vous faut aussi le ncessaire pour compiler (en bytecode) et excuter vos programmes (la machinevirtuelle). Sur le site de Sun, vous pouvez tlcharger deux versions : le JDK et le JRE. Le JDK, Java Development Kit,est celui que vous devez tlcharger, contenant tout le ncessaire pour concevoir et excuter vos programmes. Parcontre, une fois votre programme compil, vous pouvez n utiliser que le JRE, Java Runtime Environment, ce quipourrait se traduire par environnement dexcution Java. Il ne sert rien dinstaller les deux en mme temps sur lamme machine, puisque le JDK inclut le JRE.

b. Un premier programme Java

Le premier programme Java que vous allez taper, compiler et lancer est le fameux "Hello World" dont lalgorithme nemrite videmment pas dtre expliqu, vu que le programme se contente dun simple affichage. Le code Javarsultant est le suivant.

public class HelloWorld {


System.out.println("Hello world!");

}

}



22/221


23/221

La variable

1. Principe

Vous savez grce au chapitre prcdent comment lordinateur se reprsente les chiffres et les nombres : sous forme debinaire. De mme la mmoire de lordinateur, compose de cases, peut contenir des informations, notamment cesfameux nombres. En programmation, il faut quelque chose de simple, pratique et souple manipuler pour reprsenterces nombres.

Chaque case de la mmoire est numrote. Si la mmoire fait, disons, 256 octets, et que chaque case peut contenir unoctet, alors il y a 256 cases numrotes de 0 255. On peut donc obtenir la valeur d une case depuis son numro, endisant que la case 74 contient la valeur 212. L o a se complique, c est que la mmoire de vos ordinateurs atteint unnombre trs important de cases. Avec 1 Go de mmoire, vous avez 1073741824 cases pouvant contenir chacune unoctet. Comment voulez-vous vous souvenir de chaque numro de case ? Cest bien entendu impossible.

Si par contre vous donnez un nom ou une tiquette chaque valeur contenue dans la case, ou une suite de valeursde plusieurs cases, pour vous en rappeler plus facilement, cela devient bien plus vident. C est ce quon appelle unevariable. En informatique, une variable est lassociation dune tiquette une valeur. Vous nommez la valeur. Lavariable reprsente la valeur et se substitut elle. La variable est donc la valeur. Mais comme son nom lindique, cettevaleur peut changer dans le temps, soit que la variable ne reprsente plus la (ou les) mme(s) case(s) mmoire, soitque la valeur de la case a chang.

Une variable est un nom ou tiquette donn une valeur (nombre, texte, etc). Cette valeur peut varier au coursdu temps : on affecte une nouvelle valeur au nom, d o le nom de variable.

Quel nom donner une valeur ? Le nom que vous voulez et qui, si possible est en rapport avec ce que reprsente lavaleur. Ce peut tre une lettre, une association de lettres et de chiffres, ou d autres symboles. Le formalisme des nomsdes variables dpend du langage utilis. Des fois, un caractre spcifique indique le type (que vous rencontrerez plusbas) de la variable : ce qu elle peut contenir.

Certains langages acceptent des noms en lettres minuscules, majuscules, avec des chiffres dedans, des caractresspciaux comme le soulign, etc. Quelques langages, dont Java, font la diffrence entre les minuscules et lesmajuscules. Si vous pouvez gnralement utiliser un nom de grande taille, vitez pour des raisons purement pratiquesles noms rallonge. Voici quelques exemples de noms de variables :

q a

q var

q titre

q Total

q Somme_globale

Quand vous programmerez, vous veillerez vous renseigner sur les conventions utilises par le langage pour nommervos variables : certains utilisent des syntaxes trs particulires, d autres sont beaucoup moins stricts.

La variable nest quun outil pour les algorithmes et le programmeur, afin qu il puisse se reprsenter "dans le rel" lesdonnes quil manipule. Si vous modifiez le nom "Somme_globale" par "Pomme_frite" partout dans l algorithme ou leprogramme, la variable reprsentera toujours la mme donne, le programme fonctionnera l identique, mais ce seraplus difficile pour vous de faire le rapprochement. De mme la case mmoire ne porte pas rellement un nom outiquette. Chaque case est plutt rfrence par une adresse, elle-mme exprime par une valeur binaire. Cest lecompilateur ou linterprteur qui fera la conversion des noms vers les adresses des cases mmoire votre place.

Si vous souhaitez vous "amuser" manipuler directement des adresses mmoire non pas par leur nom mais par leuradresse, quelques langages le permettent. Directement, vous pouvez apprendre l assembleur (mais vous devrez tretrs courageux et patient), sinon des langages comme le C ou le C++ permettent la manipulation via des "pointeurs" :ce sont des tiquettes qui sont accoles ladresse de la case mmoire, contrairement aux noms des variablesclassiques qui sont associes la valeur que la case contient. Comme en rgle gnrale le nom d une variablereprsente tant ladresse que la valeur (la valeur a telle adresse mmoire), cest source de beaucoup d amusement (!)pour le programmeur...



24/221

La variable : une tiquette associe une valeur en mmoire

2. Dclaration

Pour exister, une variable doit tre dclare, c est--dire que vous devez indiquer au dbut de l algorithme comment ellesappelle et ce quelle doit contenir. En effet, pour que lalgorithme utilise votre variable, il doit dj savoir quelle existe

et ce quelle doit contenir. Il ne sagit pas ici de dfinir la valeur de la variable, vous pourrez le faire dans la suite delalgorithme en lui affectant une valeur. Il sagit de donner son nom et de prciser le type de valeur qu elle peut contenir.Les variables se dclarent au dbut de l algorithme, avant le programme lui-mme mais aprs le mot "VAR".

VAR

Variable1 :type

Variable2,variable3 :type

...

3. Les types

Une case mmoire contient gnralement un octet, cest--dire une valeur de 0 255. Mais une variable peut trs bien

contenir le nombre 214862, le rel 3,1415926, le texte "bonjour", etc. Donc une variable nest pas uniquement dfiniepar la valeur quelle contient, mais aussi par la place que cette valeur occupe et par la manire dont l algorithme va la

reprsenter et lutiliser : nombre, texte, etc. Cest le type de la variable.

Que pouvez-vous mettre comme valeur dans une variable ? En principe, tout ce que vous voulez. Cependant, vousdevez tout de mme prciser quel type la valeur reprsente. Est -ce un nombre ?

Si oui, un entier (sans virgule) ou un rel (avec virgule) ? Est -ce du texte ? Est-ce un tableau ? Et ainsi de suite. Vousentendrez parfois parler du "codage" de la variable : selon le type et la taille de la valeur, celle -ci est encode demanire diffrente dans la mmoire, utilisant plus de cases.

a. Les nombres

Placer des nombres dans la variable est le plus vident, et souvent le plus courant. Une case mmoire peut contenirun octet, cest--dire une valeur comprise entre 0 et 255 (28-1). Mais si elle doit contenir une valeur ngative ? Alors

sur les 8 bits, un sera rserv au signe, et la case mmoire pourra contenir des valeurs de -127 +128. On dit alorsque la variable est "signe" : elle peut contenir des valeurs positives et des valeurs ngatives. Seulement, 8 bits nesont pas suffisants pour des grandes valeurs. C est pourquoi les nombres peuvent tre placs dans deux cases (16bits), quatre cases (32 bits) ou plus.

Si lordinateur est bien plus laise et bien plus rapide avec des nombres entiers, il sait aussi manipuler des nombresrels, bien que dans ce cas leur codage en binaire soit radicalement diffrent. Vous trouverez plus bas toutes lesexplications ncessaires pour comprendre comment lordinateur se reprsente exactement les nombres ngatifs etrels : ce nest pas si vident !

Au final, lordinateur est capable de grer des nombres de longueur variable, signs ou non, entiers ou rels. Suivantle langage de programmation, les types portent des noms diffrents. Cependant le C et ses drivs proposent lestypes suivants. Attention car Java fait la diffrence entre le type Byte de un octet et le type Char qui prend deux octets cause du format de codage des caractres en Unicode.



25/221

Vous devez choisir quel type numrique utiliser selon vos besoins. La voie de la facilit consiste prendre le type leplus lev comme un entier long ou pire, un rel en double prcision afin d tre tranquille. En informatique commedans beaucoup de mtiers, il faut choisir la formule la plus conomique. On parle ici d conomie de moyens. Quun

programme donne le rsultat attendu nest pas suffisant, il faut aussi qu

il le fasse vite, bien et en consommant lemoins de ressources possibles. Le fait de disposer de plusieurs giga -octets nest pas un critre suffisant pour

programmer nimporte comment. Une liste de mille valeurs comprises entre 0 et 100 cotera 1000 octets (soit pasloin de 1 ko) dans un type byte, mais 8000 octets (pas loin de 8 ko) soit 8 fois plus dans une type rel doubleprcision. Cela peut sembler faible, mais non seulement l ordinateur doit manipuler 8 cases mmoire au lieu d une,mais en plus il doit en permanence convertir une valeur quil pense tre un nombre rel avec des chiffres aprs lavirgule en entier, alors que c est dj le cas ! Quand vous verrez plus bas la formule mathmatique ncessaire, vousvous rendrez compte du gchis !

Utilisez les types qui vont bien avec les valeurs qui vont bien. En algorithmique, c est bien plus simple. Rien ne vousempche de prciser que vous manipulez des entiers ou des rels, mais vous pouvez aussi indiquer tout simplementque vous utilisez des variables contenant des valeurs numriques avec le pseudo -type "numrique". Vous devrezcependant tre plus circonspect quand vous convertirez votre algorithme en vrai langage de programmation. D unemanire gnrale, deux types numriques sont utiliss en algorithmique :

q Les entiers : nombres sans virgule, ngatifs ou positifs

q Les rels : nombres virgule, positifs ou ngatifs.

Les variables se dclarent toutes au dbut de l algorithme. Si durant la rdaction de celui-ci vous remarquez que vousen avez besoin dautres, vous les rajouterez au dbut.

VAR

montant:rel

somme,moyenne:rels

qte :entier

Pour les variables contenant des nombres rels, ces derniers s crivent avec une vraie virgule comme en franais"3,14" ou avec le point dcimal, cependant dans les langages de programmation, ce sera bien souvent le point qui

sera utilis "3.14".En Java, les types portent les mmes noms, en anglais, des types situs dans le tableau prcdent, mais ne disposepas de types non signs. Autrement dit, une variable numrique peut contenir des nombres positifs ou ngatifs, maislintervalle de valeurs se trouve "un peu" rduite. Le seul type non sign est le type char (le type caractre) pour desraisons videntes que vous verrez plus bas.

Dans lexemple suivant, tous les types numriques classiques de Java sont dclars. Les noms des variables sontassez parlants pour les comprendre. Puis chaque variable se voit assigne la valeur maximale qu elle peut supporter.Ce programme amne trois remarques :

q Le rel 32 bits (float) voit sa dfinition force : le compilateur indique une erreur signifiant un risque de pertede prcision autrement. Il est aussi possible dajouter un "D" la fin pour forcer un double ou un "F" pour unfloat, car Java considre les valeurs relles saisies comme tant du type double par dfaut.

Type numrique Plage de valeurs possibles

Byte (char) 0 255

Entier simple sign (int) -32 768 32 767

Entier simple non sign 0 65535

Entier long sign (long) -2 147 483 648 2 147 483 647

Entier long non sign 0 4294967295

Rel simple prcision (float)Ngatif : -3,40x1038 -1,40x1045

Positif : 1,40x10-45 3,40x1038

Rel double prcision (double)Ngatif : -1,79x1030 8 -4,94x10-324

Positif : 4,94x10-324 1,79x1030 8



26/221

q Java considre les valeurs entires saisies comme tant 32 bits par dfaut. Pour un entier sur 64 bits, il fautrajouter un "L" la fin, qui signifie que cette valeur est un entier long.

q Laffichage de la valeur de PI est tronqu, rsultat de la prcision applique sur un rel 64 bits et par Java.

class chap2_types {


byte entier8bits;

short entier16bits;

int entier32bits;

long entier64bits;

float reel32bits;double reel64bits;

entier8bits=127;

entier16bits=32767;

entier32bits=2147483647;

entier64bits=9223372036854775807L;

reel32bits=3.1415927f;

reel64bits=3.1415926535897932384626433832795028841971d;

System.out.println(reel64bits);

System.out.println(entier64bits);

}

}

b. Autres types numriques

Il existe dautres types numriques moins utiliss, tout au moins sur les ordinateurs personnels ou dans des langagesde programmation classiques, mais bien plus sur des moyens ou gros systmes ou dans des bases de donnes. Lesystme BCD binary coded decimal pour dcimal cod en binaire est utilis principalement en lectronique car il estassez simple mettre en uvre. En BCD, chaque chiffre est cod sur 4 bits : 0000 (2) =0(10), 0001(2) =1(10), 0010(2) =2

(10), 0011(2) =3(10), et ainsi de suite jusqu 1001(2) =9(10). Comme un ordinateur ne manipule que des octets

(composs de 8 bits), il existe deux mthodes pour coder des nombres en BCD :

q soit ne mettre quun chiffre par octet et complter le reste que par des 1 ou des 0, "EBCDIC"

q soit mettre deux chiffres par octet, et rajouter un signe la fin, " packed BCD".

Par exemple le nombre 237 :

11110010 11110011 11110111 en EBCDIC

00100011 01111100 en Packed BCD (le 1100 final est le +, 1101 pour le -)

Vous rencontrerez peut-tre un jour le type "montaire" pour grer les sommes de mme nom et notamment lesrgles darrondi, mais aussi et surtout une grande quantit de types permettant de grer les dates, courammentexprims sous le nom "date". Lordinateur de type PC stocke les dates de diverses manires, la plus commune tantsous la forme dun timestamp, une valeur signifiant le temps coul depuis une date prcise. Ce timestamp estsouvent celui du systme Unix, qui reprsente le nombre de secondes coules depuis le 1er janvier 1970 minuitUTC, exactement. Cest donc un entier, et le langage doit fournir des instructions pour convertir cette valeur en daterelle.

c. Les caractres

Si un ordinateur ne savait manipuler que les nombres, vous ne seriez pas en train de lire ce livre, crit l aide duntraitement de texte (OpenOffice.org), qui lui manipule toute sorte de caractres : chiffres, lettres, caractres spciaux,etc. Une variable peut aussi contenir des caractres. Suivant les livres et sites Internet, vous trouverez les types"Alphanumrique", "Caractre", "Chane", "String". Ainsi une variable peut stocker votre nom, une ligne complte detexte, ou tout ce que vous voulez qui ncessite une reprsentation alphanumrique. On appelle d ailleurs une suite decaractres alphanumrique une chane de caractres.

Si vous devez reprsenter un seul caractre, utilisez le type "caractre". Pour une chane, utilisez le type "chane".

VAR

texte:chane

car:caractre



27/221

Quelle place occupe une chane de caractre ? En principe, un caractre occupe un octet. chaque valeur compriseentre 0 et 255 est associ un caractre. C est le principe de lASCII " American Standard Code for InformationInterchange", norme de codage des caractres la plus connue et la plus utilise. La table ASCII, invente par lesamricains, contient lorigine les 128 caractres utiles pour crire en anglais. Par dfaut elle ne contient pas lesaccents. Or la table ASCII peut contenir 256 caractres. Les 128 autres (huitime bit un) contiennent des caractressemi-graphiques et des caractres spcifiques certaines langues, typiquement le franais, pour les caractresaccentus. On parle alors de page de code ou de charset. Ces pages font l objet dune normalisation, par exemple lanorme ISO 8859-15 qui est la page dEurope de lOuest, avec le caractre de leuro "". Dans la plupart des langagesce codage sur un octet suffit et ainsi une chane de caractres de 50 caractres occupe 50 octets.

En pseudo-code algorithmique, les chanes de caractres sont places entre guillemets pour deux raisons :

Java dispose dun type spcial pour les chanes de caractres appel "String". Lexemple suivant montre deux moyensde placer du texte dans une chane. Il est possible de le faire ds la dclaration de la variable (c est dailleurs possibledirectement pour la plupart des types), soit ensuite par affectation.

class chap2_string1 {


String texte="Hello World !";

String text2;

text2="Bonjour les amis";

System.out.println(texte);

System.out.println(text2);

}

}

d. Le type boolen

Pour dterminer si une affirmation est vraie ou fausse, l ordinateur doit se baser sur le rsultat de cette affirmation. Eninformatique, on emploie plus volontiers la notion dexpression et dvaluation de cette expression. Une expressionpeut tre dcrite comme tant tout ce qui peut fournir une valeur que lordinateur peut dterminer, stocker, valuer.Par exemple, laffirmation "a>b" selon laquelle a est suprieur b. Si a vaut 3 et b vaut 2, l affirmation est vraie. Simaintenant a vaut 1 et b vaut 2, laffirmation est fausse. Dans les deux cas "a>b" est une expression qui vaut soitvrai, soit faux. Cest le cas le plus simple, mais aussi le plus courant et le plus pratique comme vous le verrez lors destests et des conditions.

Comment lordinateur dtermine-t-il ce qui est vrai et faux ? Cest le rle, dans larchitecture de Von Neumann, delUAL. Sous quelle forme lordinateur se reprsente-t-il ce qui est vrai ou faux ? Sous forme numrique, commetoujours. Tout ce qui retourne un rsultat diffrent de zro (0) est considr comme tant vrai, donc si le rsultat vautzro (0) alors il sera considr comme faux. Avant de considrer cette dfinition comme exacte, renseignez-vous tout

de mme car certains langages (comme linterprteur de commande Unix) font l inverse ! Cependant dans deslangages comme Java ou le C, 1 est vrai, 0 est faux.

Pour reprsenter les valeurs vrai et faux, il suffit de deux chiffres, 0 et 1. Combien faut -il de place pour stocker cesdeux valeurs ? Un seul bit ! En pratique, les langages grent les boolens de plusieurs manires. Certains crent des"champs" de bits dans un mme octet, d autres utilisent un octet complet, etc. Cependant, plusieurs langagesproposent le type boolen, trs pratique.

Dans la pratique, ces langages proposent des constantes (des variables qui prennent une valeur une fois pour toute)spciales pour reprsenter les valeurs vrai et faux :

q TRUE pour vrai

q FALSE pour faux

1. viter une ambigut entre les nombres sous forme de chane de caractres et les nombresau format numrique. Certains langages ne font certes pas directement la diffrence (cestselon le contexte dutilisation) mais avec dautres cest catastrophique. La suite decaractres 1,2,3 reprsente-t-elle le nombre 123 et stocke ainsi en mmoire sous formebinaire dans un octet de la mmoire, ou la chane "123" stocke ainsi en mmoire sousforme de codes ASCII, soit un pour chaque caractre ? Les guillemets vitent les erreursdinterprtations.

2. Ne pas confondre le nom de la variable avec son contenu, notamment lors dune affectation.Ainsi, quand vous affecterez un valeur une variable, si celle-ci est entre guillemets vous luiaffecterez une chane de caractres, si c est un nombre, ce sera ce nombre (sachant que lenom dune variable ne peut pas tre constitu uniquement de chiffres), et enfin si ce nest niune chane ni un chiffre, cest une variable. Dans ce cas la premire variable recevra commevaleur celle de la seconde qui lui est affecte. Ne pas respecter ce principe est une causederreur grave et nanmoins commune.



28/221

Ces constantes peuvent mme tre utilises directement pour valuer une expression. Telle expression est -elle vraie,telle autre est-elle fausse ? Suivant le langage, il faudra faire attention si les constantes existent et sont enminuscules ou majuscules.

VAR

Test:boolen

Java dispose aussi dun type spcial pour les boolens appel " Boolean". Comme la plus petite unit de stockagedune case mmoire est loctet, le boolen occupe un case donc un octet. Cependant il ne peut accepter que deuxvaleurs : true et false. lexcution, les valeurs [true et false] seront affiches en toutes lettres. Remarquez ici une

nouvelle proprit : la dclaration des variables il est possible tout comme en pseudo -code de mettre plusieursvariables et daffecter aussi plusieurs valeurs, en sparant les variables par des virgules.

class chap2_boolean {


Boolean b1=true, b2=false, b3;

b3=true;

System.out.println(b1);



}

}

Il n est pas possible en Java de convertir directement un boolen en entier et vice versa.

4. Affectation

a. Affectation de valeurs

Pour donner une valeur une variable, il faut passer par un processus d affectation laide dun oprateur. Enpseudo-code, on utilise le symbole daffectation . gauche de ce symbole, vous placez le nom de la variable, droite la valeur. Vous trouverez aussi dans certaines reprsentations algorithmiques le := issu du Pascal. Les deuxsont quivalents et utilisables (mais vitez de les mlanger, pour s y retrouver).

Voici quelques exemples daffectations en pseudo-code.

PROGRAMME AFFECTATION

VAR

a:entier

b,c:rels

titre:chane

vrai:boolen

DEBUT

a10b3,1415927c12345titre"ma premire affectation"vraiTRUE

FIN

Vous avez videmment rencontr dans les programmes Java prcdents comment affecter une valeur une variable.Cest le signe "=" qui est utilis. L emploi du signe "=" en pseudo-code na pas la mme signification, ce que vousverrez un peu plus loin dans les oprateurs de comparaison.

Attention cependant ne pas vous tromper entre le type de la variable et la valeur que vous lui affectez. C est unecause derreur frquente, tant en pseudo-code algorithmique que dans un vrai langage. Dans certains cas a pourramarcher (dans le sens o l ordinateur ne retournera pas forcment une erreur) mais le rsultat ne sera pas celuiattendu. Considrez lexemple, pas correct, suivant :

PROGRAMME AFFECT2VAR

a:entier

Dans le programme



29/221

b:relc:chane

DEBUTb3,1415927a3,1415927c12345

FIN

Lexcution de ce pseudo-code provoque quelques surprises, et des erreurs. Tout dabord b reoit la valeur de PI, etcomme b est dclar en rel (pour lexemple, le type classique Numrique n aurait pas t pertinent), cest correct.Puis a reoit la mme chose. Or a est un entier ! Suivant les langages de programmation, vous obtiendrez soit uneerreur, soit a fonctionnera, mais pas parfaitement. La variable a tant un entier, il se peut que a ne contienne que la

valeur entire de b, soit 3. Notez que certains langages autorisent une conversion explicite d un type vers un autre.On parle de transtypage. Quant la variable c, elle doit contenir une chane de caractres, dlimite par desguillemets, absents ici, ce qui provoquerait probablement une erreur.

Le code Java suivant ne fonctionne pas. Sauriez-vous deviner maintenant pourquoi ?

class chap2_equal1 {public static void main(String[] args) {

int i_a;double f_a;f_a=3.1415927;i_a=3.1415927;System.out.println(f_a);System.out.println(i_a);

}}

Voici la rponse donne par le compilateur javac :

chap2_equal1.java:7: possible loss of precisionfound : doublerequired: int

i_a=3.1415927;^

1 error

Le transtypage en Java consiste indiquer entre parenthses avant la valeur affecter le type final de celle-ci. Lavaleur sera convertie, si possible, dans ce type avant d tre affecte. Java ne permet pas de faire n importe quoi et letranstypage doit suivre une certaine logique (du genre, on ne peut pas convertir directement une chane de caractresen entier). De mme le transtypage, notamment vers le bas (dun type de grande taille vers une taille rduite) risquede provoquer une perte de prcision, voire mme d un grand nombre dinformations. Dans cet exemple, f_a estexplicitement convertie en entier. Java ne va donc conserver que la partie entire de f_a et i_a contiendra 3.


int i_a;double f_a;f_a=3.1415927;i_a=(int)3.1415927;System.out.println(f_a);System.out.println(i_a);

}}

Ce qui retourne :

3.14159273

Afin de ne pas vous faire taper sur les doigts par votre professeur d algorithmique, prcisez le bon type ds le dbut,et vitez les affectations douteuses.

Vous avez le droit de donner une valeur initiale ou par dfaut une variable lors de sa dclaration. Dans ce cas vousdevez utiliser loprateur daffectation lors de la dclaration.

Dans la dclaration



30/221

PROGRAMME DECLARE2VAR

a10:entierb3.5,c8.2347:relstitre"Mon titre":chane

vraiVRAI:boolenDEBUT

Afficher aFIN

Avec une valeur par dfaut, la variable dispose dj d un contenu ds son initialisation et peut tre directementutilise. Cest la mme chose en Java :

class chap4_init2 {public static void main(String[] args) {

int i=1,cpt=2,resultat=3;System.out.println(i) ;

}}

b. Affectation de variables

Le principe est exactement le mme sauf que cette fois vous ne mettez pas de valeur droite mais une autre variable,ce qui a pour effet daffecter la variable de gauche la valeur de la variable de droite.


a,b:entiersDEBUT

a10ba

FIN

L encore, vous prendrez bien soin de ne pas mlanger les torchons et les serviettes en n affectant pas des variablesde types incompatibles. Lexemple suivant est videmment faux.


a:entierb :relDEBUTb3.1415927ab

FIN

L encore, noubliez pas une ventuelle conversion dans un vrai langage et de dclarer correctement vos variablesdans le bon type. Lexemple Java suivant ne devrait pas vous poser de problmes de comprhension.


int a=10,b,c;double r1=3.1415927, r2;String txt1="Hello World", txt2;

b=a;r2=r1;c=(int)r2;txt2=txt1;System.out.println(r2);System.out.println(c);System.out.println(txt2);

}}

Note : on ne peut pas affecter de variable une autre variable lors de sa dclaration.



31/221

5. Saisie et affichage

Pour simuler laffichage dun texte ou dune valeur sur lcran, il faut utiliser la pseudo-instruction "Afficher" qui prend sa suite une chane de texte ou une variable. Si vous mlangez du texte et des variables, sparez ceux-ci par desvirgules. laffichage, les virgules seront remplaces par des espaces.

PROGRAMME AFFICHEVAR

a:entiertexte:chane

DEBUTa10texte"Hello World"Afficher aAfficher texteAfficher "Bonjour les amis"

FIN

Pour inviter un utilisateur rentrer au clavier une valeur utilisez le mot Saisir. L algorithme attendra alors une entre auclavier qui sera valide avec la touche dentre. La valeur que vous saisissez sera place dans la variable indique lasuite de "Saisir".

PROGRAMME SAISIEVAR

reponse:chaneDEBUT

Afficher "Quel est votre nom ?"Saisir reponseAfficher "Vous vous appelez",reponse

FIN

Si vous devez saisir plusieurs valeurs placer chacune dans une variable, vous pouvez utiliser plusieurs " Saisir", maisplus simplement placez les diverses variables la suite dun unique Saisir, spares par des virgules. L utilisateur devraalors saisir plusieurs valeurs (selon le langage final : les unes la suite des autres spares par des espaces, ou enappuyant sur la touche [Entre] aprs chaque saisie).

PROGRAMME SAISIE_MULTIPLEVAR

nom,prenom:chanesDEBUT

Afficher "Quels sont vos noms et prnoms ?"Saisir nom,prenom

FIN

Vous avez dj remarqu depuis le premier chapitre qu en Java les exemples utilisent "System.out.println()" pourafficher quelque chose dans la console MS-DOS ou dans le shell Unix/MacOS. Cest une syntaxe un peu complique quitrouve sa logique dans le principe de lobjet qui sera abord dans le dernier chapitre. Java est en effet avant tout unlangage permettant de manipuler des composants graphiques (fentres, botes de dialogue, etc). Voyez ce qu il estncessaire de faire pour saisir du texte au clavier depuis la console dans lexemple suivant.

import java.io.*;class chap2_saisie {

public static void main(String[] args) {String txt;BufferedReader saisie;saisie=new BufferedReader(new InputStreamReader(System.in));try {

System.out.println("Entrez votre texte:");txt=saisie.readLine();System.out.println("Vous avez saisi :");System.out.println(txt);

}catch(Exception excp) {

System.out.println("Erreur");



32/221

}}

}

6. Les constantes

Vous pouvez dcider de donner une valeur une variable et que cette valeur ne doit pas changer : elle doit rester fixedans le temps et inaltrable, pour toute la dure du programme. Sa valeur doit rester constante. Do son nom.

Une constante est une valeur, reprsente tout comme une variable par une valeur, qui ne peut pas tre modifieaprs son initialisation. Elle est immuable. Un exemple de constante pourrait tre la valeur de PI.

Une constante se dclare gnralement avant les variables sous le mot -cl CONST. Elle est aussi d un type donn.Certains langages de programmation passent parfois outre du type de la constante.

PROGRAMME CONSTANTECONST

PI3.1415927:relVAR

R5:entierAire:rel

DEBUTAire2*PI*RAfficher Aire

FIN

Une constante sutilise exactement comme une variable, sauf quelle ne peut pas recevoir de valeur. En java, uneconstante est aussi appele variable finale, dans le sens o elle ne peut plus tre modifie. Elle est dclare avec lemot-cl "final".

class chap2_cercle2 {public static void main(String[] args) {

final double PI=3.1415926;double r,surface,perimetre;r=5.2

Documents

Algorithmique Techniques Fond Amen Tales de Program Mat Ion com