Examen intermédiaire : corrigé

1 Polynômes

1.1 Partie 1

Il y a trois points auxquels il faut penser lors de l'écriture du constructeur :

  1. la classe Polynomial est immuable, donc la table des coefficients reçue doit être copiée, puis idéalement rendue non modifiable (même si ce n'est pas strictement nécessaire),
  2. les coefficients nuls éventuellement présents dans la table donnée en argument ne doivent pas être stockés,
  3. la présence d'un degré négatif doit être détectée et produire la levée de l'exception IllegalArgumentException.

Ces trois points peuvent être gérés dans le cadre d'une boucle qui parcourt la table des coefficients, vérifie que le degré de chacun est positif ou nul, et copie les coefficients non nuls dans la nouvelle table.

C'est cette approche qui est suivie dans le code ci-dessous, dans lequel on prend de plus soin de choisir TreeMap comme mise en œuvre de la table des coefficients, ce qui simplifie l'écriture de la méthode toString plus tard.

public Polynomial(Map<Integer, Integer> coefs) {
    Map<Integer, Integer> nonZeroCoefs = new TreeMap<>();
    for (Map.Entry<Integer, Integer> e: coefs.entrySet()) {
        if (e.getKey() < 0)
            throw new IllegalArgumentException();
        if (e.getValue() != 0)
            nonZeroCoefs.put(e.getKey(), e.getValue());
    }
    this.coefs = Collections.unmodifiableMap(nonZeroCoefs);
}

1.2 Partie 2

La méthode add doit construire une table de coefficients pour la somme des polyômes en combinant les coefficients de la table du récepteur avec ceux de la table du polynôme passé en argument, puis l'utiliser pour créer un nouveau polynôme qu'elle retourne.

Cela peut se faire de différentes manières, la technique utilisée ci-dessous consistant à :

  1. dans un premier temps, copier la totalité des coefficients de l'argument dans la table résultat, au moyen du constructeur de copie,
  2. ensuite, parcourir les coefficients du polynôme récepteur, et les combiner avec ceux déjà présents dans la table ; une manière simple de faire cette combinaison est d'utiliser la méthode getOrDefault pour obtenir soit le coefficient déjà présent dans la table, soit 0.
public Polynomial add(Polynomial that) {
    Map<Integer, Integer> summedCoefs =
        new HashMap<>(that.coefs);
    for (Map.Entry<Integer, Integer> e: coefs.entrySet()) {
        int c = summedCoefs.getOrDefault(e.getKey(), 0);
        summedCoefs.put(e.getKey(), c + e.getValue());
    }
    return new Polynomial(summedCoefs);
}

1.3 Partie 3

La méthode valueAt peut s'écrire simplement en parcourant les paires (degré \(d\), coefficient \(c\)) de la table, de les utiliser pour calculer le terme \(c\cdot x^d\) puis de faire la somme de ces termes.

public double valueAt(double x) {
    double r = 0;
    for (Map.Entry<Integer, Integer> e: coefs.entrySet())
        r += e.getValue() * Math.pow(x, e.getKey());
    return r;
}

1.4 Partie 4

Comme la table des coefficients n'inclut pas les coefficients nuls, on a la garantie que deux polynômes sont égaux si et seulement si leurs tables de coefficients sont égales. Cela se vérifie facilement au moyen de la méthode equals appliquée à ces tables, les collections Java étant comparées de manière structurelle.

@Override
public boolean equals(Object thatO) {
    return (thatO instanceof Polynomial)
        && coefs.equals(((Polynomial)thatO).coefs);
}

Pour la même raison, la méthode hashCode peut se contenter de retourner la valeur de hachage de la table des coefficients.

@Override
public int hashCode() {
    return coefs.hashCode();
}

Bien entendu, il n'est pas faux d'utiliser la méthode Objects.hash, mais cela est légèrement plus coûteux.

1.5 Partie 5

Non, il ne serait pas judicieux que la classe Polynomial implémente l'interface Comparable, car il n'existe pas de notion d'ordre naturelle pour les polynômes en mathématiques.

1.6 Partie 6

La méthode toString serait relativement simple à écrire s'il n'était pas demandé qu'elle produise des chaînes minimales sans facteurs, exposants ou signes + superflus. Dans ce cas simple, il suffirait de parcourir les entrées de la table des coefficients en produisant pour chacun d'eux une chaîne composée de :

  • le coefficient, toujours précédé de son signe (+ ou -),
  • la chaîne x représentant l'indéterminée,
  • la chaîne ^ représentant l'exponentiation,
  • l'exposant.

En ajoutant ces chaînes successives à un bâtisseur de chaîne, on obtiendrait soit la chaîne désirée, soit la chaîne vide pour le cas du polynôme 0. Dans ce dernier cas, il suffirait de retourner la chaine 0.

Notez qu'on fait ci-dessus l'hypothèse que les termes sont parcourus par degré croissant, ce qui est le cas si on a pris soin de les stocker dans une table de type TreeMap. Sinon, il faut au préalable placer les degrés (donc les clefs) de la table dans une liste puis la trier, ce qui complique et ralentit les choses.

La chaîne produite par la méthode décrite ci-dessus n'est malheureusement pas minimale, contrairement à ce que demande l'énoncé. Pour qu'elle le soit, il faut en supprimer (ou plutôt ne pas y ajouter) toutes les parties superflues, qui sont :

  • le signe + en tout début de la chaîne,
  • tout coefficient de degré supérieur à zéro et égal à ±1, pour lequel le signe suffit,
  • la partie ^1 pour le coefficient de degré 1,
  • la partie x^0 pour le coefficient de degré 0.

En combinant l'idée de la méthode simple avec les tests permettant de ne pas inclure ces parties superflues, on obtient la méthode toString ci-dessous :

@Override
public String toString() {
    StringBuilder b = new StringBuilder();
    for (Map.Entry<Integer, Integer> e: coefs.entrySet()) {
        int d = e.getKey(), c = e.getValue();

        if (d == 0)
            b.append(c);
        else {
            if (c < 0 || b.length() > 0)
                b.append(c < 0 ? "-" : "+");

            int cAbs = Math.abs(c);
            if (cAbs != 1)
                b.append(cAbs);
            b.append("x");
            if (d > 1)
                b.append("^").append(d);
        }
    }
    return b.length() == 0 ? "0" : b.toString();
}

2 Entropie d'un flot

La classe EntropyInputStream est similaire à la classe LineNumberReader décrite au cours, en ce qu'elle ressemble à un flot filtrant qui ne filtre pas les données du flot sous-jacent mais calcule et met à disposition une information concernant ces données. Dans le cas de LineNumberReader l'information en question est le numéro de ligne actuel, dans le cas de EntropyInputStream, il s'agit de l'entropie.

Dès lors, il est clair que EntropyInputStream doit stocker les informations concernant les octets produits jusqu'à présent par le flot sous-jacent nécessaires au calcul de l'entropie. En examinant la formule de l'énoncé, on constate que cela implique de pouvoir à tout moment déterminer la probabilité d'apparition de chaque octet, c-à-d \(p(i)\) pour \(i\) allant de 0 à 255. Or cette probabilité est donnée par le nombre d'occurrences de l'octet \(i\) divisé par le nombre total d'octets produits. On en conclut que deux informations doivent être conservées, à savoir :

  • le nombre d'occurrences pour chaque octet,
  • le nombre total d'octets produits.

La première de ces deux information se stocke naturellement dans un tableau d'entiers indicé par les octets, la seconde dans un simple entier.

Ces constatations faites, on est en mesure d'écrire la déclaration de la classe EntropyInputStream et son constructeur :

public class EntropyInputStream extends InputStream {
    private final InputStream underlyingStream;
    private final int[] counts;
    private int totalCount;

    public EntropyInputStream(InputStream underlyingStream) {
        this.underlyingStream = underlyingStream;
        this.counts = new int[256];
        this.totalCount = 0;
    }

    // … méthodes read, close et entropy
}

La méthode read doit lire un octet du flot sous-jacent et le retourner après avoir mis à jour les informations permettant le calcul de l'entropie, ce qui se fait très facilement si on pense à gérer correctement le cas où le flot sous-jacent est épuisé et sa méthode read retourne –1 :

@Override
public int read() throws IOException {
    int b = underlyingStream.read();
    if (b != -1) {
        totalCount += 1;
        counts[b] += 1;
    }
    return b;
}

La méthode close doit également être redéfinie afin que le flot sous-jacent soit fermé lorsque le flot calculant l'entropie l'est :

@Override
public void close() throws IOException {
    underlyingStream.close();
}

Finalement, seule la méthode calculant l'entropie reste à faire. Elle consiste en une simple traduction de la formule donnée dans l'énoncé :

public double entropy() {
    double sum = 0;
    for (int c: counts) {
        if (c == 0)
            continue;
        double p = (double)c / (double)totalCount;
        sum += p * log(p) / log(2d);
    }
    return -sum;
}

A noter qu'il est aussi possible d'utiliser la programmation par flots pour définir cette méthode, mais cela demande l'utilisation de méthodes qui n'ont ni été vues au cours, ni présentées dans le formulaire de l'examen. Néanmoins, il peut être intéressant de comparer une telle mise en œuvre avec celle ci-dessus, pour constater une fois de plus tout l'intérêt de ce style de programmation :

public double entropy() {
    return -IntStream.of(counts)
        .filter(c -> c != 0)
        .mapToDouble(c -> (double)c / (double)totalCount)
        .map(p -> p * log(p) / log(2d))
        .sum();
}

3 Comparateurs partiels

Le principal problème de cet exercice est de comprendre la notion de comparateur partiel, après quoi le code est presque trivial à écrire.

Notez qu'un comparateur partiel n'est rien d'autre qu'une représentation Java de ce que l'on nomme un ordre partiel en mathématiques, notion qui avait été abordée lors du cours sur la généricité avancée. De même, un comparateur (total, de type Comparator) est une représentation Java de la notion mathématique d'ordre total.

3.1 Partie 1

La définition de l'interface fonctionnelle représentant un comparateur partiel ne pose pas de difficulté, il suffit de penser à en faire une interface générique (comme Comparator, pour la simple raison que le type exact des objets à comparer peut varier) et de donner le bon type à sa méthode abstraite. On obtient :

public interface PartialComparator<T> {
    boolean lessOrEqual(T x, T y);
}

3.2 Partie 2

Sachant qu'un comparateur retourne une valeur négative ou nulle si le premier objet qu'on lui passe est inférieur ou égal au second, la définition de la méthode ofTotal est simple :

static <T> PartialComparator<T> ofTotal(Comparator<T> c) {
    return (x, y) -> c.compare(x, y) <= 0;
}

3.3 Partie 3

Finalement, la méthode comparable est une simple traduction en Java du texte de l'énoncé, qui dit que deux objets sont comparables si l'un des deux est inférieur ou égal à l'autre :

default boolean comparable(T x, T y) {
    return lessOrEqual(x, y) || lessOrEqual(y, x);
}