Base Programmation

Lesbasesde la programmation et del’algorithmique

Ecolepolytechnique

RobertCori Jean-JacquesLevy FrancoisMorain

2

2

Tabledesmatieres

1 Lespremierspasen Java 91.1 Afficherdu texte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2 Fairedescalculssimples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Typesprimitifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5 Operations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.6 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Suited’instructions 152.1 Expressionsbooleennes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Operateursdecomparaisons. . . . . . . . . . . . . . . . . . . . . . . 152.1.2 Connecteurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Instructionsconditionnelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.1 If-else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.2 Formecompacte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Iterationsbouclespour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4 Iterationstantque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.5 Instructionsderupturedecontrole . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5.1 Aiguillage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Tableauxet chaınesdecaracteres 213.1 Declarationet constructiondetableaux. . . . . . . . . . . . . . . . . . . . . . 213.2 Utilisationdetableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 Tableauxaplusieursdimensions,matrices . . . . . . . . . . . . . . . . . . . . 223.4 Chaınesdecaracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.5 Argumentsdemain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Composantsd’une classe 254.1 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Constanteset variablesglobales . . . . . . . . . . . . . . . . . . . . . . . . . 264.3 Lesclassespourdefinir desenregistrements. . . . . . . . . . . . . . . . . . . 264.4 Constructeurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.5 Lesmethodesstatiqueset lesautres . . . . . . . . . . . . . . . . . . . . . . . 274.6 Utiliser plusieursclasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5 Complements 295.1 Exceptions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.2 Graphisme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.1 Fonctionselementaires. . . . . . . . . . . . . . . . . . . . . . . . . . 305.2.2 Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.2.3 La classeMaclib . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.2.4 Jeudeballe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3

4 TABLE DESMATIERES

6 Principesde basedessystemesUnix 356.1 Survol du systeme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356.2 Le systemedefichiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366.3 Lesprocessus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6.3.1 Commenttraquerlesprocessus . . . . . . . . . . . . . . . . . . . . . 376.3.2 Fabricationetgestion. . . . . . . . . . . . . . . . . . . . . . . . . . . 396.3.3 L’ordonnancementdestaches . . . . . . . . . . . . . . . . . . . . . . 416.3.4 La gestionmemoire. . . . . . . . . . . . . . . . . . . . . . . . . . . . 426.3.5 Le mysteredudemarrage. . . . . . . . . . . . . . . . . . . . . . . . . 42

6.4 Gestiondesflux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7 Retrouver l’inf ormation 457.1 Complexite desalgorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.2 Rechercheentable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7.2.1 La recherchesequentielle. . . . . . . . . . . . . . . . . . . . . . . . . 467.2.2 La recherchedichotomique. . . . . . . . . . . . . . . . . . . . . . . . 477.2.3 Insertiondansunetable . . . . . . . . . . . . . . . . . . . . . . . . . 487.2.4 Hachage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8 Recursivit e 558.1 Fonctionsrecursives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

8.1.1 Fonctionsnumeriques . . . . . . . . . . . . . . . . . . . . . . . . . . 558.1.2 La fonctiond’Ackermann . . . . . . . . . . . . . . . . . . . . . . . . 578.1.3 Recursionimbriquee . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

8.2 Indecidabilite dela terminaison. . . . . . . . . . . . . . . . . . . . . . . . . . 588.3 Proceduresrecursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608.4 Fractales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

9 Tris sequentielset r ecursifs 659.1 Qu’est-cequ’un tri ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659.2 Methodesdetri elementaires. . . . . . . . . . . . . . . . . . . . . . . . . . . 659.3 Analyseenmoyenne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699.4 Le tri parinsertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 709.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729.6 Le tri parfusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

10 Structur esdedonneeselementaires 7710.1 Listeschaınees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7710.2 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8210.3 Piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8610.4 Evaluationdesexpressionsarithmetiquesprefixees . . . . . . . . . . . . . . . 8810.5 Operationscourantessurleslistes . . . . . . . . . . . . . . . . . . . . . . . . 90

11 Arbr es 9511.1 Filesdepriorite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9611.2 Borneinferieuresurle tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10011.3 Implementationd’un arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10111.4 Arbresderecherche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10411.5 Arbresequilibres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

TABLE DESMATIERES 5

A Demarrer avecUnix 111A.1 Cequedoit savoir l’utilisateur . . . . . . . . . . . . . . . . . . . . . . . . . . 111

A.1.1 Pasdepanique! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111A.1.2 Demarraged’unesession. . . . . . . . . . . . . . . . . . . . . . . . . 111A.1.3 Systemedefichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111A.1.4 Commentobtenirdel’aide . . . . . . . . . . . . . . . . . . . . . . . . 114A.1.5 Raccourcispourlesnomsdefichiers. . . . . . . . . . . . . . . . . . . 114A.1.6 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114A.1.7 Le chemind’accesauxcommandes. . . . . . . . . . . . . . . . . . . 115

A.2 Le reseaudel’X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115A.3 Un peudesecurite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

A.3.1 Motsdepasse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116A.3.2 Accesadistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

B Utilisation avanceedu SHELL 119B.1 Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

B.1.1 Quotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119B.1.2 Redirectionsetfiltres . . . . . . . . . . . . . . . . . . . . . . . . . . . 120B.1.3 Processus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

B.2 Programmation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122B.2.1 Structuresdecontrole . . . . . . . . . . . . . . . . . . . . . . . . . . 122B.2.2 Codederetour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123B.2.3 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123B.2.4 Commandesinternes . . . . . . . . . . . . . . . . . . . . . . . . . . . 123B.2.5 Fichierdedemarrage. . . . . . . . . . . . . . . . . . . . . . . . . . . 123

B.3 BibliographieUnix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

C SyntaxeBNF de Java 125C.1 Contanteslitt erales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125C.2 Types,valeurs,et variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125C.3 Noms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126C.4 Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126C.5 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

C.5.1 Declarationdeclasse. . . . . . . . . . . . . . . . . . . . . . . . . . . 127C.5.2 Declarationsdechamps . . . . . . . . . . . . . . . . . . . . . . . . . 127C.5.3 Declarationsdemethodes . . . . . . . . . . . . . . . . . . . . . . . . 128C.5.4 Initialieursstatiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 128C.5.5 Declarationsdeconstructeurs . . . . . . . . . . . . . . . . . . . . . . 128

C.6 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129C.7 Tableaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129C.8 Blocset instructions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129C.9 Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Bibliographie 136

Tabledesfigures 143

6 TABLE DESMATIERES

Intr oduction

Cepolycopie estutilise pourdeuxenseignementsqui ontdesbutsdifferentsmaiscomple-mentaires.

Le premier, introductiona l’informatiques’adressea deselevesdepremiereanneeayantpeuoupasdeconnaissanceseninformatique.Unepartiedececoursconsisteenuneintroduc-tion generalea l’informatique,aux logiciels,materiels,environnementsinformatiqueset a lasciencesous-jacente.

Uneautrepartieconsistea etablir lesbasesdela programmationet del’algorithmique,enetudiantun langage.On introduit desstructuresdedonneessimples: scalaires,chaınesdeca-racteres,tableaux,etdesstructuresdecontroleselementairescommel’it eration,la recursivite.

Nousavonschoisi Java pour cetteintroductiona la programmationcar c’est un langagetype assezrepanduqui permetdes’initier auxdiversesconstructionspresentesdansla plupartdeslangagesdeprogrammationmodernes.

Le second,Lesbasesde la programmationet de l’algorithmique s’adressea deselevesde premiereanneeayantdeja desconnaissancesen informatique.Une partiedu programmereprendlespointsprecedents,ensuitela partieprogrammationet algorithmiqueestcompleteeparl’ etudedestructuresdedonneespluscomplexes: listesetarbres.

A cescourssontcouples desseancesde travaux diriges et pratiquesqui sontbeaucoupplusqu’un complementaucours,puisquec’estenecrivantdesprogrammesquel’on apprendl’informatique.

Remerciements

NousremercionsSergeAbiteboul,Francois Anceau,JeanBerstel,Thierry Besançon,JeanBetrema,Francois Bourdoncle,Philippe Chassignet,Georges Gonthier, Florent Guillaume,Martin Jourdan,Francois Morain, Dominique Perrin, Jean-EricPin, Nicolas Pioch, BrunoSalvy, Michel WeinfeldR,Paul Zimmermannpour avoir relu avec attentionce cours,MichelMauny et Didier Remypour leursmacrosTEX, Ravi Sethipournousavoir donne lessourcespic desdessinsde seslivres[3, 48], Martin Jourdanpour avoir fourni cessources,DamienDoligezpoursestalentsdemetteuraupoint, pour lesdessins,lesscriptsenPerlet sagrandeconnaissanceduMacintosh,XavierLeroy poursesmagnifiquesshell-scripts, BrunoSalvypoursagrandeconnaissancedeMaple,PaulZimmermannpoursarigueur, PhilippeChassignetpoursonexpertiseengraphiqueMacintosh. . . ettousceuxquenousavonsoubliesinvolontairement.

NousdevonsspecialementmentionnerDamienDoligez et Xavier Leroy, auteursdesan-nexessurUnix.

BrunoBlanchet,FrancoisBourdoncle,PhilippeChassignet,etGeorgesGonthierontegalementcontribue a l’adaptationdupolycopie aulangageJava.

NousremercionsenfinDominiqueRossinpourledessindecouverture,PhilippeChassignetet PierrickGaudrypourleur relecturesoignee.

7

8 TABLE DESMATIERES

Le polycopie a ete traduit en html a l’aide du traducteurHevea,de Luc Maranget.Lepolycopie estconsultablea l’adresse:

http ://www.enseignement.polytechnique.fr/i nform atiqu e/Les erreursserontcorrigeesdesqu’ellesnousserontsignaleeset les misesa jour seront

effectueessurla versionhtml.

Polycopie,version1.0

Chapitr e 1

Les premierspasenJava

Danscechapitreondonnequelqueselementssimplesdela programmationavecle langageJava. Toutefoisles notionsde types,variables,affectations,fonctionsseretrouvent danstousleslangagesdeprogrammation.

1.1 Afficher du texte

Commençonspar un exemplesimplede programme.C’est un classique,il s’agit simple-mentd’afficherBonjour ! a l’ ecran.

// Voici mon premier programme

class Premier{

public static void main (String args[]){

System.out.print ln (" Bonjo ur !" );}

}

Pourexecuterceprogrammeil fautcommencerparl’ editer, pourcelaon utiliseun editeurdetexte (parexempleemacs)pourcreerun fichier qui a un nomseterminantpar .java parexemplePremier.java . Cefichier doit contenirle texte du programme.Apresavoir tapele texte,on le compileparla commande

unix% javac Premier.java

Ceci a pour effet de faire construirepar le compilateurun fichier Premier.class .Enfin, le programmejava permetd’executerle fichier Premier.class . Voila ce queceladonne:

unix% java Premier

On voit s’afficher:

Bonjour!

On achoisi le memenomici pourle nomdu fichieret pourle nomdela classedecriteparle fichier, cen’estpassystematiquementobligatoire,maisvivementconseille.

Analysonsle texte de ce premierprogramme,il contientd’abordun commentaireentreles deuxsymboles /* et */ . On peutaussimettredescommentairesde fin de ligne quicommencentapresunsymbole// etseterminentala fin dela ligne; cesdiverscommentaires

9

10 CHAPITRE1. LESPREMIERSPAS EN JAVA

nesontutilesqu’a deslecteurs(humains)du texte du programme,ils n’aurontaucuneffet surla compilationou l’execution.

Dansceprogramme,il y a uneseuleclassePremier , et uneseulefonction(on dit aussimethodelorsqu’il estquestiond’un langageavec desobjetscommeJava) danscetteclasse;cette fonction a pour nom main , elle affiche la chaıne de caracteresBonjour ! qui estdonneesousforme d’un parametre litt eral a la fonction println . Cettederniere fonctionestattacheea l’objet out dela classeSystem dela bibliotheque(d’ou la facon del’invoquerparSystem.out.prin tl n ).

Dans un premier tempson peut considerer qu’une classesert a regrouperun certainsnombresdefonctions.Cettefacon deprocederdonneunegestionmodulairedesprogrammesquel’on ecrit.

Dansnotrecas,la classene contientqu’uneseulefonctionqui a pour nom main , toutesles classesque l’on va construirecontiendrontune fonction ayantce nom. C’est en effet lafonctionqui estexecuteelorsquel’on effectuela commandejava Nom_de_Classe .

Lesaccolades�

et � servent a constituerun bloc d’instructions; ellesdoiventengloberlesinstructionsd’une fonction,de memequ’unepaired’accoladesdoit engloberl’ensembledesfonctionsd’uneclasse.

Noter qu’enJava les instructionsseterminenttoutesparun; (point-virgule). Ainsi, dansla suitele symboleI signifierasoit uneinstruction(qui seterminedoncpar; ) soit unesuited’instructions(chacunefinissantpar; ) le toutentreaccolades.

1.2 Fairedescalculssimples

On peut se servir de Java pour realiserles operationsd’une calculetteelementaire: onaffectela valeurd’uneexpressionaunevariableetondemandeensuitel’affichagedela valeurdela variableenquestion.

Bien entendu,un langagede programmationn’est pasvraimentfait pour cela, toutefoiscelanousdonnequelquesexemplesde programmessimples; nouspasseronsplus tard a desprogrammespluscomplexes.

/* Voici mon deuxieme programme */

public class PremierCalcul {

public static void main (String args[]){int a;a = 10 + 5 * 3;System.out.print ln (a );a = 287 % 7;System.out.print ln (a );

}}

Dansceprogrammeon voit apparaıtre unevariabledont le nomesta qui estdeclareeaudebut. Commeles valeursqu’elle prendsont desentierselle est dite de type entier, le motint avantsonnomindiquecetype.Par la suiteelleestaffecteedeuxfois d’unevaleurqui estensuiteaffichee.Lesresultatsaffichesseront25et0. Eneffet dansla premiereformulela regledepriorite desoperationsestappliqueeet la priorite de* etantplusgrandequecellede+, c’estcetteoperationqui esteffectueeenpremier. Dansla secondeoperationle symbole%dansa %b designel’operation �� qui estle restedela divisionde � par .

1.3. TYPESPRIMITIFS 11

1.3 Typesprimitifs

Un typeenprogrammationprecisel’ensembledesvaleursquepeutprendreunevariable;lesoperationsquel’on peuteffectuersurunevariabledependentdesontype.

Le typedesvariablesquel’on utilisedansun programmedoiventtousetredeclares.Parmiles typespossibles,lesplussimplessontles typesprimitifs. Il y a peudetypesprimitifs : lesentiers,lesreels,lescaractereset lesbooleens.

Lesprincipauxtypesentierssontint et long , le premierutilise 32 bits pourrepresenterunnombre; sachantquele premierbit estreserve ausigneceladonneunmaximumde ��pour la valeurd’un entierdeclare en int , si un nombredepassecettevaleurle resulatobtenun’estpasutilisable.Le typelong permetd’avoir desmotsde64bitsetonpeutdonctravaillersur desentiersplus grands.Il y a aussiles typesbyte et short qui permetted’utiliser desmotsde8 et 16 bits.Lesoperationssur les int sonttouteslesoperationsarithmetiquesclas-siques: addition,soustraction,multiplication,divison,reste,et lesoperationsdecomparaison:egal,differentde,pluspetit,plusgrand.

Lestypesreels(enfait nombredecimaux)sontfloat etdouble , le premiersecontented’uneprecisiondite simple,le seconddonnela possibilite d’uneplusgrandeprecision,on ditquel’on aunedoubleprecision.

Les caracteressontdeclarespar le type char ils correspondentau standardUnicode,ilssontcodessur16 bits et permettentd’atteindretoutesles languesde la planete(lescaractereshabituelsdesclaviersdeslangueseuropeennessecodentuniquementsur8 bits).On peutfairedescomparaisonssur les caracterespour determinerlequel vient avant l’autre dansl’ordrealphabetique.

Le typedesbooleensestboolean et lesdeuxvaleurspossiblessonttrue et false . Lesoperationssontet, ou, etnon ; ellessenotentrespectivement&&, ||, ! . Si a etb sontdeuxbooleens,le resultatde a && b est true si et seulementsi a et b sont tousdeuxegauxatrue . Celui dea || b esttrue si et seulementsi l’un dea et b estegala true . Enfin!aesttrue quanda estfalse etreciproquement.Lesbooleenssontutilisesdanslesconditionsquel’on verraauchapitresuivant.

La declarationdu typedesvariablesestobligatoireenJava, elle peutsefaire a l’int erieurd’unefonctionetpasnecessairementaudebut. Unedeclarationsepresentesousla formed’unnomdetypesuivi soit d’un nomdevariablesoit d’unesuitedenomsdevariablesseparespardesvirgules.En voici quelquesexemples:

int a, b, c;float x;char ch;boolean u,v;

1.4 Affectation

On a vu qu’unevariablea un nomet qu’elle estdeclareed’un certaintype.L’operationlapluscourantesurlesvariablesestl’affectationd’unevaleurelles’ecrit :

x = E;

ou Eestuneexpressionqui peutcontenirdesconstantesetdesvariables.Lorsd’uneaffectation,l’expressionE estevalueeet le resultatde sonevaluationestaffecte a la variablex . Lorsquel’expressionE contientdesvariablesleur evaluationestegalea la dernierevaleurqui leura eteaffectee.

Un exempled’affectationestle suivant:

x = x + a;


double

float

long

int char

short

byte

celaconsisteaaugmenterla valeurdex dela quantitea. Unevariablei detypeentierpeutetreincrementeeparl’operationi++ , cecia exactementle memeeffet quei = i + 1. On peututiliser auseind’uneexpressionl’operateurunaire++, on fait alorsa la fois uneevaluationdela valeuret une(postou pre)-incrementationde la variable.Cecin’est pasrecommande saufdansdescastresparticuliersdeparcoursde tableaux.La decrementationsefait par i-- , quiestequivalentea i = i - 1.

Pouruneaffectation

x = E;

le type de l’expressionE et celui de la variablex doivent etreles memes.Dansun trespetitnombredecascetteexigencen’estpasappliquee,il s’agit alorsdesconversionsimplicitesdetypes.

Les conversionsimplicites suivent la figure ci-dessus.Pour touteoperation,on convertittoujoursau plus petit communmajorantdestypesdesoperandes.Desconversionsexplicitessontaussipossibles,et recommandeesdansle doute.On peutles fairepar l’operationdite decoercion(cast) suivante

x = (nom-type) E;

L’expressionE estalorsconvertie dansle type indique entreparenthesesdevant l’expression.L’operateur= d’affectationestun operateurcommeles autresdansles expressions.Il subitdonclesmemeslois deconversion.Toutefois,il sedistinguedesautresoperationspar le typedu resultat.Pour un operateurordinaire,le type du resultatest le type communobtenuparconversiondesdeuxoperandes.Pouruneaffectation,le typeduresultatestle typedel’expres-sion a gauchede l’affectation.Il faut doncfaire uneconversionexplicite sur l’expressiondedroitepourquele resultatsoit coherentavecle typedel’expressiondegauche.

1.5 Operations

La plupartdesoperationsarithmetiquescourantessontdisponiblesen Java, ainsi quelesoperationssur les booleens(voir chapitresuivant). Cesoperationsont un ordre de prioritecorrespondantauxconventionsusuelles.

Lesprincipalesoperationssont+,-,*,/, % pour l’addition, soustraction,multiplica-tion, division et le restedela division (modulo).Il y a desreglesdepriorite, ainsi l’operationde multiplication a une plus grandepriorite que l’addition, cela signifie que les multiplica-tionssontfaitesavant lesadditions.La presencedeparenthesespermetdemieuxcontroler leresultat.Par exemple3 + 5 * 6 estevalue a 33; parcontre(3 + 5) * 6 estevalue 48.

1.6. FONCTIONS 13

Uneexpressiona toujoursun typeet le resultatdesonevaluationestunevaleurayantcetype.L’ evaluationde2/0 souleve l’exception(voir plusloin) ArithmeticExce pt io n.

Remarque Le symbole+ designeaussila concatenation(misebout a bout)dedeuxchaınesde caracteres,le contexte permetde determiners’il s’agit de l’addition de deuxnombresoude la concatenation.On dit qu’il y a surcharge de l’operation+. Par exemplelorsqu’onecritl’instruction :

System.out.prin tln (" Vous nous devez " + a + " francs " );

On demandel’impressionde la chaıne de caracteresVous nous devez a laquelleestconcatenee la chaıne representantle nombrea et la chaıne " francs " . Remarquerquedanscetteecriturele nombrea estconverti enunechaınedecaracteresdefacon implicite.

1.6 Fonctions

Unefonctionestunepartiedeprogrammesitueea l’int erieurd’uneclassedont la donneeestconstituee de certainsparametreset qui fournit un resultat.Danscertainscasla fonctionagit uniquementpareffet debord,parexemplelorsqu’ellemodifiecertainesvariablesglobalesou lorsqu’elle ne fait qu’afficher desvaleurs.On indique alors que son resultatest de typevoid , ainsila fonctionmain esttoujoursdetypevoid . Il y aaussidescasou il n’y apasdeparametreslorsquela fonctioneffectuetoujourslesmemesoperationssurlesmemesvaleurs.

L’enteted’unefonctiondecrit le typedu resultatd’abordpuislestypesdesparametresquifigurententreparantheses.

Les programmesque l’on a vu ci-dessuscontiennentuneseulefonction appelee main .Lorsqu’oneffectuela commandejava Nom-classe , c’est la fonction main se trouvantdanscetteclassequi estexecuteeenpremier.

Unefonctionpeutetreappeleeparuneautrefonction,il fautalorsdonnerdesvaleursauxparametresd’appel.

Un exemplesimpledefonctionestle calculdela circonferenced’un cercle:

/* Calcul de circonf erence */

public class Cercle {static float pi = (float) Math.PI;

public static float circonference (float r) {return 2. * pi* r;}

public static void main (String args[]){float c = circonference (1.5);System.out.print ln (" Ci rco nf er ence : " + c);}

}

Ce programmecontientdeuxfonctionsdansunememeclasse,la premierefonctiona unparametrer etutilise la constantePI qui setrouve dansla classeMath , cetteconstanteestdetypedouble il fautdoncla convertir autype float pouraffectersavaleura un nombredecetype.Le resultatestfournit, on dit plutot retourne a l’appelantparreturn . L’appelantestici la fonctionmain qui apresavoir effectue l’appel,affichele resultat.


Chapitr e 2

Suited’instructions

Danscechapitreons’interesseauxinstructionsconditionnelles,qui permettentd’effectueruneoperationdansle casou unecertaineconditionestsatisfaiteet aux iterationsqui donnentla possibilite de repeter plusieursfois la memeinstruction(pour desvaleursdifferentesdesvariables!).

2.1 Expressionsbooleennes

Le point communaux diversesinstructionsque l’on va decrireestqu’ellesutilisent desexpressionsdont l’ evaluationdonnel’une desdeuxvaleurstrue ou false . On dit quecesontdesexpressionsbooleennesouparfoisdesexpressionslogiques.

2.1.1 Operateursde comparaisons

Lesoperateursbooleenslesplussimplessont

== != < > <= >=

Le resultatd’unecomparaisonsurdesvariablesdetypeprimitif :

a == b

estegala true si l’ evaluationdela variablea et dela variableb donnentle memeresultat,ilestegala false sinon.

Remarque Attentiona nepasecrirea = 0 qui estuneaffectationetpasunecomparaison.

L’operateur!= estl’oppose de==, ainsia != b prendla valeur true si l’ evaluationdea etdeb donnedesvaleursdifferentes.

Lesoperateursdecomparaison<, >, <=, >= ontdessignificationsevidenteslorsqu’il s’agitdecompararerdesnombres.Noterqu’ils peuventaussiservir a comparerdescaracteres; pourlescaractereslatinscourantsc’estl’ordre alphabetiquequi estexprime.

2.1.2 Connecteurs

On peutconstruiredesexpressionsbooleennescomportantplusieurscomparateursenuti-lisantlesconnecteurs&&, qui signifieet, || qui signifieou et! qui signifienon.

Ainsi C1 && C2 estevalue a true si et seulementsi les deuxexpressionsC1 et C2 lesont.De memeC1 || C2 estevalue a true si l’une deuxexpressionsC1 ou C2 l’est.

Parexemple

!( ((a<c) && (c<b) && (b<d)) || ((c<a) && (a<d) && (d<b)) )

15

16 CHAPITRE2. SUITE D’INSTRUCTIONS

estunefacon de testerqueles deuxintervalles � �� et � �� sontdisjointsou contenusl’undansl’autre.

Remarque En Java l’ evaluationde l’expressionC1 && C2 s’effectuedansl’ordre C1 puisC2 si necessaire; ainsisi C1 estevalueea false alorsC2 n’estpasevaluee.C’estaussilecaspourC1 || C2 qui estevalueea true si c’est le caspourC1 et ceci sansqueC2 nesoit evaluee.Parexemplel’ evaluationdel’expression

(3 > 4) && (2/0 > 0)

donnepourresultatfalse alorsque

(2/0 > 0) && (3 > 4)

donnelieu auneerreur(exception).

2.2 Instructions conditionnelles

Il s’agitd’instructionspermettantden’effectueruneoperationquesi unecertaineconditionestsatisfaite.

2.2.1 If-else

La plussimpledecesinstructionsestcelledela forme:

if(C) I1 else I2

DanscetteecritureC estuneexpressionbooleenne(attentiona nepasoublier lesparenthesesautour); I1 et I2 sontformeesoubienuneseuleinstructionoubienunesuited’instructionsal’int erieurd’unepaired’accolades

� � . OnrappellequechaqueinstructiondeJavaseterminepar; (symbolequi fait doncpartiedel’instruction).

La partieelse I2 estfacultative,elleestomisesi la suiteI2 estvidec’estadires’il n’yaaucuneinstructionaexecuterdansle casou Cestevalueea false .

On peutavoir plusieursbranchessepareespardeselse if commeparexempledans:

if (a == 0 ) x = 1;else if (a < 0) x = 2;else if (a > -5) x = 3;else x = 4;

qui donne4 valeurspossiblespourx suivant lesvaleursdea.

2.2.2 Forme compacte

Il existeuneformecompactede l’instruction conditionnelleutiliseecommeun operateurternaire(a trois operandes)dont le premierest un booleenet les deux autressont de typeprimitif. Cet operateurs’ecrit C? E1 : E2. Elle est utilisee quandun if else paraıtlourd,parexemplepourle calculd’unevaleurabsolue:

x = (a > b)? a - b : b - a;

2.3 It erationsbouclespour

Uneiterationpermetderepeterplusieursfois la memesuited’instructions.Elle estutiliseepour evaluer une somme,une suite recurrente,le calcul d’un plus grandcommundiviseurparexemple.Elle sertaussipoureffectuerdestraitementsplusinformatiquescommela lectured’un fichier. Onal’habitudededistinguerlesbouclespourdesbouclestant-que. Lespremieres

2.4. ITERATIONSTANT QUE 17

sont utilisees lors qu’on connaıt, lors de l’ ecrituredu programme,le nombrede fois ou lesoperationsdoiventetreiterees,lessecondesserventa exprimerdestestsd’arret dontle resultatn’est pasprevisiblea l’avance.Par exemplele calcul d’une sommede valeurspour � variantde1 a � estdela categorieboucle-pourcelui du calculd’un plusgrandcommundiviseurparl’algorithmed’Euclidereleve d’uneboucletant-que.

L’it erationde type boucle-pouren Java a la meme forme qu’en langageC, forme quiderouteceuxqui la decouvrentpourla premierefois. Elle s’exprimepar:

for (Init; C ; Inc) I

DanscetteecritureInit estuneinitialisation(pouvant comporterunedeclaration),Incestune incrementation,et C un testd’arret, ce sontdesexpressionsqui ne seterminentpasparunpoint virgule.Quanta I , c’estle corpsdela boucleconstitue d’uneseuleinstructionoud’unesuited’instructionsentreaccolades.Init estexecuteeenpremier, ensuitela conditionC estevalueesi savaleuresttrue alorsla suited’instructionsI estexecuteesuivie de l’ins-truction d’incrementationInc et un nouveautour de bouclereprendavec l’ evaluationde C.NoterqueInit peutetrecomposeed’uneseuleexpressionou biendeplusieurs,separeespardes, (virgules).L’exemplele pluscourantestceluiou on executeunesuited’operationspouri variantde1 an, commedans:

int i;for(i = 1; i <= n; ++i)

System.out.println(i);

Uneformeencorepluscouranteestcelleou on declarei dansla boucle:

for(int i = 1; i <= n; ++i)System.out.println(i);

On n’a pasaccesa la variablei endehorsdu corpsdela boucle.Un autreexempleestle calculdela somme !"$# � � �

qui sefait par

float s = 0.;for(int i = 1; i <= n; ++i) s = s + 1/i;

NoterquelesinstructionsInit ou Inc dela formegenerale(oumemelesdeux)peuventetrevides.Il n’y aalorspasd’initialisation ou pasd’incrementation; l’initialisation peut,danscecas,figureravant le for et l’incrementationa l’int erieurdeI .

2.4 It erations tant que

Unetelle instructiona la formesuivante:

while (C) I

ou C estuneconditionet I uneinstructionou un bloc d’instructions.L’it erationevalueC etexecuteI si le resultatest true , cettesuiteestrepetee tant quel’ evaluationde C donnelavaleurtrue .

Un exempleclassiquedel’utilisation dewhile estle calculdupgcddedeuxnombresparl’algorithme d’Euclide.Cet algorithmeconsistea remplacerle calcul de %'&(�)�+*��+�� -, par celuide %'&(�)�*. /�102, ou 0 estle restedela division de � par etcecitantque 043576 .


while (b != 0) {r = a % b;a = b; b = r;

}

2.5 Instructions de ruptur e de controle

Il y a trois telles instructionsqui sont return, break et continue . L’instructionreturn doit etreutiliseedanstoutesles fonctionsqui calculentun resultat.L’effet de cetteinstructionestdefournir (ondit souventretourner)unevaleura l’appelant,on l’a utiliseedansla fonctiondecalculdecirconferenceduchapitrepremier. Elle s’ecrit :

return Exp;

ou Exp estuneexpressionqui evalueeavant la terminaisonde l’executionde la fonction etfourniea la proedurequi a fait appela cettefonction.

Lesdeuxautresinstructionsderupturesontbeaucoupmoinsutiliseesetpeuventetreomisesen premierelecture.L’instructionbreak permetd’interrompreunesuited’instructionsdansunebouclepourpassera l’instructionqui suit la boucledansle texte du programme.

Si plusieursbouclessontimbriqueeset quel’on souhaitesortir dediversesfaconsdecetteimbrication,il fautalorsutiliser desetiquetteseffectuerdesoperationsdebreak etiquetees.Ainsi un break etiq fait sortir de la boucleprecedee de l’ etiquetteetiq . L’instructioncontinue a un effet similaire a celui de break , mais redonnele controle a l’it erationsuivantedela boucleaulieu d’ensortir. Onpeutaussiutilisercontinue suivi d’uneetiquettedeboucle.

Il n’estengeneralpasrecommanded’utiliser lesinstructionsavecetiquettes,qui dansbeau-coup de casnuisenta la lisibilit e desprogrammes.Pourtantdanscertainessituationsparti-culieresellesserevelentutiles.

2.5.1 Aiguillage

Quanddiversesinstructionssonta realisersuivant lesvaleursqueprendunevariable,plu-sieursif imbriquesdeviennentlourdsa mettreenoeuvre,on peutlesremplaceravantageuse-mentparun aiguillageswitch . Un tel aiguillagea la formesuivantedanslaquellex estunevariableeta,b,c sontdesconstantesrepresentantdesvaleursquepeutprendrecettevariable.Lors del’executionlesvaleursapreschaquecase sonttesteesl’une apresl’autre jusqu’a ob-tenir cellepriseparx ou arriver a default , ensuitetoutesles instructionssontexecuteesensequencejusqu’a la fin. Parexempledansl’instruction :

switch (x) {case a : I1case b : I2case c : I3default : I4}

Si la variablex estevalueea b alorstouteslessuitesd’instructionsI2, I3, I4 serontexecutees,a moinsquel’une d’entreellesnecontienneun break qui interromptcettesuite.Si la variableestevalueeaunevaleurdifferentedea,b,c c’estla suiteI4 qui estexecutee.

En effet poursortir de l’instruction avant la fin, il fautpasserparuneinstructionbreak .Sinon,le restedel’instructionestexecute ensequence.Cecipeutetreparticulierementdange-reux.Parexemple,le programmesuivant

switch (c) {case ’\t’:case ’ ’:

2.5. INSTRUCTIONSDE RUPTUREDE CONTROLE 19

++ nEspaces;break;

case ’0’: case ’1’: case ’2’: case ’3’: case ’4’:case ’5’: case ’6’: case ’7’: case ’8’: case ’9’:

++ nChiffres;break;

default:++ nAutres;break;

}

permetdefactoriserle traitementdequelquescas.Il faudrabienfaireattentionanepasoublierle break a la fin de chaquecas,et a ce que break ne soit pas intercepte par une autreinstruction.


Chapitr e 3

Tableauxet chaınesdecaracteres

Jusqu’ici la plupartdesconstructionspresenteespour Java sont les memesquecellesdulangageC. En effet lesnotionsdevariables,types,affectations,appeldefonctions,condition-nelleset bouclesfigurentdanstous les langagesde programmation,et la memenotationestutiliseeenJavaetenC. La possibilite demanipulerdestableauxseretrouveaussidanstousleslangagesde programmation; toutefoisJava, qui estun langageavec desobjets,manipulelestableauxd’unefaconparticulierequel’on va decrireici.

3.1 Declaration et construction de tableaux

L’utilisation d’un tableaupermetd’avoir asadispositionuntresgrandnombredevariablesenutilisantun seulnomet donceneffectuantuneseuledeclaration.Le principeestquesi ondeclareun tableaudenom tab et detaille n contenantdesvaleursdetype typ alorson a sadispositionles variablestab[0],tab[1], ..., tab[n-1] qui secomportentcommedesvariablesordinairesdetypetyp .

En Java on separela declarationd’unevariabledetypetableaudela constructioneffectived’un tableau.

La declarationd’unevariabledetypetableaudenomtab dontleselementssontdetypetyp , s’effectuepar:

typ[] tab;

ou demaniereequivalentepar

typ tab[];

Nous prefereronsla premiere facon de faire car elle respectela convention suivant laquelledansunedeclaration,le typed’unevariablefigurecompletementavant le nomdecelle-ci.Lasecondecorrespondacequi sefait enlangageC.

Lorsquel’on adeclare un tableauenJava on nepeutpasencorel’utiliser completement,ilesteneffet interdit parexempled’affecterunevaleurauxvariablestab[i] . Il fautcommen-cer parconstruirele tableau,pour mieux comprendrece qui sepasseon peutconsidererqueconstruiresignifiereserver dela placeenmemoire.

L’operationdeconstructions’effectueenutilisantunnew, pourun tableauceladonne:

tab = new typ[taille];

danscetteinstructiontaille estuneconstanteentiereou unevariablede type entierdontl’ evaluationdoit pouvoir etreeffectueea l’execution.Unefois qu’un tableauestcree avecunecertainetaille, celle-cinepeutplusetremodifiee.

On peutaussiregrouperla declarationet la constructionenuneseulelignepar:

typ[] tab = new typ[taille];

21

22 CHAPITRE3. TABLEAUX ET CHAINESDE CARACTERES

Pourdestableauxdepetitetaille on peutenmemetempsconstruireet initialiser un tableauetinitialiser lesvaleurscontenuesdansle tableau.

L’exemplesuivantregroupeles3 operationsdedeclaration,constructionet initialisationdevaleursenutilisantuneaffectationsuivie de

�, � :

int[] tab = {1,2,4,8,16,32,6 4, 128, 256 ,5 12,1 024};

3.2 Utilisation de tableaux

Si tab estuntableaudontleselementssontdetypetyp , onpeutalorsconsiderertab[i]commeunevariableet effectuersur celle-ci toutesles operationsadmissiblesconcernantletype typ , bien entendul’indice i doit etre inferieur a la taille du tableaudonnee lors de saconstruction.L’interpreteurJava verifie cetteconditionet uneexceptionestleveesi elle n’estpassatisfaite.

La taille d’un tableautab peuts’obtenirgraceauchamplength associe acettevariable.Parmi les operationssimplessur les tableaux,il y a la recherchedu plus petit ou du plus

grandelementqui serealiseparla fonctionsuivante:

static int pluspetit (int[] x){int k = 0, n = x.length;for (int i = 1 ; i < n; i++)

if (x[i] < x[k]) k = i;return k;

}

Uneautrefacon d’utiliser un tableauconsisteaeffectueruneaffectation,parexemple:

int[] tabnouv = tab;

Cetteaffectationa pour effet de faire que les variablestabnouv et tab designentlememetableau,enprogrammationon dit qu’ellesfont referenceaumemetableau.Il n’y a pasrecopiede toutesles valeurscontenuesdansle tableautab pour former un nouveautableaumaissimplementuneindicationdereference.Ainsi si l’on modifiela valeurdetab[i] , cellede tabnouv[i] le seraaussi.

Si on souhaiterecopierun tableaudansun autreil fautecrireunefonction:

static int[] copier (int[] x){int n = x.length;int[] y = new int[n];for (int i = 0; i < n; i++) y[i] = x[i];return y;

}

Noteraussiquel’operationdecomparaisondedeuxtableauxx == y estevalueea truedansle casou x et y referencentle memetableau(parexemplesi on a effctue l’affectationy= x ). Si onsouhaiteverifier l’ egalite descontenus,il fautuneecrireunefonctionparticuliere.

3.3 Tableauxa plusieursdimensions,matrices

Un tableauaplusieursdimensionsestconsidereenJavacommeuntableaudetableaux.Parexemple,lesmatricesqui sontdestableauxadeuxdimensionssontdeclareespar:

typ[][] tab;

Il fautaussile construireon peutle fairepar

tab = new typ[N][N];

3.4. CHAINESDE CARACTERES 23

Mais on peut aussi,commepour les tableauxa une dimension,faire uneaffectationdevaleursenuneseulefois :

int[][] tab = {{1,2,3},{4,5, 6} ,{ 7, 8,9 }} ;

3.4 Chaınesdecaracteres

Leschaınesdecaracteressemanipulentde facon particuliereenJava puisqu’ellesconsti-tuentuneclasse.Commelesclassesneserontconsidereesqu’auchapitresuivant,cequ’on vavousdire ici pourraparaıtre complique, vouspouvez toutefoisnoterl’existencedesfonctions,et les utiliser sanstrop comprendre.Une chaıne de caracteresestunesuitede symbolesquel’on peuttapersurun clavier ou lire surun ecran.La declarationd’unevariablesusceptibledecontenirunechaınedecaracteressefait par

String u;

Un point importantestquel’on nepeutpasmodifierunechaınedecaracteres,ondit qu’elleestnonmutable. On peutparcontrel’afficher, la recopier, accedera la valeurd’un descaractereset effectuerun certainnombred’operationscommela concatenation,l’obtentiond’un facteur,on peutaussiverifier l’ egalite dedeuxchaınesdecaracteres.

Voici quelquesexemples:String v = new String(u);

recopiela chaıneu dansla la chaınev .

int l = u.length();

donnela longueurde la chaıne u, Noter que length est une fonction sur les chaınesdecaracteres,et queparcontrec’estunevaleurassocieeaun tableau; ceciexpliquela differenced’ecriture: lesparenthesespourla fonctionsur leschaınesdecaracteressontabsentesdanslecasdestableaux.

char x = u.charAt(i);

donnea x la valeurdu � -emecarateredela chaıneu, noterquele premiercarat`re s’obtientparu.charAt(0) .

u.compareTo(v);

a pourresultatun nombreentiernegatifsi u precedev dansl’ordre lexicographique(celui dudictionnaire),0 si leschaınesu etv sontegaleset unnombrepositif si v precedeu.

w = u.concat(v);

construitunenouvellechaıneobtenueparconcatenationdev suivie deu. Noterquev.concat(u)estunechaınedifferentedela precedente.

3.5 Ar gumentsdemain

La proceduremain qui figuredanstout programmequel’on souhaiteexecuterpeutavoirun parametredetypetableaudechaınesdecaracteres.On declarealorsla procedurepar

public static void main (String[] args)

Pourcomprendrel’int eret de tels parametres,supposonsquela proceduremain setrouve al’int erieurd’un programmequi commenceparClass Classex .

On peutalorsutiliser lesvaleurset variablesargs.length, args[0], args[1],... a l’int erieurdela proceduremain

Celles-cicorrespondentaux chaınesde caracteresqui suivent java Classex lorsquel’utilisateurdemanded’executersonprogramme.

Parexemplesi on a ecrit uneproceduremain:

24 CHAPITRE3. TABLEAUX ET CHAINESDE CARACTERES

void main (String[] args){for (int i = args.length -1; i > = 0 ; i--)

System.out.pri nt( ar gs [i ] + " ");System.out.pri ntl n( );}

et qu’unefois celle-cicompileeon demandel’executionpar

java Classex marquise d\’amour me faites mourrir

on obtientcommeresultat

mourrir faites me d’amour marquise

Noterquel’on peuttransformerunechaınedecaracteresu composeedechiffresdecimauxenunentierparla fonction Integer.parseIn t( ) commedansle programmesuivant:

class Additionner {

public static void main (String args[]) {if (args.length != 2)

System.out.print ln (" mauva is nombre d’arguments");else {

int s= Integer.parseIn t(a rg s[ 0] )+Integer.parse In t(a rg s[ 1] );

System.out.print ln (s);}}

}

On peutalorsdemander

java Additionner 1047 953

l’interpreteurrepond:

2000

Chapitr e 4

Composantsd’une classe

Ce chapitreestconsacre a l’organisationgeneraled’un programmeen Java, car jusqu’icinousnoussommesplutot interessesauxdifferentesinstructionsdebase.

On peutconsidererdansun premiertempslesclassescommeun moyenderegrouperplu-sieursfonctionsqui ont trait aun sujetcommun.Parexempleonpeutconstitueruneclassequicontientdesfonctionssurlespointsetdroitesduplan,uneautrepourmanipulerdessegments,unetroisiemepourlespolygonesetc.Celadonneunestructuremodulaire,plusagreablea lire,pourlesprogrammes.

En fait uneclassec’est bien plus qu’un regroupementde fonctions.En effet, on peutyplacerdesconstantesutilespourtouteslesfonctionsdela classeetqui neserontpasmodifieespar celles-ci,desvariablespartageespar cesfonctionset auxquelleselles pourrontaffecterune nouvelle valeur. Mais ce n’est pastout, uneclassepermetausside definir un type quedesvariablespourrontprendre,cetypepeutcontenirdesenregistrementscomposesdechamps(commelesrecordsenPascal,lesstructuresenC, oule typeproduitdeCaml).Un pointunpeudelicatestla constructiond’un objetdela classequi sefait a l’aide deconstructeurs.

4.1 Fonctions

Une fonction prenddesvaleursen parametreset donneen general un resultat.Elle sedeclarepar:

public static typeRes nomFonction(typ e1 nom1, type2 nom2,... , typek nomk)

DanscetteecrituretypeRes estle typedu resultat,noterquecelui-ci peutetrevoid , danscecasla fonctionnerendpasde resultatet operepareffet debord,parexempleen affichantdesvaleursou enmodifiantdesvariablesglobales.Il estdeconseille d’ecriredesfonctionsquiprocedentpareffet debord,saufbienentendupourlesaffichages.

La signature d’unefonctionestconstitueedela suiteordonneedestypesdesparametres.On fait appela unefonctionpar

nomFonction(var 1, var2, ... , vark)

En general cet appelsesituedansuneaffectation,saufsi le type du resultatestvoid . Lesparametresd’appeld’une fonction sontpassespar valeurs,c’est a dire queleur valeurssontrecopieeslorsdel’appel.Apresla fin dutravail dela fonctionlesnouvellesvaleurs,qui peuventavoir ete attribueesa cesvariables,nesontplusaccessibles.

Ainsi il n’estpaspossibled’ecrireunefonctionqui echangelesvaleursdedeuxvariablespasseesenparametre,saufa procederpardesmoyensdetournespeurecommandes.

25

26 CHAPITRE4. COMPOSANTSD’UNE CLASSE

Noter quesi un parametrea le type tableau(ou un autretypedeclasse),alorsla variablepasseeestunereferencesurcetableauet la modificationdesvaleursd’un elementdu tableauauraun effet accessiblea l’exterieurdela fonction.

Le resultatducalculdela fonctiondoit etreindique apresun return . Il estobligatoiredeprevoir unetelle instructiondanstouteslesbranchesd’une fonction (saufpour le typevoidbienentendu).L’executiond’un return apoureffet d’interromprele calculdela fonctionenrendantle resultata l’appelant.

En Java on peut definir plusieursfonctionsqui ont le memenom a condition que leurssignaturessoientdifferentes.On appellesurcharge cettepossibilite. Le compilateurdoit etreamemededeterminerla fonctiondontil estquestiona partir du typedesparametresd’appel.

4.2 Constanteset variablesglobales

Uneconstantesedeclarepar

static final int promotion = 2000;

ellenepourrapasetremodifieeparlesfonctionsdela classe.

Lesvariablesglobalessontdeclareespar

static int nbeleves;

On peutdeclarerdesvariablesglobalesden’importequel type,toutefoisc’estengeneraldesentiersqu’onutilisepourcompter.

4.3 Lesclassespour definir desenregistrements

Une structure,ou un type produit permetde travailler avec desvariablesqui possedentplusieurschamps.Ceci est l’ equivalentde l’operationmathematiquedu produit cartesiendedeuxou plusieursensembles.Lesdeclarationssefont commepourlesvariablesglobalessansindiquerstatic avantle type.Ainsi onpeutdefinir despointsduplanparleurscoordonnees:

public class Point {float abs;float ord;}

Par la suitepouraccedera la valeurd’un deschampson utilise le symbole. apresle nomdela variable.

parexemple:

x.abs = 1; x.ord = -1;

4.4 Constructeurs

Quandon fabriqueuneclasse,il est indispensablede donnerun moyen de construirelesobjetsde cetteclasse.Ceci se fait par desfonctionsdont le nom est le memequecelui dela classeou ellessontdefinies.Noterquela regleconcernantlessurchargespermetdedefinirplusieursconstructeurspourunememeclassedumomentquelestypesdesparametresd’appelsdecesgenerateurssontdifferents.

Parexemple:

4.5. LES METHODESSTATIQUESET LES AUTRES 27

Point (float x, float y){abs = x; ord = y;}Point (Point u) {

abs = u.abs;ord = u.ord;}

4.5 Lesmethodesstatiqueset lesautres

Onn’utilisepratiquementquedesfonctionsstatiquesdanslecadredececours,ladeclarationdecesfonctionsestprecedeedu mot reserve static . Il y a unefacon nonstatiquededefinirunefonction.Danscecasil fautfaireappelacettefonctionenutilisantunobjetdela classe,ob-jet auquella fonctionpourras’appliquer, l’appelsefait alorsparNomObjet.NomFo nct io n.Dansla descriptiond’unemethodenonstatiqueon fait referencea l’objet qui a servia l’appelparle nom this .

Un exemplecompletde classeest donne ci-dessousavec les differentespossibilites defonctions:

Exemple: lespoints du plan– Un point estrepresente parsonabcisseetsonordonnee– Un constructeurfabriquel’objet point a partir desescoordonnees– Unemethodeaffichelescoordonneesd’un point– On aparfoisbesoindu point 8 (origine)– On veutconstruirele symetriqued’un pointparrapporta 8– Unemethodeverifie si troispointssontalignes

class PointEntier{int abs, ord;

PointEntier(int a, int b){abs = a;ord = b;

}

public void affiche() {System.out.prin tl n( " Point de coordonnees"

+ abs +" " + ord );}

public static PointEntier origine(){return new PointEntier(0, 0);

}

public PointEntier oppose(){return new PointEntier(- this.abs, - this.ord);

}

public static boolean alignes(PointEn tie r p,PointEntier q,PointEntier r){

int u = (p.abs - q.abs) * (p.ord - r.ord)- (p.abs - r.abs) * (p.ord - q.ord);

28 CHAPITRE4. COMPOSANTSD’UNE CLASSE

return (u == 0);}}

4.6 Utiliser plusieursclasses

Lorsquel’on utilise la classeprecedentea l’exterieuron doit faire precederles nomsdesfonctionsdu nomdela classesuivi d’un point.

class Exemple{

public static void main (String[] args){PointEntier p = new PointEntier(3,5 );PointEntier q = p.oppose();PointEntier r = PointEntier.ori gi ne();boolean res = PointEntier.ali gnes (p ,q, r) ;p.affiche();q.affiche();r.affiche();System.out.print ln (r es );}

}

Chapitr e 5

Complements

5.1 Exceptions

Lesexceptionssontdesobjetsdela classeException . Il existeaussiuneclasseErrormoins utilisee pour les erreurssysteme.Toutesles deux sont dessous-classesde la classeThrowable , donttouslesobjetspeuventetreappliquesa l’operateurthrow , commesuit :

throw e ;

Ainsi on peutecrireenseservantdedeuxconstructeursdela classeException :

throw new Exception();throw new Exception ("Acc es interdit dans un tableau");

Heureusement,dansles classesdesbibliothequesstandard,beaucoupd’exceptionssontdejapre-definies,parexempleIndexOutOfBoun dsExc epti on .Onrecupereuneexceptionparl’instruction try . . .catch . Parexemple

try {// un programme compliqu e

} catch ( IOException e) {// essayer de r eparer cette erreur d’entr ee/sortie

}catch ( Exception e) {

// essayer de r eparer cette erreur plus generale}

Si on veut faireun traitementuniformeenfin del’instruction try , quel’on passeou nonparuneexception,quele controlesorteounondel’instructionparunerupturedesequencecommeun return , break , etc,on ecrit

try {// un programme compliqu e

} catch ( IOException e) {// essayer de r eparer cette erreur d’entr ee/sortie

}catch ( Exception e) {

//essayer de r eparer cette erreur plus generale}finally {

// un peu de nettoyage}

29

30 CHAPITRE5. COMPLEMENTS

Il y a deuxtypesd’exceptions.On doit declarerles exceptionsverifieesderriere le mot-cle throws dansla signaturedes fonctionsqui les levent. Ce n’est pas la peinepour lesexceptionsnon verifieesqui se reconnaissenten appartenanta une sous-classede la classeRuntimeExceptio n. Ainsi

static int lire () throws IOException, ParseException {int n;BufferedReader in =

new BufferedReader(new InputStreamReader(System.in));

System.out.print ("Taille du carr e magique, svp?:: ");n = Integer.parseInt (in.readLine());if ((n <= 0) || (n > N) || (n % 2 == 0))

erreur ("Taille impossible.");return n;

}

5.2 Graphisme

5.2.1 Fonctionselementaires

Les fonctionssont inspireesde la libraire QuickDraw du Macintosh,mais fonctionnentaussisur les stationsUnix. Sur Macintosh,une fenetre Drawing permetde gerer un ecrantypiquementde � 6 �:9<;>=�?A@ points.L’originedusystemedecoordonneesestenhautetagauche.L’axe des B va classiquementde la gaucheversla droite,l’axe des C va pluscurieusementduhautvers le bas(c’est unevieille tradition de l’informatique, dure a remettreen cause).EnQuickDraw, B et C sontsouventappelesh (horizontal)etv (vertical).Il y aunenotiondepointcourantetdecrayonavecunetaille etunecouleurcourantes.Onpeutdeplacerle crayon,enlelevantouendessinantdesvecteursparlesfonctionssuivantes

moveTo (x, y) Deplacele crayonauxcoordonneesabsoluesx , y .

move (dx, dy) Deplacele crayonenrelatif dedx , dy .

lineTo (x, y) Traceuneligne depuisle point courantjusqu’aupoint de coordonneesx , y .

line (dx, dy) Tracele vecteur(dx , dy ) depuisle point courant.

penPat(pattern) Changelacouleurducrayon: white ,black , gray , dkGray (darkgray), ltGray (light gray).

penSize(dx, dy) Changela taille du crayon.La taille pardefaut est(1, 1). Touteslesoperationsdetrace peuventsefaireavecunecertaineepaisseurdu crayon.

penMode(mode) Changele moded’ecriture: patCopy (modepar defaut qui effacecesurquoion trace),patOr (modeUnion, i.e. sanseffacercesurquoion trace),patXor(modeXor, i.e.eninversantcesurquoi on trace).

5.2.2 Rectangles

Certainesoperationssontpossiblessurlesrectangles.Un rectangler auntypepredefini Rect .Cetypeestuneclassequi a le formatsuivant

public class Rect {

short left, top, right, bottom;}

5.2. GRAPHISME 31

Fort heureusement,il n’y apasbesoindeconnaıtre le formatinternesdesrectangles,etonpeutfairesimplementlesoperationsgraphiquessuivantessurlesrectangles

setRect(r, g, h, d, b) fixelescoordonnees(gauche,haut,droite,bas)durectangler . C’estequivalentafairelesoperationsr.left := g ; , r.top := h ; , r.right :=d ; , r.bottom := b.

unionRect(r1, r2, r) definit le rectangler commel’enveloppeenglobantedesrec-tanglesr1 et r2 .

frameRect(r) dessinele cadredu rectangler avec la largeur, la couleuret le modeducrayoncourant.

paintRect(r) remplit l’int erieurdu rectangler avecla couleurcourante.

invertRect(r) inversela couleurdu rectangler .

eraseRect(r) effacele rectangler .

fillRect(r,pat) remplit l’int erieurdu rectangler avecla couleurpat .

drawChar(c), drawString(s) affiche le caracterec ou la chaıne s aupoint courantdansla fenetregraphique.Cesfonctionsdifferentdewrite ou writeln qui ecriventdansla fenetretexte.

frameOval(r) dessinele cadredel’ellipse inscritedansle rectangler avecla largeur, lacouleuret le modedu crayoncourant.

paintOval(r) remplit l’ellipse inscritedansle rectangler avecla couleurcourante.

invertOval(r) inversel’ellipse inscritedansr .

eraseOval(r) effacel’ellipse inscritedansr .

fillOval(r,pat) remplit l’int erieurl’ellipse inscritedansr avecla couleurpat .

frameArc(r,start,arc) dessinel’arc del’ellipse inscritedansle rectangler demarranta l’anglestart et surla longueurdefinieparl’anglearc .

frameArc(r,start,arc) peint le camembertcorrespondanta l’arc precedent. . .. Il ya aussidesfonctionspourlesrectanglesavecdescoinsarrondis.

button estunefonction qui renvoie la valeurvraie si le boutonde la sourisestenfonce,fauxsinon.

getMouse(p) renvoie dansp le point decoordonnees * p.h � p.v , courantesducurseur.

getPixel(p) donnela couleurdu point p. Repondunbooleen: false si blanc,true.si noir.

hideCursor(), showCursor() cacheou remontrele curseur.

5.2.3 La classeMaclib

class Point {short h, v;

Point(int h, int v) {h = (short)h;v = (short)v;

}}class MacLib {

static void setPt(Point p, int h, int v) {..}static void addPt(Point src, Point dst) {...}


static void subPt(Point src, Point dst) {...}static boolean equalPt(Point p1, Point p2) {...}...

}

Et lesfonctionscorrespondantes(voir page31)

static void setRect(Rect r, int left, int top, int right, int bottom)static void unionRect(Rect src1, Rect src2, Rect dst)

static void frameRect(Rect r)static void paintRect(Rect r)static void eraseRect(Rect r)static void invertRect(Rect r)

static void frameOval(Rect r)static void paintOval(Rect r)static void eraseOval(Rect r)static void invertOval(Rect r)

static void frameArc(Rect r, int startAngle, int arcAngle)static void paintArc(Rect r, int startAngle, int arcAngle)static void eraseArc(Rect r, int startAngle, int arcAngle)static void invertArc(Rect r, int startAngle, int arcAngle)static boolean button()static void getMouse(Point p)

Toutescesdefinitionssontaussisurpoly dansle fichier

/usr/local/lib/MacLib-java/MacLib.ja va

On veillera a avoir cetteclassedansl’ensembledesclasseschargeables(variabled’envi-ronnementCLASSPATH).

5.2.4 Jeudeballe

Le programmesuivantfait rebondiruneballedansunrectangle,premiereetapeversun jeudepong.

class Pong extends MacLib {

static final int C = 5, // Le rayon de la balleX0 = 5, X1 = 250,Y0 = 5, Y1 = 180;

static void getXY (Point p) {int N = 2;Rect r = new Rect();int x, y;

while (!button()) // On attend le bouton enfonc e;

while (button()) // On attend le bouton rel ach e;

getMouse(p); // On note les coordonn ees du pointeurx = p.h;y = p.v;

5.2. GRAPHISME 33

setRect(r, x - N, y - N, x + N, y + N);paintOval(r); // On affiche le point pour signifier la

lecture}

public static void main (String args[]) {int x, y, dx, dy;Rect r = new Rect();Rect s = new Rect();Point p = new Point();int i;

initQuickDraw(); // Initialisation du graphiquesetRect(s, 50, 50, X1 + 100, Y1 + 100);setDrawingRect(s);showDrawing();setRect(s, X0, Y0, X1, Y1);frameRect(s); // Le rectangle de jeugetXY(p); // On note les coordonn ees du pointeurx = p.h; y = p.v;dx = 1; // La vitesse initialedy = 1; // de la ballefor (;;) {

setRect(r, x - C, y - C, x + C, y + C);paintOval(r); // On dessine la balle en $x,y$x = x + dx;if (x - C <= X0 + 1 || x + C >= X1 - 1)

dx = -dx;y = y + dy;if (y - C <= Y0 + 1 || y + C >= Y1 - 1)

dy = -dy;for (i = 0; i < 2500; ++i)

; // On temporiseinvertOval(r); // On efface la balle

}}

}


Chapitr e 6

PrincipesdebasedessystemesUnix

6.1 Survol du systeme

Le systemeUNIX fut developpe a Bell laboratories(research) de 1970a 1980par KenThompsonet DennisRitchie. Il s’est rapidementrepandudansle milieu de la recherche,etplusieursvariantesdu systemeoriginal ont vu le jour (versionsSYSTEM V d’AT&T, BSDa Berkeley, . . .). Il triompheaujourd’huiaupresdu grandpublic avec les differentesversionsde LINUX1, dont le createuroriginal estLinus B. Torvaldset qui ont transforme les PC demachinesbureautiquescertessophistiqueesenveritablesstationsdetravail.

Les raisonsdu succes d’UNIX sont multiples.La principaleest sansdoutesa clarte etsasimplicite. Il a ete egalementle premiersystemenon proprietairequi a bien isole la par-tie logicielle de la partiematerielle de tout systemed’exploitation. Ecrit dansun langagedehautniveau(le langageC, l’un desperesde JAVA), il esttresfacile a portersur lesnouvellesarchitecturesdemachines.Celarepresenteun interet nonnegligeable: lespremierssystemesd’exploitation etaientecritsen langagemachine,cequi neplaidaitpaspour la portabilite desdits-systemes,etdoncavait uncout deportagecolossal.

Quellepourraitetrela devised’UNIX ?SansdouteProgrammez,nousfaisonsle reste. Unordinateurestunemachinecomplexe,qui doit gererdesdispositifsphysiques(la memoire,lesperipheriquescommesles disques,imprimantes,modem,etc.) et s’interfacerau reseau(IN-TERNET). L’utilisateur n’a pasbesoinde savoir commenteststocke un fichier sur le disque,il veut justeconsidererquec’estun espacememoiredanslequelil peutrangersesdonneesasaconvenance.Quele systemesedebrouillepourassurerla coherencedu fichier, quandbienmemeil seraitphysiquementeparpille enplusieursmorceaux.

Dansle memeordred’idees,l’utilisateur veut faire tournerdesprogrammes,mais il n’acuredesavoir commentle systemegerela memoiredel’ordinateuret commentle programmetourne.Ceci estd’autantplus vrai qu’UNIX estun systememulti-utilisateuret multitaches.On neveutpassavoir commentlespartagesderessourcessonteffectuesentredifferentsutili-sateurs.Chacundoit pouvoir vivre savie sansreveiller l’autre.

Toutescescontraintessont relegueesau systeme.Notonsque ceci n’est pasforcementfacile a mettreen œuvre.Nous verronsplus loin commentle systemedecidece que fait leprocesseuraun instantdonne.

Le systeme UNIX est constitue de deux couchesbien separees: le noyau permetausystemed’interagiravec la partiematerielle de la machine,la couchesuperieurecontientlesprogrammesdesutilisateurs.Tout programmequi tourneinvoquedesprimitivesde commu-nication avec le noyau, appeleesappelssystemes. Les plus courantssont ceux qui font lesentrees-sortieset lesoperationssurlesfichiers.La majeurepartiedeslangagesdehautniveau

1La premiereversion(0.01)a ete diffuseeenaout 1991.

35

36 CHAPITRE6. PRINCIPESDE BASEDESSYSTEMESUNIX

(JAVA, C) possedentdesinterfacesqui appellentdirectementle noyau,maiscelaesttransparentpourle programmeurmoyen.

materiel

noyau

programmes

FIG. 6.1– Architecturedu systemeUNIX.

Le noyau s’occupedu controle de l’executioninviduelle aussibien queglobaledespro-grammes.Un programmequi s’executeestappele processus. Le noyau permetla creation,lasuspension,la fin d’un processus.Il geredemaniereequitablel’executiondetouslesprocessuspresents.Il leuralloueetgerela placememoirenecessairea leurexecution.

6.2 Le systemede fichiers

Le systemede fichiersd’UNIX estarborescent,l’ancetre de tous les cheminspossiblesetantla racine(notee/ ). Ondisposederepertoires,qui contiennenteux-memesdesrepertoiresetdesfichiers.C’estla la seulevisionqueveutavoir unutilisateurdel’organisationdesfichiers.Aucunfichier UNIX n’est type. Pourle systeme,touslesfichiers(y comprisles repertoires)contiennentdessuitesd’octets,charge ausystemelui-memeet auxprogrammesa interpretercorrectementleur contenu.De meme,un fichier n’a pasde taille limit eea priori . Cesdeuxcaracteristiquesne sont paspartageespar grandnombrede systemes...Un desautrestraitsd’UNIX estdetraiterfacilementlesperipheriquescommedesfichiers.Parexemple:

unix% cat musique > /dev/audio

permetd’ecouterlefichiermusique sursonordinateur(defaconprimitive...).C’estlesystemequi sedebrouillepourassocierle nomspecial /dev/audio/ auxhauts-parleursdel’ordina-teur(s’ils existent).

En interne,un fichier est decrit par un i-nœud(inode pour index nodeen anglais),quicontienttoutesles informationsnecessairesa sa localisationsur le disque.Un fichier estvucommeunesuited’octets,rassemblesenblocs.Cesblocsn’ont pasvocationa etrecontigues:les fichierspeuvent croıtre de facon dynamiqueet unebonnegestionde l’espacedisquepeutamenera aller chercherde la placepartoutsur le disque.Il faut doncgererunestructurededonneespermettantde recuperersespetitsdansle bonordre.La structurela plusadapteeestcelled’unetablecontenantdesnumerosdeblocs.Celle-ciestdecoupeeentrois : la zonedes

6.3. LES PROCESSUS 37

blocsdirectscontientdesnumerosde blocscontenantvraimentdesdonnees; la zonesimpleindirectionfait referencea uneadresseou on trouve unetabledenumerosdeblocsdirects; lazonedoubleindirectioncontientdesreferencesa destablesdereferencesqui font referenceadesblocs(cf. figure6.2),et enfina la zonetriple indirection. La structurededonneescorres-pondanteestappeleeB-arbreetpermetdegerercorrectementlesdisquesactuels.

direct

direct

simpleindirection

doubleindirection

tripleindirection

blocsdedonnees

FIG. 6.2– Structureblocd’un fichier.

Le noyaunemanipulejamaislesfichiersdirectementsurdisque.Il travaille avecdestam-ponsintermediairesqui permettentde limiter l’acces a la memoiredisque.Celaameliore lesperformancesdesentrees/sortieset protegelesfichiers.

6.3 Lesprocessus

6.3.1 Comment traquer lesprocessus

Un processusestunprogrammequi s’execute.CommeUNIX estunsystememulti-taches,multi-utilisateurs,il y a toujoursun grandnombrede tels processusqui vivent a un instantdonne.Lesdifferentsprocessussontstockesdansunetableet reperesparleurnumerod’ordre.A tout instant,on peutconsulterla liste desprocessusappartenanta un utilisateurparla com-mandeps (pourprocess status ) :

unix% psPID TTY TIME CMD646 pts/1 00:00:00 bash740 pts/1 00:00:00 ps

La premierecolonnedonnele numerodu processusdansla table,la deuxiemele terminal(ondit tty ) associe auprocessus,le tempsCPUutilise estdonne dansla troisieme,et finalementla quatriemedonnela commandequi a lance le processus.

On peutegalementobtenirla listedetouslesprocessusenrajoutantdesoptionsaps avecpourresultatle contenudela table6.1.

On voit apparaıtre une colonneSTAT qui indique l’ etat de chaqueprocessus.Danscetexemple,la commandeps ax estla seulea etreactive (d’ou le R dansla troisiemecolonne).


PID TTY STAT TIME COMMAND1 ? S 0:05 init [3]2 ? SW 0:00 [kflushd]3 ? SW 0:00 [kupdate]4 ? SW 0:00 [kpiod]5 ? SW 0:00 [kswapd]6 ? SW< 0:00 [mdrecoveryd]

189 ? S 0:00 portmap203 ? S 0:00 /usr/sbin/apmd -p 10 -w 5 ...254 ? S 0:00 syslogd -m 0263 ? S 0:00 klogd281 ? S 0:00 /usr/sbin/atd295 ? S 0:00 crond309 ? S 0:01 /usr/sbin/ssfd323 ? S 0:00 lpd368 ? S 0:00 sendmail:383 ? S 0:00 gpm -t pnp413 ? S 0:00 /usr/bin/postmaster460 ? S 0:00 xfs -droppriv -daemon -port -1488 tty2 S 0:00 /sbin/mingetty tty2489 tty3 S 0:00 /sbin/mingetty tty3490 tty4 S 0:00 /sbin/mingetty tty4491 tty5 S 0:00 /sbin/mingetty tty5492 tty6 S 0:00 /sbin/mingetty tty6600 tty1 S 0:00 login -- francois601 tty1 S 0:00 /bin/bash632 tty1 S 0:00 xinit633 ? S 0:02 /etc/X11/X :0636 tty1 S 0:00 sh /home/francois/.xinitrc638 tty1 S 0:00 tvtwm640 tty1 S 0:00 xterm641 tty1 S 0:00 xterm646 pts/1 S 0:00 /bin/bash647 pts/0 S 0:00 /bin/bash737 pts/0 S 0:01 /usr/bin/emacs -nw unix.tex739 pts/1 R 0:00 ps ax

TAB. 6.1– Resultatdela commandeps ax .


Memequandon ne fait rien (ici, le seulprocessusd’un utilisateurest l’ edition d’un fichierpar la commandeemacs), il existeplein deprocessusvivants.Notonsparmiceux-la touslesprogrammesse terminantpar un d comme/usr/sbin/ssfd ou lpd , qui sont despro-grammessystemesspeciaux(appelesdemons) attendantqu’on les reveille pour executerunetachecommeseconnecterou imprimer.

Onconstatequelanumerotationdesprocessusn’estpascontinue.Au lancementdusysteme,le processus0 estlance, il creele processus1 qui prendla main.Celui-ci creed’autrespro-cessusfils qui heritent de certainesproprietes de leur pere. Certainsprocessussont crees,executentleur tacheetmeurent,le numeroqui leur etaitattribue disparait.Onpeutvoir l’arbregenealogiquedesprocessusqui tournenta l’aide dela commandepstree (voir figure6.2).

Les? dansla deuxiemecolonneindiquentl’existencedeprocessusqui nesontaffectesaaucunTTY.

6.3.2 Fabrication et gestion

Un processusconsisteen unesuited’octetsquele processeurinterpretecommedesins-tructionsmachine,ainsi quedesdonneeset unepile. Un processusexecuteles instructionsqui lui sontpropresdansun ordrebien defini, et il ne peutexecuterles instructionsapparte-nant a d’autresprocessus.Chaqueprocessuss’executedansunezonede la memoirequi luiest reservee et protegee desautresprocessus.Il peut lire ou ecrire les donneesdanssazonememoirepropre,sanspouvoir interferer avec cellesdesautresprocessus.Notonsque cettepropriete estcaracteristiqued’UNIX, et qu’elle esttrop souventabsentedecertainssystemesgrandpublic.

Lescompilateursgenerentles instructionsmachined’un programmeensupposantquelamemoireutilisable commencea l’adresse0. Charge au systemea transformerles adressesvirtuelles du programmeen adressesphysiques. L’avantaged’une telle approcheest que lecodegenere ne dependjamaisde l’endroit dansla memoireou il va vraimentetreexecute.Celapermetaussid’executerle memeprogrammesimultanement: un processusnouveauestcree a chaquefois et unenouvelle zonede memoirephysiquelui estalloue. Quediraientlesutilisateurssi l’ editeuremacs nepouvait etreutilise queparun seuld’entreeuxa la fois !

Le contexte d’un processusestla donneedesoncode,lesvaleursdesvariables,lesstruc-turesde donnees,etc. qui lui sont associees,ainsi que de son etat. A un instantdonne, unprocessuspeutetredansquatreetatspossibles:

– encoursd’executionenmodeutilisateur;– encoursd’executionenmodenoyau;– pasenexecution,maispret a l’ etre;– endormi,quandil ne peutplus continuera s’executer(parcequ’il esten attented’une

entreesortieparexemple).Un processeurne peut traiter qu’un seul processusa la fois. Le processuspeut etre en

modeutilisateur: dansce cas,il peutaccederaux donneesutilisateur, maispasaux donneesdu noyau. En modenoyau, le processuspeutaccederegalementaux donneesdu noyau. Unprocessuspassecontinuellementd’un etata l’autreaucoursdesavie,selondesreglesprecises,simplifieesici dansle diagrammedetransitiond’etatsdecritsa la figure6.3.

Il nepeuty avoir changementdecontextequ’enpassantdel’ etat2 (modenoyau)a l’ etat4(endormi).Danscecas,le systemesauvegardele contexte du processusavantd’en chargerunautre.Le systemepourrareprendrel’executiondu premierprocessusplustard.

Un processuspeutchangerd’etatde sonproprechef (parcequ’il s’endort)ou parcequele noyau vient de recevoir une interruption qui doit etre traitee, par exemple parcequ’unperipheriquea demande a ce qu’on s’occupede lui. Notonstoutefoisquele noyau ne laissepastomberun processusquandil executeunepartiesensibledu codequi pourraitcorrompredesdonneesduprocessus.


init-+-apmd|-atd|-crond|-gpm|-kflushd|-klogd|-kpiod|-kswapd|-kupdate|-login---bash- -- xi ni t- +-X| ‘-sh-+-tvtwm| |-xterm---bash- -- pst re e| ‘-xterm---bash- -- emacs|-lpd|-mdrecoveryd|-5*[mingetty]|-portmap|-postmaster|-sendmail|-ssfd|-syslogd‘-xfs

TAB. 6.2– Resultatdela commandepstree .


1. executionenmodeutilisateur

2. executionenmodenoyau

4. endormi 3. pret

Appel systemeou interruption

s’endort

sereveille

election

Interruptionouretourd’interruption

FIG. 6.3– Diagrammedetransitiond’etats.

6.3.3 L’ordonnancementdestaches

Le processeurne peuttraiter qu’un processusa chaquefois. Il donnel’impressiond’etremulti-tachesenaccordantachacundesprocessusunpeudetempsdetraitementa tourderole.

Le systemedoit doncgererl’accesequitabledechaqueprocessusauprocesseur. Le prin-cipe general est d’allouer a chaqueprocessusun quantumde tempspendantlequel il peuts’executerdansle processeur. A la fin de ce quantum,le systemele preempteet reevalue lapriorite de touslesprocessusaumoyend’unefile depriorite. Le processusavecla plushauteprioritedansl’ etat“pret as’executer, chargeenmemoire”estalorsintroduitdansle processeur.La priorite d’un processusestd’autantplusbassequ’il a recemmentutilise le processeur.

Le tempsestmesure parunehorlogematerielle,qui interromptperiodiquementle proces-seur(generantuneinterruption).A chaquetop d’horloge,le noyau peutainsi reordonnerlesprioritesdesdifferentsprocessus,cequi permetdenepaslaisserle monopoledu processeuraun seulprocessus.

La politiqueexacted’ordonnancementdestachesdependdu systemeet esttrop complexepouretredecriteici. Nousrenvoyonsauxreferencespourcela.

Notonspour finir que l’utilisateur peutchangerla priorite d’un processusa l’aide de lacommandenice . Si le programmetoto n’estpasextremementprioritaire,on peutle lancersurla machinepar:

unix% nice ./toto &

La plusbassepriorite est �ED :

unix% nice -19 ./toto &

et la plushaute(utilisableseulementpar le super-utilisateur)est �F� 6 . Dansle premiercas,leprogrammene tournequesi personned’autrene fait tournerde programme; dansle second,le programmedevient super-prioritaire, memedevant les appelssystemesles plus courants(souris,etc.).


6.3.4 La gestionmemoire

Le systemedoit partagernonseulementle tempsentrelesprocessus,maisaussila memoire.La memoirecentraledesordinateursactuelsest de l’ordre de quelquescentainesde megaoctets,maiscelanesuffit generalementpasaungrandnombred’utilisateurs.Chaqueprocessusconsommede la memoire.De maniere simplifiee, le systemegere le problemede la faconsuivante.Tantquela memoirecentralepeutcontenirtouteslesdemandes,tout va bien.Quandla memoireapprochede la saturation,le systemedefinit despriorites d’acces a la memoire,qu’onnepeutseparerdesprioritesd’execution.Si unprocessusestenmoded’execution,il estlogiquequ’il ait priorite dansl’accesa la memoire.Inversement,unprocessusendormin’a pasbesoind’occuperdela memoirecentrale,et il peutetrerelegue dansuneautrezonememoire,generalementundisque.On dit quele processusa ete swappe2.

Encoreplusprecisement,chaqueprocessusoperesurdela memoirevirtuelle, c’est-a-direqu’il fait commes’il avait toutela memoirea lui toutseul.Le systemes’occupedefairecoinci-dercettememoirevirtuelleavecla memoirephysique.Il fait mememieux: il peutsecontenterde charger en memoirela partiede celle-ci dont le processusa vraimentbesoina un instantdonne (mecanismedepagination).

6.3.5 Le mysteredu demarrage

Allumer unemachineressembleau BIG BANG : l’instant d’avant, il n’y a rien, l’instantd’apres,l’ordinateurvit etestpret a travailler.

La premiere tachea accomplirestde faire charger en memoirela procedurede miseenroute(ondit plussouventboot) dusysteme.On touchela aunproblemedetypepouleetœuf:commentle systemepeut-il secharger lui-meme? Dansles tempsanciens,il s’agissaitd’uneprocedurequasimanuellede reboot,analogueau demarragedesvoituresa la manivelle. Denos jours, le processeura peinereveille va lire unememoireROMcontenantles instructionsde boot.Apresquelquestests,le systemerecuperesur disquele noyau (fichier /vmunix ou...). Le programmede boot transfertalors la main au noyau qui commencea s’executer, enconstruisantle processus03, qui creele processus1 (init ) et setransformeen le processuskswapd .

6.4 Gestiondesflux

Un programmeUNIX typiqueprendun ou plusieursflux en entree,opereun traitementdessuset ressortun ou plusieursflux. L’exemplele plus simple est celui d’un programmes’executantsurun terminal: il attendenentreedescaracterestapesparl’utilisateur, interpretecescaracteresd’unecertainemaniereet ressortun resultatsurle memeterminal.Parexemple,le programmemail permetd’envoyer un emaila la main:

unix% mail moimemeSubject: essai144.

Un exemplepluselabore,qui reprendle memeprincipe,estle suivant.Plutot quelire lescom-mandessurle clavier, le programmeva lire lescaracteressursonentreestandard,ici unfichiercontenantle nombre144 :

unix% mail moimeme < cmds

Notezla differenceavecla commande2C’estdu franglais,maisle termeesttellementstandard...3DansLinux, c’estun peudifferent: desprocessusspeciauxsontcreesenparalleleau lancement,maisl’id ee

estgrosso-modola meme.

6.4. GESTIONDESFLUX 43

unix% mail cmds

qui transformecmds enunargumentpasseauprogrammeetqui provoqueuneerreur(amoinsqu’unutilisateurs’appellecmds. . .).

Desqu’unprogrammes’execute,il lui estassocie troisflux : le premierestle flux d’entree,le deuxiemele flux desortie,le troisiemeestunflux destine a recueillir leserreursd’execution.Ainsi, onpeutrediriger la sortiestandardd’un programmedansunfichierenutilisant:

unix% java carre < cmds > resultat

En sh ouenbash , la sortied’erreurestrecupereecommesuit :

unix% mail < cmds > resultat 2> erreurs

Pour le moment,nousnoussommescontentes de gerer les flux de facon simple,en lesfabriquanta l’aide du contenude fichiers.On peut egalementprendreun flux sortantd’unprogrammepour qu’il serve d’entree a un autreprogramme.On peut lister les fichiersd’unrepertoireet leur taille a l’aide dela commandels -s :

unix% ls -s > ficunix% cat fictotal 210

138 dps1 poly.tex

51 unix.tex20 unixsys.tex

Uneautrecommanded’UNIX biencommodeestcelle permettantde trier un fichier a l’aidedeplusieurscriteres.Parexemple,sort +0n fic permetdetrier leslignesde fic suivantla premierecolonne:

unix% sort +0n fictotal 210

1 poly.tex20 unixsys.tex51 unix.tex

138 dps

Pourobtenirceresultat,on a utilise un fichier intermediaire,alorsqu’on auraitpu procederenuneseulefois a l’aide de:

unix% ls -s | sort +0n

Le pipe (tube)permetainsi de mettreen communucationla sortiestandardde ls -s avecl’entreestandarddesort . Onpeutbiensur empilerlestubes,etmelangeravolonte >, < et | .

On a ainsi isole un despoints importantsde la philosophied’UNIX : on construitdesprimitivespuissantes,et on les assemblea la facon d’un mecanopour obtenirdesoperationsplus complexes.On n’insisterajamaisassezsur l’importancedecertainesprimitives,commecat , echo , etc.


Chapitr e 7

Retrouver l’inf ormation

Un tableaupermetl’accesdirect a un element,et nousallonsnousservir grandementdecettepropriete danslesalgorithmesdetri et derechercheentablequenousallonsconsiderer.Cechapitreva nouspermettred’introduirela notiondecomplexite d’un algorithme.

7.1 Complexite desalgorithmes

La complexite d’un algorithmeestle nombred’operationselementaires(affectations,com-paraisons,operationsarithmetiques)effectueespar un algorithme.Ce nombres’exprime enfonctionde la taille � desdonnees.On dit quela complexite de l’algorithmeest 8G*.HI*J��,1, ouH estd’habitudeunecombinaisondepolynomes,logarithmesou exponentielles.Cecireprendla notationmathematiqueclassique,etsignifiequele nombred’operationseffectueesestbornepar �-HI*J��, , ou � estuneconstante,lorsque� tendversl’infini.

Considererle comportemental’infini dela complexiteestjustifieparle fait quelesdonneesdesalgorithmessontde grandetaille et qu’on sepreoccupesurtoutde la croissancede cettecomplexite enfonctiondela taille desdonnees.Unequestionsystematiqueaseposerest: quedevient le tempsdecalculsi on multiplie la taille desdonneespar � ?

Les algorithmesusuelspeuvent etreclasses en un certainnombrede grandesclassesdecomplexite.

– Les algorithmessub-lineaires,dont la complexite esten general en 8G*�KMLANO��, . C’est lecasdela recherched’un elementdansun ensembleordonne fini decardinal� .

– Lesalgorithmeslineairesencomplexite 8P*J��, ou en 8P*J�QKMLANR��, sontconsiderescommerapides,commel’ evaluationdela valeurd’uneexpressioncomposeede � symbolesoulesalgorithmesoptimauxdetri.

– Pluslentssontlesalgorithmesde complexite situeeentre 8P*J�TSE, et 8G*J�T�-, , c’est le casdela multiplicationdesmatricesetdu parcoursdanslesgraphes.

– Au dela, les algorithmespolynomiauxen 8G*J�TU�, pour VXWZY sontconsideres commelents,sansparlerdesalgorithmesexponentiels(dont la complexite estsuperieurea toutpolynomeen � ) quel’on s’accordeadire impraticablesdesquela taille desdonneesestsuperieureaquelquesdizainesd’unites.

La recherchede l’algorithme ayantla plus faible complexite, pour resoudreun problemedonne, fait partiedu travail regulierde l’informaticien. Il ne faut toutefoispastomberdanscertainsexces, par exempleproposerun algorithmeexcessivementalambique, developpantmille astuceset ayantunecomplexite en 8P*J�[�1\ ]1]E, , alorsqu’il existe un algorithmesimpleetclair de complexite 8P*J�TSE, . Surtout,si le gain de l’exposantde � s’accompagned’une perteimportantedansla constantemultiplicative : passerd’une complexite de l’ordre de � SE^ � aunecomplexite de � 6 �`_ �QKMLANO� n’est pasvraimentuneamelioration.Les criteresde clarte et

45

46 CHAPITRE7. RETROUVERL’INFORMATION

nom tel

paul 2811roger 4501laure 2701anne 2702pierre 2805yves 2806

FIG. 7.1– Un exempledetablepourla rechercheentable

desimplicite doivent etreconsiderescommeaussiimportantsquecelui de l’efficacite danslaconceptiondesalgorithmes.

7.2 Rechercheen table

Avec les tableaux,on peutaussifaire destables.Une tablecontientdesinformationssurcertainescles.Parexemple,la tablepeutetreunannuairetelephonique.Lesclessontlesnomsdesabonnes.L’information a rechercherest le numero de telephone.Une tableestdoncunensembledepairesa nom� numerob . Il y aplusieursmanieresd’organisercettetable: untableaud’enregistrement,unelisteou unarbre(commenousle verronsplustard).Pourl’instant,noussupposonsla tabledecritepar deuxtableauxnom et tel , indicesen parallele, le numero detelephonedenom[i] etanttel[i] .

7.2.1 La recherchesequentielle

La premiere methodepour rechercherun numero de telephoneconsistea faire une re-cherchesequentielle(ou lineaire).On examinesuccessivementtousleselementsdela tableeton regardesi on trouve un abonne dunomvoulu.Ainsi

static int recherche (String x) {

for (int i = 0; i < N; ++i)if (x.equals(nom[i]))

return tel[i];return -1;

}

qui peutaussis’ecrire


int i = 0;while (i < N && !x.equals(nom[i]))

++i;if (i < N)

return tel[i];else

return -1;}

Si ona la place,uneautrepossibilite estdemettreunesentinelleauboutdela table.

7.2. RECHERCHEEN TABLE 47


int i = 0;nom[N] = x; tel[N] = -1;while (! x.equals(nom[i]))

++i;return tel[i];

}

L’ ecrituredelaprocedurederecherchedansla tabledesnomsestalorsplusefficace,caronpeutremarquerquel’on ne fait plusqu’un testla ou on en faisaitdeux.La recherchesequentielleestaussiappeleerecherchelineaire,car il estfacile de montrerquel’on fait c ^ � operationsenmoyenne,et c operationsdansle pire cas.Surunetablede10000elements,la rechercheprend5000operationsenmoyenne,soit 5ms.

Voici un programmecompletutilisantla recherchelineaireentable.

class Table {

final static int N = 6;static String nom[] = new String[N+1];static int tel[] = new int[N+1];

static void initialisation() {nom[0] = "paul"; tel[0] = 2811;nom[1] = "roger"; tel[1] = 4501;nom[2] = "laure"; tel[2] = 2701;nom[3] = "anne"; tel[3] = 2702;nom[4] = "pierre"; tel[4] = 2805;nom[5] = "yves"; tel[5] = 2806;

}


for (int i = 0; i < N; ++i)if (x.equals(nom[i]))


}

public static void main (String args[]) {

Initialisation();if (args.length == 1)

System.out.println (Recherche(args[0]));}

}

7.2.2 La recherchedichotomique

Une autretechniquede rechercheen tableestla recherche dichotomique. Supposonsquela tabledesnomssoit triee en ordre alphabetique(commel’annuairedesPTT). Au lieu derecherchersequentiellement,on comparela cle a chercheraunomqui setrouve aumilieu dela tabledesnoms.Si c’est le meme,on retournele numero de telephonedu milieu, sinononrecommencesurla premieremoitie (ou la deuxieme)si le nomrecherche estpluspetit (ouplusgrand)quele nomrange aumilieu dela table.Ainsi


static void initialisation() {

nom[0] = "anne"; tel[0] = 2702;nom[1] = "laure"; tel[1] = 2701;nom[2] = "paul"; tel[2] = 2811;nom[3] = "pierre"; tel[3] = 2805;nom[4] = "roger"; tel[4] = 4501;nom[5] = "yves"; tel[5] = 2806;

}

static int rechercheDichotomique (String x) {

int i, g, d, cmp;

g = 0; d = N-1;do {

i = (g + d) / 2;cmp = x.compareTo(nom[i]);if (cmp == 0)

return tel[i];if (cmp < 0)

d = i - 1;else

g = i + 1;} while (g <= d);return -1;

}

Le nombredfe decomparaisonspourunetabledetaille c esttel que dfe 5 �hgidkj eml Sonet d _ 5 � . Donc d eqp KMLAN S *�cr, . (Dorenavant, KMLAN S *�cr, serasimplementecrit KMLANRc .) Si latablea 10000elements,on aura d esp �)9 . C’estdoncun gainsensiblepar rapportaux5000operationsnecessairespourla recherchelineaire.Biensur, la recherchelineaireestplussimplea programmer, et seradoncutiliseepourlespetitestables.Pourdestablesplusimportantes,larecherchedichotomiqueestplusinteressante.

On peutmontrerqu’un tempssub-logarithmiqueestpossiblesi on connaıt la distributiondesobjets.Parexemple,dansl’annuairedu telephone,ou dansun dictionnaire,onsaita prioriqu’unnomcommençantparla lettreV setrouveraplutot versla fin. Ensupposantladistributionuniforme,on peutfaireuneregledetrois pour trouver l’indice del’ elementdereferencepourla comparaison,aulieu dechoisir le milieu, et on suit le restedel’algorithmedela recherchedichotomique.Cettemethodeestla recherche par interpolation. Alors le tempsderechercheesten 8G*�KMLANtKMLANucv, , c’est-a-dire4 operationspourunetablede10000elements,et5 operationsjusqu’a � 6 ] entreesdansla table!

7.2.3 Insertion dansune table

Dansla recherchelineaireoupardichotomie,onnes’estpaspreoccupe del’insertiondansla table d’elementsnouveaux.C’est par exempletres peu souvent le caspour un annuairetelephonique.Mais celapeutetrefrequentdansd’autresutilisations,commela tabledesusa-gersd’un systemeinformatique.Essayonsde voir commentorganiserl’insertion d’elementsnouveauxdansunetable,dansle casdesrecherchessequentielleet dichotomique.

Pourle cassequentiel,il suffit de rajouterau bout de la tablel’ elementnouveau,s’il y ala place.S’il n’y a pasdeplace,on appelleuneprocedureerreur qui imprimerale messaged’erreurdonne enparametreet arreterale programme.Ainsi


void insertion (String x, int val) {

++n;if (n >= N) then

erreur ("De’bordement de la table");nom[n] = x;tel[n] = val;

}

L’insertionsefait doncentempsconstant,en 8P*w�/, . Dansle casdela recherchepardichotomie,il fautmaintenirla tableordonnee.Pourinsererunnouvel elementdansla table,il fautd’abordtrouver sonemplacementparunerecherchedichotomique(ou sequentielle),puispoussertousleselementsderrierelui pourpouvoir insererle nouvel elementaubonendroit.CelapeutdoncprendreKMLANR�4gi� operations.L’insertiondansunetableordonneede � elementsprenddoncun temps8P*J��, .7.2.4 Hachage

Une autremethodede rechercheen table est le hachage. On utilise une fonction x del’ensembledescles(souventdeschaınesdecaracteres)dansun intervalle d’entiers.Pourunecle B , x�*JBy, est l’endroit ou l’on trouve B dansla table.Tout sepasseparfaitementbien si xestuneapplicationinjective. Pratiquement,on nepeutarriver a atteindreceresultat.On tentealorsdes’enapprocheret on chercheaussia minimiserle tempsdecalcul de x�*JBy, . Ainsi unexempledefonctiondehachageestx�*JBy, 5 *JB<�z��;|{~}$� � g�B<��;|{~}$� S g��-�-�:g�B[� ��J,I��L��c

On prendd’habitude { 5 �E�A@ ou { 5 �A�A? et on supposeque la taille de la table cestun nombrepremier. Pourquoi? D’abord,il fautconnaıtre la structuredesordinateurspourcomprendrele choix de { commeunepuissancede 2. En effet, les multiplicationspar despuissancesde 2 peuvent sefaire tresfacilementpardesdecalages,puisqueles nombressontrepresentesenbase2. Engeneral,danslesmachines“modernes”,cetteoperationestnettementplus rapidequela multiplication parun nombrearbitraire.Quanta prendrec premier, c’estpour eviter touteinterferenceentrelesmultiplicationspar { et la division par c . En effet, siparexemple { 5 c 5 �A�A? , alors xm*JB�, 5 B<� �� et la fonction x nedependraitquedu derniercaracterede B . Le but estdoncd’avoir unefonction x de hachagesimplea calculeret ayantunebonnedistribution surl’intervalle � 6 ��c��|�� . (Attention: il seratechniquementplussimpledanscettesectionsurle hachagedesupposerquelesindicesdestableauxvarientsur � 6 ��c��au lieu de �z��c�� ). Le calcul de la fonction x se fait par la fonction h(x, l) , ou l est lalongueurdela chaınex ,

static int h (String x) {

int r = 0;for (int i = 0; i < x.length(); ++i)

r = ((r * B) + x.charAt(i)) % N;return r;

}

Doncla fonction x donnepourtoutecle B uneentreepossibledansla table.On peutalorsverifier si B 5��'�:� ��x�*JBy,`� . Si oui, la rechercheestterminee.Si non,celasignifie quela tablecontientuneautrecle B�� telleque xm*JB��, 5 xm*JBy, . On dit alorsqu’il y aunecollision, et la tabledoit pouvoir gererlescollisions.Unemethodesimpleestdelister lescollisionsdansunetablecol parallelea la tablenom. La tabledescollisionsdonnerauneautreentree � dansla tabledesnomsou peutsetrouver la cle recherchee.Si onnetrouvepasla valeur B acettenouvelleentree


paul

roger

laure

anne

pierre

yves

laurent

�01234567891011121314

nom*J�w,pierre

paul

rogerlaure

anneyves

laurent

tel *J�o,2805

00

28110

45012701

000

270228068064

col *J�o,-1-1-1-1-11211-1-1-1-1-110 collisions

FIG. 7.2– Hachageparcollisionsseparees

� , on continueraavecl’entree �� donneepar �`� 5s�� .� . Et on continuetantque �A�� F35 �Q� .La rechercheestdonneepar


for (int i = h(x); i != -1; i = col[i])if (x.equals(nom[i]))


}

Ainsi la procedurederechercheprenduntempsauplusegala la longueurmoyennedesclassesd’equivalencedefiniessur la tablepar la valeurde xm*JB�, , c’est-a-dire a la longueurmoyennedeslistesdecollisions.Si la fonctiondehachageestparfaitementuniforme,il n’y aurapasdecollision et on atteindratout elementenunecomparaison.Cecasesttrespeuprobable.Il y adesalgorithmescompliquespourtrouverunefonctiondehachageparfaitesurunetabledonneeet fixe.Mais si le nombremoyend’elementsayantmemevaleurdehachageest V 5 c ^)� , ou� estgrossomodole nombredeclassesd’equivalencesdefiniespar x , la rechercheprendraun temps c ^)� . Le hachagene fait doncquereduired’un facteurconstantle tempspris parla recherchesequentielle.L’int eret du hachageestqu’il estsouvent tresefficace,tout en etantsimpleaprogrammer.

L’insertiondansunetableavecle hachageprecedentestplusdelicate.En effet, on devraitrapidementfusionnerdesclassesd’equivalencesde la fonction de hachage,car il faut bien


mettrelesobjetsa inserera unecertaineentreedansla tablequi correspondelle-memea unevaleurpossibledela fonctiondehachage.Unesolutionsimpleestdesupposerla tabledetaille� telle que �|�i��i� �y�2� . Pourinsererun nouvel element,on regardesi l’entreecalculeeparla fonction x estlibre, sinononmetle nouvel elementauboutdela table,etonchaınelescolli-sionsentreellesparunnouveautableaucol . (Lestableauxnom, tel etcol sontmaintenantde taille Nmax). On peutchoisirdemettrele nouvel elemententeteou a la fin de la liste descollisions; ici on le mettraentete.Remarque: a la page81, touslesoutils serontdeveloppespourenchaıner lescollisionspardeslistes; commenousneconnaissonsactuellementquelestableauxcommestructurede donnee,nousutilisonsle tableaucol . L’insertion d’un nouvelelementdansla tables’ecrit

static void insertion (String x, int val) {

int i = h(x);

if (nom[i] == null) {nom[i] = x;tel[i] = val;

} elseif (n >= Nmax)

erreur ("D ebordement de la table");else {

nom[n] = x;tel[n] = val;col[n] = col[i]; // Onmetla nouvelleentreeentetecol[i] = n; // dela listedescollisionsdesa++n; // classed’equivalence.

}}

Au debut, on supposen 5 N, nom� �.� 5 "" (chaınevide) et col � �.� 5 �� pour 6 �7�>� N . Laprocedured’insertionestdonctresrapideetprendun tempsconstant8P*w�/, .

Uneautretechniquedehachageestdefaireunhachagea adressage ouvert. Le principeenesttressimple.Au lieu degererdescollisions,si onvoit uneentreeoccupeelorsdel’insertion,onrangela cle a l’entreesuivante(modulola taille dela table).Onsupposeunevaleurinterditedanslescles,parexemplela chaınevide ’’ , pourdesigneruneentreelibre dansla table.Lesproceduresd’insertionet derecherches’ecrivent tressimplementcommesuit


int i = h(x);

while (nom[i] != null) {if (x.equals(nom[i]))

return tel[i];i = (i+1) % N;

}return -1;

}

static void insertion (String x, int val) {int i;

if (n >= N)erreur ("De’bordement de la table");

++n;


paul

roger

laure

anne

pierre

yvon

laurent

�01234567891011121314

nom*J�o,pierre

paul

rogerlaureanne

laurent

yvon

tel *J�o,2805

00

28110

4501270127028064

000

8065

FIG. 7.3– Hachageparadressageouvert


i = h(x);while ((nom[i] != null) && ! x.equals(nom[i]))

i = (i+1) % N;nom[i] = x;tel[i] = val;

}

Dansle casou la cle a inserersetrouverait deja dansla table,l’ancien numero de telephoneest ecrase, ce qui estce quel’on veut dansle caspresent.Il est interessantde reprendrelesmethodesderechercheentabledeja vueset deseposerceprobleme.Plusinteressant,on peutsedemandersi cettemethodesimpledehachagelineaireesttresefficace,etsi onnerisquepas,enfait,d’aboutiraunerecherchesequentiellestandard.Notreproblemeestdoncdecomprendrela contiguıte dela fonctiondehachage,et la chancequel’on peutavoir pourunevaleurdonneede xm*JBy, d’avoir aussilesentreesx�*JBy,�g�� , xm*JB�,�gv� , x�*JBy,�gvY . . . occupees.Onpeutdemontrerque,si la fonction de hachageestuniformeet si 5q� ^ � �y�� est le taux d’occupationde latable,le nombred’operationsest:

– � ^ �¡g7� ^ *.�¢*w�¡�� <,1, pourunerechercheavecsucces,– � ^ �¡g7� ^ *.�¢*w�¡�� <, S , pourunerechercheavecechec.

Doncsi 5 � ^ Y , on fait 2 ou 5 operations,si 5 D 62£ , on enfait 5 ou 50.La conclusionestdoncque,si on estpret a grossirla tablede50%,le tempsderechercheesttresbon,avecunemethodedeprogrammationtressimple.

Une methodeplus subtile,que l’on peut ignorer en premiere lecture,est d’optimiser lehachagea adressageouvert precedenten introduisantun deuxiemeniveaude hachage.Ainsiau lieu de considerer l’ elementsuivant dansles proceduresde rechercheet d’insertion,onchangeralesinstructions

i := (i+1) mod Nmax;

en

i := (i+u) mod Nmax;

ou ¤ 5 x S *JBm��, estunedeuxiemefonctiondehachage.Poureviterdesphenomenesdeperiodicite,il vautmieuxprendre¤ et � �y�� premiersentreeux.Unemethodesimple,comme� �y�� estdejasupposepremier, estdefaire ¤��¥� ��2� . Parexemple,x S *JB��., 5 @m�4*JB[� ��y��L��P@�, estunefonc-tion rapideacalculer, etqui tientcomptedestroisderniersbitsde B . Onpeutsemettretoujoursdansle casdedistributionsuniformes,etdefonctionsx et x S “independantes”.Alors onmontrequele nombred’operationsestenmoyenne:

– *w� ^ <,F;4KMLAN*w� ^ *w�¡�� [,1, pourunerechercheavecsucces,– � ^ *w�F�� [, pourunerechercheavecechec,

enfonctiondu tauxd’occupation dela table.Numeriquement,pour 5 @ 62£ , on fait 3 ou 5operations,pour 5 DAD £ , on fait 7 ou 100.Cequi esttout a fait raisonnable.

Le hachageesttresutilise pourlescorrecteursd’orthographe.McIlroy1 acalcule que,dansun article scientifiquetypique,il y a environ 20 erreursd’orthographe(c’est-a-diredesmotsn’apparaissantpasdansundictionnaire),etqu’unecollisionpour100papiersestacceptable.Ilsuffit doncdefaireun correcteurprobabilistequi nerisquedesetromperqu’un cassur2000.Au lieu degardertout le dictionnaireenmemoire,et doncconsommerbeaucoupdeplace,il autilise un tableaude � bits. Il calcule V fonctions x " dehachageindependantespour tout mot¦ , et regardesi les V bits positionnesen x " * ¦ , valentsimultanement1. On estalorssur qu’unmot n’estpasdansle dictionnairesi la reponseestnegative, maison pensequ’on a debonneschancesqu’il y soit si la reponseestoui. Un calcul simplemontrequela probabilite § pourqu’un mot d’un dictionnairede � entreesnepositionnepasun bit donne est § 5�¨ ��© U l . Laprobabilite pour qu’unechaıne quelconquesoit reconnuecommeun mot du dictionnaireest*w�¡��§k, U . Si on veutquecettedernierevaille � ^ � 6A6A6 , il suffit deprendre§ 5 � ^ � et V 5 �A� .

1DougMcIlroy etait le chefdel’ equipequi a fait le systemeUnix a Bell laboratories.


On a alors � ^ � 5 V ^ K$ªF� 5 �E��@�= . Pourun dictionnairede25000mots,il fautdonc400000bits(50kO),et,pourunde200000mots,if faut3200000bits(400kO).McIlroy avait unpdp11et 50 kO etait insupportable.Il a compresse la tableennestockantquelesnombresde0 entredeux1, cequi aramene la taille a30kO.Actuellement,la commandespell dusystemeUnixutilise V 5 �A� et unetablede400000bits.2

2Paul Zimmermanna remarque que les dictionnairesfrancais sontplus longsque les dictionnairesanglaisacausedesconjugaisonsdesverbes.Il a reprogramme la commandespell en francais en utilisant desarbresdigitauxqui partagentlesprefixeset suffixesdesmotsd’un dictionnairefrancaisde200000motsLe dictionnairetient alorsdansunememoirede500kO. Sonalgorithmeestaussirapideet exact(nonprobabiliste).

Chapitr e 8

Recursivit e

Lesdefinitionsparrecurrencesontassezcourantesenmathematiques.Prenonsle casdelasuitedeFibonacci,definiepar� _ 5 � � 5 �� 5 � � � g«� � S pour �¬W�Onobtientdoncla suite1, 1, 2, 3, 5, 8, 13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,.. .Nousallonsvoir quecesdefinitionss’implemententtressimplementeninformatiqueparlesdefinitionsrecursives.

8.1 Fonctionsr ecursives

8.1.1 Fonctionsnumeriques

Pourcalculerla suitedeFibonacci,unetranscriptionlitt eraledela formuleestla suivante:

static int fib (int n) {

if (n <= 1)return 1;

elsereturn fib (n-1) + fib (n-2);

}

fib estunefonctionqui utilise sonproprenomdansla definition d’elle-meme.Ainsi, si l’ar-gument � estplus petit que1, on retournecommevaleur1. Sinon,le resultatest fib *J��/,Ag fib *J�Q�®��, . Il estdoncpossibleenJava,commeenbeaucoupd’autreslangages(saufFor-tran),dedefinir detellesfonctionsrecursives. D’ailleurs,toutesuite aJ� b definieparrecurrences’ecrit decettemaniereenJava,commele confirmentlesexemplesnumeriquessuivants: fac-torielleet le triangledePascal.

static int fact(int n) {

if (n <= 1)return 1;

elsereturn n * fact (n-1);

}

static int C(int n, int p) {

if ((n == 0) || (p == n))

55

56 CHAPITRE8. RECURSIVITE

Fib *J9(,Fib *.Y�,

Fib *.��,Fib *w�/, Fib * 6 ,

Fib *w�/,Fib *.��,

Fib *w�/, Fib * 6 ,

FIG. 8.1– Appelsrecursifspourfib *J9(,return 1;

elsereturn C(n-1, p-1) + C(n-1, p);

}

On peutsedemandercommentJava s’y prendpour faire le calcul desfonctionsrecursives.Nousallonsessayerde le suivre sur le calcul de ¯'°�±�*J9(, . Rappelonsnousqueles argumentssonttransmisparvaleurdansle caspresent,etdoncqu’unappeldefonctionconsistea evaluerl’argument,puisaselancerdansl’executiondela fonctionavecla valeurdel’argument.Donc

fib(4) -> fib (3) + fib (2)-> (fib (2) + fib (1)) + fib (2)-> ((fib (1) + fib (1)) + fib (1)) + fib(2)-> ((1 + fib(1)) + fib (1)) + fib(2)-> ((1 + 1) + fib (1)) + fib(2)-> (2 + fib(1)) + fib(2)-> (2 + 1) + fib(2)-> 3 + fib(2)-> 3 + (fib (1) + fib (1))-> 3 + (1 + fib(1))-> 3 + (1 + 1)-> 3 + 2-> 5

Il y a doncun bonnombred’appelssuccessifsa la fonction fib (9 pour ¯'°�±T*J9(, ). Comptonsle nombred’appelsrecursifs ² pour cettefonction. Clairement ² _ 5 ² � 5 � , et ² 5�mgv² � � gr² � S pour �¬W� . Enposant² � 5 ² g¥� , onendeduitque ² � 5 ² � � � gv² � � Spour ��WX� , ²³� � 5 ²³�_ 5 � . D’ou ²³� 5 ��; fib *J��, , et doncle nombred’appelsrecursifs² vaut �®; fib *J��,t�i� , c’est a dire 1, 1, 3, 5, 9, 15, 25,41, 67,109,177,287,465,753,1219,1973,3193,5167,8361,13529,21891,.. . Le nombred’appelsrecursifsestdonctres eleve,d’autantplusqu’il existeunemethodeiterative simpleencalculantsimultanementfib *J��, etfib *J��´�/, . En effet, onaun calcullineairesimpleµ

fib *J��,fib *J��´�/,·¶ 5 µ � �� 6 ¶ µ

fib *J�|�¸�/,fib *J�|��,·¶

Cequi donnele programmeiteratif suivant

static int fib(int n) {

8.1. FONCTIONSRECURSIVES 57

int u, v;int u0, v0;int i;

u = 1; v = 1;for (i = 2; i <= n; ++i) {

u0 = u; v0 = v;u = u0 + v0;v = v0;

}return u;

}

Pourresumer, unebonneregleestdenepastropessayerdesuivredanslesmoindresdetailslesappelsrecursifspourcomprendrele sensd’unefonctionrecursive. Il vautmieuxengeneralcomprendresynthetiquementla fonction.La fonction de Fibonacciestun casparticuliercarsoncalcul recursifestparticulierementlong. Mais ce n’est pasle casen general.Non seule-ment,l’ ecriturerecursive peutserevelerefficace,maiselle esttoujoursplusnaturelleet doncplusesthetique.Elle nefait quesuivre lesdefinitionsmathematiquesparrecurrence.C’estunemethodedeprogrammationtrespuissante.

8.1.2 La fonction d’Ack ermann

La suitedeFibonacciavait unecroissanceexponentielle.Il existedesfonctionsrecursivesqui croissentencoreplus rapidement.Le prototypeest la fonction d’Ackermann.Au lieu dedefinir cettefonctionmathematiquement,il estaussisimpled’endonnerla definition recursiveenJava

static int ack(int m, int n) {

if (m == 0)return n + 1;

elseif (n == 0)

return ack (m - 1, 1);else

return ack (m - 1, ack (m, n - 1));}

On peutverifier que ��:¹ * 6 �1��, 5 �®g7��:¹ *w��1��, 5 �®g¥��:¹ *.��1��, p �¡ºt��:¹ *.Y��1��, p � ��:¹ *J9¢�1��, p � 2 � � �»St¼ Donc �¢��¹ *.��E�/, p �¢�:¹ *J9¢�19(, p ��½1¾1¾ � ½QW� 6A¿ _ , c’esta dire le nombred’atomesdel’univers.

8.1.3 Recursionimbriqu ee

La fonction d’Ackermanncontientdeux appelsrecursifsimbriques, c’est ce qui la faitcroıtre si rapidement.Un autreexempleestla fonction91 deMacCarthy


static int f(int n) {

if (n > 100)return n - 10;

elsereturn f(f(n+11));

}

Ainsi, lecalculdef *.DA?�, donnef *.DA?�, 5 f * f *w� 6 =A,1, 5 f *.D�=A, 5 �-�-� f *w� 6A6 , 5 f * f *w�A�A�/,1, 5f *w� 6 �/, 5 D�� . On peutmontrerquecettefonctionvaut91 si ��À� 6A6 et �Á�7� 6 si ��WÀ� 6A6 .Cettefonctionanecdotique,qui utilise la recursivite imbriquee,estinteressantecaril n’estpasdu tout evidentqu’unetelle definition donnetoujoursun resultat.1 Parexemple,la fonctiondeMorris suivante

static int g(int m, int n) {

if (m == 0)return 1;

elsereturn g(m - 1, g(m, n));

}

Quevautalorsg *w�� 6 , ?Eneffet,onag *w�� 6 , 5 g * 6 � g *w�� 6 ,1, . Il fautsesouvenirqueJavapasselesargumentsdesfonctionsparvaleur. On calculedonctoujoursla valeurdel’argumentavantdetrouver le resultatd’unefonction.Dansle caspresent,le calculdeg(1,0) doit recalculerg(1, 0) . Et le calculneterminepas.

8.2 Indecidabilite de la terminaison

Les logiciens Godel et Turing ont demontre dansles annees30 qu’il etait impossibled’esperer trouver un programmesachanttestersi une fonction recursive terminesoncalcul.L’arret d’un calcul esten effet indecidable. Danscettesection,nousmontronsqu’il n’existepasde fonction qui permettede testersi une fonction Java termine.Nous presentonscettepreuve sousla formed’unepetitehistoire:

Le responsabledestravauxpratiquesd’Informatiqueena assezdesprogrammesqui calculentindefinimentecritspardeselevespeuexperimentes.Celal’oblige a chaquefois a desmanipu-lationscompliqueespourstoppercesprogrammes.Il voit alorsdansun journalspecialise unepublicite :

Ne laissezplusbouclervosprogrammes! Utiliseznotre fonctiontermine(o) .Elle prendcommeparametre le nomd’un objet et repondtrue si la proceduref decetobjetnebouclepasindefinimentet false sinon.En n’utilisant quelesprocedurespourlesquellestermine repondtrue , vouseviteztouslesproblemesdenonterminaison.D’ailleurs, voici quelquesexemples:

class Turing {

static boolean termine (Object o) {// determinela terminaisondeo.f()boolean resultat;// contenubreveteparle vendeurreturn resultat;

}

1Certainssystemespeuventdonnerdesresultatspartiels,parexemplele systemeSYNTOX deFrancois Bour-donclequi arrive a traiterle casdecettefonction

8.2. INDECIDABILIT E DE LA TERMINAISON 59

}

class Facile {void f () {}

}

class Boucle {void f () {

for (int i = 1; i > 0; ++i);

}}

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

Facile o1 = new Facile();System.out.println (Turing.termine(o1));Boucle o2 = new Boucle();System.out.println (Turing.termine(o2));

}}

pour lesquelstermine(o) repondtrue puisfalse .

Impressionne parla publicite, le responsabledestravauxpratiquesachetea prix d’or cettepetitemerveille etpensequesavie d’enseignantvaetreenfintranquille.Un eleve lui fait toute-fois remarquerqu’il necomprendpasl’acquisitionfaiteparle Maıtre avecla classesuivante:

class Absurde {void f () {

while (Turing.termine(this));

}

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

Absurde o3 = new Absurde();System.out.println (Turing.termine(o3));

}}

Si la procedureo3.f boucleindefiniment,alorstermine(o3) 5 false . Donc la bouclewhile deo3.f s’arreteeto3.f termine.Sinon,si la procedureo3.f nebouclepasindefini-ment,alorstermine(o3) 5 true . La bouclewhile precedenteboucleindefiniment,et laprocedureo3.f boucleindefiniment.Il y adoncunecontradictionsurlesvaleurspossiblesdetermine(o3) . Cetteexpressionnepeutetredefinie.Ayantnote le mauvaisespritdel’El eve,le Maıtre conclutqu’onnepeutdecidementpasfaireconfiancea la pressespecialisee!

L’histoireestpresquevraie.Le Maıtres’appelaitDavid Hilbert etvoulaitmontrerla validitede sa thesepar desmoyensautomatiques.L’El eve impertinentetait Kurt Godel. Le tout sepassaitvers1930.GraceaGodel,ons’estrenducomptequetouteslesfonctionsmathematiquesnesontpascalculablesparprogramme.Par exemple,il y a beaucoupplusdefonctionsde Â c(entiersnaturels)dansÂ c quedeprogrammesqui sontenquantitedenombrable.Godel,Turing,ChurchetKleenesontparmilesfondateursdela theoriedela calculabilite.

Pour etre plus precis, on peut remarquerque nousdemandonsbeaucoupa notre fonc-tion termine , puisqu’elle prend en argumentun objet (en fait une “adressememoire”),desassemblepeut-etre la procedurecorrespondante,et decidede sa terminaison.Sinon,elle


nepeutquelancerl’executiondesonargumentet nepeutdonctestersaterminaison(quandilne terminepas).Un resultatplusfort peutetremontre : il n’existepasdefonctionprenantenargumentle sourcedetouteprocedure(entantquechaınedecaracteres)et decidantdesater-minaison.C’estceresultatqui estcourammentappele l’indecidabilite del’arret.Mais montrerla contradictionenJava estalorsbeaucoupplusdur.

8.3 Proceduresr ecursives

Lesprocedures,commelesfonctions,peuventetrerecursives,etcomporterunappelrecursif.L’exemple le plus classiqueest celui des tours de Hanoi. On a 3 piquetsen facede soi,numerotes 1, 2 et 3 de la gauchevers la droite, et � rondellesde tailles toutesdifferentesentourantle piquet1, formantun coneavec la plusgrosseenbaset la pluspetiteenhaut.Onveutamenertouteslesrondellesdu piquet1 aupiquet3 enneprenantqu’uneseulerondelleala fois, et ens’arrangeantpourqu’a tout momentil n’y ait jamaisunerondellesousuneplusgrosse.La legendedit quelesbonzespassaientleur vie a Hanoi a resoudreceproblemepour� 5 ?:9 , cequi leurpermettaitd’attendrel’ ecroulementdu templedeBrahma,etdoncla fin dumonde(cettelegendefut inventeeparle mathematicienfrancaisE. Lucasen1883).Un raison-nementparrecurrencepermetdetrouver la solutionenquelqueslignes.Si �¬�X� , le problemeesttrivial. Supposonsmaintenantle problemeresolupour ��´� rondellespourallerdu piquet� aupiquet Ã . Alors, il y aunesolutiontresfacilepourtransferer � rondellesde � en Ã :

1- onameneles ��´� rondellesdu hautde � surle troisiemepiquet V 5 ?Ä�r�m�|Ã ,2- onprendla granderondelleenbasde � et on la mettouteseuleen Ã ,3- onameneles ��´� rondellesde V en Ã .

Cecis’ecrit

static void hanoi(int n, int i, int j) {

if (n > 0) {hanoi (n-1, i, 6-(i+j));System.out.println (i + " -> " + j);hanoi (n-1, 6-(i+j), j);

}}

Cesquelqueslignesdeprogrammemontrentbiencommentengeneralisantle probleme,c’est-a-dire aller de tout piquet � a tout autre Ã , un programmerecursif de quelqueslignes peutresoudreun problemea priori complique. C’est la force de la recursionet du raisonnementpar recurrence.Il y a bien d’autresexemplesde programmationrecursive, et la puissancede cettemethodede programmationa ete etudiee dansla theorie dite de la recursivite quis’est developpee bien avant l’apparition de l’informatique (Kleene[25], Rogers[45]). Lemot recursivite n’a qu’un lointain rapport avec celui qui est employe ici, car il s’agissaitd’etablirunetheorieabstraitede la calculabilite, c’est a dire dedefinir mathematiquementlesobjetsqu’on sait calculer, et surtoutceuxqu’on nesaitpascalculer. Mais l’id eeinitiale de larecursivite estcertainementaattribueraKleene(1935).

8.4 Fractales

Consideronsd’autresexemplesdeprogrammesrecursifs.Desexemplesspectaculairessontle casdefonctionsgraphiquesfractales.Nousutilisonslesfonctionsgraphiquesdu Macintosh(cf. page30).Un premierexemplesimpleestle flocondevon Koch[11] qui estdefini commesuit

Le flocond’ordre0 estun triangleequilateral.Le flocond’ordre1 estcememetriangledont lescotessontdecoupesentrois et

8.4. FRACTALES 61

Hanoi(n-1, i, 6-(i+j))

1 2 3

Aller de i vers j

1 2 3

Hanoi (n-1, 6-(i+j), j)

1 2 3

1 2 3

FIG. 8.2– LestoursdeHanoi


FIG. 8.3– Floconsdevon Koch

surlequels’appuieun autretriangleequilateralaumilieu.Le flocon d’ordre ��gs� consistea prendrele flocon d’ordre � en appliquantlamemeoperationsurchacundesescotes.

Le resultatressembleeffectivementa unflocondeneigeidealise.L’ ecrituredu programmeestlaisse enexercice.On y arrive tressimplementenutilisantlesfonctionstrigonometriquessinetcos . Un autreexempleclassiqueestla courbeduDragon.La definitiondecettecourbeestlasuivante: la courbedu Dragond’ordre1 estunvecteurentredeuxpointsquelconques§ et Å ,la courbeduDragond’ordre � estla courbeduDragond’ordre �Æ�� entre§ et ² suivie delamemecourbed’ordre �G�� entre² et Å (a l’envers),ou §Q²�Å estle triangleisocelerectangleen ² , et ² estadroiteduvecteur§kÅ . Donc,si § et Å sontlespointsdecoordonnees *JBm�1C', et*�Ç¢�1È�, , lescoordonnees *J�m�1É�, de ² sont� 5 *JBPg«Ç(, ^ �¡gÊ*JÈI�vC¢, ^ �É 5 *JC�g�È�, ^ �Ä�¸*�Çk�rBy, ^ �La courbeseprogrammesimplementpar

static void dragon(int n, int x, int y, int z, int t) {

int u, v;

if (n == 1) {moveTo (x, y);lineTo (z, t);

} else {u = (x + z + t - y) / 2;v = (y + t - z + x) / 2;dragon (n-1, x, y, u, v);dragon (n-1, z, t, u, v);

}}

8.4. FRACTALES 63

FIG. 8.4– La courbeduDragon

Si on calculedragon *.� 6 �� 6 �� 6 ��A� 6 ��A� 6 , , on voit apparaıtre un petit dragon.Cettecourbeestce quel’on obtienten pliant 10 fois unefeuille de papier, puis en la depliant.Une autreremarqueestquece trace leve le crayon,et que l’on preferesouvent ne paslever le crayonpourla tracer. Pourcefaire,nousdefinissonsuneautreproceduredragonBis qui dessinelacourbea l’envers.La proceduredragon seradefinie recursivementen fonctiondedragonetdragonBis . Dememe,dragonBis estdefinierecursivemententermesdedragonBiset dragon . On dit alorsqu’il y aunerecursivite croisee.

static void dragon (int n, int x, int y, int z, int t) {int u, v;


} else {u = (x + z + t - y) / 2;v = (y + t - z + x) / 2;dragon (n-1, x, y, u, v);dragonBis (n-1, u, v, z, t);

}}

static void dragonBis(int n, int x, int y, int z, int t) {

int u, v;


} else {


u = (x + z - t + y) / 2;v = (y + t + z - x) / 2;dragon (n-1, x, y, u, v);dragonBis (n-1, u, v, z, t);

}

}

Il y a bien d’autrescourbesfractalescommela courbede Hilbert, courbede Peanoquirecouvreuncarre, lesfonctionsdeMandelbrot.Cescourbesserventenimageriepourfairedesparcours“aleatoires”desurfaces,etdonnentdesfondsesthetiquesa certainesimages.

Chapitr e 9

Tris sequentielset r ecursifs

9.1 Qu’est-cequ’un tri ?

On supposequ’on sedonneunesuitede c nombresentiers a�� " b , et on veut lesrangerenordrecroissantausenslarge.Ainsi, pour c 5 � 6 , la suiteaw�E@��Y��E� 6 ��A��D��Y��/�A�A�E�/Y��Ë�AY��@�bdevra devenir a.Y��Y��@��D��E� 6 �E�A��E�/Y��/�E@��Y��2��bCeproblemeestun classiquede l’informatique.Il a ete etudie endetail, cf. la moitie du livrede Knuth [30]. En tant qu’algorithmepratique,on le rencontresouvent. Par exemple,il fautetablirle classementdecertainseleves,mettreenordreundictionnaire,trier l’index d’un livre,faireunesortielisible d’un correcteurd’orthographe,. . . Il faudrabienfairela distinctionentrele tri d’un grandnombred’elements(plusieurscentaines),et le tri de quelqueselements(unpaquetdecartes).Danscederniercas,la methodeimportepeu.Un algorithmeamusant,bogo-tri, consistea regardersi le paquetde cartesestdeja ordonne. Sinon,on le jette par terre.Eton recommence.Au boutd’un certaintemps,on risqued’avoir lescartesordonnees.Bien sur,le bogo-tri peutne passeterminer. Uneautretechniquefrequemmentutiliseeavec un jeu decartesconsistea regarders’il n’y a pasunetranspositiona effectuer. Desqu’on envoit uneafaire,on la fait et on recommence.Cettemethodemarchetresbiensurunebonnedistributiondecartes.

Plus serieusement,il faudratoujoursavoir a l’esprit que le nombred’objets a trier estimportant.Ce n’estpasla peinede trouver unemethodesophistiqueepour trier 10 elements.Pourtant,les exemplestraitesdansun courssont toujoursde taille limit ee,pour desraisonspedagogiquesil n’est paspossiblede representerun tri sur plusieursmilliers d’elements.Letri, parsesmultiplesfacettes,estun tresbonexempled’ecole.Engeneral,onexigeraquele trisefassein situ, c’est-a-direquele resultatsoit aumemeendroitquela suiteinitiale. On peutbien sur trier autrechosequedesentiers.Il suffit de disposerd’un domainede valeursmunid’unerelationd’ordretotal.On peutdonctrier descaracteres,desmotsenordrealphabetique,desenregistrementsselonun certainchamp.On supposera,pour simplifier, qu’il existe uneoperationd’echangeouplussimplementd’affectationsurleselementsdela suitea trier. C’estpourquoinousprendronsle casdevaleursentieres.

9.2 Methodesde tri elementaires

Danstoutcequi suit,onsupposequel’on trie desnombresentiersetqueceux-cisetrouventdansuntableau� . L’algorithmedetri le plussimpleestle tri par selection. Il consisteatrouver

65

66 CHAPITRE9. TRIS SEQUENTIELSET RECURSIFS

18 3 10 25 9 3 11 13 23 8� �3 18 10 25 9 3 11 13 23 8� �3 3 10 25 9 18 11 13 23 8� �3 3 8 25 9 18 11 13 23 10� �3 3 8 9 25 18 11 13 23 10� �3 3 8 9 10 18 11 13 23 25� �3 3 8 9 10 11 18 13 23 25� �3 3 8 9 10 11 13 18 23 25� �3 3 8 9 10 11 13 18 23 25� �3 3 8 9 10 11 13 18 23 25

FIG. 9.1– Exempledetri parselection

l’emplacementde l’ elementle plus petit du tableau,c’est-a-dire l’entier � tel que � "kÌ �(Ípourtout � . Unefois cetemplacement� trouve,on echangeleselements� � et �2Í . Puison re-commencecesoperationssurla suite a�� S �� -Î-Î-Î/�� e b , ainsion recherchele pluspetit elementdecettenouvellesuiteeton l’ echangeavec � S . Et ainsidesuite. . . jusqu’aumomentou onn’aplusqu’unesuitecomposeed’un seulelement a��eÏb .

La recherchedu pluspetit elementd’un tableauestun despremiersexercicesdeprogram-mation.La determinationdela positiondecetelementesttressimilaire,elles’effectuea l’aidedela suited’instructions:

m = 0;for (int j = 1; j < N; ++j)

if (a[j] < a[m])m = j;

L’ echangededeuxelementsnecessiteunevariabletemporaireÈ et s’effectuepar:t = a[m]; a[m] = a[1]; a[1] = t;

Il fautrefairecettesuited’operationsenremplacant� par � , puispar Y etainsidesuitejusqu’ac . Ceci sefait par l’introduction d’unenouvelle variable � qui prendtoutesles valeursentre� et c . Cesconsiderationsdonnentlieu auprogrammepresente endetail ci-dessous.Pourune

9.2. METHODESDE TRI ELEMENTAIRES 67

fois, nousl’ ecrivonspourunefois entotalite; lesproceduresd’acquisitiondesdonneeset derestitutiondesresultatssontaussifournies.Pourlesautresalgorithmes,nousnouslimiteronsala descriptiondela procedureeffective detri.

class TriSelection {

final static int N = 10;

static int[] a = new int[N]; // Le tableaua trier

static void initialisation() { // Ontire ausortdesnombres// entre0 et 127,eninitialisant// le tirageausortsurl’heure

for (int i = 0; i < N; ++i)a[i] = (int) (Math.random() * 128);

}

static void impression() {for (int i = 0; i < N; ++i)

System.out.print (a[i] + " ");System.out.println ("");

}

static void triSelection() {int min, t;

for (int i = 0; i < N - 1; ++i) {min = i;for (int j = i+1; j < N; ++j)

if (a[j] < a[min])min = j;

t = a[min]; a[min] = a[i]; a[i] = t;}

}


initialisation(); // On lit le tableauimpression(); // eton l’imprimetriSelection(); // Ontrieimpression(); // On imprimele resultat

}}

Il estfaciledecompterle nombred’operationsnecessaires.A chaqueiteration,ondemarrea l’ element Ð2Ñ et on le comparesuccessivementa Ð2Ñ$Ò�Ó , Ð(Ñ$ÒyÔ , . . ., Ð�Õ . On fait donc ÖØ×�Ùcomparaisons.On commenceavec ÙuÚÀÛ et on finit avec ÙRÚÜÖÝ×¸Û . Doncon fait Þ�ÖÝ×iÛ/ß�àÞ�Öá×¬â�ßTà�ã-ã-ã�à¥â>à7Û¡Ú7Ö«Þ�ÖZ×´Û/ß1ä�â comparaisons,et ÖZ×´Û echanges.Le tri parselectionfait doncdel’ordre de Ö Ô comparaisons.Si ÖåÚqÛ-æAæ , il y a 5000comparaisons,soit 5 mssion arrive a faireunecomparaisonet l’it erationde la bouclefor en1ç s, cequi esttout a faitpossiblesur unemachineplutot rapideactuellement.On ecriraquele tri par selectionestenè Þ�Ö Ô ß . Sontempsestquadratiqueparrapportauxnombresd’elementsdu tableau.

Une variantedu tri par selectionest le tri bulle. Son principe est de parcourir la suiteé Ð ÓEê Ð Ô�ê-ë-ë-ë�ê Ð ÕÏì enintervertissanttoutepaired’elementsconsecutifs Þ�Ð�íEî Ó)ê Ð�í�ß nonordonnes.Ainsi apres un parcours,l’ elementmaximum se retrouve en Ð Õ . On recommenceavec leprefixe

é Ð ÓEê Ð Ó-ê-ë-ë-ë�ê Ð Õ î Ó�ì , . . . Le nomdetri bulle vientdoncdecequelesplusgrandsnombresse deplacentvers la droite en poussantdesbulles successives de la gauchevers la droite.L’exemplenumeriqueprecedentestdonne avecle tri bulle dansla figure9.2.


18 3 10 25 9 3 11 13 23 8Ùï3 18 10 25 9 3 11 13 23 8Ùï3 10 18 25 9 3 11 13 23 8Ùï3 10 18 9 25 3 11 13 23 8Ùï3 10 18 9 3 25 11 13 23 8Ùï3 10 18 9 3 11 25 13 23 8Ùï3 10 18 9 3 11 13 25 23 8Ùï3 10 18 9 3 11 13 23 25 8ï Ù3 10 18 9 3 11 13 23 8 25Ùï3 10 9 3 11 13 18 8 23 25Ùï3 9 3 10 11 13 8 18 23 25Ùï3 3 9 10 11 8 13 18 23 25Ùï3 3 9 10 8 11 13 18 23 25Ùï3 3 9 8 10 11 13 18 23 25Ùï3 3 8 9 10 11 13 18 23 25Ùï3 3 8 9 10 11 13 18 23 25ï Ù3 3 8 9 10 11 13 18 23 25

FIG. 9.2– Exempledetri bulle

9.3. ANALYSEEN MOYENNE 69

La procedurecorrespondanteutiliseun indice i qui marquela fin duprefixe a trier, et l’in-dice j qui permetdedeplacerla bulle qui monteversla bornei . On peutcompteraussitresfacilementle nombred’operationset serendrecomptequ’il s’agit d’un tri en

è Þ�Ö Ô ß compa-raisonset eventuellementechanges(si parexemplele tableauestdonne en ordrestrictementdecroissant).

static void triBulle() {

int t;

for (int i = N-1; i >= 0; --i)for (int j = 1; j <= i; ++j)

if (a[j-1] > a[j]) {t = a[j-1]; a[j-1] = a[j]; a[j] = t;

}}

9.3 Analyseen moyenne

Pouranalyserun algorithmedetri, c’est a dire determinerle nombremoyend’operationsqu’il effectue,on utilise le modeledespermutations.On supposedanscemodelequela suitedesnombresa trier estla suitedesentiers Û ê â ê-ë-ë-ëËð et l’on admetquetouteslespermutationsde cesentierssontequiprobables.On peutnoterquele nombrede comparaisonsa effectuerpourun tri nedependpasdeselementsa trier maisdel’ordre danslequelils apparaissent.Lessupposertouscomprisentre Û et Ö n’estdoncpasunehypotheserestrictivesi onnes’interessequ’a l’analyseet si l’on seplacedansun modele d’algorithmedont l’operationdebaseestlacomparaison.

Pourunepermutationñ de ò2Û ê â ë-ë-ë�ð[ó danslui-meme,uneinversionestuncouple Þ�Ð(Ñ ê Ð í ßtel que Ùtô ï et Ð Ñ[õ Ð:í . Ainsi, la permutationé.ö ê Û ê�÷�ê Û-æ ê1ø¢ê â ê�ù�êËú�ê�û�ê�ü2ìqui correspondal’ordre deselementsdela figure9.1,comporteâ�Û inversions.Chaqueechanged’elementsdela procedureTriBulle supprimeuneet uneseuleinversionet, unefois le tritermine, il n’y a plus aucuneinversion.Ainsi le nombretotal d’echangeseffectues est egalau nombred’inversionsdansla permutation.Calculerle nombremoyen d’echangesdanslaprocedurede tri bulle revient donc a compterle nombremoyen d’inversionsde l’ensembledespermutationssur Ö elements.Un moyende fairececalculconsistea compterle nombred’inversionsdanschaquepermutationafairela sommedetouscesnombresetadiviserpar Ö�ý .Ceciestplutot fastidieux,uneremarquesimplepermetd’aller plusvite.

L’image miroir de toute permutationñqÚ é Ð Ó-ê Ð Ô[ë-ë-ë Ð ÕÏì est la permutationþqÚ é Ð Õ ,ë-ë-ë , Ð Ô , Ð Ó�ì . Il est clair que Þ�Ð Ñwê Ð�í/ß est une inversionde ñ si et seulementsi ce n’est pasune inversionde þ . La sommedu nombred’inversionsde ñ et de cellesde þ est Ö«Þ�ÖØ×Û/ß1ä�â . On regroupealorsdeuxpardeuxles termesde la sommedesnombresd’inversionsdespermutationssur Ö elementset on obtientquele nombremoyend’inversionssur l’ensembledespermutationsestdonne par: Ö«Þ�Öá×´Û/ßøce qui est donc le nombremoyen d’echangesdansla procedureTriBulle . On note tou-tefois que le nombrede comparaisonseffectueespar TriBulle est le memequecelui deTriSelection soit Ö�Þ�ÖZ×´Û/ß1ä�â .


18 3 10 25 9 3 11 13 23 8Ùï3 18 10 25 9 3 11 13 23 8Ùï3 10 18 25 9 3 11 13 23 8Ù ï3 10 18 25 9 3 11 13 23 8Ùï3 9 10 18 25 3 11 13 23 8Ùï3 3 9 10 18 25 11 13 23 8Ùï3 3 9 10 11 18 25 13 23 8Ùï3 3 9 10 11 13 18 25 23 8Ùï3 3 9 10 11 13 18 23 25 8Ùï3 3 8 9 10 11 13 18 23 25

FIG. 9.3– Exempledetri parinsertion

9.4 Le tri par insertion

Unemethodecompletementdifferenteestle tri par insertion. C’estlamethodeutiliseepourtrier unpaquetdecartes.Onprendunecarte,puis2 etonlesmetdansl’ordre si necessaire,puis3 et on met la ü eme cartea saplacedansles2 premieres,. . . De manieregeneraleon supposeles Ù'×rÛ premierescartestriees.Onprendla Ù emecarte,etonessaiedela mettreasaplacedansles Ùm×´Û cartesdeja triees.Et on continuejusqu’a Ù[ÚÊÖ . Cecidonnele programmesuivant

static void triInsertion() {

int j, v;for (int i = 1; i < N; ++i) {

v = a[i]; j = i;while (j > 0 && a[j-1] > v) {

a[j] = a[j-1];--j;

}a[j] = v;

9.4. LE TRI PAR INSERTION 71

}}

Pourclasserle Ù eme elementdu tableaua, onregardesuccessivementenmarchearriereapartirdu Ù<×´Û ieme. On decaleleselementsvisitesversla droitepourpouvoir mettrea[i] a sajusteplace.Le programmeprecedentcontientunelegereerreur, si a[i] estle pluspetit elementdutableau,car on va sortir du tableaupar la gauche.On peuttoujoursy remedieren supposantqu’on rajouteun elementa[0] valant-maxint . On dit alorsquel’on a mis unesentinelleagauchedutableaua. Cecin’estpastoujourspossible,et il faudraalorsrajouterun testsurl’in-dice j dansla bouclewhile . Ainsi, pour le tri par insertion,l’exemplenumeriqueprecedentestdansla figure9.3.

Le nombrede comparaisonspour inserer un elementdansla suite triee de ceux qui leprecedentestegalau nombred’inversionsqu’il presenteavec ceux-ciaugmente d’une unite.Soit ÿ�Ñ cenombredecomparaisons.Onaÿ�Ñ�Ú�Ûuà cardò/Ð í�� Ð í õ Ð(Ñ ê ï ô¥Ù óPourla permutationñ correspondanta la suitea trier, dont le nombred’inversionsestinv Þ.ñ<ß ,le nombretotaldecomparaisonspourle tri parinsertionest

�� Ú Õ� Ñ��yÔ ÿ Ñ Ú7ÖZ×´ÛRà inv Þ.ñ<ßD’ou le nombremoyendecomparaisons

� ÕiÚ ÛÖ�ý � � � � Ú7ÖZ×´ÛRà Ö«Þ�Ö ×¸Û/ßø Ú Ö«Þ�Ö à ü ßø ×´ÛBienquel’ordre degrandeursoit toujoursÖ Ô , cetri estplusefficacequele tri parselection.

De plus,il a la bonnepropriete quele nombred’operationsdependfortementdel’ordre initialdu tableau.Dansle casou le tableauestpresqueen ordre,il y a peud’inversionset trespeud’operationssontnecessaires,contrairementauxdeuxmethodesdetri precedentes.Le tri parinsertionestdoncun bontri si le tableaua trier adebonneschancesd’etrepresqueordonne.

Unevariantedu tri par insertionestun tri du a D. L. Shellen1959,c’estunemethodedetri quel’on peutsauterenpremierelecture.Sonprincipeestd’eviterd’avoir a fairedelongueschaınesdedeplacementssi l’ elementa insereresttrespetit.Nouslaissonsle lecteurfanatiqueencomprendrele sens,et le mentionnonsa titre anecdotique.Au lieu decomparerleselementsadjacentspourl’insertion,on lescomparetousles. . ., 1093,364,121,40,13,4, et1 elements.(On utilise la suite �AÒ�ÓÄÚ ü ��kàXÛ ). Quandon finit parcomparerdeselementsconsecutifs,ils ont debonneschancesd’etredeja dansl’ordre. On peutmontrerquele tri Shellnefait pasplusque

è Þ�Ö �� Ô ß comparaisons,etsecomportedoncbiensurdesfichiersdetaille raisonnable(5000elements).La demonstrationestcompliquee,etnousla laissonsenexercicedifficile. Onpeutprendretout autregenerateurque3 pourgenererlessequencesa explorer. Pratta montrequepourdessequencesde la forme â�� ü�� , le cout est

è Þ ð�� Ô ð ß dansle pire cas(maisil estcouteuxdemettrecettesequencedes â�� ü�� dansl’ordre). Dansle casgeneral, le cout (danslecasle pire)dutri Shellesttoujoursunproblemeouvert.Le tri Shellesttresfacileaprogrammeret tresefficaceenpratique(c’estle tri utilise dansle noyauMaple).

static void triShell() {

int h = 1; doh = 3*h + 1;

while ( h <= N );do {

h = h / 3;


for (int i = h; i < N; ++i)if (a[i] < a[i-h]) {

int v = a[i], j = i;do {

a[j] = a[j-h];j = j - h;

} while (j >= h && a[j-h] > v);a[j] = v;

}} while ( h > 1);

}

9.5 Quicksort

Cettemethodedetri estdueaC.A.R Hoareen1960.Sonprincipeestle suivant.On prendun elementauhasarddansle tableaua trier. Soit � savaleur. Onpartitionnele restedu tableauen2 zones: leselementspluspetitsou egauxa � , et leselementsplusgrandsou egauxa � . Sionarrive amettreentetedu tableaulespluspetitsque � etenfin du tableaulesplusgrands,onpeutmettre� entrelesdeuxzonesasaplacedefinitive.OnpeutrecommencerrecursivementlaprocedureQuicksortsurchacunedespartitionstantqu’ellesnesontpasreduitesaun element.Graphiquement,onchoisit � commel’un desÐ Ñ a trier. Onpartitionnele tableaupourobtenirlapositiondela figure9.4(c). Si � et � sontlesbornesagaucheet adroitedesindicesdu tableaua trier, le schemadu programmerecursifest

static void qSort(int g, int d) {

if (g < d) {v = a[g];Partitionnerle tableauautourdela valeur �et mettre� a sabonneposition �qSort (g, m-1);qSort (m+1, d);

}}

Nousavonspris a[g] au hasard,touteautrevaleurdu tableaua auraitconvenu.En fait, laprendrevraimentauhasardnefait pasdemal,carca evitelesproblemespourlesdistributionsparticulieresdesvaleursdu tableau(parexemplesi le tableauestdeja trie). Plusimportant,ilrestea ecrire le fragmentde programmepour faire la partition.Une methodeingenieuse[6]consisteaparcourirle tableaude � a � engerantdeuxindices Ù et � telsqu’a tout momentona Ð:í�ô � pour �®ô ï"! � , et Ð�í�# � pour � ô ï ô¥Ù . Ainsi

m = g;for (i = g+1; i <= d; ++i)

if (a[i] < v) {++m;x = a[m]; a[m] = a[i]; a[i] = x; // Echanger$�% et $'&

}

cequi donnela proceduresuivantedeQuicksort

static void qSort(int g, int d) {

int i, m, x, v;

if (g < d) {v = a[g];

9.5. QUICKSORT 73

(a) � ô(� # � ?

� � Ù �(b) � ô(� #(�

� � �(c) ô � � #(�

� � �FIG. 9.4– PartitiondeQuicksort

m = g;for (i = g+1; i <= d; ++i)

if (a[i] < v) {++m;x = a[m]; a[m] = a[i]; a[i] = x; // Echanger$�% et $�&

}x = a[m]; a[m] = a[g]; a[g] = x; // Echanger$�% et $')qSort (g, m-1);qSort (m+1, d);

}}

Cettesolutionn’estpassymetrique.La presentationusuelledeQuicksortconsistea encadrerla positionfinale de � par deux indicespartantde 1 et Ö et qui convergent vers la positionfinale de � . En fait, il esttresfacilede setromperen ecrivant ce programme.C’est pourquoinousavonssuivi la methodedecritedansle livre deBentley [6]. Unemethodetresefficaceetsymetriqueestcellequi suit,deSedgewick [47].

static void quickSort(int g, int d) {

int v,t,i,j;

if (g < d) {v = a[d]; i= g-1; j = d;do {

do++i;

while (a[i] < v);do

--j;while (a[j] > v);t = a[i]; a[i] = a[j]; a[j] = t;

} while (j > i);a[j] = a[i]; a[i] = a[d]; a[d] = t;quickSort (g, i-1);quickSort (i+1, d);


}}

On peutverifier quecettemethodene marchequesi dessentinellesa gaucheet a droite dutableauexistent,enmettantun pluspetit elementque � a gaucheet un plusgranda droite.Enfait, unemanieredegarantircelaestdeprendretoujoursl’ elementdegauche,dedroiteet dumilieu, demettrecestrois elementsdansl’ordre, enmettantle pluspetitdestroisen Ð Ó , le plusgranden Ð�Õ etprendrele mediancommevaleur� aplacerdansle tableaua. Onpeutremarqueraussicommentle programmeprecedentrendbiensymetriquele casdesvaleursegalesa � dansle tableau.Le but rechercheestd’avoir la partitionla plusequilibreepossible.Eneffet, le calculdu nombremoyen

� Õ decomparaisonsemprunte a [47] donne��* Ú � Ó Ú7æ , etpour Ö+#iâ ,

� Õ Ú7Ö à7ÛRà ÛÖ �Ó-,./,+Õ Þ � . î Ó à � Õ î . ßD’ou parsymetrie

� ÕiÚ7Ö à�ÛRà âÖ �Ó-,./,+Õ � . î ÓEn soustrayant,on obtientapressimplificationÖ � ÕiÚ Þ�Ö à7Û/ß � Õ î Ó[à¥â�ÖEn divisantpar Ö«Þ�Ö à�Û/ß� ÕÖ à7Û Ú � Õ î ÓÖ à âÖqàÊÛ Ú � Ôü à �

� ,./,+Õ â0 àÊÛEn approximant � ÕÖ à7Û"1 â �Ó-,./,+Õ Û0 1 â32 ÕÓ Û4 � 4 Úâ ��5 ÖD’ou le resultat � Õ 1 Û ê�ü ö Ö �� Ô Ö

Quicksortestdonctresefficaceen moyenne.Bien sur, ce tri peut etreen tempsè Þ�Ö Ô ß ,

si les partitionssont toujoursdegenereespar exemplepour les suitesmonotonescroissantesou decroissantes.C’estun algorithmequi a unetrespetiteconstante(1,38)devant la fonctionlogarithmique.Unebonnetechniqueconsistea prendreQuicksortpourdegrostableaux,puisrevenir autri parinsertionpourlespetitstableaux(

!8 ou 9 elements).

Le tri parQuicksortestle prototypedela methodedeprogrammationDivideandConquer(enfrancais“diviserpourregner”).Eneffet, Quicksortdivisele problemeendeux(les2 appelsrecursifs)et recombinelesresultatsgracea la partition initialementfaiteautourd’un elementpivot. Divide and Conquerserala methodechaquefois qu’un problemepeut etredivise enmorceauxplus petits,et que l’on peut obtenir la solution a partir desresultatscalcules surchacundesmorceaux.Cettemethodedeprogrammationesttresgenerale,et reviendrasouventdansle cours.Elle supposedoncsouventplusieursappelsrecursifsetpermetsouventdepasserd’un nombred’operationslineaire

è Þ ð ß a unnombred’operationslogarithmiqueè Þ ��tð ß .

9.6. LE TRI PAR FUSION 75

9.6 Le tri par fusion

Uneautreprocedurerecursive pourfairele tri estle tri par fusion(ouparinterclassement).La methodeprovient du tri sur bandemagnetique(peripheriqueautrefoisfort utile desordi-nateurs).C’est aussiun exemplede la methodeDivide and Conquer. On remarqued’abordqu’il estaise de faire l’interclassemententredeuxsuitesde nombrestriesdansl’ordre crois-sant.En effet, soient

é Ð ÓEê Ð Ô�ê-ë-ë-ë Ð76 ì eté98 ÓEê 8 Ô�ê-ë-ë-ë 8 ÕÏì cesdeuxsuites.Pourobtenir, la suite

interclasseeé ÿ ÓEê ÿ Ô�ê-ë-ë-ë ÿ:6 Ò�Õ¡ì desÐ Ñ et

8 í , il suffit defairele programmesuivant.(Onsupposequel’on metdeuxsentinellesÐ;6 Ò�Ó Ú=< et

8 ÕuÒ�Ó Ú>< pournepascompliquerla structuredu programme.)

int[] a = new int[M+1],b = new int[N+1],c = new int[M+N];

int i = 0, j = 0;

a[M+1] = b[N+1] = Integer.MAX_VALUE;

for (int k = 0; k < M+N; ++k)if (a[i] <= b[j]) {

c[k] = a[i];++i;

} else {c[k] = b[j];++j;

}

Successivement, ÿ . devient le minimum de Ð Ñ et8 í en decalantl’endroit ou l’on se trouve

dansla suite Ð ou8

selonle caschoisi.L’interclassementde ? et Ö elementssefait doncenè Þ9? à´Örß operations.Pourfaire le tri fusion,enappliquantDivide andConquer, on trie lesdeuxmoitiesde la suite

é Ð ÓEê Ð Ô�ê-ë-ë-ë Ð Õ¡ì a trier, et on interclasselesdeuxmoitiestriees.Il y atoutefoisunedifficulte carondoit copierdansuntableauannexe les2 moitiesa trier, puisqu’onne sait pasfaire l’interclassementen place.Si � et � sontles bornesa gaucheet a droitedesindicesdu tableaua trier, le tri fusionestdonc

static void TriFusion(int g, int d) {

int i, j, k, m;

if (g < d) {m = (g + d) / 2;TriFusion (g, m);TriFusion (m + 1, d);for (i = m; i >= g; --i)

b[i] = a[i];for (j = m+1; j <= d; ++j)

b[d+m+1-j] = a[j];i = g; j = d;for (k = g; k <= d; ++k)

if (b[i] < b[j]) {a[k] = b[i]; ++i;

} else {a[k] = b[j]; --j;

}}

}


La recopiepour faire l’interclassementse fait dansun tableaub de memetaille quea. Il ya unepetiteastuceen recopiantunedesdeuxmoitiesdansl’ordre inverse,ce qui permetdesepasserde sentinellespour l’interclassement,puisquechaquemoitie sertde sentinellepourl’autre moitie. Le tri par fusion a unetresgrandevertu.Sonnombred’operations

� Õ esttelque� Õ ÚÜâ�Ö à´â � Õ � Ô , et donc

� Õ Ú è Þ�Ö �� Örß . Doncle tri fusionestun tri qui garantitun tempsÖ �� Ö , auprix d’un tableauannexe deN elements.Cetempsestrealise quellequesoit la distribution desdonnees,a la differencede QuickSort.Plusieursproblemesseposentimmediatement: peuton fairemieux?Faut-il utiliser cetri plutot queQuickSort?

Nousrepondronsplustard“non” alapremierequestion,voir section1.Quantaladeuxiemequestion,on peut remarquerque si ce tri garantitun bon temps,la constantepetite devantÖ �� Ö deQuickSortfait quecedernierestsouventmeilleur. Aussi,QuickSortutilise moinsdememoireannexe,puisquele tri fusiondemandeuntableauqui estaussiimportantqueceluiatrier. Enfin,onpeutremarquerqu’il existeuneversioniterativedutri parfusionencommençantpartrier dessous-suitesdelongueur2, puisdelongueur4, 8, 16, . . ..

Chapitr e 10

Structur esde donneeselementaires

Dansce chapitre,nousintroduisonsquelquesstructuresutiliseesde facon tres intensiveen programmation.Leur but est de gerer un ensemblefini d’elementsdont le nombren’estpasfixe a priori . Les elementsde cet ensemblepeuvent etrede differentessortes: nombresentiersou reels,chaınesde caracteres,ou desobjets informatiquesplus complexes commeles identificateursde processusou les expressionsde formulesen coursde calcul ë-ë-ë On nes’interesserapasauxelementsdel’ensembleenquestionmaisauxoperationsquel’on effectuesurcetensemble,independammentdela naturedeseselements.Ainsi lesensemblesquel’onutilise en programmation,contrairementa ceuxconsideres en mathematiquesqui sontfixesunefois pour toutes,sontdesobjetsdynamiques.Le nombredeleurselementsvarieaucoursde l’executiondu programme,puisqu’onpeuty ajouteret supprimerdeselementsen coursde traitement.Plusprecisementles operationsquel’on s’autorisesur les ensemblessont lessuivantes:

– testersi l’ensemble@ estvide.– ajouter l’ element4 a l’ensemble@ .– verifier si l’ element4 appartienta l’ensemble@ .– supprimerl’ element4 del’ensemble@ .Cettegestiondesensemblesdoit, pour etre efficace,repondreau mieux a deux criteres

parfoiscontradictoires: un minimumdeplacememoireutiliseeet un minimumd’instructionselementairespourrealiseruneoperation.La placememoireutiliseedevrait pourbienfaireetretresvoisinedu nombred’elementsde l’ensemble@ , multiplieepar leur taille ; c’estcequi sepasserapour lestrois structuresquel’on va etudierplusloin. En cequi concernela minimisa-tion du nombred’instructionselementaires,on peuttestertressimplementsi un ensembleestvide et on peutrealiserl’operationd’ajout enquelquesinstructions,toutefoisil estimpossiblede realiserunesuppressionou unerecherched’un elementquelconquedansun ensembleenutilisantun nombred’operationsindependantdu cardinaldecetensemble(a moinsd’utiliserunestructuredemandantune tres grandeplaceen memoire).Pourameliorer l’efficacite, onconsidere desstructuresde donneesdanslesquelleson restreintla portee desoperationsderechercheetdesuppressiond’un elementenselimitant a la realisationdecesoperationssurledernierou le premierelementdel’ensemble,cecidonnelesstructuresdepile ou defile, nousverronsquemalgre cesrestrictionslesstructuresenquestionontdenombreusesapplications.

10.1 Listes chaınees

La liste estunestructuredebasedela programmation,le langageLISP (LISt Processing),concu parJohnMacCarthyen1960,ou saversionplusrecenteScheme[1], utilise principale-mentcettestructurequi sereveleutile pourle calculsymbolique.Danscequi suit on utilise laliste pour representerun ensembled’elements.Chaqueelementestcontenudansunecellule,celle ci contienten plus de l’ elementl’adressede la cellule suivante,appeleeaussipointeur.

77

78 CHAPITRE10. STRUCTURESDE DONNEESELEMENTAIRES

A � A Ô A Ótete

A:B A � A Ô A ÓteteC

FIG. 10.1– Ajout d’un elementdansuneliste

La recherched’un elementdansla listes’apparenteaunclassique“jeu depiste”dontle but estderetrouver un objetcache : on commenceparavoir desinformationssurun lieu ou pourraitsetrouver cetobjet,encelieu ondecouvredesinformationssurunautrelieu ou il risquedesetrouveretainsidesuite.Le langageJavapermetcetterealisationa l’aide declassesetd’objets:lescellulessontdesobjets(c’estadiredesinstancesd’uneclasse)dontundeschampscontientunereferenceversla cellule suivante.La referenceversla premierecellule estelle contenuedansunevariabledetetedeliste. Lesdeclarationscorrespondantessontlessuivantes,ou l’onsupposeici queleselementsstockesdanschaquecelluledontdetypeentier..

class Liste {

int contenu;Liste suivant;

Liste (int x, Liste a) {contenu = x;suivant = a;

}}

L’instruction new Liste (x, a) construitune nouvelle cellule dont les champssont xet a. La fonction Liste(x,a) estun constructeurde la classeListe (un constructeurestunefonctionnonstatiquequi sedistinguepar le typedesonresultatqui estcelui de la classecouranteet parsonabsencedenompour l’identifier). L’objet null appartienta touteclasse,et representeradansle casdeslistesle marqueurdefin deliste.Ainsi

new Liste(2, new Liste (7, new Liste (11, null)))

representerala liste 2,7,11.Les operationssur les ensemblesquenousavonsconsidereesci-dessuss’exprimentalorscommesuit si on gereceux-cipardeslistes:

static boolean estVide (Liste a) {

return a == null;}

La procedureajouter inserel’ elementx en tetede liste. Cechoix demettrel’ elemententeteestindispensablepourquele nombred’operationslorsdel’ajout soit independantdelataille dela liste; il suffit alorsdemodifierla valeurdela tetedelistecequi estfait simplementpar

static Liste ajouter (int x, Liste a) {

return new Liste (x, a); // L’ancienneteteseretrouveapresx}

La fonctionrecherche , qui verifie si l’ elementx figurebiendansla liste a, effectueunparcoursdela listepourrechercherl’ element.La variablea estmodifieeiterativementpara =a.suivant defacon a parcourirtousles elementsjusqu’a cequel’on trouve x ou quel’onarrive a la fin dela liste (a = null ).

10.1. LISTESCHAINEES 79

A:B A � A Ô A Ótete

A:B A � A Ô A ÓteteC

FIG. 10.2– Suppressiond’un elementdansuneliste

static boolean recherche (int x, Liste a) {

while (a != null) {if (a.contenu == x)

return true;a = a.suivant;

}return false;

}

La fonctionrecherche peutaussietreecritedemaniererecursive


if (a == null)return false;

else if (a.contenu == x)return true;

elsereturn recherche (x, a.suivant);

}

ou encore


if (a == null)return false;

elsereturn (a.contenu == x) || recherche (x, a.suivant);

}

ou encoreencore(quoiquenonrecommande) :


return a != null && (a.contenu == x || recherche (x, a.suivant));}

Cetteecriturerecursive estsystematique.pour lesfonctionssur les listes.En effet, le typedeslistesverifie l’ equationsuivante:

Liste DFE Liste videGIH Element J Liste

ou K estl’union disjointeet L le produitcartesien.Touteprocedureou fonctiontravaillant surleslistespeutdoncs’ecrirerecursivementsurla structuredesalisteargument.Parexemple,lalongueurd’unelistesecalculepar

static int longueur(Liste a) {

if (a == null)


return 0;else

return 1 + longueur (a.suivant);}

cequi estpluselegantquel’ ecritureiterative qui suit

static int longueurI(Liste a) {

int longueur = 0;while (a != null) {

++longueur;a = a.suivant;

}return longueur;

}

Choisir entre la maniere recursive ou iterative est affaire de gout. Autrefois, on disait quel’ ecriture iterative etait plus efficacecar utilisant moins de memoire.Graceaux techniquesnouvellesdecompilation(commel’ eliminationdesrecursionsterminales),c’estdemoinsenmoinsvrai ; deplusl’occupationmemoireest,danslesordinateursd’aujourd’hui,unequestionnettementmoinscritique.

La suppressiondela cellulequi contientx s’effectueenmodifiantla valeurdesuivantcontenuedansle predecesseurdex : le successeurdupredecesseurdex devient le successeurdex . Un traitementparticulierdoit etrefait si l’ elementa supprimerestle premierelementdela liste.La procedurerecursive desuppressionesttrescompactedanssadefinition.

static Liste supprimer (int x, Liste a) {

if (a != null)if (a.contenu == x)

a = a.suivant;else

a.suivant = supprimer (x, a.suivant);return a;

}

Uneprocedureiterative demandebeaucoupplusd’attention.


if (a != null)if (a.contenu == x)

a = a.suivant;else {

Liste b = a ;while (b.suivant != null && b.suivant.contenu != x)

b = b.suivant;if (b.suivant != null)

b.suivant = b.suivant.suivant;}

return a;}

Noterquedanslesdeuxfonctionsci-dessus,on a modifie la liste a, on nepeutdoncdis-poserde deuxlistesdistinctesl’une qui contientx et l’autre identiquea la precedente,maisne contenantpasx . Pource faire, il faut recopierunepartiede la liste a dansunenouvelle

10.1. LISTESCHAINEES 81

liste, commele fait le programmesuivant,ou il y a uneutilisationun peuplus importantedela memoire.Mais l’espacememoireperduestrecupere parle glaneurdecellules(GC)deJava,si personnen’utilise l’ancienneliste a. Avec les techniquesactuellesde GC a generations,cetterecuperations’effectueratresrapidement.Il fautdoncnoterla differenceavecun langagecommePascalouC, ou ondoit sepreoccuperdel’espacememoireperdu,si onveutpouvoir lereutiliser.


if (a != null)return null;

else if (a.contenu == x)return a.suivant;

elsereturn new Liste (a.contenu, supprimer (x, a.suivant));

}

Une techniquesouvent utiliseepermetd’eviter quelquestestspoursupprimerun elementdansunelisteetplusgeneralementpoursimplifier la programmationsurleslistes.Elle consistea utiliser unegardepermettantderendrehomogenele traitementdela liste vide et desautreslistes.En effet dansla representationprecedente,la liste vide n’a pasla memestructurequelesautreslistes.On utilise unecelluleplaceeaudebut et n’ayantpasd’informationsignifica-tive dansle champcontenu ; l’adressede la vraiepremierecellulesetrouve dansle champsuivant decettecellule. On obtientainsiuneliste gardee, l’avantaged’unetelle gardeestquela liste vide contientaumoinsla garde,et queparconsequentun certainnombredepro-grammes,qui devaientfaireuncasspecialdansle casdela listevideoudupremierelementdeliste, deviennentplussimples.Cettenotionestun peul’ equivalentdessentinellespour les ta-bleaux.Onutiliseracettetechniquedanslesproceduressurlesfilesunpeuplusloin (voir page85) . On peutaussidefinir deslistescirculairesgardeesenmettantl’adressedecettepremierecelluledansle champsuivant dela dernierecelluledela liste.Leslistespeuventaussietregereespardifferentsautresmecanismesquenousnedonnonspasendetail ici. Onpeututiliser,parexemple,deslistesdoublementchaıneesdanslesquelleschaquecellulecontientunelementet les adressesa la fois de la cellule qui la precedeet de celle qui la suit. Descouplesde ta-bleauxpeuventaussietreutilises,le premiercontenu contientleselementsdel’ensemble,lesecondadrsuivant contientlesadressesdel’ elementsuivantdansle tableaucontenu .

Remarque La procedureajouter effectue ü operationselementaires.Elle estdonc tres ef-ficace.En revanche,les proceduresrecherche et supprimersontplus longuespuisqu’onpeutaller jusqu’aparcourirla totalited’unelistepourretrouverunelement.Onpeutestimer, si onnefait aucunehypothesesur la frequencerespective desrecherches,quele nombred’operationsestenmoyenneegala la moitie du nombred’elementsdela liste.Ceciesta comparera la re-cherchedichotomiquequi effectueunnombrelogarithmiquedecomparaisonset a la rechercheparhachagequi estsouventbienplusrapideencore.

Exemple A titre d’exempled’utilisation deslistes,nousconsideronsla constructiond’uneliste desnombrespremiersinferieursou egauxaun entier ð donne.Pourconstruirecetteliste,on commence,dansunepremierephase,pary ajoutertouslesentiersde â a ð encommençantpar le plus grandet en terminantpar le plus petit. Du fait de l’algorithme d’ajout decrit plushaut, la liste contiendradonc les nombresen ordre croissant.On utilise ensuitela methodeclassiquedu crible d’Eratosthene: on consideresuccessivementles elementsde la liste dansl’ordre croissantet on supprimetous leursmultiplesstricts.Ceci setraduit par la proceduresuivante:

static Liste listePremier (int n) {


Liste a = null;int k;

for (int i = n; i >= 2; --i) {a = ajouter (i, a);

}k = a.contenu;for (Liste b = a; k * k <= n ; b = b.suivant){

k = b.contenu;for (int j = k; j <= n/k; ++j)

a = supprimer (j * k, a);}

return(a);}

Remarque Nousnepretendonspasquecetteprogrammationsoit efficace(loin dela!). Elleest toutefoissimple a ecrire,une fois que l’on a a sadispositionles fonctionssur les listes.Elle donnedebonsresultatspour ð inferieura Û-æAæAæAæ . Un bonexerciceconsisteaenameliorerl’efficacite.

Exemple Un autreexemple,plus utile, d’applicationdeslistesest la gestiondescollisionsdansle hachagedontil a etequestionauchapitre1 (voir page51).Il s’agitpourchaqueentier Ùdel’intervalle M æ ë-ë-ë Ö ×�ÛON deconstruireunelistechaınee P Ñ formeedetouteslescles 4 tellesque QmÞ 4 ß¡ÚÜÙ . Leselementsdela liste sontdesentierspermettantd’accederauxtableauxdesnomset desnumerosde telephone.Lesproceduresderechercheet d’insertionde 4 dansunetabledeviennentdesproceduresderechercheet d’ajout dansuneliste. Ainsi, si la fonction Qestmal choisie,le nombredecollisionsdevient important,la plusgrandedeslistesdevient detaille imposanteet le hachagerisquededevenir aussicouteuxquela recherchedansunelistechaıneeordinaire.Parcontre,si Q estbienchoisie,la rechercheestrapide.

Liste al[] = new Liste[N-1];

static void insertion (String x, int val) {

int i = h(x);al[i] = ajouter (x, al[i]);

}


for (int a = al[h(x)]; a != null; a = a.suivant) {if (x.equals(nom[a.contenu]))

return tel[a.contenu];}return -1;

}

10.2 Files

Les files sontutiliseesen programmationpour gererdesobjetsqui sonten attented’untraitementulterieur, par exempledesprocessusen attented’une ressourcedu systeme,des

10.2. FILES 83

sommetsd’un graphe,desnombresentiersencoursd’examendecertainesdeleur proprietes,etc . . . Dansune file les elementssont systematiquementajoutes en queueet supprimes entete,la valeurd’unefile estparconventioncellede l’ elementde tete.En anglais,on parledestrategieFIFOFirst In FirstOut, paroppositiona la strategieLIFO LastIn FirstOutdespiles.De facon plus formelle,on sedonneun ensemble@ , l’ensembledesfiles dont les elementssontdans@ estnote RÄÙTSwÞU@·ß , la file vide (qui necontientaucunelement)est R * , lesoperationssurlesfilessontvide, ajouter, valeur, supprimer:

– estVide estuneapplicationde RÄÙVS1ÞU@·ß dans(vrai, faux), AXWXY�Z ÙV� A ÞURkß estegalavrai si etseulementsi la file R estvide.

– ajouterestuneapplicationde @[L�RÄÙVS1ÞU@~ß dansRÄÙVS1ÞU@·ß , Ð ï]\ � Y-A:^ Þ 4 ê R~ß estla file obtenueapartir dela file R eninserantl’ element4 a la fin decelle-ci.

– valeur est uneapplicationde RÄÙVS1ÞU@~ß`_aR * dans @ qui a unefile R non vide associel’ elementsetrouvantentete.

– supprimerestuneapplicationde RÄÙVS1ÞU@·ßb_�R * dansRÄÙTSwÞU@·ß qui associeaunefile R nonvide la file obtenueapartir de R ensupprimantsonpremierelement.

Lesoperationssurlesfiles satisfontlesrelationssuivantes

Pour RFcÚdR *W �fe]e ^ Ùg� Ah^ Þ�Ð ï]\ � YiAh^ Þ 4 ê Rkß1ßOÚ7Ð ï]\ � YiAh^ Þ 4 ê W �fe]e ^ Ùg� Ah^ ÞUR~ß1ß�(Ð;S A � ^ Þ�Ð ï]\ � Y-A:^ Þ 4 ê Rkß1ßRÚj�(Ð;S A � ^ ÞURkßPourtoutefile RAXWXY-Z ÙV� A Þ�Ð ï]\ � Y-A:^ Þ 4 ê R~ß1ßRÚdkyÐl� 4Pourla file R *W �fe]e ^ Ùg� Ah^ Þ�Ð ï]\ � YiAh^ Þ 4 ê R * ß1ßtÚjR *�(Ð;S A � ^ Þ�Ð ï]\ � Y-A:^ Þ 4 ê R * ß1ßIÚ 4AXWXY-Z ÙV� A ÞUR * ßOÚm� ^ Ð(Ù

Unepremiereideederealisationsousformedeprogrammesdesoperationssurlesfilesestemprunteeaunetechniquemiseenoeuvredansdeslieux ou desclientsfont la queuepouretreservis, il s’agit parexempledecertainsguichetsde reservation danslesgares,debureauxdecertainesadministrations,ou desetalsdecertainssupermarches.Chaqueclient qui sepresenteobtientun numero et les clientssontensuiteappelespar les serveursdu guicheten fonctioncroissantedeleur numerod’arrivee.Pourgerercesystemedeuxnombresdoivent etreconnuspar les gestionnaires: le numero obtenupar le dernierclient arrive et le numero du dernierclientservi.Onnotecesdeuxnombresparfin etdebut respectivementetongerele systemedela faconsuivante

– la file d’attenteestvidesi et seulementsi debut Ú fin,– lorsqu’unnouveauclient arrive on incrementefin eton donnecenumeroauclient,– lorsquele serveur est libre et peut servir un autreclient, si la file n’est pasvide, il

incrementedebut etappellele possesseurdecenumero.Dansla suite,on a represente toutescesoperationsen Java en optimisantla placeprise

par la file en utilisant la techniquesuivante: on reattribue le numero æ a un nouveauclientlorsquel’on atteintuncertainseuilpourla valeurdefin. Ondit qu’onauntableau(outampon)circulaire.

class File {

final static int MaxF = 100;

int debut;int fin;boolean pleine, vide;


12 31 11 22 91 3 13 53 23 8

debut fin

La file contientlesnombresò ü�ê Û ü�ê�÷Aü(ó12 31 11 22 91 3 13 53 27 8

debut fin

Ajout del’ elementâ ú12 31 11 22 91 3 13 53 27 8

debut fin

Suppressionssuccessivesdedeuxelements

12 31 11 22 91 3 13 53 27 37

debutfin

Ajout del’ elementü�ú12 31 11 22 91 3 13 53 27 37

debut

fin File vide apres2 suppressions

FIG. 10.3– File gereeparun tableaucirculaire

int contenu[];

File () {debut = 0; fin = 0;pleine = false; vide = true;contenu = new int[MaxF];

}

static File vide () {return new File();

}

static void faireVide (File f) {f.debut = 0; f.fin = 0;f.pleine = false; f.vide = true;

}

static boolean estVide(File f) {return f.vide;

}

static boolean estPleine(File f) {return f.pleine;

}

static int valeur (File f) {if (f.vide)

10.2. FILES 85

erreur ("File Vide.");return f.contenu[f.debut];

}

static void ajouter (int x, File f) {if (f.pleine)

erreur ("File Pleine.");f.contenu[f.fin] = x;f.fin = (f.fin + 1) % MaxF;f.vide = false;f.pleine = f.fin == f.debut;

}

static void supprimer (File f) {if (f.vide)

erreur ("File Vide.");f.debut = (f.debut + 1) % MaxF;f.vide = f.fin == f.debut;f.pleine = false;

}}

Uneautrefacon degererdesfiles consistea utiliser deslisteschaıneesgardees(voir page81)danslesquellesonconnaıt a la fois l’adressedu premieret du dernierelement.Celadonnelesoperationssuivantes:

class File {

Liste debut;Liste fin;

File (Liste a, Liste b) {debut = a;fin = b;

}

static File vide () {Liste garde = new Liste();return new File (garde, garde);

}

static void faireVide (File f) {Liste garde = new Liste();f.debut = f.fin = garde;

}

static boolean estVide (File f) {return f.debut == f.fin;

}

static int valeur (File f) {Liste b = f.debut.suivant;return b.contenu;

}


A Ó A Ô A ð #´ædebut fin

FIG. 10.4– File d’attenteimplementeeparuneliste

static void ajouter (int x, File f) {Liste a = new Liste (x, null);f.fin.suivant = a;f.fin = a;

}

static void supprimer (File f) {if (estVide (f))

erreur ("File Vide.");f.debut = f.debut.suivant;

}}

Nousavonsdeuxrealisationspossiblesdesfiles avec destableauxou deslisteschaınees.L’ ecriture de programmesconsistea faire de tels choix pour representerles structuresdedonnees.L’ensembledesfonctionssurlesfilespeutetreindistinctementunmodulemanipulantdestableauxouunmodulemanipulantdeslistes.L’utilisation desfilessefait uniquementatra-verslesfonctionsvide, ajouter, valeur, supprimer. C’estdoncl’ interfacedesfiles qui importedansdeplusgrosprogrammes,et nonleursrealisations.Lesnotionsd’interfaceet demodulesserontdeveloppeesauchapitre7.

10.3 Piles

La notion de pile intervientcourammenten programmation,sonrole principal consisteaimplementerles appelsde procedures.Nousn’entreronspasdansce sujet,plutot technique,dansce chapitre.Nousmontreronsle fonctionnementd’une pile a l’aide d’exempleschoisisdansl’ evaluationd’expressionsLisp.

Onpeutimaginerunepile commeuneboıtedanslaquelleonplacedesobjetsetdelaquelleon lesretiredansun ordreinversedecelui danslequelon lesa mis : lesobjetssontlesunssurlesautresdansla boıteetonnepeutaccederqu’a l’objet situeau“sommetdela pile”. Defaconplusformelle,onsedonneunensemble@ , l’ensembledespilesdontleselementssontdans@estnote nQÙVS1ÞU@~ß , la pile vide(qui necontientaucunelement)est n * , lesoperationssurlespilessontvide, ajouter, valeur, supprimercommesurlesfiles.Cettefois, lesrelationssatisfaitessontlessuivantes(ou n * denotela pile vide)

supprimerÞ ajouterÞ 4 ê nkß1ßOÚjnestVideÞ ajouterÞ 4 ê nkß1ßOÚokyÐf� 4valeurÞ ajouterÞ 4 ê nkß1ßRÚ 4estVideÞUn * ßOÚp� ^ Ð(Ù

A l’aide decesrelations,on peutexprimer touteexpressionsur lespilesfaisantintervenirles ø operationsprecedentesa l’aide de la seuleoperation Ð ï]\ � Y-A:^ en partantde la pile n * .Ainsi l’expressionsuivanteconcernelespilessurl’ensembledesnombresentiers:

supprimer Þ ajouter Þ ú(ê

10.3. PILES 87

supprimerÞ ajouter Þ valeur Þ ajouter Þ ÷�ê ajouter Þ ü�ê n * ß ))),ajouter Þ û�ê n * ß )))

Elle peutsesimplifieren:Ð ïf\ � Y-A:^ Þ û�ê n * ßLa realisationdesoperationssurlespilespeuts’effectuerenutilisantuntableauqui contient

leselementsetun indicequi indiquerala positiondusommetdela pile. parreference.

class Pile {

final static int maxP = 100;

int hauteur ;Element contenu[];

Pile () {hauteur = 0;contenu = new Element[maxP];

}

static File vide () {return new Pile();

}

static void faireVide (Pile p) {p.hauteur = 0;

}

static boolean estVide (Pile p) {return p.hauteur == 0;

}

static boolean estPleine (Pile p) {return p.hauteur == maxP;

}

static void ajouter (Element x, Pile p)throws ExceptionPile

{if (estPleine (p))

throw new ExceptionPile("pleine");p.contenu[p.hauteur] = x;++ p.hauteur;

}

static Element valeur (Pile p)throws ExceptionPile

{if (estVide (p))

throw new ExceptionPile("vide");return p.contenu [p.hauteur - 1];

}

static void supprimer (Pile p)


throws ExceptionPile{

if (estVide (p))throw new ExceptionPile ("vide");

-- p.hauteur;}

}

ou onsupposequ’unenouvelle classedefinit lesexceptionsExceptionPile :

class ExceptionPile extends Exception {String nom;

public ExceptionPile (String x) {nom = x;

}}

Remarques Chacunedesoperationssurlespilesdemandeun trespetit nombred’operationselementaireset ce nombreest independantdu nombred’elementscontenusdansla pile. Onpeutgereraussiunepile avec uneliste chaınee,les fonctionscorrespondantessontlaisseesatitre d’exercice.Lespilesont ete considereescommedesargumentspar referencepour eviterqu’unappeldefonctionnefasseunecopieinutile pourpasserl’argumentparvaleur.

10.4 Evaluation desexpressionsarithm etiquesprefixees

Danscettesection,on illustre l’utilisation despilesparun programmed’evaluationd’ex-pressionsarithmetiquesecritesde facon particuliere. Rappelonsqu’expressionarithmetiquesignifie dansle cadrede la programmation: expressionfaisantintervenir desnombres,desvariableset desoperationsarithmetiques(parexemple: àjq>äQ×sr ). Danscequi suit, poursimplifier, nousnouslimiteronsaux operationsbinaires à et q et aux nombresnaturels.Lageneralisationa desoperationsbinairessupplementairescommela division et la soustractionestparticulierementsimple,c’estun peuplusdifficile deconsidereraussidesoperationsagis-santsurunseulargumentcommela racinecarree,cettegeneralisationestlaisseea titre d’exer-ciceaulecteur. Nousneconsidereronsaussiquelesentiersnaturelsenraisonde la confusionqu’il pourraity avoir entrele symboledela soustractionet le signemoins.

Surcertainesmachinesa calculerdepoche,lescalculss’effectuentenmettantle symboled’operationapres les nombressur lesquelson effectuel’operation.On a alors unenotationdite postfixee. Danscertainslangagesdeprogrammation,c’estparexemplele casdeLisp oudeScheme,on ecrit lesexpressionsdefacon prefixeec’est-a-direquele symboled’operationprecedecettefois lesdeuxoperandes,ondefinit cesexpressionsrecursivement.Lesexpressionsprefixeescomprennent:

– dessymbolesparmiles ø suivants: + * ( )– desentiersnaturels

Une expressionprefixee estou bien un nombreentiernaturelou bien estde l’une desdeuxformes:

(+ t:uvt�w ) (* thuvtOw )ou A Ó et A Ô sontdesexpressionsprefixees.

Cettedefinition fait intervenir le nomde l’objet quel’on definit danssapropredefinitionmaison peutmontrerquecelane posepasde problemelogique.En effet, on peutcomparercettedefinition a celledesnombresentiers: “tout entiernaturelestou bien l’entier 0 ou bien

10.4. EVALUATION DESEXPRESSIONSARITHMETIQUESPREFIXEES 89

le successeurd’un entiernaturel”.On verifie facilementquelessuitesdesymbolessuivantessontdesexpressionsprefixees.

47(* 2 3)(+ 12 8)(+ (* 2 3) (+ 12 8))(+ (* (+ 35 36) (+ 5 6)) (* (+ 7 8) (* 9 9)))

Leur evaluationdonnerespectivement47,6, 20,26et 1996.Pour representerune expressionprefixee en Java, on utilise ici un tableaudont chaque

elementrepresenteuneentitedel’expression.Ainsi lesexpressionsci-dessusserontrepresenteespardestableauxdetaillesrespectives1, 5, 5, 13,29.Leselementsdu tableausontdesobjetsatrois champs,le premierindiquela naturedel’entite : (symboleou nombre),le secondchampestrempli parla valeurdel’entite dansle casou celleci estunnombre,enfinle dernierchampestun caractererempli danslescasou l’entite estun symbole.

class Element {boolean estOperateur;int valeur;char valsymb;

}

Onutiliselesfonctionsdonneesci-dessuspourlespilesetony ajoutelesproceduressuivantes:

static int calculer (char a, int x, int y) {

switch (a) {case ’+’: return x + y;case ’*’: return x * y;

}return -1;

}

La procedured’evaluationconsisteaempilerlesresultatsintermediaires,la pile contiendradesoperateurset desnombres,maisjamaisdeuxnombresconsecutivement.On examinesucces-sivementlesentitesdel’expressionsi l’entite estun operateurou si c’estun nombreet quelesommetdela pile estunoperateur, alorsonempilecetteentite.Enrevanche,si c’estunnombreet qu’ensommetdepile il y a aussiun nombre,on fait agir l’operateurqui precedele sommetdepile surlesdeuxnombreseton repetel’operationsurle resultattrouve.

à qà à qàüA÷à qà 71qà

à71qà

5à71qà 781à q

781àà q

781à7à q

781àq

15q781à

9q15q781à

FIG. 10.5– Piled’evaluationdel’expressiondontle resultatest1996

static void inserer (Element x, Pile p)throws ExceptionPile

{Element y, op;

while (!(Pile.estVide(p) || x.estOperateur ||


Pile.valeur(p).estOperateur)) {y = Pile.valeur(p);Pile.supprimer(p);op = Pile.valeur(p);Pile.supprimer(p);x.valeur = calculer (op.valsymb, x.valeur, y.valeur);

}Pile.ajouter(x,p);

}

static int evaluer (Element u[])throws ExceptionPile

{Pile p = new Pile();

for (int i = 0; i < u.length ; ++i) {inserer (u[i], p);

}return Pile.valeur(p).valeur;

}

Dansce cas,il peutetreutile de donnerun exemplede programmeprincipalpilotant cesdi-versesfonctions.Remarquerqu’onsesertdesargumentssurla lignedecommandepourseparerlesdifferentsnombresouoperateurs.


Element exp[] = new Element [args.length];

for (int i = 0; i < args.length; ++i) {String s = args[i];if (s.equals ("+") || s.equals ("*"))

exp[i] = new Element (true, 0, s.charAt(0));else

exp[i] = new Element (false, Integer.parseInt(s), ’ ’);}try {

System.out.println (evaluer (exp));} catch (ExceptionPile x) {

System.err.println ("Pile " + x.nom);}

}

10.5 Operations courantessur leslistes

Nousdonnonsdansceparagraphequelquesalgorithmesdemanipulationdelistes.Ceux-cisontutilisesdansleslangagesou la listeconstitueunestructuredebase.La fonctionTail estuneprimitive classique,ellesupprimele premierelementd’uneliste

class Liste {

Object contenu;Liste suivant;

10.5. OPERATIONSCOURANTESSURLESLISTES 91

A Ó A Ô A � A:BÐ Tail Þ�Ð�ß

FIG. 10.6– Queued’uneliste

A Ó A Ô A �Ð

A:x Ó A:x Ô Ahx� AhxB8

A Ó A Ô A �Append Þ�Ð ê 8 ß

FIG. 10.7– ConcatenationdedeuxlistesparAppend

Liste (Object x, Liste a) {contenu = x;suivant = a;

}

static Liste cons (Object x, Liste a) {return new Liste (x, a);

}

static Object head (Liste a) {if (a == null)

erreur ("Head d’une liste vide.");return a.contenu;

}

static Liste tail (Liste a) {if (a == null)

erreur ("Tail d’une liste vide.");return a.suivant;

}

Des proceduressur les listes construisentune liste a partir de deux autres,il s’agit demettredeuxlistesboutaboutpourenconstruireunedontla longueurestegalea la sommedeslongueursdesdeuxautres.Dansla premiereprocedureappend , les deuxlistesne sontpasmodifiees; dansla secondenConc , la premiereliste esttransformeepour donnerle resultat.Toutefois,on remarqueraque,si append copiesonpremierargument,il partagela fin delistedesonresultatavecsondeuxiemeargument.

static Liste append (Liste a, Liste b) {if (a == null)

return b;else

return ajouter (a.contenu, append (a.suivant, b)) ;


A Ó A Ô A �Ð

Ahx Ó A:x Ô A:x� AhxB8

FIG. 10.8– ConcatenationdedeuxlistesparNconc

}

static Liste nConc (Liste a, Liste b) {if (a == null)

return b;else {

Liste c = a;while (c.suivant != null)

c = c.suivant;c.suivant = b;return a;

}}

Cettederniereprocedurepeutaussis’ecrirerecursivement:

static Liste nConc (Liste a, Liste b) {if (a == null)

return b;else {

a.suivant = nConc (a.suivant, c);return a;

}}

La proceduredecalculdel’image miroir d’uneliste Ð consistea construireuneliste danslaquelleles elementsde Ð sont rencontres dansl’ordre inversede ceuxde Ð . La realisationde cetteprocedureestun exerciceclassiquede la programmationsur les listes.On en donneici deuxsolutionsl’une iterative, l’autre recursive, la complexite esten

è Þ ð Ô ß doncquadra-tique,maisclassique.A nouveau,nReverse modifiesonargument,alorsqueReverse nele modifiepasetconstruitunenouvelle listepoursonresultat.

static Liste nReverse (Liste a) {Liste b = null;while (a != null) {

Liste c = a.suivant;a.suivant = b;

A Ó A Ô A �8

A B Ahy Ahz A/{ÿÐ

FIG. 10.9– Transformationd’unelisteaucoursdenReverse

10.5. OPERATIONSCOURANTESSURLESLISTES 93

A Ó A Ô A � AhBÐ

FIG. 10.10– Listecirculairegardee

b = a;a = c;

}return b;

}

static Liste reverse (Liste a) {if (a == null)

return a;else

return append (reverse (a.suivant),ajouter (a.contenu, null));

}

On peutaussiavoir uneversionlineairedela versionrecursive,graceaunefonctionauxiliaireaccumulantle resultatdansun desesarguments:

static Liste nReverse (Liste a) {return nReverse1 (null, a);

}

static Liste nReverse1 (Liste b, Liste a) {if (a == null)

return b;else

return nReverse1 (ajouter (a.contenu, b), a.suivant);}

Un autreexerciceformateurconsistea gererdeslistesdanslesquellesles elementssontrangesenordrecroissant.La procedured’ajoutdevientpluscomplexepuisqu’ondoit retrouverla positiondela celluleou il fautajouterapresavoir parcouruunepartiedela liste.

Nousnetraiteronscetexercicequedansle casdeslistescirculairesgardees, voir page81.Dansunetelle liste, la valeurdu champcontenu de la premierecellule n’a aucuneimpor-tance.On peuty mettrele nombred’elementsdela liste si l’on veut.Le champsuivant dela dernierecellulecontientlui l’adressedela premiere.

static Liste inserer (int v, Liste a) {

Liste b = a;while (b.suivant != a && v > head(b.suivant))

b = b.suivant;b.suivant = ajouter (v, b.suivant);a.contenu = head(a) + 1;return a;

}


Chapitr e 11

Arbr es

Nousavonsdejavu la notiondefonctionrecursivedansle chapitre2.Consideronsapresentson equivalent dansles structuresde donnees: la notion d’arbre.Un arbreestsoit un arbreatomique(unefeuille), soit un noeudet unesuitedesous-arbres.Graphiquement,un arbreestrepresente commesuit

ð[ÓðTÔ

ð �ð B

ð y ð z

ð {ð}|

ð}~ ð[Ó * ð[Ó1Ó

FIG. 11.1– Un exempled’arbre

Le noeud ð[Ó est la racine de l’arbre, ð y , ð z , ð { , ð}~ , ð[Ó * , ð[Ó1Ó sont les feuilles, ð[Ó , ðTÔ , ð � ,ð B , ð}| lesnoeudsinternes. Plusgeneralement,l’ensembledesnoeudsestconstitue desnoeudsinterneset desfeuilles.Contrairementa la botanique,on dessineles arbresavec la racineenhautet les feuillesversle basen informatique.Il y a biendesdefinitionsplusmathematiquesdesarbres,quenouseviteronsici. Si unebrancherelie un noeudð�Ñ a un noeudð í plus bas,on dira que ð�Ñ estun ancetre de ð í . Une propriete fondamentaled’un arbreestqu’un noeudn’a qu’unseulpere.Enfin,un noeudpeutconteniruneouplusieursvaleurs,et on parleraalorsd’arbres etiquetes et de la valeur (ou desvaleurs)d’un noeud.Les arbres binaires sontdesarbrestelsquelesnoeudsont auplus2 fils. La hauteur, on dit aussila profondeurd’un noeudestla longueurducheminqui le joint a la racine,ainsila racineestellememedehauteuræ , sesfils dehauteurÛ et lesautresnoeudsdehauteursuperieurea Û .

Un exempled’arbretresutilise eninformatiqueestla representationdesexpressionsarith-metiqueset plusgeneralementdestermesdansla programmationsymbolique.Noustraiteronscecasdansle chapitresurl’analysesyntaxique,etnousnousrestreindronspourl’instantaucas

95

96 CHAPITRE11. ARBRES

Là

5 L2 3

àL

10 10

L9 9

FIG. 11.2– Representationd’uneexpressionarithmetiqueparunarbre

desarbresderechercheou desarbresde tri. Toutefois,pourmontrerl’aspectfondamentaldela structured’arbre,onpeuttoutdesuitevoir quelesexpressionsarithmetiquescalculeesdansla section10.4serepresententsimplementpardesarbrescommedansla figure11.2pour (*(+ 5 (* 2 3)) (+ (* 10 10) (* 9 9))) . Cetterepresentationcontientl’essencedela structured’expressionarithmetiqueet fait doncabstractiondetoutenotationprefixeeoupostfixee.

11.1 Filesdepriorit e

Un premierexemplede structurearborescenteest la structurede tas(heap1)utiliseepourrepresenterdesfilesdepriorite. Donnonsd’abordunevision intuitive d’unefile depriorite.

On suppose,commeau paragraphe10.2, que desgensse presententau guichetd’unebanqueavec un numero ecrit sur un bout de papierrepresentantleur degre de priorite. Plusce nombreesteleve, plus ils sont importantset doivent passerrapidement.Bien sur, il n’y aqu’un seulguichetouvert,et l’employe(e)dela banquedoit traiterrapidementtoussesclientspourquetout le mondegardele sourire.La file despersonnesenattentes’appelleunefile depriorite. L’employe de banquedoit doncsavoir faire rapidementles 3 operationssuivantes:trouver un maximumdansla file de priorite, retirer cet elementde la file, savoir ajouterunnouvel elementa la file. Plusieurssolutionssontenvisageables.

La premiereconsisteamettrela file dansun tableauet a trier la file depriorite dansl’ordrecroissantdespriorites.Trouver un maximumet le retirer de la file estalorssimple: il suffitde prendrel’ elementde droite,et de deplacervers la gauchela bornedroite de la file. Maisl’insertion consistea faire unepassedu tri par insertionpour mettrele nouvel elementa saplace,cequi peutprendreun temps

è Þ ð ß ou ð estla longueurdela file.Uneautremethodeconsistea gererla file commeunesimplefile du chapitreprecedent,et

a rechercherle maximumachaquefois. L’insertionestrapide,maisla recherchedu maximumpeutprendreun temps

è Þ ð ß , dememequela suppression.Unemethodeeleganteconsisteagererunestructured’ordrepartielgraceaunarbre.La file

de ð elementsestrepresenteeparun arbrebinairecontenanten chaquenoeudun elementdela file (commeillustre dansla figure11.3).L’arbreverifie deuxproprietesimportantes: d’unepart la valeurde chaquenoeudestsuperieureou egalea celle de sesfils, d’autrepart l’arbreestquasicomplet,propriete quenousallonsdecrirebrievement.Si l’on divise l’ensembledesnoeudsen lignessuivant leur hauteur, on obtientengeneral dansun arbrebinaireuneligne æcomposeesimplementdela racine,puisuneligne Û contenantauplusdeuxnoeuds,etainside

1Le mot heapa malheureusementunautresensenPascal: c’estl’espacedanslequelsontalloueeslesvariablesdynamiquesreferenceesparunpointeurapresl’instructionnew. Il serabienclair d’apresle contextesi nousparlonsdetasausensdesfilesdepriorite oudu tasdePascalpourallouerlesvariablesdynamiques.

11.1. FILESDE PRIORITE 97

16

1

14

2

8

4

2

8

4

9

10

5

7

10

10

3

9

6

3

7

FIG. 11.3– Representationenarbred’un tas

Ð�M Ù9NÙ 161

142

103

84

105

96

37

28

49

710

FIG. 11.4– Representationentableaud’un tas

suite(la ligne Ù contenantauplus â Ñ noeuds).Dansun arbrequasicompletleslignes,excepteepeutetrela derniere,contiennenttoutesun nombremaximalde noeuds(soit â Ñ ). De plus lesfeuilles de la derniere ligne se trouvent toutesa gauche,ainsi tous les noeudsinternessontbinaires,excepte le plusadroitedel’avantdernierelignequi peutnepasavoir defils droit. Lesfeuillessonttoutessurla derniereet eventuellementl’avantderniereligne.

On peutnumerotercet arbreen largeur d’abord,c’est a dire dansl’ordre donne par lespetits numerosfigurant au dessusde la figure 11.3. Danscettenumerotationon verifie quetout noeudÙ a sonpereenposition ��Ùoä�â'� , le fils gauchedu noeudÙ est â:Ù , le fils droit â:ÙmàXÛ .Formellement,onpeutdirequ’untasestuntableauÐ contenantð entiers(oudeselementsd’unensembletotalementordonne) satisfaisantlesconditions:â ! â:Ù ! ð C Ð�M�â:Ù9N�#´Ð�M Ù9Nü ! â:Ù�à7Û ! ð C Ð�M�â:Ùyà7ÛON�#´Ð�M ÙgNCeci permetd’implementercet arbredansun tableaua (voir figure 11.4) ou le numero dechaquenoeuddonnel’indice del’ elementdu tableaucontenantsavaleur.

L’ajout d’un nouvel element� a la file consistea incrementerð puisaposerÐ�M ð NÚm� . Cecine representeplusun tascar la relation Ð�M ð ä�â/N�#�� n’est pasnecessairementsatisfaite.Pourobtenirun tas,il faut echangerla valeurcontenueaunoeudð et celle contenueparsonpere,remonteraupereet reitererjusqu’acequela conditiondestassoitverifiee.Ceciseprogrammeparunesimpleiteration(cf. la figure11.5).

static void ajouter (int v) {

++nTas;int i = nTas - 1;while (i > 0 && a [(i - 1)/2] <= v) {

a[i] = a[(i - 1)/2];i = (i - 1)/2;

}a[i] = v;

}


16

1

14

2

8

4

2

8

4

9

10

5

7

10

10

3

9

6

3

7

16

1

14

2

8

4

2

8

4

9

10

5

7

10

15

11

10

3

9

6

3

7

16

1

14

2

8

4

2

8

4

915

5

7

10

10

11

10

3

9

6

3

7

16

1

15

2

8

4

2

8

4

914

5

7

10

10

11

10

3

9

6

3

7

FIG. 11.5– Ajout dansun tas

16

1

15

2

8

4

2

8

4

9

14

5

7

10

10

11

10

3

9

6

3

7

10

1

15

2

8

4

2

8

4

9

14

5

7

10

10

3

9

6

3

7

15

1

10

2

8

4

2

8

4

9

14

5

7

10

10

3

9

6

3

7

15

1

14

2

8

4

2

8

4

9

10

5

7

10

10

3

9

6

3

7

FIG. 11.6– Suppressiondansun tas

11.1. FILESDE PRIORITE 99

On verifie que,si le tas a ð elements,le nombred’operationsn’excederapasla hauteurdel’arbre correspondant.Or la hauteurd’un arbrebinairecompletde ð noeudsest ��tð . DoncAjouter neprendpasplusde

è Þ ��tð ß operations.On peutremarquerquel’operationde recherchedu maximumestmaintenantimmediate

danslestas.Elle prendun tempsconstantè ÞwÛ/ß .

static int maximum () {

return a[0];}

Consideronsl’operationdesuppressiondupremierelementdela file. Il fautalorsretirerlaracinedel’arbrerepresentantla file, cequi donnedeuxarbres! Le plussimplepourreformerunseularbreestd’appliquerl’algorithmesuivant: onmetl’ elementle plusadroitedela derniereligne a la placedela racine,oncomparesavaleuraveccelledesesfils, on echangecettevaleuraveccelledu vainqueurdecetournoi,et on reiterecetteoperationjusqu’a cequela conditiondestassoit verifiee.Bien sur, il faut faireattention,quandun noeudn’a qu’un fils, et ne fairealorsqu’un petit tournoi a deux.Le placementdela racineenbonnepositionestillustre dansla figure11.6.

static void supprimer () {

int i, j;int v;

a[0] = a[nTas - 1];--nTas;i = 0; v = a[0];while (2*i + 1 < nTas) {

j = 2*i + 1;if (j + 1 < nTas)

if (a[j + 1] > a[j])++j;

if (v >= a[j])break;

a[i] = a[j]; i = j;}a[i] = v;

}

A nouveau,la suppressiondu premierelementdela file neprendpasun tempssuperieura lahauteurdel’arbre representantla file. Donc,pourunefile de ð elements,la suppressionprendè Þ ��tð ß operations.La representationdesfiles de prioritespar destaspermetdoncde faireles trois operationsdemandees: ajout,retrait,chercherle plusgranden ��Oð operations.Cesoperationssur les taspermettentde faire le tri HeapSort. Ce tri peut etreconsidere commealambique, maisil a la bonnepropriete d’etretoujoursentempsð��Oð (commele Tri fusion,cf page75).

HeapSortsediviseendeuxphases,la premiereconsisteaconstruireun tasdansle tableaua trier, la secondea repeter l’operationde prendrel’ elementmaximal, le retirer du tasen lemettanta droitedu tableau.Il restea comprendrecommenton peutconstruireun tasa partird’ un tableauquelconque.Il y a unemethodepeuefficace,maissystematique.On remarqued’abordque l’ elementde gauchedu tableauest a lui seulun tas.Puison ajoutea ce tas ledeuxiemeelementavecla procedureAjouter quenousvenonsdevoir, puisle troisieme,. . ..A la fin, on obtientbienun tasde Ö elementsdansle tableaua a trier. Le programmeest

static void heapSort () {

int i;


int v;

nTas = 0;for (i = 0; i < N; ++i)

ajouter (a[i]);for (i = N - 1; i >= 0; --i) {

v = maximum();supprimer();a[i] = v;

}}

Si on fait undecomptegrossierdesoperations,on remarquequ’onnefait pasplusde Ö �� Öoperationspourconstruirele tas,puisqu’il y a Ö appelsalaprocedureAjouter .Unemethodeplus efficace,quenousne decrironspasici, qui peutetretraitee a titre d’exercice,permetdeconstruirele tasen

è Þ�Övß operations.Dememe,dansla deuxiemephase,onnefait pasplusdeÖ �� Ö operationspourdefaire lestas,puisqu’onappelleÖ fois la procedureSupprimer .Au total, on fait

è Þ�Ö �� Övß operationsquellequesoit la distribution initiale du tableaua,commedansle tri fusion.On peutneanmoinsremarquerquela constantequi setrouve devantÖ �� Ö estgrande,caronappelledesproceduresrelativementcomplexespourfaireetdefairelestas.Cetri adoncun interet theorique,maisil estenpratiquebienmoinsbonqueQuicksortou le tri Shell.

11.2 Borne inf erieure sur le tri

Il aetebeaucoupquestiondutri. Onpeutsedemanders’il estpossibledetrier untableaudeÖ elementsenmoinsde Ö �� Ö operations.Un resultatanciendela theoriedel’informationmontrequec’estimpossiblesi on n’utilise quedescomparaisons.

Eneffet, il fautpreciserle modeledecalculquel’on considere.Onpeutrepresentertouslestris quenousavonsrencontrespardesarbresdedecision.La figure11.7representeuntel arbrepourle tri parinsertionsurun tableaude3 elements.Chaquenoeudinterneposeunequestionsurla comparaisonentre2 elements.Le fils degauchecorresponda la reponsenegative, le filsdroit a l’affirmatif. Lesfeuillesrepresententla permutationa effectuerpourobtenirle tableautrie.

Theoreme1 Le tri de Ö elements,fonde uniquementsur lescomparaisonsdeselementsdeuxa deux,fait au moins

è Þ�Ö �� Örß comparaisons.

Demonstration Tout arbre de decision pour trier Ö elementsa Ö�ý feuilles representanttoutesles permutationspossibles.Un arbrebinaire de Ö�ý feuilles a une hauteurde l’ordrede �� Ö�ý 1 Ö �� Ö parla formuledeStirling. �Corollaire 1 HeapSortet le tri fusionsontoptimaux(asymptotiquement).

En effet, ils accomplissentle nombrede comparaisonsdonne commeborneinferieuredansle theoremeprecedent.Mais, nousrepetonsqu’un tri commeQuicksortestaussitresbon enmoyenne.Le modeledecalculparcomparaisonsdonneuneborneinferieure,maispeut-onfairemieuxdansunautremodele?La reponseestoui, si ondisposed’informationsannexescommeles valeurspossiblesdeselementsÐ Ñ a trier. Par exemple,si les valeurssontcomprisesdansl’intervalle MzÛ ê 0 N , onpeutalorsprendreun tableau

8annexe de

0elementsqui contiendraen

8 íle nombrede Ð Ñ ayantla valeur

ï. Enunepassesur Ð , onpeutremplir le tableau

0, puisgenerer

le tableauÐ trie enunedeuxiemepasseennetenantcomptequedel’information rangeedans8. Cetri prend

è Þ 0 à¥â�Örß operations,cequi esttresbonsi0

estpetit.

11.3. IMPLEMENTATION D’UN ARBRE 101

Ð ÓFõ Ð ÔÐ Ô³õ Ð �

(1,2,3) Ð ÓFõ Ð �(1,3,2) (3,1,2)

Ð ÓFõ Ð �(2,1,3) Ð ÔÄõ Ð �

(2,3,1) (3,2,1)

FIG. 11.7– Exempled’arbrededecisionpourle tri

11.3 Impl ementationd’un arbr e

Jusqu’a present,les arbressontapparuscommedesentitesabstraitesou n’ont ete imple-mentesquepardestableauxenutilisantuneproprietebienparticulieredesarbrescomplets.Onpeutbiensur manipulerlesarbrescommeleslistesavecdesenregistrementset despointeurs.Tout noeudserarepresente par un enregistrementcontenantunevaleuret despointeursverssesfils. Unefeuille necontientqu’unevaleur. On peutdoncutiliser desenregistrementsavecvariantepoursignalersi le noeudestinterneouunefeuille.Pourlesarbresbinaires,lesdeuxfilsserontrepresentespar leschampsfilsG, filsD et il seraplussimpledesupposerqu’unefeuille estun noeuddontlesfils gaucheet droit ontunevaleurvide.

class Arbre {

int contenu;Arbre filsG;Arbre filsD;

Arbre (int v, Arbre a, Arbre b) {contenu = v;filsG = a;filsD = b;

}}

Pour les arbresquelconques,on peutgagnerplus d’espacememoireen considerantdesen-registrementsvariables.Toutefois,en Pascal,il y a unedifficulte de typagea considererdesnoeudsð -aires(ayant ð fils). On doit considererdestypesdifferentspour lesnoeudsbinaires,ternaires,. . . ou un gigantesqueenregistrementavec variante.Deux solutionssystematiquessontaussipossibles: la premiereconsistea considerer le cas ð maximum(commepour lesarbresbinaires)

class Arbre {

int contenu;Arbre[] fils;

Arbre (int v, int n) {contenu = v;fils = new Arbre[n];

}}


la deuxiemeconsisteaenchaıner lesfils dansuneliste

class Arbre {

int contenu;ListeArbres fils;

}

class ListeArbres {

Arbre contenu;ListeArbres suivant;

}

Aveclestaillesmemoiredesordinateursactuels,onsecontentesouventdela premieresolution.Mais, si les contraintesde memoiresontfortes,il faut serabattresur la deuxieme.Dansunebonnepartiede la suite,il ne seraquestionqued’arbresbinaires,et nouschoisironsdonclapremiererepresentationavecleschampsfilsG et filsD .

Consideronsapresentla constructiond’un nouvel arbrebinairec a partir dedeuxarbresaetb. Un noeudseraajoute a la racinedel’arbreet lesarbresa etb serontlesfils gaucheetdroitrespectivementdecetteracine.La fonctioncorrespondanteprendla valeurdu nouveaunoeud,lesfils gaucheet droit du nouveaunoeud.Le resultatseraun pointeurverscenoeudnouveau.Voici donccommentcreerl’arbredegauchedela figure11.8.

class Arbre {

int contenu;Arbre filsG;Arbre filsD;

Arbre (int v, Arbre a, Arbre b) {contenu = v;filsG = a;filsD = b;

}

public static void main(String args[]) {

Arbre a5, a7;a5 = new Arbre (12, new Arbre (8, new Arbre (6, null, null), null),

new Arbre (13, null, null));a7 = new Arbre (20, new Arbre (3, new Arbre (3, null, null), a5),

new Arbre (25, new Arbre (21, null, null),new Arbre (28, null, null)));

imprimer (a7);}

Unefois un arbrecree, il estsouhaitabledepouvoir l’imprimer. Plusieursmethodessontpos-sibles.La pluseleganteutiliselesfonctionsgraphiquesduMacintoshdrawString ,moveTo,lineTo . Une autreconsistea utiliser une notation lineaireavec desparentheses.C’est lanotation infixe utilisee courammentsi les noeudsinternessontdesoperateursd’expressionsarithmetique.L’arbreprecedents’ecrit alors

((3 3 ((6 8 nil) 12 13)) 20 (21 25 28))

Utilisons une methodeplus rustiqueen imprimant en alphanumerique sur plusieurslignes.Ainsi, en penchantun peula teteversla gauche,on peutimprimer l’arbre precedentcommesuit

11.3. IMPLEMENTATION D’UN ARBRE 103

20 25 2821

3 12 1386

3

La procedured’impressionprendcommeargumentl’arbre a imprimeret la tabulation a faireavantl’impression,c’estadire le nombred’espaces.Onremarqueraquetoutela difficultedelaprocedureestdebiensituerl’endroit ou oneffectueunretoura la ligne.Le resteestun simpleparcoursrecursifdel’arbreenseplongeantd’aborddansl’arbrededroite.

static void imprimer (Arbre a) {imprimer (a, 0);System.out.println ();

}

static void imprimer1(Arbre a, int tab) {

if (a != null) {System.out.print(leftAligned(3, a.contenu + "") + " ");

imprimer1(a.filsD, tab + 8);if (a.filsG != null) {

System.out.println ();for (int i = 1; i <= tab; ++i)

System.out.print (" ");}imprimer1(a.filsG, tab);

}}

static String leftAligned (int size, String s) {

StringBuffer t = new StringBuffer (s);for (int i = s.length(); i < size; ++i)

t = t.append(" ");return new String (t);

}

Nousavonsdoncvu commentrepresenterunarbredansunprogramme,commentle construire,et commentl’imprimer. Cettederniereoperationesttypique: pour explorer unestructurededonneerecursive(lesarbres),il estnatureld’utiliser desproceduresrecursives.C’estanouveauunemanierenonseulementnaturelle,maisaussitresefficacedansle caspresent.

Commepourleslistes(cf. page79), la structurerecursive desprogrammesmanipulantdesarbresdecouledela definitiondesarbres,puisquele typedesarbresbinairesverifie l’ equation:

Arbre DFE Arbre videG H Arbre J Element J Arbre

Commepour l’impression,on peut calculer le nombrede noeudsd’un arbreen suivant ladefinition recursive du typedesarbres:

static int taille (Arbre a) {

if (a == null) (* a � Arbre vide *)return 0;

else (* a � Arbre � Element � Arbre *)return 1 + taille (a.filsG) + taille (a.filsD);

}


L’ ecritureiterative dansle casdesarbresesten general impossiblesansutiliser unepile. Onverifie que,pour les arbresbinairesqui ne contiennentpasde noeudsunaires,la taille Y , lenombrede feuilles Ö�� et le nombrede noeudsinternesÖ verifient Y ÚÀÖ à�Ö�� et Ö��|ÚÛRà¥Ö .11.4 Arbr esde recherche

La rechercheentableet le tri peuventetreaussitraitesavecdesarbres.Nousl’avonsvu im-plicitementdansle casdeQuicksort.Eneffet, si ondessinelespartitionssuccessivesobtenuespar les appelsrecursifsde Quicksort,on obtientun arbre.On introduit pour les algorithmesde recherched’un elementdansun ensembleordonne la notion d’arbre binaire de recherchecelui-ci aurala propriete fondamentalesuivante: tousles noeudsdu sous-arbregauched’unnoeudontunevaleurinferieure(ouegale)a la sienneet touslesnoeudsdusous-arbredroit ontunevaleursuperieure(ou egale)a la valeurdu noeudlui-meme(commedansla figure11.8).Pourla rechercheentable,lesarbresderechercheont un interet quandla tableevoluetresra-pidement,quoiquelesmethodesavechachagesontsouventaussibonnes,maispeuventexigerdescontraintesdememoireimpossiblesa satisfaire. (En effet, il fautconnaıtre la taille maxi-malea priori d’unetabledehachage).Nousallonsvoir quele tempsd’insertiond’un nouvelelementdansun arbrederechercheprendun tempscomparableau tempsderecherchesi cetarbreestbien agence. Pourle moment,ecrivons les procedureselementairesde rechercheetd’ajoutd’un element.

static Arbre recherche (int v, Arbre a) {

if (a == null || v == a.contenu)return a;

else if (v < a.contenu)return recherche (v, a.filsG);

elsereturn recherche (v, a.filsD);

}

static Arbre ajouter (int v, Arbre a) {

if (a == null)a = new Arbre (v, null, null);

else if (v <= a.contenu)a.filsG = ajouter (v, a.filsG);

elsea.filsD = ajouter (v, a.filsD);

return a;}

A nouveau,desprogrammesrecursifscorrespondenta la structurerecursive desarbres.Laprocedurederechercherenvoieunpointeurversle noeudcontenantla valeurrecherchee,nullsi echec.Il n’y a pasici d’informationassocieea la cle rechercheecommeauchapitre1. Onpeutbiensur associeruneinformationa la cle rechercheeen ajoutantun champdansl’enre-gistrementdecrivant chaquenoeud.Dansle casdu bottin de telephone,le champcontenucontiendraitlesnomsetseraitdu typeString ; l’information seraitle numerodetelephone.

La recherchetested’abordsi le contenudela racineestegala la valeurrecherchee,sinononrecommencerecursivementla recherchedansl’arbre degauchesi la valeurestpluspetitequele contenudela racine,oudansl’arbrededroitedansle cascontraire.La procedured’insertiond’unenouvellevaleursuit le memeschema.Toutefoisdansle casdel’ egalite desvaleurs,nousla rangeonsici parconventiondansle sousarbredegauche.La procedureajouter modifiel’arbre de recherche.Si nousne voulonspasle modifier, nouspouvonsadoptercommedans

11.5. ARBRESEQUILIBRES 105

20

7

3

2

3

1

12

5

8

4

6

313

6

25

9

21

8

28

10

C 20

8

3

2

3

1

12

6

8

4

6

3

9

513

7

25

10

21

9

28

11

FIG. 11.8– Ajout dansun arbrederecherche

le casdeslistesla proceduresuivante,qui consommelegerementplusdeplace,laquelleplacepeutetrerecupereetresrapidementparle glaneurdecellules:

static Arbre ajouter (int v, Arbre a) {

if (a == null)return new Arbre (v, null, null);

else if (v <= a.contenu)return new Arbre (v, ajouter (v, a.filsG), a.filsD);

elsereturn new Arbre (v, a.filsG, ajouter (v, a.filsG));

}

Le nombred’operationsde la rechercheou de l’insertion dependdela hauteurdel’arbre.Si l’arbre estbien equilibre, pour un arbrede recherchecontenantÖ noeuds,on effectueraè Þ �� Örß operationspourchacunedesprocedures.Si l’arbre estun peigne,c’est a dire com-pletementfiliforme a gaucheou a droite, la hauteurvaudraÖ et le nombred’operationsseraè Þ�Övß pourla rechercheet l’ajout. Il apparaıt doncsouhaitabled’equilibrerlesarbresaufur etamesuredel’ajout denouveauxelements,cequenousallonsvoir dansla sectionsuivante.

Enfin,l’ordredanslequelsontrangeslesnoeudsdansunarbrederechercheestappeleordreinfixe. Il correspondau petit numero qui setrouve au dessusde chaquenoeuddansla figure11.8.Nousavonsdeja vu dansle casde l’ evaluationdesexpressionsarithmetiques(cf page88) l’ordre prefixe, danslequeltout noeudrecoit un numerod’ordre inferieura celui de touslesnoeudsdesonsous-arbredegauche,qui eux-memesontdesnumerosinferieursauxnoeudsdu sous-arbrede droite.Finalement,on peutconsiderer l’ordre postfixequi ordonned’abordle sous-arbredegauche,puis le sous-arbrededroite,et enfin le noeud.C’estun bonexerciced’ecrire un programmed’impressioncorrespondanta chacunde cesordres,et de comparerl’emplacementdesdifferentsappelsrecursifs.

11.5 Arbr esequilibr es

La notion d’arbreequilibre a ete introduiteen 1962par deuxrussesAdel’son-Vel’skii etLandis,etdepuiscesarbressontconnussousle nomd’arbresAVL. Il y amaintenantbeaucoupde variantesplus ou moinsfacilesa manipuler. Au risquede paraıtre classiqueset vieillots,nousparleronsprincipalementdesarbresAVL. Un arbreAVL verifiela propriete fondamentalesuivante: la differenceentreleshauteursdesfils gaucheet desfils droit detout noeudnepeutexceder1. Ainsi l’arbredegauchedela figure11.8n’estpasequilibre. Il viole la propriete aux


B

A

a b

c

CA

a

B

b c

FIG. 11.9– Rotationdansun arbreAVL

noeudsnumerotes2 et 7, touslesautresnoeudsvalidantla propriete. Lesarbresrepresentantdestas,voir figure11.5sonttrivialementequilibres.

Onpeutmontrerquela hauteurd’un arbreAVL de Ö noeudsestdel’ordre de �� Ö , ainsilestempsmisparla procedureRecherche vuepage104seronten

è Þ �� Örß .Il faut donc maintenir l’ equilibre de tous les noeudsau fur et a mesuredesoperations

d’insertionou desuppressiond’un noeuddansun arbreAVL. Poury arriver, on supposequetout noeudcontientun champannexe bal contenantla differencedehauteurentrele fils droitet le fils gauche.Cechamprepresentedoncla balanceou l’ equilibreentreleshauteursdesfilsdu noeud,et ons’arrangedoncpourmaintenir ×QÛ !m� ë � �l��! Û pourtoutnoeudpointe para.

L’insertion se fait commedansun arbrede recherchestandard,sauf qu’il faut mainte-nir l’ equilibre. Pour cela, il est commodeque la fonction d’insertion retourneune valeurrepresentantla differenceentrela nouvelle hauteur(apres l’insertion) et l’anciennehauteur(avant l’insertion). Quandil peuty avoir un desequilibretrop importantentrelesdeuxfils dunoeudou l’on insereun nouvel element,il faut recreerun equilibrepar unerotationsimple(figure11.9)ou unerotationdouble(figure11.10).Danscesfigures,les rotationssontprisesdansle casd’un reequilibragede la gauchevers la droite. Il existe bien sur les 2 rotationssymetriquesde la droiteversla gauche.On peutaussiremarquerquela doublerotationpeutserealiserparunesuitede deuxrotationssimples.Dansla figure11.10,il suffit de faireunerotationsimplede la droite vers la gauchedu noeud � , suivie d’une rotationsimplevers ladroite du noeud � . Ainsi en supposantdeja ecritesles proceduresde rotation rotD vers ladroiteet rotG versla gauche,la procedured’insertions’ecrit

static Arbre ajouter (int v, Arbre a) {return ajouter1 (v, a).p2;

}

static Paire ajouter1 (int v, Arbre a) {

int incr, r;Paire p;

r = 0;if (a == null) {

a = new Arbre (v, null, null);a.bal = 0;r = 1;

} else {if (v <= a.contenu) {

p = ajouter1 (v, a.filsG);incr = -p.p1;a.filsG = p.p2;

} else {p = ajouter1 (v, a.filsD);


��

Ð �8 Ó 8 Ô

ÿ C�

�Ð 8 Ó

�8 Ô ÿ

FIG. 11.10– DoublerotationdansunarbreAVL

incr = p.p1;a.filsD = p.p2;

}a.bal = a.bal + incr;if (incr != 0 && a.bal != 0)

if (a.bal < -1)/* La gaucheesttropgrande */if (a.filsG.bal < 0)

a = rotD (a);else {

a.filsG = rotG (a.filsG);a = rotD (a);

}elseif (a.bal > 1)

/* La droiteesttropgrande */if (a.filsD.bal > 0)

a = rotG (a);else {

a.filsD = rotD (a.filsD);a = rotG (a);

}else

r = 1;}return new Paire (r, a);

}

static class Paire {int p1;Arbre p2;

Paire (int r, Arbre a) {p1 = r;p2 = a;

}}

Clairementcetteprocedureprenduntempsè Þ �� Övß . Onverifieaisementqu’auplusuneseule

rotation(eventuellementdouble)estnecessairelorsdel’insertiond’un nouvel element.Il reste


arealiserlesproceduresderotation.Nousneconsideronsquele casdela rotationversla droite,l’autrecass’obtenantparsymetrie.

static Arbre rotD (Arbre a) {

Arbre b;int bA, bB, bAnew, bBnew;

b = a;a = a.filsG;bA = a.bal; bB = b.bal;b.filsG = a.filsD;a.filsD = b;// Recalculerle champa.balbBnew = 1 + bB - Math.min(0, bA);bAnew = 1 + bA + Math.max(0, bBnew);a.bal = bAnew;b.bal = bBnew;return a;

}

Il y a un petit calcul savant pour retrouver le champrepresentantl’ equilibreapres rotation.Il pourrait etre simplifie si nousconservionstoute la hauteurdu noeuddansun champ.Lapresentationavecleschampsbal permetdegarderlesvaleurspossiblesentre-2 et 2, detenirdoncsur3 bits, et d’avoir le rested’un mot machinepour le champcontenu . Avec la tailledesmemoiresactuelles,cecalculpeutserevelersurperflu.Toutefois,soient Q�Þ�Ð�ß , Q�Þ 8 ß et QmÞ�ÿEßles hauteursdesarbresÐ , 8 et ÿ de la figure11.9.En appliquantla definition du champbal ,lesnouvellesvaleurs

8 x ÞU�³ß et8 x ÞU�Pß deceschampsauxnoeuds� et � secalculentenfonction

desanciennesvaleurs8 ÞU�³ß et

8 ÞU�Pß par8 x ÞU�Pß Ú Q�Þ�ÿ-ßI×�QmÞ 8 ßÚ Q�Þ�ÿ-ßI×´Û>×��UQ�Þ�Ð�ß ê Q�Þ 8 ßT�>à7ÛRà��UQmÞ�Ð¢ß ê QmÞ 8 ßT�Ï×�QmÞ 8 ßÚ 8 ÞU�Pß�à7ÛRà��UQ�Þ�Ð�ßO×�QmÞ 8 ß ê æ��Ú Ûtà 8 ÞU�Pß[×��Jæ ê 8 ÞU�ÄßT�8 x ÞU�Äß Ú Ûtà��UQ�Þ 8 ß ê QmÞ�ÿEßT�Ä×�QmÞ�Ð¢ßÚ Ûtà Q�Þ 8 ß[×�QmÞ�Ð¢ßmà��Jæ ê QmÞ�ÿEßI×�Q�Þ 8 ßT�Ú Ûtà 8 ÞU�ÄßTà��Jæ ê 8 x ÞU�PßT�Les formulespour la rotation vers la gauches’obtiennentpar symetrie. On peut meme

remarquerquele champbal peuttenir sur 1 bit poursignalersi le sous-arbrea unehauteuregaleou non a celle de son sous-arbre“fr ere”. La suppressiond’un elementdansun arbreAVL estplusdurea programmer, et nousla laissonsenexercice.Elle peutdemanderjusqu’aè Þ �� Örß rotations.

Les arbresAVL sontdelicatsa programmera causedesoperationsde rotation.On peutmontrerquelesrotationsdeviennentinutilessi ondonneunpeudeflexibilit edansle nombredefils desnoeuds.Il existedesarbresderecherche2-3 avec2 ou 3 fils. L’exemplele plussimpleest celui desarbres2-3-4 amplementdecrits dansle livre de Sedgewick [47]. Un exempled’arbre2-3-4 estdecrit dansla figure 11.11.La propriete fondamentaled’un tel arbrede re-chercheestla memequepourlesnoeudsbinaires: toutnoeuddoit avoir unevaleursuperieureou egalea cellescontenuesdanssessous-arbresgauches,et unevaleur inferieure(ou egale)a cellesdesessous-arbresdroits.Lesnoeudsternairescontiennent2 valeurs,la premieredoitetrecompriseentrelesvaleursdessous-arbresgaucheset du centre,la deuxiemeentrecelles


20

ö2 12

2 2 3 8 8 13

28 32

21 25 30 33 37

FIG. 11.11– Exempled’arbre2-3-4

dessous-arbresducentreetdedroite.Onpeutdeviner aisementla conditionpourlesnoeudsa4 fils.

L’insertiond’un nouvel elementdansun arbre2-3-4sefait en eclatanttout noeudquater-nairequel’on rencontrecommedecrit dansla figure11.12.Cesoperationssontlocaleset nefont intervenir quele nombredefils desnoeuds.Ainsi, on garantitquel’endroit ou on inserela nouvelle valeurn’estpasun noeudquaternaire,et il suffit demettrela valeurdanscenoeuda l’endroit desire. (Si la racineestquaternaire,on l’ eclateen 3 noeudsbinaires).Le nombred’eclatementsmaximumpeut etre �� Ö pour un arbrede Ö noeuds.Il a ete mesure qu’enmoyennetrespeud’eclatementssontnecessaires.

Les arbres2-3-4 peuvent etreprogrammes en utilisant desarbresbinairesbicolores.Ons’arrangepour quechaquebranchepuisseavoir la couleurrougeou noire (en trait grassurnotrefigure11.13).Il suffit d’un indicateurbooleendanschaquenoeudpourdiresi la branchele relianta sonpereestrougeou noire.Lesnoeudsquaternairessontrepresentespar3 noeudsreliesen noir. Les noeudsternairesont unedoublerepresentationpossiblecommedecrit surla figure11.13.Lesoperationsd’eclatementseprogrammentalorsfacilement,et c’estun bonexerciced’ecrirela procedured’insertiondansun arbrebicolore.


�Ð �� @8 ÿ � A

C� �

Ð �8 ÿ

@� A

� �Ð 8 �� @

ÿ � A kC

�� Ð 8 �

ÿ �@

A kFIG. 11.12– Eclatementd’arbres2-3-4

�� Ð 8 ÿ � �

��

Ð 8�

ÿ �

� �Ð 8 ÿ �

��

Ð 8ÿ ou

�Ð �

8 ÿFIG. 11.13– Arbresbicolores

AnnexeA

Demarrer avecUnix

Unix estunsystemed’exploitationtresrepandudansle mondedela rechercheetdeplusenplusendehors,commele montrele succesfoudroyantdu dernierdesesavatars,Linux. C’estle systemequi estutilise a l’X pourl’enseignement.

Cechapitredecrit l’essentieldecequedoit savoir l’utilisateurd’Unix. La premieresectionrassembleles connaissancesde basesur l’environnementde travail, la deuxieme1 donneunapercu du reseauInternet,quecesoit en interneou enexterneet la troisiemedonnequelqueselementsdesecurite elementaire.

Lesprincipesdeconceptiondusystemesontdecritsauchapitre6.

A.1 Cequedoit savoir l’utilisateur

A.1.1 Pasdepanique!

Unix estunsystemed’exploitationrobuste.Il estimpossibleaunutilisateurd’arreterinvo-lontairementunordinateuraupointquele seulremedesoitun reboot.Si toutparaitbloque,onpeutsouvents’entirer avecunCtrl-c (toucheCtrl maintenueenfonceependantqu’ontapele c ) ou avecun desboutonsdela sourisqui fait apparaıtre un menu: aupire, sedeconnectersuffit a remettretoutenplace.

A.1.2 Demarraged’une session

Quandonselogesurunestationdetravail, ontapesonnomdelogin etsonmotdepasse.Sicelui-ci estaccepte, le systemelancel’installationd’un environnementstandardmulti-fenetrespour l’utilisateur. Danschaquefenetre (on dit aussiun xterm ) est lance un interpreteurdecommandes(un SHELL) qui attenden permanenceles commandesde l’utilisateur qu’il re-transmetausystemequi lesexecute.

A.1.3 Systemedefichiers

Unix organiselesfichiersdefacon arborescente,dansdesrepertoires.

Repertoires

On lesappelleaussidirectories. Un repertoireestuneboıte qui peutcontenirdesfichierset d’autresrepertoires(commeles cataloguesde MS-DOS, ou les dossiersdu Macintosh).

1lesdeuxpremieressectionsreprennentdesnotesdecoursdu magisteredel’ENS ecritesparDamienDoligezet Xavier Leroy.

111

112 ANNEXE A. DEMARRERAVEC UNIX

Exemplesderepertoires:

/users /bin /usr/local/bin

Ondesignelesfichiers(etlesrepertoires)contenusdansunrepertoirepar: nomderepertoire/ nomdefichier. Exemple: /bin/sh estle fichier sh contenudansle repertoire/bin . Lesreper-toiressontorganisesenarbre,c’est-a-direqu’ils sonttouscontenusdansunrepertoire(designepar / ) appele la racine. Chaquerepertoirecontientdeuxrepertoiresspeciaux(visiblesquandon tapels -a ) :

. designele repertoirelui-meme

.. designele peredu repertoire

Exemples: /users/cie1/. estle memerepertoireque/users/cie1 , /users/.. estle memeque/ , etc.

Chaqueutilisateura un home-directory. C’est l’endroit ou il rangesesfichiers.Le home-directoryapournom/users/cie ð / nom.Exemples: /users/cie7/jof fr e, /users/cie5/foch .

On peut aussidesignerle home-directoryd’un autreutilisateurpar le nom de login del’utilisateurprecede d’un tilde (le caractere˜ ). Exemple: ˜foch .

Nomsde fichiers

Un nom de fichier qui commencepar / est dit absolu. Il est interprete en partantde laracine,etendescendantdansl’arbre.Un nomdefichierqui necommencepaspar/ estrelatif.Il est interprete en partantdu repertoire courant. Le repertoirecourantest initialement(aumomentou vousvousconnectez)votrehome-directory.

Exemples: /users/cie7/jo ffr e/ fo o estun nom (ou chemin)absolu.bar estunnomrelatif. Il designeunfichierappelebar etsituedansle repertoirecourant.Le fichierexactdontil s’agit dependdoncdevotrerepertoirecourant.

Remarque: Le seulcaracterespecialdanslesnomsdefichiersestle slash/ . Un nomdefichierpeutavoir jusqu’a 255caracteres,et contenirunnombrequelconquedepoints.

Commandespour visiter le systemede fichiers

– pwd affichele repertoirecourant.Exemple:poly% pwd/users/cie5/foch

– cd changele repertoirecourant.Si on nelui donnepasd’argument,on retournedanslehome-directory. Exemple:poly% cd ..poly% pwd/users/cie5poly% cdpoly% pwd/users/cie5/foch

– mkdir creeunnouveaurepertoire,(presque)vide,qui necontientque. et ..– rmdir supprimeunrepertoirevide.Si le repertoirecontientautrechoseque. et .. ca

nemarchepas.– mvrenommeunfichier, maispeutaussile deplacerd’un repertoireaunautre.Exemple:

poly% cdpoly% mkdir foopoly% emacs barpoly% mv bar foo/bar2poly% cd foo

A.1. CE QUE DOIT SAVOIR L’UTILISATEUR 113

poly% pwd/users/cie5/foch/foopoly% lsbar2

– rm -i foo supprimele fichier foo , attentionil fautmanipulercettecommandeavecprecautioncar on risque de detruire un fichier utile et il est alors impossiblede lerecupererparla suite.

– ls liste les fichiers et les repertoiresqu’on lui donneen arguments,ou le repertoirecourantsi on ne lui donnepasd’argument.ls ne liste pas les fichiers dont le nomcommencepar . , cequi expliquepourquoi. et .. n’apparaissentpasci-dessus.

Lesdroits d’acces

Chaquefichier a plusieursproprietesassociees: le proprietaire, le groupeproprietaire, ladatede dernieremodification,et les droits d’acces. On peutexaminercesproprietesgraceal’option -lg de ls . Exemple:

poly% ls -lg

drw- r-- r-- 1 foch cie5 512 Sep 30 17 :56 foo-rw- r-- r-- 1 foch cie5 7 Sep 30 17 :58 bar

nomdu fichierdatededernieremodif.

taille enoctetsgroupeproprietaire

proprietairedroitsdesautres

droitsdu groupedroitsdu proprietaire

type

Type - pourlesfichiers,d pourlesrepertoires.Droits du propri etaire

r ou - droit delire le fichier (r pouroui, - pournon)wou - droit d’ecriredansle fichierx ou - droit d’executerle fichierou devisite pourun repertoire

Droits du groupe Commelesdroits du proprietaire,maiss’appliqueauxgensqui sontdansle groupeproprietaire.

Droits desautres Commeles droits du proprietaire,maiss’appliqueauxgensqui sontni leproprietaire,ni dansle groupeproprietaire.

Propri etaire Le nomde login de la personnea qui appartientcefichier. Seulle proprietairepeutchangerlesdroitsou le grouped’un fichier.

Groupepropri etaire Le nomdugroupedu fichier. Lesgroupessontdesensemblesd’utilisa-teursqui sontfixesparl’administrateurdusysteme.

Taille Enoctets.

Pourchangerlesdroitsd’un fichier, la commandeestchmod. Exemples:chmod a+x foo ajoute(+) le droit d’execution(x ) pour tout le monde(all) au fichier

foochmod g-r bar enleve (- ) le droit delecture(r ) pourlesgensdu groupe(group)surle

fichierbarchmod u-w gee enleve (- ) le droit d’ecriture(w) pourle proprietaire(user)surle fichier

gee


A.1.4 Comment obtenir de l’aide

mancommandeMontrepageparpagele manueldecommande. FaireEspace pourpasserala pagesuivante,q pour quitter avant la fin. Pourquitter, on peutaussifaire Ctrl-c ,qui interromptla plupartdescommandesUnix.

man -k mot Donnela liste descommandesindexeessur le mot-cle mot, avecun resume decequ’ellesfont enuneligne.En Linux, man -K estplusconvivial.

Bien sur, pourcomprendrecommentmarcheman, on tapeman man...Danslesprogrammesinteractifs(elm , maple ), on peutsouventobtenirdel’aide entapant?ou h. Enfin, on peutaussiposerdesquestionsaux utilisateurshabituelsdessallesinforma-tiques; certainsensaventtreslong.

A.1.5 Raccourcis pour lesnomsdefichiers

Il estennuyeuxd’avoir a taperun nom completde fichier commenabuchodonosor ,quoiquetcsh fassede la completion automatique(taperles premiereslettres,suivies de latoucheTab).

Il estencoreplusennuyeuxd’avoir ataperunelistedefichierspourlesdonnerenargumentsa unecommande,comme: cc -o foo bar.c gee.c buz.c gog.c . Pourevitercesproblemes,on peututiliser desjokers (wildcardsenanglais.)

Une etoile * dansun nomdefichier estinterpreteepar le shell comme“n’importe quellesequencedecaracteresqui necommencepasparun point.” Exemple: cc -o foo *.c .

Pourinterpreterl’ etoile, le shell va faire la liste detouslesnomsdefichiersdu repertoirecourantqui necommencentpaspar. etqui finissentpar.c Ensuite,il remplace*.c parcetteliste (trieeparordrealphabetique)dansla ligne decommande,et executele resultat,c’est-a-direparexemple: cc -o foo bar.c buz.c foo.c gee.c gog.c .

On a aussile?, qui remplaceun (et exactementun) caracterequelconque.Par exemple,ls ?* liste touslesfichiers,y comprisceuxdontle nomcommenceparunpoint.

La forme [abcd] remplaceun caracterequelconqueparmia, b, c , d. Enfin, [âbcd]remplaceun caracterequelconquequi nesetrouve pasparmia, b, c , d.

Exemple: echo /users/* affiche la memechoseque ls /users . (La commandeecho secontented’affichersesarguments.)

Attention:– C’estle shellqui fait le remplacementdesargumentscontenantunjoker. Onnepeutdonc

pasfaire mv *.c *.bak , car le shell va passera mv les argumentsfoo.c bar.cfoo.bak bar.bak , etmvnesaitpasquelfichier remplacer.

– Attentionauxespaces.Si voustapezrm * ˜ , le shell remplacel’ etoilepar la liste desfichierspresents,et ils seronttouseffaces.Si voustapezrm *˜ , seulslesfichiersdontle nomfinit parun tilde seronteffaces.

Interlude: commenteffacerunfichiernomme?* ?Onnepeutpastaperrm ?* carle shellremplace?* parla listedetouslesfichiersdu repertoirecourant.Onpeuttaperrm -i * quisupprimetous les fichiers,maisen demandantconfirmationa chaquefichier. On repondnoa toutesles questionssauf rm: remove ?*? . Autre methode: utiliser les mecanismesdequotation(voir chapitresuivant).

A.1.6 Variables

Le shell a desvariables.Pour designerle contenud’une variable,on ecrit le nom de lavariableprecede d’un dollar. Exemple: echo $HOMEaffiche le nom du home-directorydel’utilisateur.

On peutdonnerunevaleuraunevariableavecla commandesetenv :

A.2. LE RESEAU DE L’X 115

poly% setenv DISPLAY coucou:0poly% echo $DISPLAYcoucou:0

Lesvaleursdesvariablessontaccessiblesauxcommandeslanceesparle shell.L’ensembledecesvaleursconstituel’ environnement. Onpeutaussisupprimerunevariabledel’environne-mentavecunsetenv .

Quelquesvariablesd’environnement:

PRINTER Pourlescommandesd’impression.Contientle nomdel’imprimantesurlaquelleilfautenvoyer vosfichiers.

EDITOR Utiliseeparelm etbeaucoupd’autrescommandes.Contientle nomdevotreediteurdetextesprefere.

VISUAL La memechosequ’EDITOR.

SHELL Contientle nomdevotreshellprefere.

HOMEContientle nomdevotrehome-directory.

USERContientvotrenomdelogin.

LOGNAMELa memechosequeUSER.

PATH Contient une liste de repertoiresdanslesquelsle shell va chercherles commandesexecutables.

DISPLAY Contientle nomdela machinequi affiche.

A.1.7 Le chemind’accesaux commandes

La variablePATHcontientle chemind’accesauxcommandes.Le shell l’utilise pourtrou-ver lescommandes.Il s’agit d’uneliste derepertoiresseparespardes : . La plupartdescom-mandessontenfait desprogrammes,c’est-a-diredesfichiersqu’on trouve dansle systemedefichiers.Quandvoustapezls , parexemple,le shellexecutele fichier /bin/ls . Pourtrouverce fichier, il cherchedansle premierrepertoiredu PATHun fichier qui s’appellels . S’il netrouve pas,il chercheensuitedansle deuxiemerepertoireet ainsi de suite.S’il ne trouve lacommandedansaucunrepertoiredu PATH, le shellafficheun messaged’erreur. Exemple:

poly% slsl: Command not found.

A.2 Le r eseaude l’X

Le reseauInternetrelie presde100millions d’utilisateursdansle mondeen juillet 99, cenombreesten croissancetresrapideil a ete multiplie par 5 en 4 ans.Avec le systemeUnix,les machiness’interfacentfacilementa l’Internet, certainsservicessontaussidisponiblessurMacintoshou PC.Le reseaulocal del’X contientplusieurssous-reseauxpourleseleves,pourles laboratoireset pour l’administration.Le reseaudeselevesrelie leschambres,lessallesdeTD (sallesPCou Hp), la machinesil (passerelleversl’Internet).

Physiquement,dansunechambre,on connectesamachineparun petit cablemuni d’uneprise RJ45.Une ligne en pairestorsadees10Base/Tva de la chambrea un local danslebatiment.La il y a un concentrateur(hub) qui mixe tout le trafic sur une fibre optique10Mbit/s. Il y aunhubetunefibrepourchaqueetage.Lesfibres(unevingtaine)sontregroupeessur FDDI (Fiber Data DistributedInterface) par un routeursitue au RdC de la DSI. Le toutestcertifie a 10 Megabit/s, et fonctionnevraisemblablementa 100Mbit/s. DansunesalledeTD, les stationsUnix et les imprimantessontconnecteesau reseau.Logiquement,la partie10Base/Tsupportele protocoleEtherneta10 Mbit/s.


Toute machinea une adresseInternet,de chiffres (192.104.247.103 pour poly ) ousymbolique(poly.polytechnique.fr ) qui sont les memesadressesquepour le courrierelectronique.A l’int erieur de l’X, le suffixe polytechnique.fr est inutile. Les PC de lasalle35ontdesnomsd’os (radius , cubitus , . . .), lesstationsHp dela salle34 desnomsdepoissons(carpe , lieu , . . .), cellesdela salle36 desnomsdevoitures(ferrari , bugatti ,. . .) LesPCdela salle33ontdesnomsdedepartement(loire , marne , . . .).PourlesPC,il fautrentrerl’adresseInternetmanuellement.Dansles sallesTD, elle estecriteen facede chaquechaise.

Voici uneliste deservicescourants(cf. la referenceMzÛEâ/N pourbeaucoupplusdedetails).

slogin Pourseconnectersuruneautremachineety executerdescommandes.

sftp Pour transferer desfichiersdepuisuneautremachine.Sur certainesmachines,on peutfairedestransfertssansy avoir un compte,enseconnectantsousle nom anonymous ;d’ou le nomde“anonymousFTP”, ou “FTP anonyme”, donne a cettemethodedetrans-fert defichiers.

xrn Pourlire les“News” (le foruma l’ echellemondiale).

xwais Pourinterrogerdesbasesdedonneesparmots-cle.

xarchie Pourobtenirlessourcesdomainepublic surle reseau.

netscapePourconsulterlessitesmulti-mediaduWorld WideWeb.

ir c Pourperdresonenergie adiscuteravecle mondeentier.

eudora Pourlire soncourriersurMac.

fetch Pourfaireftp depuislesMac.

Certainsservices(connexions internes,courrier, news) sontdisponiblesdepuistoutema-chinedu reseaudeseleves.Les autres(et en particulier les connexions a l’Internet) ne sontdisponiblesquedepuisla machinesil . Il convient doncd’ouvrir unesessionsur sil pouraccedera touslesservicesdel’Internet.

A.3 Un peude securite

Unix aetecreedansuntempsou le reseaun’etaitpasaussietenduqu’aujourd’hui,etou onfaisaitconfianceauxutilisateurs.L’experiencea montre qu’il valait mieuxsemontrerprudentquandon utilise Unix commepasserellepourseconnectera distance.Nousneparleronspasici ducourrierelectronique,pourlequellesproceduresamettreenœuvresontpluscomplexes.Il estfortementconseille desemettreenrapportavecla DSI pourapprendrecommentlire soncourrierdepuissachambresanssefairesniffer sonmot depasse.

A.3.1 Mots depasse

Beaucoupdeprogrammesutilisentdesmotsdepasse: login (surpoly , sursil ), connec-tion a distance(slogin ), courrierelectronique.La securite exige quetouscesmotsdepassesoientdifferentset difficiles a trouver. Rappelonsquelquesconsignesde base.La premiereestquele mot de passesoit le plus long possible(generalement,on demande8 caracteres),et n’existedansaucundictionnaireconnu(francais,anglais,languematernellesdiverses,etc.),de sortea resisteraux attaquespar enumerationexhaustive desdictionnairespresentssur lereseau.Il n’estpasbondechoisirdesnomstrop facilementidentifiables(le pire etantle motdepasseÚ nomdelogin ou le prenomassocie aunom),ceuxdesoncopainou sacopine,sonchienou sonpoissonrouge,ou leur datedenaissance.De legeresmodificationsa desmotsdecetypenesontpassuffisantes,si lesreglesdechangementsonttropsimples(renversementdesmots,permutationdesvoyelles,etc.).De meme,il estpreferabledemelangerlettres,chiffres,caracteresspeciaux(a l’exceptionnotabledu #, de@etdeslettresaccentuees).

A.3. UN PEUDE SECURITE 117

Suggeronsdeuxmoyensclassiquesderesoudreceprobleme: le premierestdechoisirunesequencedecaracterescompletementaleatoires,depreferencefacileamemoriser(maisn’etantpassusceptibledesattaquesdecritesci-dessus,commele classiqueAZERTY). Le secondestdechoisirunephrasecodeetdechoisircommemotdepasselespremiereslettresdechaquemot.

A.3.2 Accesa distance

En Unix standard,il existedeuxutilitairesdeconnectiona distance,rlogin et telnet .Cesdeux programmesont la facheusepropriete de faire circuler les mots de passeen clairsur le reseau,cequi permetde lescaptureraupassagepourpouvoir ensuitesesubstituerauxutilisateurslegitimes.Pour pallier ce probleme,cesdeux programmesont ete retires de lacirculationet remplacespar l’unique programmeslogin qui chiffre lesmotsdepasseavantde lesenvoyer sur le reseau.Il estmemepossible,si besoinest,defaireappela un modetressur, qui utilisedel’authentificationa clefspubliques,detypeRSA.

Pourtransfererlesfichiers,le programmestandard,ftp , souffre egalementdeceproblemedetransfertdesmotsdepasseenclair. Il a ete remplace parsftp .

Touscesprogrammess’utilisentdefacon transparentepourl’utilisateur, commedansl’ex-emplequi suit :

monpc% slogin poly -l moimoi@poly’s password:Last login: Fri Feb 9 13:42:04 from monpc.polytech

Digital UNIX V4.0G (Rev. 1530); Fri Oct 13 09:25:47 MET DST 2000************************************ ****** ***** ****** ***** ***** ** ** Bienvenue sur POLY ** ************************************* ****** ***** ****** ***** ***** *No mail.Shell is /usr/local/bin/tcshbilbo%

Dans le casd’une utilisation depuix Linux, il suffit d’aller chercherl’installation stan-darddisponiblesur http://www.in2 p3.f r/s ec ur it e/ . La lecturede la documenta-tion d’accompagnementestrecommandee.


AnnexeB

Utilisation avanceedu SHELL

B.1 Complements

B.1.1 Quotation

Avectouscescaracteresspeciaux1, commentfairepourpasserdesargumentsbizarresaunecommande?Parexemple,commentfaireafficherunpoint d’interrogationsuivi d’uneetoileetd’un dollar parecho ? Le shell fournit desmecanismespource faire.Cesontlesquotations.Le plussimpleestle backslash_ . Il suffit deprecederuncaracterespeciald’un backslash,et leshell remplacecesdeuxcaracterespar le caracterespecialseul.Evidemment,le backslashestlui-memeun caracterespecial.

Attention,toutceciesttresdependantdela machineet lesexemplesci-dessousnesontpasgarantis.

Exemples:

poly% echo \*\$*$poly% echo \\\\\*\\\$\\*\$

Un autremoyen estd’inclure unechaıne de caracteresentreapostrophes(simplequotes)’ .Tout ce qui setrouve entredeuxapostrophesserapasse tel quel par le shell a la commande.Exemple:

poly% echo ’$?*\’$?*\

Enfin, on peut utiliser desguillemets(doublequotes)" . Les guillemetsse comportentcommeles apostrophes,a uneexceptionpres : les dollarset les backslashessont interpretesentrelesguillemets.Exemple:

poly% echo "$HOME/*"/users/cie5/foch/*

Une techniqueutile : Quandon juxtaposedeux chaınes de caracteresquotees,le shell lesconcatene,etellesneformentqu’unargument.Exemple:

poly% echo "’"’"’’"

Quantaux interactionspluscompliquees(backslashesa l’int erieurdesguillemets,guille-metsa l’int erieurdesapostrophes,etc.),le meilleurmoyendesavoir si cadonnebienle resultatattenduestd’essayer. La commandeecho estbienutile danscecas.

1Onsuit ici encorelesnotesdecoursdu magisteredel’ENS ecritesparDamienDoligezet Xavier Leroy.

119

120 ANNEXE B. UTILISATION AVANCEEDU SHELL

Derniereformedequotation: ‘ commande‘ . Le shellexecutela commande, lit la sortiedela commandemotparmot,et remplace‘ commande‘ parla listedecesmots.Exemple:

poly% echo ‘ls‘Mail News bin foo g7 lib misc marne.aux marne.dvi marne.logpoly% ls -lg ‘which emacs‘-rwxr-xr-x 1 root system 765952 Dec 17 1992 /usr/local/bin/emacs

La commandewhich cmdemployeeci-dessusaffichesursasortiele nomabsoludufichierexecute parle shellquandon lancela commandecmd.

poly% which emacs/usr/local/bin/emacs

B.1.2 Redirectionset filtr es

Chaquecommandea uneentreestandard, unesortiestandard, et unesortied’erreur. Pardefaut, l’entree standardest le clavier, la sortie standardest l’ ecran(la fenetre),et la sortied’erreurestaussil’ ecran(la fenetre).

On peut rediriger la sortie standardd’une commandevers un fichier (caractere >). Leresultatdela commandeseraplace dansle fichieraulieu des’affichersurl’ ecran.Exemple:

poly% ls -l >foo

Le resultatde ls -l nes’affichepasa l’ ecran,maisil estplace dansle fichier foo . On peutalorstaper

poly% more foo

pourlire le fichierpageparpage.Onpeutaussiredirigerl’entreestandardd’unecommande(caractere<). La commandelira

alorsle fichieraulieu duclavier. Exemple:

poly% elm joffre <foo

envoie parmail a JosephJoffre le resultatdela commandels -l detout a l’heure.Onpeutaussitapermore <foo qui estequivalentamore foo carmore sansargument

lit sonentreestandardet l’affichepageparpagesurle terminal.

On peut aussise passerdu fichier intermediairegracea un pipe (caractere | ). Un pipeconnectedirectementla sortiestandardd’unecommandesurl’entreestandardd’uneautrecom-mande.Exemple: pourafficherpageparpagela listedesfichiersdu repertoirecourant,faire

ls -l | more

La panopliecompletedesredirectionsestla suivante:

> changela sortiestandarddela commandepourla placerdansunfichier.

< changel’entreestandarddela commandepourla prendredansun fichier.

>& placela sortiestandardet la sortieerreurdansunfichier.

| branchela sortiestandarddela commandedegauchesurl’entreestandarddela commandededroite.

|& branchela sortiestandardetlasortieerreurdela commandedegauchesurl’entreestandarddela commandededroite.

>> changela sortiestandardpourl’ajouter a la fin d’un fichierexistant.

>>& placela sortiestandardet la sortieerreura la fin d’un fichierexistant.

B.1. COMPLEMENTS 121

Remarques: Normalement,uneredirectionavec > sur un fichier qui existedeja effacelecontenudu fichier avantd’y placerle resultatde la commande.Il existeuneoptionqui dit aushell tcsh derefuserd’effacerle fichier.

Le pipe avec |& est utile pour capturertout ce qui sort d’une commande.Exemple :ls -R / |& more affichepageparpagela liste de touslesfichiersdu systeme,sansquelesmessagesd’erreurderangentl’affichage.

Une ligne de commandescontenantdes | s’appelleun pipe-line.Quelquescommandessouventutiliseesdanslespipe-linessont:

more a la fin du pipe-line,affichele resultatpageparpage,pourlaisserle tempsdele lire.

wc comptele nombredecaracteres,demotset delignesdesonentree.

grep cherchedanssonentreeleslignescontenantun motdonne,et lesecrit sursasortie.

sort lit toutesleslignesdesonentree,lestrie, et lesecrit dansl’ordre sursasortie

tail ecrit sursasortielesderniereslignesdesonentree.

head ecrit sursasortielespremiereslignesdesonentree.

cat copieplusieursfichierssursasortie.

fold coupeleslignesdesonentreea80caractereset ecrit le resultatsursasortie.

Exemples:

poly% cat glop buz >toto

Concatenelesfichiersglop etbuz et placele resultatdanstoto .

poly% wc -w /usr/dict/words

Affichele nombredemotsdu dictionnaireUnix.

poly% grep gag /usr/dict/words | tail

Afficheles20 derniersmotsdudictionnairequi contiennentla chaınegag .

B.1.3 Processus

Si on lanceunecommandequi prendbeaucoupdetemps,on peutl’interrompreentapantCtrl-c . Ceci interrompt(definitivement)la commande.On peut aussiexecuterune com-mandeentachedefond. Le shellrendalorsla mainavantla fin dela commande.Pourle faire,on ajouteun& a la fin dela commande:

poly% javac grosfichier.java &

Cettecommandelancele compilateurjavac en parallele avec le shell.On reprendla mainimmediatement,sansattendrelafin del’executiondelacommande.Onpeutdonctaperd’autrescommandespendantquela precedentes’execute.La commandeps ou ps -x montreou ensontlestachesdefond :

poly% psPID TT STAT TIME COMMAND

4450 p9 S 0:00 /usr/local/bin/tcsh4782 p9 S 0:02 javac grosfichier.java4841 p9 R 0:00 ps

Unix estun systememulti-taches, c’est-a-direqu’il peutexecuterplusieursprogrammesa lafois. Un processusestun programmeen train des’executer. La commandeps affiche la listedesprocessusquevousavez lances.Chaqueprocessusa un numero.C’est la colonnePID ci-dessus.Le shell creeun nouveauprocessuspourexecuterchaquecommande.Pourunecom-mande“normale” (sans&), il attendquele processustermine,indiquantquela commandeafini des’executer. Pourunecommandeentachedefond(avec&), le shelln’attendpas.Onpeutinterrompre(“tuer”) un processusavant la fin, avec la commandekill -9 (plus le numerodu processus).


poly% kill -9 4782poly% ps

PID TT STAT TIME COMMAND4450 p9 S 0:00 /usr/local/bin/tcsh4851 p9 R 0:00 ps

Si on lancegrosprogramme et qu’on a oublie le &, cen’estpasgrave : on commencepartaper<Ctrl-Z> , puisbg pourmettrele programmeenarriere-plan.Tantqu’ony est,si c’estvraimentun grosprogrammequi tournelongtemps,il estconseille de lui donneruneprioritefaibleparrespectpour lesautresutilisateurs,a l’aide dela commandenice . Par exemple,onlance(jamaisdegrosprogrammessurpoly svp!) :

coucou% nice ./grosprogramme > resultats &

qui permetde lancerle programmeentachedefond, avecsortiedesresultatsdansun fichier,avecunefaiblepriorite.

B.2 Programmation

Le shell peutaussiexecuterdescommandesprisesdansun fichier. Un fichier contenantdescommandespour le shell estappele un script. C’est en fait un programmeecrit danslelangagedu shell. Ce langagecomprendnon seulementles commandesquenousavonsdejavues,maisaussidesstructuresdecontrole (constructionsconditionnelleset boucles).Il existeenfait plusieursshells,ayantdeslangagesdecommandesdifferents.Jusqu’ici,onapriscommeexemplele shellcsh etsavariantetcsh . Pourla programmationdushell,nousallonsutiliserle shell sh , qui a un meilleur langagede commandes.Notonsqu’il existe plusieursshellsconviviaux, qui rajoutentdesoptionsa /bin/sh (c’est le casdebash ). Cequenousavonsvu jusqu’ici s’appliqueaussibien a sh qu’a csh , a l’exceptionde setenv et de certainesredirections.Pouretreun script,un fichierdoit commencerparla ligne :

#!/bin/sh

Il doit aussiavoir le droit d’execution(bit x ). (Le #!/bin/sh sur la premiereligne indiquequecescriptdoit etreexecute parle shellsh .)

B.2.1 Structuresde controle

– for var in liste dechaınes; do commandes; doneAffectesuccessivementa la variablede nom var chaquechaıne de caracteresdanslaliste dechaınes, et executelescommandesunefois pourchaquechaıne.Rappel: $varaccedea la valeurcourantede var. La partiecommandesestunesuitedecommandes,separeespardes; ou desretoursa la ligne.(Tousles; danscettesyntaxe peuventaussietreremplacespardesretoura la ligne.)Exemple: for i in * ; do echo $i ; done affiche touslesfichiersdu reper-toire courant,unparligne.

– if commande; then commandes; else commandes; fiExecutel’une ou l’autre deslistesdecommandes, suivantquela premierecommandeareussiou non(voir ci-dessous).

– while commande; do commande; doneExecutelescommandesdemaniererepeteetantquela premierecommandereussit.

– case chaıne inpattern) commande; ;. . .pattern) commande; ;

esacExecutela premierecommandetelle quela chaıne estde la formepattern. Un pattern

B.2. PROGRAMMATION 123

estunmotcontenanteventuellementlesconstructions* ,?, [a-d] , avecla memesigni-ficationquepourlesraccourcisdanslesnomsdefichiers.Exemple:case $var in

[0-9]* ) echo ’Nombre’;;[a-zA-Z]* ) echo ’Mot’;;* ) echo ’Autre chose’;;

esac

B.2.2 Codede retour

On remarquequela conditiondescommandesif et while estunecommande.Chaquecommanderenvoie uncodederetour(qui estignore enutilisationnormale).Si le codeest0, lacommandeareussi; sinon,la commandeaechoue.Parexemple,le compilateurcc renvoie uncoded’erreurnonnul si le fichier compile contientdeserreurs,ous’il n’existepas.

Lescommandesif et while considerentdoncle codederetour0 comme“vrai”, et toutautrecodecomme“f aux”.

Il existeunecommandetest , qui evaluedesexpressionsbooleennespasseesenargument,etrenvoieuncodederetourenfonctionduresultat.Elleestbienutilepourlesscripts.Exemple:

if test $var = foothen echo ’La variable vaut foo’else echo ’La variable ne vaut pas foo’fi

B.2.3 Variables

Danslesscripts,on peututiliser desvariablesdefiniesa l’exterieur(avecsetenv ), maisaussidefinir sespropresvariableslocalesau script.On donneunevaleura unevariableavecunecommandedela formenom-de-variableÚ valeur.

On aaussidesvariablesspeciales,initialiseesautomatiquementaudebut du script:$* La listedetouslesargumentspassesauscript.$# Le nombred’argumentspassesauscript.$1 , $2 , . . . Lesargumentspassesauscript.$ ? Le codederetourdela dernierecommandelancee.$ ! Le numerodeprocessdela dernierecommandeentachedefond.$$ Le numerodeprocessdu shelllui-meme.

B.2.4 Commandesinternes

Certainescommandesdu shellnesontpasdesprogrammesmaisdescommandesinternes.Ellessontdirectementreconnueset executeespar le shell.Un exempledecommandeinterneestcd . C’est le repertoirecourantdu shellqui estmodifie parcd , cequi signifiequele scriptsuivant:

#! /bin/shcd $1

nemarchepas,car le shell lanceun autreshellpourexecuterle script.C’estcesous-shellquichangesonrepertoirecourant,et cechangementestperduquandle sous-shellmeurt.

B.2.5 Fichier de demarrage

Il existe un script special, qui est execute au momentou on se connecte.Ce script estcontenudansle fichier $HOME/.login . C’est ce fichier qui vousdit s’il y a de nouveaux


messagesdanspolyaf, si vousavez du courrier, etc . . .. Chacunpeutainsi personnalisersonenvironnementaudebut dechaquesession.Onaquelquesinformationssurla “customization”enutilisantle menuAide (boutondedroitedela sourissurfondd’ecran).

B.3 Bibliographie Unix

Utiliser UnixMzÛON Steve Bourne,“The Unix system”,Addison-Wesley. Traductionfrancaise: “Le systemeUnix”, Intereditions.Unevued’ensembledu systemeUnix. Leschapitressur l’ editionet le traitementdetexte sontdepasses.

Programmer sousUnixM�â/N BrianKernighan,RobPike,“The Unix programmingenvironment”,Addison-Wesley. Tra-duction francaise: “L’environnementde la programmationUnix”, Intereditions.Uneautrevued’ensembledu systemeUnix, plusorienteeversla programmationenC et enshell.M�â 8 Ù W N M. J.Bach,ConceptiondusystemeUNIX. PrenticeHall, Masson,1993.M ü N Jean-MarieRifflet, “La programmationsousUnix”. ProgrammationenC et enshell (pasmal).

Traitement de texteM ø N LeslieLamport,“LATEX user’s guideandreferencemanual”.Addison-Wesley, 1986.Toutsurle traitementdetexte LATEX.M ÷ N DonaldE. Knuth. “The TEXbook”. Addison-Wesley, 1984.Tout, absolumenttout sur letraitementde texte TEX. LATEX esten fait uneextensionde TEX, un peuplus simpleautiliser; maisbeaucoupde commandessontcommunesaux deux,et non documentesdans M ø N .M ù N RaymondSeroul.“Le petit livre de TEX”. Intereditions.Petit sous-ensemblede M ÷ N ; plusaccessible,cependant.M ú N M. Goossens,F. Mittelbach,A. Samartin,“The LATEXcompanion”,Addison-Wesley. Unereference.

Le langageCM ö N Brian Kernighan,DennisRitchie,“The C programminglanguage”,Prentice-Hall.Traduc-tion francaise: “Le langageC”, Intereditions.Le livre dereferencesurle langageC.M û N SamuelHarbison,Guy Steele.“C : a referencemanual”.Une autrebonnedescriptiondulangageC.

Utiliser le r eseauMzÛ-æ'N BrendanP. Kehoe,“Zen andtheartof theInternet— A beginner’s guideto theInternet”.(Non publie.)Un exemplairesetrouve ensalleSun.MzÛAÛON Ed Krol, “The wholeInternetuser’s guide& catalog”,O’Reilly & Associates,1992.

AnnexeC

SyntaxeBNF deJava

Cequi suitestunesyntaxe sousformeBNF (BackusNaurForm). Chaquepetit paragrapheestla definition souvent recursive d’un fragmentdesyntaxe denommeeparun nom(malheu-reusementen anglais).Chaqueligne corresponda differentesdefinitionspossibles.L’indiceoptionalseramispoursignalerl’aspectfacultatifdel’objet indicee.Certainsobjets(token) se-ront supposeepreedefinis : IntegerLiteral pouruneconstanteentiere,Identifierpourtout iden-tificateur, . . .La syntaxe du langagenegarantitpasla concordancedestypes,certainesphrasespouvant etresyntaxiquementcorrectes,maisfaussespourlestypes.

Goal:CompilationUnit

C.1 Contanteslitt erales

Literal:IntegerLiteralFloatingPointLiteralBooleanLiteralCharacterLiteralStringLiteralNullLiteral

C.2 Types,valeurs,et variables

Type:PrimitiveTypeReferenceType

PrimitiveType:NumericTypeboolean

NumericType:IntegralTypeFloatingPointType

IntegralType: one ofbyte short int long char

FloatingPointType: one of

125

126 ANNEXE C. SYNTAXE BNF DE JAVA

float double

ReferenceType:ClassOrInterfaceTypeArrayType

ClassOrInterfaceType:Name

ClassType:ClassOrInterfaceType

InterfaceType:ClassOrInterfaceType

ArrayType:PrimitiveType [ ]Name [ ]ArrayType [ ]

C.3 Noms

Name:SimpleNameQualifiedName

SimpleName:Identifier

QualifiedName:Name . Identifier

C.4 Packages

CompilationUnit:PackageDeclarationopt ImportDeclarationsopt TypeDeclarationsopt

ImportDeclarations:ImportDeclarationImportDeclarationsImportDeclaration

TypeDeclarations:TypeDeclarationTypeDeclarationsTypeDeclaration

PackageDeclaration:package Name ;

ImportDeclaration:SingleTypeImportDeclarationTypeImportOnDemandDeclaration

SingleTypeImportDeclaration:import Name ;

TypeImportOnDemandDeclaration:

C.5. CLASSES 127

import Name . * ;

TypeDeclaration:ClassDeclarationInterfaceDeclaration;

Modifiers:ModifierModifiers Modifier

Modifier: one ofpublic protected privatestaticabstract final native synchronized transient volatile

C.5 Classes

C.5.1 Declaration de classe

ClassDeclaration:Modifiersopt class Identifier Superopt Interfacesopt ClassBody

Super:extends ClassType

Interfaces:implements InterfaceTypeList

InterfaceTypeList:InterfaceTypeInterfaceTypeList , InterfaceType

ClassBody: �ClassBodyDeclarationsopt �

ClassBodyDeclarations:ClassBodyDeclarationClassBodyDeclarationsClassBodyDeclaration

ClassBodyDeclaration:ClassMemberDeclarationStaticInitializerConstructorDeclaration

ClassMemberDeclaration:FieldDeclarationMethodDeclaration

C.5.2 Declarationsdechamps

FieldDeclaration:Modifiersopt Type VariableDeclarators;

VariableDeclarators:VariableDeclarator


VariableDeclarators, VariableDeclarator

VariableDeclarator:VariableDeclaratorIdVariableDeclaratorId= VariableInitializer

VariableDeclaratorId:IdentifierVariableDeclaratorId[ ]

VariableInitializer:ExpressionArrayInitializer

C.5.3 Declarationsdemethodes

MethodDeclaration:MethodHeaderMethodBody

MethodHeader:Modifiersopt Type MethodDeclaratorThrowsoptModifiersopt void MethodDeclaratorThrowsopt

MethodDeclarator:Identifier ( FormalParameterListopt )MethodDeclarator[ ]

FormalParameterList:FormalParameterFormalParameterList , FormalParameter

FormalParameter:Type VariableDeclaratorId

Throws:throws ClassTypeList

ClassTypeList:ClassTypeClassTypeList , ClassType

MethodBody:Block;

C.5.4 Initialieurs statiques

StaticInitializer:static Block

C.5.5 Declarationsdeconstructeurs

ConstructorDeclaration:Modifiersopt ConstructorDeclaratorThrowsopt ConstructorBody

ConstructorDeclarator:SimpleName( FormalParameterListopt )

C.6. INTERFACES 129

ConstructorBody:�ExplicitConstructorInvocationopt BlockStatementsopt �

ExplicitConstructorInvocation:this ( ArgumentListopt ) ;super ( ArgumentListopt ) ;

C.6 Interfaces

InterfaceDeclaration:Modifiersopt interface Identifier ExtendsInterfacesopt InterfaceBody

ExtendsInterfaces:extends InterfaceTypeExtendsInterfaces , InterfaceType

InterfaceBody:�InterfaceMemberDeclarationsopt �

InterfaceMemberDeclarations:InterfaceMemberDeclarationInterfaceMemberDeclarationsInterfaceMemberDeclaration

InterfaceMemberDeclaration:ConstantDeclarationAbstractMethodDeclaration

ConstantDeclaration:FieldDeclaration

AbstractMethodDeclaration:MethodHeader;

C.7 Tableaux

ArrayInitializer:�VariableInitializersopt , opt �

VariableInitializers:VariableInitializerVariableInitializers , VariableInitializer

C.8 Blocset instructions

Block: �BlockStatementsopt �

BlockStatements:BlockStatementBlockStatementsBlockStatement

BlockStatement:LocalVariableDeclarationStatement


Statement

LocalVariableDeclarationStatement:LocalVariableDeclaration;

LocalVariableDeclaration:Type VariableDeclarators

Statement:StatementWithoutTrailingSubstatementLabeledStatementBlockStatementsBlockStatementsIfThenStatementIfThenElseStatementWhileStatementForStatement

StatementNoShortIf:StatementWithoutTrailingSubstatementLabeledStatementNoShortIfIfThenElseStatementNoShortIfWhileStatementNoShortIfForStatementNoShortIf

StatementWithoutTrailingSubstatement:BlockEmptyStatementExpressionStatementSwitchStatementDoStatementBreakStatementContinueStatementReturnStatementSynchronizedStatementThrowStatementTryStatement

EmptyStatement:;

LabeledStatement:Identifier : Statement

LabeledStatementNoShortIf:Identifier : StatementNoShortIf

ExpressionStatement:StatementExpression;

StatementExpression:AssignmentPreIncrementExpressionPreDecrementExpressionPostIncrementExpressionPostDecrementExpressionMethodInvocationClassInstanceCreationExpression

IfThenStatement:

C.8. BLOCSET INSTRUCTIONS 131

if ( Expression) Statement

IfThenElseStatement:if ( Expression) StatementNoShortIfelse Statement

IfThenElseStatementNoShortIf:if ( Expression) StatementNoShortIfelse StatementNoShortIf

SwitchStatement:switch ( Expression) SwitchBlock

SwitchBlock:�SwitchBlockStatementGroupsopt SwitchLabelsopt �

SwitchBlockStatementGroups:SwitchBlockStatementGroupSwitchBlockStatementGroupsSwitchBlockStatementGroup

SwitchBlockStatementGroup:SwitchLabels BlockStatements

SwitchLabels:SwitchLabelSwitchLabels SwitchLabel

SwitchLabel:case ConstantExpression:default :

WhileStatement:while ( Expression) Statement

WhileStatementNoShortIf:while ( Expression) StatementNoShortIf

DoStatement:do Statementwhile ( Expression) ;

ForStatement:for ( ForInitopt ; Expressionopt ; ForUpdateopt )

Statement

ForStatementNoShortIf:for ( ForInitopt ; Expressionopt ; ForUpdateopt )

StatementNoShortIf

ForInit:StatementExpressionListLocalVariableDeclaration

ForUpdate:StatementExpressionList

StatementExpressionList:StatementExpressionStatementExpressionList, StatementExpression

BreakStatement:


break Identifieropt ;

ContinueStatement:continue Identifieropt ;

ReturnStatement:return Expressionopt ;

ThrowStatement:throw Expression ;

SynchronizedStatement:synchronized ( Expression) Block

TryStatement:try Block Catchestry Block Catchesopt Finally

Catches:CatchClauseCatchesCatchClause

CatchClause:catch ( FormalParameter) Block

Finally:finally Block

C.9 Expressions

Primary:PrimaryNoNewArrayArrayCreationExpression

PrimaryNoNewArray:Literalthis( Expression)ClassInstanceCreationExpressionFieldAccessMethodInvocationArrayAccess

ClassInstanceCreationExpression:new ClassType ( ArgumentListopt )

ArgumentList:ExpressionArgumentList , Expression

ArrayCreationExpression:new PrimitiveType DimExprs Dimsoptnew ClassOrInterfaceType DimExprs Dimsopt

DimExprs:DimExprDimExprs DimExpr

C.9. EXPRESSIONS 133

DimExpr:[ Expression ]

Dims:[ ]Dims [ ]

FieldAccess:Primary . Identifiersuper . Identifier

MethodInvocation:Name ( ArgumentListopt )Primary . Identifier ( ArgumentListopt )super . Identifier ( ArgumentListopt )

ArrayAccess:Name [ Expression ]PrimaryNoNewArray [ Expression ]

PostfixExpression:PrimaryNamePostIncrementExpressionPostDecrementExpression

PostIncrementExpression:PostfixExpression++

PostDecrementExpression:PostfixExpression--

UnaryExpression:PreIncrementExpressionPreDecrementExpression+ UnaryExpression- UnaryExpressionUnaryExpressionNotPlusMinus

PreIncrementExpression:++ UnaryExpression

PreDecrementExpression:-- UnaryExpression

UnaryExpressionNotPlusMinus:PostfixExpression˜ UnaryExpression! UnaryExpressionCastExpression

CastExpression:( PrimitiveType Dimsopt ) UnaryExpression( Expression) UnaryExpressionNotPlusMinus( Name Dims ) UnaryExpressionNotPlusMinus

MultiplicativeExpression:


UnaryExpressionMultiplicativeExpression* UnaryExpressionMultiplicativeExpression/ UnaryExpressionMultiplicativeExpression% UnaryExpression

AdditiveExpression:MultiplicativeExpressionAdditiveExpression+ MultiplicativeExpressionAdditiveExpression- MultiplicativeExpression

ShiftExpression:AdditiveExpressionShiftExpression<< AdditiveExpressionShiftExpression>> AdditiveExpressionShiftExpression>>> AdditiveExpression

RelationalExpression:ShiftExpressionRelationalExpression< ShiftExpressionRelationalExpression> ShiftExpressionRelationalExpression<= ShiftExpressionRelationalExpression>= ShiftExpressionRelationalExpressioninstanceof ReferenceType

EqualityExpression:RelationalExpressionEqualityExpression== RelationalExpressionEqualityExpression!= RelationalExpression

AndExpression:EqualityExpressionAndExpression& EqualityExpression

ExclusiveOrExpression:AndExpressionExclusiveOrExpressionˆ AndExpression

InclusiveOrExpression:ExclusiveOrExpressionInclusiveOrExpression| ExclusiveOrExpression

ConditionalAndExpression:InclusiveOrExpressionConditionalAndExpression&& InclusiveOrExpression

ConditionalOrExpression:ConditionalAndExpressionConditionalOrExpression|| ConditionalAndExpression

ConditionalExpression:ConditionalOrExpressionConditionalOrExpression? Expression : ConditionalExpression

AssignmentExpression:ConditionalExpressionAssignment

Assignment:

C.9. EXPRESSIONS 135

LeftHandSide AssignmentOperatorAssignmentExpression

LeftHandSide:NameFieldAccessArrayAccess

AssignmentOperator: one of= *= /= %= += -= <<= >>= >>>= &= ˆ= |=

Expression:AssignmentExpression

ConstantExpression:Expression

Bibliographie Java� ¡O¢Exploring Java, 2nd edition,Pat Niemeyer et JoshuaPeck628 pages,O’Reilly, ISBN :1-56592-271-9.1997.� l£/¢

TheJavaLanguageSpecification, JamesGosling,Bill Joy etGuySteele,AddisonWesley,ISBN : 0-201-63456-2.1996.� l¤/¢

Javain a Nutshell, David Flanagan,O’Reilly, ISBN : 1-56592-262-X,1997.� ]¥�¢Javaexamplesin a Nutshell, David Flanagan,O’Reilly, ISBN : 1-56592-371-5.1997.


Bibliographie

[1] HaroldAbelson,GeraldJ.Sussman,StructureandInterpretationof ComputerPrograms,MIT Press,1985.

[2] Adobe SystemsInc., PostScriptLanguage, Tutorial and Cookbook, Addison Wesley,1985.

[3] Al V. Aho,Ravi Sethi,Jeff D. Ullman,Compilers: Principles,Techniques,andTools, Ad-disonWesley, 1986.En francais: Compilateurs : principes,techniquesetoutils, trad.parPierreBoullier, PhilippeDeschamp,Martin Jourdan,BernardLorho, MoniqueMazaud,InterEditions,1989.

[4] HenkBarendregt, TheLambdaCalculus,Its SyntaxandSemantics, NorthHolland,1981.

[5] Daniele Beauquier, JeanBerstel,PhilippeChretienne,Elementsd’algorithmique, Mas-son,Paris,1992.

[6] JonBentley, ProgrammingPearls, AddisonWesley, 1986.

[7] ClaudeBerge,La theoriedesgrapheset sesapplications, Dunod,Paris,1966.

[8] JeanBerstel,Jean-EricPin,Michel Pocchiola,Mathematiqueset Informatique, McGraw-Hill, 1991.

[9] NoamChomsky, Marcel Paul Schutzenberger, Thealgebraic theoryof context freelan-guagesdansComputerProgrammingandFormal Languages, P. Braffort, D. Hirschberged.North Holland,Amsterdam,1963

[10] ThomasH. Cormen,CharlesE. Leiserson,RonaldL. Rivest, Algorithms, MIT Press,1990.

[11] Patrick Cousot,Introductiona l’algorithmique et a la programmation, EcolePolytech-nique,Coursd’Informatique,1986.

[12] ShimonEven,GraphAlgorithms, ComputerSciencePress,Potomac,Md, 1979.

[13] Adele Goldberg, Smalltalk-80: the language and its implementation, Addison-Wesley1983.

[14] David Goldberg, What Every ComputerScientistShouldKnow About Floating-PointArithmeticc, ComputingSurveys,23(1),Mars1991.

[15] GastonH. Gonnet,RiccardoBaeza-Yates,Handbookof AlgorithmsandDataStructures,In PascalandC, AddisonWesley, 1991.

[16] Mike J.C. Gordon,RobinMilner, LockwoodMorris, Malcolm C. Newey, ChrisP. Wad-sworth, A metalanguage for interactiveproof in LCF, In 5th ACM Symposiumon Prin-ciplesof ProgrammingLanguages,1978,ACM Press,New York.

[17] RonL. Graham,DonaldE. Knuth,OrenPatashnik,Concretemathematics: a foundationfor computerscience, AddisonWesley, 1989.

[18] SamuelP. Harbison,Modula-3, PrenticeHall, 1992.

[19] JohnH. Hennessy, David A. Patterson,ComputerArchitecture, A QuantitativeApproach,MorganKaufmannPublishers,Inc. , 1990.

137

138 BIBLIOGRAPHIE

[20] KathleenJensen,Niklaus Wirth, PASCALusermanualand report : ISO PASCALstan-dard, Springer, 1991.(1ereeditionen1974).

[21] GerryKane,Mips,RISCArchitecture, MIPSComputerSystems,Inc.,PrenticeHall, 1987.

[22] Brian W. Kernighan,DennisM.Ritchie, The C programminglanguage, PrenticeHall,1978.En francais : Le Langage C, trad. par Thierry Buffenoir, ManuelsinformatiquesMasson,8emetirage,1990.

[23] Brian W. Kernighan,PIC–alanguage for typesettinggraphics, SoftwarePractice& Ex-perience12(1982),1-20.

[24] Dick B. Kieburtz,StructuredProgrammingAndProblemSolvingWith Algol W, PrenticeHall, 1975.

[25] StephenC.Kleene,IntroductiontoMetamathematics, NorthHolland,6emeedition,1971.(1ereen1952).

[26] DonaldE. Knuth,TheTEXbook, AddisonWesley, 1984.

[27] DonaldE. Knuth,TheMetafontbook, AddisonWesley, 1986.

[28] DonaldE. Knuth, FundamentalAlgorithms.TheArt of ComputerProgramming, vol 1,AddisonWesley, 1968.

[29] DonaldE. Knuth,Seminumericalalgorithms,TheArt of ComputerProgramming, vol 2,AddisonWesley, 1969.

[30] DonaldE. Knuth,SortingandSearching. TheArt of ComputerProgramming, vol 3, Ad-disonWesley, 1973.

[31] LeslieLamport,LATEX, User’s guide& ReferenceManual, AddisonWesley, 1986.

[32] Butler W. Lampsonet KenA. Pier, A Processorfor a High-PerformancePersonalCom-puter, XeroxPaloAlto ResearchCenterReportCSL-81-1.1981(aussidansProceedingsof SeventhSymposiumon ComputerArchitecture, SigArch/IEEE,La Baule,Mai 1980,pp.146–160.

[33] JanvanLeeuwen,Handbookof theoreticalcomputerscience, volumesA etB, MIT press,1990.

[34] M. Lothaire,Combinatoricson Words, Encyclopediaof Mathematics,CambridgeUni-versityPress,1983.

[35] Udi Manber, Introductionto Algorithms,A creativeapproach, AddisonWesley, 1989

[36] Bob Metcalfe,D. Boggs,Ethernet: Distributed Packet Switching for Local ComputerNetworks, Communicationsof theACM 19,7,Juillet 1976,pp 395–404.

[37] RobinMilner, A proposalfor Standard ML, In ACM SymposiumonLISPandFunctionalProgramming,pp184-197,1984,ACM Press,New York.

[38] RobinMilner, MadsTofte,RobertHarper, Thedefinitonof Standard ML, TheMIT Press,1990.

[39] Greg Nelson,SystemsProgrammingwith Modula-3, PrenticeHall, 1991.

[40] Eric Raymond,TheNew Hacker’s Dictionary, dessinsde Guy L. SteeleJr., MIT Press1991.

[41] Brian Randell,L. J.Russel,Algol 60 Implementation, AcademicPress,New York, 1964.

[42] Martin Richards,Theportability of theBCPLcompiler, SoftwarePracticeandExperience1 :2, pp.135-146,1971.

[43] Martin Richards,Colin Whitby-Strevens,BCPL: TheLanguage andits Compiler, Cam-brideUniversityPress,1979.

[44] DenisM. RitchieetKenThompson,TheUNIX Time-SharingSystem, CommunicationsoftheACM, 17,7, Juillet1974,pp365–375(aussidansTheBell SystemTechnicalJournal,57,6,Juillet-Aout1978).

BIBLIOGRAPHIE 139

[45] Hartley Rogers,Theoryof recursive functionsand effectivecomputability, MIT press,1987,(editionoriginaleMcGraw-Hill, 1967).

[46] A. Sainte-Lague, Lesreseaux(ou graphes), MemoiredesSciencesMathematiques(18),1926.

[47] Bob Sedgewick, Algorithms, 2nd edition, Addison-Wesley, 1988. En francais : Algo-rithmesenlangage C, trad.parJean-MichelMoreau,InterEditions,1991.

[48] Ravi Sethi,ProgrammingLanguages,ConceptsandConstructs, AddisonWesley, 1989.

[49] BjarneStroustrup,TheC++ ProgrammingLanguage, AddisonWesley, 1986.

[50] RobertE. Tarjan,DepthFirstSearch andlinear graphalgorithms, SiamJournalof Com-puting,1, pages146-160,1972.

[51] ChuckP. Thacker, Ed M. McCreight,Butler W. Lampson,R. F. Sproull, D. R. Boggs,Alto : APersonalComputer, Xerox-PARC,CSL-79-11,1979(aussidansComputerStruc-tures: ReadingsandExamples,2ndedition, parSiewoiorek,Bell etNewell).

[52] PierreWeis,TheCamlReferenceManual,version2-6.1, Rapporttechnique121,INRIA,Rocquencourt,1990.

[53] PierreWeis,Xavier Leroy, Le langage Caml, InterEditions,1993.

Index

random , 67spell , 54evaluationd’expressions,89DivideandConquer, 74,75Heapsort, 99QuickDraw, 30Quicksort, 72heap, 96

Ackermann,57ajouter

dansunefile, 83dansuneliste,78

aleatoire,67appelparvaleur, 58arbre,95

implementation,101impression,102

arbrebinaire,95arbrederecherche,104arbresequilibres,105

arbres2-3,108arbres2-3-4,108arbresAVL, 105arbresbicolores,109rotations,106

Bentley, 73BNF

Java,125bonjour, 9break , 18

Caml,139cast, 12catch , 29chaınage,78chaınedecaracteres,31collision,49commentaire,9compilation,9conversions

explicites,12courbedu dragon,62

dessins,30dragon,62

ensembles,77Eratosthene,81

factorielle,55feuille, 95Fibonacci,55

iteratif,56file, 82

d’attente,83depriorite, 96gardee,85vide,83

finally , 30flocondevon Koch,60fonction,10fonction91,57fonctiondeMorris, 58fractales,60fusion,75

Godel,58graphique,30

hachage,49adressageouvert,51multiple,53

Hanoi,60Hoare,72

indecidable,58interclassement,75interface,86

Kleene,60Koch,60

liste,77desnombrespremiers,81gardee,81imagemiroir, 92vide,78

methode,10

140

INDEX 141

MacCarthy, 57main,10Maple,7, 71module,86Morris, 58

noeud,95noeudinterne,95nombrealeatoire,67

ordreinfixe,105ordrepostfixe,105ordreprefixe,105

pile, 86postfixee

notation,88

recursivite croisee,63racine,95recherche

dansuneliste,78dichotomique,47entable,46parinterpolation,48

Rogers,60

sentinelle,46,71supprimer

dansunefile, 83dansuneliste,80dansunepile, 87

syntaxeJava,125

tas,96TGiX, 30throw , 29throws , 30toursdeHanoi,60tri

borneinferieure,100bulle, 67fusion,75Heapsort,99insertion,70Quicksort,72selection,65Shell,71

triangledePascal,55try , 29Turing,58

142 INDEX

Tabledesfigures

6.1 ArchitecturedusystemeUNIX. . . . . . . . . . . . . . . . . . . . . . . . . . 366.2 Structureblocd’un fichier. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376.3 Diagrammedetransitiond’etats. . . . . . . . . . . . . . . . . . . . . . . . . . 41

7.1 Un exempledetablepourla rechercheentable . . . . . . . . . . . . . . . . . 467.2 Hachageparcollisionsseparees . . . . . . . . . . . . . . . . . . . . . . . . . 507.3 Hachageparadressageouvert . . . . . . . . . . . . . . . . . . . . . . . . . . 52

8.1 Appelsrecursifspourfib ¦ ¥l§ . . . . . . . . . . . . . . . . . . . . . . . . . . . 568.2 LestoursdeHanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.3 Floconsdevon Koch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628.4 La courbedu Dragon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

9.1 Exempledetri parselection . . . . . . . . . . . . . . . . . . . . . . . . . . . 669.2 Exempledetri bulle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689.3 Exempledetri parinsertion. . . . . . . . . . . . . . . . . . . . . . . . . . . . 709.4 PartitiondeQuicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

10.1 Ajout d’un elementdansuneliste . . . . . . . . . . . . . . . . . . . . . . . . 7810.2 Suppressiond’un elementdansuneliste . . . . . . . . . . . . . . . . . . . . . 7910.3 File gereeparun tableaucirculaire . . . . . . . . . . . . . . . . . . . . . . . . 8410.4 File d’attenteimplementeeparuneliste . . . . . . . . . . . . . . . . . . . . . 8610.5 Piled’evaluationdel’expressiondontle resultatest1996 . . . . . . . . . . . . 8910.6 Queued’uneliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9110.7 ConcatenationdedeuxlistesparAppend. . . . . . . . . . . . . . . . . . . . . 9110.8 ConcatenationdedeuxlistesparNconc . . . . . . . . . . . . . . . . . . . . . 9210.9 Transformationd’uneliste aucoursdenReverse . . . . . . . . . . . . . . . . . 9210.10Listecirculairegardee. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

11.1 Un exempled’arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9511.2 Representationd’uneexpressionarithmetiqueparunarbre . . . . . . . . . . . 9611.3 Representationenarbred’un tas . . . . . . . . . . . . . . . . . . . . . . . . . 9711.4 Representationentableaud’un tas . . . . . . . . . . . . . . . . . . . . . . . . 9711.5 Ajout dansun tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9811.6 Suppressiondansun tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9811.7 Exempled’arbrededecisionpourle tri . . . . . . . . . . . . . . . . . . . . . . 10111.8 Ajout dansunarbrederecherche. . . . . . . . . . . . . . . . . . . . . . . . . 10511.9 Rotationdansun arbreAVL . . . . . . . . . . . . . . . . . . . . . . . . . . . 10611.10Doublerotationdansun arbreAVL . . . . . . . . . . . . . . . . . . . . . . . . 10711.11Exempled’arbre2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10911.12Eclatementd’arbres2-3-4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11011.13Arbresbicolores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

143

Documents

Base Programmation