Université de Provence (Aix-Marseille I)
Eléments d’algorithmique en Java
Solange COUPET-GRIMAL
Ce cours s’adresse à des débutants. Les notions essentielles de programmation y sont introduites de fac¸on volontairement non exhaustive, dans le but de favoriser une acquisition correcte, rapide et intuitive des concepts fondamentaux nécessaires à la mise en œuvre en Java des algorithmes étudiés par la suite.
I Pour débuter rapidement en Java 1
1 Fondements 3
1.1 Représentation des données en machine . . .. . .. . .. . . 4
1.1.1 La mémoire . . .. . .. . .. . .. . .. 4
1.1.2 Codage en mémoire d’une donnée : présentation informelle . . .. . 4
1.1.3 Types simples et chaˆ?nes de caractères . . .. . .. . . . . . . 6
1.2 Les variables et l’affectation . . .. . .. . .. . .. . . 7
1.2.1 Déclaration de variable . . .. . .. . .. . .. 7
1.2.2 Affectation . . .. . .. . .. . .. . .. 8
1.2.3 Déclaration avec initialisation . . .. . .. . .. . . . . 8
1.2.4 Signification du nom de la variable . . .. . .. . .. . 8
1.2.5 Optimisations d’affectations . . .. . .. . .. . . . . . 9
1.2.6 Retour sur les types simples : conversions . . .. . .. . . . . 9
1.3 Instructions et expressions . . .. . .. . .. . .. . . . 10
1.3.1 L’affectation comme expression . . .. . .. . .. . . . 10
1.3.2 Cas particulier : incrémentations et décrémentations . . .. . . . . . 11
1.3.3 Expressions à effet de bord . . .. . .. . .. . . . . . 11
1.4 Blocs et boucles . . .. . .. . .. . .. . .. . . 11
1.4.1 Blocs . . .. . .. . .. . .. . .. . . . 12
1.4.2 Les instructions de branchement . . .. . .. . .. . . 12
1.4.3 Instructions while et do-while . . .. . .. . .. . . . . 14
1.4.4 Instruction for . . .. . .. . .. . .. . . . . . 15
2 Java sans objet 19
2.1 Programme minimum . . .. . .. . .. . .. . . . . . 19
2.1.1 La méthode main . . .. . .. . .. . .. . . . . 19
2.1.2 Les arguments d’un programme . . .. . .. . .. . . . 20
2.2 Les méthodes de classes (ou statiques) . . .. . .. . .. . . . 21
2.2.1 Etude d’un exemple . . .. . .. . .. . .. . . 21
2.2.2 Commentaires dans un programme . . .. . .. . .. . 22
2.2.3 Nombres en argument de programme . . .. . .. . .. 22
2.2.4 Radiographie de la méthode pgcd . . .. . .. . .. . . 22
2.2.5 Comment ¸ca marche? . . .. . .. . .. . .. . 23
2.2.6 Passage des paramètres par valeur . . .. . .. . .. . 24
2.2.7 Couˆt d’un appel de méthode . . .. . .. . .. . . . . 24
2.2.8 L’instruction return . . .. . .. . .. . .. . . 25
2.3 Modularité . . .. . .. . .. . .. . .. . . . . 25
2.4 Conclusion provisoire . . .. . .. . .. . .. . . . . . . 26
iii
iv TABLE DES MATIERES`
3 Les objets 27
3.1 Classes comme structures de données . . .. . .. . .. . . . . 27
3.1.1 Qu’est ce qu’un objet? . . .. . .. . .. . .. . 27
3.1.2 Définir les classes d’objets . . .. . .. . .. . . . . . . 27
3.1.3 Créer des objets . . .. . .. . .. . .. . . . . 29
3.2 Classes comme boˆ?tes à outils sécurisées . . .. . .. . .. . . 31
3.2.1 Méthodes d’instance . . .. . .. . .. . .. . . 31
3.2.2 Privatisation des champs . . .. . .. . .. . . . . . . 32
3.2.3 La méthode toString . . .. . .. . .. . .. . . 33
3.3 Variables statiques et constantes . . .. . .. . .. . . . . . . 34
3.3.1 this implicite . . .. . .. . .. . .. . .36
4 Les tableaux 37
4.1 Tableaux à une dimension . . .. . .. . .. . .. . . . 37
4.1.1 Déclarations . . .. . .. . .. . .. . .. 37
4.1.2 Création . . .. . .. . .. . .. . .. . . 37
4.1.3 Taille et indexation d’un tableau . . .. . .. . .. . . 38
4.1.4 Couˆt des accès . . .. . .. . .. . .. . . . . . 38
4.1.5 Tableaux d’objets . . .. . .. . .. . .. . . . 39
4.2 Tableaux à plusieurs dimensions . . .. . .. . .. . . . . . . 39
4.2.1 Déclaration et création . . .. . .. . .. . .. . 39
4.2.2 Couˆt des accès . . .. . .. . .. . .. . . . . . 41
4.3 Effet du codage sur l’occupation mémoire . . .. . .. . .. . 41
4.3.1 Puissance égyptienne . . .. . .. . .. . .. . . 42
4.3.2 Puissance d’une matrice . . .. . .. . .. . .. 42
II Eléments d’algorithmique 47
5 Principes généraux 49
5.1 Qu’est-ce qu’un algorithme? . . .. . .. . .. . .. . . 49
5.1.1 Définition informelle . . .. . .. . .. . .. . . 49
5.1.2 Les grandes questions de la calculabilité . . .. . .. . . . . . 49
5.1.3 Le problème de l’arrêt . . .. . .. . .. . .. . 50
5.1.4 Pour conclure . . .. . .. . .. . .. . . . . . . 52
5.2 Conception et expression d’algorithmes . . .. . .. . .. . . . 53
5.2.1 Spécification du problème . . .. . .. . .. . . . . . . 53
5.2.2 Analyse descendante - Modularité . . .. . .. . .. . 53
5.2.3 Correction de l’algorithme . . .. . .. . .. . . . . . . 54
5.3 Algorithmes récursifs . . .. . .. . .. . .. . . . . . . 56
5.3.1 Introduction sur des exemples . . .. . .. . .. . . . . 56
5.3.2 Terminaison des algorithmes récursifs . . .. . .. . . . . . . 58
5.3.3 Correction des algorithme récursifs . . .. . .. . .. . 60
5.4 Complexité . . .. . .. . .. . .. . .. . . . . 61
5.4.1 Couˆt et complexité en temps d’un algorithme . . .. . .. . . 62
5.4.2 Asymptotique . . .. . .. . .. . .. . . . . . . 65
6 Structures séquentielles 75
6.1 Les listes . . .. . .. . .. . .. . .. . . . . . . 75
6.1.1 Description abstraite . . .. . .. . .. . .. . . 75
6.1.2 Mise en œuvre par des tableaux . . .. . .. . .. . . . 76
6.1.3 Mise en œuvre par des listes chaˆ?nées . . .. . .. . . . . . . 80
6.1.4 Cas des listes ordonnées . . .. . .. . .. . .. 84
6.1.5 Tableaux ou listes chaˆ?nées? . . .. . .. . .. . . . . 88
TABLE DES MATIERES` v
6.2 Les piles . . .. . .. . .. . .. . .. . . . . . . 89
6.2.1 Description abstraite . . .. . .. . .. . .. . . 89
6.2.2 Application à la fonction d’Ackermann . . .. . .. . .89
6.2.3 Mise en œuvre par des tableaux . . .. . .. . .. . . . 91
6.2.4 Mise en œuvre par des listes chaˆ?nées . . .. . .. . . . . . . 92
6.2.5 Application à la fonction d’Ackermann . . .. . .. . .93
6.3 Les files d’attente . . .. . .. . .. . .. . .. . 93
6.3.1 Description abstraite . . .. . .. . .. . .. . . 93
6.3.2 Mise en œuvre par des tableaux . . .. . .. . .. . . . 94
6.3.3 Mise en œuvre par des listes chaˆ?nées . . .. . .. . . . . . . 96
6.4 Exercices . . .. . .. . .. . .. . .. . . . . . 98
7.1 Présentation informelle . . .. . .. . .. . .. . . . . . 101
7.2 Les arbres binaires . . .. . .. . .. . .. . .. 102
7.2.1 Description abstraite . . .. . .. . .. . .. . . 102
7.2.2 Les divers parcours d’arbres binaires . . .. . .. . .. 103
7.2.3 Mise en œuvre en Java . . .. . .. . .. . .. . 106
7.3 Arbres binaires de recherche (ABR) . . .. . .. . .. . . . . 107
7.3.1 Recherche . . .. . .. . .. . .. . .. . 108
7.3.2 Adjonction aux feuilles . . .. . .. . .. . .. . 108
7.3.3 Adjonction à la racine . . .. . .. . .. . .. . 109
7.3.4 Suppression . . .. . .. . .. . .. . .. 111
7.4 Complexité des opérations sur les ABR . . .. . .. . .. . . . 113
7.4.1 Instruments de mesure sur les arbres . . .. . .. . .. 113
7.4.2 Arbres aléatoires de recherche (ABRn) . . .. . .. . .115
7.4.3 Profondeur moyenne des nœuds dans ABRn . . .. . .. . . 118
7.4.4 Profondeur moyenne des feuilles des ABRn . . .. . .. . . . 120
7.4.5 Conclusion . . .. . .. . .. . .. . .. 123
7.5 Arbres binaires parfaits partiellement ordonnés (Tas) . . .. . .. . . 124
7.5.1 Codage d’un arbre binaire parfait . . .. . .. . .. . . 124
7.5.2 Tas . . .. . .. . .. . .. . .. . . . . . 125
7.5.3 Suppression du minimum d’un tas . . .. . .. . .. . 125
7.5.4 Transformation d’une liste en tas . . .. . .. . .. . . 127
7.5.5 Adjonction d’un élément à un tas . . .. . .. . .. . . 128
7.5.6 Application : Tri par Tas . . .. . .. . .. . .129
7.6 Les arbres quelconques . . .. . .. . .. . .. . . . . . 130
7.6.1 Description abstraite . . .. . .. . .. . .. . . 130
7.6.2 Parcours d’arbres quelconques . . .. . .. . .. . . . 131
7.6.3 Mise en œuvre en Java de la structure d’arbre quelconque . . .. . . 135
8.1 Présentation informelle . . .. . .. . .. . .. . . . . . 137
8.2 Terminologie . . .. . .. . .. . .. . .. . . . 138
8.3 Parcours de graphes . . .. . .. . .. . .. . .140
8.3.1 Parcours en profondeur . . .. . .. . .. . .. 141
8.3.2 Parcours en largeur . . .. . .. . .. . .. . . 142
8.4 Représentations des graphes . . .. . .. . .. . .. . . 143
8.4.1 Les matrices d’adjacence . . .. . .. . .. . .. 143
8.4.2 Les listes d’adjacence . . .. . .. . .. . .. . 145
8.5 Graphes orientés acycliques (dag) . . .. . .. . .. . .147
8.5.1 Tri topologique . . .. . .. . .. . .. . . . . . 148
8.5.2 Décomposition par niveaux . . .. . .. . .. . . . . . 149
8.6 Recherche de plus courts chemins dans un graphe valué . . .. . .. 150
vi TABLE DES MATIERES`
8.6.1 L’algorithme de Dijkstra . . .. . .. . .. . .. 150
8.6.2 Correction de l’algorithme . . .. . .. . .. . .151
8.6.3 Complexité . . .. . .. . .. . .. . .. 153
8.6.4 Une mise en œuvre de l’algorithme en Java . . .. . .. . . . 154
9.1 Tris élémentaires . . .. . .. . .. . .. . .. . 159
9.1.1 Le tri par sélection . . .. . .. . .. . .. . . . 159
9.1.2 Le tri par insertion . . .. . .. . .. . .. . . . 160
9.2 Tri rapide . . .. . .. . .. . .. . .. . . . . . 160 9.3 Tri fusion . . .. . .. . .. . .. . .. . . . . . 166 9.4 Tri par tas . . .. . .. . .. . .. . .. . . . . . 167
9.5 Complexité du problème du tri . . .. . .. . .. . .. 167
9.6 Complexité des algorithmes diviser pour régner . . .. . .. . . . . . 168
9.7 Exercices . . .. . .. . .. . .. . .. . . . . . 169
Première partie
Pour débuter rapidement en Java
Chapitre 1 Fondements
Un ordinateur est constitué de divers modules :
– le processeur qui évalue des expressions (effectue des calculs) et qui exécute des instructions
– la mémoire dans laquelle sont enregistrées les informations (les programmes, les données et les résultats de calculs effectués sur ces dernières)
– les périphériques, dont le clavier, l’écran, les imprimantes, le disque dur, les réseaux Ces divers constituants communiquent entre eux au moyen de canaux appelés bus.
Figure 1.1 – structure d’un ordinateur
Instructions et expressions Les programmes sont amenés à modifier l’état de la mémoire (en y enregistrant des résultats par exemple) au moyen d’instructions. Dans la suite de ce document, on appellera effet de bord toute action du processeur provoquant un changement de l’état de la mémoire (on dira désormais un changement d’état sans plus de précision). Une instruction a donc, sauf exception, un effet de bord.
Ils font également effectuer par le processeur des calculs codés sous forme d’expressions. Par exemple, 2*3+2 et 5>8 sont des expressions que le processeur peut évaluer pour produire 8 et false respectivement. L’évaluation de ces deux expressions ne modifie pas l’état de mémoire. Elles sont sans effet de bord.
Les programmes prennent en compte des données pour produire des résultats. Données et résultats peuvent être de types simples (entiers, flottants, caractères, booléens) ou structurés (chaˆ?nes de caractères, tableaux, dictionnaires, fiches clients ). Avant de s’intéresser à la fac¸on dont les programmes sont exécutés par le processeur et à leurs effets, il convient donc de bien comprendre comment les données et les résultats sont codés dans la mémoire.
1.1 Représentation des données en machine
La mémoire d’un ordinateur est une suite ordonnée de bits. Un bit est un composant élémentaire, pouvant prendre deux états et deux seulement, communément notés 0 et 1, tout comme un interrupteur électrique n’a que deux positions : éteint et allumé. Les bits de la mémoire sont regroupés par huit : un groupe de huit bits est un octet (byte en anglais).
Figure 1.2 – Une zone mémoire de 4 octets
Enfin, bits et octets sont numérotés. Ce numéro d’ordre est appelé adresse (du bit ou de l’octet).
La figure 1.2 représente une zone de la mémoire constituée des quatre octets d’adresses respectives 64, 72, 80, 88.
L’état de la mémoire est la suite des états (0 ou 1) des bits qui la composent. L’état de la zone mémoire représentée sur la figure 1.2 est donc :
00000000000000000000000001100001
attention! Tout comme un interrupteur est toujours dans une des deux positions “éteint” ou “allumé”, une zone mémoire est toujours dans un certain état. Il est donc absurde de dire qu’il n’y a rien dans une zone mémoire.
Toute donnée, aussi complexe soit-elle, est donc représentée in fine par une suite binaire. Inversement, il faut être capable de décoder une suite binaire pour retrouver la donnée qu’elle représente. Examinons tout d’abord les données de type simple.
En ce qui concerne les entiers, une idée naturelle est de les représenter par leur développement en base 2. Pour prendre en compte le signe, on est amené à utiliser un bit supplémentaire, dit bit de signe, qui est 0 pour les entiers positifs et 1 pour les négatifs. Par exemple, sachant que 97 = 1+25 +26, on peut envisager de coder l’entier 97 par 01100001 et l’entier -97 par 11100001.
En ce qui concerne les caractères (symboles comme : a, A, 3, ?, :, {, à, ), il existe un standard international, qui est une liste ordonnée de tous les caractères, appelée unicode. L’unicode est très complet. En informatique, on utilise souvent une sous-liste de l’unicode appelée code ASCII. Le code ASCII contient tous les caractères obtenus à partir d’un clavier QWERTY (y compris l’espace, le “retour chariot”, la tabulation et ceux obtenus par combinaison de touches comme les lettres majuscules), mais ne contient ni les caractères accentués ni les caractères des alphabets autres que l’alphabet latin. Dans cette liste (ASCII ou unicode), chaque caractère a un numéro d’ordre bien déterminé et c’est donc l’écriture binaire de ce numéro d’ordre qui code le caractère. Voici ci-dessous, par curiosité, la table ASCII. Dans la pratique, il est inutile de connaˆ?tre ces tables.
|
000 (nul) 016 (dle) 032 sp 048 0 064 @ 080 P 096 ‘ 112 p 001 (soh) 017 (dc1) 033 ! 049 1 065 A 081 Q 097 a 113 q 002 (stx) 018 (dc2) 034 " 050 2 066 B 082 R 098 b 114 r 003 (etx) 019 (dc3) 035 # 051 3 067 C 083 S 099 c 115 s 004 (eot) 020 ¶(dc4) 036 $ 052 4 068 D 084 T 100 d 116 t 005 (enq) 021 §(nak) 037 % 053 5 069 E 085 U 101 e 117 u 006 (ack) 022 (syn) 038 & 054 6 070 F 086 V 102 f 118 v 007 (bel) 023 (etb) 039 ’ 055 7 071 G 087 W 103 g 119 w 008 (bs) 024 (can) 040 ( 056 8 072 H 088 X 104 h 120 x 009 (tab) 025 (em) 041 ) 057 9 073 I 089 Y 105 i 121 y 010 (lf) 026 (eof) 042 * 058 : 074 J 090 Z 106 j 122 z 011 (vt) 027 (esc) 043 + 059 ; 075 K 091 [ 107 k 123 { 012 (np) 028 (fs) 060 < 076 L 092 \ 108 l 198 l 124 | 013 (cr) 029 (gs) 045 - 061 = 077 M 093 ] 109 m 125 } 014 (so) 030 (rs) 046 . 062 > 078 N 094 ^ 110 n 126 ~ 015 (si) 031 (us) 047 / 063 ? 079 O 095 _ 111 o 127 Table ASCII standard (codes de caractères de 0 à 127) |
Ainsi, sachant que le code de la lettre a est 97, elle sera représentée par 01100001.
Il résulte de ce qui précède que 01100001 code à la fois l’entier 97 et le caractère a. Se pose donc le problème du décodage, en général au moment de l’affichage. Pour reconnaˆ?tre la donnée représentée par 01100001, il est absolument nécessaire de connaˆ?tre le type de la donnée que l’on cherche : en l’occurrence, un entier ou un caractère.
Il est donc essentiel de préciser le type d’une donnée au moment du codage et du décodage.
Une source fréquente de confusion provient du fait que si, dans les écrits courants, le nombre entier quatre-vingt dix sept est représenté à l’aide de deux symboles 9 et 7, le nombre entier sept est représenté par un unique symbole 7. Ainsi l’entier sept et le caractère 7 sont tous deux représentés par le même symbole. L’ambigu¨?té est alors levée par le contexte. Dans la phrase 7 plus 11 font 18, il s’agit d’un nombre. Dans la phrase le nom de code du célèbre agent secret Hubert Bonisseur de La Bath se termine par 7, il s’agit du caractère. Une telle ambigu¨?té ne peut subsister dans les programmes qui sont destinés à être automatiquement exécutés sans prise en compte du contexte. Les langages de programmation utilisent donc des notations permettant de faire le distinguo. En Java :
7 désigne l’entier et ’7’ le caractère la lettre a est désignée par ’a’
Plus généralement, tout caractère est désigné par un symbole écrit entre deux apostrophes. Ainsi ’7’, dont le code ASCII (et également unicode) est 55 d’après la table ci-dessus, est codé par 010111 puisque 55 = 25 + 24 + 22 + 2 + 1. Alors que 7 est codé par 0111.
Enfin, la mémoire d’un ordinateur étant de taille finie, on con¸coit aisément que l’on ne peut représenter toutes les données. Par exemple, il est hors de question de représenter l’infinité des entiers relatifs. Et même en s’en tenant à une partie finie de cet ensemble, il n’est pas raisonnable de coder un entier tellement grand qu’il occuperait toute la mémoire, ce qui rendrait impossible toute autre opération.
Ainsi, on convient de coder toutes les données d’un même type, sur un nombre d’octets dépendant uniquement du type. Par exemple, en Java, les caractères sont codés sur 16 bits :
’7’ est représenté en machine par 0000000000010111
’a’ est représenté en machine par 0000000001100001
Dans tout codage binaire, le bit le plus à droite (bit des unités) est appelé bit de poids faible.
|
Type |
Signification |
Taille en bits |
Constantes |
Opérateurs |
|
|
char |
caractère |
16 |
’3’,’\n’, ’\’’ |
+ - |
* / % |
|
byte |
8 |
||||
|
short int |
entiers |
16 32 |
97 -97 |
+ - |
* / % |
|
long |
64 |
||||
|
float |
32 |
97. 0.97E2 |
|||
|
double |
flottants |
64 |
9.7e1 |
+ |
- * / |
|
boolean |
booléens |
8 |
true false |
&& || ! ?: |
|
Pour les types entiers, les opérateurs binaires / et % ont pour résultat respectivement le quotient et le reste de la division entière des opérandes. Par exemple : 7% 2 = 1 7/2 = 3 -7%2= -1 -7/2 = -3. Lorsque les opérandes sont de type char, il s’agit de l’opération sur l’entier qui les code.
Les valeurs de type float sont évaluées avec une précision de 10?6, celles de type double avec une précision de 10?15. Les constantes (par exemple 0.97) sont considérées comme étant de type double. Pour en faire un float, il faut écrire 0.97f.
L’opérateur ! désigne la négation et les opérateurs && et || désignent respectivement la conjonction et la disjonction logiques. Il est bon de savoir que lors de l’évaluation d’une expression booléenne de la forme e1&&e2, l’expression e2 n’est pas évaluée si e1 est fausse. De même pour e1||e2 si e1 est vraie.
Opérateurs de comparaison Les types simples supportent également les opérateurs suivants :
> >= < <= == !=
Ce sont des opérateurs binaires qui renvoient une valeur booléenne, résultat de la comparaison des deux opérandes.
Exemple 1.1 x!=0 && 1/x>10E3 est une expression booléenne. Son évaluation ne provoque jamais d’erreur puisque 1/x n’est évalué que si l’expression x!=0 a pour valeur true.
Le type String C’est un type un peu particulier qui désigne les chaˆ?nes de caractères et qui n’est donc pas un type simple. Les chaˆ?nes de caractères sont notées entre guillemets : "Ceci est une cha?^ne de caractères". Elles peuvent être concaténées au moyen de l’opérateur binaire + et affichées à l’écran au moyen de l’instruction :
.print(<chaˆ?ne de caractères>)
ou encore
.println(<chaˆ?ne de caractères>)
La deuxième instruction affiche à l’écran la chaˆ?ne de caractère suivie d’un retour chariot. Ainsi les trois instructions :
.println("Il y a dans les bois\nDes arbres fous d’oiseaux")
.print("Il y a dans les bois\nDes arbres fous d’oiseaux\n") .print("Il y a dans les bois\n"+"Des arbres fous d’oiseaux\n") provoquent l’affichage suivant (on y a fait figurer la position du curseur) :
Il y a dans les bois
Des arbres fous d’oiseaux
Noter que les opérateurs de comparaison ne s’appliquent pas aux chaˆ?nes caractères.
L’opérateur ternaire :? Il permet de construire une expression à partir d’une expression booléenne et de deux expressions <expr1> et <expr2> comme suit :
<expr booléenne>? <expr1> : < expr2>
Cette expression a pour valeur celle de <expr1> si l’expression booléenne vaut true et celle de <expr2> sinon.
Exemple 1.2 .print(x==0? "x est nul":"x est non nul") a pour effet d’afficher à l’écran x est nul ou x est non nul selon que la variable x est nulle ou pas.
Affichage des valeurs de types simples Quand une telle valeur se trouve en lieu et place d’une chaˆ?ne de caractères, elle est automatiquement convertie par Java en sa représentation sous forme de String.
Exemple 1.3Supposons que a, b et d soient trois variables de type int et que l’on ait calculé dans d le plus grand diviseur commun à a et b. L’instruction :
.print("PGCD(" + a + ", " + b + ") = "+d) affiche à l’écran : PGCD(15, 12) = 3 si les valeurs de a et b sont respectivement 15 et 12 au moment de l’exécution de l’instruction. Java a en particulier converti l’entier quinze codé en machine par : 0000000000001111 en la chaˆ?ne "15", des caractères constituant son écriture dans le système décimal sans qu’il ait été besoin d’appeler pour cela une quelconque fonction de conversion.
1.2 Les variables et l’affectation
Une variable est une zone mémoire dédiée à l’enregistrement d’une donnée. Elle est caractérisée par :
– son adresse : celle du premier octet qu’elle occupe – son type : il définit sa taille et le codage/décodage
– sa valeur : c’est son état à un instant donné. Cet état peut évidemment varier, d’ou` le nom de variable.
Toute variable utilisée dans un programme doit être déclarée au préalable comme suit.
<type> < nom de variable>;
Exemple 1.4 int age; char initiale;
Dans un programme, la déclaration d’une variable provoque l’allocation en mémoire de l’espace nécessaire pour coder les données du type indiqué. L’adresse de la zone allouée est associée au nom de la variable. A ce stade là, la valeur de la variable existe (bien évidemment, la variable se trouve dans un certain état!) mais est indéterminée : la mémoire allouée a pu être utilisée par un autre programme puis libérée en l’état. La variable est dite non initialisée. Plusieurs variables de même type peuvent être déclarées simultanément. Leurs noms sont alors séparés par des virgules.
Exemple 1.5 float perimetre, surface;
Une affectation consiste à enregistrer une valeur dans une variable. Il s’agit donc d’une instruction (effet de bord). La syntaxe des affectations est la suivante.
<nom de la variable> = <expression>;
initiale = ’a’;
Après exécution de ces deux instructions, l’état de la variable age est :
00000000000000000000000001100001
et celui de la variable initiale est : 0000000001100001.
Toute variable peut être initialisée au moment de sa déclaration selon la syntaxe suivante :
<type> <nom de la variable> = <expression>;
Ainsi, on peut écrire : int age; char initiale;
int age = 97; float surface;
char initiale = ’a’; float perimetre;
au lieu de
float surface = 0.16, age = 97;
périme`tre = 1.6; initiale = ’a’;
surface = 0.16; perimetre = 1.6; Attention : ne pas confondre l’affectation age = 97 et l’expression booléenne age == 97.
Le nom d’une variable désigne à la fois son adresse et sa valeur. Dans une affectation, l’ambigu¨?té est levée par le contexte. L’exécution de l’instruction :
age = 2*age +1;
a pour effet de rajouter 1 au double de la valeur de age et d’enregistrer le résultat à l’adresse age. Ainsi, à gauche du signe d’affectation, le nom age désigne l’adresse de la variable, tandis qu’à droite il désigne sa valeur.
1.2. LES VARIABLES ET L’AFFECTATION
Considérons l’instruction x = x+2. Son exécution requiert :
1. le calcul de l’adresse de x pour aller en mémoire récupérer sa valeur (lecture)
2. l’évaluation de l’expression à droite du signe d’affectation
3. à nouveau le calcul de l’adresse de x pour aller en mémoire enregistrer le résultat obtenu
(écriture)
On peut optimiser ce type d’affectation à l’aide de la syntaxe suivante.
<nom> <op>= <expression>;
Pour l’exemple précédent on obtient x+=2.
L’optimisation consiste à n’effectuer le calcul de l’adresse qu’une seule fois (suppression de l’étape
3). Ainsi,
n = n/2; n /= 2; x = x*x; sont avantageusement remplacées par x *= x; r = r * x; r *= x;
Soit i une variable entière. On appelle incrémentation (respectivement décrémentation) de i le fait de rajouter 1 (respectivement retrancher 1) à sa valeur. Par exemple i=i+1; et i=i-1; sont une incrémentation et une décrémentation de i. D’après ce qui précède, on peut améliorer cette écriture en i+=1; et i-=1; respectivement.
Les incrémentations et décrémentations à répétition sont très fréquentes en programmation. Lorsqu’on parcourt une suite d’éléments indexée de 0 à n, on fait varier un indice i de 0 à n (respectivement de n à 0) en l’incrémentant (respectivement le décrémentant) à chaque itération. Il est donc important d’essayer d’optimiser ces instructions.
On remarque alors qu’incrémenter un entier peut se faire beaucoup plus simplement qu’une addition normale qui demande d’examiner tous les bits des deux opérandes. Par exemple, si le bit de poids faible est 0, il suffit de changer ce bit en 1. De même pour la décrémentation. Si l’on utilise les opérateurs + ou -, avec l’une ou l’autre des deux syntaxes ci-dessus, c’est bien l’algorithme général d’addition et de soustraction qui sera effectué. La syntaxe permettant un calcul optimisé de l’incrément et du décrément est la suivante :
|
++<nom de la variable>; |
|
<nom de la variable>++; |
|
--<nom de la variable>; |
|
<nom de la variable>--; |
Ainsi par exemple, i++; et --i; ont respectivement le même effet de bord que i=i+1; et i=i-1; mais sont beaucoup plus efficaces.
Conversions implicites Certains types peuvent être implicitement convertis en d’autres. Par exemple tout entier peut être converti implicitement en un flottant et tout caractère en un entier. On peut ainsi écrire :
float longueur = 2; short x = ’a’; au lieu de float longueur = 2.0f; short x = 97;
Conversions explicites Certaines conversions peuvent être forcées (cast dans le jargon informatique). La syntaxe est la suivante :
( <type>) <expression>
Exemple 1.7 (int) (9.7*x + 2.3)
(short) ’a’
Dans le premier cas, on obtient la partie entière et dans le second, le code 97 du caractère ’a’, codé sur 16 bits.
Les conversions explicites mal maˆ?trisées relèvent de l’acrobatie et sont fortement déconseillées aux programmeurs non avertis.
1.3 Instructions et expressions
Comme évoqué en introduction, on peut distinguer les instructions des expressions. Les instructions sont exécutées et leur exécution affecte l’état de la mémoire, c’est ce que l’on appelle l’effet de bord. Les expressions sont évaluées et leur évaluation par le processeur provoque un calcul et produit, sauf erreur, un résultat.
Ce qui suit va remettre en cause cette distinction. En Java, comme en C, certaines instructions sont des expressions, en ce sens qu’à la fois elles indiquent un calcul à effectuer et elles ont une valeur. De même certaines expressions ont un effet de bord.
Considérons l’expression 2*x+1. A l’évaluation, le processeur effectue une multiplication et une addition. Le résultat obtenu est appelé valeur de l’expression. La mémoire n’est pas affectée par ce calcul. Il n’y a pas d’effet de bord. L’expression n’est donc pas une instruction.
En revanche, les affectations sont des instructions. Par exemple l’exécution de l’instruction x = 2*x+1; provoque :
- l’évaluation de l’expression 2*x+1
- l’affectation de la valeur trouvée à x (effet de bord)
En Java (et également en C), une affectation a non seulement un effet de bord, mais également une valeur : celle de l’expression située à droite du signe d’affectation. En ce sens, c’est aussi une expression.
type : celui de x
x = < expr >valeur : la valeur v de <expr>
? effet de bord : affectation de v à x
En supposant par exemple que x et y sont deux variables de type int et de valeurs respectives 3 et 5, il est possible d’écrire : x = y =2*(x+y). Ce code est interprété comme suit :
x = y
effet de bord : aucun valeur : v= 16
|effet de bord : affectation de v2 {z 1 à y}
valeur : v = v
|effet de bord : affectation de v3 {z 2 à x } valeur : v = v2
Il en résulte que la valeur 16 est affectée à y puis à x.
Examinons le cas des incrémentations et décrémentations efficaces d’une variable i de type entier. Les instructions i++; et ++i; ont le même effet de bord : elles changent l’état de la variable i en rajoutant 1 à sa valeur. Toutefois, considérées comme des expressions, elles n’ont pas la même valeur. L’expression i++ a la valeur de i avant incrémentation tandis que l’expression ++i a la valeur de i après incrémentation.
Le tableau ci-dessous résume les effets de bords et les valeurs des quatre instructions concernées dans le cas ou` la valeur initiale de la variable est 5.
|
i avant exécution |
expression instruction |
i après effet de bord |
valeur de l’expression |
|
5 |
i++ |
6 |
5 |
|
5 |
++i |
6 |
6 |
|
5 |
i-- |
4 |
5 |
|
5 |
--i |
4 |
4 |
Les blocs permettent de composer séquentiellement une suite d’instructions en les écrivant entre accolades. Un bloc est considéré comme une unique instruction.
a = b; b = r;}
Un bloc peut aussi contenir des déclarations de variables. Ces variables sont locales au bloc. Elles sont créées au moment de l’exécution du bloc et restituées dès la fin de l’exécution. Il en résulte qu’elles sont bien évidemment inconnues à l’extérieur du bloc. Si une variable locale porte le même nom qu’un variable globale, cette dernière est masquée (donc inconnue) dans le bloc par la déclaration locale.
aux = a; a = b; b = aux; }
est un bloc qui utilise temporairement une variable auxiliaire aux permettent d’échanger les valeurs de deux variables a et b supposées précédemment déclarées de type int. L’espace occupé par aux est libéré après l’exécution de la dernière instruction b = aux;
