Sujet

Énoncé

Bienvenue dans l'examen blanc de mi-semestre !

Si vous n'êtes pas en salle machine pendant votre séance 12 de TP... ne lisez pas plus loin ! Le but de ce test est de vous entraîner en conditions réelles, il n'a pas d'intérêt si vous regardez le sujet avant la séance.

Règles du jeu

Le but de cet examen blanc est de faire un point à mi-parcours et de vous permettre de vous positionner par rapport à l'avancement et aux attendus du cours : il n'est pas noté.

Pour que ce test vous apporte quelque-chose, il faut se placer dans des conditions d'examen, c'est-à-dire que :

• vous devez travailler individuellement sans communiquer avec vos camarades ;
• vous avez accès, via le site web du cours, à tous les supports utilisés jusqu'ici (CM, TD, TP), corrections incluses ;
• vous ne devez pas vous servir de vos notes de cours / TD ;
• vous ne devez pas vous servir des données sur votre compte informatique (sources de vos TP précédents, etc.) :
• conservez bien votre « rendu » (même si vous n'avez pas à le rendre !) car on travaillera à nouveau ce sujet lors du prochain TP de BPI.

Crible d'Ératosthène

On va implanter dans cet exercice le fameux crible d'Ératosthène (célèbre informaticien grec du IIIᵉ siècle avant notre ère). Le crible d'Ératosthène est un algorithme permettant de lister tous les nombres premiers inférieurs ou égaux à une valeur maximale donnée.

Le principe de cet algorithme est très simple :

• on demande à l'utilisateur la valeur maximale val_max ;
• on alloue un tableau statique (qu'on appellera les_premiers) de booléens numérotés de 1 à val_max, et on initialise toutes ses cases à True ;
• on affecte la première case de ce tableau à False, car 1 n'est pas un nombre premier ;
• on pose prem vaut 2 (le premier nombre premier) et on parcourt les_premiers pour mettre à False toutes les cases dont le numéro est multiple de prem : 4, 6, 8, etc. ne sont pas des nombres premiers, on les « barre » dans le tableau ;
• on passe prem au plus petit entier supérieur qui n'a pas été barré et on répète le processus :
  • le plus petit entier supérieur à 2 et non barré est prem = 3 : on barre tous les multiples de 3 dans le tableau ;
  • le plus petit entier supérieur à 3 et non barré est prem = 5 (4 est un multiple de 2, il a déjà été barré) : on barre tous les multiples de 5 dans le tableau ;
  • etc.
• on peut s'arrêter dès que prem atteint $\sqrt{val\_max}$, car on est alors sûr d'avoir déjà barré tous les nombres composés plus grands.

On détaille ci-dessous les différentes étapes à réaliser pour implanter cet algorithme dans un fichier que vous appellerez crible.py et dont on vous fournit le squelette :

#!/usr/bin/env python3
"""
Crible d'Ératosthène
"""

def init_tab(taille):
    # TODO
    ...

def filtre(les_premiers, prem):
    # TODO
    ...

def affiche(les_premiers, val_max):
    # TODO
    ...

def main():
    # TODO
    ...

if __name__ == "__main__":
    main()

Chaque fonction devra être commentée de façon appropriée, en précisant notamment le rôle et la nature de ses paramètres, ainsi que ce qui est renvoyé à la fin de la fonction le cas échéant. On s'attend à ce qu'une exécution de pylint crible.py donne un score de 10/10.

On rappelle qu'en Python les tableaux sont forcément indicés à partir de 0 : la case numéro 1 (la première) d'un tableau a l'indice 0, la case numéro 2 (la deuxième) a l'indice 1, etc.

On considérera dans tout l'exercice qu'on travaille sur un tableau statique : vous ne devez utiliser aucune primitive Python manipulant des tableaux dynamiques (append, del, index, etc.), qui vous seraient d'ailleurs parfaitement inutiles vu l'algorithme demandé.

Initialisation du tableau

Commencez par écrire une fonction init_tab(taille) dont le but est d'allouer un tableau de booléens de la taille voulue, d'initialiser ses cases à True (sauf la première qui devra être initialisée à False) et de renvoyer ce tableau à la fonction principale. Vous pouvez exceptionnellement utiliser la méthode append dans cette question si vous ne connaissez pas les compréhensions de listes Python.

Filtrage des multiples d'un nombre donné

Implantez maintenant une fonction filtre(les_premiers, prem) dont le rôle est d'affecter à False toutes les cases du tableau les_premiers dont le numéro est un multiple de prem.

Affichage du résultat

Écrivez ensuite une fonction affiche(les_premiers, val_max) qui affiche les numéros des cases contenant True, sous le format suivant (en supposant que val_max vaut 10) : Les nombres premiers inférieurs ou égaux à 10 sont : 2 3 5 7.

Programme principal

Implantez enfin la fonction main qui sera le point d'entrée du programme et devra donc demander à l'utilisateur la valeur maximale, puis utiliser les fonctions précédentes pour implanter l'algorithme du crible d'Ératosthène.

Votre programme devra bien vérifier que la valeur entrée par l'utilisateur est un entier supérieur ou égal à 2. Dans le cas contraire, on arrêtera immédiatement le programme avec un message d'erreur adapté. Pour cela, vous lancerez une exception de type ValueError.

Ce lien vous emmènera vers la documentation du module math qui contient notamment les fonctions floor (partie entière) et sqrt (racine carrée) qui vous serons vraisemblablement utiles.

Correction

Cliquez ici pour révéler la correction.

#!/usr/bin/env python3
"""
Crible d'Ératosthène
"""

from math import floor, sqrt

def init_tab(taille):
    """
    Alloue, initialise et renvoie un tableau de taille booléens avec :
    - False dans la première case ;
    - True dans toutes les autres.
    """
    les_premiers = [True for _ in range(taille)]
    les_premiers[0] = False # 1 n'est pas un nombre premier
    return les_premiers

def filtre(les_premiers, prem):
    """
    Affecte à False les cases de les_premiers dont le numéro est un multiple de prem
    """
    num = prem * 2
    while num <= len(les_premiers):
        les_premiers[num - 1] = False
        num += prem

def affiche(les_premiers, val_max):
    """
    Affiche les nombres premiers <= à val_max sur une seule ligne
    """
    print(f"Les nombres premiers inférieurs ou égaux à {val_max} sont : ", end="")
    for idx, est_premier in enumerate(les_premiers):
        if est_premier:
            print(idx + 1, end=" ")
    print()

def main():
    """
    Programme principal
    """
    try:
        val_max = int(input("Entrez la valeur maximale : "))
        if val_max < 2:
            raise ValueError
    except ValueError:
        print("Erreur : la valeur limite doit être un entier supérieur ou égal à 2 !")
        return
    les_premiers = init_tab(val_max)
    for num in range(2, floor(sqrt(val_max)) + 1):
        if les_premiers[num - 1]:
            filtre(les_premiers, num)
    affiche(les_premiers, val_max)

if __name__ == "__main__":
    main()

Compression / décompression d'images en noir et blanc

On va travailler dans cet exercice avec des images au format Portable BitMap file format (PBM) qui ressemble beaucoup au format PGM qu'on a vu en TP, la différence étant que PBM concerne des images monochromes en noir et blanc, alors que PGM permet de gérer des images en niveaux de gris.

L'avantage de ces formats (et de leur grand frère PPM pour les images en couleurs sur 16 bits) est que l'image est stockée dans un fichier texte très facile à interpréter et donc facilement portable d'un système à un autre. L'inconvénient majeur est que stocker des pixels sous la forme de caractères n'est vraiment pas optimal en termes d'espace disque et mémoire et engendre des fichiers de très grandes tailles même pour des images modestes.

On va donc implanter un algorithme de compression des images basé sur un codage par longueur de plage (Run-Length Encoding (RLE) en anglais) dont le principe est tout simplement de factoriser les suites de pixels égaux en comptant leurs nombres d'occurrences consécutives. Par exemple, si un fichier texte contient la suite de caractères aaaaaaaabbcccccaaa, on peut le compresser simplement en 8a2b4c3a. Évidemment, ce type de codage est d'autant plus efficace que le fichier contient de grandes plages de valeurs égales, ce qui sera vraisemblablement souvent le cas pour des images en noir et blanc.

Le format PBM

On donne un exemple d'une image PBM (téléchargeable en cliquant sur ce lien) que vous pouvez ouvrir en tapant eog image.pbm dans un terminal ou en double-cliquant dessus dans le gestionnaire de fichier. Vous noterez au passage le style très seventies de cette image, qui ne nuit cependant pas du tout à la puissance de son message !

On fournit aussi une petite image représentant un E majuscule (téléchargeable en cliquant sur ce lien) pour vous permettre de comprendre le format, et aussi de tester votre programme sur un petit exemple lisible.

Si vous ouvrez l'image dans un éditeur de texte (par exemple code e_maj.pbm dans le terminal), vous comprendrez rapidement le format texte basique utilisé :

• la première ligne contient la chaîne "P1" qui indique qu'il s'agit d'une image PBM (magic number) ;
• la deuxième ligne contient la largeur puis la hauteur de l'image, en nombre de points, sous la forme de deux entiers séparés par un ou plusieurs caractères d'espacement (espace ou tabulation) ;
• le reste du fichier contient les couleurs des points de l'image (0 représente du blanc et 1 représente du noir), potentiellement séparés par (zéro ou) un ou plusieurs caractères d'espacement (espace ou tabulation) ou retours à la ligne : tous les séparateurs sont facultatifs et ignorés.

On vous donne également une version simplifiée de l'image du E majuscule (téléchargeable en cliquant sur ce lien) qui ne contient aucun séparateur superflu, afin de vous permettre d'écrire et tester une version simplifiée de votre programme si vous le souhaitez.

Lorsque les images sont très larges, il est recommandé d'aller à la ligne au bout de 70 caractères, ce qui ne change rien au contenu de l'image : c'est le cas pour le fichier image.pbm.

Le format compressé

Une image PBM compressée sera également un fichier texte, sous le format suivant :

• la première ligne contiendra la largeur puis la hauteur de l'image, en nombre de points, sous la forme de deux entiers séparés par un espace ;
• chacune des lignes suivantes contiendra un entier naturel correspondant au nombre de répétitions de la couleur courante, en supposant qu'on démarre avec du blanc.

Par exemple, le fichier :

32 16
14
7
23
76
...

décrit une image 32x16 contenant 14 points blancs, puis 7 points noirs, puis 23 points blancs, puis 76 points noirs, etc.

Et le fichier :

48 32
0
14
7
23
76
...

décrit une image 48x32 contenant 0 point blanc, puis 14 points noirs, puis 7 points blancs, puis 23 points noirs, puis 76 points blancs, etc. On voit donc comment gérer facilement le cas des images commençant par du noir.

Travail demandé

Vous devez écrire un programme rleimg.py prenant un fichier en paramètre sur la ligne de commande et capable de compresser ou décompresser l'image PBM qu'il contient. On s'attend à ce que le programme puisse être appelé selon le schéma d'usage suivant : ./rleimg.py (-c ou -d) fichier_source où :

• le premier paramètre dira si on doit compresser (-c) ou décompresser (-d) le fichier ;
• le deuxième paramètre sera tout simplement le nom du fichier source.

On ne détaille pas précisément comment vous devez implanter votre programme, mais on s'attend à ce que vous respectiez les directives ci-dessous.

Vous ne devez lire qu'une seule fois le fichier source et compter à la volée les nombres de répétitions (pour la compression) ou générer à la volée les points (pour la décompression). Vous utiliserez un tableau dynamique comme mémoire tampon pour la compression afin de permettre la vérification des nombres de répétitions (comme demandé ci-dessous), mais pas pour la décompression qui peut se faire en une seule passe sans stockage intermédiaire des données.

On s'attend à ce que vous implantiez des vérifications d'intégrité raisonnables dans votre code, et notamment :

• vous devez vérifier que les paramètres passés sur la ligne de commande respectent bien le schéma d'usage détaillé plus haut (c.-à-d. vérifier que le premier paramètre est bien -c ou -d) et afficher un message approprié puis terminer proprement le programme si ce n'est pas le cas ;
• pour la compression, vous devez vérifier (et là encore terminer le programme avec un message d'erreur sinon) :
  • que la première ligne du fichier source contient bien la chaîne "P1" ;
  • que le fichier source contient bien $largeur \times hauteur$ points ;
  • que la somme des nombres de répétitions calculée à l'issue de la compression est bien égale au nombre de points dans le fichier source (cette vérification servira en fait à détecter des erreurs dans votre code) ;
• pour la décompression, vous pouvez partir du principe que le fichier en entrée a été produit correctement pour essayer de générer le résultat le plus efficacement possible.

N'hésitez pas à utiliser des exceptions pour gérer proprement les cas d'erreur.

Votre programme devra bien évidemment être découpé en sous-fonctions, que l'on vous laisse libre de définir comme cela vous parait le plus pertinent pour factoriser autant de possible le code. On attend bien sûr que tout soit commenté de façon appropriée, avec notamment la nature et le rôle des paramètres de vos fonctions, et ce qu'elles renvoient.

Le résultat de l'exécution du programme sur un fichier source sera envoyé directement sur la sortie standard (stdout) à l'aide de la fonction print : vous pourrez générer un fichier en redirigeant la sortie comme on vous l'a appris en Unix, par exemple en exécutant ./rleimg.py -c image.pbm > resultat.rle.

Si vous voulez comparer directement le résultat d'une compression + décompression avec le fichier image.pbm, il vous faudra fractionner les lignes générées tous les 70 caractères, ce que vous pouvez soit implanter directement dans votre code, soit réaliser a-posteriori en utilisant la commande Unix fold qui fait exactement ça : ./rleimg.py -d resultat.rle | fold -w 70 > resultat.pbm. Vous pourrez alors utiliser la commande diff image.pbm resultat.pbm classique pour vérifier que les deux fichiers sont égaux.

On rappelle l'existence de la méthode split (dont la documentation est accessible en cliquant sur ce lien) qui devrait vous faciliter la vie pour analyser le fichier source. La documentation du module sys ainsi que celle concernant les entrées-sorties en Python vous seront vraisemblablement utiles.

Correction

Cliquez ici pour révéler la correction.

#!/usr/bin/env python3
"""
  Compression / décompression d'une image PBM
"""

import sys

MAGIC = "P1\n"

def usage(args):
    """
      Analyse de la ligne de commande
    """
    if  len(args) == 3:
        if args[1] == "-c":
            return True
        if args[1] == "-d":
            return False
    print(f"usage : {args[0]} (-c ou -d) fichier_source")
    sys.exit(1)

def inv(etat):
    """
      Renvoie '0' ssi etat vaut '1' et '1' sinon
    """
    return '1' if etat == '0' else '0'

def traite_car(car, etat, nbr, tampon, cpt):
    """
      Traite un caractère :
        - en mettant à jour l'état et le nbr de répétitions ;
        - en accumulant éventuellement un nbr de répétition dans le tampon ;
        - en incrémentant le cpt de caractères si on a bien lu un point.
    """
    if car == etat:
        nbr += 1
        cpt += 1
    elif car == inv(etat):
        tampon.append(nbr)
        etat = inv(etat)
        nbr = 1
        cpt += 1
    else:
        pass # on ignore tous les autres caractères
    return etat, nbr, cpt

def verifie_dimensions(larg, haut, tampon):
    """
      Verifie qu'il y a bien autant de "points" dans le tampon que larg * haut
      Sinon : c'est une erreur dans notre code, on utilise donc une assertion pour vérifier
    """
    tot = larg * haut
    for nbr in tampon:
        tot -= nbr
    assert tot == 0, "la somme des répétitions est différente de largeur x hauteur !"

def compresse(fich):
    """
      Compresse le fich en écrivant le résultat sur la sortie standard
      On gère les erreurs dans le fichier source via des ValueError
    """
    tampon = []
    etat = '0'
    nbr = 0
    cpt = 0
    with open(fich, "r", encoding="utf-8") as src:
        if src.readline() != MAGIC:
            raise ValueError(f"{fich} n'est pas un fichier PBM !")
        try:
            larg, haut = (int(dim) for dim in src.readline().split())
        except ValueError as exc:
            raise ValueError("erreur lors de la lecture des dimensions de l'image !") from exc
        print(larg, haut)
        for ligne in src:
            for car in ligne:
                etat, nbr, cpt  = traite_car(car, etat, nbr, tampon, cpt)
        tampon.append(nbr)
    if cpt != larg * haut:
        raise ValueError("le nombre de points dans le fichier est incohérent avec les dimensions !")
    verifie_dimensions(larg, haut, tampon)
    for val in tampon:
        print(val)

def decompresse(fich):
    """
      Décompresse le fich en écrivant le résultat sur la sortie standard
      On considère que le fichier source est bien formé (énoncé)
    """
    etat = '0'
    print(MAGIC, end="")
    with open(fich, "r", encoding="utf-8") as src:
        larg, haut = src.readline().split()
        print(larg, haut)
        for ligne in src:
            for _ in range(int(ligne[:-1])):
                print(etat, end="")
            etat = inv(etat)
    print()

def main():
    """
      Programme principal
    """
    if usage(sys.argv):
        compresse(sys.argv[2])
    else:
        decompresse(sys.argv[2])

if __name__ == "__main__":
    main()