Algorithme et Structure de données :

Les exemples de ce cours sont illustrés en Java, mais la notin d'algorithme reste le mêmepour d'autres langages de programmation.

Notions de base :

Un programme informatique est, en gros, une séquence d'instructions, d'ordres données à un ordinateur afin de lui faire accomplir une tâche précise. Un même programme est en général appelé à être exécuté plusieurs fois. Bien qu'on ait parlé de "tâche précise", chacune des exécutions d'un "alternatives", c'est-à-dire des sous-séquences d'instructions qui seront exécutées ou non en fonctions des circonstances extérieures.

Si l'on retire du paragraphe précédent le mot "ordinateur", cette définition pourrait aussi s'appliquer à une recette de cuisine, telle qu'elle figuererait dans un livre de recettes. En voici un exemple (plutôt élémentaire !) :

POUR préparer une salade :

prendre une belle laitue, séparer les feuilles en retirant les plus abîmées
laver soigneusement les feuilles, puis bien les sécher
mettre dans un saladier3 cuillers à soupe d'huile, une de vinaigre, un peu de moutarde, de sel et de poivre
bien mélanger ces ingrédients
rajouter les feuilles de laitue et remuer le tout au moment de servir

Jusqu'ici, dans cet exemple, il n'ya qu'un seul cheminement possible. Mais l'on pourrait imaginer la recette suivante :

POUR préparer une salade :

SI on dispose d'une laitue qui a été vendue déjà nettoyée et découpée
- ALORS ouvrir le sachet
- SINON
  - prendre une belle laitue, séparer les feuilles en retirant les plus abîmées
  - laver soigneusement les feuilles, puis bien les sécher
SI on a de la vinaigrette toute faite
- ALORS mettre 4 cuillers à soupe de vinaigrette dans un saladier
- SINON
  - mettre dans un saladier 3 cuillers à soupe d'huile, de vinaigre, un peu de moutarde, de sel et de poivre
  - bien mélanger ces ingrédients
rajouter les feuilles de laitue et remuer le tout au moment de servir

Dans de très nombreux programmes informatiques, en outre, une même sous-séquence d’instructions est appelée à être exécutée plusieurs fois d’affilée. Cette situation est assez naturelle, si l’on pense que l’ordinateur est surtout destiné à exécuter très rapidement des tâches de routine, c’est-à-dire des tâches répétitives.

Pour revenir à notre exemple de salade, on pourrait rencontrer les instructions suivantes :

POUR CHACUNE des feuilles de laitue :
1. détacher la feuille délicatement de la laitue
2. l'examiner pour voir si elle ne possède pas de tâche ou de partie froissée
3. retirer les parties suspectes
4. couper la feuille en morceaux et mettre ceux-ci dans l'eau de nettoyage
gôuter la vinaigrette
TANT QUE la vinaigrette n'est pas assez piquante :
1. rajouter un peu de moutarde
2. rajouter un peu de vinaigre
3. bien mélanger
4. goûter de nouveau la vinaigrette

Les programmeurs parleront, dans un tel cas, de "répétitive", d'"itérative", ou encore de "boucle".

Enfin, de nombreux livres de cuisine renvoient le lecteur d’une recette à l’autre, lorsqu’un mets plus élaboré en inclut un autre, plus simple. Ainsi la recette de salade pourrait se résumer à :

POUR péparer une salade :

préparer des feuilles de laitue (voir page XXX)
préparer une vinaigrette (voir page YYY) et la mettre dans un sablier
rajouter les feuilles de laitue et remuer le tout au moment de servir

À la page XXX, on trouverait :

POUR préparer des feuilles de laitue :

SI on dispose d'une laitue qui a été venue déjà nettoyée et découpée
- ALORS ouvrir le sachet
- SINON
  - prendre une laitue, séparer les feuilles en retirant les plus abîmées
  - laver soigneusement les feuilles, puis bien les sécher

et la page YYY :

POUR préparer une vinaigrette :

mettre dans un saladier 3 cuillers à soupe d'huile, une de vinaigre, un peu de moutarde, de sel et de poivre
bien mélanger ces ingrédients

Cette dernière situation est rencontrée aussi en programmation : un programme fait souvent appel à un "sous-programme" qui doit exécuter pour lui une partie du traitement. Et cette sous-traitance peut se répercuter en cascade : le sous-programme peu à son tour sous-traiter à un autre sous-programme une partie de tâche qui lui a été confiée par le "programme principal", etc.

On parlera, selon les langages et les contextes, de "sous-programmes", de "procédures", de "fonctions, de "méthodes, etc.

Le cycle de vie d'un programme :

Pour concevoir un programme, ou à fortiori toute une "application informatique" (qui peut elle-même être constituée de plusieurs programmes), l’informaticien doit d’abord faire une analyse fouillée de la situation et de ce qu’on lui demande de réaliser : c’est la phase d’"analyse", située en amont de la programmation proprement dite.

Ensuite, il doit élaborer, structurer la séquence d’instructions qui permettront de réaliser la tâche demandée. Une telle séquence d’actions, structurées à l’aide d’alternatives, de répétitives, de sousprogrammes, est appelée un "algorithme".

Une fois conçus sur papier, les algorithmes n’auront alors plus qu’à être "implémentés" ou "programmés sur une machine, via un langage informatique, avant d'être exécutés.

Enfin, la phase de test est de mise au point est tout à fait essentielle. Elle doit être réalisée de manière professionnelle, c’est-à-dire systématique et rigoureuse. (L’idéal est de prévoir déjà les tests avant d’écrire le programme : on pense ainsi dès le départ à tous les cas que devra traiter ce programme.)

Et il ne faut pas négliger la mise en oeuvre effective, la formation éventuelle des utilisateurs (par exemple via un "manuel d'utilisation"), et les réaménagements ultérieurs (ce qu'on appelle la "maintenance" du programme).

Pour accompagner tout ce cheminement, une documentation complète, précise et bien mise à jour est indispensable : elle figuera dans un dossier (sur papier ou sur support informatique) accompagnant le programme, ainsi que dans les commentaires insérés dans celui-ci.

Les types de référence :

La déclaration d'une variable sert :

à donner à la variable son type
à demander à l'ordinateur de réserver une zone de mémoire pour elle, zone dont la taille dépendra du type
à fixer la portée de la variable : où et quand sera-t-elle accessible ?

Une variable possédera à tout moment une valeur : c’est cette valeur qui sera stockée dans la zone de mémoire propre à la variable. Cette valeur peut changer au fur et à mesure de l’exécution du programme, d’où le terme de "variable". Mais la valeur doit toujours être conforme au "type" de la variable.

type	type Java	valeurs	valeur par défaut
nombre entier	int	325, -65, 0, 1234567890	0
nombre réel simple précision	float	32.56, -0.001, 1.03e+04(= 10300.0)	0.0
nombre réel double précision	double	32.56, -0.001, 1.03e+04(= 10300.0)	0.0
caractère	char	'A', '2', '+', ' '	''
booléen	boolean	true, false	false

Les inputs/outputs :

On définit une varibale servant de "lecteur" des entrées :

Scanner scanner = new Scanner(System.in);

On l'utilise pour lire une valeur :

int nombre = scanner.nextInt();

Comme le montre le tableau suivant, cette instruction diffère légèrement en fonction du type de la variable que l'on désire lire :

Type	Instruction
int	int nombre = scanner.nextInt();
char	char caractere = scanner.nextChar();
String	String texte = scanner.next();

Cette instruction est un peu délicate à manier car à la moindre erreur d’entrée de l’utilisateur, si rien n’est fait pour rattraper celle-ci, le programme s’arrêtera.

Pour écrire dans la console, on utilise :

System.out.println("texte à écrire dans la console");

ASTUCE : Sur Eclipse, écrire "sysout" et taper simultanément sur les touches "Ctrl" et "Space" permet d'écrire plus facilement le "System.out.println".

Cette instruction permet d'écrire le texte situé entre parenthèses dans la console et on passe à la ligne. Si on met "print" au lieu de "println", le texte sera écrit dans la console mais sans le saut à la ligne.

Les alternatives :

Une alternative est une instruction qui permet l'ordinateur, au moment de l'exécution du programme, de choisir la partie de code à exécuter : ce choix s'effectue en fonction de certaines conditions qui, en général, font intervenir les valeurs d'une ou plusieurs variables.

Il existe deux familles d'alternatives : les alternatives à deux branches et celles à nombre quelconque de branches.

En Java, l'alternative à deux branches s'écrit comme suit :

if (condition) {
    instruction_1_1;
    instruction_1_2;
    ...
    instruction_1_N;
} else {
    instruction_2_1;
    instruction_2_2;
    ...
    instruction_2_N;
} // FIN if

Une alternative n’est au final qu’une instruction comme les autres et peut donc être utilisée au sein d’une autre alternative ! C’est ce qu’on appelle "alternative imbriquée".

if (x > y) {
    System.out.println("x est le plus grand");
} else {
    if (y > x) {
        System.out.println("y estle plus grand");
    } else {
        System.out.println("x et y sont égaux");
    }
}

Pour éviter de multiplier les if imbriqués, il existe une instruction permettant d'exprimer plus de deux cas : le switch-case. C'est une des alternatives à N branches.

switch (expression) {
    case valeur_1 :
        instruction_1_1;
        instruction_1_2;
        ...
        instruction_1_N1;
    case valeur_2 :
        instruction_1_1;
        instruction_1_2;
        ...
        instruction_1_N2;
    case valeur_M :
        instruction_1_1;
        instruction_1_2;
        ...
        instruction_1_NM;
    default :
        instruction_1_1;
        instruction_1_2;
        ...
}

La sémantique de l'instruction switch est la suivante :

On évalue l'expression entre parenthèses. (Si nécessaire, on la convertit en int.)
On compare sa valeur aux valeurs des différentes "expressions constantes".
Si sa valeur a été trouvée, on exécute toutes les instructions qui suivent cette constante, y compris celles qui sont situées au-delà des mots "case" et "default" suivants.
Si sa valeur n'a été trouvée, et qu'il y a une branche "default", on passe directement à l'instruction "break;, on quitte le switch.
Dans tous les cas, après l'exécution de ce qu'il fait, on continue en exécutant les instructions situées au-delà de l'instruction switch (sauf bien sûr si l'on a rencontré au passage une instruction qui nous fait sortir du bloc où se trouve ce switch : return, throw, ...).

L'expression du switch ne peut être que d'un type dont les valeurs peuvent être énumérées (int, char, ...) et donc ni des float ni des objets (pas de String non plus).

Les opérateurs :

En Java,

l'opérateur OU (inclusif) s'écrit | ou || (voir plus loin la différence)
l'opérateur ET s'écrit & ou && (voir plus loin la différence)
l'opérateur NON s'écrit !

En Java, les opérateurs ET et OU sont dédoublés :

& et | imposent une évaluation complète
- l'ordinateur évalue exp1
- puis il évalue exp2
- puis il effectue l'opérateur "ET" ou "OU"
&& et || demandent une évaluation court-circuitée
- l'ordinateur évalue exp1
- si la valeur de exp1 est true, il sait que le résultat de l'ensemble est aussi true dans l'opération "OU", sans qu'il n'ait dû évaluer exp2
- si la valeur exp1 est false dans l'opération "OU", il évalue exp2, et le résultat de l'ensemble est égal à la valeur de exp2

La différence entre les deux consiste surtout en un gain de temps, surtout dans le cas où exp2 est une expression dont l’évaluation prend du temps : l’évaluation court-circuitée permet d’éviter ce temps inutilement dépensé.

Remarquons que :: (expression1) & (expression2)
Est (en général) "équivalent à" :: (expression2) & (expression1)
Ce qui n'est plus le cas si l'on utilise l'opérateur &&.
La même remarque s'applique à | et ||.

Les opérateurs de relation :

= (== en Java), !=
<, <=, >, >=

Quelques conseils de styles :
Au dieu d'écrire :	Écrivez plutôt
if (trouve == true) { ... } while (file == false) { ... } if ((a > b) \|\| (x == y)) b1 = true; else b2 = false; if (a == b + c) b1 = true; if (a == 0) b1 = false; boolean b = (a > b) \|\| (x == y); return b;	if (trouve) { ... } while (!fini) { ... } b1 = (a > b) \|\| (x == y); b1 = b1 \| (a == b + c); (lisibilité discutable) b1 = b1 & !(a == 0); (lisibilité discutable) return (a > b) \|\| (x == y);

En Java, l'opérateur ternaire : "... ? ... : ..." permet aussi d'éviter certains "if" :

au lieu de :
```
if (a > b) max = a;
else max = b;
```
on écrira :
```
max = (a > b) ? a : b;
```

Les répétitives :

Une répétitive (ou itérative, ou boucle) est une instruction demandant à l'ordinateur d'exécuter plusieurs fois un groupe d'instructions spécifiées (le mot "plusieurs" est à prendre ici au sens large, englobant les cas 0 et 1).

Les types de répétitives sont très variables d’un langage à l’autre, et certains langages en présentent même une grande diversité. Ces types de répétitives se différencient essentiellement par la façon dont on spécifie le nombre d'exécutions.

Nous présenterons ici celle de Java ainsi que quelques macro-algorithmes.

La boucle for :

Le modèle général de la boucle for en Java est le suivant :

for ( <init var de contrôle>; <cond. de continuation>; <increment> ) {
    <Action_1>;
    <Action_2>;
    <Action_3>;
    ...
    <Action_N>;
}

Exemple :

for (int i = 1; i <= nombreJoueurs; i++) {
    donnerUneCarte();
}

La sémantique de cette instruction est résumée par le schéma suivant :

Le corps de la boucle situé entre les deux accolades est la suite d'instructions à répéter.

La variable de contrôle de la répétitive sert à contrôler le nombre de répétitions. Il s'agit en général d'une variable entière, d'autres types sont possibles : le type caractère par exemple. Elle doit être déclarée et initialisée dans la boucle. Dans l'exemple donné i est la variable de contrôle. Elle est de type int est initialisée à 1.

La condition de continuation dela répétitive est une expression de type booléen. Le corps de la boucle est répété tant que cette condition est vraie (true). Il s'agit d'une condition de continuation car on continue la boucle tant que la condition est vraie.

L'incrément sert à augmenter (ou dimuer) la valeur de la variable de contrôle.

ATTENTION : La boucle for est impérativement soumise aux deux contraintes ci-dessous, au risque de gravement porter atteinte à la lisibilité du programme, et donc en particulier d'entraver sa maintenance :

Ne JAMAIS modifier la valeur de la variable de contrôle à l'intérieur de la répétitive !
Après sortie de la répétitive, la variable de contrôle est censée n'avoir plus aucune valeur : elle est "indéterminée" (comme en début d'exécution d'un programme).

La boucle while et do while :

`while (<condition>) { <action_1> ... <action_n> }`	D'abord letest (donc : min. 0 passage
`do { <action_1> ... <action_2> } while ( <condition> );`	D'abord les actions (donc : min. 1 passage)

Tout comme la boucle for, la condition des while et do while est une condition de continuation.

Si on connaît le nombre de fois qu'il faut répéter l'action et que le pas est lui aussi connu à l'avance, on emploiera une boucle for.

Si l'on ne connaît pas le nombre de tour de boucle ou si le pas d'incrémentation n'est pas constant, on devrait utiliser une boucle while ou do while.

Les instructions que l’on place à l’intérieur d’une répétitive peuvent être de tout type, en particulier il peut s’agir d’autres répétitives. On obtient ainsi des boucles imbriquées dans d’autres boucles.

Une des erreurs les plus fréquentes lorsque l'on écrit des répétitives est ce que l'on appelle la boucle infinie : une répétitive qui ne s'arrête jamais.

La façon la plus simple d'avoir une boucle infinie est d'écrire une condition constante true :

while(true) {
    System.out.println("Rien ne l'arrêtera !");
}

De façon évidente, si l'on ne modifie aucune des variables composants la condition de la boucle, on peut avoir une boucle infinie :

int a = 3, b = 5, c = 6;
while (a < b) {
    c--;
}

Ici, a et b conserveront leurs valeurs initiales et la condition a<b est éternellement vraie.

Les String :

Une chaîne de caractères est une suite ordonnée de 0,1 ou plusieurs caractères, que l'on peut en général manipuler globalement ou caractère par caractère. En Java, le type String représente les chaînes de caractères.

Un littéral de type String commence et termine par des guillemets doubles. Entre eux, on peut trouver :

des caractères autres que " et \
des caractères spéciaux marqués sous forme du caractère\ suivi d'un autre caractère :
- \" qui représente "
- \\ qui représente \
- \n qui représente un passage à la ligne
- \t qui représente une tabulation
- etc.

En Java, les chaînes de caractères ne constituent pas un type primitif, mais un type objet (un "type référence").

Ou, plus exactement, deux types objet. Ce langage met en effet à notre disposition deux classes, appelées String et StringBuffer. La seconde permet plus de manipulations à l'intérieur de la chaîne. Par contre, un objet de type String est "immuable" : on ne peut le modifier, si ce n'est en constituant une nouvelle chaîne.

On peut facilement construire une String à partir d'un StringBuffer, et vice-versa.

L’opérateur de concaténation (+) fournit une String comme résultat, obtenue par mise bout à bout des deux opérandes. Il s’applique en principe à deux Strings, mais, si un des opérandes du + est une String et l’autre pas, il y a conversion automatique de cet autre en String. (Si aucun des deux opérandes n’est une String, il s’agit de l’opérateur d’addition !).

Rappelons que l'associativité est à gauche, ce qui a de l'importance dans certains cas.

La classe String présente une dizaine de constructeurs, mais la plupart du temps on peut s’en passer, car la syntaxe du Java permet, par facilité, une notation similaire à celle des types primitfs.

Par exemple : à la place de l'écriture "orientée objet" suivante :

String chaine = new String("Hello !");

Le Java accepte l'écriture équivalente suivante :

String chaine = "Hello !";

La documentation du Java, en ligne ou trouvée dans un livre, vous donnera la liste complète des méthodes de la classe String. En voici quelques-unes :

Fonction	Description
public char char (int indice);	renvoie le caractère n°"indice" de la chaîne (NB : on commence à compter à 0).
public int compareTo (String autreChaine);	renvoie un entier positif, nul ou négatif selon que la chaîne-cible soit "supérieure", "égale" ou "inférieure" à la chaîne passée en paramètre; la comparaison se fait selon l'ordre "lexicographique".
public boolean equals (Object unObjet);	renvoie true seulement si l'objet passé en paramètre est une String, et que cette String a la même valeur que la chaîne-cible.
public boolean equalsIgnoreCase (String autreChaine);	renvoie true seulement si les deux chaînes sont identiques, sans tenir compte toutefois de la distinction entre majuscules et minuscules.
public int indexOf (String sousChaine);	renvoie la position de la première occurence de la sous-chaîne dans la chaîne-cible; exemple : String chaine = "Un coucou tout fou"; int position = chaine.indexOf("ou"); → 4 S'il n'y a pas d'occurence, on renvoie -1.
public int indexOf (String sousChaine, int depart);	renvoie la position de la première occurence de la sous-chaîne dans la chaîne-cibe, à partir de l'indice "départ"; exemple : String chaine = "Un coucou tout fou"; int position = chaine.indexOf("ou", 8"); → 11 S'il n'y a pas d'occurence, on renvoie -1. Rappel : on commence à l'indice 0.
public int length();	renvoie la longueur de la chaîne, c'est-à-dire le nombre de caractères qu'elle contient. Ex : String chaine "Un coucou tout fou"; int longueur = chaine.length; char dernierCaractere = chaine.charAt(longueur - 1);
public String substring (int debut, int fin);	renvoie une sous-chaîne, obtenue en prenant dans la chaîne-cible tous les caractères depuis celui de l'indice "début" jusqu'à celui situé juste avant l'indice "fin" (rappel : on commence à compter à 0); exemple : String chaine = "Un coucou tout fou"; String ssch = chaine.substring(3,9); → "coucou"
public String toUpperCase(); public String toLowerCase();	convertissent respectivement les minuscules en majuscules (tout en conservant inchangés tous les caractères) et vice-versa.

Les tableaux :

Remarque : dans de nombreux langages, la souplesse de programmation en utilisant les tableaux est un peu atténuée par le fait qu’il faut dimensionner les tableaux dans les déclarations de variables, dès la phase d’écriture du programme; cet inconvénient est résolu par un surdimensionnement systématique de tels tableaux.

En Java cependant, on peut créer un tableau en ne connaissant sa taille qu'au moment de l'exécution en suivant par exemple le code suivant :

int taille = scanner.nextInt();
int[] tab = new int[taille];

Attention : Il est à noter qu'en Java les tableaux commencent toujours à la case 0. Le tableau créé compte taille cases : de 0 à taille - 1.

Remarque : Un danger non négligeable de l'outil "tableaux" est cependant la tentation d'en abuser.

Dans les langages classiques, un tableau (ou une table, ou une variable indicée), c'est un groupe de "cases de mémoire"

toute de même "type".
donc forcément de même taille.
possédant un nom (identificateur) commun.
différenciées les unes des autres par la valeur d'un (ou de plusieurs) indice(s).

Si le tableau n'a qu'un seul indice, comme dans l'exemple donné, on parle parfois de vecteur, et s'il en a deux, de matrice.

Les indices commencent, selon les langages, à une valeur imposée (toujours 0 en Java, toujours 1 dans certains langages) ou au contraire à une valeur au choix du programmeur (en Pascal par exemple, on peut décider de créer un tableau indicé de 5 à 20, ou encore de -1850 à -127).

Le type des indices est souvent réduit aux nombres entiers, mais certains langages acceptent d'autres types, comme le type caractère.

En Java, les tableaux sont des constructions hybrides : ce sont des "objets" sous certains aspects, mais pas sous tous.

Un tableau est toujours une référence. L'espace-mémoire du tableau doit être construit par l'utilisation de l'opérateur "new" (ou par un "array initializer").

Un tableau possède un "champ, qui représente sa longueur physique et s'appelle length.

Les éléments du tableau peuvent être de n'importe quel type Java, y compris un type objet ou un type tableau (ce dernier cas, tableau de tableaux, permet d'implémenter des tableaux à plusieurs dimensions).

En Java, tous les tableaux sont indicés à partir de 0. Ceci est une limitation du Java (par exemple par rapport au PHP).

On peut aussi déclarer et allouer et initialiser le tableau tableDEntiers en utilisant un "array initializer" :

int[] tableDEntiers = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18};

Ceci n'est cependant possible que pour des tableaux d'éléments d'un type primitif (int dans l'exemple).

Attirons aussi sur le fait que la fixation de la taille du table et donc aussi l'allocation de mémoire se font dynamiquement, lors de l'exécution (et pourra donc être différente d'une exécution à l'autre !). D'oùl'intérêt du champ "length" qui donne la longueur physique d'un tableau, comptée en nombre de "cases", c'est-à-dire en nombre de valeurs différentes de l'indice. Comme l'indice commence toujours à 0, cette longueur est aussi égale à la plus grande valeur de l'indice, plus 1.

Taille physique et taille logique :

Un tableau est conçu en vue de stocker, durant l’exécution d’un programme ou une partie de celle-ci, un certain nombre d’informations de même nature. Le nombre de telles informations effectivement mémorisées à un moment donné peut être ou bien fixe ou bien variable. Dans ce dernier cas, étant donné qu’un tableau doit en général être pré-dimensionné lors de l’écriture du programme, ou en tout cas lors de sa création, il y a une distinction à opérer entre :

la taille physique du tablau : le nombre de "cases" réservées dans les déclarations de variables ou lors de la construction (le "prédimensionnement").
la taille logique du tableau : le nombre de "cases effectivement occupées à un moment donné par des informations pertinentes (autres donc que des "crasses").

La taille physiqueapparaît dans les déclarations de variables ou dans l'appel au constructeur : elle ne pose pas de problème particulier, sinon qu'il faut veuiller, lors de tout adressage à un élément du tableau, à ne pas "sortir" des limites autorisées.

Selon les langages, les compilateurs et parfois même les options de compilation, le comportement peut varier si l’on sort malencontreusement de ces limites. En Java, qui est un langage plein de garde-fous, une telle erreur provoque la levée d’une "exception" et, au pire, l'arrêt du programme avec un message d’erreur. Ailleurs, on peut avoir une situation où aucun contrôle n’est effectué et où, tout en croyant qu’on se "promène" dans le tableau, on se trouve dans une autre partie de la mémoire... (d'où des risques de catastrophes imprévisibles !)

Quant à la taille logique, il revient au programmeur de la gérer convenablement dans son programme. Les deux techniques les plus fréquentes à cet égard sont :

Au tableau proprement dit, on adjoint un attribut de la gérer, qui sert à dire jusqu'où le tableau est rempli. On s'arrange dans ce cas pour que tous les éléments "utiles" du tableau soient toujours rassemblés au début de celui-ci.
- Si les indices commencent à 1, cette variable représente à la fois le nombre d'éléments utiles (donc la taille logique) et l'indice du dernier d'entre eux.
- S'ils commencent à 0, comme c'est le cas en Java, cette variable représente à la fois le nombre d'éléments utiles et l'indice de la première case inutilisée.
Si les N premières cases du tableau sont utilisées et pas les suivantes, on met en position N + 1 un "élément-bidons" dans toutes les cases inoccupées).

La seconde de ces techniques présente divers inconvénients :

Le tableau doit avoir une "case" de plus que le plus grand nombre possible d'éléments.
Il n'existe pas toujours un "élément-bidon" qui ne peut être égal à aucune valeur "normale" des éléments du tableau.
Le tableau contient des informations de deux natures différentes : d'une part les éléments proprement dits, et d'autre part le signal de fin.
Certains algorithmes (recherche dichotomique par exemple) sont fort alourdis.

Nous préconisons donc la première technique, et suggérons même de déclarer les tables sous forme de classes contenant le tableau proprement dit et sa dimension logique. Exemple :

public class TableauDeTailleVariable {
    int nombreElements;
    VotreClasse[] tab;
}

Ainsi, lorsqu'une telle table sera par exemple transmise comme paramètre à une méthode, elle ne se présentera que sous forme d'un seul paramètre tout en véhiculant l'information complète.

Par ailleurs en Java, on peut aussi utiliser la classe toute faite "Vector".

Classement des tableaux selon les types de clés :

La "clé" est une information connue d'un tableau et permet de trouver la bonne case.

La clé est l'indice. Exemple : un tableau indicé de 1 à N.
La clé et l'indice sont liés par une fonction bijective simple : c'est une variante trivale du cas précédent. Exemple : un tableau commençant à 0.
La clé est un des champs de l'objet, et la table n'est pas triée (ou du moins n'est pas triée suivant cette clé). Exemple : nous avons un tableau d'articles, chaque "case" pointe vers un objet qui contient un numéro d'article et un total, la clé étant le numéro :

Pour conaître ou modifier le total de l'article n°175, il fau d'abord faire une recherche pour localiser la case où se trouve cet article.
La clé est un des champs de l'objet, et la table est triée suivant cette clé. Exemple : chaque "case" contient un numéro d'article et un total. Les numéros d'articles se présentent cette fois en ordre croissant et constituent toujours la clé.

De nouveau, une recherche est nécessaire avant toute intervention, mais cette recherche pourra être améliorée grâce au classement du tableau (recherche de dichotomique, par exemple).
La clé est un des champs de l'objet, et la table n'est pas triée; la table contient des "trous". Ici, les "trous" sont concrétisés par une valeur null (représentée par un point sur la figure).
Idem, avec table triée (sauf pour les éléments "trous" qui sont intercalés n'importe où entre les éléments triés).

Insertion dans une table non triée :

Dans les exemples, nous présenterons des algorithmes travaillant sur des tableaux d'entiers ou sur des tableaux d'objets.

Nous allons travailler sur base des classes TableauDArticles qui contiendront le tableau et le nombre d'éléments réellement présents dans cette table. Ce nombre d'éléments est la taille logique du tableau :

public class TableauDEntiers {
    public static final int MAX_ELEM = 30;
    int[] tab = new int[MAX_ELEM];
    int nbEntiers = 0;
}

public class TableauDArticles {
    public static final int MAX_ELEM = 30;
    Article[] tab = new Article[MAX_ELEM];
    int nbArticles = 0;
}

Nous donnons ici un premier exemple d’algorithme, en choisissant un cas extrêmement simple. Le but de cet exemple est essentiellement de montrer comment écrire proprement ce type d’algorithme : sous forme d’une méthode où l’on indique clairement les paramètres, avec commentaires Javadoc explicatifs, et en n’oubliant pas les tests de validité.

En cas d’impossibilité de l’insertion, la méthode renvoie cette information d’échec dans sa valeur de retour de type booléen : cette attitude est à adapter aux nécessités lorsqu’on implémente cet algorithme dans un programme réel (dans certains cas, il n’y a rien à faire en cas d’échec, dans d’autres, il suffira d’afficher un message à l’écran, dans d’autres encore, il faudra arrêter toute l’exécution du programme, etc.).

/**
* Insère un nouvel entier dans le Tableau
* @param elem l'entier à insérer
* @return faux si le tableau est plein, true sinon
*/
public boolean inserer (int elem) {
    if (nbEntiers == MAX_ELEM) {
        return false;
    }
    tab[nbEntiers] = elem;
    nbEntiers++;
    return true;
}

L’insertion décrite dans cet algorithme consiste simplement à insérer le nouvele entier après le dernier élément logique. Vu qu’en Java les tableaux commencent à l’indice 0, de façon assez commode le dernier élément logique est à l’indice nbEntiers – 1 et l’on fait donc l’insertion à l’indice nbEntiers.

L’inconvénient de cette méthode est qu’une fois le tableau plein on ne peut plus rien faire. Voici une méthode permettant d’augmenter la taille du tableau une fois celui-ci complètement rempli :

/**
* Insère un nouvel entier dans le Tableau
* Si la table est pleine, on double sa taille
* @param elem l'entier à insérer
*/
public boolean inserer (int elem) {
    if (nbEntiers == tab.length) {
        // Plus de place ? On double la taille du tableau
        int[] tmp = new int[tab.length * 2];
        for (int i = 0; i < nbEntiers; i++) {
            tmp[i] = tab[i];
        }
        tab = tmp;
    }
    tab[nbEntiers] = elem;
    nbEntiers++;
    return true;
}

Ici lorsque l’on détecte que le tableau est plein, on crée un deuxième tableau deux fois plus grand dans lequel on vient recopier les éléments du tableau original. Ensuite l’instruction tab = tmp remplace l’ancien tableau par le nouveau. Cela est possible car en Java les tableaux sont traités comme des objets et la table tab contient une référence vers le tableau. tab = tmp change donc uniquement les références.

Insertion dans une table triée :

Lors de cette insertion, nous devons conserver le caractère trié du tableau. Nous ne pouvons donc pas simplement insérer l’élément en dernière position.

Si la case prévue pour le nouvel élément est occupée, nous allons déplacé les éléments situés entre l’indice de la case occupée et l’indice du dernier élément. Ce déplacement ne pourra pas se faire d’un seul coup. Nous devrons les déplacer un à un en commençant par le dernier :

/**
* Insère un nouvel entier dans le tableau
* Les entiers sont triés par ordre croissant de numéro.
* @param elem l'entier à insérer
* @return false si le tableau est plein, true sinon
*/
public boolean inserer (int elem) {
    if (nbEntiers == MAX_ELEM) {
        return false;
    }
    int i = nbEntiers - 1;
    while (i >= 0 && tab[i] > elem) {
        tab[i + 1] = tab[i];
        i = i - 1;
    }
    tab[i + 1] = elem;
    nbEntiers++;
    return true;
}

Nous pourrions écrire un algorithme équivalent pour un tableau d’objets. La différence avec l’algorithme sur le tableau d’entiers est qu’ici nous devons explicitement aller chercher la clef des éléments avec la méthode getNumero() :

public class TableauDArticle {

    public static final int MAX_ARTICLES = 30;
    Article[] tabArticles = new Article[MAX_ARTICLES];
    int nbArticles = 0;

    /**
    * Insère un nouvel article dans le Tableau
    * Les articles sont triés par ordre croissant de numéro.
    * @param a l'article à Insérer
    * @return false si le tableau est plein, true sinon
    */
    public boolean inserer (Article a) {
        if (nbArticles == MAX_ARTICLES) {
            return false;
        }
        int i = nbArticles - 1;
        while (i > 0 && tabArticles[i].getNumero() > a.getNumero()) {
            tabArticles[i + 1] = tabArticles[i];
            i = i - 1;
        }
        tab[i + 1] = a;
        nbArticles++;
        return true;
    }
}

Recherche séquentielle dans une table triée :

/**
* Recherche si elem se trouve dans le tableau
* et renvoie son indice si nécessaire
* @param elem clef de l'élément cherché
* @return -1 si elem n'est pas présent, l'indice
* dans le tableau sinon
*/
public int chercherIndice (int elem) {
    if (nbEntiers == 0) {
        return -1;
    }
    int pos = 0;
    while (pos < nbEntiers - 1 && tab[pos] < elem) {
        pos++;
    }
    if (tab[pos] == elem) {
        return pos;
    } else {
        return -1;
    }
}

Recherche dichotomique dans une table triée :

Version 1 :

/**
* Recherche si elem se trouve dans le tableau
* et renvoie son indice si nécessaire
* @param elem clef de l'élément cherché
* @return -1 si elem n'est pas présent, l'indice
* dans le tableau sinon
*/
public int chercherIndiceDicho (int elem) {
    if (nbEntiers == 0) {
        return -1;
    }
    int debut = 0, fin = nbEntiers - 1;
    int milieu;
    while (debut <= fin) {
       milieu = (debut + fin) / 2;
       if (tab[milieu] == elem) {
        debut = milieu + 1;
       } else {
        fin = milieu - 1;
       }
    }
    return -1;
}

Version 2 :

public int chercherIndiceDicho2 (int elem) {
    if (nbEntiers == 0) {
        return -1;
    }
    int debut = 0, fin = nbEntiers - 1;
    int milieu = 0;
    while (debut < fin) {
        milieu = (debut + fin) / 2;
        if (tab[milieu] >= elem) {
            fin = milieu;
        } else {
            debut = milieu + 1;
        }
    }
    if (tab[milieu] == elem) {
        return fin;
    } else {
        return -1;
    }
}

Intuitivement, on pourrait être tenté de croire que rechercheDichoomique1 est plus efficace : en effet, si on tombe directement (ou en cours de traitement) sur l’élément cherché lui-même, on sort directement de la répétitive : on gagne du temps dans ce cas-là.

Mais... y gagne-t-on en moyenne ?

La réponse est sûrement affirmative pour un traitement humain (recherche de la bonne fiche dans un tas de fiches cartonnées bien triées), car, pour nous, il est aussi rapide (voire plus rapide !) de trouver quelle relation est correcte parmi "A > B", "A = B", et "A < B" que de trouver quelle relation est correcte parmi "A >= B" et "A <= B". Pour un ordinateur cependant, cette dernière tâche demande une seule comparaison, alors que la première en demande deux (qui se présentent comme deux "SI" imbriqués) ! Il faut donc regarder de plus près ce quel'on gagne et ce que l'on perd.

Conclusion : si ce sont les comparaisons qui prennent le plus de temps, rechercheDichotomique2 est presque 2 fois plus rapide que rechercherDichotomique1 (en moyenne), bien que ces deux algorithmes soient tous deux en O(log n); si les comparaisons sont moins coûteuses que la simple manipulation de la répétitive (par exemple si les clés sont de simples entiers), le gain es moins flagrant mais reste net.

Algorithmes de tri :

Un algorithme de tri interne a pour but de trier le contenu d'une table unidimensionnelle dans la mémoire centrale de l'ordinateur (à l'opposé d'un tri externe, qui trie des données situées à l'extérieur de l'ordinateur, donc dans un fichier).

Le verbe "trier" est utilisé ici dans le sens où on le rencontre dans le jargon des informaticiens; le verbe "ordonner" serait plus approprié, puisqu'il s'agit en fait de modifier l'ordre de rangement des éléments dans la table de façon à les placer en ordre croissant (ou décroissant d'une certaine clé.

On essaie en général que ces algorithmes n’utilisent pas d’espace supplémentaire par rapport à la table elle-même, à l’exception d’une ou deux zones servant à stocker temporairement un élément de la table. On ne travaille donc pas sur une seconde table !

Un algorithme de tri est dit stable si l'ordre relatif de deux éléments ayant même valeur de clé est toujours conservé, et instable dans le cas contraire. Le caractère de stabilité d'un tri est essentiel dans certaines applications, et inintéressant dans d'autres : l'informaticien saura tenir compte de ce critère dans le choix d'un algorithme !

Le tri par insertion :

Cet algorithme part du fait que la sous-table constituée du seul premier élément est trivialement déjà triée (comme toute table d’un seul élément !). Ensuite, il considère successivement chacun des éléments du deuxième jusqu’au dernier, il insère chacun d’eux dans la partie de la table déjà triée, celle-ci gonflant progressivement jusqu’à recouvrir la table complète. S’il y a N éléments à trier, cet algorithme effectue donc N – 1 opérations d’insertion dans une table triée.

// Les éléments 0 ... i-1 sont triés
for (int i = 1; i < nbEntiers - 1; i++) {
    int elem = tab[i] // élément à insérer
    int j = i - 1;
    while (j >= 0 && tab[j] > elem) {
        tab[j + 1] = tab[j];
        j = j - 1;
    }
    tab[j + 1] = elem;
}

Cet algorithme de tri est stable.

Sa complexité est en O(N²), le nombre de comparaisons et le nombre de déplacements étant tous deux en moyenne approximativement égaux à N²/4.

Le tri par sélection (ou extraction) :

L’idée est encore plus simple : on cherche d’abord dans toute la table quel est le plus petit élément, et on vient le placer en première position en le permutant avec celui qui s’y trouve. Ensuite, on recommence pour le plus petit de ceux qui restent, et on le place en deuxième position. Et ainsi de suite jusqu’à l’avant-dernier. Le dernier est forcément déjà bien placé quand on y arrive.

// Le tableau 0 ... i - 1 est trié
// Tous les éléments en i ... nbEntiers - 1
// sont plus grands que tab[i - 1]
for (int i = 0; i < nbEntiers - 1; i++) {
    // On va chercher le min dans le tableau i ... nbEntiers - 1
    int indiceMin = i;
    for (int j = i + 1; j < nbEntiers; j++) {
        if (tab[j] < tab[indiceMin]) {
            indiceMin = j;
        }
    }
    // On échange le min avec l'élément en pos i
    int tmp = tab[i];
    tab[i] = tab[indiceMin];
    tab[indiceMin] = tmp;
}

Cet algorithme n’est pas stable, comme on peut aisément s’en assurer. En effet, lorsque l’on échange deux éléments, on perd l’ordre entre les ex-aequos.

Sa complexité est en O(N²), mais seules les opérateurs de comparaison sont effectivement de cette complexité, tandis que le nombre de déplacements d'éléments est seulement en O(N) : cet algorithme sera donc à privilégier lorsque les éléments seront de grande taille, mais les clés petites.

Le tri-bulles (Bubble-sort) :

Ce tri est, à juste titre, considéré comme le plus lent des tris classiques : il est donc à éviter à tout prix, sauf dans des situations particulières (tables très petites par exemple).

On n’y compare chaque fois que deux éléments consécutifs, et on les permute si leur ordre relatif est incorrect. En répétant cette opération un très grand nombre de fois, on finit par obtenir une table ordonnée.

// Le tableau i + 1 ... nbEntiers - 1 est trié
for (int i = nbEntiers - 1; i >= 1; i--) {
    // inverser tous les éléments consécutifs qui ne
    // sont pas dans le bon ordre
    for (int j = 1; j <= i; j++) {
        if (tab[j + 1] > tab[j]) {
            int tmp = tab[j];
            tab[j] = tab[j + 1];
            tab[j + 1] = tmp;
        }
    }
}

Cet algorithme est stable. Sa complexité est en O(N²). Au total : environ N passes, et à chacune en moyenne N/2 comparaisons et N/4 échanges, soit en tout environ N²/2 comparaisons et 3N²/4 déplacements.

Les tableaux à plusieurs dimensions :

Dans de nombreux langages, en particulier en Java, une table à plusieurs dimensions n’est pas un nouveau concept. En effet, elle n’est rien d’autre qu’une table à une dimension, mais dont les éléments sont eux-mêmes des tables.

L'organisation dans la mémoire de l'ordinateur peut être deux espèces :

Dans un langage où les tableaux sont accessibles directement, sans l'intermédiaire de "pointeurs", on a une organisation en mémoire selon les schémas suivants :

En particulier, on pourrait avoir la situation où le "n'importe quoi" est à son tour un tableau :
Dans des langages comme le Java, où les tableaux sont accessibles via des "pointeurs", la situation est la suivante :

Dans les deux cas, on pourra écrire :

Parfois, la notation condensée t[i, j] peut t[i][j], ce qui donne l'illusion d'un rôle similaire pour les deux indices.

La représentation d'un tableau bidimensionnel sous forme de lignes et de colonnes n'est qu'une facilité de présentation pour l'oeil humain. Souvent, on convient que le premier indice est le numéro de la ligne et le second celui de la colonne, mais ce n'est qu'une pure convention, qui n'intervient en rien dans la définition du langage de programmation lui-même.

En Java :

Soit la déclaration suivante :
```
int[][] matrice; // tableau de tableaux d'entiers
```
La variable matrice est un tableau à une dimension d'éléments qui sont du type int[], c'est-à-dire eux-mêmes des tableaux à une dimension de nombres entiers. Supposons que cette variable soit construite par l'instruction :
```
matrice = new int[5][];
```
On a ainsi construit un tableau de 5 "cases" qui contiennent en fait 5 "pointeurs" vers des objets non encore alloués, qui seront des tableaux d'entiers.

On peut alors allouer chaucun de ces 5 tableaux. Il y a deux cas :
1. Ces 5 tableaux d'entiers ont la même taille :
```
for (int i = 0; i < 5; i++) {
    matrice[i] = new int[7];
}
```
  On a ainsi créé au total un tableau de 5 éléments qui sont eux-mêmes des tableaux de 7 entiers. On peut voir cela comme un tableau à deux dimensions, ou encore une "matrice" 5x7. (N.B. Il s'agit ici d'une "matrice à 5 lignes et 7 colonnes", selon la convention fréquente; mais ce n'est qu'une convention de considérer que le premier indice est l'indice de ligne et le second indice celui de colonne : l'inverse est tout aussi admissible !).
  
  La construction du tableau complet peut aussi se faire en un coup :
```
matrice = new int[5][7];
```
  Les éléments de la matrice seront désignés dans les instructions par matrice[ligne][colonne] où ligne et colonne peuvent être remplacées par des expressions quelconques fournissant des nombres entiers.
2. Ces 5 tableaux ont des tailles différentes. On ne parlera alors plus de "matrice" ou de "tableau à plusieurs dimensions" mais simplement de "tableau de tableaux".
  
  Exemple :
```
int[][] tabTab = new int[5][];
tabTab[0] = new int[7];
tabTab[1] = new int[9];
tabTab[2] = new int[2];
tabTab[3] = new int[15];
tabTab[4] = new int[7];
```
  On pourra ainsi utiliser les variables entières tabTab[0][4] et tabTab[3][14] mais pas tabTab[0][14].
  
  Tout ceci peut être étendu à des dimensions plus élevées. Exemple :
```
float[][][] tableauTridimensionnel = new float[5][10][5];
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 5; k++) {
            tableauTridimensionnel[i][j][k] = 0.0;
        }
    }
}
```
  Tant conceptuellement que techniquement, tout ce qui a été dit à propos des tableaux à deux dimensions (ou "matrices") peut s'étendre à un nombre arbitraire de dimensions. Seule la représentation graphique en est plus malaisée : cela est uniquement dû au caractère dimensionnel des écrans et feuilles de papier (ainsi que de notre rétine !).
  
  Voici un exemple :
  
  L'horaire de cours de l'Institut Paul Lambin, pour lequel on va supposer pour simplifier tous les cours débutent à une heure "ronde" (8h, 9h, 10h, ...), peut être représenté comme :
  - Un tableau de deux éléments correspondant aux deux semestres, constitués chacun de :
  - Un tableau de 5 éléments correspondant aux 5 sections, chacun étant constitué de :
  - Un tableau de 3 éléments correspondant aux 3 années, chacun étant constitué de :
  - Un tableau de X éléments correspondant aux X séries de cette section et de cette année, chacun étant constitué de :
  - Un tableau de 5 éléments correspondant aux 5 jours de la semaine, chacun étant constitué de :
  - Un tableau de 11 éléments, correspondant aux 11 heures de la journée (de 8h à 19h), chacun étant constitué de :
  - Un nom de cours, un numéro de local, un professeur.
  Nous pouvons donc utiliser un tableau à 6 dimensions, ou plutôt un "tableau de tableaux de tableaux de tableaux de tableaux".
  
  Par exemple :
```
int [] [] [] [] [] [] horaire = new int [0] [4] [0] [7] [2] [10];
```
  Désignera l'activité, durantle premier semestre (0), des étudiants de la série 7 de 1^ère (0) informatique (4) le mercredi (jour n°2) à 17h (heure n°10).
  
  Et pour imprimer tout l'horaire de cette série en 5 colonnes correspondant aux 5 jours et en 11 lignes correspondant aux 11 heures, le tout sur deux pages correspondant aux deux semestres, on peut écrire :
```
for (int semestre = 0; semestre < 2; semestre++) {

    saut_de_page;
    imprimer("semestre numéro "+ (semestre + 1));

    for (int jour = 0; jour < 5; jour++) {
        imprimer(nomDuJour[jour]); // titre colonnes
        passer_à_la_ligne;

        for (int heure = 0; heure < 11; heure++) {
            imprimer(heure + 8); // titre lignes
            for (int jour = 0; jour < 5; jour++) {
                imprimer(horaire[semestre][4][0][7][jour][heure]);
                passer_à_la_ligne;
            }
        }
    }
```

Résumé d'Algo et d'APOO :

import java.util.Iterator;

public class NomDeLaClasse extends ClasseParent implements Interface1, Interface2 {

    // dÃ©clarer des attributs d'une classe en private
    // remplacer typeDeMaVariable par un type primitif (int, char, float, boolean)
    // ou par un type référence (String, Object, ...)
    // le nom d'une variable utilise le camelCase (première lettre de chaque mot en
    // Majuscules) et ne possède
    // ni accents ni caractères spéciaux ('_' par exemple)
    private typeDeMaVariable maVariable;
    private typeDeMaVariable[] monTableau;
    private int tailleLogique;
    // une constante est toujours static et final et en MAJUSCULES
    private static final typeDeMaVariable MA_CONSTANTE;

    // Le constructeur de la classe est public et initialise tous les attributs de
    // la classe lors de l'initialisation
    // il porte le même nom que la classe et n'a pas de typeDeRetour
    public NomDeLaClasse (typeDeMaVariable maVariable, int taillePhysique) {
        // this permet de différencier l'attribut de la classe au paramètre
        this.maVariable = maVariable;
        this.monTableau = new typeDeMaVariable[taillePhysique];
        this.tailleLogique = 0;
    }
    
    // un getter est un accesseur
    public typeDeMaVariable getMaVariable() {
        return maVariable;
    }
    
    // un setter est un modificateur
    public void setMaVariable(typeDeMaVariable maVariable) {
        this.maVariable = maVariable;
    }
    
    public boolean ajouterElem(typeDeMaVariable elem) {
        int taillePhysique = monTableau.length;
        // test si le tableau est rempli
        if (taillePhysique == tailleLogique) {
            return false;
        }
        monTableau[tailleLogique] = elem;
        tailleLogique++;
        return true;
    }
    
}

Cryptage du RSA :

Dans le fichier "MathException.java" :

package crypto;

public class MathException extends RuntimeException {

    /**
    * 
    */
    private static final long serialVersionUID = 1L;

    public MathException() {
        super();
    }

    public MathException(String message) {
        super(message);
    }

}

Dans le fichier "Zn.java" :

package crypto;

/*
* Classe représentant Z_n : l'ensemble des entiers modulo n
*/
public class Zn {

    private long n;

    public Zn(long n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n's less that 0 !");
        }
        this.n = n;
    }

    // renvoie le cardinal de Z_n
    public long getN() {
        return n;
    }

    // renvoie true si l'entier x appartient à Z_n, false sinon
    public boolean contient(long x) {
        return x < n && x >= 0;
    }

    // calcule a + b dans Z_n
    // renvoie une IllegalArgumentException si a ou b n'appartient pas à Z_n
    public long plus(long a, long b) {
        if (!contient(a) || !contient(b)) {
            throw new IllegalArgumentException("nor a or b are in Zn");
        }
        return (a + b) % n;
    }

    // calcule a * b dans Z_n
    // renvoie une IllegalArgumentException si a ou b n'appartient pas à Z_n
    public long fois(long a, long b) {
        if (!contient(a) || !contient(b)) {
            throw new IllegalArgumentException("nor a or b are in Zn");
        }
        return (a * b) % n;
    }

    // calcule l'inverse de x dans Z_n en utilisant l'algorithme d'Euclide étendu
    // lance une IllegalArgumentException si x n'est pasdans Z_n
    // lance une MathException si x n'admet pas d'inverse dans Z_n
    public long inverse(long x) { // TODO
        if (!contient(x)) {
            throw new IllegalArgumentException("x's not in Zn");
        }
        if (x == 0) {
            throw new MathException("x cannot be 0 because 0 is not invertible");
        }
        long vi0 = 0;
        long vi1 = 1;
        long lastVi0 = 0;
        long lastVi1 = 1;
        long ri0 = n;
        long ri1 = x;
        long qi = ri0 / ri1; // initiate Qi
        long ri = ri0 % ri1; // initiate Ri
        while (n > 1) {
            // viGen2 = n
            // n = ri;
            
            // z swap value
            long temp = vi0;
            vi0 = lastVi1 - qi * vi0; // put value lastVi - 2 + (-Qi * ViGen-2) in ViGen-2
            lastVi1 = temp;
            
            // z swap value
            temp = vi1;
            vi1 = lastVi0 - qi * vi1; // do same for ViGen-1
            lastVi0 = temp;
        }
        if (ri == 1) {
            if (vi0 < 0) {
                return (n - Math.negateExact(vi0)) % n;
            }
            return vi0;
        } else {
            throw new MathException("x is not invertible");
        }
    }
    
    // calcule x^a dans Z_n en utilisant l'algorithme récursif d'exponentiation rapide modulaire
    // lance une IllegalArgumentException si x n'est pas dans Z_n ou si l'exposant est strictement négatif
    // lance une MathException si x  = 0 et a = 0 (0^0 est une indetermination)
    public long puissance (long x, long a) {
        if (a == 0 && x == 0) {
            throw new MathException("indetermined case0^0");
        }
        if (!contient(x) || a < 0) {
            throw new IllegalArgumentException("either x is not in Zn or a is negative !");
        }
        if (a % 2 != 0) { // if the exponen's odd
            long p = puissance(x, (a - 1) / 2);
            return x * p * p;
        } else {
            long p = puissance(x, a / 2);
            return p * p;
        }
    }
}

Dans le fichier "TestZn.java" :

package crypto;

import java.lang.reflect.Field;
import java.util.Scanner;

public class TestZn {

    private static Class<Zn> classe = Zn.class;
    private static Field cardinal;
    private static final Scanner scanner = new Scanner(System.in);
    private static final String[] NOMS_METHODES = { "du constructeur Zn(int n)", "de la méthode contient",
            "de la méthode plus", "de la méthode fois", "de la méthode inverse", "de la méthode puissance" };

    public static void main(String[] args) throws IllegalAccessException {
        Field[] champs = classe.getDeclaredFields();
        for (Field f : champs) {
            if (f.getType() == long.class) {
                if ("n".equals(f.getName())) {
                    cardinal = f;
                    cardinal.setAccessible(true);
                }
            }
        }

        System.out.println("*********************************");
        System.out.println("Programme Test pour la classe Zn ");
        System.out.println("*********************************");

        int choix = 0;
        while (true) {
            for (int i = 0; i < NOMS_METHODES.length; i++) {
                System.out.println((i + 1) + " -> Test " + NOMS_METHODES[i]);
            }
            System.out.println("autre -> Quitter");

            choix = scanner.nextInt();
            boolean testOK;
            switch (choix) {
            case 1:
                testOK = testConstructeur();
                break;
            case 2:
                testOK = testContient();
                break;
            case 3:
                testOK = testPlus();
                break;
            case 4:
                testOK = testFois();
                break;
            case 5:
                testOK = testInverse();
                break;
            case 6:
                testOK = testPuissance();
                break;
            default:
                return;
            }
            if (testOK) {
                System.out.println("Le test " + NOMS_METHODES[choix - 1] + " a réussi.");
            } else {
                System.out.println("Le test " + NOMS_METHODES[choix - 1] + " a échoué.");
            }
            System.out.println();
        }
    }

    private static boolean testConstructeur() throws IllegalAccessException {

        Zn zn;

        System.out.println("Test 1");
        System.out.println();

        try {
            zn = new Zn(0);
            System.out.println("Il fallait une exception car n = 0");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancer la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            zn = new Zn(-1);
            System.out.println("Il fallait une exception car n est négatif");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancer la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        try {
            long exemple = 5;
            zn = new Zn(exemple);
            long n = cardinal.getLong(zn);
            if (n != exemple) {
                System.out.println("Le cardinal deZn n'est pas bon : attendu : " + exemple + " reçu : " + n);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception");
        }

        return true;
    }

    private static boolean testContient() throws IllegalAccessException {

        if (!testConstructeur()) {
            System.out.println("Il faut d'abord écrire le constructeur de manière correcte.");
            return false;
        }

        System.out.println("Constructeur OK");
        System.out.println("Début des tests de la méthode contient");
        System.out.println();
        System.out.println("Test 1");
        System.out.println();

        long exemple = 32;
        Zn zn = new Zn(exemple);
        if (zn.contient(exemple)) {
            System.out.println(exemple + " n'appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        exemple = 33;
        if (zn.contient(exemple)) {
            System.out.println(exemple + " n'appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        exemple = 355;
        if (zn.contient(exemple)) {
            System.out.println(exemple + " n'appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        exemple = -1;
        if (zn.contient(exemple)) {
            System.out.println(exemple + " n'appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        exemple = -32;
        if (zn.contient(exemple)) {
            System.out.println(exemple + " n'appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        exemple = 0;
        if (!zn.contient(exemple)) {
            System.out.println(exemple + " appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 7");
        System.out.println();

        exemple = 1;
        if (!zn.contient(exemple)) {
            System.out.println(exemple + " appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 8");
        System.out.println();

        exemple = 31;
        if (!zn.contient(exemple)) {
            System.out.println(exemple + " appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        }

        return true;
    }

    private static boolean testPlus() throws IllegalAccessException {
        if (!testConstructeur()) {
            System.out.println("Il faut d'abord écrire le constructeur de manière correcte.");
            return false;
        }

        System.out.println("Constructeur OK");
        System.out.println("Début des tests de la méthode plus");
        System.out.println();
        System.out.println("Test 1");
        System.out.println();

        Zn zn = new Zn(8);
        long somme;

        try {
            somme = zn.plus(-1, 2);
            System.out.println("Il fallait une exception car a = -1 < 0");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            somme = zn.plus(8, 2);
            System.out.println("Il fallait une exception car a = 8 >= n = 8");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        try {
            somme = zn.plus(2, -1);
            System.out.println("Il fallait une exception car b = -1 < 0");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        try {
            somme = zn.plus(2, 8);
            System.out.println("Il fallait une exception car b = 8 >= n = 8");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        try {
            somme = zn.plus(-1, 2);
            System.out.println("Il fallait une exception car a = -1 < 0");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        try {
            somme = zn.plus(0, 3);
            if (somme != 3) {
                System.out.println("(0 + 3) mod 8 = 3 | reçu : (0 + 3) mod 8 = " + somme);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 7");
        System.out.println();

        try {
            somme = zn.plus(5, 0);
            if (somme != 5) {
                System.out.println("(5 + 0) mod 8 = 5 | reçu : (5 + 0) mod 8 = " + somme);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 8");
        System.out.println();

        try {
            somme = zn.plus(5, 2);
            if (somme != 7) {
                System.out.println("(5 + 2) mod 8 = 7 | reçu : (5 + 2) mod 8 = " + somme);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 9");
        System.out.println();

        try {
            somme = zn.plus(5, 7);
            if (somme != 4) {
                System.out.println("(5 + 7) mod 8 = 4 | reçu : (5 + 7) mod 8 = " + somme);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        return true;
    }

    private static boolean testFois() throws IllegalAccessException {
        if (!testConstructeur()) {
            System.out.println("Il faut d'abord écrire le constructeur de manière correcte.");
            return false;
        }

        System.out.println("Constructeur OK");
        System.out.println("Début des tests de la méthode fois");
        System.out.println();
        System.out.println("Test 1");
        System.out.println();

        Zn zn = new Zn(6);
        long produit;

        try {
            produit = zn.fois(-1, 2);
            System.out.println("Il fallait une exception car a = -1 < 0");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            produit = zn.fois(6, 2);
            System.out.println("Il fallait une exception car a = 6 >= n = 6");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        try {
            produit = zn.fois(2, -1);
            System.out.println("Il fallait une exception car b = -1 < 0");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        try {
            produit = zn.fois(2, 6);
            System.out.println("Il fallait une exception car b = 6 >= n = 6");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        try {
            produit = zn.fois(-1, 2);
            System.out.println("Il fallait une exception car a = -1 < 0");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        try {
            produit = zn.fois(0, 3);
            if (produit != 0) {
                System.out.println("(0 * 3) mod 6 = 0 | reçu : (0 * 3) mod 6 = " + produit);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 7");
        System.out.println();

        try {
            produit = zn.fois(5, 0);
            if (produit != 0) {
                System.out.println("(5 * 0) mod 6 = 0 | reçu : (5 * 0) mod 6 = " + produit);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 8");
        System.out.println();

        try {
            produit = zn.fois(1, 2);
            if (produit != 2) {
                System.out.println("(1 * 2) mod 6 = 2 | reçu : (1 * 2) mod 6 = " + produit);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 9");
        System.out.println();

        try {
            produit = zn.fois(5, 3);
            if (produit != 3) {
                System.out.println("(5 * 3) mod 6 = 3 | reçu : (5 * 3) mod 6 = " + produit);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 10");
        System.out.println();

        try {
            produit = zn.fois(5, 5);
            if (produit != 1) {
                System.out.println("(5 * 5) mod 6 = 1 | reçu : (5 * 5) mod 6 = " + produit);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        return true;
    }

    private static boolean testInverse() throws IllegalAccessException {
        if (!testConstructeur()) {
            System.out.println("Il faut d'abord écrire le constructeur de manière correcte.");
            return false;
        }

        System.out.println("Constructeur OK");
        System.out.println("Début des tests de la méthode inverse");
        System.out.println();
        System.out.println("Test 1");
        System.out.println();

        Zn zn = new Zn(21);
        long inverse;
        long exemple;

        try {
            exemple = -1;
            inverse = zn.inverse(exemple);
            System.out.println("Il fallait lancer une IllegalArgumentException car " + exemple
                    + " n'appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            exemple = 21;
            inverse = zn.inverse(exemple);
            System.out.println("Il fallait lancer une IllegalArgumentException car " + exemple
                    + " n'appartient pas à Z_" + cardinal.getLong(zn));
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        try {
            exemple = 0;
            inverse = zn.inverse(exemple);
            System.out.println("Il fallait lancer une MathException car " + exemple + " n'a pas d'inverse dans Z_"
                    + cardinal.getLong(zn));
            return false;
        } catch (MathException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        try {
            exemple = 14;
            inverse = zn.inverse(exemple);
            System.out.println("Il fallait lancer une MathException car " + exemple + " n'a pas d'inverse dans Z_"
                    + cardinal.getLong(zn));
            return false;
        } catch (MathException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        exemple = 1;
        try {
            inverse = zn.inverse(exemple);
            if (inverse != 1) {
                System.out.println(
                        "L'inverse de " + exemple + " dans Z_" + cardinal.getLong(zn) + " est 1. Reçu : " + inverse);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception car " + exemple + " a un inverse dans Z_"
                    + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        exemple = 2;
        try {
            inverse = zn.inverse(exemple);
            if (inverse != 11) {
                System.out.println(
                        "L'inverse de " + exemple + " dans Z_" + cardinal.getLong(zn) + " est 11. Reçu : " + inverse);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception car " + exemple + " a un inverse dans Z_"
                    + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 7");
        System.out.println();

        exemple = 7;
        zn = new Zn(279180);
        try {
            inverse = zn.inverse(exemple);
            if (inverse != 39883) {
                System.out.println("L'inverse de " + exemple + " dans Z_" + cardinal.getLong(zn) + " est 39883. Reçu : "
                        + inverse);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception car " + exemple + " a un inverse dans Z_"
                    + cardinal.getLong(zn));
            return false;
        }

        System.out.println();
        System.out.println("Test 8");
        System.out.println();

        zn = new Zn(26);
        try {
            inverse = zn.inverse(exemple);
            if (inverse != 15) {
                System.out.println(
                        "L'inverse de " + exemple + " dans Z_" + cardinal.getLong(zn) + " est 15. Reçu : " + inverse);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception car " + exemple + " a un inverse dans Z_"
                    + cardinal.getLong(zn));
            return false;
        }

        return true;
    }

    private static boolean testPuissance() throws IllegalAccessException {
        if (!testConstructeur()) {
            System.out.println("Il faut d'abord écrire le constructeur de manière correcte.");
            return false;
        }

        System.out.println("Constructeur OK");
        System.out.println("Début des tests de la méthode puissance");
        System.out.println();
        System.out.println("Test 1");
        System.out.println();

        Zn zn = new Zn(21);
        long puissance;

        try {
            puissance = zn.puissance(-1, -1);
            System.out.println("Il fallait lancer une IllegalArgumentException car -1 n'appartient pas à Z_"
                    + cardinal.getLong(zn));
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            puissance = zn.puissance(21, 1);
            System.out.println("Il fallait lancer une IllegalArgumentException car 21 n'appartient pas à Z_"
                    + cardinal.getLong(zn));
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        try {
            puissance = zn.puissance(2, -1);
            System.out.println("Il fallait lancer une IllegalArgumentException car l'exposant est négatif");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        try {
            puissance = zn.puissance(0, 0);
            System.out.println("Il fallait lancer une MathException car 0^0 est indéterminé.");
            return false;
        } catch (MathException e) {

        } catch (Exception e) {
            System.out.println("Vous n'avez pas lancé la bonne exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        try {
            puissance = zn.puissance(0, 2);
            if (puissance != 0) {
                System.out.println("0^2 mod 21 = 0 | reçu : 0^2 mod 21 = " + puissance);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception 0^2 mod 21 = 0.");
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        try {
            puissance = zn.puissance(2, 0);
            if (puissance != 1) {
                System.out.println("2^0 mod 21 = 1 | reçu : 2^0 mod 21 = " + puissance);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception 2^0 mod 21 = 1.");
            return false;
        }

        System.out.println();
        System.out.println("Test 7");
        System.out.println();

        try {
            puissance = zn.puissance(2, 5);
            if (puissance != 11) {
                System.out.println("2^5 mod 21 = 11 | reçu : 2^5 mod 21 = " + puissance);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception 2^5 mod 21 = 11.");
            return false;
        }

        System.out.println();
        System.out.println("Test 8");
        System.out.println();

        zn = new Zn(280453);
        try {
            puissance = zn.puissance(60521, 39883);
            if (puissance != 38597) {
                System.out.println("60521^39883 mod 280453 = 38597 | reçu : 60571^39883 mod 280453 = " + puissance);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception 60521^39883 mod 280453 = 38597.");
            return false;
        }

        System.out.println();
        System.out.println("Test 9");
        System.out.println();

        try {
            long p = 69073;
            long q = 69389;
            long puissanceCorrecte = 4133696652l;
            zn = new Zn(p * q);
            puissance = zn.puissance(2011407, 5);
            if (puissance != puissanceCorrecte) {
                System.out.println(
                        "2011407^5 mod 4792906397 = 4133696652  | reçu : 2011407^5 mod 4792906397 = " + puissance);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception 2011407^5 mod 4792906397 = 4133696652.");
            return false;
        }

        return true;
    }

}

Dans le fichier "RSAClefPrivee.java" :

package crypto;

/*
* Classe représentant une clef privée de codage RSA
*/
public class RSAClefPrivee {

    private long d;
    private Zn zn;

    // crée une nouvelle clef privée (d, p, q)
    public RSAClefPrivee(long d, long p, long q) {
        zn = new Zn(p * q);
        this.d = d;
    }

    // renvoie une String représentant le message M décodé par this
    // lance une IllegalArgumentException si M n'est pas dans zn
    public String decoder(long M) {
        if (!zn.contient(M)) {
            throw new IllegalArgumentException("M n'est pas dans z_n");
        }
        return convertir(zn.puissance(M, d));
    }

    // converti en texte l'entier m
    public static String convertir(long m) {
        long x = m;
        String texte = "";
        while (x != 0) {
            char lettre = (char) (x % 100 + 64);
            texte = lettre + texte;
            x /= 100;
        }
        return texte;
    }

}

Dans le fichier "RSAClefPublique.java" :

package crypto;

/*
* Classe représentant une clef publique de codage RSA
*/
public class RSAClefPublique {

    private long e;
    private Zn zn;

    // crée une nouvelle clef publique (e,n)
    public RSAClefPublique(long e, long n) {
        this.e = e;
        zn = new Zn(n);
    }

    // renvoie un entier représentant message codé par this.
    // lance une IllegalArgumentException si message est null ou vide,
    // si l'entier représentant message n'est pas dans zn
    public long coder(String message) {
        // TODO
        if (message == null || message.isEmpty()) {
            throw new IllegalArgumentException("Le message est null ou vide !");
        }
        if (!zn.contient(e)) {
            throw new IllegalArgumentException("L'entier 'e' représentant le message n'est pas dans z_n");
        }
        long m = convertir(message);
        return zn.puissance(m, e);
    }

    // converti le String texte en un nombre entier
    public static long convertir(String texte) {
        long m = 0;
        for (char c : texte.toCharArray()) {
            m = 100 * m + (int) c - 64;
        }
        return m;
    }

}

Pour le fichier "TestRSAClefs.java" :

package crypto;

import java.util.Scanner;

public class TestRSAClefs {

    private static final Scanner scanner = new Scanner(System.in);
    private static final String[] NOMS_METHODES = { "de la méthode coder de la classe RSAClefPublique",
            "de la méthode decoder de la classe RSAClefPrivee" };

    public static void main(String[] args) throws IllegalAccessException {

        System.out.println("*****************************************************************");
        System.out.println("Programme Test pour les classes RSAClefPublique et RSAClefPrivee ");
        System.out.println("*****************************************************************");

        int choix = 0;
        while (true) {
            for (int i = 0; i < NOMS_METHODES.length; i++) {
                System.out.println((i + 1) + " -> Test " + NOMS_METHODES[i]);
            }
            System.out.println("autre -> Quitter");

            choix = scanner.nextInt();
            boolean testOK;
            switch (choix) {
            case 1:
                testOK = testCoder();
                break;
            case 2:
                testOK = testDecoder();
                break;
            default:
                return;
            }
            if (testOK) {
                System.out.println("Le test " + NOMS_METHODES[choix - 1] + " a réussi.");
            } else {
                System.out.println("Le test " + NOMS_METHODES[choix - 1] + " a échoué.");
            }
            System.out.println();
        }
    }

    private static boolean testCoder() throws IllegalAccessException {

        long M;

        RSAClefPublique cp = new RSAClefPublique(27, 598153);

        System.out.println("Test 1");
        System.out.println();

        try {
            String texte = "null";
            M = cp.coder(texte);
            System.out.println("Il fallait une IllegalArgumentException car le texte est null !");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e2) {
            System.out.println("Vous n'avez pas lancé la bonne exception.");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            String texte = "";
            M = cp.coder(texte);
            System.out.println("Il fallait une exception car le texte est vide!");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e2) {
            System.out.println("Vous n'avez pas lancé la bonne exception.");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        try {
            String texte = "GOUUUU";
            M = cp.coder(texte);
            System.out.println("Il fallait une exception car le texte est trop grand!");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e2) {
            System.out.println("Vous n'avez pas lancé la bonne exception.");
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        try {
            String texte = "GO";
            M = cp.coder(texte);
            if (M != 418483) {
                System.out.println("Texte : GO : codé attendu : 418483 | reçu : " + M);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        cp = new RSAClefPublique(39883, 280453);
        try {
            String texte = "FEU";
            M = cp.coder(texte);
            if (M != 38597) {
                System.out.println("Texte : FEU : codé attendu : 38597 | reçu : " + M);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        cp = new RSAClefPublique(5, 204255253);
        try {
            String texte = "BOUM";
            M = cp.coder(texte);
            if (M != 90252728) {
                System.out.println("Texte : BOUM : codé attendu : 38597 | reçu : " + M);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        return true;
    }

    private static boolean testDecoder() throws IllegalAccessException {

        String texteAttendu;
        String texte;

        System.out.println("Test 1");
        System.out.println();

        RSAClefPrivee cp = new RSAClefPrivee(176755, 587, 1019);

        try {
            long M = -1;
            texte = cp.decoder(M);
            System.out.println("Il fallait une IllegalArgumentException car le message est negatif !");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e2) {
            System.out.println("Vous n'avez pas lancé la bonne exception.");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            long M = 598153;
            texte = cp.decoder(M);
            System.out.println("Il fallait une exception car le message est trop grand.");
            return false;
        } catch (IllegalArgumentException e) {

        } catch (Exception e2) {
            System.out.println("Vous n'avez pas lancé la bonne exception.");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        try {
            long M = 418483;
            texte = cp.decoder(M);
            texteAttendu = "GO";
            if (!texte.equals(texteAttendu)) {
                System.out.println("Texte attendu : " + texteAttendu + " | reçu : " + texte);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        cp = new RSAClefPrivee(7, 283, 991);
        try {
            long M = 38597;
            texte = cp.decoder(M);
            texteAttendu = "FEU";
            if (!texte.equals(texteAttendu)) {
                System.out.println("Texte attendu : " + texteAttendu + " | reçu : " + texte);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        cp = new RSAClefPrivee(122536001, 14107, 14479);

        try {
            long M = 90252728;
            texte = cp.decoder(M);
            texteAttendu = "BOUM";
            if (!texte.equals(texteAttendu)) {
                System.out.println("Texte attendu : " + texteAttendu + " | reçu : " + texte);
                return false;
            }
        } catch (Exception e) {
            System.out.println("Il ne fallait pas d'exception");
            return false;
        }

        return true;
    }

}

Pour le fichier "CodageRSA.java" :

package crypto;

import java.util.HashMap;

public class CodageRSA {

    private RSAClefPrivee clefPrivee;
    private RSAClefPublique clefPublique;
    private String proprietaire;
    private static final HashMap<String, RSAClefPublique> REGISTRE = new HashMap<String, RSAClefPublique>(); // registre
                                                                                                                // contenant
                                                                                                                // toutes
                                                                                                                // les
                                                                                                                // clefs
                                                                                                                // publiques
                                                                                                                // existantes

    // construit le codeage et publie la clef publique
    // lance une IllegalArgumentException si p et q négatif,
    // si p ou q n'est pas premier,
    // si e n'est dans Z_phi,
    // si (e, p * q) n'est pas une clef publique valable,
    // si proprietaire est vide ou null
    public CodageRSA(long e, long p, long q, String proprietaire) {
        if (p <= 0 || q <= 0 || e <= 0) {
            throw new IllegalArgumentException();
        }
        if (!estPremier(p) || !estPremier(q)) {
            throw new IllegalArgumentException();
        }
        long phi = (p - 1) * (q - 1);
        Zn znPhi = new Zn(phi);
        if (!znPhi.contient(e)) {
            throw new IllegalArgumentException();
        }
        if (pgcd(p * q, e) != 1) {
            throw new IllegalArgumentException();
        }
        if (proprietaire == null || proprietaire.isEmpty()) {
            throw new IllegalArgumentException();
        }
        this.proprietaire = proprietaire;
        clefPublique = new RSAClefPublique(e, p * q);
        clefPrivee = new RSAClefPrivee(znPhi.inverse(e), p, q);
        publier(proprietaire, clefPublique);
    }

    // renvoie la clef privée du codage
    public RSAClefPrivee getClefPrivee() {
        return clefPrivee;
    }

    // renvoie la clef publique du codage
    public RSAClefPublique getClefPublique() {
        return clefPublique;
    }

    // méthode publiant la clef (elle ajoute la clef dans le registre des clefs)
    private void publier(String proprietaire, RSAClefPublique clef) {
        CodageRSA.REGISTRE.put(proprietaire, clef);
    }

    // renvoie la clef publique associé à propriétaire s'il y en a une, null sinon
    public static RSAClefPublique obtenirClefPublique(String proprietaire) {
        return CodageRSA.REGISTRE.get(proprietaire);
    }

    // renvoie true si le nombre entier x est premier et false sinon
    public static boolean estPremier(long x) {
        if (x <= 1) {
            return false;
        }
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static long pgcd(long m, long n) {
        long r;
        while (n != 0) {
            r = m % n;
            m = n;
            n = r;
        }
        return m;
    }

}

Dans le fichier "TestCodageRSA.java" :

package crypto;

import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Scanner;

public class TestCodageRSA {

    private static Class<CodageRSA> classe = CodageRSA.class;
    private static Class<RSAClefPrivee> classeCPr = RSAClefPrivee.class;
    private static Class<RSAClefPublique> classeCPu = RSAClefPublique.class;
    private static Field clefPrivee;
    private static Field clefPublique;
    private static Field proprietaire;
    private static Field registre;
    private static Field znPr;
    private static Field znPu;
    private static Field e;
    private static Field d;
    private static final Scanner scanner = new Scanner(System.in);
    private static final String[] NOMS_METHODES = {
            "du constructeur CodageRSA(long e, long p, long q, String proprietaire)", "estPremier(long x)" };

    public static void main(String[] args) throws IllegalAccessException {
        Field[] champs = classe.getDeclaredFields();
        for (Field f : champs) {
            if (f.getType() == RSAClefPrivee.class) {
                if ("clefPrivee".equals(f.getName())) {
                    clefPrivee = f;
                    clefPrivee.setAccessible(true);
                }
            } else if (f.getType() == RSAClefPublique.class) {
                if ("clefPublique".equals(f.getName())) {
                    clefPublique = f;
                    clefPublique.setAccessible(true);
                }
            } else if (f.getType() == java.lang.String.class) {
                if ("proprietaire".equals(f.getName())) {
                    proprietaire = f;
                    proprietaire.setAccessible(true);
                }
            } else if (f.getType() == java.util.HashMap.class) {
                if ("REGISTRE".equals(f.getName())) {
                    registre = f;
                    registre.setAccessible(true);
                }
            }
        }

        Field[] champsPr = classeCPr.getDeclaredFields();
        for (Field f : champsPr) {
            if (f.getType() == long.class) {
                if ("d".equals(f.getName())) {
                    d = f;
                    d.setAccessible(true);
                }
            } else if (f.getType() == Zn.class) {
                if ("zn".equals(f.getName())) {
                    znPr = f;
                    znPr.setAccessible(true);
                }
            }
        }

        Field[] champsPu = classeCPu.getDeclaredFields();
        for (Field f : champsPu) {
            if (f.getType() == long.class) {
                if ("e".equals(f.getName())) {
                    e = f;
                    e.setAccessible(true);
                }
            } else if (f.getType() == Zn.class) {
                if ("zn".equals(f.getName())) {
                    znPu = f;
                    znPu.setAccessible(true);
                }
            }
        }

        System.out.println("****************************************");
        System.out.println("Programme Test pour la classe CodageRSA ");
        System.out.println("****************************************");

        int choix = 0;
        while (true) {
            for (int i = 0; i < NOMS_METHODES.length; i++) {
                System.out.println((i + 1) + " -> Test " + NOMS_METHODES[i]);
            }
            System.out.println("autre -> Quitter");

            choix = scanner.nextInt();
            boolean testOK;
            switch (choix) {
            case 1:
                testOK = testConstructeur();
                HashMap<String, RSAClefPublique> registreCodage = (HashMap<String, RSAClefPublique>) registre
                        .get(new CodageRSA(7, 3, 5, "moi"));
                registreCodage.clear();
                break;
            case 2:
                testOK = testEstPremier();
                break;
            default:
                return;
            }
            if (testOK) {
                System.out.println("Le test " + NOMS_METHODES[choix - 1] + " a réussi.");
            } else {
                System.out.println("Le test " + NOMS_METHODES[choix - 1] + " a échoué.");
            }
            System.out.println();
        }
    }

    private static boolean testConstructeur() throws IllegalAccessException {

        CodageRSA codage;

        System.out.println("Test 1");
        System.out.println();

        try {
            codage = new CodageRSA(-1, 5, 7, "loic");
            System.out.println("Il fallait une exception car e < 0");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            codage = new CodageRSA(0, 5, 7, "loic");
            System.out.println("Il fallait une exception car e = 0 n'est pas premier avec phi(n)");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        try {
            codage = new CodageRSA(24, 5, 7, "loic");
            System.out.println("Il fallait une exception car e >= phi(n)");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        try {
            codage = new CodageRSA(30, 5, 7, "loic");
            System.out.println("Il fallait une exception car e > phi(n)");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        try {
            codage = new CodageRSA(24, 5, 7, "loic");
            System.out.println("Il fallait une exception car e >= phi(n)");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        try {
            codage = new CodageRSA(15, 5, 7, "loic");
            System.out.println("Il fallait une exception car e = 15 n'a pas d'inverse dans Z_phi(n)");
            System.out.println("car 15 n'est pas premier avec phi(n)=24");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 7");
        System.out.println();

        try {
            codage = new CodageRSA(15, 144, 17, "loic");
            System.out.println("Il fallait une exception car p = 144 n'est pas premier");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 8");
        System.out.println();

        try {
            codage = new CodageRSA(15, 5, 22, "loic");
            System.out.println("Il fallait une exception car q = 22 n'est pas premier");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 9");
        System.out.println();

        try {
            codage = new CodageRSA(13, 5, 7, null);
            System.out.println("Il fallait une exception car proprietaire est null");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 10");
        System.out.println();

        try {
            codage = new CodageRSA(13, 5, 7, "");
            System.out.println("Il fallait une exception car proprietaire est vide");
            return false;
        } catch (IllegalArgumentException e) {
            if (CodageRSA.obtenirClefPublique("Loic") != null) {
                System.out.println("Vous avez publié la clef publique alors qu'elle n'était pas valable");
                return false;
            }
        } catch (Exception f) {
            System.out.println("Vous n'avez pas lancer la bonne exception : " + f.getClass());
            return false;
        }

        System.out.println();
        System.out.println("Test 11");
        System.out.println();

        try {
            codage = new CodageRSA(13, 5, 11, "Loic");
            String prop = (String) proprietaire.get(codage);
            if (prop == null) {
                System.out.println("L'attribut proprietaire n'a pas été initialisé");
                return false;
            }
            if (!prop.equals("Loic")) {
                System.out.println("L'attribut proprietaire n'a pas été bien initialisé");
                System.out.println("Attendu : Loic  |   Reçu : " + prop);
                return false;
            }

            RSAClefPublique cPu = (RSAClefPublique) clefPublique.get(codage);
            if (cPu == null) {
                System.out.println("L'attribut clefPublique n'a pas été initialisé");
                return false;
            }
            long ePu = e.getLong(cPu);
            if (ePu != 13) {
                System.out.println("L'attribut e de la clef publique n'a pas été bien initialisée : attendu : 13"
                        + " | reçu : " + ePu);
                return false;
            }

            Zn znPuO = (Zn) znPu.get(cPu);
            if (znPuO.getN() != 55) {
                System.out.println("Le Zn de la clef publique n'a pas été bien initialisée : attendu n = 55 "
                        + "| reçu n = " + znPuO.getN());
                return false;
            }

            RSAClefPrivee cPr = (RSAClefPrivee) clefPrivee.get(codage);
            if (cPr == null) {
                System.out.println("L'attribut clefPrivee n'a pas été initialisé");
                return false;
            }
            long dPr = d.getLong(cPr);
            if (dPr != 37) {
                System.out.println("L'attribut d de la clef privee n'a pas été bien initialisée : attendu : 37"
                        + " | reçu : " + dPr);
                return false;
            }

            Zn znPrO = (Zn) znPr.get(cPr);
            if (znPrO.getN() != 55) {
                System.out.println("L'attribut Zn de la clef privee n'a pas été bien initialisée : attendu : 55 "
                        + "| reçu : " + znPrO.getN());
                return false;
            }

            if (CodageRSA.obtenirClefPublique("Loic") == null) {
                System.out.println("Vous n'avez pas publiée la clef publique");
                return false;
            }

        } catch (Exception e) {
            System.out.println("Il ne fallait pas lancer d'exception : " + e.getClass());
            e.printStackTrace();
            return false;
        }

        return true;
    }

    private static boolean testEstPremier() throws IllegalAccessException {

        System.out.println("Test 1");
        System.out.println();
        if (CodageRSA.estPremier(-3)) {
            System.out.println("-3 n'est pas premier car divisible par -1");
            return false;
        }

        System.out.println();
        System.out.println("Test 2");
        System.out.println();

        if (CodageRSA.estPremier(0)) {
            System.out.println("0 n'est pas premier car divisible par n'importe quel entier !");
            return false;
        }

        System.out.println();
        System.out.println("Test 3");
        System.out.println();

        if (CodageRSA.estPremier(1)) {
            System.out.println("1 n'est pas premier car n'admet que lui-même comme diviseur.");
            return false;
        }

        System.out.println();
        System.out.println("Test 4");
        System.out.println();

        if (CodageRSA.estPremier(169)) {
            System.out.println("169 n'est pas premier car admet 13 comme diviseur");
            return false;
        }

        System.out.println();
        System.out.println("Test 5");
        System.out.println();

        if (CodageRSA.estPremier(4)) {
            System.out.println("4 n'est pas premier car admet 2 comme diviseur");
            return false;
        }

        System.out.println();
        System.out.println("Test 6");
        System.out.println();

        long p = 999983;
        p = p * p;

        if (CodageRSA.estPremier(p)) {
            System.out.println(p + " n'est pas premier car admet 999983 comme diviseur");
            return false;
        }

        System.out.println();
        System.out.println("Test 7");
        System.out.println();

        p = 103 * 113;

        if (CodageRSA.estPremier(p)) {
            System.out.println(p + " n'est pas premier car admet 103 comme diviseur");
            return false;
        }

        System.out.println();
        System.out.println("Test 8");
        System.out.println();

        p = 2;

        if (!CodageRSA.estPremier(p)) {
            System.out.println(p + " est premier car divisible uniquement par 1 et lui même.");
            return false;
        }

        System.out.println();
        System.out.println("Test 9");
        System.out.println();

        p = 101;

        if (!CodageRSA.estPremier(p)) {
            System.out.println(p + " est premier car divisible uniquement par 1 et lui-même.");
            return false;
        }

        System.out.println();
        System.out.println("Test 10");
        System.out.println();

        p = 999983;

        if (!CodageRSA.estPremier(p)) {
            System.out.println(p + " est premier car divisible uniquement par 1 et lui-même.");
            return false;
        }

        return true;
    }

}

Vecteur (VECTOR) :

Un vecteur est une suite d'objets de même type, possédant un ordre bien précis, et dont le nombre est variable.

Un vecteur peut être vide !

L'ordre des éléments est important.

On accède à un élément via son rang.

On appelle rang d'un élément d'une structure linéaire, le nombre d'éléments situés avant lui. On abstrait ainsi la notion d'indice du tableau.

Méthodes de l'interface Vecteur :

public int taille ()
public boolean estVide ()
public String toString ()
public Object element (int rang) throws VecteurOutException
public void insere (int rang, Object element) throws VecteurOutException
public void ajoute (Object valeur)
public Object remplace (int rang, Object element) throws VecteurOutException
public Object supprime (int rang) throws VecteurOutException
public Iterator iterator()

public class VecteurImpl implements Vecteur {

    private Object[] table;
    private int taille;

    public VecteurImpl () {
        this(16);
    }

    public VecteurImpl (int taille-) {
        this.table = new Object[taille];
        this.taille = 0;
    }

    public boolean estVide() {
        return taille == 0;
    }

    // taille logique
    public int taille() {
        return taille;
    }

    public String toString() {
        String aRenvoyer = "";
        if (taille > 0) {
            aRenvoyer += table[0];
            for (int i = 1; i < taille; i++) {
                aRenvoyer += " " + table[i];
            }
        }
        return aRenvoyer;
    }

    private void testRang (int rang) throws VecteurOutException {
        if (rang < 0 || rang >= taille) {
            throw new VecteurOutException();
        }
    }

    private void testRangPourAjout (int rang) throws VecteurOutException{
        if (rang < 0 || rang > taille) {
            throw new VecteurOutException();
        }
    }

    public Object element (int rang) throws VecteurOutException {
        testRang(rang);
        return table[rang];
    }

    // conserve l'ordre des objets (décalages)
    public void insere (int rang, Objet element) throws VecteurOutException {
        testRangPourAjout(rang);
        if (taille == table.length) {
            Object[] temp = new Object[table.length * 2];
            for (int i = 0; i < taille; i++) {
                temp[i] = table[i];
            }
            table = temp;
        }
        for (int i = taille - 1; i >= rang; i--) {
            table[i + 1] = table[i];
        }
        taille++;
        table[rang] = element;
    }

    // ajout en fin de table
    public void ajoute (Object element) {
        try {
            insere(taille, element);
        } catch (VecteurOutException e) {
            e.printStackTrace();
        }
    }

    public Object remplace (int rang, Object element) throws VecteurOutException {
        testRang(rang);
        Object aRenvoyer = table[rang];
        table[rang] = element;
        return aRenvoyer;
    }

    // conserve l'ordre des objets (décalages)
    public Object supprime  (int rang) throws VecteurOutException {
        testRang(rang);
        Object aRenvoyer = table[rang];
        for (int i = rang; i < taille - 1; i++) {
            table[i] = table[i + 1];
        }
        taille--;
        return aRenvoyer;
    }

}

Pile (STACK) :

Une pile est une suite d'objets de même type, possédant un ordre bien précis, et dont le nombre est variable.

Une pile peut être vide !

L'ajout et le retrait se font "au sommet" de la pile.

ajouter ↔ empiler ↔ push

retirer ↔ dépiler ↔ pop

L.I.F.O. (Last In First Out)

Méthodes de l'interface Pile :

public int taille ()
public boolean estVide ()
public void push (Object c)
public Object pop () throws PileVideException
public Object sommet () throws PileVideException

public class PileImpl implements Pile {

    Object[] table;
    int taille;

    public PileImpl() {
        this(4);
    }

    public PileImpl(int capacite) {
        table = new Object[capacite];
        taille = 0;
    }

    // renvoie le nombre d'objets contenus dans la pile
    public int taille() {
        return taille;
    }

    public boolean estVide() {
        return taille == 0;
    }

    // ajoute l'élément sur la pile
    pubic void push (Object element) {
        if (taille == table.length) {
            Object[] temp = new Object[table.length * 2];
            for (int i = 0; i < taille; i++) {
                tmp[i] = table[i];
            }
            table = temp;
        }
        table[taille] = element;
        taille++;
    }

    // enlève et renvoie l'objet qui se trouve au sommet de la pile
    public Object pop() throws PileVideException {
        if (estVide()) {
            throw new PileVideException();
        }
        taille--;
        return table[taille];
    }

    // renvoie l'objet qui se trouve au sommet de la pile sans l'enlever de la pile
    public Objectt sommet() throws PileVideException {
        if (estVide()) {
            throw new PileVideException();
        }
        return table[taille - 1];
    }

}

Les classes internes :

Attention : les itérateurs des collections seront des classes internes.

Une classe interne (ou Inner class en anglais) est une classe définie dans une autre classe.

Une classe externe ou englobante (ou Outer class en anglais) est une clsse qui contient la ou les classe(s) interne(s).

Une classe interne a un accès direct aux attributs et méthodes de la classe englobante (à ses propriétés).

Avantage : une classe qui manipule les attributs d'une autre classe sans pour autant que cette seconde ne doive les rendre publics ou accessibles via getter/setter.
À la construction, inutile de passer en paramètre les données de la classe englobante.

Une classe interne a les mêmes règles de visibilité que pour les attributs et méthodes de la classse englobante.

L'interface Iterable<T> et l'interface Iterator<T> :

public Iterator<T> iterator() {...} est la méthode imposée par l'ubrerface Iterable<T>.

Un itérateur permet de parcourir qui se trouve dans une collection.
<T> : type d'objet contenu dans la liste.
L'interface Iterator<T> impose les méthodes suivantes :
- public boolean hashNext() {...}
- public <T> next() {...}
- public void remove() {...}

La méthode public hasNext() {...} a comme responsabilité de signaler s'il reste un élément de la collection qui n'a pas encore été consulté. Elle renvoie true s'il y a encore un élément à consulter et false s'il y en a plus.

La méthode public <T> next() {...} a comme responsabilité de renvoyer l'élément suivant, présent dans la collection parcourue par l'itérateur. Elle renvoie donc l'élément suivant de type <T>. Une NoSuchElementException est levée s'il n'y a plus d'élément à consulter. Une ConcurrentModificationException est levée si la collection a été modifée, autrement que via l'itérateur, depuis le moment où l'iterateur a été créé.

La méthode public void remove() {...} a comme responsabilité de supprimer l'élément de la collection qui a été renvoyée par le dernier next(). Une UnsupportedOperationException est levée si les suppressions sont interdites. Une IllegalStateException est levée si un appel à remove() vient d'être fait ou si la méthode next() n'a pas encore été appelée. Une ConcurrentModificationException est levée si la collection a été modifiée, autrement que via l'itérateur, depuis le moment où l'itérateur a été créé.

VecteurImpl

ArrayList

VecteurImpl ()

ArrayList ()

VecteurImpl (int capacite)

ArrayList (int initialCapacity)

int taille ()

int size ()

boolean estVide ()

boolean isEmpty ()

Object element (int rang) throws VecteurOutException

E get (int index) throw indexOutOfBoundsException

void insere (int rang, Object element) throws VecteurOutException

void add (int index, E element) throws indexOutOfBoundsException

void ajoute (Object valeur)

boolean remplace (E element)

Object remplace (int rang, Object element) throws VecteurOutException

E set (int index, E element) throws IndexOutOfBoundsException

Object supprime (int rang) throws VecteurOutException

E remove (int index) throws IndexOutOfBoundsException

boolean contains (Object o)

int indexOf (Object o)

boolean remove (Object o)

Exemple :

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ListeDeCercles implements Iterable {

    private Cercle[] cercles;
    private int nombreDeCercles;
    private int numVersion = 0;

    public ListeDeCercles() {
        this.cercles = new Cercle[20];
    }

    ...

    public boolean ajouter (Cercle c) {
        if (c == null) {
            throw new IllegalArgumentException();
        }
        if (contains(c)) {
            return false;
        }
        if (cercle.length == nombreDeCercles) {
            return false;
        }
        numVersion++;
        cercles[nombreDeCercles] = c;
        nombreDeCercles++;
        return true;
    }

    public Iterator iterator() {
        return new CercleIterateur();
    }

    // Classe interne : itérateur
    public class CercleIterateur implements Iterator<Cercle> {

        private int indice;
        private int version;
        private boolean removeAutorise;

        public CerclceIterateur() {
            this.version = numVersion;
            this.indice = 0;
            this.removeAutorise = false;
        }

        public boolean hashNext() {
            return indice < nombreDeCercles;
        }

        public Cercle next() {
            if (numVersion != version) {
                throw new ConcurrentModificationException();
            }
            if(!hasNext()){
                throw new NoSuchElementException();
            }
            removeAutorise = true;
            Cercle cercle = cercles[indice];
            indice++;
            return cercle;
        }

        public void remove() {
            if (!removeAutorise) {
                throw new IllegalArgumentException();
            }
            if (numVersion != version) {
                throw new ConcurrentModificationException();
            }
            removeAutorise = false;
            cercles[indice - 1] = cercles[nombreDeCercles - 1];
            cercles[nombreDeCercles - 1] = null;
            indice--;
            nombreDeCercles--;
        }

    } // fin de la classe interne

    ...

} // fin de la classe ListeDeCercles

La complexité d'un algorithme :

Soit f(n) une fonction de n.

On dira qu'un algorithme est en O(f(n)) si son temps d'exécution est proportionnel à f(n).

On dira qu'un algorithme est en O(f(n)) s'il existe deux nombres positifs constants k et n₀ tels que T(n) <= k * f(n) quand n = n₀.

La fonction d(n) est appelée l'ordre de complexité de l'algorithme.

Les cas les plus fréquemment rencontrés sont les suivants :

O(1) : durée indépendante de n
O(log n) : complexité logarithmique
O(n) : complexité linéaire
O(n * log n) : complexité quasi-linéaire
O(n²) : complexité quadratique
O(n³) : complexité cubique
O(n^d) : complexité polynomiale
O(2ⁿ) : complexité exponentielle
O(n^!) : complexité factorielle

Le facteur de proportionnalité est négligé. Il ne sera utilisé que pour départager deux agorithmes qui le même ordre de complexité.

Par exemple : O(n/2), O(n) et O(2n) → O(n).

FILE (QUEUE) :

Une file d'attente est une suite d'objets de même type, possédant un ordre bien précis, et dont le nombre est variable.

Une file peut être vide !

L'ajout se fait en queue (fin).

Le retrait se fait en tête (début).

ajouter ↔ enfiler ↔ enfile

retirer ↔ défiler ↔ defile

F.I.F.O. (Fist In First Out)

Méthode de l'interface File :

public int taille ()
public boolean estVide ()
public void enfile (Object c)
public Object defile () throws FileVideException
public premier () throws FileVideException

FileImpl

ArrayDeque

int taille ()

int size ()

boolean estVide ()

boolean isEmpty ()

Object defile () throws FileVideException

E removeFirst () throws NoSuchElementException

Object premier () throws FileVideException

E getFirst () throws NoSuchElementException

// implémentation de l'interface File via une table circulaire
public class FileImpl implements File {

    Object[] table;
    int tete;
    int queue;
    int taille;

    public FileImpl() {
        table = new Object[4];
        tete = queue = taille = 0;
    }

    // renvoie true ssi la file est vide
    public boolean estVide() {
        return taille == 0;
    }

    // renvoie le nombre d'objets contenus dans la file
    public int taille() {
        return taille;
    }

    // ajoute l'objet element en queue de file
    public void enfile(Object element) {
        if (!estVide() && tete == queue) {
            doublerTaille(table);
        }
        table[queue] = element;
        queue = (queue + 1) % table.length;
        taille++;
    }

    // enlève et renvoie l'objet qui se trouve en tête
    public Object defile() throws FileVideException {
        if (estVide()) {
            throw new FileVideException("la file est vide");
        }
        return table[tete];
    }

    private void doublerTaille(Object[] file) {
        Object[] tmp = new Object[taille.length * 2];
        int indice = 0;
        for (int i = tete; i < file.length; i++) {
            tmp[i] = table[i];
            indice++;
        }
        for (int j = 0; j  < tete; j++) {
            tmp[indice] = file[j];
            indice++;
        }
        tete = 0;
        queue = indice;
        table = tmp;
    }

}

Programmation de mathématique :

Les MathException peuvent donc ne pas être "catchée"; elles provoquent dans ce cas le "plantage" du programme.

La valeur actuelle de MaxEltValue est 50. L'ensemble de tous les Elt est appelé "Univers".

Class Elt

MAXELT

Élément maximum (= MaxEltValue)

Elt(int i)

Constructeur sur base d'un entier

Elt(Elt e)

Constructeur par recopie

int val()

Valeur numérique de l'élément

String toString

boolean equals(Object o)

int hashCode()

Elt succ()

Renvoie l'élément suivant (2 suit 1, 3 suit 2, 1 suit MAXELT)

Elt prec()

Renvoie l'élément précédent (1 précède 2, 2 précède 3, MAXELT précède 1)

Programmation sur les suites :

Class SuiteDeBase implements Iterable<Elt>

SuiteDeBase()

Construit une suite vide

SuiteDeBase(SuiteDeBase s)

Constructeur par recopie

SuiteDeBase(Elt t, SuiteDeBase c)

Construit la suite dont la tête vaut t et dont le corps vaut c

SuiteDeBase(String s)

Constructeur à partir d'une chaîne de caractères

boolean estVide()

Retourne true si la suite est vide

Elt tete()

Retourne la tête de la suite

SuiteDeBase corps()

Renvoie le corps de la suite

void couper()

Supprime la tête de la suite

void ajouter(Elt e)

Ajoute e devant la suite

String toString()

Iterator<Elt> iterator()

Class Suite extends SuiteDeBase

// variables

private static final int MAX = Elt.MAXELT.val();

public int compteurSubstitut = 0;

// méthodes

public Suite()

super();

public Suite(SuiteDeBase s)

super(s);

public Suite(String st)

super(st);

public Suite(Elt t, SuiteDeBase c)

super(t, c);

public Suite(Elt e)

this();
ajouter(e);

public Suite corps()

return (Suite) super.corps();

public int longueur()

// programme récursif
if(estVide()){return 0;}
return 1 + corps().longueur();
// programme itératif
int compteur = 0;
for(Elt elt : this){
    compteur++;
}
return compteur;

public boolean contient(Elt e)

// programme récursif
if(e==null){throw new IllegalArgumentException();}
if(estVide()){return false;}
if(e.equals(tete())){return true;}
return corps().contient(e);
// programme itératif
if(e==null){throw new IllegalArgumentException();}
for(Elt elt : this){
    if(elt.equals(e)){return true;}
}
return false;

public int nombreOccur(Elt e)

// programme récursif
if(e==null){throw new IllegalArgumentException();}
if(estVide()){return 0;}
int compteur = 0;
if(e.equals(tete())){compteur = 1;}
return compteur + corps().nombreOccur(e);
// programme itératif
if(e==null){throw new IllegalArgumentException();}
int compteur = 0;
for(Elt e : this){
    if(elt.equals(e)){compteur++;}
}
return compteur;

public int position(Elt e)

// programme récursif
if(e==null){throw new IllegalArgumentException();}
if(estVide()){return 0;}
if(tete().equals(e)){return 1;}
int temp = corps().position(e);
if(temp == 0){return 0;}
return 1 + temp;
// programme itératif
if(e==null){throw new IllegalArgumentException();}
int index = 1;
for(Elt elt : this){
    if(elt.equals(e)){return index;}
    index++;
}
return 0;

public Elt i_eme(int i)

// programme récursif
if(longueur() < i || i <= 0){throw new IllegalArgumentException();}
if(i == 1){return tete();}
return corps().i_eme(i - 1);
// programme itératif
if(longueur() < i || i <= 0){throw new IllegalArgumentException();}
int compteur = 1;
for(Elt elt : this){
    if(compteur == i){return elt;}
    compteur++;
}
return null;

public Elt dernier()

// programme récursif
if(estVide()){throw new MathException();}
if(corps().estVide()){return tete();}
return corps().dernier();
// programme itératif
if(estVide()){throw new MathException();}
return i_eme(longueur());

public boolean equals(Object o)

if(this == o){return true;}
if(o == null){return false;}
if(this.getClass() != o.getClass()){return false;}
Suite s = (Suite) o;
return estEgalA(s);

public estEgalA(Suite s)

// programme récursif
if(estVide() != s.estVide()){return false;}
if(estVide() && s.estVide()){return true;}
if(!tete().equals(s.tete())){return false;}
return corps().estEgalA(s.corps());

public boolean prefixe(Suite s)

// programme récursif
if(s == null){throw new IllegalArgumentException();}
if(estVide() && s.estVide()){return true;}
if(!estVide() && s.estVide()){return false;}
if(estVide() && !estVide()){return true;}
if(tete().equals(s.tete())){return corps().prefixe(s.corps());}
return false;
// programme itératif
if(s == null){throw new IllegalArgumentException();}
if(estVide() && s.estVide()){return true;}
if(longueur() > s.longueur()){return false;}
Iterator<Elt> it = s.iterator();
for(Elt elt : this){
    if(!elt.equals(it.next())){return false;}
}
return true;

public boolean sousSuite(Suite s)

// programme récursif
if(s == null){throw new IllegalArgumentException();}
if(longueur() > s.longueur()){return false;}
if(estVide()){return true;}
if(estVide() && s.estVide()){return true;}
if(estVide() && !s.estVide()){return false;}
if(!estVide() && s.estVide()){return true;}
if(s.tete().equals(tete())){return corps().sousSuite(s.corps());}
return sousSuite(s.corps());
// programme itératif
if(s == null){throw new IllegalArgumentException();}
if(longueur() > s.longueur()){return false;}
if(estVide()){return true;}
for(Elt elt : this){
    if(elt == tete() && !s.corps().equals(corps())){return false;}
}
return true;

public void ajouter(Suite s)

// programme récursif
if(s == null){throw new IllegalArgumentException();}
if(!s.estVide()){
    ajouter(s.corps());
    ajouter(s.tete());
}
// programme itératif
if(s == null){throw new IllegalArgumentException();}
Suite temp = new Suite();
for(Elt elt : s){
    temp.ajouter(elt);
}
for(Elt elt : temp){
    ajouter(elt);
}

public void ajouterALEnvers(Suite s)

// programme récursif
if(s == null){throw new IllegalArgumentException();}
if(!s.estVide()){
    ajouter(s.tete());
    ajouterALEnvers(s.corps());
}
// programme itératif
if(s == null){throw new IllegalArgumentException();}
for(Elt elt : s){
    ajouter(elt);
}

public Suite inverse()

// programme récursif
Suite s = new Suite();
if(estVide()){return s;}
s.ajouter(tete());
s.ajouter(corps().inverse());
return s;
// programme itératif
Suite aRenvoyer = new Suite();
aRenvoyer.ajouterALEnvers(this);
return aRenvoyer;

public Suite reduite()

// programme récursif
if(estVide()){return new Suite();}
if(!corps().contient(tete())){return new Suite(tete(), corps().reduite());}
else{return new Suite(corps().reduite());}
// programme itératif
Suite reduite = new Suite();
for(Elt elt : this){
    if(!reduite.contient(elt)){reduite.ajouter(elt);}
}
return reduite;

public Suite moinsPremOcc(Elt e)

// programme récursif
if(e == null){throw new IllegalArgumentException();}
Suite resultat;
if(estVide()){resultat = new Suite();}
else if(tete().equals(e)){resultat = new Suite(corps());}
else {
    resultat = corps().moinsPremOcc(e);
    resultat.ajouter(tete());
}
return resultat;
// programme itératif
if(e == null){throw new IllegalArgumentException();}
if(!contient(e)){
    Suite copie = new Suite(this);
    return copie;
}
int compteur = 0;
int position = position(e) - 1;
Suite aRenvoyer = new Suite(this);
for(Elt elt : this){
    if(compteur != position){aRenvoyer.ajouter(elt);}
    compteur++;
}
return aRenvoyer.inverse();

public Suite moinsToutesOcc(Elt e)

// programme récursif
if(x == null){throw new IllegalArgumentException();}
if(estVide()){return new Suite();}
if(!tete().equals(e)){return new Suite(tete(), corps().moinsToutesOcc(e));}
else{return new Suite(corps().moinsToutesOcc(e));}
// programme itératif
if(x == null){throw new IllegalArgumentException();}
Suite tmp = new Suite();
for(Elt elt : this){
    if(!elt.equals(e)){tmp.ajouter(elt);}
}
return tmp.inverse();

public Suite substitut(Elt x, Elt y)

// programme récursif
if(x == null){throw new IllegalArgumentException();}
if(y == null){throw new IllegalArgumentException();}
if(estVide()){return new Suite();}
if(!tete().equals(x)){return new Suite(tete(), corps().substitut());}
else{new Suite(y, corps().substitut());}
// corps itératif
if(x == null){throw new IllegalArgumentException();}
if(y == null){throw new IllegalArgumentException();}
Suite temp = new Suite();
for(Elt elt : this){
    if(elt.equals(x)){temp.ajouter(y);}
    else{temp.ajouter(elt);}
}
return temp.inverse();

public Suite doublons()

// programme itératif
Suite s = new Suite();
for(Elt elt : this){
    if(nombreOccur(elt) > 1 && !s.contient(elt)){s.ajouter(elt);}
}
return s;

public boolean auMoinsK(int k)

// programme itératif
if(k < 0){throw new IllegalArgumentException();}
if(estVide()){return true;}
Suite s = new Suite();
int compteur = 0;
for(Elt elt : this){
    if(!s.contient(elt)){
        s.ajouter(elt);
        compteur++;
    }
    if(compteur == k){return true;}
}
return false;

public boolean tousDistincts()

// programme récursif
if(estVide()){return true;}
if(corps().contient(tete())){return false;}
return corps().tousDistincts();
// programme itératif
if(estVide()){return true;}
Suite s = new Suite();
for(Elt elt : this){
    if(s.contient(elt)){return false;}
    s.ajouter(elt);
}
return true;

Programmation sur les polynômes :

Class Polynome

// variables

private double[] coefficients;

private degre;

// méthodes

public Polynome(int degre)

if(degre < 0){throw new IllegalArgumentException();}
this.degre = degre;
this.coefficients = new double[degre + 1];
for(int i = 0; i < degre; i++){
    this.coefficients[i] = 0;
}
this.coefficients[degre] = 1;

public Polynome()

this.degre = 0;
this.coefficients = new double[1];
this.coefficients[0] = 0;

public void setCoefficient(int degre, double coefficient)

if(degre < 0 || degre > this.degre){throw new IllegalArgumentException();}
if(this.degre != 0 && this.degre == degre && coefficient == 0){throw new IllegalArgumentException();}
this.coefficients[degre] = coefficient;

public double evalueEn(double x)

double valeur = 0;
for(int i = 0; i < degre +1; i++){
    valeur += coefficients[i] * Math.pow(x, i);
}
return valeur;

public int signeEn(double x)

double valeur = evalueEn(x);
if(valeur > 0){return 1;}
if(valeur < 0){return -1;}
return 0;

public String toString()

if(degre == 0){return "" + this.coefficients[0];}
String result = "" + this/coefficients[degre] + " x^" + degre;
for(int i = degre -1; i > 0; i--){
    if(this.coefficients[i] < 0){result += "-" + Math.abs(this.coefficients[i]) + " x^" + i;}
    else if(this.coefficients[i] > 0){result += " + " + this.coefficients[i] + " x^" + i;}
}
if(this.coefficients[0] != 0){result += " " + this.coefficients[0];}
return result;

public double racineParBissection(double a, double b, int maxEtape, double tol) throws NumeriqueException

if(maxEtape < 0){throw new IllegalArgumentException();}
if(tol < 0){throw new IllegalArgumentException();}
if(a > b){
    double c = b;
    b = a;
    a = c;
}
int signeFA = signeEn(a);
int signeFB = signeEn(b);
if(signeFA == 0){return a;}
if(signeFB == 0){return b;}
if(signeFA * signeFB > 0){throw new NumeriqueException();}
double p = 0;
for(int i = 1; i <= maxEtape; i++){
    p = a + (b - a)/2;
    int signeFP = signeEn(p);
    if(signeFP == 0 || (b - a)/2 < tol){return p;}
    if(signeFA * signeFP > 0){a = p;}
    else{b = p;}
}
return p;

public int getDegre()

return this.degre;

public Polynome polynomeDerive()

Polynome polynomeDerive = new Polynome(this.degre-1);
for(int i = 1; i < this.degre + 1; i++){
    polynomeDerive.setCoefficient(i - 1, this.coefficients[i] * i);
}
return polynomeDerive;

public double racineCombine(double a, double b) throws NumeriqueException

double FP, FPP, p = racineParBissection(a, b, 20, 0);
Polynome derive = polynomeDerive();
for(int i = 1; i <= 20, i++){
    FP = evalueEn(p);
    FPP = derive.EvalueEn(p);
    p -= (FP/FPP);
}
return p;

Programmation sur les ensembles :

Interface EnsembleInterface

MAX

Elt.MAXELT.val()

boolean estVide()

Retourne true si l'ensemble est vide

boolean contient(Elt e)

Retourne true si l'élément est dans l'ensemble

void ajouter(Elt e)

Ajoute l'élément e à l'ensemble (! pas de doublons)

void enlever(Elt e)

Supprime l'élément e de l'ensemble (s'il y était)

void complementer()

Remplace l'ensemble courant par son complémentaire

int cardinal()

Retourne le cardinal de l'ensemble

// méthodes

default void ajouter(EnsembleInterface a)

if(a == null){throw new IllegalArgumentException();}
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if(a.contient(e)){ajouter(e);}
}

default void enlever(EnsembleInterface a)

if(a == null){throw new IllegalArgumentException();}
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if(a.contient(e)){enlever(e);}
}

default void intersecter(EnsembleInterface a)

if(a == null){throw new IllegalArgumentException();}
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if(!a.contient(e)){enlever(e);}
}

abstract Class EnsembleAbstrait implements EnsembleInterface

// méthodes

public boolean inclusDans(EnsembleAbstrait a)

if(a == null){throw new IllegalArgumentException();}
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if(!a.contient(e) && contient(e)){return false;}
}
return true;

public final boolean equals(Object o)

if(o == null){return false;}
if(o == this){return true;}
if(!(o instanceof EnsembleAbstrait)){return false;}
EnsembleAbstrait ens = (EnsembleAbstrait) o;
return inclusDans(ens) && ens.inclusDans(this);

public final int hashCode()

int reult = 1;
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if(contient(e)){result = 31 * result + e.hashCode();}
}
return result;

Class Ens1 extends EnsembleAbstrait

// variables

private boolean[] tabB;

private int cardinal;

// méthodes

public Ens1()

this.cardinal = 0;
this.tabB = new boolean[MAX + 1];

public Ens1(EnsembleInterface a)

this();
if(a == null){throw new IllegalArgumentException();}
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if(a.contient(e)){ajouter(e);}
}

public Ens1(Elt e)

this();
if(e == null){throw new IllegalArgumentException();}
ajouter(e);

public boolean estVide()

return cardinal == 0;

public boolean contient(Elt e)

if(e == null){throw new IllegalArgumentException();}
return tabB[e.val()];

public void ajouter(Elt e)

if(e == null){throw new IllegalArgumentException();}
if(!contient(e)){
    tabB[e.val()] = true;
    cardinal++;
}

public void enlever(Elt e)

if(e == null){throw new IllegalArgumentException();}
if(contient(e)){
    tabB[e.val()] = false;
    cardinal--;
}

public int cardinal()

return this.cardinal;

public void complementer()

for(int i = 1; i < tabB.length; i++){
    tabB[i] = !tabB[i];
}
cardinal = MAX - cardinal;

public String toString()

String str = "{";
for(int i = 1; i < tabB.length; i++){
    if(tabB[i]){str += i;}
    if(i != MAX){str += ", ";}
}
return str + "}";

Class Ens2 extends EnsembleAbstrait

//variables

private Elt[] elements;

private int cardinal;

// méthodes

public Ens2()

this.cardinal = 0;
this.elements = new Elt[MAX];

public Ens2(EnsembleInterface a)

this();
if(a == null){throw new IllegalArgumentException();}
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if(a.contient(e)){ajouter(e);}
}

public Ens2(Elt e)

this();
if(e == null){throw new IllegalArgumentException();}
ajouter(e);

public boolean estVide()

return this.cardinal == 0;

public int cardinal()

return this.cardinal;

public boolean contient(Elt e)

if(e == null){throw new IllegalArgumentException();}
for(int i = 0; i < cardinal; i++){
    if(elements[i].equals(e)){return true;}
}
return false;

public void ajouter(Elt e)

if(e == null){throw new IllegalArgumentException();}
if(!contient(e)){
    elements[cardinal] = e;
    cardinal++;
}

public void enlever(Elt e)

if(e == null){throw new IllegalArgumentException();}
for(int i = 0; i < cardinal; i++){
    if(elements[i].equals(e)) {
        elements[i] = elements[cardinal - 1];
        cardinal--;
        return;
    }
}

public void complementer()

Elt[] tmp = new Elt[MAX];
int cardTmp = 0;
for(int i = 1; i <= MAX; i++){
    Elt e = new Elt(i);
    if (!contient(e)){
        tmp[cardTmp] = e;
        cardTmp++;
    }
}
elements = tmp;
cardinal = cardTmp;

public String toString()

String str = "{";
int i;
for(int i = 0; i <= cardinal - 2; i++){
    str += elements[i] + ", ";
}
if(elemnts[i] != null){str ++ elements[i];}
return str + "}";

Programmation sur les matrices :

Class Matrice

// variables

private final int nbLignes;

private final int nbColonnes;

private final double[][] data;

// méthodes

public Matrice(int a, int)

if(a <= 0 || b <= 0){throw new IllegalArgumentException();}
data = new double[a][b];
nbLignes = a;
nbColonnes = b;

public Matrice(double[][] tab)

if(tab == null || tab.length == 0 || tab[0] == null || tab[0].length == 0){throw new IllegalArgumentException();}
int tmp = tab[0].length;
for(int i = 1; i < tab.length; i++){
    if(tab[i] == null || tab[i].length != tmp){throw new IllegalArgumentException();}
}
data = new double[tab.length][tmp];
for(int i = 0; i < tab.length; i++){
    for(int j = 0; j < tmp; j++){
        data[i][j] = tab[i][j];
    }
}
nbLignes = tab.length;
nbColonnes = tmp;

public Matrice(Matrice a)

if(a == null){throw new IllegalArgumentException();}
data = new double[a.data.length][a.data[0].length];
for(int i = 0; i < a.data.length; i++){
    for(int j = 0; j < a.data[0].length; j++){
        data[i][j] = a.data[i][j];
    }
}
nbLignes = a.nbLignes;
nbColonnes = a.nbColonnes;

public static Matrice identite(int a)

if(a <= 0){throw new IllegalArgumentException();}
Matrice matrice = new Matrice(a, a);
for(int i = 0; i < matrice.data.length; i++){
    matrice.data[i][i] = 1;
}
return matrice;

public double getElement(int numLigne, int numColonne)

if(numLigne > data.length || numLigne <= 0 || numColonne < data[0].length || numColonne <= 0){throw new IllegalArgumentException();}
return data[numLigne - 1][numColonne - 1];

public Matrice somme(Matrice b)

if(b == null || nbLignes != b.nbLignes || nbColonnes != b.nbColonnes){throw new IllegalArgumentException();}
Matrice matrice = new Matrice(b);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        matrice.data[i][j] += data[i][j];
    }
}
return matrice;

public Matrice produitParScalaire(double scalaire)

Matrice matrice = new Matrice(this);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        matrice.data[i][j] *= scalaire;
    }
}
return matrice;

public Matrice produitAGauche(Matrice b)

if(b == null || nbColonnes != b.nbLignes){throw new IllegalArgumentException();}
Matrice matrice = new Matrice(nbLignes, b.nbColonnes);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < b.nbColonnes; j++){
        for(int k = 0; k < b.nbLignes; k++){
            matrice.data[i][j] = data[i][k] * b.data[k][j];
        }
    }
}
return matrice;

public Matrice produitADroite(Matrice b)

if(b == null){throw new IllegalArgumentException();}
return b.produitAGauche(this);

public boolean carree()

return nbLignes == nbColonnes;

public Matrice puissance(int n)

if(carree()){throw new MathException();}
if(n < 0){throw new IllegalArgumentException();}
if(n == 0){return identite(nbLignes);}
Matrice matrice = new Matrice(this);
for(int i = 2; i <= n; i++) {
    matrice = matrice.produitAGauche(this);
}
return matrice;

public String toString()

String aRenvoyer = "";
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        aRenvoyer += data[i][j];
        int nbEspaces = 15 - String.valueOf(data[i][j]).length();
        for(int k = 0; k < nbEspaces; k++){
            aRenvoyer += " ";
        }
    }
    aRenvoyer += "\n";
}
return aRenvoyer;

public Matrice pageRank()

if(!carree()){throw new MathException();}
int[] tab = new int[nbColonnes];
for(int i = 0; i < nbColonnes; i++){
    for(int j = 0; j < nbLignes; j++){
        if(data[j][i] != 0 && data[j][i] != 1){throw new MathException();}
        tab[i] += data[j][i];
    }
}
Matrice transition = new Matrice(this);
for(int i = 0; i < nbColonnes; i++){
    if(tab[i] == 0){
        for(int j = 0; j < nbLignes; j++){
            transition.data[j][i] = 1.0 / nbLignes;
        }
    } else {
        for(int j = 0; j < nbLignes; j++){
            if(transition.data[j][i] == 1){transition.data[j][i] = 1.0 / tab[i];}
        }
    }
}
Matrice random = new Matrice(nbLignes, nbLignes);
for(int i = 0; i < nbColonnes; i++){
    for(int j = 0; j < nbLignes; j++){
        random.data[j][i] = 1.0 / nbLignes;
    }
}
transition = transition.produitParScalaire(0.85);
random = random.produitParScalaire(0.15);
Matrice x = new Matrice(nbLignes, 1),
x.data[0][0] = 1;
for(int i = 0; i < 85; i++){
    x = google.produitAGauche(x);
    double somme = 0;
    for(int j = 0; j < nbLignes; j++){
        somme += x.data[j][0];
    }
    x = x.produitParScalaire(1/somme);
}
return x;

public Matrice sousMatrice(int l, int c)

if(l < 1 || c < 1 || c > nbColonnes || l > nbLignes){throw new IllegalArgumentException();}
if(nbColonnes == 1 || nbLignes == 1){throw new MathException();}
Matrice matrice = new Matrice(nbLignes - 1, nbColonnes - 1);
for(int i = 0; i < l - 1; i++){
    for(int j = 0; j < c - 1; j++){
        matrice.data[i][j] = data[i][j];
    }
}
for(int i = l; i < nbLignes; i++){
    for(int j = 0; j < c - 1; j++){
        matrice.data[i - 1][j] = data[i][j];
    }
}
for(int i = 0; i < l - 1; i++){
    for(int j = c; j < nbColonnes; i++){
        matrice.data[i][j - 1] = data[i][j];
    }
}
for(int i = l; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        matrice.data[i - 1][j - 1] = data[i][j];
    }
}
return matrice;

Programmation sur les relations :

Class Couple

public Couple(Elt x, Elt y)

public Couple(int i, int j)

public Elt getX()

Renvoie la première composante

public Elt getY()

Renvoie la deuxième composante

public String toString()

public Couple reciproque()

Renvoie le couple réciproque du couple courant (<i,j> renvoie <j,i>)

public boolean equals(Object o)

public int hashCode()

Interface RelationInterface extends Iterable<Couple>

int MAX = Elt.MAXELT.val()

boolean estVide()

boolean contient(Couple c)

void ajouter(Couple c)

void enlever(Couple c)

EnsembleAbstrait depart()

EnsembleAbstrait arrivee()

String toString()

Class RelationDeBase

public RelationDeBase()

Construit la relation vide sur l'ensemble vide

public RelationDeBase(EnsembleAbstrait dep, EnsembleAbstrait arr)

Construit la relation vide de dep vers arr

public void ajouterDepart(Elt e)

Ajouter l'élément e à l'ensemble de départ

public void ajouterArrivee(Elt e)

Ajouter l'élément e à l'ensemble d'arrivée

public void supprimerDepart(Elt e)

Supprimer l'élément e de l'ensemble de départ (y compris les flèches)

public void supprimerArrivee(Elt e)

Supprimer l'élément e de l'ensemble d'arrivée (y compris les flèches)

Utilisation massive du foreach :

foreach d'un ensemble donnera un élément.
foreach d'une relation donnera un couple.

Abstract class RelationAbstraite implements RelationInterface

// méthodes

public boolean inclusDans(RelationInterface r)

if(r == null || !depart().equals(r.depart()) || !arrivee().equals(r.arrivee())){return false;}
for(Couple couple : this){
    if(!r.contient(couple)){return false;}
}
return true;

public boolean equals(Object o)

if(o == null){return false;}
if(o == this){return true;}
if(!(o instanceof RelationAbstraite)){return false;}
RelationAbstraite r = (RelationAbstraite) o;
return inclusDans(r) && r.inclusDans(this);

public int hashCode()

int hash = depart().hashCode() * 31 + arrivee().hashCode();
for(Couple c : this){
    hash = hash * 31 + c.hashCode();
}
return hash;

Class Relation extends RelationDeBase

// variables

public static final int MAX = Elt.MAXELT.val();

// méthodes

public Relation

super();

public Relation(EnsembleAbstrait d, EnsembleAbstrait a)

super(d, a);

public Relation clone()

return (Relation) super.clone();

public Relation(RelationInterface r)

this();
if(r == null){throw new IllegalArgumentException();}
for(Elt elt : r.depart()){ajouterDepart(elt);}
for(Elt elt : r.arrivee()){ajouterArrivee(elt);}
for(Couple c : r){ajouter(c);}

public static Relation identite(EnsembleAbstrait e)

if(e == null){throw new IllegalArgumentException();}
Relation aRenvoyer = new Relation(e, e);
for(Elt elt : e){
    aRenvoyer.ajouter(new Couple(elt, elt));
}
return aRenvoyer;

public static Relation produitCartesien(EnsembleAbstrait a, EnsembleAbstrait b)

if(a == null || b == null){throw new IllegalArgumentException();}
Relation aRenvoyer = new Relation(a, b);
for(Elt elt1 : a){
    for(Elt elt2 : b){
        aRenvoyer.ajouter(new Couple(elt1, elt2));
    }
}
return aRenvoyer;

public Relation complementaire()

Relation aRenvoyer = produitCartesien(depart(), arrivee());
for(Couple c : this){
    aRenvoyer.enlever(c);
}
return aRenvoyer;

public Relation reciproque()

Relation aRenvoyer = new Relation(depart(), arrivee());
for(Couple c : this){
    aRenvoyer.ajouter(c.reciproque());
}
return aRenvoyer;

public void ajouter(RelationInterface r)

if(r == null || !r.depart().equals(depart()) || !r.arrivee().equals(arrivee())){throw new IllegalArgumentException();}
for(Couple c : r){
    ajouter(c);
}

public void enlever(RelationInterface r)

if(r == null || !r.depart().equals(depart()) || !r.arrivee().equals(arrivee())){throw new IllegalArgumentException();}
for(Elt elt1 : r.depart()){
    for(Elt elt2 : r.arrivee()){
        Couple c = new Couple(elt1, elt2);
        if(contient(c) && r.contient(c)){enlever(c);}
    }
}

public void intersecter(RelationInterface r)

if(r == null || !r.depart().equals(depart()) || !r.arrivee().equals(arrivee())){throw new IllegalArgumentException();}
Relation tmp = clone();
for(Couple c : tmp){
    if(!r.contient(c)){enlever(c);}
}

public void apres(RelationInterface r)

if(r == null || !r.arrivee().equals(depart())){throw new IllegalArgumentException();}
Relation aRenvoyer = new Relation(r.depart(), arrivee());
for(Couple cR : r){
    for(Couple cT : this){
        if(cR.getY().equals(cT.getX())){aRenvoyer.ajouter(new Couple(cR.getX(), cT.getY()));}
    }
}
return aRenvoyer;

public void cloReflex()

if(!depart().equals(arrivee())){throw new MathException();}
for(Elt elt : depart()){
    ajouter(new Couple(elt, elt));
}

public void cloSym()

if(!depart().equals(arrivee())){throw new MathException();}
Relation tmp = clone();
for(Couple c : tmp){
    ajouter(c.reciproque());
}

public void cloTrans()

if(!depart().equals(arrivee())){throw new MathException();}
Relation tmp = new Relation(this);
for(Elt k : tmp.depart()){
    for(Elt sDepart : tmp.depart()){
        if(contient(sDepart, k)){
            for(Elt sArrivee : tmp.arrivee()){
                if(contient(k, sArrivee)){ajouter(sDepart, sArrivee);}
            }
        }
    }
}

public boolean reflexive()

if(!depart().equals(arrivee())){throw new MathException();}
for(Elt elt : depart()){
    if(!contient(elt, elt)){return false;}
}
return true;

public boolean antireflexive()

if(!depart().equals(arrivee())){throw new MathException();}
for(Elt elt : depart()){
    if(contient(new Couple(elt, elt))){return false;}
}
return true;

public boolean symetrique()

if(!depart().equals(arrivee())){throw new MathException();}
for(Couple c : this){
    if(!contient(c.reciproque())){return false;}
}
return true;

public boolean antisymetrique()

if(!depart().equals(arrivee())){throw new MathException();}
for(Couple c : this){
    if(contient(c.reciproque()) && !c.getX().equals(c.getY())){return false;}
}
return true;

public boolean transitive()

if(!depart().equals(arrivee())){throw new MathException();}
for(Couple c1 : this){
    for(Couple c2 : this){
        if(c1.getY().equals(c2.getX()) && !contient(new Couple(c1.getX(), c2.getY()))){return false;}
    }
}
return true;

Class Equivalence extends RelationAbstraite

// variables

private EnsembleAbstrait sousJac;

private Elt[] tabRep;

private int numVersion;

// méthodes

public Equivalence(EnsembleAbstrait e)

if(e == null){throw new IllegalArgumentException();}
sousJac = new Ensemble(e);
tabRep = new Elt[MAX + 1];
numVersion = 1;
for(Elt elt : e){
    tabRep[elt.val()] = elt;
}

public boolean contient(Couple c)

if(c == null){throw new IllegalArgumentException();}
if(!sousJac.contient(c.getX()) || !sousJac.contient(c.getY())){throw new IllegalArgumentException();}
return tabRep[c.getX().val()].equals(tabRep[c.getY().val()]);

public void ajouter(Couple c)

if(contient(c)){return;}
for(Elt elt : sousJac){
    if(tabRep[elt.val()].equals(tabRep[c.getX().val()])){tabRep[elt.val()] = tabRep[c.getY().val()];}
}
numVersion++;

public Equivalence(Relation r)

if(r == null){throw new IllegalArgumentException();}
sousJac = new Ensemble(r.depart());
tabRep = new Elt[MAX + 1];
for(Elt elt : r.depart()){
    tabRep[elt.val()] = elt;
}
for(Couple c : r){
    ajouter(c);
}

public EnsembeAbstrait classe(Elt e)

if(e == null || !sousJac.contient(e)){throw new IllegalArgumentException();}
Ensemble aRenvoyer = new Ensemble();
for(Elt elt : sousJac){
    if(tabRep[elt.val()].equals(tabRep[e.val()])){aRenvoyer.ajouter(elt);}
}
return aRenvoyer;

public void enlever(Couple c)

if(c == null){throw new IllegalArgumentException();}
if(!contient(c)){return;}
if(!sousJac.contient(c.getX()) || !sousJac.contient(c.getY())){throw new IllegalArgumentException();}
if(classe(c.getX()).cardinal() != 2){throw new IllegalArgumentException();}
tabRep[c.getX().val()] = c.getX();
tabRep[c.getY().val()] = c.getY();
numVersion++;

public int nbreClasses()

EnsembleAbstrait classes = new Ensemble();
for(Elt elt : sousJac){
    if(!classes.contient(elt)){classes.ajouter(tabRep[elt.val()]);}
}
return classes.cardinal();

public EnsembleAbstrait[] quotient()

EnsembleAbstrait[] quotient = new Ensemble[nbreClasses()];
for(int i = 0; i < quotient.length; i++){
    quotient[i] = new Ensemble();
}
for(Elt elt : sousJac){
    for(EnsembleAbstrait ensemble : quotient){
        if(ensemble.estVide() || tabRep[ensemble.unElement().val()].equals(tabRep[elt.val()])){
            ensemble.ajouter(elt);
            break;
        }
    }
}
return quotient;

public boolean estVide()

return sousJac.estVide();

public EnsembleAbstrait depart()

return sousJac.clone();

public EnsembleAbstrait arrivee()

return sousJac.clone();

public Iterator<Couple> iterator()

return new EquivalenceIterator();

private class EquivalenceIterator implements Iterable<Couple>

// variables

private Iterator<Couple>itC;

private int version;

// méthodes

public EquivalenceIterator()

version = numVersion;
Relation r = new Relation(sousJac, sousJac);
EnsembleInterface reste = sousJac.clone();
while(!reste.estVide()){
    Elt e = reste.unElement();
    EnsembleAbstrait classeE = classe(e);
    Iterator<Elt> itClasseE = classeE.iterator();
    while(itClasseE.hashNext()){
        Elt next = itClasseE.next();
        r.ajouter(e, next);
        r.ajouter(next, e);
        r.ajouter(next, next);
    }
    reste.enlever(classeE);
}
r.cloTrans();
itC = r.iterator();

public boolean hashNext()

return itC.hashNext();

public boolean hashNext()

return itC.hashNext();

public Couple next()

if(numVersion != version){throw new ConcurrentModificationException();}
if(!hashNext()){throw new NoSuchElementException();}
return itC.next();

public void remove()

throw new UnsupportedOperationException();

Class Ordre extends RelationAbstraite

// variables

private Relation couples;

// méthodes

public Ordre(EnsembleAbstrait e)

if(e == null){throw new IllegalArgumentException();}
couples = new Relation(e, e);
for(Elt elt : e){
    couples.ajouter(new Couple(elt, elt));
}

public Ordre(Relation r)

if(r == null){throw new IllegalArgumentException();}
if(!r.arrivee().equals(r.depart())){throw new IllegalArgumentException();}
couples = new Relation(r);
couples.cloReflex();
couples.cloTrans();
if(!couples.antisymetrique()){throw new IllegalArgumentException();}

public Ordre(Ordre or)

if(o == null){throw new IllegalArgumentException();}
couples = new Relation(or.depart(), or.arrivee());
for(Couple c : or.couples){
    couples.ajouter(c);
}

public void ajouterAuSousJacent(Elt x)

if(x == null){throw new IllegalArgumentException();}
if(depart().contient(x)){return;}
couples.ajouterDepart(x);
couples.ajouterArrivee(x);
couples.ajouter(new Couple(x, x));

public void enleverDuSousJacent(Elt x)

if(x == null){throw new IllegalArgumentException();}
if(!depart().contient(x)){return;}
couples.supprimerDepart(x);
couples.supprimerArrivee(x);

public Iterator<Couple> iterator()

return couples.iterator();

public boolean estVide()

return couples.estVide();

public boolean contient(Couple c)

if(c == null){throw new IllegalArgumentException();}
if(!couples.depart().contient(c.getX()) || !couples.arrivee().contient(c.getY())){throw new IllegalArgumentException();}
return couples.contient(c.getX(), c.getY());

public void ajouter(Couple c)

if(c == null){throw new IllegalArgumentException();}
if(contient(c)){return;}
if(contient(c.reciproque())){throw new IllegalArgumentException();}
couples.ajouter(c);
couples.cloReflex();
couples.cloTrans();
if(!couples.antisymetrique()){throw new IllegalArgumentException();}

public void enlever(Couple c)

if(c == null){throw new IllegalArgumentException();}
if(!depart().contient(c.getX())){throw new IllegalArgumentException();}
if(depart().contient(c.getY())){throw new IllegalArgumentException();}
if(!contient(new Couple(c.getX(), c.getY()))){return;}
if(!estUneAreteDeHasse(c.getX(), c.getY())){throw new IllegalArgumentException();}
Ensemble plusPetitX = plusPetitQue(c.getX());
Ensemble plusGrandY = plusGrandQue(c.getY());
for(Elt eX : plusPetitX){
    for(Elt eY : plusGrandY){
        couples.enlever(eX, eY);
    }
}
couples.cloTrans();

private Ensemble plusPetitQue(Elt e)

Ensemble min = new Ensemble();
for(Elt eC : couples.depart()){
    if(couples.contient(eC, e)){min.ajouter(eC);}
}
return min;

private Ensemble plusGrandQue(Elt e)

Ensemble max = new Ensemble();
for(Elt eC : couples.depart()){
    if(couples.contient(e, eC)){max.ajouter(eC);}
}
return max;

private boolean estUneAreteDeHasse(Elt x, Elt y)

if(!contient(new Couple(x, y))){return false;}
if(x.equals(y)){return false;}
EnsembeAbstrait aParcourir = depart();
aParcourir.enlever(x);
aParcourir.enlever(y);
for(Elt e : aParcourir){
    if(contient(new Couple(x, e)) && contient(new Couple(e, y))){return false;}
}
return true;

public boolean estUneAreteDeHasse(Couple c)

if(c == null){throw new IllegalArgumentException();}
return estUneAreteDeHasse(c.getX(), c.getY());

public EnsembleAbstrait depart()

return couples.depart();

public EnsembleAbstrait arrivee()

return couples.arrivee();

public boolean comparables(Elt x, Elt y)

if(x == null || y == null){throw new IllegalArgumentException();}
return contient(new Couple(x, y)) || contient(new Couple(y, x));

public EnsembleAbstrait minimaux(Ensemble abstrait b)

if(b == null || !b.inclusDans(depart())){throw new IllegalArgumentException();}
EnsembeAbstrait aRetourner = new Ensemble();
for(Elt e : b){
    boolean petit = true;
    for(Elt f : b){
        if(!f.equals(e) && contient(new Couple(f, e))){petit = false;}
    }
    if(petit){aRetourner.ajouter(e);}
}
return aRetourner;

public EnsembleAbstrait maximaux(Ensemble abstrait b)

if(b == null || !b.inclusDans(depart())){throw new IllegalArgumentException();}
EnsembeAbstrait aRetourner = new Ensemble();
for(Elt e : b){
    boolean grand = true;
    for(Elt f : b){
        if(!f.equals(e) && contient(new Couple(e, f))){grand = false;}
    }
    if(grand){aRetourner.ajouter(e);}
}
return aRetourner;

public Elt minimum(EnsembleAbstrait b)

if(b == null){throw new IllegalArgumentException();}
Ensemble min = minimaux(b);
if(min.cardinal() == 1){return min.unElement();}
return null;

public Elt maximum(EnsembleAbstrait b)

if(b == null){throw new IllegalArgumentException();}
Ensemble max = maximaux(b);
if(max.cardinal() == 1){return max.unElement();}
return null;

public EnsembleAbstrait minor(EnsembleAbstrait b)

if(b == null || !b.inclusDans(depart())){throw new IllegalArgumentException();}
EnsembleAbstrait aRetourner = new Ensemble();
for(Elt e : depart()){
    boolean petit = true;
    for(Elt f : b){
        if(!f.equals(e) && !contient(new Couple(e, f))){petit = false;}
    }
    if(petit){aRetourner.ajouter(e);}
}
return aRetourner;

public EnsembleAbstrait major(EnsembleAbstrait b)

if(b == null || !b.inclusDans(depart())){throw new IllegalArgumentException();}
EnsembleAbstrait aRetourner = new Ensemble();
for(Elt e : depart()){
    boolean grand = true;
    for(Elt f : b){
        if(!f.equals(e) && !contient(new Couple(f, e))){grand = false;}
    }
    if(grand){aRetourner.ajouter(e);}
}
return aRetourner;

public Elt infinum(EnsembleAbstrait b)

if(b == null){throw new IllegalArgumentException();}
return maximum(minor(b));

public Elt supremum(EnsembleAbstrait b)

if(b == null){throw new IllegalArgumentException();}
return minimum(major(b));

public boolean treillis()

for(Elt e : depart()){
    for(Elt f : depart()){
        EnsembleAbstrait a = new Ensemble();
        a.ajouter(e);
        a.ajouter(f);
        if(infinum(a) == null || supremum(a) == null){return false;}
    }
}
return true;

public String toString

return couples.toString();

Programmation sur la morphologie mathématique :

Class ImageBinaire

// variables

private final int nbLignes;

private final int nbColonnes;

private final boolean[][] data;

// méthodes

public ImageBinaire(int a, int b)

if(a < 0 || b < 0){throw new IllegalArgumentException();}
nbLignes = a;
nbColonnes = b;
data = new boolean[a][b];

public ImageBinaire(double[][] tab)

if(tab == null || tab.length == 0 || tab[0] == null || tab[0].length == 0){throw new IllegalArgumentException();}
int tmp = tab[0].length;
for(int i = 1; i < tab.length; i++){
    if(tab[i] == null || tab[i].length != tmp){throw new IllegalArgumentException();}
}
data = new boolean[tab.length][tab[0].length];
for(int i = 0; i < tab.length; i++){
    for(int j = 0; j < tab[0].length; j++){
        data[i][j] = tab[i][j];
    }
}
nbLignes = tab.length;
nbColonnes = tab[0].length;

public ImageBinaire(ImageBinaire a)

if(a == null){throw new IllegalArgumentException();}
data = new boolean[a.data.length][a.data[0].length];
for(int i = 0; i < a.data.length; i++){
    for(int j = 0; j < a.data[0].length; j++){
        data[i][j] = a.data[i][j];
    }
}
nbColonnes = a.nbColonnes;
nbLignes = a.nbLignes;

public ImageBinaire union(ImageBinaire b)

if(b == null){throw new IllegalArgumentException();}
if(nbLignes != b.nbLignes || nbColonnes != b.nbColonnes){throw new IllegalArgumentException();}
ImageBinaire aRenvoyer = new ImageBinaire(this);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        if(b.data[i][j]){aRenvoyer.data[i][j] = true;}
    }
}
return aRenvoyer;

public ImageBinaire intersec(ImageBinaire b)

if(b == null){throw new IllegalArgumentException();}
if(nbLignes != b.nbLignes || nbColonnes != b.nbColonnes){throw new IllegalArgumentException();}
ImageBinaire aRenvoyer = new ImageBinaire(nbLignes, nbColonnes);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        aRenvoyer.data[i][j] = (data[i][j] && b.data[i][j]);
    }
}
return aRenvoyer;

public ImageBinaire inverse()

ImageBinaire aRenvoyer = new ImageBinaire(this);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        aRenvoyer.data[i][j] = !data[i][j];
    }
}
return aRenvoyer;

public ImageBinaire dilatation()

ImageBinaire aRenvoyer = new ImageBinaire(this);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; i++){
        if(data[i][j]){
            if(i - 1 >= 0){aRenvoyer.data[i - 1][j] = true;}
            if(i + 1 < nbLignes){aRenvoyer.data[i + 1][j] = true;}
            if(j - 1 >= 0){aRenvoyer.data[i][j - 1] = true;}
            if(j + 1 < nbColonnes){aRenvoyer.data[i][j + 1] = true;}
        }
    }
}
return aRenvoyer;

public ImageBinaire erosion()

// méthode rapide
return inverse().dilatation().inverse();
// méthode officielle
ImageBinaire aRenvoyer = new ImageBinaire(this);
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; i++){
        if(data[i][j]){
            if(i - 1 >= 0){aRenvoyer.data[i - 1][j] = false;}
            if(i + 1 < nbLignes){aRenvoyer.data[i + 1][j] = false;}
            if(j - 1 >= 0){aRenvoyer.data[i][j - 1] = false;}
            if(j + 1 < nbColonnes){aRenvoyer.data[i][j + 1] = false;}
        }
    }
}
return aRenvoyer;

public ImageBinaire ouverture()

return erosion().dilatation();

public ImageBinaire fermeture()

return dilatation().erosion();

public ImageBinaire bord()

return erosion().inverse().intersec(this);

public String toString()

String aRenvoyer = "";
for(int i = 0; i < nbLignes; i++){
    for(int j = 0; j < nbColonnes; j++){
        aRenvoyer += (data[i][j]) ? 1 : 0;
    }
    if(i != nbLignes - 1){aRenvoyer += "\n";}
}
return aRenvoyer;