0% ont trouvé ce document utile (0 vote)

411 vues145 pages

Base Programmation

Transféré par

balha1985

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

411 vues145 pages

Base Programmation

Transféré par

balha1985

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Vous êtes sur la page 1/ 145

Les bases de la programmation et de lalgorithmique

Ecole polytechnique

Robert Cori

Jean-Jacques L evy

Franc ois Morain

Table des mati` eres

1 Les premiers pas en Java 1.1 Afcher du texte . . . . 1.2 Faire des calculs simples 1.3 Types primitifs . . . . . 1.4 Affectation . . . . . . . 1.5 Op erations . . . . . . . . 1.6 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 10 11 11 12 13 15 15 15 15 16 16 16 16 17 18 18 21 21 22 22 23 23 25 25 26 26 26 27 28 29 29 30 30 30 31 32

Suite dinstructions 2.1 Expressions bool eennes . . . . . . . 2.1.1 Op erateurs de comparaisons 2.1.2 Connecteurs . . . . . . . . . 2.2 Instructions conditionnelles . . . . . 2.2.1 If-else . . . . . . . . . . . . 2.2.2 Forme compacte . . . . . . 2.3 It erations boucles pour . . . . . . . 2.4 It erations tant que . . . . . . . . . . 2.5 Instructions de rupture de contr ole . 2.5.1 Aiguillage . . . . . . . . . .

Tableaux et cha nes de caract` eres 3.1 D eclaration et construction de tableaux . . 3.2 Utilisation de tableaux . . . . . . . . . . 3.3 Tableaux a ` plusieurs dimensions, matrices 3.4 Cha nes de caract` eres . . . . . . . . . . . 3.5 Arguments de main . . . . . . . . . . .

Composants dune classe 4.1 Fonctions . . . . . . . . . . . . . . . . . . 4.2 Constantes et variables globales . . . . . . 4.3 Les classes pour d enir des enregistrements 4.4 Constructeurs . . . . . . . . . . . . . . . . 4.5 Les m ethodes statiques et les autres . . . . 4.6 Utiliser plusieurs classes . . . . . . . . . . Compl ements 5.1 Exceptions . . . . . . . . . . . 5.2 Graphisme . . . . . . . . . . . 5.2.1 Fonctions e l ementaires 5.2.2 Rectangles . . . . . . 5.2.3 La classe Maclib . . 5.2.4 Jeu de balle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . .

4 6 Principes de base des syst` emes Unix 6.1 Survol du syst` eme . . . . . . . . . . . . 6.2 Le syst` eme de chiers . . . . . . . . . . 6.3 Les processus . . . . . . . . . . . . . . 6.3.1 Comment traquer les processus 6.3.2 Fabrication et gestion . . . . . . 6.3.3 Lordonnancement des t aches . 6.3.4 La gestion m emoire . . . . . . . 6.3.5 Le myst` ere du d emarrage . . . . 6.4 Gestion des ux . . . . . . . . . . . . . Retrouver linformation 7.1 Complexit e des algorithmes . . . 7.2 Recherche en table . . . . . . . . 7.2.1 La recherche s equentielle . 7.2.2 La recherche dichotomique 7.2.3 Insertion dans une table . 7.2.4 Hachage . . . . . . . . . . R ecursivit e 8.1 Fonctions r ecursives . . . . . . . . 8.1.1 Fonctions num eriques . . 8.1.2 La fonction dAckermann 8.1.3 R ecursion imbriqu ee . . . 8.2 Ind ecidabilit e de la terminaison . . 8.3 Proc edures r ecursives . . . . . . . 8.4 Fractales . . . . . . . . . . . . . . Tris s equentiels et r ecursifs 9.1 Quest-ce quun tri ? . . . . 9.2 M ethodes de tri e l ementaires 9.3 Analyse en moyenne . . . . 9.4 Le tri par insertion . . . . . 9.5 Quicksort . . . . . . . . . . 9.6 Le tri par fusion . . . . . . .

TABLE DES MATIERES

35 35 36 37 37 39 41 42 42 42 45 45 46 46 47 48 49 55 55 55 57 57 58 60 60 65 65 65 69 70 72 75 77 77 82 86 88 90 95 96 100 101 104 105

. . . . . . . . .

. . . . . .

. . . . . . .

. . . . . .

l 10 Structures de donn ees e ementaires 10.1 Listes cha n ees . . . . . . . . . . . . . . . . . . . 10.2 Files . . . . . . . . . . . . . . . . . . . . . . . . . 10.3 Piles . . . . . . . . . . . . . . . . . . . . . . . . . 10.4 Evaluation des expressions arithm etiques pr ex ees 10.5 Op erations courantes sur les listes . . . . . . . . . 11 Arbres 11.1 Files de priorit e . . . . . . 11.2 Borne inf erieure sur le tri . 11.3 Impl ementation dun arbre 11.4 Arbres de recherche . . . . 11.5 Arbres e quilibr es . . . . .

. . . . .

TABLE DES MATIERES

A D emarrer avec Unix A.1 Ce que doit savoir lutilisateur . . . . . . . A.1.1 Pas de panique ! . . . . . . . . . . A.1.2 D emarrage dune session . . . . . . A.1.3 Syst` eme de chiers . . . . . . . . . A.1.4 Comment obtenir de laide . . . . . A.1.5 Raccourcis pour les noms de chiers A.1.6 Variables . . . . . . . . . . . . . . A.1.7 Le chemin dacc` es aux commandes A.2 Le r eseau de lX . . . . . . . . . . . . . . . A.3 Un peu de s ecurit e . . . . . . . . . . . . . A.3.1 Mots de passe . . . . . . . . . . . . A.3.2 Acc` es a ` distance . . . . . . . . . . B Utilisation avanc ee du SHELL B.1 Compl ements . . . . . . . . . B.1.1 Quotation . . . . . . . B.1.2 Redirections et ltres . B.1.3 Processus . . . . . . . B.2 Programmation . . . . . . . . B.2.1 Structures de contr ole B.2.2 Code de retour . . . . B.2.3 Variables . . . . . . . B.2.4 Commandes internes . B.2.5 Fichier de d emarrage . B.3 Bibliographie Unix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 111 111 111 111 111 114 114 114 115 115 116 116 117 119 119 119 120 121 122 122 123 123 123 123 124 125 125 125 126 126 127 127 127 128 128 128 129 129 129 132 136 143

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C Syntaxe BNF de Java C.1 Contantes litt erales . . . . . . . . . . C.2 Types, valeurs, et variables . . . . . . C.3 Noms . . . . . . . . . . . . . . . . . C.4 Packages . . . . . . . . . . . . . . . C.5 Classes . . . . . . . . . . . . . . . . C.5.1 D eclaration de classe . . . . . C.5.2 D eclarations de champs . . . C.5.3 D eclarations de m ethodes . . C.5.4 Initialieurs statiques . . . . . C.5.5 D eclarations de constructeurs C.6 Interfaces . . . . . . . . . . . . . . . C.7 Tableaux . . . . . . . . . . . . . . . . C.8 Blocs et instructions . . . . . . . . . . C.9 Expressions . . . . . . . . . . . . . . Bibliographie Table des gures

TABLE DES MATIERES

Introduction
Ce polycopi e est utilis e pour deux enseignements qui ont des buts diff erents mais compl ementaires. Le premier, introduction a ` des e l` eves de premi` ere ann ee ayant ` linformatique sadresse a peu ou pas de connaissances en informatique. Une partie de ce cours consiste en une introduction g en erale a ` linformatique, aux logiciels, mat eriels, environnements informatiques et a ` la science sous-jacente. Une autre partie consiste a `e tablir les bases de la programmation et de lalgorithmique, en e tudiant un langage. On introduit des structures de donn ees simples : scalaires, cha nes de caract` eres, tableaux, et des structures de contr oles e l ementaires comme lit eration, la r ecursivit e. Nous avons choisi Java pour cette introduction a ` la programmation car cest un langage typ e assez r epandu qui permet de sinitier aux diverses constructions pr esentes dans la plupart des langages de programmation modernes. Le second, Les bases de la programmation et de lalgorithmique sadresse a ` des e l` eves de premi` ere ann ee ayant d ej` a des connaissances en informatique. Une partie du programme reprend les points pr ec edents, ensuite la partie programmation et algorithmique est compl et ee par l etude de structures de donn ees plus complexes : listes et arbres. ` ces cours sont coupl A es des s eances de travaux dirig es et pratiques qui sont beaucoup plus quun compl ement au cours, puisque cest en e crivant des programmes que lon apprend linformatique.

Remerciements
Nous remercions Serge Abiteboul, Franc ois Anceau, Jean Berstel, Thierry Besanc on, Jean Betr ema, Franc ois Bourdoncle, Philippe Chassignet, Georges Gonthier, Florent Guillaume, Martin Jourdan, Franc ois Morain, Dominique Perrin, Jean-Eric Pin, Nicolas Pioch, Bruno Salvy, Michel WeinfeldR, Paul Zimmermann pour avoir relu avec attention ce cours, Michel Mauny et Didier R emy pour leurs macros TEX, Ravi Sethi pour nous avoir donn e les sources pic des dessins de ses livres [3, 48], Martin Jourdan pour avoir fourni ces sources, Damien Doligez pour ses talents de metteur au point, pour les dessins, les scripts en Perl et sa grande connaissance du Macintosh, Xavier Leroy pour ses magniques shell-scripts, Bruno Salvy pour sa grande connaissance de Maple, Paul Zimmermann pour sa rigueur, Philippe Chassignet pour son expertise en graphique Macintosh . . . et tous ceux que nous avons oubli es involontairement. Nous devons sp ecialement mentionner Damien Doligez et Xavier Leroy, auteurs des annexes sur Unix. Bruno Blanchet, Franc ois Bourdoncle, Philippe Chassignet, et Georges Gonthier ont e galement contribu ea ` ladaptation du polycopi e au langage Java. Nous remercions enn Dominique Rossin pour le dessin de couverture, Philippe Chassignet et Pierrick Gaudry pour leur relecture soign ee. 7

TABLE DES MATIERES

Le polycopi e ae t e traduit en html a ` laide du traducteur Hevea, de Luc Maranget. Le polycopi e est consultable a ` ladresse :
http ://www.enseignement.polytechnique.fr/informatique/

Les erreurs seront corrig ees d` es quelles nous seront signal ees et les mises a ` jour seront effectu ees sur la version html.

Polycopi e, version 1.0

Chapitre 1

Les premiers pas en Java

Dans ce chapitre on donne quelques e l ements simples de la programmation avec le langage Java. Toutefois les notions de types, variables, affectations, fonctions se retrouvent dans tous les langages de programmation.

1.1

Afcher du texte

Commenc ons par un exemple simple de programme. Cest un classique, il sagit simplement dafcher Bonjour ! a ` l ecran. // Voici mon premier programme class Premier{ public static void main (String args[]){ System.out.println("Bonjour!"); } } Pour ex ecuter ce programme il faut commencer par l editer, pour cela on utilise un e diteur de texte (par exemple emacs) pour cr eer un chier qui a un nom se terminant par .java par exemple Premier.java . Ce chier doit contenir le texte du programme. Apr` es avoir tap e le texte, on le compile par la commande unix% javac Premier.java Ceci a pour effet de faire construire par le compilateur un chier Premier.class . Enn, le programme java permet dex ecuter le chier Premier.class . Voil` a ce que cela donne : unix% java Premier On voit safcher : Bonjour! On a choisi le m eme nom ici pour le nom du chier et pour le nom de la classe d ecrite par le chier, ce nest pas syst ematiquement obligatoire, mais vivement conseill e. Analysons le texte de ce premier programme, il contient dabord un commentaire entre les deux symboles /* et */ . On peut aussi mettre des commentaires de n de ligne qui commencent apr` es un symbole // et se terminent a ` la n de la ligne ; ces divers commentaires 9

CHAPITRE 1. LES PREMIERS PAS EN JAVA

ne sont utiles qu` a des lecteurs (humains) du texte du programme, ils nauront aucun effet sur la compilation ou lex ecution. Dans ce programme, il y a une seule classe Premier , et une seule fonction (on dit aussi m ethode lorsquil est question dun langage avec des objets comme Java) dans cette classe ; cette fonction a pour nom main , elle afche la cha ne de caract` eres Bonjour ! qui est donn ee sous forme dun param` etre litt eral a ` la fonction println . Cette derni` ere fonction est attach ee a ` lobjet out de la classe System de la biblioth` eque (do` u la fac on de linvoquer par System.out.println ). Dans un premier temps on peut consid erer quune classe sert a ` regrouper un certains nombres de fonctions. Cette fac on de proc eder donne une gestion modulaire des programmes que lon e crit. Dans notre cas, la classe ne contient quune seule fonction qui a pour nom main, toutes les classes que lon va construire contiendront une fonction ayant ce nom. Cest en effet la fonction qui est ex ecut ee lorsque lon effectue la commande java Nom_de_Classe . Les accolades et servent a ` constituer un bloc dinstructions ; elles doivent englober les instructions dune fonction, de m eme quune paire daccolades doit englober lensemble des fonctions dune classe. Noter quen Java les instructions se terminent toutes par un ; (point-virgule). Ainsi, dans la suite le symbole I signiera soit une instruction (qui se termine donc par ;) soit une suite dinstructions (chacune nissant par ;) le tout entre accolades.

1.2

Faire des calculs simples

On peut se servir de Java pour r ealiser les op erations dune calculette e l ementaire : on affecte la valeur dune expression a ` une variable et on demande ensuite lafchage de la valeur de la variable en question. Bien entendu, un langage de programmation nest pas vraiment fait pour cela, toutefois cela nous donne quelques exemples de programmes simples ; nous passerons plus tard a ` des programmes plus complexes. /* Voici mon deuxieme programme */ public class PremierCalcul { public static void main (String args[]){ int a; a = 10 + 5 * 3; System.out.println(a); a = 287 % 7; System.out.println(a); } } Dans ce programme on voit appara tre une variable dont le nom est a qui est d eclar ee au d ebut. Comme les valeurs quelle prend sont des entiers elle est dite de type entier, le mot int avant son nom indique ce type. Par la suite elle est affect ee deux fois dune valeur qui est ensuite afch ee. Les r esultats afch es seront 25 et 0. En effet dans la premi` ere formule la r` egle de priorit e des op erations est appliqu ee et la priorit e de * e tant plus grande que celle de +, cest cette op eration qui est effectu ee en premier. Dans la seconde op eration le symbole % dans a % qui est le reste de la division de par . b d esigne lop eration

1.3. TYPES PRIMITIFS

1.3

Types primitifs

Un type en programmation pr ecise lensemble des valeurs que peut prendre une variable ; les op erations que lon peut effectuer sur une variable d ependent de son type. Le type des variables que lon utilise dans un programme doivent tous e tre d eclar es. Parmi les types possibles, les plus simples sont les types primitifs. Il y a peu de types primitifs : les entiers, les r eels, les caract` eres et les bool eens. Les principaux types entiers sont int et long, le premier utilise 32 bits pour repr esenter un nombre ; sachant que le premier bit est r eserv e au signe cela donne un maximum de pour la valeur dun entier d eclar e en int, si un nombre d epasse cette valeur le r esulat obtenu nest pas utilisable. Le type long permet davoir des mots de 64 bits et on peut donc travailler sur des entiers plus grands. Il y a aussi les types byte et short qui permette dutiliser des mots de 8 et 16 bits. Les op erations sur les int sont toutes les op erations arithm etiques classiques : addition, soustraction, multiplication, divison, reste, et les op erations de comparaison : e gal, diff erent de, plus petit, plus grand. Les types r eels (en fait nombre d ecimaux) sont float et double, le premier se contente dune pr ecision dite simple, le second donne la possibilit e dune plus grande pr ecision, on dit que lon a une double pr ecision. Les caract` eres sont d eclar es par le type char ils correspondent au standard Unicode, ils sont cod es sur 16 bits et permettent datteindre toutes les langues de la plan` ete (les caract` eres habituels des claviers des langues europ eennes se codent uniquement sur 8 bits). On peut faire des comparaisons sur les caract` eres pour d eterminer lequel vient avant lautre dans lordre alphab etique. Le type des bool eens est boolean et les deux valeurs possibles sont true et false. Les op erations sont et, ou, et non ; elles se notent respectivement &&, ||, !. Si a et b sont deux bool eens, le r esultat de a && b est true si et seulement si a et b sont tous deux e gaux a ` true. Celui de a || b est true si et seulement si lun de a et b est e gal a ` true. Enn !a est true quand a est false et r eciproquement. Les bool eens sont utilis es dans les conditions que lon verra au chapitre suivant. La d eclaration du type des variables est obligatoire en Java, elle peut se faire a ` lint erieur dune fonction et pas n ecessairement au d ebut. Une d eclaration se pr esente sous la forme dun nom de type suivi soit dun nom de variable soit dune suite de noms de variables s epar es par des virgules. En voici quelques exemples :

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

1.4

Affectation

On a vu quune variable a un nom et quelle est d eclar ee dun certain type. Lop eration la plus courante sur les variables est laffectation dune valeur elle s ecrit : x = E;

o` u E est une expression qui peut contenir des constantes et des variables. Lors dune affectation, lexpression E est e valu ee et le r esultat de son e valuation est affect ea ` la variable x. Lorsque lexpression E contient des variables leur e valuation est e gale a ` la derni` ere valeur qui leur a e t e affect ee. Un exemple daffectation est le suivant : x = x + a;

12
double float long int short byte

CHAPITRE 1. LES PREMIERS PAS EN JAVA

char

cela consiste a ` augmenter la valeur de x de la quantit e a. Une variable i de type entier peut e tre incr ement ee par lop eration i++, ceci a exactement le m eme effet que i = i + 1. On peut utiliser au sein dune expression lop erateur unaire ++, on fait alors a ` la fois une e valuation de la valeur et une (post ou pr e)-incr ementation de la variable. Ceci nest pas recommand e sauf dans des cas tr` es particuliers de parcours de tableaux. La d ecr ementation se fait par i--, qui est e quivalente a ` i = i - 1. Pour une affectation x = E; le type de lexpression E et celui de la variable x doivent e tre les m emes. Dans un tr` es petit nombre de cas cette exigence nest pas appliqu ee, il sagit alors des conversions implicites de types. Les conversions implicites suivent la gure ci-dessus. Pour toute op eration, on convertit toujours au plus petit commun majorant des types des op erandes. Des conversions explicites sont aussi possibles, et recommand ees dans le doute. On peut les faire par lop eration dite de coercion (cast) suivante x = (nom-type) E; Lexpression E est alors convertie dans le type indiqu e entre parenth` eses devant lexpression. Lop erateur = daffectation est un op erateur comme les autres dans les expressions. Il subit donc les m emes lois de conversion. Toutefois, il se distingue des autres op erations par le type du r esultat. Pour un op erateur ordinaire, le type du r esultat est le type commun obtenu par conversion des deux op erandes. Pour une affectation, le type du r esultat est le type de lexpression a ` gauche de laffectation. Il faut donc faire une conversion explicite sur lexpression de droite pour que le r esultat soit coh erent avec le type de lexpression de gauche.

1.5

Op erations

La plupart des op erations arithm etiques courantes sont disponibles en Java, ainsi que les op erations sur les bool eens (voir chapitre suivant). Ces op erations ont un ordre de priorit e correspondant aux conventions usuelles. Les principales op erations sont +,-,*,/, % pour laddition, soustraction, multiplication, division et le reste de la division (modulo). Il y a des r` egles de priorit e, ainsi lop eration de multiplication a une plus grande priorit e que laddition, cela signie que les multiplications sont faites avant les additions. La pr esence de parenth` eses permet de mieux contr oler le r esultat. Par exemple 3 + 5 * 6 est e valu ea ` 33 ; par contre (3 + 5) * 6 est e valu e 48.

1.6. FONCTIONS

Une expression a toujours un type et le r esultat de son e valuation est une valeur ayant ce type. L evaluation de 2/0 soul` eve lexception (voir plus loin) ArithmeticException. Remarque Le symbole + d esigne aussi la concat enation (mise bout a ` bout) de deux cha nes de caract` eres, le contexte permet de d eterminer sil sagit de laddition de deux nombres ou de la concat enation. On dit quil y a surcharge de lop eration +. Par exemple lorsquon e crit linstruction : System.out.println("Vous nous devez " + a + " francs " ); On demande limpression de la cha ne de caract` eres Vous nous devez a ` laquelle est concat en ee la cha ne repr esentant le nombre a et la cha ne " francs ". Remarquer que dans cette e criture le nombre a est converti en une cha ne de caract` eres de fac on implicite.

1.6

Fonctions

Une fonction est une partie de programme situ ee a ` lint erieur dune classe dont la donn ee est constitu ee de certains param` etres et qui fournit un r esultat. Dans certains cas la fonction agit uniquement par effet de bord, par exemple lorsquelle modie certaines variables globales ou lorsquelle ne fait quafcher des valeurs. On indique alors que son r esultat est de type void, ainsi la fonction main est toujours de type void. Il y a aussi des cas o` u il ny a pas de param` etres lorsque la fonction effectue toujours les m emes op erations sur les m emes valeurs. Lent ete dune fonction d ecrit le type du r esultat dabord puis les types des param` etres qui gurent entre paranth` eses. Les programmes que lon a vu ci-dessus contiennent une seule fonction appel ee main. Lorsquon effectue la commande java Nom-classe , cest la fonction main se trouvant dans cette classe qui est ex ecut ee en premier. Une fonction peut e tre appel ee par une autre fonction, il faut alors donner des valeurs aux param` etres dappel. Un exemple simple de fonction est le calcul de la circonf erence dun 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.println("Circonf erence: " + c);} } Ce programme contient deux fonctions dans une m eme classe, la premi` ere fonction a un param` etre r et utilise la constante PI qui se trouve dans la classe Math, cette constante est de type double il faut donc la convertir au type float pour affecter sa valeur a ` un nombre de ce type. Le r esultat est fournit, on dit plut ot retourn ea ` lappelant par return. Lappelant est ici la fonction main qui apr` es avoir effectu e lappel, afche le r esultat .

CHAPITRE 1. LES PREMIERS PAS EN JAVA

Chapitre 2

Suite dinstructions
Dans ce chapitre on sint eresse aux instructions conditionnelles, qui permettent deffectuer une op eration dans le cas o` u une certaine condition est satisfaite et aux it erations qui donnent la possibilit e de r ep eter plusieurs fois la m eme instruction (pour des valeurs diff erentes des variables !).

2.1

Expressions bool eennes

Le point commun aux diverses instructions que lon va d ecrire est quelles utilisent des expressions dont l evaluation donne lune des deux valeurs true ou false. On dit que ce sont des expressions bool eennes ou parfois des expressions logiques.

2.1.1

Op erateurs de comparaisons
<= >=

Les op erateurs bool eens les plus simples sont == != < >

Le r esultat dune comparaison sur des variables de type primitif : a == b est e gal a ` true si l evaluation de la variable a et de la variable b donnent le m eme r esultat, il est e gal a ` false sinon. Remarque Attention a ` ne pas e crire a = 0 qui est une affectation et pas une comparaison. Lop erateur != est loppos e de ==, ainsi a != b prend la valeur true si l evaluation de a et de b donne des valeurs diff erentes. Les op erateurs de comparaison <, >, <=, >= ont des signications e videntes lorsquil sagit de compararer des nombres. Noter quils peuvent aussi servir a ` comparer des caract` eres ; pour les caract` eres latins courants cest lordre alphab etique qui est exprim e.

2.1.2

Connecteurs

On peut construire des expressions bool eennes comportant plusieurs comparateurs en utilisant les connecteurs &&, qui signie et, || qui signie ou et ! qui signie non. Ainsi C1 && C2 est e valu ea ` true si et seulement si les deux expressions C1 et C2 le sont. De m eme C1 || C2 est e valu ea ` true si lune deux expressions C1 ou C2 lest. Par exemple !( ((a<c) && (c<b) && (b<d)) || ((c<a) && (a<d) && (d<b)) ) 15

16 est une fac on de tester que les deux intervalles dans lautre.

CHAPITRE 2. SUITE DINSTRUCTIONS

" $#%%& et " '(#)&

sont disjoints ou contenus lun

Remarque En Java l evaluation de lexpression C1 && C2 seffectue dans lordre C1 puis C2 si n ecessaire ; ainsi si C1 est e valu ee a ` false alors C2 nest pas e valu ee. Cest aussi le cas pour C1 || C2 qui est e valu ee a ` true si cest le cas pour C1 et ceci sans que C2 ne soit e valu ee. Par exemple l evaluation de lexpression (3 > 4) && (2/0 > 0) && (3 > 0) 4) donne pour r esultat false alors que (2/0 > donne lieu a ` une erreur (exception).

2.2

Instructions conditionnelles

Il sagit dinstructions permettant de neffectuer une op eration que si une certaine condition est satisfaite.

2.2.1

If-else

La plus simple de ces instructions est celle de la forme : if(C) I1 else I2 Dans cette e criture C est une expression bool eenne (attention a ` ne pas oublier les parenth` eses autour) ; I1 et I2 sont form ees ou bien une seule instruction ou bien une suite dinstructions a ` . On rappelle que chaque instruction de Java se termine lint erieur dune paire daccolades par ; (symbole qui fait donc partie de linstruction).

La partie else I2 est facultative, elle est omise si la suite I2 est vide cest a ` dire sil ny a aucune instruction a ` ex ecuter dans le cas o` u C est e valu ee a ` false. On peut avoir plusieurs branches s epar ees par des else if comme par exemple dans : if (a == 0 ) x = 1; else if (a < 0) x = 2; else if (a > -5) x = 3; else x = 4; qui donne 4 valeurs possibles pour x suivant les valeurs de a.

2.2.2

Forme compacte

Il existe une forme compacte de linstruction conditionnelle utilis ee comme un op erateur ternaire (` a trois op erandes) dont le premier est un bool een et les deux autres sont de type primitif. Cet op erateur s ecrit C ? E1 : E2. Elle est utilis ee quand un if else para t lourd, par exemple pour le calcul dune valeur absolue : x = (a > b)? a - b : b - a;

2.3

It erations boucles pour

Une it eration permet de r ep eter plusieurs fois la m eme suite dinstructions. Elle est utilis ee pour e valuer une somme, une suite r ecurrente, le calcul dun plus grand commun diviseur par exemple. Elle sert aussi pour effectuer des traitements plus informatiques comme la lecture dun chier. On a lhabitude de distinguer les boucles pour des boucles tant-que. Les premi` eres

2.4. ITERATIONS TANT QUE

sont utilise es lors quon conna t, lors de l ecriture du programme, le nombre de fois o` u les op erations doivent e tre it er ees, les secondes servent a ` exprimer des tests darr et dont le r esultat nest pas pr evisible a ` lavance. Par exemple le calcul dune somme de valeurs pour variant de 1 a ` est de la cat egorie boucle-pour celui du calcul dun plus grand commun diviseur par lalgorithme dEuclide rel` eve dune boucle tant-que.

Lit eration de type boucle-pour en Java a la m eme forme quen langage C, forme qui d eroute ceux qui la d ecouvrent pour la premi` ere fois. Elle sexprime par : for (Init; C ; Inc) I Dans cette e criture Init est une initialisation (pouvant comporter une d eclaration), Inc est une incr ementation, et C un test darr et, ce sont des expressions qui ne se terminent pas par un point virgule. Quant a ` I, cest le corps de la boucle constitu e dune seule instruction ou dune suite dinstructions entre accolades. Init est ex ecut ee en premier, ensuite la condition C est e valu ee si sa valeur est true alors la suite dinstructions I est ex ecut ee suivie de linstruction dincr ementation Inc et un nouveau tour de boucle reprend avec l evaluation de C. Noter que Init peut e tre compos ee dune seule expression ou bien de plusieurs, s epar ees par des , (virgules). Lexemple le plus courant est celui o` u on ex ecute une suite dop erations pour i variant de 1 a ` n, comme dans :
int i; for(i = 1; i <= n; ++i) System.out.println(i);

Une forme encore plus courante est celle o` u on d eclare i dans la boucle :
for(int i = 1; i <= n; ++i) System.out.println(i);

On na pas acc` es a ` la variable i en dehors du corps de la boucle. Un autre exemple est le calcul de la somme

32 465 0

qui se fait par float s = 0.; for(int i = 1; i <= n; ++i) s = s + 1/i; Noter que les instructions Init ou Inc de la forme g en erale (ou m eme les deux) peuvent e tre vides. Il ny a alors pas dinitialisation ou pas dincr ementation ; linitialisation peut, dans ce cas, gurer avant le for et lincr ementation a ` lint erieur de I.

2.4

It erations tant que

while (C) I

Une telle instruction a la forme suivante :

o` u C est une condition et I une instruction ou un bloc dinstructions. Lit eration e value C et ex ecute I si le r esultat est true, cette suite est r ep et ee tant que l evaluation de C donne la valeur true. Un exemple classique de lutilisation de while est le calcul du pgcd de deux nombres par lalgorithme dEuclide. Cet algorithme consiste a ` remplacer le calcul de par celui de o` u est le reste de la division de par et ceci tant que .

798@'ABFG#IHPD

798@'ACBC#%ED HRSU Q T

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

CHAPITRE 2. SUITE DINSTRUCTIONS

2.5

Instructions de rupture de contr ole

Il y a trois telles instructions qui sont return, break et continue . Linstruction return doit e tre utilis ee dans toutes les fonctions qui calculent un r esultat. Leffet de cette instruction est de fournir (on dit souvent retourner) une valeur a ` lappelant, on la utilis ee dans la fonction de calcul de circonf erence du chapitre premier. Elle s ecrit : return Exp; o` u Exp est une expression qui e valu ee avant la terminaison de lex ecution de la fonction et fournie a ` la pro edure qui a fait appel a ` cette fonction. Les deux autres instructions de rupture sont beaucoup moins utilis ees et peuvent e tre omises en premi` ere lecture. Linstruction break permet dinterrompre une suite dinstructions dans une boucle pour passer a ` linstruction qui suit la boucle dans le texte du programme. Si plusieurs boucles sont imbriqu ees et que lon souhaite sortir de diverses fac ons de cette imbrication, il faut alors utiliser des e tiquettes effectuer des op erations de break e tiquet ees. Ainsi un break etiq fait sortir de la boucle pr ec ed ee de l etiquette etiq. Linstruction continue a un effet similaire a ` celui de break , mais redonne le contr ole a ` lit eration suivante de la boucle au lieu den sortir. On peut aussi utiliser continue suivi dune e tiquette de boucle. Il nest en g en eral pas recommand e dutiliser les instructions avec e tiquettes, qui dans beaucoup de cas nuisent a ` la lisibilit e des programmes. Pourtant dans certaines situations particuli` eres elles se r ev` elent utiles.

2.5.1

Aiguillage

Quand diverses instructions sont a ` r ealiser suivant les valeurs que prend une variable, plusieurs if imbriqu es deviennent lourds a ` mettre en oeuvre, on peut les remplacer avantageusement par un aiguillage switch. Un tel aiguillage a la forme suivante dans laquelle x est une variable et a,b,c sont des constantes repr esentant des valeurs que peut prendre cette variable. Lors de lex ecution les valeurs apr` es chaque case sont test ees lune apr` es lautre jusqu` a obtenir celle prise par x ou arriver a ` default , ensuite toutes les instructions sont ex ecut ees en s equence jusqu` a la n. Par exemple dans linstruction : switch (x) { case a : I1 case b : I2 case c : I3 default : I4 } Si la variable x est e valu ee a ` b alors toutes les suites dinstructions I2, I3, I4 seront ex ecut ees, a ` moins que lune dentre elles ne contienne un break qui interrompt cette suite. Si la variable est e valu ee a ` une valeur diff erente de a,b,c cest la suite I4 qui est ex ecut ee. En effet pour sortir de linstruction avant la n, il faut passer par une instruction break. Sinon, le reste de linstruction est ex ecut e en s equence. Ceci peut e tre particuli` erement dangereux. Par exemple, le programme suivant switch (c) { case \t: case :

2.5. INSTRUCTIONS DE RUPTURE DE CONTROLE

++ 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; }

permet de factoriser le traitement de quelques cas. Il faudra bien faire attention a ` ne pas oublier le break a ` la n de chaque cas, et a ` ce que break ne soit pas intercept e par une autre instruction.

CHAPITRE 2. SUITE DINSTRUCTIONS

Chapitre 3

Tableaux et cha nes de caract` eres

Jusquici la plupart des constructions pr esent ees pour Java sont les m emes que celles du langage C. En effet les notions de variables, types, affectations, appel de fonctions, conditionnelles et boucles gurent dans tous les langages de programmation, et la m eme notation est utilis ee en Java et en C. La possibilit e de manipuler des tableaux se retrouve aussi dans tous les langages de programmation ; toutefois Java, qui est un langage avec des objets, manipule les tableaux dune fac on particuli` ere que lon va d ecrire ici.

3.1

D eclaration et construction de tableaux

Lutilisation dun tableau permet davoir a ` sa disposition un tr` es grand nombre de variables en utilisant un seul nom et donc en effectuant une seule d eclaration. Le principe est que si on d eclare un tableau de nom tab et de taille n contenant des valeurs de type typ alors on a sa disposition les variables tab[0],tab[1], ..., tab[n-1] qui se comportent comme des variables ordinaires de type typ. En Java on s epare la d eclaration dune variable de type tableau de la construction effective dun tableau. La d eclaration dune variable de type tableau de nom tab dont les e l ements sont de type typ, seffectue par : typ[] tab; ou de mani` ere e quivalente par typ tab[]; Nous pr ef ererons la premi` ere fac on de faire car elle respecte la convention suivant laquelle dans une d eclaration, le type dune variable gure compl` etement avant le nom de celle-ci. La seconde correspond a ` ce qui se fait en langage C. Lorsque lon a d eclar e un tableau en Java on ne peut pas encore lutiliser compl` etement, il est en effet interdit par exemple daffecter une valeur aux variables tab[i]. Il faut commencer par construire le tableau, pour mieux comprendre ce qui se passe on peut consid erer que construire signie r eserver de la place en m emoire. Lop eration de construction seffectue en utilisant un new, pour un tableau cela donne : tab = new typ[taille]; dans cette instruction taille est une constante enti` ere ou une variable de type entier dont l evaluation doit pouvoir e tre effectu ee a ` lex ecution. Une fois quun tableau est cr ee avec une certaine taille, celle-ci ne peut plus e tre modi ee. On peut aussi regrouper la d eclaration et la construction en une seule ligne par : typ[] tab = new typ[taille]; 21

CHAPITRE 3. TABLEAUX ET CHAINES DE CARACTERES

Pour des tableaux de petite taille on peut en m eme temps construire et initialiser un tableau et initialiser les valeurs contenues dans le tableau. Lexemple suivant regroupe les 3 op erations de d eclaration, construction et initialisation de valeurs en utilisant une affectation suivie de , :

int[] tab = {1,2,4,8,16,32,64,128,256,512,1024};

3.2

Utilisation de tableaux

Si tab est un tableau dont les e l ements sont de type typ, on peut alors consid erer tab[i] comme une variable et effectuer sur celle-ci toutes les op erations admissibles concernant le type typ, bien entendu lindice i doit e tre inf erieur a ` la taille du tableau donn ee lors de sa construction. Linterpr eteur Java v erie cette condition et une exception est lev ee si elle nest pas satisfaite. La taille dun tableau tab peut sobtenir grace au champ length associ ea ` cette variable. Parmi les op erations simples sur les tableaux, il y a la recherche du plus petit ou du plus grand e l ement qui se r ealise par la fonction suivante : 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; } Une autre fac on dutiliser un tableau consiste a ` effectuer une affectation, par exemple : int[] tabnouv = tab; Cette affectation a pour effet de faire que les variables tabnouv et tab d esignent le m eme tableau, en programmation on dit quelles font r ef erence au m eme tableau. Il ny a pas recopie de toutes les valeurs contenues dans le tableau tab pour former un nouveau tableau mais simplement une indication de r ef erence. Ainsi si lon modie la valeur de tab[i], celle de tabnouv[i] le sera aussi. Si on souhaite recopier un tableau dans un autre il faut e crire une fonction : 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; } Noter aussi que lop eration de comparaison de deux tableaux x == y est e valu ee a ` true dans le cas o` u x et y r ef erencent le m eme tableau (par exemple si on a effctu e laffectation y = x). Si on souhaite v erier l egalit e des contenus, il faut une e crire une fonction particuli` ere.

3.3

` plusieurs dimensions, matrices Tableaux a

Un tableau a ` plusieurs dimensions est consid er e en Java comme un tableau de tableaux. Par exemple, les matrices qui sont des tableaux a ` deux dimensions sont d eclar ees par : typ[][] tab; Il faut aussi le construire on peut le faire par tab = new typ[N][N];

3.4. CHAINES DE CARACTERES

Mais on peut aussi, comme pour les tableaux a ` une dimension, faire une affectation de valeurs en une seule fois : int[][] tab = {{1,2,3},{4,5,6},{7,8,9}};

3.4

Cha nes de caract` eres

Les cha nes de caract` eres se manipulent de fac on particuli` ere en Java puisquelles constituent une classe. Comme les classes ne seront consid er ees quau chapitre suivant, ce quon va vous dire ici pourra para tre compliqu e, vous pouvez toutefois noter lexistence des fonctions, et les utiliser sans trop comprendre. Une cha ne de caract` eres est une suite de symboles que lon peut taper sur un clavier ou lire sur un e cran. La d eclaration dune variable susceptible de contenir une cha ne de caract` eres se fait par String u; Un point important est que lon ne peut pas modier une cha ne de caract` eres, on dit quelle est non mutable. On peut par contre lafcher, la recopier, acc eder a ` la valeur dun des caract` eres et effectuer un certain nombre dop erations comme la concat enation, lobtention dun facteur, on peut aussi v erier l egalit e de deux cha nes de caract` eres. Voici quelques exemples : String v = new String(u); recopie la cha ne u dans la la cha ne v. int l = u.length(); donne la longueur de la cha ne u, Noter que length est une fonction sur les cha nes de caract` eres, et que par contre cest une valeur associ ee a ` un tableau ; ceci explique la diff erence d ecriture : les parenth` eses pour la fonction sur les cha nes de caract` eres sont absentes dans le cas des tableaux. char x = u.charAt(i); donne a ` x la valeur du -` eme carat` ere de la cha ne u, noter que le premier carat` re sobtient par u.charAt(0) . u.compareTo(v); a pour r esultat un nombre entier n egatif si u pr ec` ede v dans lordre lexicographique (celui du dictionnaire), 0 si les cha nes u et v sont e gales et un nombre positif si v pr ec` ede u. w = u.concat(v); construit une nouvelle cha ne obtenue par concat enation de v suivie de u. Noter que v.concat(u) est une cha ne diff erente de la pr ec edente.

3.5

Arguments de main

La proc edure main qui gure dans tout programme que lon souhaite ex ecuter peut avoir un param` etre de type tableau de cha nes de caract` eres. On d eclare alors la proc edure par public static void main (String[] args) Pour comprendre lint er et de tels param` etres, supposons que la proc edure main se trouve a ` lint erieur dun programme qui commence par Class Classex . On peut alors utiliser les valeurs et variables args.length, args[0], args[1], ... a ` lint erieur de la proc edure main Celles-ci correspondent aux cha nes de caract` eres qui suivent java Classex lorsque lutilisateur demande dex ecuter son programme. Par exemple si on a e crit une proc edure main :

CHAPITRE 3. TABLEAUX ET CHAINES DE CARACTERES

void main (String[] args){ for (int i = args.length -1; i > = 0 ; i--) System.out.print(args[i] + " "); System.out.println(); } et quune fois celle-ci compil ee on demande lex ecution par java Classex marquise d\amour me faites mourrir on obtient comme r esultat mourrir faites me damour marquise Noter que lon peut transformer une cha ne de caract` eres u compos ee de chiffres d ecimaux en un entier par la fonction Integer.parseInt() comme dans le programme suivant : class Additionner { public static void main (String args[]) { if (args.length != 2) System.out.println("mauvais nombre darguments"); else { int s= Integer.parseInt(args[0]) +Integer.parseInt(args[1]); System.out.println (s);} } } On peut alors demander java Additionner 1047 953 linterpr eteur r epond : 2000

Chapitre 4

Composants dune classe

Ce chapitre est consacr ea ` lorganisation g en erale dun programme en Java, car jusquici nous nous sommes plut ot int eress es aux diff erentes instructions de base. On peut consid erer dans un premier temps les classes comme un moyen de regrouper plusieurs fonctions qui ont trait a ` un sujet commun. Par exemple on peut constituer une classe qui contient des fonctions sur les points et droites du plan, une autre pour manipuler des segments, une troisi` eme pour les polygones etc. Cela donne une structure modulaire, plus agr eable a ` lire, pour les programmes. En fait une classe cest bien plus quun regroupement de fonctions. En effet, on peut y placer des constantes utiles pour toutes les fonctions de la classe et qui ne seront pas modi ees par celles-ci, des variables partag ees par ces fonctions et auxquelles elles pourront affecter une nouvelle valeur. Mais ce nest pas tout, une classe permet aussi de d enir un type que des variables pourront prendre, ce type peut contenir des enregistrements compos es de champs (comme les records en Pascal, les structures en C, ou le type produit de Caml). Un point un peu d elicat est la construction dun objet de la classe qui se fait a ` laide de constructeurs.

4.1

Fonctions

Une fonction prend des valeurs en param` etres et donne en g en eral un r esultat. Elle se d eclare par : public static typeRes nomFonction(type1 nom1, type2 nom2, ... , typek nomk) Dans cette e criture typeRes est le type du r esultat, noter que celui-ci peut e tre void, dans ce cas la fonction ne rend pas de r esultat et op` ere par effet de bord, par exemple en afchant des valeurs ou en modiant des variables globales. Il est d econseill e d ecrire des fonctions qui proc` edent par effet de bord, sauf bien entendu pour les afchages. La signature dune fonction est constitu ee de la suite ordonn ee des types des param` etres. On fait appel a ` une fonction par nomFonction(var1, var2, ... , vark) En g en eral cet appel se situe dans une affectation, sauf si le type du r esultat est void. Les param` etres dappel dune fonction sont pass es par valeurs, cest a ` dire que leur valeurs sont recopi ees lors de lappel. Apr` es la n du travail de la fonction les nouvelles valeurs, qui peuvent avoir e t e attribu ees a ` ces variables, ne sont plus accessibles. Ainsi il nest pas possible d ecrire une fonction qui e change les valeurs de deux variables pass ees en param` etre, sauf a ` proc eder par des moyens d etourn es peu recommand es. 25

CHAPITRE 4. COMPOSANTS DUNE CLASSE

Noter que si un param` etre a le type tableau (ou un autre type de classe), alors la variable pass ee est une r ef erence sur ce tableau et la modication des valeurs dun e l ement du tableau aura un effet accessible a ` lext erieur de la fonction. Le r esultat du calcul de la fonction doit e tre indiqu e apr` es un return. Il est obligatoire de pr evoir une telle instruction dans toutes les branches dune fonction (sauf pour le type void bien entendu). Lex ecution dun return a pour effet dinterrompre le calcul de la fonction en rendant le r esultat a ` lappelant. En Java on peut d enir plusieurs fonctions qui ont le m eme nom a ` condition que leurs signatures soient diff erentes. On appelle surcharge cette possibilit e. Le compilateur doit e tre a ` m eme de d eterminer la fonction dont il est question a ` partir du type des param` etres dappel.

4.2

Constantes et variables globales

Une constante se d eclare par static final int promotion = 2000; elle ne pourra pas e tre modi ee par les fonctions de la classe. Les variables globales sont d eclar ees par static int nbeleves; On peut d eclarer des variables globales de nimporte quel type, toutefois cest en g en eral des entiers quon utilise pour compter.

4.3

Les classes pour d enir des enregistrements

Une structure, ou un type produit permet de travailler avec des variables qui poss` edent plusieurs champs. Ceci est l equivalent de lop eration math ematique du produit cart esien de deux ou plusieurs ensembles. Les d eclarations se font comme pour les variables globales sans indiquer static avant le type. Ainsi on peut d enir des points du plan par leurs coordonn ees : public class Point { float abs; float ord; } Par la suite pour acc eder a ` la valeur dun des champs on utilise le symbole . apr` es le nom de la variable. par exemple : x.abs = 1; x.ord = -1;

4.4

Constructeurs

Quand on fabrique une classe, il est indispensable de donner un moyen de construire les objets de cette classe. Ceci se fait par des fonctions dont le nom est le m eme que celui de la classe o` u elles sont d enies. Noter que la r` egle concernant les surcharges permet de d enir plusieurs constructeurs pour une m eme classe du moment que les types des param` etres dappels de ces g en erateurs sont diff erents. Par exemple :

4.5. LES METHODES STATIQUES ET LES AUTRES

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

4.5

Les m ethodes statiques et les autres

On nutilise pratiquement que des fonctions statiques dans le cadre de ce cours, la d eclaration de ces fonctions est pr ec ed ee du mot r eserv e static. Il y a une fac on non statique de d enir une fonction. Dans ce cas il faut faire appel a ` cette fonction en utilisant un objet de la classe, objet auquel la fonction pourra sappliquer, lappel se fait alors par NomObjet.NomFonction. Dans la description dune m ethode non statique on fait r ef erence a ` lobjet qui a servi a ` lappel par le nom this. Un exemple complet de classe est donn e ci-dessous avec les diff erentes possibilit es de fonctions : Exemple : les points du plan Un point est repr esent e par son abcisse et son ordonn ee Un constructeur fabrique lobjet point a ` partir de ses coordonn ees Une m ethode afche les coordonn ees dun point On a parfois besoin du point (origine) On veut construire le sym etrique dun point par rapport a ` Une m ethode v erie si trois points sont align es

class PointEntier{ int abs, ord; PointEntier(int a, int b){ abs = a; ord = b; } public void affiche() { System.out.println(" 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(PointEntier p, PointEntier q, PointEntier r){ int u = (p.abs - q.abs) * (p.ord - r.ord) - (p.abs - r.abs) * (p.ord - q.ord);

28 return (u == 0);} }

CHAPITRE 4. COMPOSANTS DUNE CLASSE

4.6

Utiliser plusieurs classes

Lorsque lon utilise la classe pr ec edente a ` lext erieur on doit faire pr ec eder les noms des fonctions du nom de la classe suivi dun point. class Exemple{ public static void main (String[] args){ PointEntier p = new PointEntier(3,5); PointEntier q = p.oppose(); PointEntier r = PointEntier.origine(); boolean res = PointEntier.alignes(p,q,r); p.affiche(); q.affiche(); r.affiche(); System.out.println(res); } }

Chapitre 5

Compl ements
5.1 Exceptions

Les exceptions sont des objets de la classe Exception . Il existe aussi une classe Error moins utilis ee pour les erreurs syst` eme. Toutes les deux sont des sous-classes de la classe Throwable , dont tous les objets peuvent e tre appliqu es a ` lop erateur throw, comme suit :
throw e ;

Ainsi on peut e crire en se servant de deux constructeurs de la classe Exception :

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

Heureusement, dans les classes des biblioth` eques standard, beaucoup dexceptions sont d ej` a pr e-d enies, par exemple IndexOutOfBoundsException. On r ecup` ere une exception par linstruction try . . .catch. Par exemple
try { // un programme compliqu e } catch ( IOException e) { // essayer de r eparer cette erreur dentr ee/sortie } catch ( Exception e) { // essayer de r eparer cette erreur plus g en erale }

Si on veut faire un traitement uniforme en n de linstruction try, que lon passe ou non par une exception, que le contr ole sorte ou non de linstruction par une rupture de s equence comme un return, break, etc, on e crit
try { // un programme compliqu e } catch ( IOException e) { // essayer de r eparer cette erreur dentr ee/sortie } catch ( Exception e) { //essayer de r eparer cette erreur plus g en erale } finally { // un peu de nettoyage }

CHAPITRE 5. COMPLEMENTS

Il y a deux types dexceptions. On doit d eclarer les exceptions v eri ees derri` ere le motcl e throws dans la signature des fonctions qui les l` event. Ce nest pas la peine pour les exceptions non v eri ees qui se reconnaissent en appartenant a ` une sous-classe de la classe RuntimeException. 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
5.2.1

Graphisme
l Fonctions e ementaires

Les fonctions sont inspir ees de la libraire QuickDraw du Macintosh, mais fonctionnent aussi sur les stations Unix. Sur Macintosh, une fen etre Drawing permet de g erer un e cran typiquement de points. Lorigine du syst` eme de coordonn ees est en haut et a ` gauche. Laxe des va classiquement de la gauche vers la droite, laxe des va plus curieusement du haut vers le bas (cest une vieille tradition de linformatique, dure a ` remettre en cause). En QuickDraw, et sont souvent appel es h (horizontal) et v (vertical). Il y a une notion de point courant et de crayon avec une taille et une couleur courantes. On peut d eplacer le crayon, en le levant ou en dessinant des vecteurs par les fonctions suivantes

T XW`Ybaced

f g

moveTo (x, y) D eplace le crayon aux coordonn ees absolues x, y. move (dx, dy) D eplace le crayon en relatif de dx, dy. lineTo (x, y) Trace une ligne depuis le point courant jusquau point de coordonn ees x, y. line (dx, dy) Trace le vecteur (dx, dy) depuis le point courant. penPat(pattern) Change la couleur du crayon : white, black, gray, dkGray (dark gray), ltGray (light gray). penSize(dx, dy) Change la taille du crayon. La taille par d efaut est (1, 1). Toutes les op erations de trac e peuvent se faire avec une certaine e paisseur du crayon. penMode(mode) Change le mode d ecriture : patCopy (mode par d efaut qui efface ce sur quoi on trace), patOr (mode Union, i.e. sans effacer ce sur quoi on trace), patXor (mode Xor, i.e. en inversant ce sur quoi on trace).

5.2.2

Rectangles

Certaines op erations sont possibles sur les rectangles. Un rectangle r a un type pr ed eni Rect. Ce type est une classe qui a le format suivant
public class Rect { short left, top, right, bottom; }

5.2. GRAPHISME

Fort heureusement, il ny a pas besoin de conna tre le format internes des rectangles, et on peut faire simplement les op erations graphiques suivantes sur les rectangles setRect(r, g, h, d, b) xe les coordonn ees (gauche, haut, droite, bas) du rectangle r. Cest e quivalent a ` faire les op erations r.left := g ;, r.top := h ;, r.right := d ;, r.bottom := b. unionRect(r1, r2, r) d enit le rectangle r comme lenveloppe englobante des rectangles r1 et r2. frameRect(r) dessine le cadre du rectangle r avec la largeur, la couleur et le mode du crayon courant. paintRect(r) remplit lint erieur du rectangle r avec la couleur courante. invertRect(r) inverse la couleur du rectangle r. eraseRect(r) efface le rectangle r. fillRect(r,pat) remplit lint erieur du rectangle r avec la couleur pat. drawChar(c), drawString(s) afche le caract` ere c ou la cha ne s au point courant dans la fen etre graphique. Ces fonctions diff` erent de write ou writeln qui e crivent dans la fen etre texte. frameOval(r) dessine le cadre de lellipse inscrite dans le rectangle r avec la largeur, la couleur et le mode du crayon courant. paintOval(r) remplit lellipse inscrite dans le rectangle r avec la couleur courante. invertOval(r) inverse lellipse inscrite dans r. eraseOval(r) efface lellipse inscrite dans r. fillOval(r,pat) remplit lint erieur lellipse inscrite dans r avec la couleur pat. frameArc(r,start,arc) dessine larc de lellipse inscrite dans le rectangle r d emarrant a ` langle start et sur la longueur d enie par langle arc. frameArc(r,start,arc) peint le camembert correspondant a ` larc pr ec edent . . .. Il y a aussi des fonctions pour les rectangles avec des coins arrondis. button est une fonction qui renvoie la valeur vraie si le bouton de la souris est enfonc e, faux sinon. getMouse(p) renvoie dans p le point de coordonn ees p.h p.v courantes du curseur. getPixel(p) donne la couleur du point p. R epond un bool een : false si blanc, true. si noir. hideCursor(), showCursor() cache ou remontre le curseur.

5.2.3

La classe Maclib

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) {...}

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

Et les fonctions correspondantes (voir page 31)

static void setRect(Rect r, int left, int top, int right, int bottom) static void unionRect(Rect src1, Rect src2, Rect dst) static static static static static static static static static static static static static static void void void void void void void void frameRect(Rect r) paintRect(Rect r) eraseRect(Rect r) invertRect(Rect r) frameOval(Rect r) paintOval(Rect r) eraseOval(Rect r) invertOval(Rect r)

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

Toutes ces d enitions sont aussi sur poly dans le chier

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

On veillera a ` avoir cette classe dans lensemble des classes chargeables (variable denvironnement CLASSPATH ).

5.2.4

Jeu de balle

Le programme suivant fait rebondir une balle dans un rectangle, premi` ere e tape vers un jeu de pong.
class Pong extends MacLib { static final int C = 5, // Le rayon de la balle X0 = 5, X1 = 250, Y0 = 5, Y1 = 180; static void getXY (Point p) { int N = 2; Rect r = new Rect(); int x, y; while (!button()) ; while (button()) ; getMouse(p); x = p.h; y = p.v; // On attend le bouton enfonc e // On attend le bouton rel ach e // On note les coordonn ees du pointeur

5.2. GRAPHISME

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 graphique setRect(s, 50, 50, X1 + 100, Y1 + 100); setDrawingRect(s); showDrawing(); setRect(s, X0, Y0, X1, Y1); frameRect(s); // Le rectangle de jeu getXY(p); // On note les coordonn ees du pointeur x = p.h; y = p.v; dx = 1; // La vitesse initiale dy = 1; // de la balle for (;;) { 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 temporise invertOval(r); // On efface la balle } } }

CHAPITRE 5. COMPLEMENTS

Chapitre 6

Principes de base des syst` emes Unix

6.1 Survol du syst` eme

Le syst` eme UNIX fut d evelopp ea ` Bell laboratories (research) de 1970 a ` 1980 par Ken Thompson et Dennis Ritchie. Il sest rapidement r epandu dans le milieu de la recherche, et plusieurs variantes du syst` eme original ont vu le jour (versions SYSTEM V dAT&T, BSD a ` Berkeley, . . .). Il triomphe aujourdhui aupr` es du grand public avec les diff erentes versions de LINUX1 , dont le cr eateur original est Linus B. Torvalds et qui ont transform e les PC de machines bureautiques certes sophistiqu ees en v eritables stations de travail. Les raisons du succ` es dUNIX sont multiples. La principale est sans doute sa clart e et sa simplicit e. Il a e t ee galement le premier syst` eme non propri etaire qui a bien isol e la par tie logicielle de la partie mat erielle de tout syst` eme dexploitation. Ecrit dans un langage de haut niveau (le langage C, lun des p` eres de JAVA), il est tr` es facile a ` porter sur les nouvelles architectures de machines. Cela repr esente un int er et non n egligeable : les premiers syst` emes dexploitation e taient e crits en langage machine, ce qui ne plaidait pas pour la portabilit e des dits-syst` emes, et donc avait un co ut de portage colossal. Quelle pourrait e tre la devise dUNIX ? Sans doute Programmez, nous faisons le reste. Un ordinateur est une machine complexe, qui doit g erer des dispositifs physiques (la m emoire, les p eriph eriques commes les disques, imprimantes, modem, etc.) et sinterfacer au r eseau (I N TERNET). Lutilisateur na pas besoin de savoir comment est stock e un chier sur le disque, il veut juste consid erer que cest un espace m emoire dans lequel il peut ranger ses donn ees a ` sa convenance. Que le syst` eme se d ebrouille pour assurer la coh erence du chier, quand bien m eme il serait physiquement e parpill e en plusieurs morceaux. Dans le m eme ordre did ees, lutilisateur veut faire tourner des programmes, mais il na cure de savoir comment le syst` eme g` ere la m emoire de lordinateur et comment le programme tourne. Ceci est dautant plus vrai quUNIX est un syst` eme multi-utilisateur et multit aches. On ne veut pas savoir comment les partages de ressources sont effectu es entre diff erents utilisateurs. Chacun doit pouvoir vivre sa vie sans r eveiller lautre. Toutes ces contraintes sont rel egu ees au syst` eme. Notons que ceci nest pas forc ement facile a ` mettre en uvre. Nous verrons plus loin comment le syst` eme d ecide ce que fait le processeur a ` un instant donn e. Le syst` eme UNIX est constitu e de deux couches bien s epar ees : le noyau permet au syst` eme dint eragir avec la partie mat erielle de la machine, la couche sup erieure contient les programmes des utilisateurs. Tout programme qui tourne invoque des primitives de communication avec le noyau, appel ees appels syst` emes. Les plus courants sont ceux qui font les entr ees-sorties et les op erations sur les chiers. La majeure partie des langages de haut niveau
1

La premi` ere version (0.01) a e t e diffus ee en ao ut 1991.

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

(JAVA, C) poss` edent des interfaces qui appellent directement le noyau, mais cela est transparent pour le programmeur moyen.

mat eriel

noyau programmes

F IG . 6.1 Architecture du syst` eme UNIX. Le noyau soccupe du contr ole de lex ecution inviduelle aussi bien que globale des programmes. Un programme qui sex ecute est appel e processus. Le noyau permet la cr eation, la suspension, la n dun processus. Il g` ere de mani` ere e quitable lex ecution de tous les processus pr esents. Il leur alloue et g` ere la place m emoire n ecessaire a ` leur ex ecution.

6.2

Le syst` eme de chiers

Le syst` eme de chiers dUNIX est arborescent, lanc etre de tous les chemins possibles e tant la racine (not ee /). On dispose de r epertoires, qui contiennent eux-m emes des r epertoires et des chiers. Cest l` a la seule vision que veut avoir un utilisateur de lorganisation des chiers. Aucun chier UNIX nest typ e. Pour le syst` eme, tous les chiers (y compris les r epertoires) contiennent des suites doctets, charge au syst` eme lui-m eme et aux programmes a ` interpr eter correctement leur contenu. De m eme, un chier na pas de taille limit ee a priori. Ces deux caract eristiques ne sont pas partag ees par grand nombre de syst` emes... Un des autres traits dUNIX est de traiter facilement les p eriph eriques comme des chiers. Par exemple : unix% cat musique > /dev/audio permet d ecouter le chier musique sur son ordinateur (de fac on primitive...). Cest le syst` eme qui se d ebrouille pour associer le nom sp ecial /dev/audio/ aux hauts-parleurs de lordinateur (sils existent). En interne, un chier est d ecrit par un i-nud (inode pour index node en anglais), qui contient toutes les informations n ecessaires a ` sa localisation sur le disque. Un chier est vu comme une suite doctets, rassembl es en blocs. Ces blocs nont pas vocation a `e tre contigues : les chiers peuvent cro tre de fac on dynamique et une bonne gestion de lespace disque peut amener a ` aller chercher de la place partout sur le disque. Il faut donc g erer une structure de donn ees permettant de r ecup erer ses petits dans le bon ordre. La structure la plus adapt ee est celle dune table contenant des num eros de blocs. Celle-ci est d ecoup ee en trois : la zone des

6.3. LES PROCESSUS

blocs directs contient des num eros de blocs contenant vraiment des donn ees ; la zone simple indirection fait r ef erence a ` une adresse o` u on trouve une table de num eros de blocs directs ; la zone double indirection contient des r ef erences a ` des tables de r ef erences qui font r ef erence a ` des blocs (cf. gure 6.2), et enn a ` la zone triple indirection. La structure de donn ees correspondante est appel ee B-arbre et permet de g erer correctement les disques actuels. direct direct

blocs de donn ees simple indirection double indirection triple indirection F IG . 6.2 Structure bloc dun chier. Le noyau ne manipule jamais les chiers directement sur disque. Il travaille avec des tampons interm ediaires qui permettent de limiter lacc` es a ` la m emoire disque. Cela am eliore les performances des entr ees/sorties et prot` ege les chiers.

6.3
6.3.1

Les processus
Comment traquer les processus

Un processus est un programme qui sex ecute. Comme UNIX est un syst` eme multi-t aches, multi-utilisateurs, il y a toujours un grand nombre de tels processus qui vivent a ` un instant donn e. Les diff erents processus sont stock es dans une table et rep er es par leur num ero dordre. ` A tout instant, on peut consulter la liste des processus appartenant a ` un utilisateur par la commande ps (pour process status) :
unix% PID 646 740 ps TTY pts/1 pts/1 TIME CMD 00:00:00 bash 00:00:00 ps

La premi` ere colonne donne le num ero du processus dans la table, la deuxi` eme le terminal (on dit tty) associ e au processus, le temps CPU utilis e est donn e dans la troisi` eme, et nalement la quatri` eme donne la commande qui a lanc e le processus. On peut e galement obtenir la liste de tous les processus en rajoutant des options a ` ps avec pour r esultat le contenu de la table 6.1. On voit appara tre une colonne STAT qui indique le tat de chaque processus. Dans cet exemple, la commande ps ax est la seule a `e tre active (do` u le R dans la troisi` eme colonne).

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

PID 1 2 3 4 5 6 189 203 254 263 281 295 309 323 368 383 413 460 488 489 490 491 492 600 601 632 633 636 638 640 641 646 647 737 739

TTY ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? tty2 tty3 tty4 tty5 tty6 tty1 tty1 tty1 ? tty1 tty1 tty1 tty1 pts/1 pts/0 pts/0 pts/1

STAT S SW SW SW SW SW< S S S S S S S S S S S S S S S S S S S S S S S S S S S S R

TIME 0:05 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:01 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:02 0:00 0:00 0:00 0:00 0:00 0:00 0:01 0:00

COMMAND init [3] [kflushd] [kupdate] [kpiod] [kswapd] [mdrecoveryd] portmap /usr/sbin/apmd -p 10 -w 5 ... syslogd -m 0 klogd /usr/sbin/atd crond /usr/sbin/ssfd lpd sendmail: gpm -t pnp /usr/bin/postmaster xfs -droppriv -daemon -port -1 /sbin/mingetty tty2 /sbin/mingetty tty3 /sbin/mingetty tty4 /sbin/mingetty tty5 /sbin/mingetty tty6 login -- francois /bin/bash xinit /etc/X11/X :0 sh /home/francois/.xinitrc tvtwm xterm xterm /bin/bash /bin/bash /usr/bin/emacs -nw unix.tex ps ax

TAB . 6.1 R esultat de la commande ps ax.

6.3. LES PROCESSUS

M eme quand on ne fait rien (ici, le seul processus dun utilisateur est l edition dun chier par la commande emacs), il existe plein de processus vivants. Notons parmi ceux-l` a tous les programmes se terminant par un d comme /usr/sbin/ssfd ou lpd, qui sont des programmes syst` emes sp eciaux (appel es d emons) attendant quon les r eveille pour ex ecuter une t ache comme se connecter ou imprimer. On constate que la num erotation des processus nest pas continue. Au lancement du syst` eme, le processus 0 est lanc e, il cr ee le processus 1 qui prend la main. Celui-ci cr ee dautres processus ls qui h eritent de certaines propri et es de leur p` ere. Certains processus sont cr ee s, ex ecutent leur t ache et meurent, le num ero qui leur e tait attribu e disparait. On peut voir larbre g en ealogique des processus qui tournent a ` laide de la commande pstree (voir gure 6.2). Les ? dans la deuxi` eme colonne indiquent lexistence de processus qui ne sont affect es a ` aucun TTY.

6.3.2

Fabrication et gestion

Un processus consiste en une suite doctets que le processeur interpr` ete comme des instructions machine, ainsi que des donn ees et une pile. Un processus ex ecute les instructions qui lui sont propres dans un ordre bien d eni, et il ne peut ex ecuter les instructions appartenant a ` dautres processus. Chaque processus sex ecute dans une zone de la m emoire qui lui est r eserv ee et prot eg ee des autres processus. Il peut lire ou e crire les donn ees dans sa zone m emoire propre, sans pouvoir interf erer avec celles des autres processus. Notons que cette propri et e est caract eristique dUNIX, et quelle est trop souvent absente de certains syst` emes grand public. Les compilateurs g en` erent les instructions machine dun programme en supposant que la m emoire utilisable commence a ` ladresse 0. Charge au syst` eme a ` transformer les adresses virtuelles du programme en adresses physiques. Lavantage dune telle approche est que le code g en er e ne d epend jamais de lendroit dans la m emoire o` u il va vraiment e tre ex ecut e. Cela permet aussi dex ecuter le m eme programme simultan ement : un processus nouveau est cr ee a ` chaque fois et une nouvelle zone de m emoire physique lui est allou e. Que diraient les utilisateurs si l editeur emacs ne pouvait e tre utilis e que par un seul dentre eux a ` la fois ! Le contexte dun processus est la donn ee de son code, les valeurs des variables, les struc` un instant donn tures de donn ees, etc. qui lui sont associ ees, ainsi que de son e tat. A e, un processus peut e tre dans quatre e tats possibles : en cours dex ecution en mode utilisateur ; en cours dex ecution en mode noyau ; pas en ex ecution, mais pr et a ` l etre ; endormi, quand il ne peut plus continuer a ` sex ecuter (parce quil est en attente dune entr ee sortie par exemple). Un processeur ne peut traiter quun seul processus a ` la fois. Le processus peut e tre en mode utilisateur : dans ce cas, il peut acc eder aux donn ees utilisateur, mais pas aux donn ees du noyau. En mode noyau, le processus peut acc eder e galement aux donn ees du noyau. Un processus passe continuellement dun e tat a ` lautre au cours de sa vie, selon des r` egles pr ecises, simpli ees ici dans le diagramme de transition d etats d ecrits a ` la gure 6.3. Il ne peut y avoir changement de contexte quen passant de l etat 2 (mode noyau) a ` l etat 4 (endormi). Dans ce cas, le syst` eme sauvegarde le contexte du processus avant den charger un autre. Le syst` eme pourra reprendre lex ecution du premier processus plus tard. Un processus peut changer d etat de son propre chef (parce quil sendort) ou parce que le noyau vient de recevoir une interruption qui doit e tre trait ee, par exemple parce quun p eriph erique a demand ea ` ce quon soccupe de lui. Notons toutefois que le noyau ne laisse pas tomber un processus quand il ex ecute une partie sensible du code qui pourrait corrompre des donn ees du processus.

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

6.3. LES PROCESSUS

1. ex ecution en mode utilisateur Appel syst` eme ou interruption 2. ex ecution en mode noyau Interruption ou retour dinterruption

sendort se r eveille 4. endormi

e lection

3. pr et

F IG . 6.3 Diagramme de transition d etats.

6.3.3

Lordonnancement des t aches

Le processeur ne peut traiter quun processus a ` chaque fois. Il donne limpression d etre multi-t aches en accordant a ` chacun des processus un peu de temps de traitement a ` tour de r ole. Le syst` eme doit donc g erer lacc` es e quitable de chaque processus au processeur. Le principe g en eral est dallouer a ` chaque processus un quantum de temps pendant lequel il peut ` la n de ce quantum, le syst` sex ecuter dans le processeur. A eme le pr eempte et r ee value la priorit e de tous les processus au moyen dune le de priorit e. Le processus avec la plus haute priorit e dans l etat pr et a ` sex ecuter, charg e en m emoire est alors introduit dans le processeur. La priorit e dun processus est dautant plus basse quil a r ecemment utilis e le processeur. Le temps est mesur e par une horloge mat erielle, qui interrompt p eriodiquement le proces` chaque top dhorloge, le noyau peut ainsi r seur (g en erant une interruption). A eordonner les priorit es des diff erents processus, ce qui permet de ne pas laisser le monopole du processeur a ` un seul processus. La politique exacte dordonnancement des t aches d epend du syst` eme et est trop complexe pour e tre d ecrite ici. Nous renvoyons aux r ef erences pour cela. Notons pour nir que lutilisateur peut changer la priorit e dun processus a ` laide de la commande nice. Si le programme toto nest pas extremement prioritaire, on peut le lancer sur la machine par : unix% nice ./toto & La plus basse priorit e est

unix% nice -19 ./toto &

et la plus haute (utilisable seulement par le super-utilisateur) est . Dans le premier cas, le programme ne tourne que si personne dautre ne fait tourner de programme ; dans le second, le programme devient super-prioritaire, m eme devant les appels syst` emes les plus courants (souris, etc.).

p T

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

6.3.4

La gestion m emoire

Le syst` eme doit partager non seulement le temps entre les processus, mais aussi la m emoire. La m emoire centrale des ordinateurs actuels est de lordre de quelques centaines de m ega octets, mais cela ne suft g en eralement pas a ` un grand nombre dutilisateurs. Chaque processus consomme de la m emoire. De mani` ere simpli ee, le syst` eme g` ere le probl` eme de la fac on suivante. Tant que la m emoire centrale peut contenir toutes les demandes, tout va bien. Quand la m emoire approche de la saturation, le syst` eme d enit des priorit es dacc` es a ` la m emoire, quon ne peut s eparer des priorit es dex ecution. Si un processus est en mode dex ecution, il est logique quil ait priorit e dans lacc` es a ` la m emoire. Inversement, un processus endormi na pas besoin doccuper de la m emoire centrale, et il peut e tre rel egu e dans une autre zone m emoire, g en eralement un disque. On dit que le processus a e t e swapp e2 . Encore plus pr ecis ement, chaque processus op` ere sur de la m emoire virtuelle, cest-` a-dire quil fait comme sil avait toute la m emoire a ` lui tout seul. Le syst` eme soccupe de faire coincider cette m emoire virtuelle avec la m emoire physique. Il fait m eme mieux : il peut se contenter de charger en m emoire la partie de celle-ci dont le processus a vraiment besoin a ` un instant donn e (m ecanisme de pagination).

6.3.5

Le myst` ere du d emarrage

Allumer une machine ressemble au B IG BANG : linstant davant, il ny a rien, linstant dapr` es, lordinateur vit et est pr et a ` travailler. La premi` ere t ache a ` accomplir est de faire charger en m emoire la proc edure de mise en route (on dit plus souvent boot) du syst` eme. On touche l` aa ` un probl` eme de type poule et uf : comment le syst` eme peut-il se charger lui-m eme ? Dans les temps anciens, il sagissait dune proc edure quasi manuelle de reboot, analogue au d emarrage des voitures a ` la manivelle. De nos jours, le processeur a peine r eveill e va lire une m emoire ROM contenant les instructions de boot. Apr` es quelques tests, le syst` eme r ecup` ere sur disque le noyau (chier /vmunix ou ...). Le programme de boot transfert alors la main au noyau qui commence a ` sex ecuter, en construisant le processus 03 , qui cr ee le processus 1 (init) et se transforme en le processus kswapd.

6.4

Gestion des ux

Un programme UNIX typique prend un ou plusieurs ux en entr ee, op` ere un traitement dessus et ressort un ou plusieurs ux. Lexemple le plus simple est celui dun programme sex ecutant sur un terminal : il attend en entr ee des caract` eres tap es par lutilisateur, interpr` ete ces caract` eres dune certaine mani` ere et ressort un r esultat sur le m eme terminal. Par exemple, le programme mail permet denvoyer un email a ` la main : unix% mail moimeme Subject: essai 144 . Un exemple plus e labor e, qui reprend le m eme principe, est le suivant. Plut ot que lire les commandes sur le clavier, le programme va lire les caract` eres sur son entr ee standard, ici un chier contenant le nombre 144 : unix% mail moimeme < cmds Notez la diff erence avec la commande
Cest du franglais, mais le terme est tellement standard... Dans Linux, cest un peu diff erent : des processus sp eciaux sont cr ee s en parall` ele au lancement, mais lid ee est grosso-modo la m eme.
3 2

6.4. GESTION DES FLUX

unix% mail cmds qui transforme cmds en un argument pass e au programme et qui provoque une erreur (` a moins quun utilisateur sappelle cmds. . .). D` es quun programme sex ecute, il lui est associ e trois ux : le premier est le ux dentr ee, le deuxi` eme le ux de sortie, le troisi` eme est un ux destin ea ` recueillir les erreurs dex ecution. Ainsi, on peut rediriger la sortie standard dun programme dans un chier en utilisant : unix% java carre < cmds > resultat En sh ou en bash, la sortie derreur est r ecup er ee comme suit : unix% mail < cmds > resultat 2> erreurs Pour le moment, nous nous sommes content es de g erer les ux de fac on simple, en les fabriquant a ` laide du contenu de chiers. On peut e galement prendre un ux sortant dun programme pour quil serve dentr ee a ` un autre programme. On peut lister les chiers dun r epertoire et leur taille a ` laide de la commande ls -s : unix% ls -s > fic unix% cat fic total 210 138 dps 1 poly.tex 51 unix.tex 20 unixsys.tex Une autre commande dUNIX bien commode est celle permettant de trier un chier a ` laide de plusieurs crit` eres. Par exemple, sort +0n fic permet de trier les lignes de fic suivant la premi` ere colonne : unix% sort +0n fic total 210 1 poly.tex 20 unixsys.tex 51 unix.tex 138 dps Pour obtenir ce r esultat, on a utilis e un chier interm ediaire, alors quon aurait pu proc eder en une seule fois a ` laide de : unix% ls -s | sort +0n Le pipe (tube) permet ainsi de mettre en communucation la sortie standard de ls -s avec lentr ee standard de sort. On peut bien s ur empiler les tubes, et m elanger a ` volont e >, < et |. On a ainsi isol e un des points importants de la philosophie dUNIX : on construit des primitives puissantes, et on les assemble a ` la fac on dun m ecano pour obtenir des op erations plus complexes. On ninsistera jamais assez sur limportance de certaines primitives, comme cat, echo, etc.

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

Chapitre 7

Retrouver linformation
Un tableau permet lacc` es direct a ` un e l ement, et nous allons nous servir grandement de cette propri et e dans les algorithmes de tri et de recherche en table que nous allons consid erer. Ce chapitre va nous permettre dintroduire la notion de complexit e dun algorithme.

7.1

Complexit e des algorithmes

La complexit e dun algorithme est le nombre dop erations e l ementaires (affectations, comparaisons, op erations arithm etiques) effectu ees par un algorithme. Ce nombre sexprime en ees. On dit que la complexit e de lalgorithme est o` u fonction de la taille des donn est dhabitude une combinaison de polyn omes, logarithmes ou exponentielles. Ceci reprend la notation math ematique classique, et signie que le nombre dop erations effectu ees est born e , o` u est une constante, lorsque tend vers linni. par

VqBFrsBt1DID

'ErsBt1D

Consid erer le comportement a ` linni de la complexit e est justi e par le fait que les donn ees des algorithmes sont de grande taille et quon se pr eoccupe surtout de la croissance de cette complexit e en fonction de la taille des donn ees. Une question syst ematique a ` se poser est : que devient le temps de calcul si on multiplie la taille des donn ees par ?

Les algorithmes usuels peuvent e tre class es en un certain nombre de grandes classes de complexit e. . Cest le Les algorithmes sub-lin eaires, dont la complexit e est en g en eral en cas de la recherche dun e l ement dans un ensemble ordonn e ni de cardinal . Les algorithmes lin eaires en complexit e ou en sont consid er es comme rapides, comme l evaluation de la valeur dune expression compos ee de symboles ou les algorithmes optimaux de tri. Plus lents sont les algorithmes de complexit e situ ee entre et , cest le cas de la multiplication des matrices et du parcours dans les graphes. pour sont consid er es comme Au del` a, les algorithmes polynomiaux en lents, sans parler des algorithmes exponentiels (dont la complexit e est sup erieure a ` tout polyn ome en ) que lon saccorde a ` dire impraticables d` es que la taille des donn ees est sup erieure a ` quelques dizaines dunit es.

VqBuwvexy1D 1 VBt1D VBt1uwvex1D 1 VBt1iD VqBt1ED VqBt1D

La recherche de lalgorithme ayant la plus faible complexit e, pour r esoudre un probl` eme donn e, fait partie du travail r egulier de linformaticien. Il ne faut toutefois pas tomber dans certains exc` es, par exemple proposer un algorithme excessivement alambiqu e, d eveloppant mille astuces et ayant une complexit e en , alors quil existe un algorithme simple et clair de complexit e . Surtout, si le gain de lexposant de saccompagne dune perte importante dans la constante multiplicative : passer dune complexit e de lordre de a ` une complexit e de nest pas vraiment une am elioration. Les crit` eres de clart e et

VBt1iD T 1uwvexy1

VBt1I IiD

1 i

46 nom paul roger laure anne pierre yves

CHAPITRE 7. RETROUVER LINFORMATION

tel 2811 4501 2701 2702 2805 2806

F IG . 7.1 Un exemple de table pour la recherche en table de simplicit e doivent e tre consid er es comme aussi importants que celui de lefcacit e dans la conception des algorithmes.

7.2

Recherche en table

Avec les tableaux, on peut aussi faire des tables. Une table contient des informations sur certaines cl es. Par exemple, la table peut e tre un annuaire t el ephonique. Les cl es sont les noms des abonn es. Linformation a ` rechercher est le num ero de t el ephone. Une table est donc un ensemble de paires nom num ero . Il y a plusieurs mani` eres dorganiser cette table : un tableau denregistrement, une liste ou un arbre (comme nous le verrons plus tard). Pour linstant, nous supposons la table d ecrite par deux tableaux nom et tel, indic es en parall` ele, le num ero de t el ephone de nom[i] e tant tel[i].

7.2.1

La recherche s equentielle

La premi` ere m ethode pour rechercher un num ero de t el ephone consiste a ` faire une recherche s equentielle (ou lin eaire). On examine successivement tous les e l ements de la table et on regarde si on trouve un abonn e du nom voulu. Ainsi
static int recherche (String x) { for (int i = 0; i < N; ++i) if (x.equals(nom[i])) return tel[i]; return -1; }

qui peut aussi s ecrire

static int recherche (String x) { int i = 0; while (i < N && !x.equals(nom[i])) ++i; if (i < N) return tel[i]; else return -1; }

Si on a la place, une autre possibilit e est de mettre une sentinelle au bout de la table.

7.2. RECHERCHE EN TABLE

static int recherche (String x) { int i = 0; nom[N] = x; tel[N] = -1; while (! x.equals(nom[i])) ++i; return tel[i]; }

L ecriture de la proc edure de recherche dans la table des noms est alors plus efcace, car on peut remarquer que lon ne fait plus quun test l` a o` u on en faisait deux. La recherche s equentielle est aussi appel ee recherche lin eaire, car il est facile de montrer que lon fait op erations en moyenne, et op erations dans le pire cas. Sur une table de 10000 e l ements, la recherche prend 5000 op erations en moyenne, soit 5ms. Voici un programme complet utilisant la recherche lin eaire en table.

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; } static int recherche (String x) { for (int i = 0; i < N; ++i) if (x.equals(nom[i])) return tel[i]; return -1; } public static void main (String args[]) { Initialisation(); if (args.length == 1) System.out.println (Recherche(args[0])); } }

7.2.2

La recherche dichotomique

Une autre technique de recherche en table est la recherche dichotomique. Supposons que la table des noms soit tri ee en ordre alphab etique (comme lannuaire des PTT). Au lieu de rechercher s equentiellement, on compare la cl ea ` chercher au nom qui se trouve au milieu de la table des noms. Si cest le m eme, on retourne le num ero de t el ephone du milieu, sinon on recommence sur la premi` ere moiti e (ou la deuxi` eme) si le nom recherch e est plus petit (ou plus grand) que le nom rang e au milieu de la table. Ainsi

48
static void initialisation() { nom[0] nom[1] nom[2] nom[3] nom[4] nom[5] } = = = = = =

CHAPITRE 7. RETROUVER LINFORMATION

"anne"; tel[0] = 2702; "laure"; tel[1] = 2701; "paul"; tel[2] = 2811; "pierre"; tel[3] = 2805; "roger"; tel[4] = 4501; "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 nombre de comparaisons pour une table de taille est tel que et . Donc . (Dor enavant, sera simplement e crit .) Si la table a 10000 e l ements, on aura . Cest donc un gain sensible par rapport aux 5000 op erations n ecessaires pour la recherche lin eaire. Bien s ur, la recherche lin eaire est plus simple a ` programmer, et sera donc utilis ee pour les petites tables. Pour des tables plus importantes, la recherche dichotomique est plus int eressante. On peut montrer quun temps sub-logarithmique est possible si on conna t la distribution des objets. Par exemple, dans lannuaire du t el ephone, ou dans un dictionnaire, on sait a priori quun nom commenc ant par la lettre V se trouvera plut ot vers la n. En supposant la distribution uniforme, on peut faire une r` egle de trois pour trouver lindice de l el ement de r ef erence pour la comparaison, au lieu de choisir le milieu, et on suit le reste de lalgorithme de la recherche dichotomique. Cette m ethode est la recherche par interpolation. Alors le temps de recherche est en , cest-` a-dire 4 op erations pour une table de 10000 e l ements, et 5 op erations jusqu` a entr ees dans la table !

d S

dfe

d eqp wu vex BrD d esp AW

uwvex BrD

dfe S hgidkj eml on uwvex

VqBuwT vextuwvexuvD

7.2.3

Insertion dans une table

Dans la recherche lin eaire ou par dichotomie, on ne sest pas pr eoccup e de linsertion dans la table d el ements nouveaux. Cest par exemple tr` es peu souvent le cas pour un annuaire t el ephonique. Mais cela peut e tre fr equent dans dautres utilisations, comme la table des usagers dun syst` eme informatique. Essayons de voir comment organiser linsertion d el ements nouveaux dans une table, dans le cas des recherches s equentielle et dichotomique. Pour le cas s equentiel, il suft de rajouter au bout de la table l el ement nouveau, sil y a la place. Sil ny a pas de place, on appelle une proc edure erreur qui imprimera le message derreur donn e en param` etre et arr etera le programme. Ainsi

7.2. RECHERCHE EN TABLE

void insertion (String x, int val) { ++n; if (n >= N) then erreur ("Debordement de la table"); nom[n] = x; tel[n] = val; }

Linsertion se fait donc en temps constant, en . Dans le cas de la recherche par dichotomie, il faut maintenir la table ordonn ee. Pour ins erer un nouvel e l ement dans la table, il faut dabord trouver son emplacement par une recherche dichotomique (ou s equentielle), puis pousser tous les e l ements derri` ere lui pour pouvoir ins erer le nouvel e l ement au bon endroit. Cela peut donc op erations. Linsertion dans une table ordonn ee de e l ements prend donc prendre un temps .

VBwGD

uwvex1Rgi1 VBt1D

7.2.4

Hachage

Une autre m ethode de recherche en table est le hachage. On utilise une fonction de lensemble des cl es (souvent des cha nes de caract` eres) dans un intervalle dentiers. Pour une cl e , est lendroit o` u lon trouve dans la table. Tout se passe parfaitement bien si est une application injective. Pratiquement, on ne peut arriver a ` atteindre ce r esultat. On tente alors de sen approcher et on cherche aussi a ` minimiser le temps de calcul de . Ainsi un exemple de fonction de hachage est

f xBtfyD

xBtfyD

puissances de 2 peuvent se faire tr` es facilement par des d ecalages, puisque les nombres sont repr esent es en base 2. En g en eral, dans les machines modernes, cette op eration est nettement premier, cest plus rapide que la multiplication par un nombre arbitraire. Quant a ` prendre pour e viter toute interf erence entre les multiplications par et la division par . En effet, si par exemple , alors et la fonction ne d ependrait que du dernier caract` ere de . Le but est donc davoir une fonction de hachage simple a ` calculer et ayant une bonne distribution sur lintervalle . (Attention : il sera techniquement plus simple dans cette section sur le hachage de supposer que les indices des tableaux varient sur au lieu de ). Le calcul de la fonction se fait par la fonction h(x, l), o` u l est la longueur de la cha ne x,

xBtfyD S Btf`"z&Y|{~}6 gf`"(&Y|{~}6 gEEXgf" &tDsv On prend dhabitude { S ied ou { S eec et on suppose que la taille de la table est un nombre premier. Pourquoi ? Dabord, il faut conna tre la structure des ordinateurs pour comprendre le choix de { comme une puissance de 2. En effet, les multiplications par des f { S S eec xmBtfD S f`" & " T #)|& x x { x

"z#)&

" T #)&

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; }

e une entr ee possible dans la table. On peut alors Donc la fonction donne pour toute cl v erier si . Si oui, la recherche est termin ee. Si non, cela signie que la table contient une autre cl e telle que . On dit alors quil y a une collision, et la table doit pouvoir g erer les collisions. Une m ethode simple est de lister les collisions dans une table col parall` ele a ` la table nom. La table des collisions donnera une autre entr ee dans la table des noms o` u peut se trouver la cl e recherch ee. Si on ne trouve pas la valeur a ` cette nouvelle entr ee

x f S9X "xtB fyD& f$

f xmBtf$D S xmBtfyD

CHAPITRE 7. RETROUVER LINFORMATION

paul

0
roger 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

nom

Bt0wD

tel

Bt0oD

col

Bt0oD

pierre

laure

paul roger laure

anne

pierre

yves

anne yves laurent

2805 0 0 2811 0 4501 2701 0 0 0 2702 2806 8064

-1 -1 -1 -1 -1 12 11 -1 -1 -1 -1 -1 10

collisions

laurent

F IG . 7.2 Hachage par collisions s epar ees

La recherche est donn ee par

0 , on continuera avec lentr ee 0 donn ee par 0 Ss " 0F& . Et on continue tant que e " 0&pS Q .
for (int i = h(x); i != -1; i = col[i]) if (x.equals(nom[i])) return tel[i]; return -1;

static int recherche (String x) {

Ainsi la proc edure de recherche prend un temps au plus e gal a ` la longueur moyenne des classes , cest-` a-dire a ` la longueur moyenne d equivalence d enies sur la table par la valeur de des listes de collisions. Si la fonction de hachage est parfaitement uniforme, il ny aura pas de collision et on atteindra tout e l ement en une comparaison. Ce cas est tr` es peu probable. Il y a des algorithmes compliqu es pour trouver une fonction de hachage parfaite sur une table donn ee et xe. Mais si le nombre moyen d el ements ayant m eme valeur de hachage est , o` u est grosso modo le nombre de classes d equivalences d enies par , la recherche prendra un temps . Le hachage ne fait donc que r eduire dun facteur constant le temps pris par la recherche s equentielle. Lint er et du hachage est quil est souvent tr` es efcace, tout en e tant simple a ` programmer. Linsertion dans une table avec le hachage pr ec edent est plus d elicate. En effet, on devrait rapidement fusionner des classes d equivalences de la fonction de hachage, car il faut bien

xmBtfD

S A

7.2. RECHERCHE EN TABLE

mettre les objets a ` ins erer a ` une certaine entr ee dans la table qui correspond elle-m eme a ` une valeur possible de la fonction de hachage. Une solution simple est de supposer la table de taille telle que . Pour ins erer un nouvel e l ement, on regarde si lentr ee calcul ee par la fonction est libre, sinon on met le nouvel e l ement au bout de la table, et on cha ne les collisions entre elles par un nouveau tableau col. (Les tableaux nom, tel et col sont maintenant de taille Nmax). On peut choisir de mettre le nouvel e l ement en t ete ou a ` la n de la liste des collisions ; ici on le mettra en t ete. Remarque : a ` la page 81, tous les outils seront d evelopp es pour encha ner les collisions par des listes ; comme nous ne connaissons actuellement que les tableaux comme structure de donn ee, nous utilisons le tableau col. Linsertion dun nouvel e l ement dans la table s ecrit

|i1i yP

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

if (nom[i] == null) { nom[i] = x; tel[i] = val; } else if (n >= Nmax) erreur ("D ebordement de la table"); else { nom[n] = x; tel[n] = val; col[n] = col[i]; // On met la nouvelle entr ee en t ete col[i] = n; // de la liste des collisions de sa ++n; // classe d equivalence. } }

Au d ebut, on suppose n N, nom "" (cha ne vide) et col pour N . La proc edure dinsertion est donc tr` es rapide et prend un temps constant . Une autre technique de hachage est de faire un hachage a ` adressage ouvert. Le principe en est tr` es simple. Au lieu de g erer des collisions, si on voit une entr ee occup ee lors de linsertion, on range la cl ea ` lentr ee suivante (modulo la taille de la table). On suppose une valeur interdite dans les cl es, par exemple la cha ne vide , pour d esigner une entr ee libre dans la table. Les proc edures dinsertion et de recherche s ecrivent tr` es simplement comme suit
static int recherche (String x) { int i = h(x);

" 0F& S

" 0F& S VBwGD

T U0b

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 ("Debordement de la table"); ++n;

CHAPITRE 7. RETROUVER LINFORMATION

paul

0
roger 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

nom

Bt0oD

tel

Bt0oD

pierre

laure

paul roger laure anne laurent

anne

pierre

yvon

2805 0 0 2811 0 4501 2701 2702 8064 0 0 0 8065

laurent

F IG . 7.3 Hachage par adressage ouvert

7.2. RECHERCHE EN TABLE

i = h(x); while ((nom[i] != null) && ! x.equals(nom[i])) i = (i+1) % N; nom[i] = x; tel[i] = val; }

Dans le cas o` u la cl ea ` ins erer se trouverait d ej` a dans la table, lancien num ero de t el ephone est e cras e, ce qui est ce que lon veut dans le cas pr esent. Il est int eressant de reprendre les m ethodes de recherche en table d ej` a vues et de se poser ce probl` eme. Plus int eressant, on peut se demander si cette m ethode simple de hachage lin eaire est tr` es efcace, et si on ne risque pas, en fait, daboutir a ` une recherche s equentielle standard. Notre probl` eme est donc de comprendre la contigu t e de la fonction de hachage, et la chance que lon peut avoir pour une valeur donn ee de davoir aussi les entr ees , , . . . occup ees. On peut d emontrer est le taux doccupation de la que, si la fonction de hachage est uniforme et si table, le nombre dop erations est : pour une recherche avec succ` es, pour une recherche avec e chec. Donc si , on fait 2 ou 5 op erations, si , on en fait 5 ou 50. La conclusion est donc que, si on est pr et a ` grossir la table de 50%, le temps de recherche est tr` es bon, avec une m ethode de programmation tr` es simple. Une m ethode plus subtile, que lon peut ignorer en premi` ere lecture, est doptimiser le hachage a ` adressage ouvert pr ec edent en introduisant un deuxi` eme niveau de hachage. Ainsi au lieu de consid erer l el ement suivant dans les proc edures de recherche et dinsertion, on changera les instructions

xmBtfyD

gU BFBw!`DID gU BFBw!`D D S

xBtfyDg xmBtfDgv xS Btfy D gv q y S h TP

i := (i+1) mod Nmax;

est une deuxi` eme fonction de hachage. Pour e viter des ph enom` enes de p eriodicit e, o` u il vaut mieux prendre et premiers entre eux. Une m ethode simple, comme est d ej` a suppos e premier, est de faire . Par exemple, est une fonction rapide a ` calculer, et qui tient compte des trois derniers bits de . On peut se mettre toujours dans le cas de distributions uniformes, et de fonctions et ind ependantes. Alors on montre que le nombre dop erations est en moyenne : pour une recherche avec succ` es, pour une recherche avec e chec, en fonction du taux doccupation de la table. Num eriquement, pour , on fait 3 ou 5 op erations, pour , on fait 7 ou 100. Ce qui est tout a ` fait raisonnable. Le hachage est tr` es utilis e pour les correcteurs dorthographe. McIlroy1 a calcul e que, dans un article scientique typique, il y a environ 20 erreurs dorthographe (cest-` a-dire des mots napparaissant pas dans un dictionnaire), et quune collision pour 100 papiers est acceptable. Il suft donc de faire un correcteur probabiliste qui ne risque de se tromper quun cas sur 2000. Au lieu de garder tout le dictionnaire en m emoire, et donc consommer beaucoup de place, il a utilis e un tableau de bits. Il calcule fonctions de hachage ind ependantes pour tout mot , et regarde si les bits positionn es en valent simultan ement 1. On est alors s ur quun mot nest pas dans le dictionnaire si la r eponse est n egative, mais on pense quon a de bonnes chances quil y soit si la r eponse est oui. Un calcul simple montre que la probabilit e pour quun mot dun dictionnaire de entr ees ne positionne pas un bit donn e est . La probabilit e pour quune cha ne quelconque soit reconnue comme un mot du dictionnaire est . Si on veut que cette derni` ere vaille , il suft de prendre et .

S x Btfm#)D

i := (i+u) mod Nmax;

y P

Bw `DpYRuwvexBw Bw!DID Bwp!D S heh 1

x Btf#)FD S m d RBtf" &yvdD f x x S d TP

4 x B D

Bw!kD
1

TeTeT

l2 S $ S S e

Doug McIlroy e tait le chef de l equipe qui a fait le syst` eme Unix a ` Bell laboratories.

CHAPITRE 7. RETROUVER LINFORMATION

On a alors . Pour un dictionnaire de 25000 mots, il faut donc 400000 bits (50 kO), et, pour un de 200000 mots, if faut 3200000 bits (400 kO). McIlroy avait un pdp11 et 50 kO e tait insupportable. Il a compress e la table en ne stockant que les nombres de 0 entre deux 1, ce qui a ramen e la taille a ` 30 kO. Actuellement, la commande spell du syst` eme Unix utilise et une table de 400000 bits.2

1 S u6p S i#%da

S e

Paul Zimmermann a remarqu e que les dictionnaires franc ais sont plus longs que les dictionnaires anglais a ` cause des conjugaisons des verbes. Il a reprogramm e la commande spell en franc ais en utilisant des arbres digitaux qui partagent les pr exes et sufxes des mots dun dictionnaire franc ais de 200000 mots Le dictionnaire tient alors dans une m emoire de 500 kO. Son algorithme est aussi rapide et exact (non probabiliste).

Chapitre 8

R ecursivit e
Les d enitions par r ecurrence sont assez courantes en math ematiques. Prenons le cas de la suite de Fibonacci, d enie par

On obtient donc la suite 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,. . .Nous allons voir que ces d enitions simpl ementent tr` es simplement en informatique par les d enitions r ecursives.

SS S 2 2 g 2

pour

8.1
8.1.1

Fonctions r ecursives
Fonctions num eriques
static int fib (int n) { if (n <= 1) return 1; else return fib (n-1) + fib (n-2); }

Pour calculer la suite de Fibonacci, une transcription litt erale de la formule est la suivante :

fib est une fonction qui utilise son propre nom dans la d enition delle-m eme. Ainsi, si largument est plus petit que 1, on retourne comme valeur 1. Sinon, le r esultat est fib fib . Il est donc possible en Java, comme en beaucoup dautres langages (sauf Fortran), de d enir de telles fonctions r ecursives. Dailleurs, toute suite d enie par r ecurrence s ecrit de cette mani` ere en Java, comme le conrment les exemples num eriques suivants : factorielle et le triangle de Pascal.

GDeg

Bt1D

t 2

Bt1

static int fact(int n)

if (n <= 1) return 1; else return n * fact (n-1); } static int C(int n, int p) if ((n == 0) || (p == n)) {

56 Fib

CHAPITRE 8. RECURSIVITE

BtW@D
Fib

Fib

BFD
Fib

Fib

BFD
Fib

BwGD

Fib

BwGD

BT D

Fib

BwGD

BT D BtW@D

F IG . 8.1 Appels r ecursifs pour fib

return 1; else return C(n-1, p-1) + C(n-1, p); }

On peut se demander comment Java sy prend pour faire le calcul des fonctions r ecursives. Nous allons essayer de le suivre sur le calcul de . Rappelons nous que les arguments sont transmis par valeur dans le cas pr esent, et donc quun appel de fonction consiste a `e valuer largument, puis a ` se lancer dans lex ecution de la fonction avec la valeur de largument. Donc

9(BtW@D

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

). Comptons Il y a donc un bon nombre dappels successifs a ` la fonction fib (9 pour le nombre dappels r ecursifs pour cette fonction. Clairement , et pour . En posant , on en d eduit que pour , . Do` u fib , et donc le nombre dappels r ecursifs vaut fib , cest a ` dire 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,. . . Le nombre dappels r ecursifs est donc tr` es e lev e, dautant plus quil existe une m ethode it erative simple en calculant simultan ement fib et fib . En effet, on a un calcul lin eaire simple

mgv 2 r g 2 S S 1 1 Y Bt1Dti Bt1GD

fib fib

2 S 2 g S 2 Y tB 1D

9(BtW@D S S S 2 S 2 2 gv 2 2 Bt1D

Bt1D S Bt1GD
{

fib fib

Bt1|GD Bt1|D

Ce qui donne le programme it eratif suivant

static int fib(int n)

8.1. FONCTIONS RECURSIVES

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; }

Pour r esumer, une bonne r` egle est de ne pas trop essayer de suivre dans les moindres d etails les appels r ecursifs pour comprendre le sens dune fonction r ecursive. Il vaut mieux en g en eral comprendre synth etiquement la fonction. La fonction de Fibonacci est un cas particulier car son calcul r ecursif est particuli` erement long. Mais ce nest pas le cas en g en eral. Non seulement, l ecriture r ecursive peut se r ev eler efcace, mais elle est toujours plus naturelle et donc plus esth etique. Elle ne fait que suivre les d enitions math ematiques par r ecurrence. Cest une m ethode de programmation tr` es puissante.

8.1.2

La fonction dAckermann

La suite de Fibonacci avait une croissance exponentielle. Il existe des fonctions r ecursives qui croissent encore plus rapidement. Le prototype est la fonction dAckermann. Au lieu de d enir cette fonction math ematiquement, il est aussi simple den donner la d enition r ecursive en Java
static int ack(int m, int n) { if (m == 0) return n + 1; else if (n == 0) return ack (m - 1, 1); else return ack (m - 1, ack (m, n - 1)); }

S 1gU S 1g p 2 t1 p t 2 X BtW#I1D p 2 X BtW#IW@D p II Te , cest a Donc ( BF#iGD p ` dire le nombre datomes de lunivers.
8.1.3 R ecursion imbriqu ee
La fonction dAckermann contient deux appels r ecursifs imbriqu es, cest ce qui la fait cro tre si rapidement. Un autre exemple est la fonction 91 de MacCarthy

On peut v erier que

X X X X

B T #I1D Bw#I1D BF#I1D BF#I1D

58
static int f(int n) {

CHAPITRE 8. RECURSIVITE

if (n > 100) return n - 10; else return f(f(n+11));

Cette fonction anecdotique, qui utilise la r ecursivit e imbriqu ee, est int eressante car il nest pas du tout e vident quune telle d enition donne toujours un r esultat.1 Par exemple, la fonction de Morris suivante
static int g(int m, int n) { if (m == 0) return 1; else return g(m - 1, g(m, n)); }

Ainsi, le calcul de f BFhecD donne f BFhecD S f B f Bw T aeDID S f BFhaeD S EE f Bw TeT D S f B f BweeGDID S T f Bw GD S h . On peut montrer que cette fonction vaut 91 si 1 TeT et 1U T si 1 TeT .

Que vaut alors g ? En effet, on a g g g . Il faut se souvenir que Java passe les arguments des fonctions par valeur. On calcule donc toujours la valeur de largument avant de trouver le r esultat dune fonction. Dans le cas pr esent, le calcul de g(1,0) doit recalculer g(1, 0). Et le calcul ne termine pas.

Bw# T D

Bw# T D S B T # Bw# T DID

8.2

Ind ecidabilit e de la terminaison

Les logiciens G odel et Turing ont d emontr e dans les ann ees 30 quil e tait impossible desp erer trouver un programme sachant tester si une fonction r ecursive termine son calcul. Larr et dun calcul est en effet ind ecidable. Dans cette section, nous montrons quil nexiste pas de fonction qui permette de tester si une fonction Java termine. Nous pr esentons cette preuve sous la forme dune petite histoire : Le responsable des travaux pratiques dInformatique en a assez des programmes qui calculent ind eniment e crits par des e l` eves peu exp eriment es. Cela loblige a ` chaque fois a ` des manipulations compliqu ees pour stopper ces programmes. Il voit alors dans un journal sp ecialis e une publicit e: Ne laissez plus boucler vos programmes ! Utilisez notre fonction termine(o) . Elle prend comme param` etre le nom dun objet et r epond true si la proc edure f de cet objet ne boucle pas ind eniment et false sinon. En nutilisant que les proc edures pour lesquelles termine r epond true, vous e emes vitez tous les probl` de non terminaison. Dailleurs, voici quelques exemples :
class Turing { static boolean termine (Object o) { // d etermine la terminaison de o.f() boolean resultat; // contenu brevet e par le vendeur return resultat; }
1 Certains syst` emes peuvent donner des r esultats partiels, par exemple le syst` eme SYNTOX de Franc ois Bourdoncle qui arrive a ` traiter le cas de cette fonction

8.2. INDECIDABILITE DE LA TERMINAISON

} 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 lesquels termine(o) r epond true puis false. Impressionn e par la publicit e, le responsable des travaux pratiques ach` ete a ` prix dor cette petite merveille et pense que sa vie denseignant va e tre enn tranquille. Un e l` eve lui fait toutefois remarquer quil ne comprend pas lacquisition faite par le Ma tre avec la classe suivante :
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 proc edure o3.f boucle ind eniment, alors termine(o3) false. Donc la boucle while de o3.f sarr ete et o3.f termine. Sinon, si la proc edure o3.f ne boucle pas ind eniec edente boucle ind eniment, et la ment, alors termine(o3) true. La boucle while pr proc edure o3.f boucle ind eniment. Il y a donc une contradiction sur les valeurs possibles de termine(o3) . Cette expression ne peut e tre d enie. Ayant not e le mauvais esprit de lEl` eve, le Ma tre conclut quon ne peut d ecid ement pas faire conance a ` la presse sp ecialis ee ! Lhistoire est presque vraie. Le Ma tre sappelait David Hilbert et voulait montrer la validit e de sa th` ese par des moyens automatiques. LEl` eve impertinent e tait Kurt G odel. Le tout se passait vers 1930. Gr ace a ` G odel, on sest rendu compte que toutes les fonctions math ematiques ne sont pas calculables par programme. Par exemple, il y a beaucoup plus de fonctions de (entiers naturels) dans que de programmes qui sont en quantit e d enombrable. G odel, Turing, Church et Kleene sont parmi les fondateurs de la th eorie de la calculabilit e. Pour e tre plus pr ecis, on peut remarquer que nous demandons beaucoup a ` notre fonction termine , puisquelle prend en argument un objet (en fait une adresse m emoire), d esassemble peut- etre la proc edure correspondante, et d ecide de sa terminaison. Sinon, elle

CHAPITRE 8. RECURSIVITE

ne peut que lancer lex ecution de son argument et ne peut donc tester sa terminaison (quand il ne termine pas). Un r esultat plus fort peut e tre montr e : il nexiste pas de fonction prenant en argument le source de toute proc edure (en tant que cha ne de caract` eres) et d ecidant de sa terminaison. Cest ce r esultat qui est couramment appel e lind ecidabilit e de larr et. Mais montrer la contradiction en Java est alors beaucoup plus dur.

8.3

Proc edures r ecursives

Les proc edures, comme les fonctions, peuvent e tre r ecursives, et comporter un appel r ecursif. Lexemple le plus classique est celui des tours de Hanoi. On a 3 piquets en face de soi, erentes num erot es 1, 2 et 3 de la gauche vers la droite, et rondelles de tailles toutes diff entourant le piquet 1, formant un c one avec la plus grosse en bas et la plus petite en haut. On veut amener toutes les rondelles du piquet 1 au piquet 3 en ne prenant quune seule rondelle a ` la fois, et en sarrangeant pour qu` a tout moment il ny ait jamais une rondelle sous une plus grosse. La l egende dit que les bonzes passaient leur vie a ` Hanoi a ` r esoudre ce probl` eme pour , ce qui leur permettait dattendre l ecroulement du temple de Brahma, et donc la n du monde (cette l egende fut invent ee par le math ematicien franc ais E. Lucas en 1883). Un raisonnement par r ecurrence permet de trouver la solution en quelques lignes. Si , le probl` eme est trivial. Supposons maintenant le probl` eme r esolu pour rondelles pour aller du piquet au piquet . Alors, il y a une solution tr` es facile pour transf erer rondelles de en : 1- on am` ene les rondelles du haut de sur le troisi` eme piquet , 2- on prend la grande rondelle en bas de et on la met toute seule en , 3- on am` ene les rondelles de en . Ceci s ecrit

1 S cXW 0

1 1

1 0 S cr0m|

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); } }

Ces quelques lignes de programme montrent bien comment en g en eralisant le probl` eme, cest` tout autre , un programme r ecursif de quelques lignes peut a ` -dire aller de tout piquet a r esoudre un probl` eme a priori compliqu e. Cest la force de la r ecursion et du raisonnement par r ecurrence. Il y a bien dautres exemples de programmation r ecursive, et la puissance de cette m ethode de programmation a e t ee tudi ee dans la th eorie dite de la r ecursivit e qui sest d evelopp ee bien avant lapparition de linformatique (Kleene [25], Rogers [45]). Le mot r ecursivit e na quun lointain rapport avec celui qui est employ e ici, car il sagissait d etablir une th eorie abstraite de la calculabilit e, cest a ` dire de d enir math ematiquement les objets quon sait calculer, et surtout ceux quon ne sait pas calculer. Mais lid ee initiale de la r ecursivit e est certainement a ` attribuer a ` Kleene (1935).

8.4

Fractales

Consid erons dautres exemples de programmes r ecursifs. Des exemples spectaculaires sont le cas de fonctions graphiques fractales. Nous utilisons les fonctions graphiques du Macintosh (cf. page 30). Un premier exemple simple est le ocon de von Koch [11] qui est d eni comme suit Le ocon dordre 0 est un triangle e quilat eral. Le ocon dordre 1 est ce m eme triangle dont les c ot es sont d ecoup es en trois et

8.4. FRACTALES
Hanoi(n-1, i, 6-(i+j))

2
Aller de i vers j

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

F IG . 8.2 Les tours de Hanoi

CHAPITRE 8. RECURSIVITE

F IG . 8.3 Flocons de von Koch sur lequel sappuie un autre triangle e quilat eral au milieu. Le ocon dordre consiste a ` prendre le ocon dordre m eme op eration sur chacun de ses c ot es.

1gs

en appliquant la

Le r esultat ressemble effectivement a ` un ocon de neige id ealis e. L ecriture du programme est laiss e en exercice. On y arrive tr` es simplement en utilisant les fonctions trigonom etriques sin et cos. Un autre exemple classique est la courbe du Dragon. La d enition de cette courbe est la suivante : la courbe du Dragon dordre 1 est un vecteur entre deux points quelconques et , la courbe du Dragon dordre est la courbe du Dragon dordre entre et suivie de la m eme courbe dordre entre et (` a lenvers), o` u est le triangle isoc` ele rectangle en , et est a ` droite du vecteur . Donc, si et sont les points de coordonn ees et , les coordonn ees de sont

1q k B#I)D Btm#ID S S Btfg@D gBtsvgD Btgg)D BkrfyD

int u, v;

Btfm#Ig9D

La courbe se programme simplement par

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

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

2; 2; v); v);

8.4. FRACTALES

F IG . 8.4 La courbe du Dragon Si on calcule dragon , on voit appara tre un petit dragon. Cette courbe est ce que lon obtient en pliant 10 fois une feuille de papier, puis en la d epliant. Une autre remarque est que ce trac e l` eve le crayon, et que lon pr ef` ere souvent ne pas lever le crayon pour la tracer. Pour ce faire, nous d enissons une autre proc edure dragonBis qui dessine la courbe a ` lenvers. La proc edure dragon sera d enie r ecursivement en fonction de dragon et dragonBis . De m eme, dragonBis est d enie r ecursivement en termes de dragonBis et dragon. On dit alors quil y a une r ecursivit e crois ee.
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) / v = (y + t - z + x) / dragon (n-1, x, y, u, dragonBis (n-1, u, v, } } static void dragonBis(int n, int x, int y, int z, int t) int u, v; if (n == 1) { moveTo (x, y); lineTo (z, t); } else { { {

BF T #% T % # T #%e T #%e T D

2; 2; v); z, t);

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

CHAPITRE 8. RECURSIVITE

Il y a bien dautres courbes fractales comme la courbe de Hilbert, courbe de Peano qui recouvre un carr e, les fonctions de Mandelbrot. Ces courbes servent en imagerie pour faire des parcours al eatoires de surfaces, et donnent des fonds esth etiques a ` certaines images.

Chapitre 9

Tris s equentiels et r ecursifs

9.1 Quest-ce quun tri ?

On suppose quon se donne une suite de ordre croissant au sens large. Ainsi, pour

Tnombres entiers 4 , et on veut les ranger en S , la suite wid#%#i T #%e#%h#%#Gee#iG#e#d F#%#%d#%h#i T #ie#iG#Gid#%#%P

devra devenir

Ce probl` eme est un classique de linformatique. Il a e t ee tudi e en d etail, cf. la moiti e du livre de Knuth [30]. En tant qualgorithme pratique, on le rencontre souvent. Par exemple, il faut e tablir le classement de certains e l` eves, mettre en ordre un dictionnaire, trier lindex dun livre, faire une sortie lisible dun correcteur dorthographe, . . . Il faudra bien faire la distinction entre le tri dun grand nombre d el ements (plusieurs centaines), et le tri de quelques e l ements (un paquet de cartes). Dans ce dernier cas, la m ethode importe peu. Un algorithme amusant, bogotri, consiste a ` regarder si le paquet de cartes est d ej` a ordonn e. Sinon, on le jette par terre. Et on recommence. Au bout dun certain temps, on risque davoir les cartes ordonn ees. Bien s ur, le bogo-tri peut ne pas se terminer. Une autre technique fr equemment utilis ee avec un jeu de cartes consiste a ` regarder sil ny a pas une transposition a ` effectuer. D` es quon en voit une a ` faire, on la fait et on recommence. Cette m ethode marche tr` es bien sur une bonne distribution de cartes. Plus s erieusement, il faudra toujours avoir a ` lesprit que le nombre dobjets a ` trier est important. Ce nest pas la peine de trouver une m ethode sophistiqu ee pour trier 10 e l ements. Pourtant, les exemples trait es dans un cours sont toujours de taille limit ee, pour des raisons p edagogiques il nest pas possible de repr esenter un tri sur plusieurs milliers d el ements. Le tri, par ses multiples facettes, est un tr` es bon exemple d ecole. En g en eral, on exigera que le tri se fasse in situ, cest-` a-dire que le r esultat soit au m eme endroit que la suite initiale. On peut bien s ur trier autre chose que des entiers. Il suft de disposer dun domaine de valeurs muni dune relation dordre total. On peut donc trier des caract` eres, des mots en ordre alphab etique, des enregistrements selon un certain champ. On supposera, pour simplier, quil existe une op eration d echange ou plus simplement daffectation sur les e l ements de la suite a ` trier. Cest pourquoi nous prendrons le cas de valeurs enti` eres.

9.2

l M ethodes de tri e ementaires

Dans tout ce qui suit, on suppose que lon trie des nombres entiers et que ceux-ci se trouvent dans un tableau . Lalgorithme de tri le plus simple est le tri par s election. Il consiste a ` trouver

66 18 3 10

CHAPITRE 9. TRIS SEQUENTIELS ET RECURSIFS

25 9 3 11 13 23 8

F IG . 9.1 Exemple de tri par s election lemplacement de l el ement le plus petit du tableau, cest-` a-dire lentier tel que pour tout . Une fois cet emplacement trouv e, on e change les e l ements et . Puis on recommence ces op erations sur la suite , ainsi on recherche le plus petit e l ement u on na de cette nouvelle suite et on l echange avec . Et ainsi de suite . . . jusquau moment o` plus quune suite compos ee dun seul e l ement . La recherche du plus petit e l ement dun tableau est un des premiers exercices de programmation. La d etermination de la position de cet e l ement est tr` es similaire, elle seffectue a ` laide de la suite dinstructions :

#) #EEEG#) e e

4k @

m = 0; for (int j = 1; j < N; ++j) if (a[j] < a[m]) m = j;

L echange de deux e l ements n ecessite une variable temporaire et seffectue par :

t = a[m]; a[m] = a[1]; a[1] = t;

Il faut refaire cette suite dop erations en remplacant par , puis par et ainsi de suite jusqu` a . Ceci se fait par lintroduction dune nouvelle variable qui prend toutes les valeurs entre et . Ces consid erations donnent lieu au programme pr esent e en d etail ci-dessous. Pour une

9.2. METHODES DE TRI ELEMENTAIRES

fois, nous l e crivons pour une fois en totalit e ; les proc edures dacquisition des donn ees et de restitution des r esultats sont aussi fournies. Pour les autres algorithmes, nous nous limiterons a ` la description de la proc edure effective de tri.
class TriSelection { final static int N = 10; static int[] a = new int[N]; // Le tableau a ` trier

static void initialisation() { // On tire au sort des nombres // entre 0 et 127, en initialisant // le tirage au sort sur lheure 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; } } public static void main (String args[]) { initialisation(); impression(); triSelection(); impression(); } } // // // // On lit le tableau et on limprime On trie On imprime le r esultat

Il est facile de compter le nombre dop erations n ecessaires. A chaque it eration, on d emarre a ` l el ement et on le compare successivement a ` , , . . ., . On fait donc comparaisons. On commence avec et on nit avec . Donc on fait comparaisons, et e changes. Le tri par s election fait donc de lordre de comparaisons. Si , il y a 5000 comparaisons, soit 5 ms si on arrive a ` faire une comparaison et lit eration de la boucle for en 1 s, ce qui est tout a ` fait possible sur une machine plut ot rapide actuellement. On e crira que le tri par s election est en . Son temps est quadratique par rapport aux nombres d el ements du tableau. Une variante du tri par s election est le tri bulle. Son principe est de parcourir la suite en intervertissant toute paire d el ements cons ecutifs non ordonn es. Ainsi apr` es un parcours, l el ement maximum se retrouve en . On recommence avec le pr exe , . . . Le nom de tri bulle vient donc de ce que les plus grands nombres se d eplacent vers la droite en poussant des bulles successives de la gauche vers la droite. Lexemple num erique pr ec edent est donn e avec le tri bulle dans la gure 9.2.

P u EEbUU G I

P6 @ 6y qEe

i EEE( i EEEE(

i A (

CHAPITRE 9. TRIS SEQUENTIELS ET RECURSIFS

10 10

25 25 25

9 9

3 3 3 3

11 11 11 11 11

13 13 13 13 13 13

23 23 23 23 23 23 23

3 3 3 3 3 3 3 3 3 3

18 10 10 10 10 10 10 10

8 8 8 8 8 8

18 18 18 18 18 18 18 9 3 9 9 9 8

9 9 9 9 9 9 3 10 10 10 8

25 3 3 3 3 3 11 11 11 8

25 11 11 11 11 13 13 8

25 13 13 13 18 8

25 23 23 8

25 8

25 25 25 25 25 25 25 25 25

10 9 3 3 3 3 3 3

23 23 23 23 23 23 23 23

18 18 18 18 18 18 18

3 3 3 3 3 3

13 13 13 13 13 13

11 11 11 11 11

10 10 10 10

9 9 9

8 8

F IG . 9.2 Exemple de tri bulle

9.3. ANALYSE EN MOYENNE

La proc edure correspondante utilise un indice i qui marque la n du pr exe a ` trier, et lindice j qui permet de d eplacer la bulle qui monte vers la borne i. On peut compter aussi tr` es facilement le nombre dop erations et se rendre compte quil sagit dun tri en comparaisons et e ventuellement e changes (si par exemple le tableau est donn e en ordre strictement d ecroissant).

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

Analyse en moyenne

Pour analyser un algorithme de tri, cest a ` dire d eterminer le nombre moyen dop erations quil effectue, on utilise le mod` ele des permutations. On suppose dans ce mod` ele que la suite des nombres a ` trier est la suite des entiers et lon admet que toutes les permutations de ces entiers sont e quiprobables. On peut noter que le nombre de comparaisons a ` effectuer pour un tri ne d epend pas des e l ements a ` trier mais de lordre dans lequel ils apparaissent. Les supposer tous compris entre et nest donc pas une hypoth` ese restrictive si on ne sint eresse qu` a lanalyse et si lon se place dans un mod` ele dalgorithme dont lop eration de base est la comparaison.

EEE

Pour une permutation de dans lui-m eme, une inversion est un couple tel que et . Ainsi, la permutation

t X

P EE F % E I %%%P

qui correspond a ` lordre des e l ements de la gure 9.1, comporte inversions. Chaque e change d el ements de la proc edure TriBulle supprime une et une seule inversion et, une fois le tri termin e, il ny a plus aucune inversion. Ainsi le nombre total d echanges effectu es est e gal au nombre dinversions dans la permutation. Calculer le nombre moyen d echanges dans la proc edure de tri bulle revient donc a ` compter le nombre moyen dinversions de lensemble e l ements. Un moyen de faire ce calcul consiste a ` compter le nombre des permutations sur dinversions dans chaque permutation a ` faire la somme de tous ces nombres et a ` diviser par . Ceci est plut ot fastidieux, une remarque simple permet daller plus vite. est la permutation , Limage miroir de toute permutation , , . Il est clair que est une inversion de si et seulement si ce nest pas une inversion de . La somme du nombre dinversions de et de celles de est . On regroupe alors deux par deux les termes de la somme des nombres dinversions des permutations sur e l ements et on obtient que le nombre moyen dinversions sur lensemble des permutations est donn e par :

EE GI

w G

q E EE

G
ce qui est donc le nombre moyen d echanges dans la proc edure TriBulle . On note toutefois que le nombre de comparaisons effectu ees par TriBulle est le m eme que celui de TriSelection soit .

70 18 3 10

CHAPITRE 9. TRIS SEQUENTIELS ET RECURSIFS

25 9 3 11 13 23 8

F IG . 9.3 Exemple de tri par insertion

9.4

Le tri par insertion

Une m ethode compl` etement diff erente est le tri par insertion. Cest la m ethode utilis ee pour trier un paquet de cartes. On prend une carte, puis 2 et on les met dans lordre si n ecessaire, puis ` me carte a 3 et on met la e ` sa place dans les 2 premi` eres, . . . De mani` ere g en erale on suppose ` me premi` eres cartes tri ees. On prend la e carte, et on essaie de la mettre a ` sa place dans les cartes d ej` a tri ees. Et on continue jusqu` a . Ceci donne le programme suivant les

9r m

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

} }

` me e Pour classer le e l ement du tableau a, on regarde successivement en marche arri` ere a ` partir i` e me du . On d ecale les e l ements visit es vers la droite pour pouvoir mettre a[i] a ` sa juste place. Le programme pr ec edent contient une l eg` ere erreur, si a[i] est le plus petit e l ement du tableau, car on va sortir du tableau par la gauche. On peut toujours y rem edier en supposant quon rajoute un e l ement a[0] valant -maxint . On dit alors que lon a mis une sentinelle a ` gauche du tableau a. Ceci nest pas toujours possible, et il faudra alors rajouter un test sur lindice j dans la boucle while. Ainsi, pour le tri par insertion, lexemple num erique pr ec edent est dans la gure 9.3. Le nombre de comparaisons pour ins erer un e l ement dans la suite tri ee de ceux qui le pr ec edent est e gal au nombre dinversions quil pr esente avec ceux-ci augment e dune unit e. Soit ce nombre de comparaisons. On a

Pour la permutation correspondant a ` la suite a ` trier, dont le nombre dinversions est inv le nombre total de comparaisons pour le tri par insertion est

card

G @
inv

F` ,

U y

Do` u le nombre moyen de comparaisons

i U G

Bien que lordre de grandeur soit toujours , ce tri est plus efcace que le tri par s election. De plus, il a la bonne propri et e que le nombre dop erations d epend fortement de lordre initial du tableau. Dans le cas o` u le tableau est presque en ordre, il y a peu dinversions et tr` es peu dop erations sont n ecessaires, contrairement aux deux m ethodes de tri pr ec edentes. Le tri par insertion est donc un bon tri si le tableau a ` trier a de bonnes chances d etre presque ordonn e. Une variante du tri par insertion est un tri d ua ` D. L. Shell en 1959, cest une m ethode de tri que lon peut sauter en premi` ere lecture. Son principe est d eviter davoir a ` faire de longues cha nes de d eplacements si l el ement a ` ins erer est tr` es petit. Nous laissons le lecteur fanatique en comprendre le sens, et le mentionnons a ` titre anecdotique. Au lieu de comparer les e l ements adjacents pour linsertion, on les compare tous les . . ., 1093, 364, 121, 40, 13, 4, et 1 e l ements. (On utilise la suite ). Quand on nit par comparer des e l ements cons ecutifs, ils ont de bonnes chances d etre d ej` a dans lordre. On peut montrer que le tri Shell ne fait pas plus que comparaisons, et se comporte donc bien sur des chiers de taille raisonnable (5000 e l ements). La d emonstration est compliqu ee, et nous la laissons en exercice difcile. On peut prendre tout autre g en erateur que 3 pour g en erer les s equences a ` explorer. Pratt a montr e que pour des s equences de la forme , le co ut est dans le pire cas (mais il est co uteux de mettre cette s equence des dans lordre). Dans le cas g en eral, le co ut (dans le cas le pire) du tri Shell est toujours un probl` eme ouvert. Le tri Shell est tr` es facile a ` programmer et tr` es efcace en pratique (cest le tri utilis e dans le noyau Maple).

e k

!#"%$

static void triShell() { int h = 1; do h = 3*h + 1; while ( h <= N ); do { h = h / 3;

CHAPITRE 9. TRIS SEQUENTIELS ET RECURSIFS

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

Cette m ethode de tri est due a ` C.A.R Hoare en 1960. Son principe est le suivant. On prend un e l ement au hasard dans le tableau a ` trier. Soit sa valeur. On partitionne le reste du tableau en 2 zones : les e l ements plus petits ou e gaux a ` , et les e l ements plus grands ou e gaux a ` . Si on arrive a ` mettre en t ete du tableau les plus petits que et en n du tableau les plus grands, on peut mettre entre les deux zones a ` sa place d enitive. On peut recommencer r ecursivement la proc edure Quicksort sur chacune des partitions tant quelles ne sont pas r eduites a ` un e l ement. Graphiquement, on choisit comme lun des a ` trier. On partitionne le tableau pour obtenir la position de la gure 9.4 (c). Si et sont les bornes a ` gauche et a ` droite des indices du tableau a ` trier, le sch ema du programme r ecursif est

static void qSort(int g, int d)

if (g < d) { v = a[g]; Partitionner le tableau autour de la valeur et mettre a ` sa bonne position qSort (g, m-1); qSort (m+1, d); }

Nous avons pris a[g] au hasard, toute autre valeur du tableau a aurait convenu. En fait, la prendre vraiment au hasard ne fait pas de mal, car c a e vite les probl` emes pour les distributions particuli` eres des valeurs du tableau (par exemple si le tableau est d ej` a tri e). Plus important, il reste a `e crire le fragment de programme pour faire la partition. Une m ethode ing enieuse [6] consiste a ` parcourir le tableau de a ` en g erant deux indices et tels qu` a tout moment on a pour , et pour . Ainsi

X2&

' 43 1

!52&

' (

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 }

698

ce qui donne la proc edure suivante de Quicksort

static void qSort(int g, int d) int i, m, x, v; if (g < d) { v = a[g]; {

9.5. QUICKSORT
(a)

& '

@&
1

52&

( 5@& 1 ( & 1 5@& (

(b)

& '

(c)

2&
'

F IG . 9.4 Partition de Quicksort

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 } x = a[m]; a[m] = a[g]; a[g] = x; // Echanger qSort (g, m-1); qSort (m+1, d); } }

67 67

68 et 69A
et

Cette solution nest pas sym etrique. La pr esentation usuelle de Quicksort consiste a ` encadrer la position nale de par deux indices partant de 1 et et qui convergent vers la position nale de . En fait, il est tr` es facile de se tromper en e crivant ce programme. Cest pourquoi nous avons suivi la m ethode d ecrite dans le livre de Bentley [6]. Une m ethode tr` es efcace et sym etrique est celle qui suit, de Sedgewick [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);

74
} }

CHAPITRE 9. TRIS SEQUENTIELS ET RECURSIFS

On peut v erier que cette m ethode ne marche que si des sentinelles a ` gauche et a ` droite du tableau existent, en mettant un plus petit e l ement que a ` gauche et un plus grand a ` droite. En fait, une mani` ere de garantir cela est de prendre toujours l el ement de gauche, de droite et du milieu, de mettre ces trois e l ements dans lordre, en mettant le plus petit des trois en , le plus grand en et prendre le m edian comme valeur a ` placer dans le tableau a. On peut remarquer aussi comment le programme pr ec edent rend bien sym etrique le cas des valeurs e gales a ` dans le tableau. Le but recherch e est davoir la partition la plus e quilibr ee possible. En effet, le calcul du nombre moyen de comparaisons emprunt ea ` [47] donne , et pour ,

U U

F F EDFGDC F EDFGDC

B U

& 5i C

Do` u par sym etrie

iU
En soustrayant, on obtient apr` es simplication

En divisant par

G H U q D FGDC R H Q P ( S U4I E DFGDC I R

i UG

En approximant

Do` u le r esultat

% #"%$ I 3

Quicksort est donc tr` es efcace en moyenne. Bien s ur, ce tri peut e tre en temps , si les partitions sont toujours d eg en er ees par exemple pour les suites monotones croissantes ou d ecroissantes. Cest un algorithme qui a une tr` es petite constante (1,38) devant la fonction logarithmique. Une bonne technique consiste a ` prendre Quicksort pour de gros tableaux, puis l ements). revenir au tri par insertion pour les petits tableaux ( 8 ou 9 e Le tri par Quicksort est le prototype de la m ethode de programmation Divide and Conquer (en franc ais diviser pour r egner). En effet, Quicksort divise le probl` eme en deux (les 2 appels r ecursifs) et recombine les r esultats gr ace a ` la partition initialement faite autour dun e l ement pivot. Divide and Conquer sera la m ethode chaque fois quun probl` eme peut e tre divis e en morceaux plus petits, et que lon peut obtenir la solution a ` partir des r esultats calcul es sur chacun des morceaux. Cette m ethode de programmation est tr` es g en erale, et reviendra souvent dans le cours. Elle suppose donc souvent plusieurs appels r ecursifs et permet souvent de passer dun nombre dop erations lin eaire a ` un nombre dop erations logarithmique .

"%$t

9.6. LE TRI PAR FUSION

9.6

Le tri par fusion

Une autre proc edure r ecursive pour faire le tri est le tri par fusion (ou par interclassement). La m ethode provient du tri sur bande magn etique (p eriph erique autrefois fort utile des ordinateurs). Cest aussi un exemple de la m ethode Divide and Conquer. On remarque dabord quil est ais e de faire linterclassement entre deux suites de nombres tri es dans lordre croissant. En effet, soient et ces deux suites. Pour obtenir, la suite interclass ee des et , il suft de faire le programme suivant. (On suppose et pour ne pas compliquer la structure que lon met deux sentinelles du programme.)

EEE UT WV i V EEE V i EEE Xi T V V T a` Y u b`

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; if (a[i] <= c[k] = ++i; } else { c[k] = ++j; } k < M+N; ++k) b[j]) { a[i];

b[j];

devient le minimum de et en d ecalant lendroit o` u lon se trouve Successivement, dans la suite ou selon le cas choisi. Linterclassement de et e l ements se fait donc en op erations. Pour faire le tri fusion, en appliquant Divide and Conquer, on trie les deux moiti es de la suite a ` trier, et on interclasse les deux moiti es tri ees. Il y a toutefois une difcult e car on doit copier dans un tableau annexe les 2 moiti es a ` trier, puisquon ne sait pas faire linterclassement en place. Si et sont les bornes a ` gauche et a ` droite des indices du tableau a ` trier, le tri fusion est donc

Wc r

V (

i EEE

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; } } }

CHAPITRE 9. TRIS SEQUENTIELS ET RECURSIFS

La recopie pour faire linterclassement se fait dans un tableau b de m eme taille que a. Il y a une petite astuce en recopiant une des deux moiti es dans lordre inverse, ce qui permet de se passer de sentinelles pour linterclassement, puisque chaque moiti e sert de sentinelle pour lautre moiti e. Le tri par fusion a une tr` es grande vertu. Son nombre dop erations est tel que , et donc . Donc le tri fusion est un tri qui garantit un temps , au prix dun tableau annexe de N e l ements. Ce temps est r ealis e quelle que soit la distribution des donn ees, a ` la diff erence de QuickSort. Plusieurs probl` emes se posent imm ediatement : peut on faire mieux ? Faut-il utiliser ce tri plut ot que QuickSort ? Nous r epondrons plus tard non a ` la premi` ere question, voir section 1. Quant a ` la deuxi` eme question, on peut remarquer que si ce tri garantit un bon temps, la constante petite devant de QuickSort fait que ce dernier est souvent meilleur. Aussi, QuickSort utilise moins de m emoire annexe, puisque le tri fusion demande un tableau qui est aussi important que celui a ` trier. Enn, on peut remarquer quil existe une version it erative du tri par fusion en commenc ant par trier des sous-suites de longueur 2, puis de longueur 4, 8, 16, . . ..

"%$

#"%$ r

#"%$

Chapitre 10

l Structures de donn ees e ementaires

Dans ce chapitre, nous introduisons quelques structures utilis ees de fac on tr` es intensive en programmation. Leur but est de g erer un ensemble ni d el ements dont le nombre nest pas x e a priori. Les e l ements de cet ensemble peuvent e tre de diff erentes sortes : nombres entiers ou r eels, cha nes de caract` eres, ou des objets informatiques plus complexes comme les identicateurs de processus ou les expressions de formules en cours de calcul On ne sint eressera pas aux e l ements de lensemble en question mais aux op erations que lon effectue sur cet ensemble, ind ependamment de la nature de ses e l ements. Ainsi les ensembles que lon utilise en programmation, contrairement a ` ceux consid er es en math ematiques qui sont x es une fois pour toutes, sont des objets dynamiques. Le nombre de leurs e l ements varie au cours de lex ecution du programme, puisquon peut y ajouter et supprimer des e l ements en cours de traitement. Plus pr ecis ement les op erations que lon sautorise sur les ensembles sont les suivantes : tester si lensemble est vide. ajouter l el ement a ` lensemble . v erier si l el ement appartient a ` lensemble . supprimer l el ement de lensemble . Cette gestion des ensembles doit, pour e tre efcace, r epondre au mieux a ` deux crit` eres parfois contradictoires : un minimum de place m emoire utilis ee et un minimum dinstructions e l ementaires pour r ealiser une op eration. La place m emoire utilis ee devrait pour bien faire e tre tr` es voisine du nombre d el ements de lensemble , multipli ee par leur taille ; cest ce qui se passera pour les trois structures que lon va e tudier plus loin. En ce qui concerne la minimisation du nombre dinstructions e l ementaires, on peut tester tr` es simplement si un ensemble est vide et on peut r ealiser lop eration dajout en quelques instructions, toutefois il est impossible de r ealiser une suppression ou une recherche dun e l ement quelconque dans un ensemble en utilisant un nombre dop erations ind ependant du cardinal de cet ensemble (` a moins dutiliser une structure demandant une tr` es grande place en m emoire). Pour am eliorer lefcacit e, on consid` ere des structures de donn ees dans lesquelles on restreint la port ee des op erations de recherche et de suppression dun e l ement en se limitant a ` la r ealisation de ces op erations sur le dernier ou le premier e l ement de lensemble, ceci donne les structures de pile ou de le, nous verrons que malgr e ces restrictions les structures en question ont de nombreuses applications.

R d

10.1

Listes cha n ees

La liste est une structure de base de la programmation, le langage LISP (LISt Processing), conc u par John MacCarthy en 1960, ou sa version plus r ecente Scheme [1], utilise principalement cette structure qui se r ev` ele utile pour le calcul symbolique. Dans ce qui suit on utilise la liste pour repr esenter un ensemble d el ements. Chaque e l ement est contenu dans une cellule, celle ci contient en plus de l el ement ladresse de la cellule suivante, appel ee aussi pointeur. 77

78 t ete

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

t ete

eXf

F IG . 10.1 Ajout dun e l ement dans une liste La recherche dun e l ement dans la liste sapparente a ` un classique jeu de piste dont le but est de retrouver un objet cach e : on commence par avoir des informations sur un lieu o` u pourrait se trouver cet objet, en ce lieu on d ecouvre des informations sur un autre lieu o` u il risque de se trouver et ainsi de suite. Le langage Java permet cette r ealisation a ` laide de classes et dobjets : les cellules sont des objets (cest a ` dire des instances dune classe) dont un des champs contient une r ef erence vers la cellule suivante. La r ef erence vers la premi` ere cellule est elle contenue dans une variable de t ete de liste. Les d eclarations correspondantes sont les suivantes, o` u lon suppose ici que les e l ements stock es dans chaque cellule dont de type entier..
class Liste { int contenu; Liste suivant; Liste (int x, Liste a) { contenu = x; suivant = a; } }

Linstruction new Liste (x, a) construit une nouvelle cellule dont les champs sont x et a. La fonction Liste(x,a) est un constructeur de la classe Liste (un constructeur est une fonction non statique qui se distingue par le type de son r esultat qui est celui de la classe courante et par son absence de nom pour lidentier). Lobjet null appartient a ` toute classe, et repr esentera dans le cas des listes le marqueur de n de liste. Ainsi
new Liste(2, new Liste (7, new Liste (11, null)))

repr esentera la liste 2,7,11. Les op erations sur les ensembles que nous avons consid er ees cidessus sexpriment alors comme suit si on g` ere ceux-ci par des listes :
static boolean estVide (Liste a) { return a == null; }

La proc edure ajouter ins` ere l el ement x en t ete de liste. Ce choix de mettre l el ement en t ete est indispensable pour que le nombre dop erations lors de lajout soit ind ependant de la taille de la liste ; il suft alors de modier la valeur de la t ete de liste ce qui est fait simplement par
static Liste ajouter (int x, Liste a) { return new Liste (x, a); } // Lancienne t ete se retrouve apr` es x

La fonction recherche , qui v erie si l el ement x gure bien dans la liste a, effectue un parcours de la liste pour rechercher l el ement. La variable a est modi ee it erativement par a = a.suivant de fac on a ` parcourir tous les e l ements jusqu` a ce que lon trouve x ou que lon arrive a ` la n de la liste (a = null).

10.1. LISTES CHAINEES

t ete

eXf

t ete

eXf

F IG . 10.2 Suppression dun e l ement dans une liste

static boolean recherche (int x, Liste a) { while (a != null) { if (a.contenu == x) return true; a = a.suivant; } return false; }

La fonction recherche peut aussi e tre e crite de mani` ere r ecursive

static boolean recherche (int x, Liste a) { if (a == null) return false; else if (a.contenu == x) return true; else return recherche (x, a.suivant); }

ou encore
static boolean recherche (int x, Liste a) { if (a == null) return false; else return (a.contenu == x) || recherche (x, a.suivant); }

ou encore encore (quoique non recommand e) :

static boolean recherche (int x, Liste a) { return a != null && (a.contenu == x || recherche (x, a.suivant)); }

Cette e criture r ecursive est syst ematique. pour les fonctions sur les listes. En effet, le type des listes v erie l equation suivante :

les listes peut donc s ecrire r ecursivement sur la structure de sa liste argument. Par exemple, la longueur dune liste se calcule par
static int longueur(Liste a) { if (a == null)

hpi Liste vide qsr Element t Liste o` u u est lunion disjointe et v le produit cart esien. Toute proc edure ou fonction travaillant sur
Liste

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

return 0; else return 1 + longueur (a.suivant);

ce qui est plus e l egant que l ecriture it erative qui suit

static int longueurI(Liste a) { int longueur = 0; while (a != null) { ++longueur; a = a.suivant; } return longueur; }

Choisir entre la mani` ere r ecursive ou it erative est affaire de go ut. Autrefois, on disait que l ecriture it erative e tait plus efcace car utilisant moins de m emoire. Gr ace aux techniques nouvelles de compilation (comme l elimination des r ecursions terminales), cest de moins en moins vrai ; de plus loccupation m emoire est, dans les ordinateurs daujourdhui, une question nettement moins critique. La suppression de la cellule qui contient x seffectue en modiant la valeur de suivant contenue dans le pr ed ecesseur de x : le successeur du pr ed ecesseur de x devient le successeur de x. Un traitement particulier doit e tre fait si l el ement a ` supprimer est le premier e l ement de la liste. La proc edure r ecursive de suppression est tr` es compacte dans sa d enition.
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; }

Une proc edure it erative demande beaucoup plus dattention.

static Liste supprimer (int x, Liste a) { 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; }

Noter que dans les deux fonctions ci-dessus, on a modi e la liste a, on ne peut donc disposer de deux listes distinctes lune qui contient x et lautre identique a ` la pr ec edente, mais ne contenant pas x. Pour ce faire, il faut recopier une partie de la liste a dans une nouvelle

10.1. LISTES CHAINEES

liste, comme le fait le programme suivant, o` u il y a une utilisation un peu plus importante de la m emoire. Mais lespace m emoire perdu est r ecup er e par le glaneur de cellules (GC) de Java, si personne nutilise lancienne liste a. Avec les techniques actuelles de GC a ` g en erations, cette r ecup eration seffectuera tr` es rapidement. Il faut donc noter la diff erence avec un langage comme Pascal ou C, o` u on doit se pr eoccuper de lespace m emoire perdu, si on veut pouvoir le r eutiliser.
static Liste supprimer (int x, Liste a) { if (a != null) return null; else if (a.contenu == x) return a.suivant; else return new Liste (a.contenu, supprimer (x, a.suivant)); }

Une technique souvent utilis ee permet d eviter quelques tests pour supprimer un e l ement dans une liste et plus g en eralement pour simplier la programmation sur les listes. Elle consiste a ` utiliser une garde permettant de rendre homog` ene le traitement de la liste vide et des autres listes. En effet dans la repr esentation pr ec edente, la liste vide na pas la m eme structure que les autres listes. On utilise une cellule plac ee au d ebut et nayant pas dinformation signicative dans le champ contenu ; ladresse de la vraie premi` ere cellule se trouve dans le champ suivant de cette cellule. On obtient ainsi une liste gard ee, lavantage dune telle garde est que la liste vide contient au moins la garde, et que par cons equent un certain nombre de programmes, qui devaient faire un cas sp ecial dans le cas de la liste vide ou du premier e l ement de liste, deviennent plus simples. Cette notion est un peu l equivalent des sentinelles pour les tableaux. On utilisera cette technique dans les proc edures sur les les un peu plus loin (voir page 85) . On peut aussi d enir des listes circulaires gard ees en mettant ladresse de cette premi` ere cellule dans le champ suivant de la derni` ere cellule de la liste. Les listes peuvent aussi e tre g er ees par diff erents autres m ecanismes que nous ne donnons pas en d etail ici. On peut utiliser, par exemple, des listes doublement cha n ees dans lesquelles chaque cellule contient un e l ement et les adresses a ` la fois de la cellule qui la pr ec` ede et de celle qui la suit. Des couples de tableaux peuvent aussi e tre utilis es, le premier contenu contient les e l ements de lensemble, le second adrsuivant contient les adresses de l el ement suivant dans le tableau contenu . Remarque La proc edure ajouter effectue op erations e l ementaires. Elle est donc tr` es efcace. En revanche, les proc edures recherche et supprimer sont plus longues puisquon peut aller jusqu` a parcourir la totalit e dune liste pour retrouver un e l ement. On peut estimer, si on ne fait aucune hypoth` ese sur la fr equence respective des recherches, que le nombre dop erations est en moyenne e gal a ` la moiti e du nombre d el ements de la liste. Ceci est a ` comparer a ` la recherche dichotomique qui effectue un nombre logarithmique de comparaisons et a ` la recherche par hachage qui est souvent bien plus rapide encore. Exemple A titre dexemple dutilisation des listes, nous consid erons la construction dune liste des nombres premiers inf erieurs ou e gaux a ` un entier donn e. Pour construire cette liste, on commence, dans une premi` ere phase, par y ajouter tous les entiers de a ` en commenc ant par le plus grand et en terminant par le plus petit. Du fait de lalgorithme dajout d ecrit plus haut, la liste contiendra donc les nombres en ordre croissant. On utilise ensuite la m ethode classique du crible dEratosth` ene : on consid` ere successivement les e l ements de la liste dans lordre croissant et on supprime tous leurs multiples stricts. Ceci se traduit par la proc edure suivante :

static Liste listePremier (int n) {

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

Liste int

a = null; 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 Nous ne pr etendons pas que cette programmation soit efcace (loin de l` a !). Elle est toutefois simple a `e crire, une fois que lon a a ` sa disposition les fonctions sur les listes. Elle donne de bons r esultats pour inf erieur a ` . Un bon exercice consiste a ` en am eliorer lefcacit e.

Eeee

Exemple Un autre exemple, plus utile, dapplication des listes est la gestion des collisions dans le hachage dont il a e t e question au chapitre 1 (voir page 51). Il sagit pour chaque entier de lintervalle de construire une liste cha n ee form ee de toutes les cl es telles que . Les e l ements de la liste sont des entiers permettant dacc eder aux tableaux des noms et des num eros de t el ephone. Les proc edures de recherche et dinsertion de dans une table deviennent des proc edures de recherche et dajout dans une liste. Ainsi, si la fonction est mal choisie, le nombre de collisions devient important, la plus grande des listes devient de taille imposante et le hachage risque de devenir aussi co uteux que la recherche dans une liste cha n ee ordinaire. Par contre, si est bien choisie, la recherche est rapide.

m R

w EE yx

Liste al[] = new Liste[N-1]; static void insertion (String x, int val) { int i = h(x); al[i] = ajouter (x, al[i]); } static int recherche (String x) { 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 les sont utilis ees en programmation pour g erer des objets qui sont en attente dun traitement ult erieur, par exemple des processus en attente dune ressource du syst` eme, des

10.2. FILES

sommets dun graphe, des nombres entiers en cours dexamen de certaines de leur propri et es, etc . . . Dans une le les e l ements sont syst ematiquement ajout es en queue et supprim es en t ete, la valeur dune le est par convention celle de l el ement de t ete. En anglais, on parle de strat egie FIFO First In First Out, par opposition a ` la strat egie LIFO Last In First Out des piles. De fac on plus formelle, on se donne un ensemble , lensemble des les dont les e l ements sont dans est not e , la le vide (qui ne contient aucun e l ement) est , les op erations sur les les sont vide, ajouter, valeur, supprimer : estVide est une application de dans (vrai, faux), est e gal a ` vrai si et seulement si la le est vide. ajouter est une application de dans , est la le obtenue a ` partir de la le en ins erant l el ement a ` la n de celle-ci. valeur est une application de dans qui a ` une le non vide associe l el ement se trouvant en t ete. supprimer est une application de dans qui associe a ` une le non vide la le obtenue a ` partir de en supprimant son premier e l ement. Les op erations sur les les satisfont les relations suivantes

Pour

e ieh R kIyU ieh R fee g1 h h e ~I EeX R kIj&@Y e k Pour toute le eE ( e EeX R ~Idkyl R B Pour la le fee g1 eh ieh R B Itj B e EeX R B Is R &@ Y eE ( e B ym& @

pd B fee g1 &@Y e

e ( Id dvId~ R Id EeX I ~ d B d I d B wd

e k R ~

Une premi` ere id ee de r ealisation sous forme de programmes des op erations sur les les est emprunt ee a ` une technique mise en oeuvre dans des lieux o` u des clients font la queue pour e tre servis, il sagit par exemple de certains guichets de r eservation dans les gares, de bureaux de certaines administrations, ou des e tals de certains supermarch es. Chaque client qui se pr esente obtient un num ero et les clients sont ensuite appel es par les serveurs du guichet en fonction croissante de leur num ero darriv ee. Pour g erer ce syst` eme deux nombres doivent e tre connus par les gestionnaires : le num ero obtenu par le dernier client arriv e et le num ero du dernier client servi. On note ces deux nombres par n et d ebut respectivement et on g` ere le syst` eme de la fac on suivante la le dattente est vide si et seulement si d ebut n, lorsquun nouveau client arrive on incr emente n et on donne ce num ero au client, lorsque le serveur est libre et peut servir un autre client, si la le nest pas vide, il incr emente d ebut et appelle le possesseur de ce num ero. Dans la suite, on a repr esent e toutes ces op erations en Java en optimisant la place prise par la le en utilisant la technique suivante : on r eattribue le num ero a ` un nouveau client lorsque lon atteint un certain seuil pour la valeur de n. On dit quon a un tableau (ou tampon) circulaire.

class File { final static int MaxF = 100; int int boolean debut; fin; pleine, vide;

84 12 31

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

11 22 91 3
d ebut

23
n

La le contient les nombres 12 31 11 22 91 3

d ebut

%e@
13 53

8
n

Ajout de l el ement 12 31 11 22 91 3

13 53
d ebut

8
n

Suppressions successives de deux e l ements 12

27
d ebut

Ajout de l el ement 12
d ebut n

13 53

File vide apr` es 2 suppressions F IG . 10.3 File g er ee par un tableau circulaire

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
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; } }

Une autre fac on de g erer des les consiste a ` utiliser des listes cha n ees gard ees (voir page 81) dans lesquelles on conna t a ` la fois ladresse du premier et du dernier e l ement. Cela donne les op erations suivantes :
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; }

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

d ebut n

F IG . 10.4 File dattente impl ement ee par une liste

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; } }

Nous avons deux r ealisations possibles des les avec des tableaux ou des listes cha n ees. L ecriture de programmes consiste a ` faire de tels choix pour repr esenter les structures de donn ees. Lensemble des fonctions sur les les peut e tre indistinctement un module manipulant des tableaux ou un module manipulant des listes. Lutilisation des les se fait uniquement a ` travers les fonctions vide, ajouter, valeur, supprimer. Cest donc linterface des les qui importe dans de plus gros programmes, et non leurs r ealisations. Les notions dinterface et de modules seront d evelopp ees au chapitre 7.

10.3

Piles

La notion de pile intervient couramment en programmation, son r ole principal consiste a ` impl ementer les appels de proc edures. Nous nentrerons pas dans ce sujet, plut ot technique, dans ce chapitre. Nous montrerons le fonctionnement dune pile a ` laide dexemples choisis dans l evaluation dexpressions Lisp. On peut imaginer une pile comme une bo te dans laquelle on place des objets et de laquelle on les retire dans un ordre inverse de celui dans lequel on les a mis : les objets sont les uns sur les autres dans la bo te et on ne peut acc eder qu` a lobjet situ e au sommet de la pile. De fac on l ements sont dans plus formelle, on se donne un ensemble , lensemble des piles dont les e est not e , la pile vide (qui ne contient aucun e l ement) est , les op erations sur les piles sont vide, ajouter, valeur, supprimer comme sur les les. Cette fois, les relations satisfaites sont les suivantes (o` u d enote la pile vide)

nId~

supprimer ajouter estVide ajouter valeur ajouter estVide

R nkIyjn R nkIyoR kyf R R B nkI n yp& @

A laide de ces relations, on peut exprimer toute expression sur les piles faisant intervenir les op erations pr ec edentes a ` laide de la seule op eration en partant de la pile . Ainsi lexpression suivante concerne les piles sur lensemble des nombres entiers :

EeX

supprimer ajouter

10.3. PILES
supprimer ajouter valeur ajouter ajouter ajouter ))) Elle peut se simplier en :

n B

n B ))),

eX f E n B

La r ealisation des op erations sur les piles peut seffectuer en utilisant un tableau qui contient les e l ements et un indice qui indiquera la position du sommet de la pile. par r ef erence.
class Pile { final static int maxP = 100; int Element hauteur ; 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)

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

throws ExceptionPile { if (estVide (p)) throw new ExceptionPile ("vide"); -- p.hauteur; }

o` u on suppose quune nouvelle classe d enit les exceptions ExceptionPile :

class ExceptionPile extends Exception { String nom; public ExceptionPile (String x) { nom = x; } }

Remarques Chacune des op erations sur les piles demande un tr` es petit nombre dop erations e l ementaires et ce nombre est ind ependant du nombre d el ements contenus dans la pile. On peut g erer aussi une pile avec une liste cha n ee, les fonctions correspondantes sont laiss ees a ` titre dexercice. Les piles ont e t e consid er ees comme des arguments par r ef erence pour e viter quun appel de fonction ne fasse une copie inutile pour passer largument par valeur.

10.4

Evaluation des expressions arithm etiques pr ex ees

Dans cette section, on illustre lutilisation des piles par un programme d evaluation dexpressions arithm etiques e crites de fac on particuli` ere. Rappelons quexpression arithm etique signie dans le cadre de la programmation : expression faisant intervenir des nombres, des variables et des op erations arithm etiques (par exemple : ). Dans ce qui suit, pour simplier, nous nous limiterons aux op erations binaires et et aux nombres naturels. La g en eralisation a ` des op erations binaires suppl ementaires comme la division et la soustraction est particuli` erement simple, cest un peu plus difcile de consid erer aussi des op erations agissant sur un seul argument comme la racine carr ee, cette g en eralisation est laiss ee a ` titre dexercice au lecteur. Nous ne consid ererons aussi que les entiers naturels en raison de la confusion quil pourrait y avoir entre le symbole de la soustraction et le signe moins.

jqbsr q

Sur certaines machines a ` calculer de poche, les calculs seffectuent en mettant le symbole dop eration apr` es les nombres sur lesquels on effectue lop eration. On a alors une notation dite postx ee. Dans certains langages de programmation, cest par exemple le cas de Lisp ou de Scheme, on e crit les expressions de fac on pr ex ee cest-` a-dire que le symbole dop eration pr ec` ede cette fois les deux op erandes, on d enit ces expressions r ecursivement. Les expressions pr ex ees comprennent : des symboles parmi les suivants : + * ( ) des entiers naturels Une expression pr ex ee est ou bien un nombre entier naturel ou bien est de lune des deux formes :

o` u

et sont des expressions pr ex ees. Cette d enition fait intervenir le nom de lobjet que lon d enit dans sa propre d enition mais on peut montrer que cela ne pose pas de probl` eme logique. En effet, on peut comparer cette d enition a ` celle des nombres entiers : tout entier naturel est ou bien lentier 0 ou bien

tXuvtw )

thuvtyw )

10.4. EVALUATION DES EXPRESSIONS ARITHMETIQUES PREFIXEES

le successeur dun entier naturel. On v erie facilement que les suites de symboles suivantes sont des expressions pr ex ees.
47 (* (+ (+ (+ 2 3) 12 8) (* 2 3) (+ 12 8)) (* (+ 35 36) (+ 5 6)) (* (+ 7 8) (* 9 9)))

Leur e valuation donne respectivement 47, 6, 20, 26 et 1996. Pour repr esenter une expression pr ex ee en Java, on utilise ici un tableau dont chaque e l ement repr esente une entit e de lexpression. Ainsi les expressions ci-dessus seront repr esent ees par des tableaux de tailles respectives 1, 5, 5, 13, 29. Les e l ements du tableau sont des objets a ` trois champs, le premier indique la nature de lentit e : (symbole ou nombre), le second champ est rempli par la valeur de lentit e dans le cas o` u celle ci est un nombre, enn le dernier champ est un caract` ere rempli dans les cas o` u lentit e est un symbole.
class Element { boolean estOperateur; int valeur; char valsymb; }

On utilise les fonctions donn ees ci-dessus pour les piles et on y ajoute les proc edures suivantes :
static int calculer (char a, int x, int y) { switch (a) { case +: return x + y; case *: return x * y; } return -1; }

La proc edure d evaluation consiste a ` empiler les r esultats interm ediaires, la pile contiendra des op erateurs et des nombres, mais jamais deux nombres cons ecutivement. On examine successivement les entit es de lexpression si lentit e est un op erateur ou si cest un nombre et que le sommet de la pile est un op erateur, alors on empile cette entit e. En revanche, si cest un nombre et quen sommet de pile il y a aussi un nombre, on fait agir lop erateur qui pr ec` ede le sommet de pile sur les deux nombres et on r ep` ete lop eration sur le r esultat trouv e. 5 7

e q

781

15 781

q q

9 15 781

q q

F IG . 10.5 Pile d evaluation de lexpression dont le r esultat est 1996

static void inserer (Element x, Pile p) throws ExceptionPile { Element y, op; while (!(Pile.estVide(p) || x.estOperateur ||

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

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; }

Dans ce cas, il peut e tre utile de donner un exemple de programme principal pilotant ces diverses fonctions. Remarquer quon se sert des arguments sur la ligne de commande pour s eparer les diff erents nombres ou op erateurs.
public static void main (String args[]) { 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

Op erations courantes sur les listes

Nous donnons dans ce paragraphe quelques algorithmes de manipulation de listes. Ceux-ci sont utilis es dans les langages o` u la liste constitue une structure de base. La fonction Tail est une primitive classique, elle supprime le premier e l ement dune liste
class Liste { Object contenu; Liste suivant;

10.5. OPERATIONS COURANTES SUR LES LISTES

e e

Tail

eXf

F IG . 10.6 Queue dune liste

e e
Append

e e

eXx

ehx

ehxf

F IG . 10.7 Concat enation de deux listes par Append

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 dune liste vide."); return a.contenu; } static Liste tail (Liste a) { if (a == null) erreur ("Tail dune liste vide."); return a.suivant; }

Des proc edures sur les listes construisent une liste a ` partir de deux autres, il sagit de mettre deux listes bout a ` bout pour en construire une dont la longueur est e gale a ` la somme des longueurs des deux autres. Dans la premi` ere proc edure append, les deux listes ne sont pas modi ees ; dans la seconde nConc, la premi` ere liste est transform ee pour donner le r esultat. Toutefois, on remarquera que, si append copie son premier argument, il partage la n de liste de son r esultat avec son deuxi` eme argument.
static Liste append (Liste a, Liste b) { if (a == null) return b; else return ajouter (a.contenu, append (a.suivant, b)) ;

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

e e e ehx

V eXx eXx ehxf

F IG . 10.8 Concat enation de deux listes par Nconc

} 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; } }

Cette derni` ere proc edure peut aussi s ecrire r ecursivement :

static Liste nConc (Liste a, Liste b) { if (a == null) return b; else { a.suivant = nConc (a.suivant, c); return a; } }

La proc edure de calcul de limage miroir dune liste consiste a ` construire une liste dans laquelle les e l ements de sont rencontr es dans lordre inverse de ceux de . La r ealisation de cette proc edure est un exercice classique de la programmation sur les listes. On en donne ici deux solutions lune it erative, lautre r ecursive, la complexit e est en donc quadratique, mais classique. A nouveau, nReverse modie son argument, alors que Reverse ne le modie pas et construit une nouvelle liste pour son r esultat.

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

ef ehy ehz eG{

F IG . 10.9 Transformation dune liste au cours de nReverse

10.5. OPERATIONS COURANTES SUR LES LISTES

e e e ehf

F IG . 10.10 Liste circulaire gard ee

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 peut aussi avoir une version lin eaire de la version r ecursive, gr ace a ` une fonction auxiliaire accumulant le r esultat dans un de ses arguments :
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 autre exercice formateur consiste a ` g erer des listes dans lesquelles les e l ements sont rang es en ordre croissant. La proc edure dajout devient plus complexe puisquon doit retrouver la position de la cellule o` u il faut ajouter apr` es avoir parcouru une partie de la liste. Nous ne traiterons cet exercice que dans le cas des listes circulaires gard ees, voir page 81. Dans une telle liste, la valeur du champ contenu de la premi` ere cellule na aucune importance. On peut y mettre le nombre d el ements de la liste si lon veut. Le champ suivant de la derni` ere cellule contient lui ladresse de la premi` ere.
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; }

CHAPITRE 10. STRUCTURES DE DONNEES ELEMENTAIRES

Chapitre 11

Arbres
Nous avons d ej` a vu la notion de fonction r ecursive dans le chapitre 2. Consid erons a ` pr esent son e quivalent dans les structures de donn ees : la notion darbre. Un arbre est soit un arbre atomique (une feuille), soit un noeud et une suite de sous-arbres. Graphiquement, un arbre est repr esent e comme suit

f y f }| z
F IG . 11.1 Un exemple darbre

}| { }~ B I

Le noeud est la racine de larbre, , , , , , sont les feuilles, , , , , les noeuds internes. Plus g en eralement, lensemble des noeuds est constitu e des noeuds internes et des feuilles. Contrairement a ` la botanique, on dessine les arbres avec la racine en haut et les feuilles vers le bas en informatique. Il y a bien des d enitions plus math ematiques des arbres, que nous e viterons ici. Si une branche relie un noeud a ` un noeud plus bas, on dira que est un anc etre de . Une propri et e fondamentale dun arbre est quun noeud na quun seul p` ere. Enn, un noeud peut contenir une ou plusieurs valeurs, et on parlera alors darbres e es et de la valeur (ou des valeurs) dun noeud. Les arbres binaires sont des tiquet arbres tels que les noeuds ont au plus 2 ls. La hauteur, on dit aussi la profondeur dun noeud est la longueur du chemin qui le joint a ` la racine, ainsi la racine est elle m eme de hauteur , ses ls de hauteur et les autres noeuds de hauteur sup erieure a ` . Un exemple darbre tr` es utilis e en informatique est la repr esentation des expressions arithm etiques et plus g en eralement des termes dans la programmation symbolique. Nous traiterons ce cas dans le chapitre sur lanalyse syntaxique, et nous nous restreindrons pour linstant au cas

y z { }~ B I

CHAPITRE 11. ARBRES

5 2

v
3 10

v
10 9

v
9

F IG . 11.2 Repr esentation dune expression arithm etique par un arbre des arbres de recherche ou des arbres de tri. Toutefois, pour montrer laspect fondamental de la structure darbre, on peut tout de suite voir que les expressions arithm etiques calcul ees dans la section 10.4 se repr esentent simplement par des arbres comme dans la gure 11.2 pour (* (+ 5 (* 2 3)) (+ (* 10 10) (* 9 9))). Cette repr esentation contient lessence de la structure dexpression arithm etique et fait donc abstraction de toute notation pr ex ee ou postx ee.

11.1

Files de priorit e

Un premier exemple de structure arborescente est la structure de tas (heap1 )utilis ee pour repr esenter des les de priorit e. Donnons dabord une vision intuitive dune le de priorit e. On suppose, comme au paragraphe 10.2, que des gens se pr esentent au guichet dune banque avec un num ero e crit sur un bout de papier repr esentant leur degr e de priorit e. Plus ce nombre est e lev e, plus ils sont importants et doivent passer rapidement. Bien s ur, il ny a quun seul guichet ouvert, et lemploy e(e) de la banque doit traiter rapidement tous ses clients pour que tout le monde garde le sourire. La le des personnes en attente sappelle une le de priorit e. Lemploy e de banque doit donc savoir faire rapidement les 3 op erations suivantes : trouver un maximum dans la le de priorit e, retirer cet e l ement de la le, savoir ajouter un nouvel e l ement a ` la le. Plusieurs solutions sont envisageables. La premi` ere consiste a ` mettre la le dans un tableau et a ` trier la le de priorit e dans lordre croissant des priorit es. Trouver un maximum et le retirer de la le est alors simple : il suft de prendre l el ement de droite, et de d eplacer vers la gauche la borne droite de la le. Mais linsertion consiste a ` faire une passe du tri par insertion pour mettre le nouvel e l ement a ` sa o` u est la longueur de la le. place, ce qui peut prendre un temps Une autre m ethode consiste a ` g erer la le comme une simple le du chapitre pr ec edent, et a ` rechercher le maximum a ` chaque fois. Linsertion est rapide, mais la recherche du maximum peut prendre un temps , de m eme que la suppression. Une m ethode e l egante consiste a ` g erer une structure dordre partiel gr ace a ` un arbre. La le de e l ements est repr esent ee par un arbre binaire contenant en chaque noeud un e l ement de la le (comme illustr e dans la gure 11.3). Larbre v erie deux propri et es importantes : dune part la valeur de chaque noeud est sup erieure ou e gale a ` celle de ses ls, dautre part larbre est quasi complet, propri et e que nous allons d ecrire bri` evement. Si lon divise lensemble des noeuds en lignes suivant leur hauteur, on obtient en g en eral dans un arbre binaire une ligne compos ee simplement de la racine, puis une ligne contenant au plus deux noeuds, et ainsi de

1 Le mot heap a malheureusement un autre sens en Pascal : cest lespace dans lequel sont allou ees les variables dynamiques r ef erenc ees par un pointeur apr` es linstruction new. Il sera bien clair dapr` es le contexte si nous parlons de tas au sens des les de priorit e ou du tas de Pascal pour allouer les variables dynamiques.

11.1. FILES DE PRIORITE

16
2 3

14
4 5 6

10
7

8
8 9 10

F IG . 11.3 Repr esentation en arbre dun tas

w Wx

1 2 3 16 14 10

4 8

5 10

6 9

7 3

8 2

9 4

10 7

F IG . 11.4 Repr esentation en tableau dun tas suite (la ligne contenant au plus noeuds). Dans un arbre quasi complet les lignes, except ee peut e tre la derni` ere, contiennent toutes un nombre maximal de noeuds (soit ). De plus les feuilles de la derni` ere ligne se trouvent toutes a ` gauche, ainsi tous les noeuds internes sont binaires, except e le plus a ` droite de lavant derni` ere ligne qui peut ne pas avoir de ls droit. Les feuilles sont toutes sur la derni` ere et e ventuellement lavant derni` ere ligne. On peut num eroter cet arbre en largeur dabord, cest a ` dire dans lordre donn e par les petits num eros gurant au dessus de la gure 11.3. Dans cette num erotation on v erie que tout noeud a son p` ere en position , le ls gauche du noeud est , le ls droit . Formellement, on peut dire quun tas est un tableau contenant entiers (ou des e l ements dun ensemble totalement ordonn e) satisfaisant les conditions :

3 X 33 3 XU
&

g g

wXWx5w Wx wXyUy x5w gx w xm&

Ceci permet dimpl ementer cet arbre dans un tableau a (voir gure 11.4) o` u le num ero de chaque noeud donne lindice de l el ement du tableau contenant sa valeur. Lajout dun nouvel e l ement a ` la le consiste a ` incr ementer puis a ` poser . Ceci ne repr esente plus un tas car la relation nest pas n ecessairement satisfaite. Pour obtenir un tas, il faut e changer la valeur contenue au noeud et celle contenue par son p` ere, remonter au p` ere et r eit erer jusqu` a ce que la condition des tas soit v eri ee. Ceci se programme par une simple it eration (cf. la gure 11.5).

w Gx5&
{

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; }

CHAPITRE 11. ARBRES

16
2 3 2

16
3

14
4 5 6

10
7 4

14
5 6

10
7

8
8 9 10

10 4 7

3
8

8
9 10

10
11

9 15

16
2 3 2

16
3

14
4 5 6

10
7 4

15
5 6

10
7

8
8 9 10

15
11

9 10

3
8

8
9 10

14
11

9 10

F IG . 11.5 Ajout dans un tas

16
2 3 2

10
3

15
4 5 6

10
7 4

15
5 6

10
7

8
8 9 10

14
11

9 10

3
8

8
9 10

14 4 7

15
2 3 2

15
3

10
4 5 6

10
7 4

14
5 6

10
7

8
8 9 10

14 4 7

3
8

8
9 10

10 4 7

F IG . 11.6 Suppression dans un tas

11.1. FILES DE PRIORITE

On v erie que, si le tas a e l ements, le nombre dop erations nexc edera pas la hauteur de larbre correspondant. Or la hauteur dun arbre binaire complet de noeuds est . Donc Ajouter ne prend pas plus de op erations. On peut remarquer que lop eration de recherche du maximum est maintenant imm ediate dans les tas. Elle prend un temps constant .

#"%$t
{

#"%$t

static int maximum () return a[0]; }

Consid erons lop eration de suppression du premier e l ement de la le. Il faut alors retirer la racine de larbre repr esentant la le, ce qui donne deux arbres ! Le plus simple pour reformer un seul arbre est dappliquer lalgorithme suivant : on met l el ement le plus a ` droite de la derni` ere ligne a ` la place de la racine, on compare sa valeur avec celle de ses ls, on e change cette valeur avec celle du vainqueur de ce tournoi, et on r eit` ere cette op eration jusqu` a ce que la condition des tas soit v eri ee. Bien s ur, il faut faire attention, quand un noeud na quun ls, et ne faire alors quun petit tournoi a ` deux. Le placement de la racine en bonne position est illustr e dans la gure 11.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 suppression du premier e l ement de la le ne prend pas un temps sup erieur a ` la l ements, la suppression prend hauteur de larbre repr esentant la le. Donc, pour une le de e op erations. La repr esentation des les de priorit es par des tas permet donc de faire les trois op erations demand ees : ajout, retrait, chercher le plus grand en op erations. Ces op erations sur les tas permettent de faire le tri HeapSort. Ce tri peut e tre consid er e comme alambiqu e, mais il a la bonne propri et e d etre toujours en temps (comme le Tri fusion, cf page 75). HeapSort se divise en deux phases, la premi` ere consiste a ` construire un tas dans le tableau a ` trier, la seconde a ` r ep eter lop eration de prendre l el ement maximal, le retirer du tas en le mettant a ` droite du tableau. Il reste a ` comprendre comment on peut construire un tas a ` partir d un tableau quelconque. Il y a une m ethode peu efcace, mais syst ematique. On remarque dabord que l el ement de gauche du tableau est a ` lui seul un tas. Puis on ajoute a ` ce tas le deuxi` eme e l ement avec la proc edure Ajouter que nous venons de voir, puis le troisi` eme, . . .. A la n, on obtient bien un tas de e l ements dans le tableau a a ` trier. Le programme est

#"%$t

!#"%$y

#"%$y

static void heapSort () int i;

100
int v;

CHAPITRE 11. ARBRES

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 un d ecompte grossier des op erations, on remarque quon ne fait pas plus de op erations pour construire le tas, puisquil y a appels a ` la proc edure Ajouter . Une m ethode plus efcace, que nous ne d ecrirons pas ici, qui peut e tre trait ee a ` titre dexercice, permet de construire le tas en op erations. De m eme, dans la deuxi` eme phase, on ne fait pas plus de op erations pour d efaire les tas, puisquon appelle fois la proc edure Supprimer . Au total, on fait op erations quelle que soit la distribution initiale du tableau a, comme dans le tri fusion. On peut n eanmoins remarquer que la constante qui se trouve devant est grande, car on appelle des proc edures relativement complexes pour faire et d efaire les tas. Ce tri a donc un int er et th eorique, mais il est en pratique bien moins bon que Quicksort ou le tri Shell.

#"%$ #"%$

v "%$ v

#"%$

11.2

Borne inf erieure sur le tri

Il a e t e beaucoup question du tri. On peut se demander sil est possible de trier un tableau de e l ements en moins de op erations. Un r esultat ancien de la th eorie de linformation montre que cest impossible si on nutilise que des comparaisons. En effet, il faut pr eciser le mod` ele de calcul que lon consid` ere. On peut repr esenter tous les tris que nous avons rencontr es par des arbres de d ecision. La gure 11.7 repr esente un tel arbre pour le tri par insertion sur un tableau de 3 e l ements. Chaque noeud interne pose une question sur la comparaison entre 2 e l ements. Le ls de gauche correspond a ` la r eponse n egative, le ls droit a ` lafrmatif. Les feuilles repr esentent la permutation a ` effectuer pour obtenir le tableau tri e.

#"%$

Th eor` eme 1 Le tri de a ` deux, fait au moins

ements, fond e uniquement sur les comparaisons des e ements deux l l e #"%$ r comparaisons.

D emonstration Tout arbre de d ecision pour trier e l ements a feuilles repr esentant toutes les permutations possibles. Un arbre binaire de feuilles a une hauteur de lordre par la formule de Stirling. de

I #"%$ #"%$

Corollaire 1 HeapSort et le tri fusion sont optimaux (asymptotiquement). En effet, ils accomplissent le nombre de comparaisons donn e comme borne inf erieure dans le th eor` eme pr ec edent. Mais, nous r ep etons quun tri comme Quicksort est aussi tr` es bon en moyenne. Le mod` ele de calcul par comparaisons donne une borne inf erieure, mais peut-on faire mieux dans un autre mod` ele ? La r eponse est oui, si on dispose dinformations annexes comme les valeurs possibles des e l ements a ` trier. Par exemple, si les valeurs sont comprises dans lintervalle , on peut alors prendre un tableau annexe de e l ements qui contiendra en le nombre de ayant la valeur . En une passe sur , on peut remplir le tableau , puis g en erer le tableau tri e en une deuxi` eme passe en ne tenant compte que de linformation rang ee dans . Ce tri prend op erations, ce qui est tr` es bon si est petit.

wz H x

H r

11.3. IMPLEMENTATION DUN ARBRE

101

p
(1,2,3)

p p
(2,1,3)

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

(1,3,2)

(3,1,2)

F IG . 11.7 Exemple darbre de d ecision pour le tri

11.3

Impl ementation dun arbre

Jusqu` a pr esent, les arbres sont apparus comme des entit es abstraites ou nont e t e impl ement es que par des tableaux en utilisant une propri et e bien particuli` ere des arbres complets. On peut bien s ur manipuler les arbres comme les listes avec des enregistrements et des pointeurs. Tout noeud sera repr esent e par un enregistrement contenant une valeur et des pointeurs vers ses ls. Une feuille ne contient quune valeur. On peut donc utiliser des enregistrements avec variante pour signaler si le noeud est interne ou une feuille. Pour les arbres binaires, les deux ls seront repr esent es par les champs filsG, filsD et il sera plus simple de supposer quune feuille est un noeud dont les ls gauche et droit ont une valeur vide.
class Arbre { int Arbre Arbre contenu; filsG; filsD;

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

Pour les arbres quelconques, on peut gagner plus despace m emoire en consid erant des enregistrements variables. Toutefois, en Pascal, il y a une difcult e de typage a ` consid erer des noeuds -aires (ayant ls). On doit consid erer des types diff erents pour les noeuds binaires, ternaires, . . . ou un gigantesque enregistrement avec variante. Deux solutions syst ematiques sont aussi possibles : la premi` ere consiste a ` consid erer le cas maximum (comme pour les arbres binaires)

class Arbre { int Arbre[] contenu; fils;

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

102 la deuxi` eme consiste a ` encha ner les ls dans une liste
class Arbre { int ListeArbres } class ListeArbres { Arbre ListeArbres } contenu; suivant; contenu; fils;

CHAPITRE 11. ARBRES

Avec les tailles m emoire des ordinateurs actuels, on se contente souvent de la premi` ere solution. Mais, si les contraintes de m emoire sont fortes, il faut se rabattre sur la deuxi` eme. Dans une bonne partie de la suite, il ne sera question que darbres binaires, et nous choisirons donc la premi` ere repr esentation avec les champs filsG et filsD. Consid erons a ` pr esent la construction dun nouvel arbre binaire c a ` partir de deux arbres a et b. Un noeud sera ajout ea ` la racine de larbre et les arbres a et b seront les ls gauche et droit respectivement de cette racine. La fonction correspondante prend la valeur du nouveau noeud, les ls gauche et droit du nouveau noeud. Le r esultat sera un pointeur vers ce noeud nouveau. Voici donc comment cr eer larbre de gauche de la gure 11.8.
class Arbre { int Arbre Arbre contenu; filsG; 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 new a7 = new Arbre (20, new new imprimer (a7); }

Arbre Arbre Arbre Arbre

(8, new Arbre (6, null, null), null), (13, null, null)); (3, new Arbre (3, null, null), a5), (25, new Arbre (21, null, null), new Arbre (28, null, null)));

Une fois un arbre cr ee , il est souhaitable de pouvoir limprimer. Plusieurs m ethodes sont possibles. La plus e l egante utilise les fonctions graphiques du Macintosh drawString , moveTo, lineTo. Une autre consiste a ` utiliser une notation lin eaire avec des parenth` eses. Cest la notation inxe utilis ee couramment si les noeuds internes sont des op erateurs dexpressions arithm etique. Larbre pr ec edent s ecrit alors
((3 3 ((6 8 nil) 12 13)) 20 (21 25 28))

Utilisons une m ethode plus rustique en imprimant en alphanum erique sur plusieurs lignes. Ainsi, en penchant un peu la t ete vers la gauche, on peut imprimer larbre pr ec edent comme suit

11.3. IMPLEMENTATION DUN ARBRE

20 3 25 21 12 8 6 28 13

103

La proc edure dimpression prend comme argument larbre a ` imprimer et la tabulation a ` faire avant limpression, cest a ` dire le nombre despaces. On remarquera que toute la difcult e de la proc edure est de bien situer lendroit o` u on effectue un retour a ` la ligne. Le reste est un simple parcours r ecursif de larbre en se plongeant dabord dans larbre de droite.
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); } ");

Nous avons donc vu comment repr esenter un arbre dans un programme, comment le construire, et comment limprimer. Cette derni` ere op eration est typique : pour explorer une structure de donn ee r ecursive (les arbres), il est naturel dutiliser des proc edures r ecursives. Cest a ` nouveau une mani` ere non seulement naturelle, mais aussi tr` es efcace dans le cas pr esent. Comme pour les listes (cf. page 79), la structure r ecursive des programmes manipulant des arbres d ecoule de la d enition des arbres, puisque le type des arbres binaires v erie l equation :

Arbre

hpi Arbre vide q r

Arbre

Element

Arbre

Comme pour limpression, on peut calculer le nombre de noeuds dun arbre en suivant la d enition r ecursive du type des arbres :
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);

104

CHAPITRE 11. ARBRES

L ecriture it erative dans le cas des arbres est en g en eral impossible sans utiliser une pile. On v erie que, pour les arbres binaires qui ne contiennent pas de noeuds unaires, la taille , le nombre de feuilles et le nombre de noeuds internes v erient et .

11.4

Arbres de recherche

La recherche en table et le tri peuvent e tre aussi trait es avec des arbres. Nous lavons vu implicitement dans le cas de Quicksort. En effet, si on dessine les partitions successives obtenues par les appels r ecursifs de Quicksort, on obtient un arbre. On introduit pour les algorithmes de recherche dun e l ement dans un ensemble ordonn e la notion darbre binaire de recherche celui-ci aura la propri et e fondamentale suivante : tous les noeuds du sous-arbre gauche dun noeud ont une valeur inf erieure (ou e gale) a ` la sienne et tous les noeuds du sous-arbre droit ont une valeur sup erieure (ou e gale) a ` la valeur du noeud lui-m eme (comme dans la gure 11.8). Pour la recherche en table, les arbres de recherche ont un int er et quand la table e volue tr` es rapidement, quoique les m ethodes avec hachage sont souvent aussi bonnes, mais peuvent exiger des contraintes de m emoire impossibles a ` satisfaire. (En effet, il faut conna tre la taille maximale a priori dune table de hachage). Nous allons voir que le temps dinsertion dun nouvel e l ement dans un arbre de recherche prend un temps comparable au temps de recherche si cet arbre est bien agenc e. Pour le moment, e crivons les proc edures e l ementaires de recherche et dajout dun e l ement.
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); else return 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); else a.filsD = ajouter (v, a.filsD); return a; }

A nouveau, des programmes r ecursifs correspondent a ` la structure r ecursive des arbres. La proc edure de recherche renvoie un pointeur vers le noeud contenant la valeur recherch ee, null si e chec. Il ny a pas ici dinformation associ ee a ` la cl e recherch ee comme au chapitre 1. On peut bien s ur associer une information a ` la cl e recherch ee en ajoutant un champ dans lenregistrement d ecrivant chaque noeud. Dans le cas du bottin de t el ephone, le champ contenu contiendrait les noms et serait du type String ; linformation serait le num ero de t el ephone. La recherche teste dabord si le contenu de la racine est e gal a ` la valeur recherch ee, sinon on recommence r ecursivement la recherche dans larbre de gauche si la valeur est plus petite que le contenu de la racine, ou dans larbre de droite dans le cas contraire. La proc edure dinsertion dune nouvelle valeur suit le m eme sch ema. Toutefois dans le cas de l egalit e des valeurs, nous la rangeons ici par convention dans le sous arbre de gauche. La proc edure ajouter modie larbre de recherche. Si nous ne voulons pas le modier, nous pouvons adopter comme dans

11.5. ARBRES EQUILIBRES

105

20
2 9

g
2

20
10

3
1 5 8

25
10 1

3
6 9

25
11

3
4

12
6

21 13

3
4

12
7

21 13

8
3

8
3 5

F IG . 11.8 Ajout dans un arbre de recherche le cas des listes la proc edure suivante, qui consomme l eg` erement plus de place, laquelle place peut e tre r ecup er ee tr` es rapidement par le glaneur de cellules :
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); else return new Arbre (v, a.filsG, ajouter (v, a.filsG)); }

Le nombre dop erations de la recherche ou de linsertion d epend de la hauteur de larbre. noeuds, on effectuera Si larbre est bien e quilibr e, pour un arbre de recherche contenant op erations pour chacune des proc edures. Si larbre est un peigne, cest a ` dire compl` etement liforme a ` gauche ou a ` droite, la hauteur vaudra et le nombre dop erations sera pour la recherche et lajout. Il appara t donc souhaitable d equilibrer les arbres au fur et a ` mesure de lajout de nouveaux e l ements, ce que nous allons voir dans la section suivante. Enn, lordre dans lequel sont rang es les noeuds dans un arbre de recherche est appel e ordre inxe. Il correspond au petit num ero qui se trouve au dessus de chaque noeud dans la gure 11.8. Nous avons d ej` a vu dans le cas de l evaluation des expressions arithm etiques (cf page 88) lordre pr exe, dans lequel tout noeud rec oit un num ero dordre inf erieur a ` celui de tous les noeuds de son sous-arbre de gauche, qui eux-m emes ont des num eros inf erieurs aux noeuds du sous-arbre de droite. Finalement, on peut consid erer lordre postxe qui ordonne dabord le sous-arbre de gauche, puis le sous-arbre de droite, et enn le noeud. Cest un bon exercice d ecrire un programme dimpression correspondant a ` chacun de ces ordres, et de comparer lemplacement des diff erents appels r ecursifs.

#"%$ r v

11.5

quilibr Arbres e es

La notion darbre e quilibr eae t e introduite en 1962 par deux russes Adelson-Velskii et Landis, et depuis ces arbres sont connus sous le nom darbres AVL. Il y a maintenant beaucoup de variantes plus ou moins faciles a ` manipuler. Au risque de para tre classiques et vieillots, nous parlerons principalement des arbres AVL. Un arbre AVL v erie la propri et e fondamentale suivante : la diff erence entre les hauteurs des ls gauche et des ls droit de tout noeud ne peut exc eder 1. Ainsi larbre de gauche de la gure 11.8 nest pas e quilibr e. Il viole la propri et e aux

106 B A c a b A

CHAPITRE 11. ARBRES

g
a b

F IG . 11.9 Rotation dans un arbre AVL noeuds num erot es 2 et 7, tous les autres noeuds validant la propri et e. Les arbres repr esentant des tas, voir gure 11.5 sont trivialement e quilibr es. On peut montrer que la hauteur dun arbre AVL de noeuds est de lordre de , ainsi les temps mis par la proc edure Recherche vue page 104 seront en . Il faut donc maintenir l equilibre de tous les noeuds au fur et a ` mesure des op erations dinsertion ou de suppression dun noeud dans un arbre AVL. Pour y arriver, on suppose que tout noeud contient un champ annexe bal contenant la diff erence de hauteur entre le ls droit et le ls gauche. Ce champ repr esente donc la balance ou l equilibre entre les hauteurs des ls du noeud, et on sarrange donc pour maintenir pour tout noeud point e par a. Linsertion se fait comme dans un arbre de recherche standard, sauf quil faut maintenir l equilibre. Pour cela, il est commode que la fonction dinsertion retourne une valeur repr esentant la diff erence entre la nouvelle hauteur (apr` es linsertion) et lancienne hauteur (avant linsertion). Quand il peut y avoir un d es equilibre trop important entre les deux ls du noeud o` u lon ins` ere un nouvel e l ement, il faut recr eer un e quilibre par une rotation simple (gure 11.9) ou une rotation double (gure 11.10). Dans ces gures, les rotations sont prises dans le cas dun r ee quilibrage de la gauche vers la droite. Il existe bien s ur les 2 rotations sym etriques de la droite vers la gauche. On peut aussi remarquer que la double rotation peut se r ealiser par une suite de deux rotations simples. Dans la gure 11.10, il suft de faire une rotation simple de la droite vers la gauche du noeud , suivie dune rotation simple vers la droite du noeud . Ainsi en supposant d ej` ae crites les proc edures de rotation rotD vers la droite et rotG vers la gauche, la proc edure dinsertion s ecrit

#"%$ r

#"%$

3 l3 m

static Arbre ajouter (int v, Arbre a) { return ajouter1 (v, a).p2; } static Paire ajouter1 (int v, Arbre a) { int Paire incr, r; 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);

11.5. ARBRES EQUILIBRES

107

V V

F IG . 11.10 Double rotation dans un arbre AVL

incr = p.p1; a.filsD = p.p2; } a.bal = a.bal + incr; if (incr != 0 && a.bal != 0) if (a.bal < -1) /* La gauche est trop grande */ if (a.filsG.bal < 0) a = rotD (a); else { a.filsG = rotG (a.filsG); a = rotD (a); } else if (a.bal > 1) /* La droite est trop grande */ 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; } }

. On v erie ais ement quau plus une seule Clairement cette proc edure prend un temps rotation ( eventuellement double) est n ecessaire lors de linsertion dun nouvel e l ement. Il reste

#"%$ v

108

CHAPITRE 11. ARBRES

a ` r ealiser les proc edures de rotation. Nous ne consid erons que le cas de la rotation vers la droite, lautre cas sobtenant par sym etrie.
static Arbre rotD (Arbre a) { Arbre int b; bA, bB, bAnew, bBnew;

b = a; a = a.filsG; bA = a.bal; bB = b.bal; b.filsG = a.filsD; a.filsD = b; // Recalculer le champ a.bal bBnew = 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 champ repr esentant l equilibre apr` es rotation. Il pourrait e tre simpli e si nous conservions toute la hauteur du noeud dans un champ. La pr esentation avec les champs bal permet de garder les valeurs possibles entre -2 et 2, de tenir donc sur 3 bits, et davoir le reste dun mot machine pour le champ contenu . Avec la taille , et des m emoires actuelles, ce calcul peut se r ev eler surperu. Toutefois, soient les hauteurs des arbres , et de la gure 11.9. En appliquant la d enition du champ bal, les nouvelles valeurs et de ces champs aux noeuds et se calculent en fonction des anciennes valeurs et par

V mi V V x V x V V V x Esm V V m V V Esb V b U m m UVym V V t t V x t V mim t2V V m m x t m is V V t t

Les formules pour la rotation vers la gauche sobtiennent par sym etrie. On peut m eme remarquer que le champ bal peut tenir sur 1 bit pour signaler si le sous-arbre a une hauteur e gale ou non a ` celle de son sous-arbre fr` ere. La suppression dun e l ement dans un arbre AVL est plus dure a ` programmer, et nous la laissons en exercice. Elle peut demander jusqu` a rotations.

#"%$ r

Les arbres AVL sont d elicats a ` programmer a ` cause des op erations de rotation. On peut montrer que les rotations deviennent inutiles si on donne un peu de exibilit e dans le nombre de ls des noeuds. Il existe des arbres de recherche 2-3 avec 2 ou 3 ls. Lexemple le plus simple est celui des arbres 2-3-4 amplement d ecrits dans le livre de Sedgewick [47]. Un exemple darbre 2-3-4 est d ecrit dans la gure 11.11. La propri et e fondamentale dun tel arbre de recherche est la m eme que pour les noeuds binaires : tout noeud doit avoir une valeur sup erieure ou e gale a ` celles contenues dans ses sous-arbres gauches, et une valeur inf erieure (ou e gale) a ` celles de ses sous-arbres droits. Les noeuds ternaires contiennent 2 valeurs, la premi` ere doit e tre comprise entre les valeurs des sous-arbres gauches et du centre, la deuxi` eme entre celles

11.5. ARBRES EQUILIBRES

109

F IG . 11.11 Exemple darbre 2-3-4 des sous-arbres du centre et de droite. On peut deviner ais ement la condition pour les noeuds a ` 4 ls. Linsertion dun nouvel e l ement dans un arbre 2-3-4 se fait en e clatant tout noeud quaternaire que lon rencontre comme d ecrit dans la gure 11.12. Ces op erations sont locales et ne font intervenir que le nombre de ls des noeuds. Ainsi, on garantit que lendroit o` u on ins` ere la nouvelle valeur nest pas un noeud quaternaire, et il suft de mettre la valeur dans ce noeud a ` lendroit d esir e. (Si la racine est quaternaire, on l eclate en 3 noeuds binaires). Le nombre d eclatements maximum peut e tre pour un arbre de noeuds. Il a e t e mesur e quen moyenne tr` es peu d eclatements sont n ecessaires. Les arbres 2-3-4 peuvent e tre programm es en utilisant des arbres binaires bicolores. On sarrange pour que chaque branche puisse avoir la couleur rouge ou noire (en trait gras sur notre gure 11.13). Il suft dun indicateur bool een dans chaque noeud pour dire si la branche le reliant a ` son p` ere est rouge ou noire. Les noeuds quaternaires sont repr esent es par 3 noeuds reli es en noir. Les noeuds ternaires ont une double repr esentation possible comme d ecrit sur la gure 11.13. Les op erations d eclatement se programment alors facilement, et cest un bon exercice d ecrire la proc edure dinsertion dans un arbre bicolore.

#"%$

110

CHAPITRE 11. ARBRES

d ( e g

V (

d e k

d ( e

F IG . 11.12 Eclatement darbres 2-3-4

F IG . 11.13 Arbres bicolores

Annexe A

D emarrer avec Unix

Unix est un syst` eme dexploitation tr` es r epandu dans le monde de la recherche et de plus en plus en dehors, comme le montre le succ` es foudroyant du dernier de ses avatars, Linux. Cest le syst` eme qui est utilis ea ` lX pour lenseignement. Ce chapitre d ecrit lessentiel de ce que doit savoir lutilisateur dUnix. La premi` ere section rassemble les connaissances de base sur lenvironnement de travail, la deuxi` eme1 donne un aperc u du r eseau Internet, que ce soit en interne ou en externe et la troisi` eme donne quelques e l ements de s ecurit ee l ementaire. Les principes de conception du syst` eme sont d ecrits au chapitre 6.

A.1
A.1.1

Ce que doit savoir lutilisateur

Pas de panique !

Unix est un syst` eme dexploitation robuste. Il est impossible a ` un utilisateur darr eter involontairement un ordinateur au point que le seul rem` ede soit un reboot. Si tout parait bloqu e, on peut souvent sen tirer avec un Ctrl-c (touche Ctrl maintenue enfonc ee pendant quon tape le c) ou avec un des boutons de la souris qui fait appara tre un menu : au pire, se d econnecter suft a ` remettre tout en place.

A.1.2

D emarrage dune session

Quand on se loge sur une station de travail, on tape son nom de login et son mot de passe. Si celui-ci est accept e, le syst` eme lance linstallation dun environnement standard multi-fen etres pour lutilisateur. Dans chaque fen etre (on dit aussi un xterm) est lanc e un interpr eteur de commandes (un SHELL) qui attend en permanence les commandes de lutilisateur quil retransmet au syst` eme qui les ex ecute.

A.1.3

Syst` eme de chiers

Unix organise les chiers de fac on arborescente, dans des r epertoires. R epertoires On les appelle aussi directories. Un r epertoire est une bo te qui peut contenir des chiers et dautres r epertoires (comme les catalogues de MS-DOS, ou les dossiers du Macintosh).
1 les deux premi` eres sections reprennent des notes de cours du magist` ere de lENS e crites par Damien Doligez et Xavier Leroy.

111

112 Exemples de r epertoires :

/users /bin /usr/local/bin

ANNEXE A. DEMARRER AVEC UNIX

On d esigne les chiers (et les r epertoires) contenus dans un r epertoire par : nom de r epertoire/nom de chier. Exemple : /bin/sh est le chier sh contenu dans le r epertoire /bin. Les r epertoires sont organis es en arbre, cest-` a-dire quils sont tous contenus dans un r epertoire (d esign e par /) appel e la racine. Chaque r epertoire contient deux r epertoires sp eciaux (visibles quand on tape ls -a) :
. .. d esigne le r epertoire lui-m eme d esigne le p` ere du r epertoire

Exemples : /users/cie1/. est le m eme r epertoire que /users/cie1 , /users/.. est le m eme que /, etc. Chaque utilisateur a un home-directory. Cest lendroit o` u il range ses chiers. Le homedirectory a pour nom /users/cie /nom. Exemples : /users/cie7/joffre, /users/cie5/foch . On peut aussi d esigner le home-directory dun autre utilisateur par le nom de login de lutilisateur pr ec ed e dun tilde (le caract` ere ). Exemple : foch.

Noms de chiers Un nom de chier qui commence par / est dit absolu. Il est interpr et e en partant de la racine, et en descendant dans larbre. Un nom de chier qui ne commence pas par / est relatif. Il est interpr et e en partant du r epertoire courant. Le r epertoire courant est initialement (au moment o` u vous vous connectez) votre home-directory. Exemples : /users/cie7/joffre/foo est un nom (ou chemin) absolu. bar est un nom relatif. Il d esigne un chier appel e bar et situ e dans le r epertoire courant. Le chier exact dont il sagit d epend donc de votre r epertoire courant. Remarque : Le seul caract` ere sp ecial dans les noms de chiers est le slash /. Un nom de chier peut avoir jusqu` a 255 caract` eres, et contenir un nombre quelconque de points. Commandes pour visiter le syst` eme de chiers pwd afche le r epertoire courant. Exemple :
poly% pwd /users/cie5/foch

cd change le r epertoire courant. Si on ne lui donne pas dargument, on retourne dans le home-directory. Exemple :
poly% cd .. poly% pwd /users/cie5 poly% cd poly% pwd /users/cie5/foch

mkdir cr ee un nouveau r epertoire, (presque) vide, qui ne contient que . et .. rmdir supprime un r epertoire vide. Si le r epertoire contient autre chose que . et .. c a ne marche pas. mv renomme un chier, mais peut aussi le d eplacer dun r epertoire a ` un autre. Exemple :
poly% poly% poly% poly% poly% cd mkdir foo emacs bar mv bar foo/bar2 cd foo

A.1. CE QUE DOIT SAVOIR LUTILISATEUR

poly% pwd /users/cie5/foch/foo poly% ls bar2

113

rm -i foo supprime le chier foo, attention il faut manipuler cette commande avec pr ecaution car on risque de d etruire un chier utile et il est alors impossible de le r ecup erer par la suite. ls liste les chiers et les r epertoires quon lui donne en arguments, ou le r epertoire courant si on ne lui donne pas dargument. ls ne liste pas les chiers dont le nom commence par ., ce qui explique pourquoi . et .. napparaissent pas ci-dessus. Les droits dacc` es Chaque chier a plusieurs propri et es associ ees : le propri etaire, le groupe propri etaire, la date de derni` ere modication, et les droits dacc` es. On peut examiner ces propri et es gr ace a ` loption -lg de ls. Exemple :
poly% ls -lg drw-r--r-- 1 -rw-r--r-- 1 foch foch cie5 cie5 512 7 Sep 30 17 :56 Sep 30 17 :58 foo bar nom du chier date de derni` ere modif. taille en octets groupe propri etaire propri etaire droits des autres droits du groupe droits du propri etaire type

Type - pour les chiers, d pour les r epertoires. Droits du propri etaire r ou - droit de lire le chier (r pour oui, - pour non) w ou - droit d ecrire dans le chier x ou - droit dex ecuter le chier ou de visite pour un r epertoire Droits du groupe Comme les droits du propri etaire, mais sapplique aux gens qui sont dans le groupe propri etaire. Droits des autres Comme les droits du propri etaire, mais sapplique aux gens qui sont ni le propri etaire, ni dans le groupe propri etaire. Propri etaire Le nom de login de la personne a ` qui appartient ce chier. Seul le propri etaire peut changer les droits ou le groupe dun chier. Groupe propri etaire Le nom du groupe du chier. Les groupes sont des ensembles dutilisateurs qui sont x es par ladministrateur du syst` eme. Taille En octets. Pour changer les droits dun chier, la commande est chmod. Exemples : chmod a+x foo ajoute (+) le droit dex ecution (x) pour tout le monde (all) au chier foo chmod g-r bar enl` eve (-) le droit de lecture (r) pour les gens du groupe (group) sur le chier bar chmod u-w gee enl` eve (-) le droit d ecriture (w) pour le propri etaire (user) sur le chier gee

114

ANNEXE A. DEMARRER AVEC UNIX

A.1.4

Comment obtenir de laide

man commande Montre page par page le manuel de commande. Faire Espace pour passer a ` la page suivante, q pour quitter avant la n. Pour quitter, on peut aussi faire Ctrl-c, qui interrompt la plupart des commandes Unix. man -k mot Donne la liste des commandes index ees sur le mot-cl e mot, avec un r esum e de ce quelles font en une ligne. En Linux, man -K est plus convivial. Bien s ur, pour comprendre comment marche man, on tape man man... Dans les programmes interactifs (elm, maple), on peut souvent obtenir de laide en tapant ? ou h. Enn, on peut aussi poser des questions aux utilisateurs habituels des salles informatiques ; certains en savent tr` es long.

A.1.5

Raccourcis pour les noms de chiers

Il est ennuyeux davoir a ` taper un nom complet de chier comme nabuchodonosor , quoique tcsh fasse de la compl etion automatique (taper les premi` eres lettres, suivies de la touche Tab). Il est encore plus ennuyeux davoir a ` taper une liste de chiers pour les donner en arguments a ` une commande, comme : cc -o foo bar.c gee.c buz.c gog.c. Pour e viter ces probl` emes, on peut utiliser des jokers (wildcards en anglais.) Une e toile * dans un nom de chier est interpr et ee par le shell comme nimporte quelle s equence de caract` eres qui ne commence pas par un point. Exemple : cc -o foo *.c. Pour interpr eter l etoile, le shell va faire la liste de tous les noms de chiers du r epertoire courant qui ne commencent pas par . et qui nissent par .c Ensuite, il remplace *.c par cette liste (tri ee par ordre alphab etique) dans la ligne de commande, et ex ecute le r esultat, cest-` adire par exemple : cc -o foo bar.c buz.c foo.c gee.c gog.c. On a aussi le ?, qui remplace un (et exactement un) caract` ere quelconque. Par exemple, ls ?* liste tous les chiers, y compris ceux dont le nom commence par un point. La forme [abcd] remplace un caract` ere quelconque parmi a, b, c, d. Enn, [abcd] remplace un caract` ere quelconque qui ne se trouve pas parmi a, b, c, d. Exemple : echo /users/* afche la m eme chose que ls /users. (La commande echo se contente dafcher ses arguments.) Attention : Cest le shell qui fait le remplacement des arguments contenant un joker. On ne peut donc pas faire mv *.c *.bak, car le shell va passer a ` mv les arguments foo.c bar.c foo.bak bar.bak , et mv ne sait pas quel chier remplacer. Attention aux espaces. Si vous tapez rm * , le shell remplace l etoile par la liste des chiers pr esents, et ils seront tous effac es. Si vous tapez rm *, seuls les chiers dont le nom nit par un tilde seront effac es. Interlude : comment effacer un chier nomm e ?* ? On ne peut pas taper rm ?* car le shell remplace ?* par la liste de tous les chiers du r epertoire courant. On peut taper rm -i * qui supprime tous les chiers, mais en demandant conrmation a ` chaque chier. On r epond no a ` toutes les questions sauf rm: remove ?*?. Autre m ethode : utiliser les m ecanismes de quotation (voir chapitre suivant).

A.1.6

Variables

Le shell a des variables. Pour d esigner le contenu dune variable, on e crit le nom de la variable pr ec ed e dun dollar. Exemple : echo $HOME afche le nom du home-directory de lutilisateur. On peut donner une valeur a une variable avec la commande setenv :

A.2. LE RESEAU DE LX
poly% setenv DISPLAY coucou:0 poly% echo $DISPLAY coucou:0

115

Les valeurs des variables sont accessibles aux commandes lanc ees par le shell. Lensemble de ces valeurs constitue lenvironnement. On peut aussi supprimer une variable de lenvironnement avec unsetenv . Quelques variables denvironnement : PRINTER Pour les commandes dimpression. Contient le nom de limprimante sur laquelle il faut envoyer vos chiers. EDITOR Utilis ee par elm et beaucoup dautres commandes. Contient le nom de votre e diteur de textes pr ef er e. VISUAL La m eme chose quEDITOR. SHELL Contient le nom de votre shell pr ef er e. HOME Contient le nom de votre home-directory. USER Contient votre nom de login. LOGNAME La m eme chose que USER. PATH Contient une liste de r epertoires dans lesquels le shell va chercher les commandes ex ecutables. DISPLAY Contient le nom de la machine qui afche.

A.1.7

Le chemin dacc` es aux commandes

La variable PATH contient le chemin dacc` es aux commandes. Le shell lutilise pour trouver les commandes. Il sagit dune liste de r epertoires s epar es par des :. La plupart des commandes sont en fait des programmes, cest-` a-dire des chiers quon trouve dans le syst` eme de chiers. Quand vous tapez ls, par exemple, le shell ex ecute le chier /bin/ls . Pour trouver ce chier, il cherche dans le premier r epertoire du PATH un chier qui sappelle ls. Sil ne trouve pas, il cherche ensuite dans le deuxi` eme r epertoire et ainsi de suite. Sil ne trouve la commande dans aucun r epertoire du PATH, le shell afche un message derreur. Exemple :
poly% sl sl: Command not found.

A.2

Le r eseau de lX

Le r eseau Internet relie pr` es de 100 millions dutilisateurs dans le monde en juillet 99, ce nombre est en croissance tr` es rapide il a e t e multipli e par 5 en 4 ans. Avec le syst` eme Unix, les machines sinterfacent facilement a ` lInternet, certains services sont aussi disponibles sur Macintosh ou PC. Le r eseau local de lX contient plusieurs sous-r eseaux pour les e l` eves, pour les laboratoires et pour ladministration. Le r eseau des e l` eves relie les chambres, les salles de TD (salles PC ou Hp), la machine sil (passerelle vers lInternet). Physiquement, dans une chambre, on connecte sa machine par un petit c able muni dune prise RJ45. Une ligne en paires torsad ees 10Base/T va de la chambre a un local dans le b atiment. L` a il y a un concentrateur (hub) qui mixe tout le trac sur une bre optique 10 Mbit/s. Il y a un hub et une bre pour chaque e tage. Les bres (une vingtaine) sont regroup ees sur FDDI (Fiber Data Distributed Interface) par un routeur situ e au RdC de la DSI. Le tout est certi ea ` 10 M ega bit/s, et fonctionne vraisemblablement a ` 100 Mbit/s. Dans une salle de TD, les stations Unix et les imprimantes sont connect ees au r eseau. Logiquement, la partie 10Base/T supporte le protocole Ethernet a ` 10 Mbit/s.

116

ANNEXE A. DEMARRER AVEC UNIX

Toute machine a une adresse Internet, de chiffres (192.104.247.103 pour poly) ou symbolique (poly.polytechnique.fr ) qui sont les m emes adresses que pour le courrier e lectronique. A lint erieur de lX, le sufxe polytechnique.fr est inutile. Les PC de la salle 35 ont des noms dos (radius, cubitus, . . .), les stations Hp de la salle 34 des noms de poissons (carpe, lieu, . . .), celles de la salle 36 des noms de voitures (ferrari, bugatti, . . .) Les PC de la salle 33 ont des noms de d epartement (loire, marne, . . .). Pour les PC, il faut rentrer ladresse Internet manuellement. Dans les salles TD, elle est e crite en face de chaque chaise. Voici une liste de services courants (cf. la r ef erence pour beaucoup plus de d etails).

wziGx

slogin Pour se connecter sur une autre machine et y ex ecuter des commandes. sftp Pour transf erer des chiers depuis une autre machine. Sur certaines machines, on peut faire des transferts sans y avoir un compte, en se connectant sous le nom anonymous ; do` u le nom de anonymous FTP, ou FTP anonyme, donn ea ` cette m ethode de transfert de chiers. xrn Pour lire les News (le forum a ` l echelle mondiale). xwais Pour interroger des bases de donn ees par mots-cl e. xarchie Pour obtenir les sources domaine public sur le r eseau. netscape Pour consulter les sites multi-media du World Wide Web. irc Pour perdre son e nergie a ` discuter avec le monde entier. eudora Pour lire son courrier sur Mac. fetch Pour faire ftp depuis les Mac. Certains services (connexions internes, courrier, news) sont disponibles depuis toute machine du r eseau des e l` eves. Les autres (et en particulier les connexions a ` lInternet) ne sont disponibles que depuis la machine sil. Il convient donc douvrir une session sur sil pour acc eder a ` tous les services de lInternet.

A.3

Un peu de s ecurit e

Unix a e t e cr ee dans un temps o` u le r eseau n etait pas aussi e tendu quaujourdhui, et o` u on faisait conance aux utilisateurs. Lexp erience a montr e quil valait mieux se montrer prudent quand on utilise Unix comme passerelle pour se connecter a ` distance. Nous ne parlerons pas ici du courrier e lectronique, pour lequel les proc edures a ` mettre en uvre sont plus complexes. Il est fortement conseill e de se mettre en rapport avec la DSI pour apprendre comment lire son courrier depuis sa chambre sans se faire sniffer son mot de passe.

A.3.1

Mots de passe

Beaucoup de programmes utilisent des mots de passe : login (sur poly, sur sil), connection a ` distance (slogin), courrier e lectronique. La s ecurit e exige que tous ces mots de passe soient diff erents et difciles a ` trouver. Rappelons quelques consignes de base. La premi` ere est que le mot de passe soit le plus long possible (g en eralement, on demande 8 caract` eres), et nexiste dans aucun dictionnaire connu (franc ais, anglais, langue maternelles diverses,etc.), de sorte a ` r esister aux attaques par e num eration exhaustive des dictionnaires pr esents sur le r eseau. Il nest pas bon de choisir des noms trop facilement identiables (le pire e tant le mot enom associ e au nom), ceux de son copain ou sa copine, son de passe nom de login ou le pr chien ou son poisson rouge, ou leur date de naissance. De l eg` eres modications a ` des mots de ce type ne sont pas sufsantes, si les r` egles de changement sont trop simples (renversement des mots, permutation des voyelles, etc.). De m eme, il est pr ef erable de m elanger lettres, chiffres, caract` eres sp eciaux (` a lexception notable du #, de @ et des lettres accentu ees).

A.3. UN PEU DE SECURITE

117

Sugg erons deux moyens classiques de r esoudre ce probl` eme : le premier est de choisir une s equence de caract` eres compl` etement al eatoires, de pr ef erence facile a ` m emoriser (mais n etant pas susceptible des attaques d ecrites ci-dessus, comme le classique AZERTY). Le second est de choisir une phrase code et de choisir comme mot de passe les premi` eres lettres de chaque mot.

A.3.2

` distance Acc` es a

En Unix standard, il existe deux utilitaires de connection a ` distance, rlogin et telnet. Ces deux programmes ont la f acheuse propri et e de faire circuler les mots de passe en clair sur le r eseau, ce qui permet de les capturer au passage pour pouvoir ensuite se substituer aux utilisateurs l egitimes. Pour pallier ce probl` eme, ces deux programmes ont e t e retir es de la circulation et remplac es par lunique programme slogin qui chiffre les mots de passe avant de les envoyer sur le r eseau. Il est m eme possible, si besoin est, de faire appel a ` un mode tr` es s ur, qui utilise de lauthentication a ` clefs publiques, de type RSA. Pour transf erer les chiers, le programme standard, ftp, souffre e galement de ce probl` eme de transfert des mots de passe en clair. Il a e t e remplac e par sftp. Tous ces programmes sutilisent de fac on transparente pour lutilisateur, comme dans lexemple qui suit :
monpc% slogin poly -l moi moi@polys 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/tcsh bilbo%

Dans le cas dune utilisation depuix Linux, il suft daller chercher linstallation standard disponible sur http://www.in2p3.fr/securite/. La lecture de la documentation daccompagnement est recommand ee.

118

ANNEXE A. DEMARRER AVEC UNIX

Annexe B

Utilisation avanc ee du SHELL

B.1
B.1.1

Compl ements
Quotation

Avec tous ces caract` eres sp eciaux1 , comment faire pour passer des arguments bizarres a ` une commande ? Par exemple, comment faire afcher un point dinterrogation suivi dune e toile et dun dollar par echo ? Le shell fournit des m ecanismes pour ce faire. Ce sont les quotations. ec eder un caract` ere sp ecial dun backslash, et le Le plus simple est le backslash . Il suft de pr shell remplace ces deux caract` eres par le caract` ere sp ecial seul. Evidemment, le backslash est lui-m eme un caract` ere sp ecial. Attention, tout ceci est tr` es d ependant de la machine et les exemples ci-dessous ne sont pas garantis. Exemples :

poly% echo \\$ $ poly% echo \\\\\\\\$ \\\$

Un autre moyen est dinclure une cha ne de caract` eres entre apostrophes (simple quotes) . Tout ce qui se trouve entre deux apostrophes sera pass e tel quel par le shell a ` la commande. Exemple :
poly% echo $?*\ $?*\

Enn, on peut utiliser des guillemets (double quotes) ". Les guillemets se comportent comme les apostrophes, a ` une exception pr` es : les dollars et les backslashes sont interpr et es entre les guillemets. Exemple :
poly% echo "$HOME/*" /users/cie5/foch/*

Une technique utile : Quand on juxtapose deux cha nes de caract` eres quot ees, le shell les concat` ene, et elles ne forment quun argument. Exemple :
poly% echo """ "

Quant aux interactions plus compliqu ees (backslashes a ` lint erieur des guillemets, guillemets a ` lint erieur des apostrophes, etc.), le meilleur moyen de savoir si c a donne bien le r esultat attendu est dessayer. La commande echo est bien utile dans ce cas.
1

On suit ici encore les notes de cours du magist` ere de lENS e crites par Damien Doligez et Xavier Leroy.

119

120

ANNEXE B. UTILISATION AVANCEE DU SHELL

Derni` ere forme de quotation : commande. Le shell ex ecute la commande, lit la sortie de la commande mot par mot, et remplace commande par la liste de ces mots. Exemple :
poly% echo ls Mail News bin foo g7 lib misc marne.aux marne.dvi marne.log poly% ls -lg which emacs -rwxr-xr-x 1 root system 765952 Dec 17 1992 /usr/local/bin/emacs

La commande which cmd employ ee ci-dessus afche sur sa sortie le nom absolu du chier ex ecut e par le shell quand on lance la commande cmd.
poly% which emacs /usr/local/bin/emacs

B.1.2

Redirections et ltres

Chaque commande a une entr ee standard, une sortie standard, et une sortie derreur. Par d efaut, lentr ee standard est le clavier, la sortie standard est l ecran (la fen etre), et la sortie derreur est aussi l ecran (la fen etre). On peut rediriger la sortie standard dune commande vers un chier (caract` ere >). Le r esultat de la commande sera plac e dans le chier au lieu de safcher sur l ecran. Exemple :
poly% ls -l >foo

Le r esultat de ls -l ne safche pas a ` l ecran, mais il est plac e dans le chier foo. On peut alors taper
poly% more foo

pour lire le chier page par page. On peut aussi rediriger lentr ee standard dune commande (caract` ere <). La commande lira alors le chier au lieu du clavier. Exemple :
poly% elm joffre <foo

envoie par mail a ` Joseph Joffre le r esultat de la commande ls -l de tout a ` lheure. On peut aussi taper more <foo qui est e quivalent a ` more foo car more sans argument lit son entr ee standard et lafche page par page sur le terminal. On peut aussi se passer du chier interm ediaire gr ace a ` un pipe (caract` ere |). Un pipe connecte directement la sortie standard dune commande sur lentr ee standard dune autre commande. Exemple : pour afcher page par page la liste des chiers du r epertoire courant, faire
ls -l | more

La panoplie compl` ete des redirections est la suivante : > change la sortie standard de la commande pour la placer dans un chier. < change lentr ee standard de la commande pour la prendre dans un chier. >& place la sortie standard et la sortie erreur dans un chier. | branche la sortie standard de la commande de gauche sur lentr ee standard de la commande de droite. |& branche la sortie standard et la sortie erreur de la commande de gauche sur lentr ee standard de la commande de droite. >> change la sortie standard pour lajouter a ` la n dun chier existant. >>& place la sortie standard et la sortie erreur a ` la n dun chier existant.

B.1. COMPLEMENTS

121

Remarques : Normalement, une redirection avec > sur un chier qui existe d ej` a efface le contenu du chier avant dy placer le r esultat de la commande. Il existe une option qui dit au shell tcsh de refuser deffacer le chier. Le pipe avec |& est utile pour capturer tout ce qui sort dune commande. Exemple : ls -R / |& more afche page par page la liste de tous les chiers du syst` eme, sans que les messages derreur d erangent lafchage. Une ligne de commandes contenant des | sappelle un pipe-line. Quelques commandes souvent utilis ees dans les pipe-lines sont : more a ` la n du pipe-line, afche le r esultat page par page, pour laisser le temps de le lire. wc compte le nombre de caract` eres, de mots et de lignes de son entr ee. grep cherche dans son entr ee les lignes contenant un mot donn e, et les e crit sur sa sortie. sort lit toutes les lignes de son entr ee, les trie, et les e crit dans lordre sur sa sortie tail e crit sur sa sortie les derni` eres lignes de son entr ee. head e crit sur sa sortie les premi` eres lignes de son entr ee. cat copie plusieurs chiers sur sa sortie. fold coupe les lignes de son entr ee a ` 80 caract` eres et e crit le r esultat sur sa sortie. Exemples :
poly% cat glop buz >toto

Concat` ene les chiers glop et buz et place le r esultat dans toto.
poly% wc -w /usr/dict/words

Afche le nombre de mots du dictionnaire Unix.

poly% grep gag /usr/dict/words | tail

Afche les 20 derniers mots du dictionnaire qui contiennent la cha ne gag.

B.1.3

Processus

Si on lance une commande qui prend beaucoup de temps, on peut linterrompre en tapant Ctrl-c. Ceci interrompt (d enitivement) la commande. On peut aussi ex ecuter une commande en t ache de fond. Le shell rend alors la main avant la n de la commande. Pour le faire, on ajoute un & a ` la n de la commande :
poly% javac grosfichier.java &

Cette commande lance le compilateur javac en parall` ele avec le shell. On reprend la main imm ediatement, sans attendre la n de lex ecution de la commande. On peut donc taper dautres commandes pendant que la pr ec edente sex ecute. La commande ps ou ps -x montre o` u en sont les t aches de fond :
poly% PID 4450 4782 4841 ps TT p9 p9 p9 STAT S S R TIME 0:00 0:02 0:00 COMMAND /usr/local/bin/tcsh javac grosfichier.java ps

Unix est un syst` eme multi-t aches, cest-` a-dire quil peut ex ecuter plusieurs programmes a ` la fois. Un processus est un programme en train de sex ecuter. La commande ps afche la liste des processus que vous avez lanc es. Chaque processus a un num ero. Cest la colonne PID cidessus. Le shell cr ee un nouveau processus pour ex ecuter chaque commande. Pour une commande normale (sans &), il attend que le processus termine, indiquant que la commande a ni de sex ecuter. Pour une commande en t ache de fond (avec &), le shell nattend pas. On peut interrompre (tuer) un processus avant la n, avec la commande kill -9 (plus le num ero du processus).

122
poly% poly% PID 4450 4851

ANNEXE B. UTILISATION AVANCEE DU SHELL

kill -9 4782 ps TT STAT TIME COMMAND p9 S 0:00 /usr/local/bin/tcsh p9 R 0:00 ps

Si on lance grosprogramme et quon a oubli e le &, ce nest pas grave : on commence par taper <Ctrl-Z> , puis bg pour mettre le programme en arri` ere-plan. Tant quon y est, si cest vraiment un gros programme qui tourne longtemps, il est conseill e de lui donner une priorit e faible par respect pour les autres utilisateurs, a ` laide de la commande nice. Par exemple, on lance (jamais de gros programmes sur poly svp !) :
coucou% nice ./grosprogramme > resultats &

qui permet de lancer le programme en t ache de fond, avec sortie des r esultats dans un chier, avec une faible priorit e.

B.2

Programmation

Le shell peut aussi ex ecuter des commandes prises dans un chier. Un chier contenant des commandes pour le shell est appel e un script. Cest en fait un programme e crit dans le langage du shell. Ce langage comprend non seulement les commandes que nous avons d ej` a vues, mais aussi des structures de contr ole (constructions conditionnelles et boucles). Il existe en fait plusieurs shells, ayant des langages de commandes diff erents. Jusquici, on a pris comme exemple le shell csh et sa variante tcsh. Pour la programmation du shell, nous allons utiliser le shell sh, qui a un meilleur langage de commandes. Notons quil existe plusieurs shells conviviaux, qui rajoutent des options a ` /bin/sh (cest le cas de bash). Ce que nous avons vu jusquici sapplique aussi bien a ` sh qu` a csh, a ` lexception de setenv et de certaines redirections. Pour e tre un script, un chier doit commencer par la ligne :
#!/bin/sh

Il doit aussi avoir le droit dex ecution (bit x). (Le #!/bin/sh sur la premi` ere ligne indique que ce script doit e tre ex ecut e par le shell sh.)

B.2.1

Structures de contr ole

for var in liste de cha nes ; do commandes ; done Affecte successivement a ` la variable de nom var chaque cha ne de caract` eres dans la liste de cha nes, et ex ecute les commandes une fois pour chaque cha ne. Rappel : $var acc` ede a ` la valeur courante de var. La partie commandes est une suite de commandes, s epar ees par des ; ou des retours a ` la ligne. (Tous les ; dans cette syntaxe peuvent aussi e tre remplac es par des retour a ` la ligne.) Exemple : for i in * ; do echo $i ; done afche tous les chiers du r epertoire courant, un par ligne. if commande ; then commandes ; else commandes ; fi Ex ecute lune ou lautre des listes de commandes, suivant que la premi` ere commande a r eussi ou non (voir ci-dessous). while commande ; do commande ; done Ex ecute les commandes de mani` ere r ep et ee tant que la premi` ere commande r eussit. case cha ne in pattern ) commande ; ; ... pattern ) commande ; ; esac Ex ecute la premi` ere commande telle que la cha ne est de la forme pattern. Un pattern

B.2. PROGRAMMATION

123

est un mot contenant e ventuellement les constructions *, ?, [a-d], avec la m eme signication que pour les raccourcis dans les noms de chiers. Exemple :
case $var in [0-9]* ) echo Nombre;; [a-zA-Z]* ) echo Mot;; * ) echo Autre chose;; esac

B.2.2

Code de retour

On remarque que la condition des commandes if et while est une commande. Chaque commande renvoie un code de retour (qui est ignor e en utilisation normale). Si le code est 0, la commande a r eussi ; sinon, la commande a e chou e. Par exemple, le compilateur cc renvoie un code derreur non nul si le chier compil e contient des erreurs, ou sil nexiste pas. Les commandes if et while consid` erent donc le code de retour 0 comme vrai, et tout autre code comme faux. Il existe une commande test, qui e value des expressions bool eennes pass ees en argument, et renvoie un code de retour en fonction du r esultat. Elle est bien utile pour les scripts. Exemple :
if test $var = foo then echo La variable vaut foo else echo La variable ne vaut pas foo fi

B.2.3

Variables

Dans les scripts, on peut utiliser des variables d enies a ` lext erieur (avec setenv), mais aussi d enir ses propres variables locales au script. On donne une valeur a ` une variable avec une commande de la forme nom-de-variable valeur. On a aussi des variables sp eciales, initialis ees automatiquement au d ebut du script : $* La liste de tous les arguments pass es au script. $# Le nombre darguments pass es au script. $1, $2, . . . Les arguments pass es au script. $? Le code de retour de la derni` ere commande lanc ee. $! Le num ero de process de la derni` ere commande en t ache de fond. $$ Le num ero de process du shell lui-m eme.

B.2.4

Commandes internes

Certaines commandes du shell ne sont pas des programmes mais des commandes internes. Elles sont directement reconnues et ex ecut ees par le shell. Un exemple de commande interne est cd. Cest le r epertoire courant du shell qui est modi e par cd, ce qui signie que le script suivant :
#! /bin/sh cd $1

ne marche pas, car le shell lance un autre shell pour ex ecuter le script. Cest ce sous-shell qui change son r epertoire courant, et ce changement est perdu quand le sous-shell meurt.

B.2.5

Fichier de d emarrage

Il existe un script sp ecial, qui est ex ecut e au moment o` u on se connecte. Ce script est contenu dans le chier $HOME/.login . Cest ce chier qui vous dit sil y a de nouveaux

124

ANNEXE B. UTILISATION AVANCEE DU SHELL

messages dans polyaf, si vous avez du courrier, etc . . .. Chacun peut ainsi personnaliser son environnement au d ebut de chaque session. On a quelques informations sur la customization en utilisant le menu Aide (bouton de droite de la souris sur fond d ecran).

B.3

Bibliographie Unix

wzyx wGx

w V x w x w x w x w x w x w x w x

wzE9x wzeyx

Utiliser Unix Steve Bourne, The Unix system, Addison-Wesley. Traduction franc aise : Le syst` eme Unix, Inter editions. Une vue densemble du syst` eme Unix. Les chapitres sur l edition et le traitement de texte sont d epass es. Programmer sous Unix Brian Kernighan, Rob Pike, The Unix programming environment, Addison-Wesley. Traduction franc aise : Lenvironnement de la programmation Unix, Inter editions. Une autre vue densemble du syst` eme Unix, plus orient ee vers la programmation en C et en shell. M. J. Bach, Conception du syst` eme UNIX. Prentice Hall, Masson, 1993. Jean-Marie Rifet, La programmation sous Unix. Programmation en C et en shell (pas mal). Traitement de texte AT X users guide and reference manual. Addison-Wesley, 1986. Tout Leslie Lamport, L E AT X. sur le traitement de texte L E Donald E. Knuth. The TEXbook. Addison-Wesley, 1984. Tout, absolument tout sur le AT X est en fait une extension de T X, un peu plus simple a traitement de texte TEX. L ` E E utiliser ; mais beaucoup de commandes sont communes aux deux, et non document es dans . Raymond Seroul. Le petit livre de TEX. Inter editions. Petit sous-ensemble de ; plus accessible, cependant. AT Xcompanion, Addison-Wesley. Une M. Goossens, F. Mittelbach, A. Samartin, The L E r ef erence. Le langage C Brian Kernighan, Dennis Ritchie, The C programming language, Prentice-Hall. Traduction franc aise : Le langage C, Inter editions. Le livre de r ef erence sur le langage C. Samuel Harbison, Guy Steele. C : a reference manual. Une autre bonne description du langage C. Utiliser le r eseau Brendan P. Kehoe, Zen and the art of the Internet A beginners guide to the Internet. (Non publi e.) Un exemplaire se trouve en salle Sun. Ed Krol, The whole Internet users guide & catalog, OReilly & Associates, 1992.

w x

Annexe C

Syntaxe BNF de Java

Ce qui suit est une syntaxe sous forme BNF (Backus Naur Form). Chaque petit paragraphe est la d enition souvent r ecursive dun fragment de syntaxe d enomm ee par un nom (malheureusement en anglais). Chaque ligne correspond a ` diff erentes d enitions possibles. Lindice optional sera mis pour signaler laspect facultatif de lobjet indic ee. Certains objets (token) seront suppos ee pr eed enis : IntegerLiteral pour une constante enti` ere, Identier pour tout identicateur, . . .La syntaxe du langage ne garantit pas la concordance des types, certaines phrases pouvant e tre syntaxiquement correctes, mais fausses pour les types.
Goal: CompilationUnit

C.1
Literal:

Contantes litt erales

IntegerLiteral FloatingPointLiteral BooleanLiteral CharacterLiteral StringLiteral NullLiteral

C.2
Type:

Types, valeurs, et variables

PrimitiveType ReferenceType

PrimitiveType: NumericType boolean NumericType: IntegralType FloatingPointType IntegralType: one of byte short int long char FloatingPointType: one of

125

126
float double ReferenceType: ClassOrInterfaceType ArrayType ClassOrInterfaceType: Name ClassType: ClassOrInterfaceType InterfaceType: ClassOrInterfaceType ArrayType: PrimitiveType [ ] Name [ ] ArrayType [ ]

ANNEXE C. SYNTAXE BNF DE JAVA

C.3
Name:

Noms
SimpleName QualiedName

SimpleName: Identier QualiedName: Name . Identier

C.4

Packages

CompilationUnit: PackageDeclarationopt ImportDeclarationsopt TypeDeclarationsopt ImportDeclarations: ImportDeclaration ImportDeclarations ImportDeclaration TypeDeclarations: TypeDeclaration TypeDeclarations TypeDeclaration PackageDeclaration: package Name ; ImportDeclaration: SingleTypeImportDeclaration TypeImportOnDemandDeclaration SingleTypeImportDeclaration: import Name ; TypeImportOnDemandDeclaration:

C.5. CLASSES
import Name . * ; TypeDeclaration: ClassDeclaration InterfaceDeclaration ; Modiers: Modier Modiers Modier Modier: one of public protected private static abstract final native synchronized transient volatile

127

C.5
C.5.1

Classes
D eclaration de classe

ClassDeclaration: Modiersopt class Identier Superopt Interfacesopt ClassBody Super: extends ClassType Interfaces: implements InterfaceTypeList InterfaceTypeList: InterfaceType InterfaceTypeList , InterfaceType ClassBody: ClassBodyDeclarationsopt

ClassBodyDeclarations: ClassBodyDeclaration ClassBodyDeclarations ClassBodyDeclaration ClassBodyDeclaration: ClassMemberDeclaration StaticInitializer ConstructorDeclaration ClassMemberDeclaration: FieldDeclaration MethodDeclaration

C.5.2

D eclarations de champs

FieldDeclaration: Modiersopt Type VariableDeclarators ; VariableDeclarators: VariableDeclarator

128
VariableDeclarators , VariableDeclarator VariableDeclarator: VariableDeclaratorId VariableDeclaratorId = VariableInitializer VariableDeclaratorId: Identier VariableDeclaratorId [ ] VariableInitializer: Expression ArrayInitializer

ANNEXE C. SYNTAXE BNF DE JAVA

C.5.3

D eclarations de m ethodes

MethodDeclaration: MethodHeader MethodBody MethodHeader: Modiersopt Type MethodDeclarator Throwsopt Modiersopt void MethodDeclarator Throwsopt MethodDeclarator: Identier ( FormalParameterListopt ) MethodDeclarator [ ] FormalParameterList: FormalParameter FormalParameterList , FormalParameter FormalParameter: Type VariableDeclaratorId Throws: throws ClassTypeList ClassTypeList: ClassType ClassTypeList , ClassType MethodBody: Block ;

C.5.4

Initialieurs statiques

StaticInitializer: static Block

C.5.5

D eclarations de constructeurs

ConstructorDeclaration: Modiersopt ConstructorDeclarator Throwsopt ConstructorBody ConstructorDeclarator: SimpleName ( FormalParameterListopt )

C.6. INTERFACES

129

ConstructorBody: ExplicitConstructorInvocationopt BlockStatementsopt

ExplicitConstructorInvocation: this ( ArgumentListopt ) ; super ( ArgumentListopt ) ;

C.6

Interfaces

InterfaceDeclaration: Modiersopt interface Identier ExtendsInterfacesopt InterfaceBody ExtendsInterfaces: extends InterfaceType ExtendsInterfaces , InterfaceType InterfaceBody: InterfaceMemberDeclarationsopt

InterfaceMemberDeclarations: InterfaceMemberDeclaration InterfaceMemberDeclarations InterfaceMemberDeclaration InterfaceMemberDeclaration: ConstantDeclaration AbstractMethodDeclaration ConstantDeclaration: FieldDeclaration AbstractMethodDeclaration: MethodHeader ;

C.7

Tableaux

ArrayInitializer: VariableInitializersopt ,opt

VariableInitializers: VariableInitializer VariableInitializers , VariableInitializer

C.8
Block:

Blocs et instructions

BlockStatementsopt

BlockStatements: BlockStatement BlockStatements BlockStatement BlockStatement: LocalVariableDeclarationStatement

130
Statement LocalVariableDeclarationStatement: LocalVariableDeclaration ; LocalVariableDeclaration: Type VariableDeclarators Statement: StatementWithoutTrailingSubstatement LabeledStatement BlockStatementsBlockStatementsIfThenStatement IfThenElseStatement WhileStatement ForStatement StatementNoShortIf: StatementWithoutTrailingSubstatement LabeledStatementNoShortIf IfThenElseStatementNoShortIf WhileStatementNoShortIf ForStatementNoShortIf StatementWithoutTrailingSubstatement: Block EmptyStatement ExpressionStatement SwitchStatement DoStatement BreakStatement ContinueStatement ReturnStatement SynchronizedStatement ThrowStatement TryStatement EmptyStatement: ; LabeledStatement: Identier : Statement LabeledStatementNoShortIf: Identier : StatementNoShortIf ExpressionStatement: StatementExpression ; StatementExpression: Assignment PreIncrementExpression PreDecrementExpression PostIncrementExpression PostDecrementExpression MethodInvocation ClassInstanceCreationExpression IfThenStatement:

ANNEXE C. SYNTAXE BNF DE JAVA

C.8. BLOCS ET INSTRUCTIONS

if ( Expression ) Statement IfThenElseStatement: if ( Expression ) StatementNoShortIf else Statement IfThenElseStatementNoShortIf: if ( Expression ) StatementNoShortIf else StatementNoShortIf SwitchStatement: switch ( Expression ) SwitchBlock SwitchBlock: SwitchBlockStatementGroupsopt SwitchLabelsopt

131

SwitchBlockStatementGroups: SwitchBlockStatementGroup SwitchBlockStatementGroups SwitchBlockStatementGroup SwitchBlockStatementGroup: SwitchLabels BlockStatements SwitchLabels: SwitchLabel SwitchLabels SwitchLabel SwitchLabel: case ConstantExpression : default : WhileStatement: while ( Expression ) Statement WhileStatementNoShortIf: while ( Expression ) StatementNoShortIf DoStatement: do Statement while ( Expression ) ; ForStatement: for ( ForInitopt ; Expressionopt ; ForUpdateopt ) Statement ForStatementNoShortIf: for ( ForInitopt ; Expressionopt ; ForUpdateopt ) StatementNoShortIf ForInit: StatementExpressionList LocalVariableDeclaration ForUpdate: StatementExpressionList StatementExpressionList: StatementExpression StatementExpressionList , StatementExpression BreakStatement:

132
break Identieropt ; ContinueStatement: continue Identieropt ; ReturnStatement: return Expressionopt ; ThrowStatement: throw Expression ; SynchronizedStatement: synchronized ( Expression ) Block TryStatement: try Block Catches try Block Catchesopt Finally Catches: CatchClause Catches CatchClause CatchClause: catch ( FormalParameter ) Block Finally: finally Block

ANNEXE C. SYNTAXE BNF DE JAVA

C.9
Primary:

Expressions
PrimaryNoNewArray ArrayCreationExpression

PrimaryNoNewArray: Literal this ( Expression ) ClassInstanceCreationExpression FieldAccess MethodInvocation ArrayAccess ClassInstanceCreationExpression: new ClassType ( ArgumentListopt ) ArgumentList: Expression ArgumentList , Expression ArrayCreationExpression: new PrimitiveType DimExprs Dimsopt new ClassOrInterfaceType DimExprs Dimsopt DimExprs: DimExpr DimExprs DimExpr

C.9. EXPRESSIONS

133

DimExpr: [ Expression ] Dims: [ ] Dims [ ] FieldAccess: Primary . Identier super . Identier MethodInvocation: Name ( ArgumentListopt ) Primary . Identier ( ArgumentListopt ) super . Identier ( ArgumentListopt ) ArrayAccess: Name [ Expression ] PrimaryNoNewArray [ Expression ] PostxExpression: Primary Name PostIncrementExpression PostDecrementExpression PostIncrementExpression: PostxExpression ++ PostDecrementExpression: PostxExpression -UnaryExpression: PreIncrementExpression PreDecrementExpression + UnaryExpression - UnaryExpression UnaryExpressionNotPlusMinus PreIncrementExpression: ++ UnaryExpression PreDecrementExpression: -- UnaryExpression UnaryExpressionNotPlusMinus: PostxExpression UnaryExpression ! UnaryExpression CastExpression CastExpression: ( PrimitiveType Dimsopt ) UnaryExpression ( Expression ) UnaryExpressionNotPlusMinus ( Name Dims ) UnaryExpressionNotPlusMinus MultiplicativeExpression:

134
UnaryExpression MultiplicativeExpression * UnaryExpression MultiplicativeExpression / UnaryExpression MultiplicativeExpression % UnaryExpression AdditiveExpression: MultiplicativeExpression AdditiveExpression + MultiplicativeExpression AdditiveExpression - MultiplicativeExpression ShiftExpression: AdditiveExpression ShiftExpression << AdditiveExpression ShiftExpression >> AdditiveExpression ShiftExpression >>> AdditiveExpression RelationalExpression: ShiftExpression RelationalExpression RelationalExpression RelationalExpression RelationalExpression RelationalExpression

ANNEXE C. SYNTAXE BNF DE JAVA

< ShiftExpression > ShiftExpression <= ShiftExpression >= ShiftExpression instanceof ReferenceType

EqualityExpression: RelationalExpression EqualityExpression == RelationalExpression EqualityExpression != RelationalExpression AndExpression: EqualityExpression AndExpression & EqualityExpression ExclusiveOrExpression: AndExpression ExclusiveOrExpression AndExpression InclusiveOrExpression: ExclusiveOrExpression InclusiveOrExpression | ExclusiveOrExpression ConditionalAndExpression: InclusiveOrExpression ConditionalAndExpression && InclusiveOrExpression ConditionalOrExpression: ConditionalAndExpression ConditionalOrExpression || ConditionalAndExpression ConditionalExpression: ConditionalOrExpression ConditionalOrExpression ? Expression : ConditionalExpression AssignmentExpression: ConditionalExpression Assignment Assignment:

C.9. EXPRESSIONS
LeftHandSide AssignmentOperator AssignmentExpression LeftHandSide: Name FieldAccess ArrayAccess AssignmentOperator: one of = *= /= %= += -= <<= >>= >>>= &= = |= Expression: AssignmentExpression ConstantExpression: Expression

135

Bibliographie Java

y lG lG

Exploring Java, 2nd edition, Pat Niemeyer et Joshua Peck 628 pages, OReilly, ISBN : 1-56592-271-9. 1997. The Java Language Specication, James Gosling, Bill Joy et Guy Steele, Addison Wesley, ISBN : 0-201-63456-2. 1996. Java in a Nutshell, David Flanagan, OReilly, ISBN : 1-56592-262-X, 1997. Java examples in a Nutshell, David Flanagan, OReilly, ISBN : 1-56592-371-5. 1997.

136

ANNEXE C. SYNTAXE BNF DE JAVA

Bibliographie
[1] Harold Abelson, Gerald J. Sussman, Structure and Interpretation of Computer Programs, MIT Press, 1985. [2] Adobe Systems Inc., PostScript Language, Tutorial and Cookbook, Addison Wesley, 1985. [3] Al V. Aho, Ravi Sethi, Jeff D. Ullman, Compilers : Principles, Techniques, and Tools, Addison Wesley, 1986. En franc ais : Compilateurs : principes, techniques et outils, trad. par Pierre Boullier, Philippe Deschamp, Martin Jourdan, Bernard Lorho, Monique Mazaud, InterEditions, 1989. [4] Henk Barendregt, The Lambda Calculus, Its Syntax and Semantics, North Holland, 1981. [5] Dani` ele Beauquier, Jean Berstel, Philippe Chr etienne, El ements dalgorithmique, Masson, Paris, 1992. [6] Jon Bentley, Programming Pearls, Addison Wesley, 1986. [7] Claude Berge, La th eorie des graphes et ses applications, Dunod, Paris, 1966. [8] Jean Berstel, Jean-Eric Pin, Michel Pocchiola, Math ematiques et Informatique, McGrawHill, 1991. [9] Noam Chomsky, Marcel Paul Sch utzenberger, The algebraic theory of context free languages dans Computer Programming and Formal Languages, P. Braffort, D. Hirschberg ed. North Holland, Amsterdam, 1963 [10] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Algorithms, MIT Press, 1990. [11] Patrick Cousot, Introduction a ` lalgorithmique et a ` la programmation, Ecole Polytechnique, Cours dInformatique, 1986. [12] Shimon Even, Graph Algorithms, Computer Science Press, Potomac, Md, 1979. [13] Adele Goldberg, Smalltalk-80 : the language and its implementation, Addison-Wesley 1983. [14] David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmeticc, Computing Surveys, 23(1), Mars 1991. [15] Gaston H. Gonnet, Riccardo Baeza-Yates, Handbook of Algorithms and Data Structures, In Pascal and C, Addison Wesley, 1991. [16] Mike J. C. Gordon, Robin Milner, Lockwood Morris, Malcolm C. Newey, Chris P. Wadsworth, A metalanguage for interactive proof in LCF, In 5th ACM Symposium on Principles of Programming Languages, 1978, ACM Press, New York. [17] Ron L. Graham, Donald E. Knuth, Oren Patashnik, Concrete mathematics : a foundation for computer science, Addison Wesley, 1989. [18] Samuel P. Harbison, Modula-3, Prentice Hall, 1992. [19] John H. Hennessy, David A. Patterson, Computer Architecture, A Quantitative Approach, Morgan Kaufmann Publishers, Inc. , 1990. 137

138

BIBLIOGRAPHIE

[20] Kathleen Jensen, Niklaus Wirth, PASCAL user manual and report : ISO PASCAL standard, Springer, 1991. (1` ere e dition en 1974). [21] Gerry Kane, Mips, RISC Architecture, MIPS Computer Systems, Inc., Prentice Hall, 1987. [22] Brian W. Kernighan, Dennis M.Ritchie, The C programming language, Prentice Hall, 1978. En franc ais : Le Langage C, trad. par Thierry Buffenoir, Manuels informatiques Masson, 8` eme tirage, 1990. [23] Brian W. Kernighan, PICa language for typesetting graphics, Software Practice & Experience 12 (1982), 1-20. [24] Dick B. Kieburtz, Structured Programming And Problem Solving With Algol W, Prentice Hall, 1975. [25] Stephen C. Kleene, Introduction to Metamathematics, North Holland, 6` eme e dition, 1971. (1` ere en 1952). [26] Donald E. Knuth, The TEXbook, Addison Wesley, 1984. [27] Donald E. Knuth, The Metafont book, Addison Wesley, 1986. [28] Donald E. Knuth, Fundamental Algorithms. The Art of Computer Programming, vol 1, Addison Wesley, 1968. [29] Donald E. Knuth, Seminumerical algorithms, The Art of Computer Programming, vol 2, Addison Wesley, 1969. [30] Donald E. Knuth, Sorting and Searching. The Art of Computer Programming, vol 3, Addison Wesley, 1973. A [31] Leslie Lamport, L TEX, Users guide & Reference Manual, Addison Wesley, 1986. [32] Butler W. Lampson et Ken A. Pier, A Processor for a High-Performance Personal Computer, Xerox Palo Alto Research Center Report CSL-81-1. 1981 (aussi dans Proceedings of Seventh Symposium on Computer Architecture, SigArch/IEEE, La Baule, Mai 1980, pp. 146160. [33] Jan van Leeuwen, Handbook of theoretical computer science, volumes A et B, MIT press, 1990. [34] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics, Cambridge University Press, 1983. [35] Udi Manber, Introduction to Algorithms, A creative approach, Addison Wesley, 1989 [36] Bob Metcalfe, D. Boggs, Ethernet : Distributed Packet Switching for Local Computer Networks, Communications of the ACM 19,7, Juillet 1976, pp 395404. [37] Robin Milner, A proposal for Standard ML, In ACM Symposium on LISP and Functional Programming, pp 184-197, 1984, ACM Press, New York. [38] Robin Milner, Mads Tofte, Robert Harper, The deniton of Standard ML, The MIT Press, 1990. [39] Greg Nelson, Systems Programming with Modula-3, Prentice Hall, 1991. [40] Eric Raymond, The New Hackers Dictionary, dessins de Guy L. Steele Jr., MIT Press 1991. [41] Brian Randell, L. J. Russel, Algol 60 Implementation, Academic Press, New York, 1964. [42] Martin Richards, The portability of the BCPL compiler, Software Practice and Experience 1 :2, pp. 135-146, 1971. [43] Martin Richards, Colin Whitby-Strevens, BCPL : The Language and its Compiler, Cambride University Press, 1979. [44] Denis M. Ritchie et Ken Thompson, The UNIX Time-Sharing System, Communications of the ACM, 17, 7, Juillet 1974, pp 365375 (aussi dans The Bell System Technical Journal, 57,6, Juillet-Aout 1978).

BIBLIOGRAPHIE

139

[45] Hartley Rogers, Theory of recursive functions and effective computability, MIT press, 1987, ( edition originale McGraw-Hill, 1967). [46] A. Sainte-Lagu e, Les r eseaux (ou graphes), M emoire des Sciences Math ematiques (18), 1926. [47] Bob Sedgewick, Algorithms, 2nd edition, Addison-Wesley, 1988. En franc ais : Algorithmes en langage C, trad. par Jean-Michel Moreau, InterEditions, 1991. [48] Ravi Sethi, Programming Languages, Concepts and Constructs, Addison Wesley, 1989. [49] Bjarne Stroustrup, The C++ Programming Language, Addison Wesley, 1986. [50] Robert E. Tarjan, Depth First Search and linear graph algorithms, Siam Journal of Computing, 1, pages 146-160, 1972. [51] Chuck P. Thacker, Ed M. McCreight, Butler W. Lampson, R. F. Sproull, D. R. Boggs, Alto : A Personal Computer, Xerox-PARC, CSL-79-11, 1979 (aussi dans Computer Structures : Readings and Examples, 2nd edition, par Siewoiorek, Bell et Newell). [52] Pierre Weis, The Caml Reference Manual, version 2-6.1, Rapport technique 121, INRIA, Rocquencourt, 1990. [53] Pierre Weis, Xavier Leroy, Le langage Caml, InterEditions, 1993.

Index
random, 67 spell, 54 e valuation dexpressions, 89 Divide and Conquer, 74, 75 Heapsort, 99 QuickDraw, 30 Quicksort, 72 heap, 96 Ackermann, 57 ajouter dans une le, 83 dans une liste, 78 al eatoire, 67 appel par valeur, 58 arbre, 95 impl ementation, 101 impression, 102 arbre binaire, 95 arbre de recherche, 104 arbres e quilibr es, 105 arbres 2-3, 108 arbres 2-3-4, 108 arbres AVL, 105 arbres bicolores, 109 rotations, 106 Bentley, 73 BNF Java, 125 bonjour, 9 break, 18 Caml, 139 cast, 12 catch, 29 cha nage, 78 cha ne de caract` eres, 31 collision, 49 commentaire, 9 compilation, 9 conversions explicites, 12 courbe du dragon, 62 140 dessins, 30 dragon, 62 ensembles, 77 Eratosth` ene, 81 factorielle, 55 feuille, 95 Fibonacci, 55 it eratif, 56 le, 82 dattente, 83 de priorit e, 96 gard ee, 85 vide, 83 finally , 30 ocon de von Koch, 60 fonction, 10 fonction 91, 57 fonction de Morris, 58 fractales, 60 fusion, 75 G odel, 58 graphique, 30 hachage, 49 adressage ouvert, 51 multiple, 53 Hanoi, 60 Hoare, 72 ind ecidable, 58 interclassement, 75 interface, 86 Kleene, 60 Koch, 60 liste, 77 des nombres premiers, 81 gard ee, 81 image miroir, 92 vide, 78 m ethode, 10

INDEX
MacCarthy, 57 main, 10 Maple, 7, 71 module, 86 Morris, 58 noeud, 95 noeud interne, 95 nombre al eatoire, 67 ordre inxe, 105 ordre postxe, 105 ordre pr exe, 105 pile, 86 postx ee notation, 88 r ecursivit e crois ee, 63 racine, 95 recherche dans une liste, 78 dichotomique, 47 en table, 46 par interpolation, 48 Rogers, 60 sentinelle, 46, 71 supprimer dans une le, 83 dans une liste, 80 dans une pile, 87 syntaxe Java, 125 tas, 96 TGiX, 30 throw, 29 throws, 30 tours de Hanoi, 60 tri borne inf erieure, 100 bulle, 67 fusion, 75 Heapsort, 99 insertion, 70 Quicksort, 72 s election, 65 Shell, 71 triangle de Pascal, 55 try, 29 Turing, 58

141

142

INDEX

Table des gures

6.1 6.2 6.3 7.1 7.2 7.3 8.1 8.2 8.3 8.4 9.1 9.2 9.3 9.4 Architecture du syst` eme UNIX. . . . . . . . . . . . . . . . . . . . . . . . . . 36 Structure bloc dun chier. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Diagramme de transition d etats. . . . . . . . . . . . . . . . . . . . . . . . . . 41 Un exemple de table pour la recherche en table . . . . . . . . . . . . . . . . . 46 Hachage par collisions s epar ees . . . . . . . . . . . . . . . . . . . . . . . . . 50 Hachage par adressage ouvert . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Appels r ecursifs pour fib . . Les tours de Hanoi . . . . . . . Flocons de von Koch . . . . . . La courbe du Dragon . . . . . . Exemple de tri par s election Exemple de tri bulle . . . . . Exemple de tri par insertion . Partition de Quicksort . . . . . . . . . . . .

. . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56 61 62 63 66 68 70 73 78 79 84 86 89 91 91 92 92 93 95 96 97 97 98 98 101 105 106 107 109 110 110

10.1 Ajout dun e l ement dans une liste . . . . . . . . . . . . 10.2 Suppression dun e l ement dans une liste . . . . . . . . . 10.3 File g er ee par un tableau circulaire . . . . . . . . . . . . 10.4 File dattente impl ement ee par une liste . . . . . . . . . 10.5 Pile d evaluation de lexpression dont le r esultat est 1996 10.6 Queue dune liste . . . . . . . . . . . . . . . . . . . . . 10.7 Concat enation de deux listes par Append . . . . . . . . . 10.8 Concat enation de deux listes par Nconc . . . . . . . . . 10.9 Transformation dune liste au cours de nReverse . . . . . 10.10Liste circulaire gard ee . . . . . . . . . . . . . . . . . . .

11.1 Un exemple darbre . . . . . . . . . . . . . . . . . . . . . 11.2 Repr esentation dune expression arithm etique par un arbre 11.3 Repr esentation en arbre dun tas . . . . . . . . . . . . . . 11.4 Repr esentation en tableau dun tas . . . . . . . . . . . . . 11.5 Ajout dans un tas . . . . . . . . . . . . . . . . . . . . . . 11.6 Suppression dans un tas . . . . . . . . . . . . . . . . . . . 11.7 Exemple darbre de d ecision pour le tri . . . . . . . . . . . 11.8 Ajout dans un arbre de recherche . . . . . . . . . . . . . . 11.9 Rotation dans un arbre AVL . . . . . . . . . . . . . . . . 11.10Double rotation dans un arbre AVL . . . . . . . . . . . . . 11.11Exemple darbre 2-3-4 . . . . . . . . . . . . . . . . . . . 11.12Eclatement darbres 2-3-4 . . . . . . . . . . . . . . . . . . 11.13Arbres bicolores . . . . . . . . . . . . . . . . . . . . . . .

143

Vous aimerez peut-être aussi

Langage C
Pas encore d'évaluation
Langage C
209 pages
Programmer C++
100% (1)
Programmer C++
287 pages
Langage C - Diapos
Pas encore d'évaluation
Langage C - Diapos
40 pages
Support de Cours de Langage C
Pas encore d'évaluation
Support de Cours de Langage C
236 pages
Les Bibliothèques en Python
100% (1)
Les Bibliothèques en Python
7 pages
CSharp Base PDF
Pas encore d'évaluation
CSharp Base PDF
25 pages
Isi1 PDF
Pas encore d'évaluation
Isi1 PDF
213 pages
Exercices Bash pour Débutants
Pas encore d'évaluation
Exercices Bash pour Débutants
9 pages
Autocad Guide
Pas encore d'évaluation
Autocad Guide
35 pages
DAO Communication Graphique1
Pas encore d'évaluation
DAO Communication Graphique1
115 pages
COURS Alg2 21-22 ENSAO
Pas encore d'évaluation
COURS Alg2 21-22 ENSAO
66 pages
Python Tres Facile Preview
Pas encore d'évaluation
Python Tres Facile Preview
43 pages
Liste de Commande Autocad
Pas encore d'évaluation
Liste de Commande Autocad
6 pages
Guide SQL Université Nice v5.4.5
Pas encore d'évaluation
Guide SQL Université Nice v5.4.5
101 pages
Cours Analyse 1: Théorie et Applications
Pas encore d'évaluation
Cours Analyse 1: Théorie et Applications
130 pages
Autocad 2018 Manu
Pas encore d'évaluation
Autocad 2018 Manu
22 pages
TP2 Corrigé
Pas encore d'évaluation
TP2 Corrigé
12 pages
Lobna KRIAA
Pas encore d'évaluation
Lobna KRIAA
62 pages
Python M Cours
Pas encore d'évaluation
Python M Cours
19 pages
Introduction aux Ontologies : RDFS, OWL, Inférences
Pas encore d'évaluation
Introduction aux Ontologies : RDFS, OWL, Inférences
38 pages
PGCD Sous Algobox Par Algorithme D'euclide
Pas encore d'évaluation
PGCD Sous Algobox Par Algorithme D'euclide
1 page
Cours Python 3
100% (2)
Cours Python 3
155 pages
Programmation AutoLISP pour M2 GCI
Pas encore d'évaluation
Programmation AutoLISP pour M2 GCI
46 pages
Simulation Numérique avec ANSYS
Pas encore d'évaluation
Simulation Numérique avec ANSYS
95 pages
M135 - Archive
Pas encore d'évaluation
M135 - Archive
56 pages
Introduction aux Bases du C#
Pas encore d'évaluation
Introduction aux Bases du C#
54 pages
Introduction au Fortran pour Physiciens
Pas encore d'évaluation
Introduction au Fortran pour Physiciens
46 pages
Cours 2
Pas encore d'évaluation
Cours 2
6 pages
C-Sharp L-Essentiel Du Code Et Des Classes
Pas encore d'évaluation
C-Sharp L-Essentiel Du Code Et Des Classes
364 pages
02 Guide App Initia
Pas encore d'évaluation
02 Guide App Initia
18 pages
4 - Les Familles Revit - Bases
Pas encore d'évaluation
4 - Les Familles Revit - Bases
9 pages
Étudier au Québec : Choix et Opportunités
Pas encore d'évaluation
Étudier au Québec : Choix et Opportunités
6 pages
Introduction Au Python
Pas encore d'évaluation
Introduction Au Python
11 pages
02 Applications Et Fonctions
Pas encore d'évaluation
02 Applications Et Fonctions
7 pages
Tuto-Catia V5-Pot de Confiture
Pas encore d'évaluation
Tuto-Catia V5-Pot de Confiture
32 pages
Initiation A Matlab
100% (1)
Initiation A Matlab
75 pages
TP Informatique (Matlab)
Pas encore d'évaluation
TP Informatique (Matlab)
6 pages
Ext 1255 8
Pas encore d'évaluation
Ext 1255 8
481 pages
Liste Livres
Pas encore d'évaluation
Liste Livres
30 pages
Chap 3 Excel Solver Pour Résoudre Des Programmes Linéaires
Pas encore d'évaluation
Chap 3 Excel Solver Pour Résoudre Des Programmes Linéaires
10 pages
Langage C & C++ Chap 6
Pas encore d'évaluation
Langage C & C++ Chap 6
30 pages
Chapitre 3 Les Fonctions Python
100% (2)
Chapitre 3 Les Fonctions Python
13 pages
Vi Memento FR
Pas encore d'évaluation
Vi Memento FR
2 pages
Initiation au VBA pour Excel
Pas encore d'évaluation
Initiation au VBA pour Excel
32 pages
Avant Propos Lacomme PDF
Pas encore d'évaluation
Avant Propos Lacomme PDF
6 pages
Matlab Insa LYON
Pas encore d'évaluation
Matlab Insa LYON
78 pages
Polyx2010 Java PDF
Pas encore d'évaluation
Polyx2010 Java PDF
252 pages
Algo en Java
100% (1)
Algo en Java
255 pages
Introduction à Java pour Débutants
Pas encore d'évaluation
Introduction à Java pour Débutants
189 pages
Introduction à Java et Programmation
Pas encore d'évaluation
Introduction à Java et Programmation
189 pages
MR David Célestin FAYE Cours D'algorithmique I Programmation I-1
100% (1)
MR David Célestin FAYE Cours D'algorithmique I Programmation I-1
209 pages
Algorithmique Isig 2025
Pas encore d'évaluation
Algorithmique Isig 2025
76 pages
Langage CCCC
Pas encore d'évaluation
Langage CCCC
222 pages
Programmation C et Algorithmique
Pas encore d'évaluation
Programmation C et Algorithmique
198 pages
Introduction à Java pour Débutants
Pas encore d'évaluation
Introduction à Java pour Débutants
179 pages
Fortran90 PDF PDF
Pas encore d'évaluation
Fortran90 PDF PDF
73 pages
Inf3105 Notes PDF
Pas encore d'évaluation
Inf3105 Notes PDF
132 pages
Cours - Chapitre I
Pas encore d'évaluation
Cours - Chapitre I
24 pages
Cours5tti Pascal
Pas encore d'évaluation
Cours5tti Pascal
254 pages
Info CH 1 2
Pas encore d'évaluation
Info CH 1 2
65 pages
Offre de Service Gestion de Trésorerie
Pas encore d'évaluation
Offre de Service Gestion de Trésorerie
3 pages
Bases de Données Relationnelles
Pas encore d'évaluation
Bases de Données Relationnelles
236 pages
Bases de Données Relationnelles
Pas encore d'évaluation
Bases de Données Relationnelles
236 pages
Les Différents Types de Câbles
Pas encore d'évaluation
Les Différents Types de Câbles
5 pages
Analyse Merise : Concepts et Cas Pratique
100% (1)
Analyse Merise : Concepts et Cas Pratique
32 pages
1 Concepts Fondamentaux
Pas encore d'évaluation
1 Concepts Fondamentaux
28 pages
Module 13: Techniques de Programmation Structurée
83% (12)
Module 13: Techniques de Programmation Structurée
75 pages
CPU928A 6ES5998-1PR31 (F) OCR
Pas encore d'évaluation
CPU928A 6ES5998-1PR31 (F) OCR
458 pages
La Programmation en Langage C
100% (2)
La Programmation en Langage C
190 pages
DSP
Pas encore d'évaluation
DSP
62 pages
Algorithmes et Structures de Données
Pas encore d'évaluation
Algorithmes et Structures de Données
63 pages
Pfe Ascenceur
64% (14)
Pfe Ascenceur
90 pages
IDRIS Fortran Cours
Pas encore d'évaluation
IDRIS Fortran Cours
129 pages
99 Java Intro
Pas encore d'évaluation
99 Java Intro
100 pages
Cours Sur Le Langage C PDF
Pas encore d'évaluation
Cours Sur Le Langage C PDF
22 pages
Protocole I2C avec PIC16F877
Pas encore d'évaluation
Protocole I2C avec PIC16F877
75 pages
Cours Automate Scheinder TSX2-2-2
Pas encore d'évaluation
Cours Automate Scheinder TSX2-2-2
12 pages
Ch5 Structure de Controle Itératives
Pas encore d'évaluation
Ch5 Structure de Controle Itératives
11 pages
LeÃ On 2
Pas encore d'évaluation
LeÃ On 2
6 pages
Cours 1
Pas encore d'évaluation
Cours 1
79 pages
Bases de Données BTS
67% (6)
Bases de Données BTS
64 pages
Programmation des PIC avec MPLAB
Pas encore d'évaluation
Programmation des PIC avec MPLAB
5 pages
Cours Microcont Microprocesseur Uvt Version Envoyeewith Hkoubeib Tahenti Ingénieur
100% (2)
Cours Microcont Microprocesseur Uvt Version Envoyeewith Hkoubeib Tahenti Ingénieur
134 pages
Annexe Jeu Dinstructions Du 8086
Pas encore d'évaluation
Annexe Jeu Dinstructions Du 8086
29 pages
Algorithmique BTS : Cours et Exercices
Pas encore d'évaluation
Algorithmique BTS : Cours et Exercices
27 pages
Pic16f876 Omnad
Pas encore d'évaluation
Pic16f876 Omnad
80 pages
Architecture et Fonctionnement du Microprocesseur Intel 8086
Pas encore d'évaluation
Architecture et Fonctionnement du Microprocesseur Intel 8086
15 pages
Unité Centrale de Traitement
Pas encore d'évaluation
Unité Centrale de Traitement
31 pages
API
Pas encore d'évaluation
API
9 pages
Introduction au Microprocesseur
Pas encore d'évaluation
Introduction au Microprocesseur
18 pages
Sam1a Coursv11
Pas encore d'évaluation
Sam1a Coursv11
66 pages
Conception Serrure Codee PDF
100% (1)
Conception Serrure Codee PDF
76 pages
Le Langage C
100% (1)
Le Langage C
152 pages
Les Secrets de La Programmation
Pas encore d'évaluation
Les Secrets de La Programmation
99 pages
DS Arci Avancee 2011 Corrigé
0% (1)
DS Arci Avancee 2011 Corrigé
4 pages

Base Programmation

Transféré par

Base Programmation

Transféré par

Les bases de la programmation et de lalgorithmique

Franc ois Morain

Table des mati` eres

TABLE DES MATIERES

TABLE DES MATIERES

TABLE DES MATIERES

TABLE DES MATIERES

Polycopi e, version 1.0

Les premiers pas en Java

CHAPITRE 1. LES PREMIERS PAS EN JAVA

Faire des calculs simples

1.3. TYPES PRIMITIFS

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

CHAPITRE 1. LES PREMIERS PAS EN JAVA

CHAPITRE 1. LES PREMIERS PAS EN JAVA

Expressions bool eennes

CHAPITRE 2. SUITE DINSTRUCTIONS

" $#%%& et " '(#)&

sont disjoints ou contenus lun

It erations boucles pour

2.4. ITERATIONS TANT QUE

It erations tant que

Une telle instruction a la forme suivante :

CHAPITRE 2. SUITE DINSTRUCTIONS

Instructions de rupture de contr ole

2.5. INSTRUCTIONS DE RUPTURE DE CONTROLE

CHAPITRE 2. SUITE DINSTRUCTIONS

Tableaux et cha nes de caract` eres

D eclaration et construction de tableaux

CHAPITRE 3. TABLEAUX ET CHAINES DE CARACTERES

int[] tab = {1,2,4,8,16,32,64,128,256,512,1024};

` plusieurs dimensions, matrices Tableaux a

3.4. CHAINES DE CARACTERES

Cha nes de caract` eres

CHAPITRE 3. TABLEAUX ET CHAINES DE CARACTERES

Composants dune classe

CHAPITRE 4. COMPOSANTS DUNE CLASSE

Constantes et variables globales

Les classes pour d enir des enregistrements

4.5. LES METHODES STATIQUES ET LES AUTRES

Les m ethodes statiques et les autres

CHAPITRE 4. COMPOSANTS DUNE CLASSE

Utiliser plusieurs classes

Ainsi on peut e crire en se servant de deux constructeurs de la classe Exception :

Et les fonctions correspondantes (voir page 31)

Toutes ces d enitions sont aussi sur poly dans le chier

Principes de base des syst` emes Unix

La premi` ere version (0.01) a e t e diffus ee en ao ut 1991.

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

Le syst` eme de chiers

6.3. LES PROCESSUS

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

TAB . 6.1 R esultat de la commande ps ax.

6.3. LES PROCESSUS

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

6.3. LES PROCESSUS

sendort se r eveille 4. endormi

F IG . 6.3 Diagramme de transition d etats.

Lordonnancement des t aches

unix% nice -19 ./toto &

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

Le myst` ere du d emarrage

6.4. GESTION DES FLUX

CHAPITRE 6. PRINCIPES DE BASE DES SYSTEMES UNIX

Complexit e des algorithmes

VqBuwvexy1D 1 VBt1D VBt1uwvex1D 1 VBt1iD VqBt1ED VqBt1D

46 nom paul roger laure anne pierre yves

CHAPITRE 7. RETROUVER LINFORMATION

qui peut aussi s ecrire

7.2. RECHERCHE EN TABLE

CHAPITRE 7. RETROUVER LINFORMATION

static int rechercheDichotomique (String x) { int i, g, d, cmp;

d eqp wu vex BrD d esp AW

dfe S hgidkj eml on uwvex

Insertion dans une table

7.2. RECHERCHE EN TABLE

" $#%%& et " '(#)&

VqBuwvexy1D 1 VBt1D VBt1uwvex1D 1 VBt1iD VqBt1ED VqBt1D

d eqp wu vex BrD d esp AW

x f S9X "xtB fyD& f$

" 0F& S VBwGD

gU BFBw!`DID gU BFBw!`D D S

xBtfyDg xmBtfDgv xS Btfy D gv q y S h TP

Bw `DpYRuwvexBw Bw!DID Bwp!D S heh 1

x Btf#)FD S m d RBtf" &yvdD f x x S d TP

mgv 2 r g 2 S S 1 1 Y Bt1Dti Bt1GD

B T #I1D Bw#I1D BF#I1D BF#I1D

1q k B#I)D Btm#ID S S Btfg@D gBtsvgD Btgg)D BkrfyD

BF T #% T % # T #%e T #%e T D

#) #EEEG#) e e

G H U q D FGDC R H Q P ( S U4I E DFGDC I R

EEE UT WV i V EEE V i EEE Xi T V V T a` Y u b`