Archives de l’auteur : pedago

PPC : Miniprojets

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Mini-projets de PPC

Objectif

Maîtriser les bases de l’utilisation de CHOCO avec des contraintes à domaines finis.

Prérequis

Partie I

Miniprojet 1

Ce travail peut rapporter jusqu’à 2 points. Vous pourrez avoir une assistance et une pré-validation avec droit à l’erreur en séances de TP.


Énoncé

Vous devez implémenter en Java et CHOCO un programme permettant de résoudre le problèmes des sacs à dos présenté en exercice de modélisation dans la partie B du cours.

On a \(N\) objets numérotés de 0 à \(N-\)1 et \(K\) sacs numérotés de 0 à \(K-1\). Chaque objet peut être embarqué dans au plus un sac. Chaque objet a un poids et une valeur. On note \(w_0, …, w_{N-1}\) les poids des objets et \(v_0, …, v_{K-1}\) leurs valeurs. Le poids cumulé des objet embarqués dans un même sac ne doit pas excéder une valeur \(W\). La valeur cumulée de tous les objets embarqués dans tous les sacs doit être au moins égale à \(V\).

Vous pouvez bien sûr vous inspirer de la modélisation proposée dans les indices et solutions de la partie B du cours.

Voici comment les données d’une instance du problème peuvent être représentées en Java :

int[] w = {7000,2000,3000,5000,5000,4000,4000,3000,5000,7000};
int[] v = {150,100,200,50,100,200,150,200,100,100};
int N = 10; int K=3;
int V = 1000; int W = 10000;

Votre solution devra être testée avec des instances cohérentes et des instances incohérentes non trivialement simplifiables. Une instance est dite trivialement simplifiable si elle comporte des objets de poids supérieur à \(W\) ou si la somme des valeurs des objets est inférieure à \(V\).

Pour toute instance cohérente, votre programme doit afficher une solution. L’affichage devra indiquer les objet embarqués dans chaque sac, soit sous forme explicite, soit sous une forme permettant de retrouver l’information à partir de l’affichage des valeurs des variables. Dans ce dernier cas, vous devrez donner sous forme explicite, par exemple à l’aide d’une représentation sur papier, les solutions de vos instances de test.


Livrables

Si vous terminez ce projet avant la fin de la première heure de la troisième et dernière séance de TP, vous n’avez pas à rédiger de document. Vous devrez monter à votre enseignant votre code commenté et lui faire une démo en faisant apparaitre explicitement les solutions, quand applicable.

Si vous terminez plus tard et que l’enseignant n’a pas le temps de valider votre travail, vous devrez lui transmettre votre code commenté, une copie d’écran de vos instances de tests et résultats, un document illustrant les solutions obtenues si celle-ci ne sont pas explicites sur les copies d’écran (par explicite on entend que les objets embarqués dans chaque sac apparaissent clairement), et un document d’une ou deux pages expliquant comment vous avez traduit votre modèle théorique en Java + CHOCO.



Miniprojet 2

Énoncé

Vous devez modéliser le problème suivant :

Soit un rectangle de largeur \(L\) et de hauteur \(H\), ou \(H\) et \(L\) sont des entiers. Soient \(K\) rectangles de largeurs et hauteurs \(l_1, h_1,…, l_k, h_k\), qui sont également des valeurs entières.

Peut-on placer les \(K\) petits rectangles dans le grand rectangle sans qu’aucun petit rectangle ne chevauche un autre ? Si c’est possible, une solution doit être donnée. Un affichage graphique de cette solution n’est pas exigé. Les positions des coins inférieurs gauche de chaque petit rectangle sont suffisantes.

La figure ci-dessous donne un exemple d’instance du problème et d’une solution.

image-20211003134447539

Pour traiter ce sujet, vous pourriez avoir besoin de spécifier des contraintes complexes par composition logique (négation, disjonction,…) de contraintes plus simple. La lecture de la documentation du site https://choco-solver.org, et notamment de cette page concernant la composition de contraintes arithmétiques, pourra vous apporter des informations très utiles.

Le petit exemple suivant (sans rapport avec le sujet) montre comment exprimer facilement la contrainte \((A+B=3) \vee (A+B=5)\), où \(A\) et \(B\) sont des variables de domaine \(1..5\).

Model model = new Model("Test");
IntVar A = model.intVar("A", 1,5);
IntVar B = model.intVar("B", 1,5);
( A.add(B).eq(3) ).or( A.add(B).eq(5) ).post();

Livrables

Pour livrer ce projet, vous devez vous inscrire à l’équipe Teams Livraison projets PPC 2122 grâce au code d’accès ipr9fop. Vous aurez alors accès à un devoir permettant de livrer le projet.

Les fichiers à remettre sont les suivants. Merci de ne pas les placer dans des archives zip ou autres.

  • Le code java, dans un unique fichier avec l’extension java, de votre solution. Le code devra être commenté et indenté en style Allman, c’est à dire avec un alignement strict des accolades ouvrantes et fermantes.
  • Un document au format pdf d’au plus 3 pages
    • expliquant succinctement le principe de votre modélisation, avec autant que possible des illustrations qui peuvent être des photographies de dessins réalisées à la main,
    • et présentant les instances avec lesquelles vous avez testé votre programme et les résultats obtenus. Les résultats doivent être représentés sous la forme d’un dessins, ne serait-ce que la photographie d’un croquis fait à la main sur papier. Vous ne serez pas évalués sur la forme. Le seul but est que le correcteur et vous-même puissent vérifier que les solutions trouvées par le solveur sont correctes.

Vous pouvez utiliser l’instance présentée en exemple ci-dessus pour la mise au point de votre programme, mais vous devez créer au moins deux instances de votre cru : une criticalement cohérente et une incohérente non triviale.

Par criticalement cohérente, on entend que la somme des aires des petits rectangles est égale à l’aire du grand rectangle.

Par incohérente non triviale, on entend que la somme des aires des petits rectangles est au plus égale à l’aire du grand rectangle, mais qu’il n’y a aucune solution. Faites preuve de créativité.

Si vous avez travaillé en binôme,

  • l’un des auteurs doit livrer les deux fichiers du projet, avec le nom du coauteur mentionné dans chaque document,
  • et l’autre auteur doit seulement livrer un fichier pdf d’une page sur laquelle est juste indiqué le nom du coauteur.

POO – CC1 avec corrigés

Partie A

A1 (2 point)

Réalisez une méthode de classe…

public static void amplitude(int[] tab)
{
  // À compléter
}

…qui retourne la différence entre la plus grande et la plus petite valeur du tableau tab. Par exemple si tab contient les valeurs 5, 1, 4, 23, 4 ,4, 8, 5, alors la valeur de retour devra être 22 c’est à dire 23-1.

"Solution"

public static int amplitude(int[] tab)
{
    int mini = tab[0]; int maxi = tab[0];
    for(int i=1; i<tab.length; i++)
    {
        if(tab[i] > maxi) maxi = tab[i];
        else if(tab[i] < mini) mini = tab[i];
    }
    return  maxi - mini;
}

A2 (1 point)

Réalisez une méthode main qui crée un tableau d’entier contenant les valeurs de l’exemple précédent, qui appelle la méthode amplitude avec ce tableau et affiche le résultat.

"Solution"

public static void main(String[] args)
{
    int[] tab = {5, 1, 4, 23, 4, 4, 8, 5};
    System.out.println(amplitude(tab));
}


Partie B

Soit une classe Terrain représentant un terrain agricole de forme rectangulaire localisé par les coordonnées géographiques (qui sont des valeurs de types double, en mètres) de deux de ses coins opposés. A cette fin, la classe Terrain a 4 attributs privés de type double nommés x1, y1, x2, y2. Elle possède en outre un attribut privé nom de type String qui permet d’attribuer un nom à chaque terrain.

La classe Terrain dispose d’un constructeur Terrain(double x1, double y1, double x2, double y2, String nom) permettant la création d’une instance à l’aide des informations fournies en paramètres. Elle dispose également d’une méthode toString retournant une description textuelle du terrain courant. On supposera que x1 < x2 et y1 < y2.

public class Terrain
{
    private String nom;
    private double x1; private double y1;
    private double x2; private double y2;

    public Terrain(String nom, double x1, double y1, double x2, double y2)
    {
        this.nom = nom;
        this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2;
    }

    public String toString()

    {
        return "Terrain : " + nom + "(" + x1 + "," + y1 + ") (" + x2 + "," + y2 +")";
    }
}

Soit une classe Cadastre représentant une liste de plusieurs terrains. Nous appellerons cadastre toute instance de cette classe. Cette classe a un attribut privé terrains de type ArrayList<Terrain> qui permet le stockage de toutes les instances de Terrain du cadastre courant.


B1 (1 point)

Donnez la définition du constructeur de la classe Cadastre.

"Solution"

public Cadastre()
{
    this.terrains = new ArrayList<>();
}

B2 (1 point)

Donnez la définition d’une méthode d’instance public void add(double x1, double y1, double x2, double y2, String nom) de la classe Cadastre qui ajoute un nouveau terrain à la liste.

"Solution"

public void add(double x1, double y1, double x2, double y2, String nom)
{
    terrains.add(new Terrain(nom, x1, y1, x2, y2));
}

B3 (1 point)

On suppose que la classe Terrain a une méthode d’instance public double surface() qui retourne la surface du terrain courant.

Donnez la définition d’une méthode d’instance public double surface() de la classe Cadastre qui retourne la somme des surfaces des terrains du cadastre courant.

"Solution"

public double surface()
{
    double r = 0.0;
    for(Terrain t : terrains)
    {
        r = r + t.surface();
    }
    return r;
}

B4 (1point)

Donnez les lignes de codes, supposées être dans une méthode de classe void test() située dans une classe Test, permettant de créer un cadastre, d’y ajouter deux terrains, et d’afficher la surface cumulée des terrains du cadastre.

"Solution"

Cadastre cad = new Cadastre();
cad.add(100,200,120,230,"parcelle 1");
cad.add(560,320,570,330,"parcelle 2");
System.out.println(cad.surface());

Partie C

On considère les classes et interface suivantes.

image-20210926101630425


La classe Point représente juste un point avec deux coordonnées de type double.

public class Point
{
    private double x,y;

    public Point(double x, double y) { ... }

    public String toString() { ... }
}

La classe Courbe représente une liste de points pouvant être interprétée comme une courbe si on imagine que chaque point est relié au suivant (si applicable).

public class Courbe
{
    private ArrayList<Point> points;

    public Courbe(){ ... }

    public void add(double x, double y) { ... }

    public String toString() { return }
}

Voici une représentation graphique de l’instance de courbe représentée par la liste de points [(1.0,1.0), (2.0,3.0), (3.0,2.0)].

image-20210926104152664

Ceci est juste donné à titre d’exemple. La partie affichage graphique n’est pas du tout traitée dans cet exercice.


L’interface Graphable oblige les classes qui l’implémentent à être dotées d’une méthode permettant de produire une instance de courbe représentée par une liste de n points dont les abscisses (coordonnées \(x\)) vont de min à max avec des écarts constants entre ces abscisses.

Par exemple si n vaut 5, min vaut 10.0 et max vaut 12.0, les abscisses des 5 points devront être 10.0, 10.5, 11.0, 11.5 et 12.0.

public interface Graphable
{
    public Courbe getCourbe(double min, double max, int n);
}

La classe abstraite Fonction représente une fonction calculable. Elle dispose d’une méthode abstraite getImage qui accepte en paramètre une valeur x et retourne l’image de x par cette fonction. Par exemple, dans une classe dérivée de Fonction qui représente la fonction \(x \mapsto x^2\), l’appel getImage(3.0) retournera 9.0.

public abstract class Fonction implements Graphable
{
    public abstract double getImage(double x);

    public Courbe getCourbe(double min, double max, int n)
    {
        // À compléter
    }
}

C1 (2 points)

Implémentez la méthode getCourbe de la classe Foncton.

"Solution"

public Courbe getCourbe(double min, double max, int n)
{
    double delta = (max - min) / (n - 1);
    double x = min;
    Courbe r = new Courbe();
    for(int i = 0; i< n; i++)
    {
        r.add(x, getImage(x));
        x = x + delta;
    }
    return r;
}

C2 (1 point)

Réalisez une classe Xcarre sans attribut, dérivée de Fonction représentant la fonction qui à tout réel \(x\) associe \(x^2\).

"Solution"

public class Xcarre extends Fonction
{
    public double getImage(double x)
    {
        return x * x;
    }
}

C3 (2 points)

On souhaite que la méthode main suivante…

public static void main(String[] args)
{
    Fonction f = new Xcarre();
    System.out.println(f.getNom());
}

…produise l’affichage

Fonction carré

Donnez le code complet de la ou des méthodes concrètes et / ou abstraites à ajouter aux classes Fonction et Xcarre pour obtenir ce résultat sans ajouter d’attribut à ces classses.

"Solution"

Dans Fonction :

public abstract String getNom();

Dans Xcarre :

public String getNom()
{
    return "Fonction carré";
}

Partie D

La classe Fraction représente une fraction (un nombre rationnel) ayant un dénominateur et un numérateur.

public class Fraction
{
    private int num;
    private int den;

    public Fraction(int numerateur, int denominateur) throws  DenZero
    {
        if(denominateur == 0) throw new DenZero();
        this.num = numerateur;
        this.den = denominateur;
        normalise();
    }

    public int getDenum() {return den;}

    public int getNum() {return num;}

    public void normalise()
    {
        // Code classifié très secret cosmique
    }

    public Fraction add(Fraction f)
    {
        // À comlpléter
    }

    public String toString()
    {
        return num + " / " + den;
    }
}

Regardez attentivement le code du constructeur. Il lève une exception de type DenZero si par malheur on tente de l’utiliser pour créer une fraction ayant un dénominateur nul. Dans le cas contraire, il initialise les attributs et appelle une méthode de normalisation. Le code de cette méthode est ultra secret et ne sera pas révélé ici. Il permet de normaliser la fraction de manière à ce que le dénominateur soit toujours positif et de la simplifier de manière à minimiser les valeurs du numérateur et du dénominateur. Par exemple, si les valeurs données sont 4 et 12, après simplification au aura 1 / 3.

La classe DenZero est définie ainsi :

public class DenZero extends Exception
{
    public String toString()
    {
        return "Dénominateur nul";
    }
}

D1 (2 points)

Complétez le fonction testFrac suivante de manière à ce qu’elle crée une instance de Fraction représentant la fraction \(a/b\) et affiche sa représentation à l’aide de la méthode toString. Dans le cas où le constructeur de la classe Fraction lève une exception de type DenZero, le message "ERREUR : Dénominateur nul" doit s’afficher.

public static void testFrac(int a, int b)
{
    // À compléter
}
"Solution"

public static void testFrac(int a, int b)
{
    try
    {
        Fraction r = new Fraction(a,b);
        System.out.println(r.toString());
    }
    catch(DenZero e)
    {
        System.out.println("ERREUR  : " + e);
    }
}

D2 (2 points)

On rappelle que la somme de deux fractions valides (avec dénominateurs non nuls) \(a/b\) et \(c/d\) a pour résultat la simplification (avec la méthode normalize) de \((ad + bc) / bd\).

Complétez une méthode add de la classe Fraction en faisant en sorte qu’elle retourne la somme de la fraction courante et de cette désignée par le paramètre f. La fraction courante ne doit pas être modifiée. Si l’exception DenZero est levée lors de la construction du résultat (Ça ne devrait pas se produire, mais il faut le prévoir quand même), la méthode add doit lever une exception de type RuntimeException avec message "Erreur inattendue" passé en argument à son constructeur.

public Fraction add(Fraction f)
{
    // À compléter
}
"Solution"

public Fraction add(Fraction f)
{
    int n = (getNum() * f.getDenum()) + (f.getNum() * getDenum());
    int d = getDenum() * f.getDenum();
    try
    {
        return new Fraction(n, d);
    }
    catch (DenZero e)
    {
        throw new RuntimeException("Erreur inattendue");
    }
}

Partie E

Un multi-ensemble est une structure de donnée pouvant contenir des éléments, comme un ensemble, mais à la différence d’un ensemble, chaque élément peut avoir plusieurs occurrences. Par exemple, {2, 5, 5, 56} est un multi-ensemble dont les éléments sont 2, 5 et 56. L’élément 5 a deux occurrences, alors que les autres en ont une seule.

La classe MultiInt représente un multi-ensemble d’entiers naturels (c’est à dire supérieurs ou égaux à 0).

public class MultiInt
{
    // Attributs à completer

    public MultiInt(int max)
    {
        // À compléter
    }

    public void add(int e)
    {
				// À compléter
    }

    public void remove(int e)
    {
				// À compléter
    }
    // ...
}

La classe MultiInt comporte d’autres méthodes, mais seules celles qui sont mentionnées plus haut nous intéressent dans cet exercices.

Le constructeur permet de créer un multi-ensemble pouvant contenir les éléments compris entre 0 et max, chacun pouvant n’avoir aucune occurrence ou avoir un nombre quelconque d’occurrences.


E1 (4 points)

Vous devez donner le ou les attributs de la classe et le code du constructeur et des deux méthodes. Si e est un entier compris entre 0 et max et m est une instance de MultiInt construite de la manière suivante…

MultiInt m = new MultiInt(max);

…alors :

  • m.add(e) ajoute une occurrence de e dans le multi-ensemble désigné par m,
  • m.remove(e) retire une occurrence de e s’il en reste au moins une et sinon n’a aucun effet.

Vous devez essayer de trouver une solution permettant de minimiser la complexité en temps (en fonction du nombre d’éléments du multi-ensemble courant) des méthodes add et remove. Vous devez également donner l’ordre de grandeur asymptotique des ces complexité (constante ou logarithmique ou linéaire ou quadratique ou autre …) en justifiant brièvement votre réponse.

"Solution"

public class MultiInt
{
    private int[] tab;

    public MultiInt(int max)
    {
        tab = new int[max+1];
    }

    public void add(int e)
    {
        tab[e]++;
    }

    public void remove(int e)
    {
        if(tab[e]>0) tab[e]--;
    }

    public int count(int e)
    {
        return tab[e];
    }
}

Complexité :

  • add : \(\Theta(1)\) (temps constant)
  • remove : \(\Theta(1)\) (temps constant)


PPC : Test d’auto-évaluation sur la partie B

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Objectif

Entraînement et évaluation partielle des vos compétences en modélisation.

Prérequis

Parties A et B


Question 1

On appelle séquenceur d’un mot binaire \(a_1 a_2 … a_n\) le mot binaire \(x_2 … x_n\) tel que \(x_i = 1\) si et seulement si \(a_{i-1} \neq a_i\).

Voici un exemple de mot binaire et de son séquenceur.

mot m :           001110000000
séquenceur de m :  01001000000

On considère les variables \(A_1, …, A_n\) et \(X_2, …, X_n\) ayant toutes pour domaines \(\{0,1\}\).

Vous devez spécifier un réseau de contraintes \(T_n\) tel que toute assignation \(A_1=a_1,…,A_n=a_n\), \(X_2=x_2,…,X_n=x_n\) satisfait \(T_n\) si et seulement si le mot binaire \(x_2 … x_n\) est le séquenceur du mot binaire \(a_1 a_2 … a_n\).

Par exemple, l’assignation \(A_1=1, A_2=0, A_3=1, X_2=1, X_3=1\) satisfait \(T_3\) car 11 est le séquenceur de 101. Par contre l’assignation \(A_1=1, A_2=0, A_3=1, X_2=0, X_3=1\) ne satisfait pas \(T_3\) car 01 n’est pas le séquenceur de 101.

\(T_n\) est constitué de \(n-1\) contraintes nommées \(q_1, …, q_{n-1}\).

Précisez les variables reliées par chaque contrainte. Donnez une spécification en extension et une spécification en compréhension (avec des opérations arithmétiques ou logiques) d’une de ces contraintes.

Réponse

Chaque contrainte \(q_i\) relie les variables \(A_i\), \(A_{i+1}\) et \(X_{i+1}\).

Exemple de spécification de \(q_i\) en compréhension : $X_{i+1} = |A_{i}-A_{i+1}|$.

Spécification de \(q_i\) en extension : sur \(A_i\), \(A_{i+1}\), \(X_{i+1}\) : \(\{(0,0,0),(1,1,0),(0,1,1),(1,0,1)\}\).

Question 2

En supposant que \(n>3\), quelles contraintes faut-il ajouter au réseau \(T_n\) de la question précédente pour exprimer que le mot binaire \(a_1 a_2 … a_n\) comporte exactement une séquence de 3 bits à 1 consécutifs, tous les autres bits étant à 0 ?

On entend par là que si on note le réseau \(T’_n\) le réseau obtenu en ajoutant à \(T_n\) ces nouvelles contraintes, alors toute assignation partielle \(A_1=a_1,…,A_n=a_n\) a une extension satisfaisant \(T’_n\) si et seulement si le mot binaire \(a_1 a_2 … a_n\) comporte exactement une séquence de 3 bits à 1 consécutifs, tous les autres bits étant à 0, comme dans les exemples suivants : 00111100, 000111, 111000000.

Les nouvelles contraintes sont à donner en compréhension.

Réponse

  • \(\sum_{i=1}^n A_i = 3\) (Il y a trois bits à 1).
  • \(\sum_{i=2}^n X_i \leq 2\) (Il y a au plus deux transitions).
  • \(A_1 + A_n \leq 1\) (Il ne doit pas y avoir un bit à 1 aux deux extrémité)

Question 3

On considère un dirigeable dont la nacelle est scindée en trois parties : une cabine destinée aux passagers au milieu et deux compartiments de fret, nommés A et B, aux extrémités. Parmi \(N\) objets, numérotés de 1 à \(N\) et de poids \(w_1, …, w_n\) , au moins \(K\) doivent être embarqués en respectant les conditions suivantes :

  • La somme des poids des objets embarqués dans le compartiment A doit être égale à la somme des poids des objets embarqués dans le compartiment B.
  • La somme des poids des objets embarqués dans les deux compartiments ne doit pas dépasser une valeur W.

Les valeurs \(K\) et W, ainsi que les poids des \(N\) objets susceptibles d’être embarqués, sont des données connues. Vous devez modéliser ce problème sous la forme d’un réseau de contraintes utilisant exclusivement des variables à domaine {0,1}. Vous devez utiliser des contraintes arithmétiques linéaires construites à l’aide de sommes, produits d’une variable par une constante, opérateurs de comparaison (\(=\), \(\neq\), \(<\), \(>\), \(\leq\), \(\geq\)). Précisez bien le rôle et la signification d’une assignation à 1 de chaque variable.

Réponse

Variables :

  • \(A_1, … ,A_N\) de domaine \(\{0,1\}\). \(A_N=1\) signifie que l’objet numéro \(i\) va dans le compartiment A.
  • \(B_1, … ,B_N\) de domaine \(\{0,1\}\). \(B_N=1\) signifie que l’objet numéro \(i\) va dans le compartiment B.

Contraintes :

  • \((\sum_{i=1}^n A_i) + (\sum_{i=1}^n B_i) \geq K\) (au moins \(K\) objets embarqués)
  • \(\sum_{i=1}^n w_i A_i = \sum_{i=1}^n w_i B_i\) (équilibre des charges)
  • \(\sum_{i=1}^n w_i A_i + \sum_{i=1}^n w_i B_i \leq W\) (charge maximale autorisée)
  • Pour tout \(i\in 1..N\), \(A_i + B_i < 2\) (un objet est est embarqué dans un seul compartiment ou n’est pas embarqué)

Question 4

On considère 8 variables \(X_1, X_2, Y_1, Y_2\), \(X’_1, X’_2, Y’_1, Y’_2\) ayant toutes pour domaine l’ensemble \(0..N\) des entiers naturels compris entre 0 et \(N\).

Une assignation de ces variables représente deux rectangles situés dans un repère cartésien discret avec les conventions suivantes :

  • \(X_1, Y_1\) sont les coordonnées du coin inférieur gauche du premier rectangle.
  • \(X_2, Y_2\) sont les coordonnées du coin supérieur droit du premier rectangle.
  • \(X’_1, Y’_1\) sont les coordonnées du coin inférieur gauche du deuxième rectangle.
  • \(X’_2, Y’_2\) sont les coordonnées du coin supérieur droit du deuxième rectangle.

La figure ci-dessous représente un exemple de positions et formes des deux rectangles, mais il y a un très grand nombre d’autres possibilités.

Vous devez spécifier les contraintes qui expriment que les deux rectangles se recouvrent (l’intersection entre les 2 est non vide). La ou les contraintes à écrire peuvent combiner des opérations arithmétiques (additions, soustractions, comparaisons) et logiques (et, non).

On suppose que \(X_2 > X_1\), \(Y_2 >Y_2\), \(X’_2 > X’_1\) et \(Y’_2 >Y’_2\).

Réponse

\(X’_1 < X_2\),

\(X_1 < X’_2\), 

\(Y’_1 < Y_2\), 

\(Y_1 < Y’_2\)

Question 5

On considère un échiquier (une grille) de N par N. Une pièce appelée cavalier peut se déplacer sur cette grille en se décalant de deux positions horizontalement et d’une verticalement ou de deux positions verticalement et d’une horizontalement. La figure ci-dessous donne deux exemples indépendants dans lesquels la grosse pastille désigne la position initiale d’un cavalier et les petites pastilles désignent les cases pouvant être atteintes par ce cavalier.

image2

On considère les variables \(X_1, Y_1, X_2, Y_2, V, H\) de domaines respectifs \(1..N\), \(1..N\), \(1..N\), \(1..N\), \(\{-2,-1,1,2\}\), \(\{-2,-1,1,2\}\).

Donnez en compréhension les contraintes qui spécifient qu’un cavalier situé en position \((X_1,Y_1)\) peut aller en \((X_2,Y_2)\) en se déplaçant de \(H\) cases horizontalement et de \(V\) case verticalement.

Réponse

  • $|X_1-X_2| = H$
  • $|Y_1-Y_2| = V$
  • \(H\neq V\)

Question 6

On numérote de la manière suivante les 8 déplacements réalisables par un cavalier sous réserve que les cases de destination soient dans les limites de l’échiquier.

image3

On ajoute une variable \(D\) de domaine \(1..8\) au réseau de contraintes précédent. Donnez en extension la contrainte à ajouter entre \(V\), \(H\) et \(D\) pour que dans toute assignation satisfaisant toutes les contraintes, \(D\) aie pour valeur le numéro du déplacement correspondant aux valeurs de \(V\) et \(H\).

Réponse

Sur \(V,H,D\) : \(\{(2,1,1),(1,2,2),(-1,2,3),(-2,1,4),(-2,-1,5),(-1,-2,6),(1,-2,7),(2,-1,8)\}\)

POO : Test Partie C

POO : Test Partie C

En licence pro MI AW

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne


On considère l’interface suivante :

public interface RandGen
{
    public void setMin(double min);
    public void setMax(double max);
    public double getMin();
    public double getMax();
    public String getLaw();
    public double draws();
}

Les classes qui implémentent cette interface ont vocation à produire des nombres aléatoires de type double compris entre deux valeurs pouvant être déterminées par les méthodes setMin et setMax et pouvant être consultées à l’aide des méthodes getMin et getMax. Ces classes doivent aussi disposer d’une méthode getLaws qui retourne une chaîne de caractères décrivant la loi de probabilité utilisée et d’une méthode draws dont le rôle est de produire une valeur aléatoire dans l’intervalle getMin() .. getMax().


La classe abstraite GenericRandGen implémente l’interface RandGen.

public abstract class GenericRandGen implements RandGen
{
    private double min;
    private double max;

    public GenericRandGen()
    {
        this.min = 0.0; this.max = 1.0;
    }

    public void setMin(double min) {this.min = min;}

    public void setMax(double max) {this.max = max;}

    public double getMin() {return this.min;}

    public double getMax() {return this.max;}

    public abstract String getLaw();

    public abstract double draws();

    public String toString()
    {
        return "Générator " + getLaw() + " in [" + min + "," + max + "]";
    }

    public double[] sample(int n)
    {
        // À compléter
    }
}

La méthode sample produit un tableau de longueur n rempli de valeurs alétoires produites par la méthode draws.

Q1 (1.5 point)

Complétez la méthode sample de la classeGenericRandGen.

public double[] sample(int n)
{
    // À compléter
}

Merci d’envoyer votre réponse à Olivier Bailleux via teams.

Q2 (1.5 points)

Complétez la classe UniformGen qui représente un générateur aléatoire permettant de produire des valeurs selon une loi de probabilité uniforme. Ces valeurs peuvent être obtenues à partir de la méthode Math.random() qui produit une valeur comprise entre 0.0 et 1.0 selon une loi uniforme.

public class UniformGen extends GenericRandGen
{
    // À compléter
}

Merci d’envoyer votre réponse à Olivier Bailleux via teams.

Q3 (2 points)

Réalisez une méthode main, situé dans une classe Main, qui :

  • Crée un générateur de type UniformGen.
  • Initialise à 1.0 et 3.0 les bornes minimum et maximum de l’intervalle des valeurs pouvant être produites par ce générateur.
  • Utilise la méthode sample pour produire une tableau de 10 nombres aléatoires.
  • Affiche à l’écran les valeurs récupérées dans ce tableau.
public class Main
{
    public static void main(String[] args)
    {
        // À compléter
    }
}

Merci d’envoyer votre réponse à Olivier Bailleux via teams.

Programmation par contraintes : partie D

Programmation par contraintes

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Partie D : résolution énumérative

Objectif

Comprendre le principe de fonctionnement d’un solveur de type MAC (Maintaining Arc Consistency) et être capable de simuler le déroulement de l’exécution d’un tel solveur sur une instance de problème dont l’arbre de recherche peut être dessiné sur une feuille A4, et d’énumérer ou comptabiliser les solutions (si applicable) de cette instance.

Prérequis

Parties A et C

Introduction

Résoudre un réseau de contraintes, c’est déterminer s’il existe au moins une assignation des variables qui satisfait toutes les contraintes. Le nombre de ces assignations étant proprement astronomique – il croît exponentiellement en fonction du nombre de variables – il n’est pas possible en pratique d’énumérer et de tester une par une toutes les assignations possibles.

La résolution dite « énumérative » ne l’est donc pas totalement mais fait aussi appel à des déductions pour accélérer la recherche d’éventuelle solutions. Dans le cas du solveur MAC que nous allons étudier, ces déductions sont des restaurations de cohérence de domaines.

L’idée de l’algorithme MAC est de décomposer le réseau de contraintes à résoudre, après restauration de la cohérence de domaines, en plusieurs réseaux plus simples dans lesquels une des variables du réseau initial a été assignée avec une des valeurs de son domaine. Par exemple, un réseau ayant une variable A de domaine {1, 2} sera décomposé en deux réseaux : un dans lequel la variable A vaut 1 et un dans lequel elle vaut 2. Chacun de ses réseaux sera filtré et si nécessaire, à nouveau décomposé sur la base d’une autre variable. La variable A est appelée variable de branchement.

image1

D-dec-10

Soit le réseau de contraintes $(a\vee b \vee c), (\neg a \vee \neg c), (\neg b \vee c)$, où les variables $a,b,c$ ont toutes pour domaine ${0,1}$. Donnez les réseaux obtenus pour $a=0$ et $a=1$.

"Solution"

  • $a=0$ : $(b \vee c), (\neg b \vee c)$
  • $a=1$ : $(\neg c), (\neg b \vee c)$

En effet, pour $a=0$, la contrainte $(\neg a\vee \neg c)$ est satisfaite, on peut donc la retirer du réseau. D’autre part, la contrainte $(a\vee b \vee c)$ peut se simplifier en $(b \vee c)$.

Pour $a=1$, je vous laisse vérifier par vous-même les simplifications.

D2 : Algorithme MAC

Cette version de l’algorithme produit toutes les solutions. On peut la modifier pour qu’elle s’arrête dès qu’une solution est trouvée.

image2

Simulons l’exécution de cet algorithme sur le réseau suivant :

image3

La première chose à faire est de restaurer la cohérence de domaines. Cela peut permettre de simplifier le problème avant de faire le premier branchement. Voici le résultat du filtrage.

image4

Si ce résultat vous paraît étonnant, c’est que vous ne maîtrisez pas le badge C, qui est un prérequis (où que le rédacteur du présent document s’est trompé).

Le filtrage simplifie le réseau (ce n’est pas toujours le cas), mais ne produit pas immédiatement de solution et ne fait pas apparaître d’incohérence (domaine vide).

Il nous faut donc choisir une variable de branchement. Nous allons utiliser la variable A. Nous obtenons l’arbre de recherche suivant, qui permet d’énumérer les deux solutions du réseau. Selon les besoins, on peut arrêter la recherche à la première solution ou n’énumérer qu’une partie des solutions. Si toute les branches de l’arbre de recherche aboutissent à une incohérence (domaine vide après filtrage), on conclut à l’incohérence du réseau.

image5

En pratique, pour présenter une simulation de résolution, on ne redessinera pas tout le réseau de contraintes à chaque nœud, mais seulement les domaines et les variables de branchement.

image6

D-dec-20

Est-il plus avantageux, moins avantageux ou aussi avantageux d’utiliser la variable $B$ comme variable de branchement à la racine de l’arbre de recherche ?

"Solution"

C’est plus avantageux car pour $B=2$, on déduit $A\neq 2$ puis $C\neq 4$ par filtrage et on obtient une solution. Pour $B=3$, on déduit $C \neq 3$ puis $A \neq 2$ par filtrage et on obtient la deuxième solution. On a donc un seul branchement au lieu de deux.

D3 : variantes

Filtrage affaibli

Dans l’algorithme MAC, un filtrage complet par restauration de cohérence de domaine est réalisé à chaque nœud (y compris racine) de l’arbre de recherche. Ce filtrage est généralement rentable dans la mesure où le temps qu’il consomme est largement compensé par la réduction du nombre de branchements, donc de la taille de l’arbre de recherche. Mais il peut y avoir des exceptions pour certaines contraintes dont la restauration de cohérence de domaines est couteuse, pour lesquelles on peut utiliser un filtrage plus « faible ».

Par exemple, restaurer la cohérence de domaine sur une contrainte de type $a_{1} x_{1} + \ldots + a_{n} x_{n} = b$, où $a_{1}, \ldots, a_{n}$ et $b$ sont des entiers relatifs, est très couteux. On ne connait aucun algorithme capable de le faire en temps polynomial. (Ce qui est contre-intuitif !)

On peut utiliser à la place un filtrage très rapide bien que moins puissant, qui consiste à restaurer la cohérence de domaine sur les deux contraintes $a_{1} x_{1} + \ldots + a_{n} x_{n} \leq b$ et $a_{1}\ x_{1} + \ldots + a_{n} x_{n} \geq b$. Même si cela vous paraît très étrange en première lecture, restaurer la cohérence de domaine sur les deux inégalités ne permet pas de la restaurer sur l’égalité.

Pas convaincu ?

D-dec-30

Restaurez la cohérence de domaine sur le réseau de contraintes suivant, avec domaine {0,1} pour toutes les variables :

  • $q_{1}: x_{1} + 2x_{2} + 3x_{3} + 4x_{4} \leq 6$

  • $q_{2}: x_{1} + 2x_{2} + 3x_{3} + 4x_{4} \geq 6$

"Solution"

On ne peut retirer aucune valeur des domaines en considérant les deux contraintes séparément. Si vous ne voyez pas pourquoi, c’est que le badge C n’est pas complètement acquis. Vous avez peut-être été en excès de confiance si vous pensiez le maîtriser.

En effet, en mettant n’importe laquelle des variables à 0, on peut toujours trouver une manière d’assigner les autres variables pour obtenir une somme au moins égale à 6 et une manière de les assigner pour obtenir une somme au plus égale à 6. Il en va de même en assignant n’importe quelle variable à 1.

D-dec-31

A présent, toujours avec les mêmes domaines initiaux {0,1}, restaurez la cohérence de domaine sur la contrainte suivante :

  • $q : x_{1} + 2x_{2} + 3x_{3} + 4x_{4} = 6$

Ce n’est pas immédiat à réaliser. Il faut se poser des questions du genre « est-il possible d’obtenir une somme égale à 6 si $x_{1}$ vaut 1 ? »

"Solution"

La réponse est oui. Il suffit d’assigner $x_{2} = 1, x_{3} = 1,x_{4} = 0$. Donc $x_{1} = 1$ a un support, et donc on ne retire pas 1 du domaine de $x_{1}$. En faisant un raisonnement similaire pour les autres valeurs, on obtient les domaines respectifs suivants pour les variables $x_{1}$ à $x_{4}$ : {0,1}, {1}, {0,1}, {0,1}.


La restauration de la cohérence de domaines sur $q$ a permis de faire un filtrage qui n’a pas été réalisé par la restauration de la cohérence de domaines sur $q_{1}$ et $q_{2}$. Mais faute de disposer d’un algorithme efficace pour les contraintes telles que $q$, c’est-à-dire les égalités pseudo-Booléennes, on peut appliquer à ces contraintes des filtrages moins puissants qui restaurent la cohérence de domaines sur leur décomposition en deux inégalités pseudo-Booléennes.

Dans certains cas, contrairement à ce qui s’est produit dans notre exemple, ce filtrage affaibli réduit certains domaines et c’est mieux que rien.

Filtrage partiel

La restauration de cohérence de domaines s’applique itérativement à toutes les contraintes d’un réseau jusqu’à ce que toutes les valeurs de chaque domaine aient au moins un support pour toutes les contraintes. On peut réduire le coût du filtrage – et son efficacité – en ne filtrant que les contraintes directement reliées à la variable de branchement. L’algorithme obtenu est appelé forward checking (FC).

MAC est en général plus rapide que FC, mais on ne peut en faire un dogme. Dans certains cas particuliers où le filtrage complet serait couteux et peu rentable, on peut envisager d’utiliser FC, en prolongeant toutefois le filtrage lorsque certains domaines deviennent des singletons.

Dans le cadre de cet enseignement, on travaillera uniquement avec MAC.

Au delà de la cohérence de domaines

La restauration de la cohérence de domaines déduit tout ce qu’il est possible de déduire à partir d’une seule contrainte et lorsque la conclusion de la déduction est une restriction des domaines. Mais on peut imaginer d’autres formes de déductions faisant intervenir plusieurs contraintes. Lorsque le résultat d’une telle déduction est une nouvelle contrainte, on parlera d’apprentissage, mais si le résultat est une restriction de domaines on peut encore parler de filtrage.

L’exemple typique est la notion de k-cohérence, souvent appelée k-consistance dans la littérature par francisation du terme anglais consistency qui se dit en français cohérence. Un réseau de contraintes et k-cohérent si toute assignation partielle de k-1 variables peut être étendue à une assignation partielle de k variables sans falsifier de contrainte.

Cette notion ne sera pas développée ici, mais rien n’empêche de remplacer dans un solveur de type MAC la restauration de la cohérence de domaines par la restauration de la k-cohérence. Le risque est que le coût d’un tel filtrage soit plus élevé que son bénéfice, mais rien ne permet d’affirmer qu’il ne soit pas rentable pour certains types de contraintes ou de réseaux.

Branchements binaires

Dans l’algorithme MAC décrit au début de ce document, chaque nœud de l’arbre de recherche est associé à une certaine variable de branchement, appelons-là $V$, et chaque branche partant de ce nœud correspond à une valeur du domaine de $V$. On peut donc avoir des nœuds à deux, trois, quatre branches et plus. On peut interpréter ces branchements comme des hypothèses. En branchant sur $V = x$, où $x$ est dans le domaine de $V$, on fait l’hypothèse qu’il existe au moins une solution pour laquelle $V = x$. Si cette hypothèse est vraie, on trouvera de telles solutions dans le sous-arbre induit par le branchement. Si elle est fausse, on aura acquis une connaissance, à savoir qu’avec les domaines considérés avant le branchement, il n’existe aucun moyen de satisfaire le réseau si $V = x$. Cette connaissance est enregistrée implicitement par le solveur grâce au mécanisme qu’il utilise pour éviter de faire à nouveau le branchement $V = x$ à partir du même nœud de son arbre de recherche. On parle parfois de phase de la variable de branchement.

image7

Il existe une variante de MAC dans laquelle on réalise exactement deux branchements à chaque nœud. Dans cette variante, pour une variable de branchement $V$, on va avoir un branchement correspondant à l’hypothèse $V = x$ et un autre correspondant à l’hypothèse $V \neq x$.

image8

Tout arbre de MAC classique peut être aisément simulé par un MAC à branchements binaires. Par exemple dans le cas d’une variable de branchement $V$ de domaine ${ 1,2,3}$, le deuxième branchement correspondant à $V \neq 1$ pourra être prolongé par un branchement basé sur la même variable $V$ avec les hypothèses $V = 2$ et $V \neq 2$, mais comme à ce stade il n’y aura plus que 2 et 3 dans le domaine de $V$, cela reviendra au même que brancher sur $V = 2$ et $V = 3$.

image9

La réciproque n’est pas vraie. MAC à branchements binaires peut produire des arbres de recherche impossibles à obtenir avec MAC classique.

MAC à branchements binaires peut être plus efficace que MAC classique sur certains problèmes, à condition de bien choisir les variables et valeurs de branchements. Or ce choix est loin d’être évident, comme nous le verrons plus loin.

D-dec-32

Soit le réseau de contraintes suivant :

  • Variables : $A, B, C$ ayant toutes pour domaine ${1,2,3}$.

  • Contraintes : $\text{allDiff}(A,B,C)$, $A+B=4$.

Donnez l’arbre de recherche MAC à branchement binaire en utilisant $A$ comme première variable de branchement.

"Solution"

image-20210927104846784

Apprentissage (approfondissement hors programme)

Dans MAC classique et MAC à branchements binaires, il y a une forme d’apprentissage dans le sens où le solveur accumule des connaissances sur des assignations partielles qui ne peuvent être étendues à des solutions. Prenons comme exemple l’arbre de recherche suivant (peu importe les contraintes).

image10

Cet arbre est parfaitement plausible. Rien n’oblige à choisir les variables de branchement dans le même ordre sur chaque branche. D’autre part, en raison des filtrages réalisés à chaque nœud, une même variable de branchement peut avoir un domaine différent selon le nœud où elle est utilisée. Les croix représentent des échecs, ou incohérences, c’est-à-dire des situations où après branchement et filtrage, un domaine devient vide.

Intéressons-nous au moment où la recherche vient de produire le quatrième échec. A ce moment précis, le solveur à accumulé les connaissances suivantes :

  • Il n’y a pas de solution avec $A = 1$.

  • Il n’y a pas de solution avec $A = 2$ et $C = 1$.

image11

C’est ce que l’auteur de ce cours appelle de l’apprentissage implicite. C’est le mécanisme de retour arrière qui permet au solveur de conserver ces connaissances. Par exemple, après le stade matérialisé sur la figure ci-dessus, le solveur n’essaiera plus de trouver des solutions avec $A = 1$, ni avec $A = 2$ et $C = 1$.

Mais certains mécanismes d’apprentissage explicite peuvent être ajouté au solveur. Il peut s’agir de systèmes déductifs activés au moment des échecs. Par exemple, imaginons que le deuxième échec ne dépende pas de la valeur de la variable $A$. On dira que ${B = 5,\ C = 1}$ est un nogood. Trouver ce genre de nogood requiert des algorithmes spécifiques qui sortent du périmètre de ce cours.

Si notre algorithme MAC était équipé d’un mécanisme permettant de détecter le nogood ${B = 5,\ C = 1}$, alors on pourrait ajouter cette information dans une base de connaissances ou l’ajouter au réseau comme une nouvelle contrainte. Ainsi, si par exemple l’assignation $B = 5$ se reproduit plus tard, la valeur $1$ sera retirée du domaine de $C$, ce qui évitera des branchements qui auraient été nécessaires sans cet apprentissage.

image12

En pratique, les solveurs avec apprentissage sont très complexes et font généralement des redémarrages et des retours arrière non chronologiques, c’est-à-dire qu’après certains échecs et apprentissages associés, ils remontent plus haut que la dernière variable de branchement même si toutes les valeurs du domaine de cette variable n’ont pas été essayées.

Les nogoods ou autres connaissances qu’ils apprennent occupent un espace mémoire important, ce qui impose de retirer régulièrement certaines connaissances apprises. Malgré cette grande complexité, ces solveurs peuvent être beaucoup plus efficaces que les solveurs sans apprentissage (ou à apprentissage implicite). Par exemple pour problème SAT, dans lequel les contraintes sont des clauses en logique propositionnelle, les solveurs de type CDCL (pour Conflict Driven Clause Learning) qui apprennent (comme leur nom l’indique) de nouvelles clauses, pulvérisent les performances des solveurs énumératifs de type MAC (qui dans le contexte de SAT sont appelés DPLL d’après les initiales des noms des inventeurs).

D4 : Heuristiques de branchement

Le choix des variables de branchement (et des valeurs dans le cas de la version à branchement binaire) est critique pour l’efficacité des solveurs de type MAC. Sur des réseaux de quelques dizaines de variables, on peut facilement observer des rapports de temps d’exécution de l’ordre du milliard, ou beaucoup plus, selon la manière dont les variables de branchement sont choisies.

Pour comprendre l’importance de choisir les « bonnes » variable de branchement, considérons cet exemple.

image13

La cohérence de domaine est vérifiée pour toutes les contraintes. (Rappelez-vous que cette forme de cohérence ne considère qu’une seule contrainte à la fois !).

Si MAC commence par brancher avec une des variables A, B ou C, il déduira rapidement que le réseau est incohérent. Mais s’il commence par la variable D, il revérifiera trois fois l’incohérence du sous-réseau A, B, C.

Trouver la meilleure variable de branchement est (dans le cas général) plus difficile que résoudre le réseau, mais il existe des heuristiques de choix de la variable de branchement qui sont plus ou moins efficaces selon la nature des contraintes et la structure du réseau.

On appelle heuristique un critère de choix facile à calculer (qui prend un temps faible au regard des autres traitement réalisé par le solveur) mais qui ne donne aucune garantie d’optimalité.

Ces heuristiques peuvent prendre en compte, par exemple :

  • la taille du domaine de chaque variable,

  • le nombre de contraintes dans lesquelles chaque variable intervient,

  • le nombre d’assignations partielles autorisées par chaque contraintes,

  • des poids attribués à chaque variable, qui évoluent au cours de la recherche en fonction de l’efficacité des filtrages réalisés sur leurs domaines (on parle alors d’heuristiques dynamiques)…

C’est un très vaste sujet que nous n’approfondirons pas ici. Même lorsque le réseau de contraintes est cohérent, c’est le choix des variables de branchement qui est particulièrement critique pour trouver une solution. Bien évidemment, si on pouvait « deviner » les assignations des variables d’une solution, on la trouverait immédiatement quelles que soient les variables de branchement. Mais en pratique il s’avère souvent que « deviner » les solutions à l’aide d’une heuristique ne fonctionne pas, alors que les heuristiques efficaces pour prouver l’incohérence du réseau de contraintes sont celles qui sont également les plus efficaces pour trouver des solutions lorsque le réseau de contraintes est cohérent.


Exercices d’assimilation

D-ass-01

Complétez cet arbre de recherche de l’algorithme MAC sur le problème des 5 reines. Chaque pastille ronde rose représente l’assignation d’une variable de branchement. Les croix grises représentent les valeurs des domaines des variables qui ont été filtrées (ou éliminées du fait de l’assignation de la variable). Les pastilles carrées roses représentent les valeurs assignées par filtrage (quand il ne reste qu’une valeur dans le domaine concerné). On considère qu’il y a 10 contraintes reliant respectivement A et B, A et C, A et D, A et E, B et C, B et D, B et E, C et D, C et E, D et E. Chacune de ces contraintes exprime que les reines situées sur les colonnes associées aux variables concernées ne sont ni sur une même ligne, ni sur une même diagonale.

image14

"Indice1"

Tout d’abord, il faut que vous soyez convaincu du résultat du filtrage pour $A = 1$. Les croix apparaissant sur la figure de gauche sont assez évidentes, puis qu’elles correspondent à des valeurs des variables B, C, D, E qui représentent des reines positionnées sur une même ligne ou une même diagonale que la reine représentée par A=1. Par exemple, il y a une croix pour C=3 parce-que C=3 n’a pas de support pour la contrainte entre A et C, parce que si on avait A=1 et C=3, cela reviendrait à mettre les reines des colonnes A et C sur une même diagonale.

image16

Mais pourquoi faut-il aussi mettre des croix pour C=4 et D=3 ? N’oubliez pas que vous devez continuer le filtrage tant qu’il reste dans certains domaines des valeurs n’ayant pas de support pour certaines contraintes.

Or C=4 n’a pas de support pour la contrainte entre B et C ! En effet, le domaine de B est {3,4,5} (les valeurs non barrées dans la colonne B. Si on assignait C=4, on ne pourrait pas assigner B=3 (conflit diagonale), ni B=4 (conflit ligne), ni B=5 (conflit diagonale). Donc aucune des valeurs du domaine de B n’est compatible avec C=4 au regard de la contrainte entre B et C. On doit donc retirer C=4.

Un raisonnement similaire pour la contrainte entre D et E permet de supprimer D=3, d’où les deux croix en C=4 et D=3. Quels sont les filtrages supplémentaires à ajouter si on assigne C=5 ? Trouvez les vous-même avant de consulter la réponse au prochain indice.

"Indice2"

Sur cette figure, le filtrage pour la branche A=1, C=5 a été terminé et a donné lieu à une solution. Le filtrage pour A=2 a été réalisé. Merci de continuer avec la variable de branchement C.

image20

"Indice3"

Les branchements C=1 et C=3 après A=2 produisent chacun une solution par filtrage. A vous de tenter de terminer l’arbre de recherche avant de consulter le dernier indice.

image25

"Solution"

Voici le développement complet des branches A=1, A=2, A=3.

image32

Comme les branches A=4 et A=5 sont symétriques avec les branches A=2 et A=1 (bien que peu de solveurs soient capables de le prendre en compte), on en déduit que le problème des 5 reines a 10 solutions.

D-ass-02

Soit le problème suivant :

Variables :

image15

Contraintes :

Pour chaque ligne et chaque colonne, une contrainte exprime que la somme des variables concernées vaut 2. $A + B + C = 2$, $D + E + F = 2$, $G + H + I = 2$, $A + D + G = 2$,$B + E + H = 2$, $C + F + I = 2$.

Réalisez une simulation de l’exécution d’un solveur MAC sur cette instance de problème. Dessinez l’arbre de recherche complet (recherchant toutes les solutions), en précisant à chaque nœud les domaines des différentes variables. Pour faciliter la lecture, merci de représenter ces domaines sous la forme d’une grille de 3 par 3 avec la convention suivante : une case blanche représente le domaine {0,1} , une case contenant la valeur 0 représente le domaine {0} , et une case contenant la valeur 1 représente le domaine {1}.

"Indice1"

Voici le premier niveau de l’arbre de recherche en choisissant E comme variable de branchement. Ce n’est pas obligatoire, mais les indices suivants seront basés sur ce choix.

image17

On voit que le côté gauche filtre un peu, alors que le côté droit ne filtre pas, mais cela aurait été la même chose avec tout autre choix de la variable de branchement.

"Indice2"

La branche gauche aboutit à deux solutions en branchant sur A, par exemple. Le prochain indice sera basé sur un branchement sur D à droite.

image21

"Indice3"

Voici le développement de tout le deuxième niveau. Pour la suite, E est la variable de branchement préconisée.

image26

"Solution"

Voici l’arbre de résolution complet, qui fait apparaitre les 6 solutions du réseau. Étant donné qu’il y a 6 solutions, quelles que soit les choix des variables de branchement, l’arbre de recherche aura au moins 6 branches, donc 5 nœuds binaires. Il n’existe donc pas de stratégie de branchement produisant un arbre plus petit.

image33

D-ass-03

Soit le réseau de contraintes suivant :

  • Variables : A avec domaine {0,5}, B avec domaine {0,6}, C avec domaine {0,9}, D avec domaine {0,2}.

  • Contraintes : A + B + C + D >= 15 et A + B + C + D <= 15.

Détaillez la résolution de ce problème par l’algorithme MAC (Maintaining Arc Consistency). Choisissez les variables de branchement de manière à minimiser la taille de l’arbre de recherche.

"Indice1"

La première chose à faire est de rétablir la cohérence de domaine, si applicable. Or il y a bien une valeur à enlever. C=0 n’a pas de support pour la contrainte A + B + C + D >= 15. C’est le seul filtrage possible, donc pour continuer il faut choisir une variable de branchement. Pourquoi pas B ?

image18

"Indice2"

Avec B=0, A=0 et D=0 ne peuvent satisfaire la contrainte A + B + C + D = 15. Les valeurs 0 sont donc retirées des domaines de A et D. Mais alors, aucune des valeurs restant dans les domaines ne permet de satisfaire la contrainte A + B + C + D <= 15.

image22

Pour la forme, on matérialise l’incohérence en retirant 5 du domaine de A, mais on aurait pu vider tout autre domaine, puisque les valeurs restantes, par définition, n’ont pas de support pour A + B + C + D <= 15.

Il reste un espoir de trouver une solution avec la branche B=6…

"Solution"

Voici l’arbre de recherche complet. Le filtrage des domaines de A et D au regard de la contrainte A + B + C + D >= 15 permet de retirer les valeurs non nulles et de produire une solution.

image27

D-ass-04

Soit le réseau constitué des 6 contraintes logiques suivantes, appelées clauses.

$$(a \vee b), (\neg a \vee b), (a \vee \neg b), (\neg a \vee \neg b \vee c), (\neg c \vee d), (\neg c \vee \neg d)$$

Les variables ont toutes pour domaine {0,1}.

Détaillez la résolution de ce problème par l’algorithme MAC. A chaque nœud ou feuille, redonnez les domaines en barrant les valeurs éliminées par filtrage ou par assignation de la variable de branchement. A chaque feuille, précisez s’il y a échec ou solution. Essayez de choisir les variables de branchement de manière à minimiser la taille de l’arbre de recherche.

"Indice1"

Tout d’abord il faut restaurer la cohérence de domaine. Mais il n’y a aucun filtrage possible avec les domaines initiaux. Chaque clause fait intervenir plusieurs variables et quelle que soit la valeur d’une de ces variables, il existe toujours au moins une valeur pour l’autre qui permet de satisfaire la clause.

Pour la suite, merci d’utiliser la variable $a$ comme variable debranchement.

image19

"Indice2"

Avec $a = 0$, $b = 0$ n’a pas de support pour la clause $(a \vee b)$ et $b = 1$ n’a pas de support pour la clause $(\neg a \vee b)$.

image23

Avec les clauses, on peut raisonner directement sur les contraintes en barrant les littéraux qui sont falsifiés par les assignations déjà réalisées.

image24

Quand il reste un seul littéral dans une clause, cela impose une assignation de la variable concernée. Dans le contexte du problème SAT, c’est-à-dire quand toutes les contraintes sont des clauses, cette technique est appelée propagation unitaire.

"Solution"

Voici l’arbre de résolution complet.

image28

Puisque $a = 1$, $b = 0$ n’a pas de support pour la clause $(\neg a \vee b)$ qui ne peut être satisfaite que si $b = 1$. Cette première étape peut aussi être formalisée comme ci-dessous en termes de propagation unitaire.

image29

Ensuite, puisque le domaine de $b$ est ${ 1}$, ce qui revient à dire que $b = 1$, et que par ailleurs $a = 1$, $c = 0$ n’a pas de support pour la clause $(\neg a \vee \neg b \vee c)$ qui ne peut être satisfaite que si $c = 1$.

image30

Mais avec $c = 1$, $d = 0$ n’a plus de support pour la clause $(\neg c \vee d)$ et $d = 1$ n’a plus de support pour la clause $(\neg c \vee \neg d)$. Le domaine de $d$ se retrouve vide et la branche aboutit à un échec. Le réseau initial est donc incohérent.

image31


PPC : test d’autoévaluation partie A

Programmation par contraintes

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Test d’auto-évaluation sur la partie A

Objectif

Vérifier si vous avez assimilé de manière approfondie les notions de la partie A

Prérequis

Partie A


Question 1

Pour chacune de ces deux contraintes, dites si elle est donnée en extension et/ou en compréhension et/ou sous forme énumérative. On suppose que les variable ont toutes pour domaines ${1,2,3}$.

  1. $A > C+1$
  2. sur $A,B,C$, ${(1,1,1),(1,2,1),(2,1,2)}$
"Réponse"

La première contrainte est en compréhension. La deuxième est en extension. Elle est donnée sous forme énumérative. (Les deux termes sont équivalents.)

Question 2

Le réseau de contraintes suivant a-t-il des solutions ? Si oui, donnez les.

![](img

"Réponse"

Ce réseau n’a pas de solution. Il est incohérent.

Question 3

Le réseau de contraintes suivant a-t-il des solutions ? Si oui, donnez les.

"Réponse"

  1. $A=\alpha, B=\beta, C=\alpha, D=\beta$
  2. $A=\beta, B=\alpha, C=\beta, D=\alpha$

Question 4

On dit que deux contraintes sont équivalentes si et seulement si elles relient les mêmes variables, de même domaines, et sont satisfaites par les même assignations de ces variables.

Soit $A$ et $B$ deux variables à domaine ${0,1}$. Les contraintes $A=\neg B$ et $A\vee B$ sont elles équivalentes ?

"Réponse"

Non, car l’assignation $A=1,B=1$ falsifie la première contrainte et satisfait la deuxième.

Question 5

Soit $A$ et $B$ deux variables à domaine ${0,1}$. Les contraintes $A=\neg B$ et $(A\vee B)\wedge(\neg A\vee \neg B)$ sont elles équivalentes ?

"Réponse"

Oui.

Question 6

Soit la contrainte $10 A + 5 B + C \leq 11$, où $A$, $B$ et $C$ ont pour domaine ${0, 1}$.

Donnez une assignation partielle $I$ qui falsifie cette contrainte et une assignation partielle $J$ qui la satisfait.

"Réponse"

$I$ : $A=1, B=1$.

$J$ : $A=0$ ou $B=0$ ou toute extension de ces assignations.

Question 7

Soient $A$ et $B$ deux variables ayant pour domaine ${0,1}$. Donnez une contrainte équivalente à $A = \neg B$ spécifiée en compréhension en utilisant uniquement des opérateurs arithmétiques +, -, = et des constantes entières (0, 1, …).

"Réponse"

$A = 1 – B$ ou $B= 1 – A$ ou $A+B = 1$.

Question 8

Soient les variables $A$ et $B$ de domaine ${0,1}$ et les variables $X$ et $Y$ de domaine ${0,2}$.

On considère :

  • la contrainte $q : A\vee B$,
  • et le réseau $r : A\neq X, B\neq Y, X\neq Y$.

Soit $I$ une assignation des variable $A,B$, qui est aussi une assignation partielle des variables de $r$. Parmi les affirmations suivantes, lesquelles sont vraies ?

  1. Si $I$ satisfait $q$ alors il existe une extension de $I$ qui satisfait $r$.
  2. Si il existe une extension de $I$ qui satisfait $r$ alors $I$ satisfait $q$.
  3. Si $I$ falsifie $q$ alors $I$ (vu comme une assignation partielle des variables de $r$) falsifie $r$.
  4. Si $I$ satisfait $q$ alors $I$ (vu comme une assignation partielle des variables de $r$) satisfait $r$.
"Réponse"

  1. Oui. On peut vérifier que pour chacune des assignations qui satisfont $q$, c’est à dire ${A=0,B=1}$, ${A=1,B=0}$, et ${A=1, B=1}$, il existe une valeur de $X$ et une valeur de $Y$ qui permettent de satisfaire $r$.
  2. Oui. Il existe une extension de $I$ qui satisfait $r$ si $I={A=0,B=1}$ ou si $I={A=1,B=0}$ ou si $I={A=1, B=1}$. (et pas si $I={A=0, B=0}$). Ces trois assignations satisfont $q$.
  3. Oui. La seule assignation $I$ qui falsifie $q$ est ${A=0, B=0}$. Cette assignation falsifie $r$.
  4. Non. Par exemple, $A=1,B=1$ satisfait $q$ mais son extension $A=1,B=1,X=2,Y=2$ falsifie $r$.

Programmation par contraintes : partie I

Programmation par contraintes

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Implémentation avec CHOCO v4

Objectif

Être capable de concevoir une application Java permettant de résoudre un problème de satisfaction de contraintes en utilisant la bibliothèque CHOCO version 4.

Prérequis

Partie B et bases de programmation en JAVA.

Introduction

Entendons-nous bien. La programmation par contraintes est une programmation déclarative : on spécifie un problème à l’aide de contraintes, et un solveur résout ce problème. L’intérêt est précisément de ne pas avoir à programmer un solveur. Java n’est pas un langage déclaratif mais impératif, qui exige de détailler toutes les étapes et opérations nécessaires à l’exécution d’un programme.

Alors pourquoi et comment utiliser un langage impératif pour faire de la programmation déclarative ?

Il faut comprendre que les applications réalisées avec la bibliothèque CHOCO s’exécutent en deux temps. Dans un premier temps, un programme Java produits des objets de types variables et contraintes, qui sont placés dans un objet appelé modèle, qui représente un réseau de contraintes.

Une application utilisant CHOCO exécute un algorithme qui « fabrique » une spécification déclarative d’un problème de satisfaction de contraintes. Dans un deuxième temps, un objet solveur prend en charge le modèle préalablement construit pour résoudre le réseau de contraintes. Donc le code Java ne sert pas à résoudre le problème, mais à construire des réseaux de contraintes représentant des instances du problème à résoudre. La résolution en elle-même est assurée par le solveur fourni par CHOCO.

image1

Avant d’aller plus loin, vous devez récupérer la bibliothèque CHOCO qui est disponible sous la forme d’une archive au format jar en suivant les instructions du site choco-solver.org. On vous envoie vers un dépôt github où, en cherchant bien, vous pourrez trouver un lien vers la "latest release". Au moment où j’écris ces lignes, il s’agit de la version 4.10.6. Vous arrivez enfin à une page proposant plusieurs archives. Celle qui nous intéresse est nommée choco-solver-4.10.6-jar-with-dependencies.jar au moment où j’écris ce ligne. Il se peut qu’il s’agisse d’une version ultérieur lorsque vous vous rendrez sur le site, mais l’important est que la bonne archive a l’extension jar et comporte les termes choco-solver et with-dependencies dans son nom.

Vous devez ensuite faire en sorte d’utiliser cette bibliothèque dans le code Java que vous allez écrire et compiler. Les IDE proposent tous un moyen spécifique de faire cela. Il faut parfois tâtonner un peu.

Exemple introductif

Avant de coder une application CHOCO, il faut modéliser le problème à résoudre sous la forme d’un réseau de contraintes comme nous avons appris à le faire dans la préparation du badge B.

Nous parlons ici du problème suivant : peut-on placer n reines sur un échiquier n par n de manière à qu’il y ait exactement une reine sur chaque ligne et chaque colonne et au plus une reine sur chaque diagonale ?

Pour modéliser ce problème, nous utilisons $n$ variables $v_{0},\ldots,\ v_{n – 1}$ à domaines ${ 1..n}$. Chaque variable est associée à une colonne de l’échiquier. Une assignation $v_{i} = j$ signifie que la reine située dans la colonne $i$ se trouve en ligne $j$.

La figure ci-dessous représente une solution pour $n = 5$ et l’assignation des variables $v_{0}$ à $v_{4}$ qui représente cette solution.

image3

Pour chaque couple $(i,j),\ i \in 0..(n – 2),\ j \in (i + 1)..(n – 1)$, on pose les trois contraintes suivantes :

  1. $v_{i} \neq v_{j}$, qui interdit que les reines des colonnes $i$ et $j$ soient une même ligne.

  2. $v_{i} \neq v_{j} – (j – i)$, qui interdit que les reines des colonnes $i$ et $j$ soient sur une même diagonale descendante.

  3. $v_{i} \neq v_{j} + (j – i)$, qui interdit que les reines des colonnes $i$ et $j$ soient sur une même diagonale montante.

Par exemple, on aura trois contraintes reliant les variables $v_{0}$ et $v_{2}$, à savoir $v_{0} \neq v_{2}$, $v_{0} \neq v_{2} – 2$ et $v_{0} \neq v_{2} + 2$. Si par exemple $v_{0} = 3$, ces trois contraintes interdiront les valeurs 2, 4 et 6 pour $v_{2}$.

image4

Au total, pour $n$ reines, on aura $3n(n – 1)/2$ contraintes.


Il nous faut maintenant traduire ce modèle en un ensemble d’objets créés avec la bibliothèque CHOCO. Voici les différentes étapes.

Création du modèle

Ces deux lignes permettent de créer un modèle (instance de la classe Model) à laquelle seront ensuite ajoutées les contraintes et les variables. La chaîne passée en paramètre est purement « cosmétique ».

    int n = 8;
    Model model = new Model(n + "-queens problem");

Création des variables

Ces lignes permettent de créer les variables du réseau de contraintes. Attention. Nous parlons bien ici des variables du réseau de contraintes, dont les domaines contiennent des entiers. Ces variables ne sont pas des variables de type int de Java. Ce sont des instances de la classe IntVar de CHOCO qui représentent les variables du réseau de contraintes sur lequel le solveur CHOCO va raisonner.

    IntVar[] vars = new IntVar[n];
    for(int q = 0; q < n; q++)
    {
        vars[q] = model.intVar("Q_"+q, 1, n);
    }

La première ligne crée un tableau qui regroupera toutes les variables du problème. Attention, cette liste produit juste un tableau dont les cellules contiennent la pseudo-référence null.

image7

En Java, les cellules d’un tableau, tout comme les variables ayant un type non scalaire T ne contiennent jamais une instance de type T, mais contiennent soit la valeur null, soit la référence d’un objet de type T.

En résumé, une variable ou une cellule de tableau ne peut pas contenir un objet, mais seulement sa référence. Donc dans notre cas, la création du tableau ne crée pas les variables de notre réseau mais juste les cellules destinées à contenir les références de ces variables.

C’est la boucle for qui va créer les variables de notre réseau de contraintes, qui est appelé modèle dans la documentation CHOCO, et placer les références de ces variables, représentées par des objets de type IntVar, dans le tableau vars.

La création de chaque variable est assurée par la méthode intvar de la classe Model de CHOCO.

L’appel model.intVar(\"Q\_\"+q, 1, n) retourne la référence un objet de type IntVar qui représente une variable (au sens de la programmation par contrainte) nommée Q_q (où q désigne la colonne associée à la variable) et de domaine 1..n (où n est le nombre de reines). Le nom de la variable est un attribut purement cosmétique qui pourra servir pour des affichages et lors de la mise au point du programme.

Création des contraintes

Les contraintes de notre modèle sont des objets de type Constraint. Ces objets sont produits par la méthode arithm de la classe Model. Différentes variantes surchargées de cette méthode permettent de construire aisément des contraintes arithmétiques à partir de variables, d’opérateurs et de constantes comme le montrent les lignes de code suivantes qui créent les contraintes pour le problème de n reines et les intègrent dans le modèle.

    for(int i  = 0; i < n-1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            model.arithm(vars[i], "!=",vars[j]).post();
            model.arithm(vars[i], "!=", vars[j], "-", j - i).post();
            model.arithm(vars[i], "!=", vars[j], "+", j - i).post();
        }
    }

Examinons par exemple la ligne model.arithm(vars\[i\], \"!=\", vars\[j\], \"-\", j - i).post(). Cette ligne appelle la méthode arithm qui, avec les paramètres qui lui sont transmis, crée un objet de type Constraint représentant la contrainte $v_{i} \neq v_{j} – (j – i)$. La méthode post de la classe Constraint est ensuite appelée pour intégrer cette contrainte dans le modèle dans lequel elle a été créée. Il faut bien comprendre que du point de vue de CHOCO, les valeurs des variables Java i et j sont des constantes qui vont être figées dans la contrainte au moment de sa création.

En pratique, toutes les contraintes créées dans un modèle doivent y être intégrées par la méthode post sauf les contraintes dites réifiées.

La réification d’une contrainte $q$ sur un ensemble $V$ de variables est une contrainte $q^{r}$ sur $V \cup { r}$, où $r$ est une variable additionnelle appelée variable de réification à domaine Booléen {0,1}, telle que pour toute assignation $A$ sur $V$, $A \cup { r = 1}$ satisfait $q^{r}$ si et seulement si $A$ satisfait $q$ et $A \cup { r = 0}$ satisfait $q^{r}$ si et seulement si $A$ falsifie $q$. En résumé, la réification $q^{r}$ d’une contrainte $q$ peut toujours être satisfaite mais avec une valeur de sa variable de réification qui indique si $q$ est satisfaite par les valeurs des autres variables.

Si cela vous parait confus, pour l’instant retenez juste que pour ajouter des contraintes ordinaires, telle que celles que nous avons vu dans la préparation des parties A et B, il faut toujours intégrer les contraintes avec la méthode post et que si vous oubliez de le faire, le solveur ne prendra pas en compte les contraintes concernées.

Dans notre exemple, les boucles for imbriquées ne servent donc en aucun cas à résoudre le problème des n reines. Elles servent à fabriquer les contraintes qui spécifient ce problème et à intégrer ces contraintes dans le modèle qui servira ensuite au solveur pour résoudre le problème.

Résolution

Pour résoudre notre problème, il suffit de créer un objet de type Solveur et d’exécuter une méthode de cet objet permettant de lancer la résolution du réseau de contraintes spécifiée par le modèle précédemment construit. C’est ce que font les lignes de code ci-dessous.

    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }

La méthode getSolver crée un objet de type Solver dédié au modèle représenté par l’objet model. La méthode findSolution appelée avec cet objet recherche une solution de ce modèle. Si le réseau de contraintes représenté par le modèle est incohérent, findSolution retourne null, sinon elle retourne un objet de type Solution qui contient les détails de la solution trouvée. La méthode toString de l’objet solution permet d’afficher les valeurs assignées aux variables par cette solution.

Il existe d’autres méthodes applicables aux objets de type Solver pour rechercher toutes les solutions du problème.

Voici le code complet de cet exemple introductif avec les imports des packages de CHOCO requis pour son fonctionnement.

public static void main(String[] args)
{
    int n = 8;
    Model model = new Model(n + "-queens problem");
    IntVar[] vars = new IntVar[n];
    for(int q = 0; q < n; q++)
    {
        vars[q] = model.intVar("Q_"+q, 1, n);
    }
    for(int i  = 0; i < n-1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            model.arithm(vars[i], "!=",vars[j]).post();
            model.arithm(vars[i], "!=", vars[j], "-", j - i).post();
            model.arithm(vars[i], "!=", vars[j], "+", j - i).post();
        }
    }
    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }
}

L’auteur a compilé ce code dans l’IDE IntelliJIDEA et l’exécution a produit l’affichage suivant :

Solution: Q_0=7, Q_1=4, Q_2=2, Q_3=5, Q_4=8, Q_5=1, Q_6=3, Q_7=6

Voici une représentation graphique de la solution trouvée par le solveur.

image10

Exercices d’assimilation

A-ass-00

Le problème des reines en booléens. On modélise le problème des $N$ reines en utilisant uniquement des variables Booléennes. Le réseau de contraintes comporte $N^{2}$ variables, chacune associée à une case de l’échiquier. Voici par exemple les variables pour $N = 5$.

image11

Une contrainte est associée à chaque ligne, chaque colonne et chaque diagonale de l’échiquier. Les contraintes relient toutes les variables d’une même ligne ou d’une même colonne expriment qu’une seule des variables concernées vaut 1. Les contraintes qui relient toutes les variables d’une même diagonale expriment qu’au plus une des variables concernées vaut 1.

Voici deux exemples de contraintes pour $N = 5$.

image12

image13

Réalisez une application CHOCO qui résout ce problème.

"Indice1"

La première chose à faire est de créer un modèle et de lui ajouter les variables du problème. Voici les lignes de code qui permettent de faire cela.

    int N = 8;

    //Création du modèle
    Model model = new Model(N + "-queens problem");

    // Création des variables
    IntVar[][] x = new IntVar[N][N];
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            x[i][j] = model.intVar("X_"+i+"_"+j, 0, 1);
        }
    }

Voici les données créées en mémoire (dans le tas) par l’exécution de ces lignes de code.

image14

"Indice2"

A présent il nous faut construire les contraintes. Commençons par les plus faciles, qui concernent les lignes de l’échiquier. En cherchant un peu dans la documentation CHOCO, on trouve une contrainte somme qui exprime que la somme de toutes les variables situées dans un tableau est égale à une valeur donnée (des variantes de cette contrainte permettent d’exprimer une inégalité $\leq ,\ \geq ,\ > ,\ <$ avec une constante ou une variable du réseau).

Pour construire une contrainte somme, les références des variables à prendre en compte doivent être dans un tableau. Ça tombe bien, les variables de chaque ligne de l’échiquier sont déjà dans des tableaux. Vous pouvez le vérifier en observant la figure donnée dans l’indice précédent. En java, chaque cellule d’un tableau à 2 dimensions contient la référence d’un tableau à une dimension.

Le code suivant permet de produire toutes les contraintes relatives aux lignes de l’échiquier.

    for(int i=0; i<N; i++)
    {
        model.sum(x[i], "=", 1).post();
    }

Dans la lignemodel.sum(x[i], "=" 1).post(), x[i] désigne un tableau de taille N dont les cellules contiennent les références des objets de type IntVar qui représentent les variables d’une ligne de l’échiquier.

"Indice3"

Après les lignes, il nous faut produire les contraintes relatives aux colonnes. Mais cette fois-ci, nous ne disposons pas de tableau tout fait contenant les références des variables d’une même colonne. Il faut donc, pour chaque colonne, créer un tel tableau et le remplir avant de l’utiliser pour créer une contrainte de type somme similaire à celles utilisées pour les lignes.

Voici les lignes de codes permettant de faire cela.

    for(int j=0; j<N; j++)
    {
        IntVar[] col = new IntVar[N];
        for(int i=0; i<N; i++)
        {
            col[i] = x[i][j];
        }
        model.sum(col, "=", 1).post();
    }

"Indice4"

Nous devons maintenant produire une contrainte pour chacune des $2N – 1$ diagonales montantes et des $2N – 1$ diagonales descendantes de l’échiquier. Il existe plusieurs moyens de collecter les variables de ces diagonales. Voici celui que je propose pour les diagonales montantes. Comme le montre la figure ci-dessous, on peut numéroter les diagonales montantes de 0 à $2N – 2$. Les cellules appartenant à la diagonale $i$ ont pour particularité que la somme de leurs indices vaut $i$. Par exemple, la cellule d’indice $(3,1)$ est sur la diagonale 4.

image15

On peut créer les listes des variables des différentes diagonale en parcourant une seule fois toutes les cellules du tableau représentant l’échiquier. Pour ce faire, on crée un tableau dUp de $2n – 1$ listes initialement vides. On parcourt l’échiquier en faisant varier les indices $i$ et $j$ entre $0$ et $N – 1$ et pour chaque $(i,j)$ on ajoute la variable $x_{\text{ij}}$ à la liste dUp[i+j].

A l’issue du parcours, il suffit de parcourir le tableau dUp, de transformer chaque liste qu’il contient en un tableau de références d’objet de type IntVar représentant les variables d’une diagonale, et de produire une contrainte expriment que la somme de ces variables est inférieure ou égale à 1. Voici les lignes de code qui font cela.

    //Diagonales montantes
    ArrayList<IntVar>[] dUp = new ArrayList[2*N-1];

    for(int k=0; k<2*N-1; k++)
    {
        dUp[k] = new ArrayList<>();
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            dUp[i+j].add(x[i][j]);
        }
    }

    for(int k=0; k<2*N-1; k++)
    {
        IntVar[] tmp = dUp[k].toArray(new IntVar[0]);
        model.sum(tmp, "<=", 1).post();
    }

La première boucle crée les $2N – 1$ listes vides. La double boucle suivante parcoure toutes les variables et place chacune d’elles dans la liste qui représente la diagonale montante à laquelle elle appartient.

La dernière boucle récupère chaque liste de variable, la transforme en un tableau, crée une contrainte exprimant que la somme des variables de ce tableau est inférieure ou égale à 1, et enregistre cette contrainte dans le modèle.

Il ne reste plus qu’à produire les contraintes correspondant aux diagonales descendantes. Essayez de trouver vous-même le moyen de le faire en vous inspirant de la méthode qui vient d’être décrite pour les diagonales montante.

"Solution"

On peut numéroter les $2N – 1$ diagonale comme indiqué sur la figure ci-dessous. Une cellule de coordonnées $(i,j)$ appartient à la diagonale descendante numéro $i – j + N – 1$.

image16

Cette observation étant faite, il devient facile d’implémenter la production des contraintes relatives aux diagonales descendantes.

    //Diagonales descendantes
    ArrayList<IntVar>[] dDown = new ArrayList[2*N-1];

    for(int k=0; k<2*N-1; k++)
    {
        dDown[k] = new ArrayList<>();
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            dDown[i-j+N-1].add(x[i][j]);
        }
    }

    for(int k=0; k<2*N-1; k++)
    {
        IntVar[] tmp = dDown[k].toArray(new IntVar[0]);
        model.sum(tmp, "<=", 1).post();
    }

Lorsque ces contraintes sont ajoutées au modèle, le reste du code est similaire à celui de l’exemple introductif.

    //Résolution
    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }

A-ass-01

Le problème du sac à dos. Les données du problème sont les suivantes :

  • Deux entiers $W$ et $V$ représentant respectivement le poids maximum et la valeur minimum des objets à mettre dans un sac à dos.

  • Une liste $w_{0},\ldots w_{n – 1}$ des poids des objets susceptibles d’être mis dans le sac.

  • Une liste $v_{0},\ldots v_{n – 1}$ des valeurs des objets susceptibles d’être mis dans le sac.

Les variables du problème, $x_{0},\ldots,x_{n}$ ont toutes pour domaine {0,1}.

Les contraintes sont : $\sum_{i = 0}^{n – 1}{w_{i}\ x_{i}} \leq W$ et $\sum_{i = 0}^{n – 1}{\text{wv}{i}\ x{i}} \geq V$.

Réalisez une application CHOCO qui résout ce problème et testez-là avec l’instance suivante :

  • Poids des objets (en kg) : 2, 5, 7, 8, 15, 21, 23

  • Prix correspondants (en Euros) : 3, 11, 8, 10, 10, 8, 9

  • Valeur minimum des objets emportés : 40 Euros

  • Poids maximum des objets emportés : 50 Kgs

"Indice1"

Il faut définir les constantes représentant les données de l’instance de problème. On peut le faire de la manière suivante :

    int W = 50;
    int V = 40;
    int[] w = new int[]{2,5,7,8,15,21,23};
    int[] v = new int[]{3,11,8,10,10,8,9};

Dans une version plus sophistiquée de l’application, ces variables seraient initialisées par des données issues d’un fichier représentant l’instance à résoudre. A vous maintenant de définir le modèle et les variables.

"Indice2"

Le code permettant de définir et initialiser les variables est très proche de ce que nous avons déjà rencontré.

    //Création du modèle
    Model model = new Model("Backpack");

    // Création des variables
    int N = w.length;
    IntVar[] x = new IntVar[w.length];
    for(int i=0; i<N; i++)
    {
        x[i] = model.intVar("X_"+i, 0, 1);
    }

Il faut maintenant trouver le moyen de produire les contraintes. CHOCO dispose de contrainte de type $a_{0} x_{0} + \ldots + a_{n – 1} x_{n – 1} \ \text{op} \ b$ où, $a_{0}$ à $a_{n – 1}$ et $b$ sont des coefficients réels et $x_{0}$ à $x_{n – 1}$ des variables dont les domaines contiennent des entiers. Plusieurs possibilités existe pour l’opérateur op, telles que <, >, = etc.

Cette contrainte est produite par la méthode scalar de la classe Model. Consultez la documentation de CHOCO pour savoir comment utiliser cette méthode.

"Solution"

Voici le code permettant de produire les deux contraintes du problème, et dans la foulée celui permettant de lancer la résolution.

    // Création des contraintes
    model.scalar(x, w, "<=", W).post();
    model.scalar(x, v, ">=", V).post();

    //Résolution
    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }

L’implémentation est terminée et l’exécution produit immédiatement une solution du problème.

Java : test partie B

Test partie B

Classes et objets

Introduction

On souhaite réaliser une classe permettant de gérer des tableaux extensibles de valeurs Booléennes. Par tableau extensible, on entend qu’il est possible de lire ou d’écrire une valeur au-delà de la taille d’un tableau, ce que ne permettent pas les tableaux classiques.

Prenons un exemple. Je crée (dans une méthode) un tableau classique de boolean de longueur 5 comme ceci.

boolean[] tb = new boolean[5];

J’obtiens un tableau de 5 cellules, numérotées de 0 à 4, qui contiennent toutes la valeur false (c’est la valeur par défaut des cellules lorsqu’on crée un tableau de valeurs de type boolean).

Je peux facilement changer la valeur d’une cellule d’indice entre 0 et 4, mais si je tente d’écrire une valeur dans la cellule d’indice 7…

tb[7] = true;

… le programme s’arrête avec pertes et fracas en affichant un message d’erreur. Même problème si je tente de lire la valeur tb[10], par exemple.

Avec un tableau extensible, ces opérations sont autorisées. Imaginons que nous disposions d’une classe BoolExt représentant un tableau extensible de boolean. Pour créer un tel tableau, j’écris…

BoolExt te = new BoolExt();

… ce qui crée un tableau extensible de taille 1. Ce tableau n’a qu’une seule cellule et elle a la valeur false. Je ne peux pas l’utiliser avec les crochets car il ne s’agit pas d’un vrai tableau mais d’une instance de la classe BoolExt. Pour écrire ou lire des valeurs dans ce tableau extensible, je dois utiliser des méthodes spécifiques.

Je peux écrire une valeur à la position de mon choix, même au-delà de la taille actuelle du tableau, avec la méthode write. Par exemple…

te.write(4, true);

…a pour effet d’agrandir le tableau et de placer la valeur true en position 4. L’objet désigné par la variable te représente alors le tableau suivant.

Au lieu de produire une erreur, l’écriture dans la cellule d’indice 4 a provoqué l’agrandissement du tableau et les nouvelles cellules crées entre les indices 0 et 4 ont été remplie avec la valeur false.

Pour lire la valeur contenue dans une cellule, je dois utiliser la méthode read. Par exemple…

System.out.println(te.read(2));
System.out.println(te.read(4));

… produit l’affichage false true.

Mais il y a mieux encore. J’ai le droit de lire le contenu d’une cellule située au-delà de la fin du tableau. Au lieu de produire une erreur comme avec les tableaux ordinaires, cette opération retourne false, comme si le tableau avait une longueur illimitée et que toutes les valeurs situées après le dernier true étaient false. Ainsi, par exemple, la ligne…

System.out.println(te.read(7));

… produit l’affichage false.

Le fait d’écrire false à un emplacement situé après le dernier true, comme par exemple…

te.write(11, false);

…est équivalent à ne rien faire du tout puisque la position 11 est située au-delà de la position du dernier true (qui est à l’indice 4) et que toute lecture à cette position retournera false.


Récapitulons.

Tout se passe comme si un tableau extensible comportait une partie concrète, effectivement représentée en mémoire par un tableau de boolean, prolongé par une partie imaginaire infinie, non représentée en mémoire, dont toutes les cellules sont supposées contenir la valeur false.

img

On appelle taille du tableau le nombre de cellules de la partie concrète. Cette parie concrète sera effectivement représentée en mémoire par un tableau de boolean désigné par un attribut de la classe BoolExt. La partie imaginaire est le prolongement imaginaire infini de la partie concrète et toutes les cellules de cette partie imaginaire sont supposées contenir la valeur false.

Attention ! Il n’y a pas nécessairement la valeur true dans la dernière cellule de la partie concrète car pour ne pas compliquer le code, l’écriture d’une valeur false à la place du dernier true ne provoque pas le rétrécissement de la partie concrète.

Par exemple, à l’issue de l’exécution du code suivant…

BoolExt te = new BoolExt();
te.write(4, true);
te.write(3, true);
te.write(4, false);

… la partie concrète du tableau est la suivante.

Elle a une longueur égale à 5 parce qu’à un moment donné, la valeur true la plus éloignée du début était en position 4, bien qu’elle ait ensuite été remplacée par false.

Q1

Vous devez compléter la classe BoolExt en donnant les codes du constructeur et des méthodes adjust, et read. Pour comprendre le rôle de la méthode ajust, analysez le code de la méthode write.

public class BoolExt
{
   private boolean[] data;
 
   public BoolExt() 
   {
     // À compléter  
   }
 
   private void adjust(int newSize) 
   {
     // À compléter  
   }
 
   public void write(int index, boolean value) 
   {
      if((index >= data.length) && (value == true))
      {
        adjust(index+1);
      }
      data[index] = value;
   }
 
   public boolean read(int index) 
   {
     // À compléter 
   }
 
   public int size() 
   {
     return data.length;
   }
 
   public String toString()
   {
     String r = "";
     for(int i=0; i < data.length; i++)
     {
       if(data[i]) r = r + "1";
       else r = r + "0";
     }
     return r;
   }
}

La méthode ajust augmente la taille de la partie concrète, c’est-à-dire la taille du tableau désigné par l’attribut data, de manière à ce que la nouvelle taille soit égale à la valeur du paramètre newSize. En pratique, java ne permet pas de redimensionner un tableau, donc cette opération suppose de créer un nouveau tableau plus grand dans lequel le contenu de l’ancien tableau est recopié, puis de remplacer l’ancien tableau par le nouveau.

Cette méthode adjust est appelée par la méthode write lors d’une écriture d’une valeur true dans une cellule située au-delà de la limite de la partie concrète. (Dans le cas de l’écriture d’une valeur false, un agrandissement n’est pas nécessaire puisque toutes les valeurs situées dans la partie imaginaire sont considérées comme false).

Notez que la méthode toString utilise les caractères 0 et 1 à la place de false et true pour des raisons de lisibilité et concision.


Commencez par le constructeur, qui doit créer un tableau extensible de une cellule contenant false.

Merci de transmettre votre réponse au responsable de l’unité d’enseignement via Teams.


Ensuite, donnez le code de la méthode adjust qui augmente la taille du tableau désigné par l’attribut data. En pratique, on ne peut par rallonger un tableau donc la seule solution est de le remplacer par un tableau plus grand. Mais il faut recopier le contenu de l’ancien tableau dans le nouveau.

Merci de transmettre votre réponse au responsable de l’unité d’enseignement via Teams.


Maintenant, donnez le code de la méthode read, en prenant en compte le fait que l’indice de la cellule à lire peut se situer au delà de la partie concrète du tableau, et que dans ce cas la valeur à retourner est false.

Merci de transmettre votre réponse au responsable de l’unité d’enseignement via Teams.

Q2

Réalisez un constructeur en copie pour la classe BoolExt. Ce constructeur doit accepter en paramètre une instance de BoolExt et créer une nouvelle instance identique mais complètement indépendante en mémoire.

Merci de transmettre votre réponse au responsable de l’unité d’enseignement via Teams.

Q3

Dessinez la représentation en mémoire, dans la pile et le tas, des données créées par les lignes de code suivantes.

BoolExt t1 = new BoolExt() ;
t1.write(5, true);
t1.write(1, true);
BoolExt t2 = t1;
BoolExt t3 = new BoolExt(t1);

Merci de transmettre votre réponse au responsable de l’unité d’enseignement via Teams.

Java : test partie A

Partie A

Programmation procédurale en Java

Q1

public class Main
{
    public static void test()
    {
       System.out.println("Bonjour");
    }
    public static void main(String[] args)
    {
       System.out.println(test());
    }
}

Ce programme compile-t-il ? Si oui qu’est ce qui est affiché à son exécution ? Si non pourquoi ?

"Réponse"

Il ne compile pas car la méthode test ne retourne rien (void) et sa valeur de retour ne peut donc être affichée, dans main, par la méthode d’affichage printf.

Puisque l’affichage est réalisé par la méthode test, la méthode main doit juste appeler cette méthode test.

public static void main(String[] args)
{
   test();
}

Q2

public class Main
{
    public static String test()
    {
       return System.out.println("Bonjour");
    }
    public static void main(String[] args)
    {
       System.out.println(test());
    }
}

Ce programme compile-t-il ? Si oui qu’est ce qui est affiché à son exécution ? Si non pourquoi ?

"Réponse"

Il ne compile pas car la méthode println ne retourne rien (void) alors que la méthode test est censée retourner une chaine. Une version correcte de cette méthode est :

public static String test()
{
   return "Bonjour";
}

Q3

Soit la méthode suivante :

    public static int m1(int k)
    {
        int sum = 0;
        for(int i=1; i<=k; i=i+2)
        {
            sum = sum + i;
        }
        return sum;
    }

Quelle est la valeur retournée par m1(3) et par m1(5) ?

"Réponse"

4 et 9

Q4

Soit la classe suivante.

public class Main
{
    public static int[] tab = new int[5];

    public static void printTabInt(int[] t)
    {
        for(int i=0; i<t.length; i++)
        {
            System.out.print(t[i] + " ");
        }
        System.out.println();
    }

    public static void test1()
    {
        int[] t = new int[5];
        t = tab; t[2] = 12;
        printTabInt(tab);
    }

    public static void test2()
    {
        int[] t = tab;
        t[2] = 12;
        printTabInt(tab);
    }

    public static void main(String[] args)
    {
        test1(); test2();
    }
}

Ce programme compile-t-il ou comporte-t-il une erreur ?

"Réponse"

Il compile mais il comporte néanmoins une maladresse, quelque chose d’inutile. Essayez de trouver quoi avant de répondre à la questions suivante.

Les deux appels à test1 et test2 produisent-ils exactement le même affichage à l’écran ?

"Réponse"

Oui. Mais dans test1, l’initialisation de la variable de méthode t est inutile car elle crée un tableau de 5 entiers qui ne sera jamais utilisé.

    public static void test1()
    {
        int[] t = new int[5];   // ligne A
        t = tab;                // ligne B
        t[2] = 12;
        printTabInt(tab);
    }

Voici les données en mémoire juste après l’exécution de la ligne A.

image-20210920115817844

Et juste après l’exécution de la ligne B.

image-20210920115931325

Q5

Soit la classe suivante.

public class Main
{
    public static int[] tab = new int[5];

    public static void printTabInt(int[] t)
    {
        for(int i=0; i< t.length; i++)
        {
            System.out.print(t[i] + " ");
        }
        System.out.println();
    }

    public static void test1()
    {
        int[] t = new int[5];
        t[3] = 5;
        t = tab; 
        t[2] = 12;
        printTabInt(t);
        printTabInt(tab);
    }

    public static void main(String[] args)
    {
        test1();
    }
}

Donnez les affichages réalisés par l’exécution du programme.

"Réponse"

0 0 12 0 0 
0 0 12 0 0 

Q6

Soit les lignes de code suivantes :

String[] t = new String[2];
String s = "Tim";
t[0] = s; t[1] = s;

Dessinez les données en mémoire à l’issue de l’exécution de ces lignes.

"Réponse"

image-20210920123626822

Q7

Soit les lignes de code suivantes :

String[] t = new String[2];
String s = "Tim";
t[0] = s; 
t[1] = t[0] + "Tom";

Dessinez les données en mémoire à l’issue de l’exécution de ces lignes.

"Réponse"

image-20210920124007347


Vous avez commis des erreurs ? N’ayez aucune inquiétude. Le but de ce test était de vous faire commettre quelques erreurs pour attirer votre attention sur certaines subtilités. Vous devez vous expliquer à vous-même (vous auto-expliquer) ces erreurs et comment il fallait raisonner pour les éviter.

Au besoin, reprenez les ressources pédagogiques de la partie A pour revoir les points problématiques. N’hésitez pas à poser des questions à votre enseignant. Après avoir bien compris vos erreurs, retaites le test, mais pas tout de suite ! Attendez au moins une semaine, voire deux.

Java en LP : partie D

Partie D : Les exceptions

Objectif

Être capable d’implémenter au sein d’une application telle que celles décrites dans les objectifs des parties B et C une gestion des exceptions : implémentation de classes d’exception, levée et interception d’exceptions. Être capable de prévoir le comportement d’un programme dans lequel des exceptions peuvent être produites et interceptées.

Prérequis

Partie C


D1 : Lancer et gérer une exception

Java permet à une méthode ou un constructeur de lancer une exception lorsqu’une situation particulière se produit lors de son exécution. Une exception est un objet, plus précisément une instance d’une classe dérivant de la classe prédifinie Exception.

Nous allons découvrir ce ce concept avec un exemple. La classe ci-dessous représente une liste de notes obtenues par un élève à une unité d’enseignement.

public class SuiviUE
{
    private String idUE;  //Intitulé de l'UE
    private double coeff; //Coefficient
    private ArrayList<Double> notes;

    public SuiviUE(String nom, double coeff)
    {
        this.coeff = coeff;
        this.idUE = nom;
        this.notes = new ArrayList<>();
    }

    public void add(double note)
    {
        notes.add(note);
    }

    public String toString()
    {
        return "UE : " + idUE + " coefficient : " + coeff
                + " notes " + notes;
    }
}

On y trouve un constructeur créant une liste de note vide, une méthode pour ajouter une note, et une méthode pour afficher une description de l’instance courante. Une schéma très classique qui correspond aux compétences introduites dans la partie B du cours.

A titre d’exercice de rappel, ajoutez à la classe SuiviEU une méthode moyenne qui calcule et retourne la moyenne des notes situées dans la liste.

"Solution"

public double moyenne()
{
    double sum = 0.0;
    for(double x : notes) sum += x;
    return sum / notes.size();
}

Faisons maintenant l’expérience suivante, qui consiste à calculer la moyenne d’une instance de suiviUE à laquelle aucune note n’a été ajoutée.

public class Main
{
    public static void main(String[] args)
    {
        SuiviUE r = new SuiviUE("Java", 2.0);
        System.out.println(r.moyenne());
    }
}

On obtient l’affichage…

NaN

…qui signifie "Non Arithmetic Number". C’est ce qui se produit, dans beaucoup de langages de programmation, lors d’une tentative de division par 0 d’un nombre flottant (de type double).

Nous allons changer ce comportement en faisant en sorte que lorsqu’il n’y a pas de note, une exception soit levée, puis nous allons montrer comment exploiter cette exception. Mais pour commencer, il nous faut une classe dérivant de Exception.

public class Defaillance extends Exception
{
    private String id;

    public Defaillance(String ue)
    {
        //super();           // ligne A
        this.id = ue;
    }

    public String getID()
    {
        return id;
    }
}

Cette classe ne comporte pas d’attribut (mais on pourrait lui en ajouter si nécessaire) ni de méthode (mais on pourrait aussi en ajouter en cas de besoin). Son constructeur, qui permet de créer un objet de type exception, fait appel à un constructeur de la superclasse Exception qui accepte en argument une chaîne de caractères. Cette chaîne pourra être récupérée avec la méthode toString héritée de la classe Exception.

Si on enlève la mise en commentaire de la ligne A, le constructeur par défaut de la superclasse Exception est appelé explicitement, alors que sinon il est appelé implicitement, ce qui en pratique ne change rien.

Voici une nouvelle version de la méthode moyenne qui lève une exception de type Defaillance lorsque la liste de notes est vide.

public double moyenne() throws Defaillance // ligne A
{
    if(notes.size() == 0)
    {
        throw new Defaillance(idUE);       // ligne B
    }
    double sum = 0.0;
    for(double x : notes) sum += x;
    return sum / notes.size();
}

Deux nouveaux mot-clés importants apparaissent ici :

  • throws permet de dire au compilateur java que la méthode moyenne est susceptible de produire une exception du type indiqué. Il est possible d’indiquer ici plusieurs types d’exceptions.
  • throw permet de lever (lancer, produire) une exception et doit être suivi par une instance d’exception, généralement produite avec new et un constructeur d’une classe d’exception.

À chaque fois qu’une méthode susceptible de lancer une exception est appelée par une méthode m, la méthode m doit :

  • soit intercepter l’exception et la gérer,
  • soit la remonter à la méthode ayant appelé m.

Nous allons illustrer le premier cas.

public class Main
{
    public static void main(String[] args)
    {
        SuiviUE r = new SuiviUE("Java", 2.0);
        // r.add(12.0); r.add(17.0);  // ligne A
        try                           // ligne B
        {
            System.out.println(r.moyenne());
        }
        catch(Defaillance d)          // ligne C
        {
            System.out.println("Défaillance à l'UE : " + d.getID());
            return;
        }
        System.out.println(r);
    }
}

L’instruction trycatch permet d’intercepter les exceptions d’un ou plusieurs types qui se produisent dans le bloc de code try et et définir les actions à réaliser si de telles exceptions se produisent. Il peut y avoir plusieurs blocs catch permettant de spécifier des traitement spécifiques à différents types d’exceptions susceptibles de se produire lors de l’exécution du code du bloc try.

À l’issue de l’exécution du try catch, l’exécution du code de la méthode reprend son cours, qu’il y ait eu exception ou pas, sauf si le traitement d’une exception a mis fin à cette exécution par une instruction return, ce qui est le cas dans l’exemple.

Exercices de découverte

D-dec-10

Tentez de déterminer ce que va afficher le programme d’exemple ci-dessus, en prenant en compte que la ligne A est un commentaire, qui ne s’exécutera pas.

"Solution"

Défaillance à l'UE : Java

D-dec-11

Tentez de déterminer ce que va afficher le programme d’exemple ci-dessus si on retire la mise en commentaire de la ligne A.

"Solution"

14.5
UE : Java coefficient : 2.0 notes [12.0, 17.0]

D-dec-12

Tentez de déterminer ce que va afficher le programme d’exemple ci-dessus si on remet en commentaire la ligne A, comme dans l’exercice D-dec-10, et qu’on supprime le return.

"Solution"

Défaillance à l'UE : Java
UE : Java coefficient : 2.0 notes []

D-dec-13

On remplace la ligne C par :

        catch(Exception d)          // ligne C

On refait les expériences décrites dans les trois exercices précédentes et on obtient exactement les mêmes résultats. Pourquoi ?

"Solution"

Comme la classe Defaillance hérite de la classe Exception, toute instance de Defaillance est aussi une instance de Exception et sera donc capturée.

D2 : Plus loin avec les exceptions

Dans la section précédente, nous avons introduit une classe SuiviUE qui représente une liste de notes attribuées à un même élève (non désigné) pour une même unité d’enseignement identifiée par une chaîne de caractères et à laquelle est associé un coefficient.

Dans cette section, nous reprenons la même classe mais avec une petite modification : les attributs n’ont plus les droits d’accès private mais par défaut, c’est à dire qu’ils sont accessibles depuis toutes les classes du package dans lequel se trouve la classes SuiviUE.

public class SuiviUE
{
    String idUE;  //Intitulé de l'UE
    double coeff; //Coefficient
    ArrayList<Double> notes;

    public SuiviUE(String nom, double coeff)
    {
        this.coeff = coeff;
        this.idUE = nom;
        this.notes = new ArrayList<>();
    }

    public void add(double note)
    {
        notes.add(note);
    }

    public String toString()
    {
        return "UE : " + idUE + " coefficient : " + coeff
                + " notes " + notes;
    }

    public double moyenne() throws Defaillance
    {
        if(notes.size() == 0)
        {
            throw new Defaillance(idUE);
        }
        double sum = 0.0;
        for(double x : notes) sum += x;
        return sum / notes.size();
    }
}

Nous allons ajouter à ce package une nouvelle classe SuiviEtu qui représente les notes d’un même élève, identifié par un numéro, dans plusieurs unités d’enseignement. Les notes de cet élève, ou cette élève, pour chaque unité d’enseignement auquel il est inscrit (ou elle est inscrite), sont stockées dans une instance de SuiviUE.

Nous avons là une structure de donnée un peu complexe qui peut être difficile à bien visualiser mentalement en lisant la description ce-dessus. Pour mieux visualiser les données représentées et leur organisation, voici une représentation graphique qui correspond à un exemple dans lequel :

  • Il y a une instance de SuiviEtu représentant un élève identifié par le numéro 1233, qui est inscrit à deux unités d’enseignement : Java et BD.
  • Pour chacune de ces deux unités d’enseignement (UE en abrégé), il y a une instance de SuiviUE qui contient l’intitulé de l’UE concernée, son coefficient, et les notes de l’élève 1233 pour cette UE.

image-20210912230610160

Avant d’écrire le code de la classe SuiviUE, nous allons voir comment elle devra être utilisée pour créer les données représentées ci-dessus, mais, dans un premier temps, sans nous soucier de la gestion des exceptions.

public class Main
{
    public static void main(String[] args)
    {// Attention, les exceptions ne sont pas gérées
        SuiviEtu fiche = new SuiviEleve(1233);
        fiche.addUE("Java", 2.0);
        fiche.addUE("BD", 3.0);

        fiche.addNote("Java", 12.0);
        fiche.addNote("Java", 17.0);
        fiche.addNote("BD", 14.0);
        System.out.println(fiche.moyenne());
    }
}

Appelons élève courant la personne apprenante désignée par le numéro passé en paramètre au constructeur de la classe SuiviEtu On voit que la classe SuiviEtu devra disposer d’un constructeur, d’une méthode addUE pour ajouter une unité d’enseignement au suivi de l’élève courant, d’une méthode addNote pour ajouter une note de l’élève dans une des UE auxquelles l’élève courant est inscrit, et une méthode moyenne permettant de calculer la moyenne général de l’élève courant.

Examinons à présent le détail du code de la classe SuiviEtu en considérant différentes situation pouvant produire des exceptions (il nous faudra donc les gérer dans la version définitive de notre fonction main donnée en exemple ci dessus). Procédons par étape. Voici une première partie de la classe SuiviEtu dans laquelle il n’y a ni levée, ni gestion d’exception.

public class SuiviEtu
{
    private int numEtu;
    private ArrayList<SuiviUE> suivi;

    public SuiviEtu(int num)
    {
        this.numEtu = num;
        this.suivi = new ArrayList<>();
    }

    public void addUE(String idUE, double coeff)
    {
        suivi.add(new SuiviUE(idUE, coeff));
    }

    // À compléter
}

Vérifiez que vous comprenez bien ce code. Le constructeur est assez classique. La méthode addUE permet d’ajouter une UE à laquelle l’élève courant est inscrit. Pour se faire, elle crée une instance de SuiviUE et elle l’ajoute à la liste des UE suivies par l’élève courant, qui est désignée par l’attribut suivi. N’allez pas trop vite. Si vous ne comprenez pas de manière limpide, revenez en arrière et regardez l’illustration basée sur l’exemple présenté plus haut.

À présent regardons le code de la méthode moyenne permettant de calculer la moyenne générale de l’élève courant.

public double moyenne() throws Defaillance     // ligne A
{
    double sum = 0.0; double sumCoeffs = 0.0;
    for(SuiviUE sue : suivi)
    {
        sum += sue.moyenne() * sue.coeff;
        sumCoeffs += sue.coeff;
    }
    return sum / sumCoeffs;
}

Il y a une nouveauté. Cette méthode appelle la méthode moyenne de la classe suiviUE, qui est susceptible de produire une exception de type Defaillance. Mais au lieu d’intercepter cette exception avec un trycatch, elle la fait remonter en indiquant throws Defaillance (ligne A). Ceci signifie que c’est la méthode qui appelle la méthode moyenne de la classe SuiviEtu qui va devoir soit gérer cette exception, soit la faire remonter.

Mais tout ceci ne nous sert à rien tant qu’on ne peut pas attribuer de note à l’élève courant, ce qui est le rôle de la méthode addNote de la classe SuiviEtu Cette méthode devra rechercher dans la liste des UE auxquelles est inscrit l’élève courant (désignée par l’attribut suivi) l’instance de SuiviUE dans laquelle il faut placer la note à ajouter. Cette recherche est basée sur l’intitulé de l’UE concernée. Mais que faire si l’UE en question n’est pas dans la liste ? C’est à dire par exemple si on veut ajouter une note à l’UE "Allemand" mais que cette UE n’a pas été ajoutée à celle suivies par l’élève courant avec la méthode addUE ?

On va lever une exception ! Mais pour éviter de tout mélanger, on va introduire pour cet usage un nouveau type d’exception appelé BadUE.

public class BadUE extends Exception
{
    private String idUE;

    public BadUE(String id)
    {
        this.idUE = id;
    }

    public String getId()
    {
        return idUE;
    }
}

Voilà, maintenant voici le code de la méthode addNote de la classe SuiviEtu.

public void addNote(String idUE, double note) throws BadUE
{
    for(SuiviUE sue : suivi)
    {
        if(sue.idUE.equals(idUE))
        {
            sue.add(note); return;
        }
    }
    throw new BadUE(idUE);
}

Le principe est assez simple : on parcours la liste des instances de SuiviUE enregistrées dans la liste désignée par l’attribut suivi jusqu’à trouver celle ayant l’intitulé recherché. Si on la trouve, alors on utilise la méthode add de la classe SuiviUE pour ajouter la note, puis on arrête l’exécution de la méthode avec return. Si on ne la trouve pas, on lève une exception de type BadUE.

Si vous êtes débutant ou débutante, vous devez faire attention à ne pas confondre l’identifiant (ou nom ou intitulé) d’une unité d’enseignement et l’instance de SuiviUE représentant les notes obtenue par un élève dans cette UE.

Bien que le principe soit simple, il y a une subtilité qui, si elle n’est pas maîtrisée, pourra vous amener à faire des erreurs lorsque vous aurez besoin de comparer deux chaînes de caractères (représentant des identifiants d’UE).

Pour chaque instance sue de la la classe SuiviUE stockée dans la liste désignée par l’attribut suivi de l’instance courante de la classe SuiviEtu

for(SuiviUE sue : suivi)

…on veut comparer l’intitulé de l’UE représentée par sue, c’est à dire sue.idUE, avec l’intitulé de l’UE à rechercher, c’est à dire idUE, passé en paramètre. On veut donc comparer les deux chaînes de caractères désignées respectivement par idUE et sue.idUE. Pour comparer ces chaînes, on pourrait être tenter d’écrire…

if(sue.idUE == idUE)    // ERREUR !

…, ce qui serait une mauvaise idée. En effet, les chaînes sont des objets, des instances de String, désignées par leur référence, c’est à dire leurs adresses en mémoire. L’opérateur == compare les références et non les contenus des chaînes. Pour comparer les contenus, on peut utiliser la méthode equals qui a été définie dans le classe pédéfinie String pour cet usage. D’où la ligne…

if(sue.idUE.equals(idUE))

Il nous reste à revoir notre méthode main car telle qu’elle est codée plus haut, elle ne gère pas les deux types d’exceptions qu’elle peut recevoir : Defaillance et BadUE. Voici une manière de procéder.

public class Main
{
    public static void main(String[] args)
    {
        SuiviEtu fiche = new SuiviEtu(1233);
        fiche.addUE("Java", 2.0);
        fiche.addUE("BD", 3.0);
        try
        {
            fiche.addNote("Java", 12.0);
            fiche.addNote("Java", 17.0);
            fiche.addNote("BD", 14.0);
            System.out.println(fiche.moyenne());
        }
        catch(Defaillance ue)
        {// Traitement des exceptions produites par fiche.moyenne()
            System.out.println("Défaillance à l'UE : " + ue.getID());
        }
        catch(BadUE ue)
        {// Traitement des exceptions produites par fiche.addNote(...)
            System.out.println("UE non référencée : " + ue.getId());
        }
    }
}

Examinez ce code avec attention. La création de la fiche de suivi de l’élève 1233 et l’ajout des deux UE auxquelles cet élève est inscrit reste identique puisque ni le constructeur, ni la méthode addUE de la classe SuiviEtu ne sont susceptibles de lever une exception.

Par contre, les lignes qui suivent ont été placées dans un trycatch chargé d’intercepter, si applicable, les deux types d’exception pouvant être produites.

Ce programme est un peu compliqué lorsqu’on l’examine morceau par morceau sans avoir une vue d’ensemble. Certaines personnes peuvent avoir cette vue d’ensemble juste en lisant les codes des classes, mais si vous êtes débutante ou débutant, cela peut être très difficile. Ce schéma devrait vous aider. Il présente chacune des deux classes, leurs attributs, constructeurs et principales méthodes, et fait apparaitre le graphe d’appel qui matérialise par une flèche les appels de méthodes.

image-20210918221710711

Par exemple, la méthode main appelle la méthode moyenne de la classe SuiviEtu qui appelle la méthode moyenne de la classe SuiviUE. On voit que la méthode moyenne de SuiviUE peut lever une exception de type Defaillance, qui est récupérée pat la méthode moyenne de la classe SuiviEtu qui la remonte à la méthode main.

Exercices de découverte

D-dec-20

Lors de l’exécution de la méthode main ci dessus, aucune exception n’est levée. Faite une modification pour qu’une exception de type Defaillance soit levée et dites quels seront alors les affichages réalisés lors de l’exécution.

"Solution"

Dans le bloc try on met en commentaire la ligne qui ajoute une note pour l’UE "BD".

try
{
    fiche.addNote("Java", 12.0);
    fiche.addNote("Java", 17.0);
    //fiche.addNote("BD", 14.0);
    System.out.println(fiche.moyenne());
}

À l’exécution, le programme affiche uniquement :

Défaillance à l'UE : BD

D-dec-21

En repartant de la méthode main donnée plus haut, celle qui ne produit aucune exception, faire une modification pour qu’une exception de type BadUE soit levée et dites quels seront alors les affichages réalisés lors de l’exécution.

"Solution"

Par exemple on peut remplacer "BD" par "GEO" dans la troisième ligne du bloc try.

try
{
    fiche.addNote("Java", 12.0);
    fiche.addNote("Java", 17.0);
    fiche.addNote("GEO", 14.0);
    System.out.println(fiche.moyenne());
}

À l’exécution, le programme affiche uniquement :

UE non référencée : GEO

D-dec-22

Dans la version de la classe SuiviEtu donnée plus haut, la méthode moyenne, si elle reçoit une exception de type Defaillance, la fait remonter. Modifiez la méthode de manière à ce que, si elle reçoit une exception de type Defaillance, elle affiche le message "L’élève n’a pas de note dans l’UE {ID de l’ue}" et retourne 0.0.

"Solution"

public double moyenne_bis()
{
    double sum = 0.0; double sumCoeffs = 0.0;
    for(SuiviUE sue : suivi)
    {
        try
        {
            sum += sue.moyenne() * sue.coeff;
        }
        catch(Defaillance d)
        {
            System.out.println("L'élève n'a pas de note dans l'UE " + d.getID());
            return 0.0;
        }
        sumCoeffs += sue.coeff;
    }
    return sum / sumCoeffs;
}

D3 : Compléments

Le bloc Finaly

Un trycatch peut être suivi d’un bloc finally. Le code situé dans ce bloc est systématiquement exécuté à l’issue du trycatch qu’i y ait eu ou non interception d’exception, et même si un return est réalisé dans un bloc catch.

Un usage typique est de refermer un fichier ayant été ouvert dans le bloc try, mais cela sort du périmètre de cet enseignement.

Les exceptions "run time"

Les exceptions dérivant de la classe RuntimeException ont la particularité de remonter automatiquement, si elle ne sont pas interceptées, sans que les méthodes où elles se produisent aient à le spécifier avec throws. L’usage typique est la gestion des erreurs de programmations qui doivent entrainer un arrêt de l’exécution du programme. Java produit lui même de telles exceptions, par exemple lors d’une tentative d’appel d’une méthode avec une variables contenant une valeur null au lieu de la référence d’un objet (NullPointerException), ou encore lors d’une tentative d’accès à une cellule de tableau à un indice incorrect (OutOfBoundException).

Vous pouvez créer et intercepter des exceptions de type RuntimeException, et vous pouvez également intercepter celles produites par Java. Les exceptions de ce type non interceptées remontent jusqu’à la machine virtuelle Java, provoquant l’affichage d’un message d’erreur indiquant dans quelle méthode le problème est survenu.

Faisons l’expérience suivante.

public class TestRuntimeExceptions
{
    public static void main(String[] args)
    {
        int[] tab = new int[5];
        tab[5] = 12;
        System.out.println("Exécution terminée");
    }
}

À l’exécution, le programme s’arrête et affiche :

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 
Index 5 out of bounds for length 5	at TestRuntimeExceptions.main(TestRuntimeExceptions.java:8)

On voit que le message "Exécution terminée" ne s’est pas affiché car le programme a été interrompu avant par une exception de type ArrayIndexOutOfBoundsException déclenchée par une tentative d’accès à tab[5] alors que le tableau désigné par tab possède 5 cellules allant de tab[0] à tab[4]. (Une erreur classique de débutant.)

Voici un exemple d’interception de toute exception de type RuntimeException.

public static void main(String[] args)
{
    try
    {
        int[] tab = new int[5];
        tab[5] = 12;
        System.out.println("Exécution terminée");
    }
    catch(RuntimeException e)
    {
        System.out.println("Une erreur s'est produite.");
    }
}

Lors de l’exécution, on obtient l’affichage :

Une erreur s'est produite.

Le genre de message un peu énervant parce que pas très informatif…

Si on écrit ceci…

public static void main(String[] args)
{
    try
    {
        int[] tab = new int[5];
        tab[5] = 12;
        System.out.println("Exécution terminée");
    }
    catch(RuntimeException e)
    {
        System.out.println(e);
    }
}

…alors on obtient l’affichage :

ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

L’affichage de l’instance d’exception e a invoqué la méthode toString de la classe ArrayOutOfBoundsException qui a fourni des informations utiles.

Exercices de découverte

D-dec-30

Soit la méthode main suivante :

public static void main(String[] args)
{
    try
    {
        int[] tab = new int[5];
        tab[5] = 12;
        System.out.println("Exécution terminée");
    }
    catch(RuntimeException e)
    {
        System.out.println("----- ERREUR D'EXECUTION -----");
        throw e;
    }
}

Tentez de prévoir ce que le l’exécution de cette méthode va afficher à l’écran.

"Solution"

Comme une exception de type Runtime Exception est produite dans le bloc try, le bloc catch sera exécuté et affichera "----- ERREUR D'EXECUTION -----". Le code situé dans le bloc try après la ligne où l’erreur se produit ne sera pas exécuté.

Mais dans le bloc catch, l’exception est relancée par throw e ! (Celle là, on ne vous l’avait encore jamais faite.) Donc cette exécution est remontée à la machine virtuelle et provoque un affichage détaillé de l’erreur à l’origine de l’exception. On obtient l’affichage :

----- ERREUR D'EXECUTION -----
Exception in thread "main" ArrayIndexOutOfBoundsException: 
Index 5 out of bounds for length 5 at TestRuntimeExceptions.main(TestRuntimeExceptions.java:10)

D-dec-31

Soit la méthode main suivante :

public class TestRuntimeExceptions
{
    public static void main(String[] args)
    {
        try
        {
            int[] tab = new int[5];
            tab[5] = 12;
            System.out.println("Exécution terminée");
        }
        catch(RuntimeException e)
        {
            System.out.println("----- ERREUR D'EXECUTION -----");
        }
    }
}

On voudrait que le message "Exécution terminée" s’affiche toujours à l’issue de l’exécution du programme, qu’il y ait ou non une exception produite dans le bloc catch. Avec la nouvelle version, si on écrit tab[5] = 12 dans le bloc try, on devra avoir l’affichage…

----- ERREUR D'EXECUTION -----
Exécution terminée

…alors que si on écrit tab[4] = 12 on aura l’affichage :

Exécution terminée

Essayez de trouver deux manières d’obtenir ce résultat, une utilisant un bloc finally et une autre solution sans utiliser un tel bloc.

"Solution"

Avec un bloc finally, on peut écrire :

public static void main(String[] args)
{
    try
    {
        int[] tab = new int[5];
        tab[5] = 12;
    }
    catch(RuntimeException e)
    {
        System.out.println("----- ERREUR D'EXECUTION -----");
    }
    finally
    {
        System.out.println("Exécution terminée");
    }
}

Sans utiliser un tel bloc, on peut écrire :

    public static void main(String[] args)
    {
        try
        {
            int[] tab = new int[5];
            tab[4] = 12;
        }
        catch(RuntimeException e)
        {
            System.out.println("----- ERREUR D'EXECUTION -----");
        }
        System.out.println("Exécution terminée");
    }

En effet, s’il n’y a pas de return ou de levée d’une exception ou autre instruction qui arrête le programme dans le bloc catch, l’exécution reprend son cours après les blocs trycatch et le bloc finally n’est pas vraiment utile. En revanche, si un bloc catch interrompt le programme, le bloc finally sera quand même exécuté alors que le code qui est au delà ne le sera jamais.

D-dec-32

Soit la méthode main suivante :

public static void main(String[] args)
{
    try
    {
        int[] tab = new int[5];
        tab[5] = 12;      // ligne A
    }
    catch(RuntimeException e)
    {
        System.out.println("----- ERREUR D'EXECUTION -----");
        return;
    }
    System.out.println("Exécution terminée");
}

Qu’affiche très exactement l’exécution du programme ? Même question si on supprime la ligne A ou si on la met complètement en commentaire ?

"Solution"

Avec la ligne A :

----- ERREUR D'EXECUTION -----

Sans la ligne A :

Exécution terminée

D-dec-33

Soit la méthode main suivante :

    public static void main(String[] args)
    {
        try
        {
            int[] tab = new int[5];
            tab[5] = 12;      // ligne A
        }
        catch(RuntimeException e)
        {
            System.out.println("----- ERREUR D'EXECUTION -----");
            return;
        }
        finally
        {
            System.out.println("Exécution terminée");
        }
    }

Qu’affiche très exactement l’exécution du programme ? Même question si on supprime la ligne A ou si on la met complètement en commentaire ?

"Solution"

Avec la ligne A :

----- ERREUR D'EXECUTION -----
Exécution terminée

Sans la ligne A :

Exécution terminée

Exercices d’assimilation

D-ass-00

La méthode suivante permet de saisir un entier au clavier.

    public static int lireInt()
    {
        return new Scanner(System.in).nextInt();
    }

Mais si la valeur saisie n’est pas un entier, elle produit une exception de type InputMismatchException. Proposez une nouvelle version de la méthode lireInt qui en cas de saisie correcte, retourne une instance de la classe enveloppe Integer contenant l’entier saisi, et qui dans le cas contraire retourne null.

"Indice

Voici un squelette de la méthode à compléter. L’exception attendue dans la partie catch est de type InputMismatchException, mais le type Exception plus général convient aussi dans ce cas.

public static Integer lireInt()
{
    try
    {
        // À compléter
    }
    catch(Exception e)
    {
        // À compléter
    }
}

"Solution"

Voici une solution complète. Des variantes sont possibles. Au besoin faites des essais sur machine.

public static Integer lireInt()
{
    try
    {
        return new Scanner(System.in).nextInt();
    }
    catch(Exception e)
    {
        return null;
    }
}

D-ass-01

Proposez une troisième version de la méthode lireInt de l’exercice précédent qui en cas de saisie correcte, retourne l’entier saisi (la valeur de retour est donc de type int, comme pour la première version), et qui, en cas de saisie incorrecte, redemande à l’utilisateur de faire une nouvelle saisie jusqu’à ce qu’une saisie correcte soit réalisée.

"Indice

Voici un squelette d’une solution simple. La présence du while(true) pout choquer certains puristes, mais elle ne me semble pas nuire à la lisibilité du code. La sortie de la boucle se fait par l’instruction return lorsque le « job » de la méthode est terminé, c’est-à-dire quand l’utilisateur a réalisé une saisie correcte.

public static Integer lireInt()
{
    while(true)
    {
        try
        {
            // À compléter
        }
        catch(Exception e)
        {
            // À compléter
        }
    }
}

"Solution"

public static Integer lireInt()
{
    while(true)
    {
        try
        {
            return new Scanner(System.in).nextInt();
        }
        catch(Exception e)
        {
            System.out.println("Saisie incorrecte, veuillez recommencer");
        }
    }
}

D-ass-02

Modifiez le constructeur de la classe Date du badge B pour qu’il lève une exception de type BadDate, à définir, si la valeur du jour ou du mois est incorrecte ou si celle de l’année est inférieure à MINY ou supérieure MAXY, deux constantes de classe définies dans BadDate. La classe BadDate dispose d’un constructeur acceptant un paramètre de type String qui appelle le constructeur Exception(String message). C’est ce constructeur qui devra être utilisé pour lever (si applicable) l’exception en lui passant en argument un message indiquant la nature du problème (Année incorrecte, ou Jour incorrect ou Mois incorrect). Un jour est considéré comme incorrect s’il est inférieur à 1 ou supérieur à 31. On ne prend pas en compte la durée réelle des mois dans cette version simplifiée. Réalisez une méthode de test qui tente de créer une date incorrecte, intercepte l’exception et affiche un message d’erreur pertinent.

"Indice

Commençons par définir la classe d’exception.

public class BadDate extends Exception
{
    public BadDate(String message)
    {
        super(message);
    }
}

"Indice

Regardons les modifications à faire dans la classe Date. Voici la déclaration des constantes (initialisées avec des valeurs arbitraires à titre d’exemple) et le squelette du constructeur à modifier.

public class Date
{
    final public static int MAXY = 2100;
    final public static int MINY = 1700;

    private int jour;
    private int mois;
    private int annee;

    public Date(int jour, int mois, int annee) throws BadDate
    {
        // À compléter

        this.jour=jour; this.mois=mois; this.annee=annee;
    }
}

"Indice

Voici le détail du constructeur de la classe Date, qui lève une même exception, mais avec des messages d’erreur différents selon le paramètre erroné.

public Date(int jour, int mois, int annee) throws BadDate
{
    if((annee<MINY)||(annee>MAXY))
    {
        throw new BadDate("Annee incorrecte");
    }
    else if ((jour<1)||(jour>31))
    {
        throw new BadDate("Jour incorrect");
    }
    else if ((mois<1)||(mois>12))
    {
        throw new BadDate("Mois incorrect");
    }
    this.jour=jour; this.mois=mois; this.annee=annee;
}

Il vous reste à écrire la méthode de test.

"Solution"

Voici le détail de la méthode de test.

public static void test()
{
    try
    {
        Date d = new Date(32,7,2012);
    }
    catch(BadDate e)
    {
        System.out.println(e);
    }
}