2021/2022-s1

L'épreuve dure 1h30.

Elle se déroule en mode examen, pour lequel l'accès au web est bloqué, excepté les sites suivants :

• le site de BPI (https://bpi-etu.pages.ensimag.fr/) sur lequel vous vous trouvez actuellement. Vous y trouverez le contenu habituel (CMs, sujets et corrigés de TD/TP avec vidéos volontairement non disponibles) ;
• le site officiel de la documentation python (https://docs.python.org/3.8/) ;
• un site de traduction pour les élèves pour qui le français n'est pas la langue maternelle (https://www.deepl.com/fr/translator).

Cet examen se compose de deux exercices indépendants.

Le deuxième exercice est volontairement long. Votre objectif premier ne doit pas être de tout faire absolument, mais d'écrire du code fonctionnel et propre pour les fonctions que vous aurez le temps d'implémenter.

Vous devez travailler directement sur les fichiers python fournis et présents dans le dossier exam se trouvant sur le bureau de votre session d'examen.

Vous devez sauvegarder votre travail, toutes les 15 minutes environ, en cliquant sur ENVOYER se trouvant également sur le bureau.

Enfin, à la fin de l'examen il faut cliquer sur ENVOYER/TERMINER, toujours sur le bureau, et ne surtout pas éteindre la machine à la main en appuyant sur le bouton de mise/arrêt sous tension.

Le barème est donné à titre indicatif.

Les fichiers à compléter pour chacun des deux exercices sont les deux suivants:

• rangemaison.py est disponible ici
• koch.py est disponible ici

Exercice 1 : Range Maison (6 points)

Description du problème

Premier entretien d'embauche de ma vie, le représentant technique présent me demande "vous qui êtes un expert en algorithmique et en python, comment implémenteriez-vous le concept de range fourni en standard, s'il ne l'était pas ?"

Comme j'ai du recul après mes trois années de formation à l'Ensimag, je demande des précisions quant à la spécification du problème. Voici la tâche précise qui m'est finalement confiée.

Représentation d'un rangemaison

Je suis libre de représenter un range maison comme bon me semble (structure de données de mon choix) sauf bien entendu en utilisant le type standard renvoyé par la fonction range. Autrement dit, je n'ai pas le droit d'utiliser la fonction range (qui techniquement n'est pas une fonction mais un constructeur).

Opérations sur un rangemaison

Les trois opérations principales sur un rangemaison, que je dois implémenter, sont les suivantes :

• création à partir des paramètres start, stop et step. Ces trois paramètres peuvent être négatifs.
• récupération du ième élément, sachant que le premier élément du rangemaison est l'élément 0 ;
• récupération d'un itérateur sur tous les éléments.

Travail à réaliser

Il vous est demandé de compléter le squelette du module rangemaison.py qui se trouve dans le dossier exam se trouvant lui même sur le bureau de votre session d'examen. Ce module doit également être un programme exécutable qui appelle la fonction test_rangemaison. Le squelette de ce module est également donné ci-dessous. Le travail à réaliser est symbolisé par #TODO suivi de ... dans le code.

Il est aussi demandé de justifier vos choix, notamment en terme de complexité temporelle et spatiale. Ces justifications sont à donner dans les commentaires des fonctions que vous modifierez donc.

Correction

Correction

Cliquez ici pour révéler la correction.

Voici un exemple de correction utilisant un namedtuple pour représenter un range. Comme dans l'implémentation standard de python, on implémente un range simplement en stockant ses trois paramètres, à savoir start, stop et step.

Ces informations sont suffisantes pour avoir des accès indicés en temps constant et un coût constant en mémoire quelque soit la taille du range.

#!/usr/bin/env python3

"""Module implémentant notre range maison."""
import collections

RangeMaison = collections.namedtuple("RangeMaison", ["start", "stop", "step"])


def test_range():
    """Teste les deux fonctions ci-dessous."""
    range1 = create_range(0, 5, 1)
    print(get_ith(range1, 2))
    for elem in get_elements(range1):
        print(elem, end=" ")
    print()
    range2 = create_range(10, 0, -2)
    print(get_ith(range2, 2))
    for elem in get_elements(range2):
        print(elem, end=" ")
    print()
    range3 = create_range(7, 5, 1)
    for elem in get_elements(range3):
        print(elem)


def create_range(start, stop, step):
    """Renvoie un nouveau range dont le type dépend de la structure de
    données choisie.

    Ce range démarre à start (inclus), termine à stop (exclus) et avance
    de step unités à chaque élément. Chacun des trois paramètre peut
    ếtre un nombre négatif.

    Par exemple create_range(0, 5, 1) renvoie un range qui permettra
    d'itérer sur les nombres `0 1 2 3 4` en utilisant la fonction
    get_elements.

    pré-conditions :
    - step != 0

    Autrement dit, dans cet exercice on ne manipulera que des ranges avec
    des steps différents de 0.
    """
    return RangeMaison(start, stop, step)


def get_ith(rangemaison, i):
    """Renvoie le ième élément de rangemaison.

    Le premier élément est l'élément 0.

    pré-conditions :
    - rangemaison n'est pas None.
    - il y a au moins i+1 éléments dans rangemaison.

    Autrement dit, pas besoin de vérifier quoi que ce soit dans la fonction.
    """
    return rangemaison.start + (rangemaison.step * i)


def get_elements(rangemaison):
    """Renvoie un itérateur sur tous les éléments de rangemaison.

    pré-conditions :
    - rangemaison n'est pas None.
    """
    ith = rangemaison.start
    while True:
        stop = (
            ith >= rangemaison.stop if rangemaison.step > 0 else ith <= rangemaison.stop
        )
        if stop:
            break
        yield ith
        ith += rangemaison.step


# Ce module doit également être un programme exécutable
# qui appelle la fonction `test_range`.
if __name__ == "main":
    test_range()
# END_CORRECTION

Exercice 2 : C'est l'hiver, il neige, il faut chaîner (14 points)

Description du problème

On s'intéresse ici à la génération et au tracé de flocons de Koch, de manière à générer des images ressemblant à celles de l'animation ci-dessous :

On part d'un ensemble de sommets formant un polygone. Le polygone initial est, ici, un triangle équilatéral. Une étape de Koch consiste alors à appliquer une transformation de Koch à chaque arête de ce polygone. Cette transformation consiste à découper l'arête en trois parties égales, et à remplacer la partie centrale par la pointe d'un triangle équilatéral, comme illustré par la figure ci-dessous, qui représente le polygone à l'étape 0 (à gauche) et à l'étape 1 (à droite).

Sur cette figure, une transformation de koch est appliquée à chacune des arêtes du triangle équilatéral initial. En particulier, l'application de la transformation de Koch à l'arête délimitée par les sommets s_a et s_e engendre la création des sommets intermédiaires s_b, s_c et s_d.

L'objectif de l'exercice est d'écrire un programme qui génère une image SVG représentant un flocon de Koch après un certain nombre d'étapes donné en paramètre.

Description des structures de données

Un sommet du polygone sera représenté par une instance de la classe Sommet que nous allons implémenter.

Le polygone lui-même sera représenté par l'ensemble des sommets du polygone sous la forme d'un chaînage circulaire de Sommet. Nous n'utiliserons pas de classe Polygone pour représenter le polygone, celui-ci sera simplement représenté par le Sommet en tête de chaînage. Il vous est donc interdit d'utiliser les tableaux dynamiques de python, mal nommés list.

Dans ce chaînage, les points seront ordonnés dans le sens du dessin ci-dessus. Par exemple, le sommet s_a sera suivi dans le chaînage de s_b, lui-même suivi par s_c, et ainsi de suite.

Travail à réaliser

Le point de départ de cet exercice se trouve dans le fichier koch.py disponible dans le dossier exam sur le bureau de votre session d'examen. Cette section présente l'ensemble des fonctionnalités à implémenter dans ce fichier.

1 Chaînage

1.1 Constructeurs

Implémentez le constructeur de la classe Sommet. Une ébauche, que vous devez donc compléter, est donnée dans le fichier koch.py.

Pour pouvoir utiliser le module svg fourni quand viendra le moment du dessin, un Sommet devra obligatoirement contenir :

• un attribut appelé x représentant l'abscisse du sommet dans le plan ;
• un attribut appelé y représentant l'ordonnée du sommet dans le plan.

Un polygone sera représenté par une liste chaînée circulaire de Sommet. Implémentez ensuite la fonction suivante :

def cree_polygone_initial()

Cette fonction retourne le polygone représentant le triangle équilatéral initial, c'est à dire comme indiqué plus haut, le sommet en tête de chaînage. On considère qu'à l'étape 0, le polygone ne contient que les Sommet du triangle équilatéral initial, qui sont déjà instanciés dans le squelette de code fourni (s_a, s_b et s_c dans le squelette de code de la fonction creer_polygone_initial()).

1.2 Insertion dans le chaînage

Implémentez la fonction suivante :

def insere_apres(prec, sommet)

Cette fonction insère le Sommet sommet à la suite du Sommet prec.

1.3 Itérateur sur les arêtes

Implémentez la fonction génératrice suivante que vous utiliserez dans les questions suivantes quand cela vous semble pertinent :

def recupere_couples_sommets(polygone, distance=1)

Cette fonction génératrice retourne un itérateur permettant de "faire le tour" du polygone arête par arête, c'est-à-dire permettant d'itérer sur les couples de sommets contenus dans polygone.

Par exemple, si polygone contient les sommets s_a, s_b, s_c (dans cet ordre), alors cet itérateur permettra d'itérer sur le couple (s_a, s_b), puis (s_b, s_c) et enfin (s_c, s_a).

Le paramètre optionnel distance représente l'écart dans le chaînage entre les sommets des couples retournés par l'itérateur. Il sera ignoré pour cette question (on considère qu'il vaut toujours 1, ce qui signifie que les sommets des couples retournés par l'itérateur sont voisins dans le chaÎnage), et sera traité plus tard.

2 Création du flocon

2.1 Une fonction auxiliaire bien utile

Implémentez la fonction suivante :

def applique_transformation(s_a, s_e)

Cette fonction applique une transformation de Koch sur l'arête délimitée par les sommets s_a et s_e. Elle doit donc :

• créer les sommets intermédiaires s_b, s_c, s_d : pour ce faire, on utilisera la fonction calcule_coordonnees(), qui retourne les coordonnées des points à créer (se référer à la docstring de la fonction dans le fichier koch.py pour plus d'informations) ;
• les chaîner ensemble et avec les sommets s_a et s_e, de manière à obtenir le chaînage s_a -> s_b -> s_c -> s_d -> s_e.

2.2 Solution récursive

Pour concevoir votre solution récursive, commencez par implémenter la fonction récursive suivante :

def applique_transformations_rec(s_a, s_e, profondeur)

Cette fonction applique profondeur transformations de Koch récursivement, en partant du segment [s_a; s_e].

Implémentez ensuite la fonction suivante :

def cree_flocon_koch_v1(polygone, nb_etapes)

Cette fonction appelle la fonction récursive applique_transformations_rec() sur chaque arête du polygone passé en paramètre afin d'obtenir au final le polygone issu de nb_etapes étapes de Koch.

2.3 Solution itérative

Vous devez maintenant réaliser une version itérative de l'algorithme de création de flocon de Koch. Pour cela, implémentez la fonction suivante :

def cree_flocon_koch_v2(polygone, nb_etapes)

Cette fonction applique une transformation de Koch à la première arête du polygone passé en paramètre, puis passe à l'arête suivante, jusqu'à les traiter toutes.

Cette opération est ensuite répétée jusqu'à l'obtention du polygone après nb_etapes étapes de Koch.

3 Écriture du polygone dans un fichier SVG

Implémentez la fonction suivante :

def ecrit_fichier_svg(nom_fichier, polygone, nb_etapes, dump_all_steps=False)

Cette fonction écrit dans le fichier nommé nom_fichier les balises SVG permettant de représenter le polygone passé en paramètre. Le paramètre dump_all_steps sera ignoré pour le moment. Le paramètre nb_etapes correspond au nombre d'étapes appliquées précédemment sur le polygone passé en paramètre.

Vous devrez utiliser le module svg.py disponible dans le dossier exam sur le bureau de votre session d'examen. Attention, il est un peu différent de celui utilisé en TP, à vous de le parcourir et d'identifier les fonctionnalités dont vous aurez besoin.

4 Génération des images intermédiaires

À partir du polygone final, on souhaite maintenant générer une image après chaque étape. L'idée ici est de parvenir à n'itérer que sur les sommets du polygone correspondant à l'étape que l'on souhaite écrire dans le fichier.

Pour ce faire, commencez par modifier la fonction génératrice recupere_couples_sommets(polygone, distance=1) pour qu'elle renvoie un itérateur faisant le tour du polygone en sautant distance sommets à chaque fois, c'est-à-dire retourne un itérateur de couples de sommets espacés de distance. Par exemple, si poly contient les sommets A, B, C, D, E et F, un appel à recupere_couples_sommets(poly, 2) retournera un itérateur itérant sur les couples (A, C), (C, E), (E, A).

Ensuite, modifiez la fonction ecrit_fichier_svg(nom_fichier, polygone, nb_etapes, dump_all_steps=False) pour qu'elle puisse générer un fichier par étape de Koch si le paramètre optionnel dump_all_steps vaut True. Dans ce cas, si nom_fichier vaut par exemple flocon.svg et que polygone contient par exemple les sommets engendrés par l'application de 3 étapes de Koch, alors ecrit_fichier_svg(nom_fichier, polygone, dump_all_steps) créera les fichiers 0-flocon.svg, 1-flocon.svg, 2-flocon.svg et 3-flocon.svg, chacun contenant la représentation SVG du polygone après le nombre d'étapes de Koch correspondant. Vous utiliserez le paramètre distance de la fonction recupere_couples_sommets(polygone, distance=1).

5 Pour terminer

Indiquez dans la docstring du module koch.py quel est le nombre de points dans le polygone en fonction du nombre d'étapes nbe ?

Correction globale

Cliquez ici pour révéler la correction.

Voici une proposition de correction.

#! /usr/bin/env python3

"""Dessin d'un joli flocon de Koch. C'est l'hiver."""

import math
import sys
import svg


COS_60 = math.cos(math.pi / 3)
SIN_60 = math.sin(math.pi / 3)
LINE_COLOR = "purple"


class Sommet:
    """Classe représentant un point dans le plan.

    Attributs :
        - x représente l'abscisse du Sommet ;
        - y représente l'ordonnée du Sommet ;
        - suiv permet de chainer des Sommet entre eux.
    """

    # On dit à pylint qu'ON SAIT que x et y sont des
    # noms d'attributs très raisonnables ici.
    # pylint: disable=invalid-name
    def __init__(self, coord_x, coord_y):
        self.x = coord_x
        self.y = coord_y
        self.suiv = None

    def __str__(self):
        """Pour débogguer.

        C'est important de pouvoir afficher un sommet
        avec print.
        """
        return f"({self.x}, {self.y})"


def cree_polygone_initial():
    """Retourne le polygone représentant le triangle équilatéral initial.

    Un polygone est représenté par une liste chainée circulaire de Sommet.

    Le polygone créé ici contient seulement les sommets du triangle initial qu'on
    a déjà instanciés pour vous (s_a, s_b, s_c). Trop sympas les profs de BPI !

    Retourne le polygone créé, c'est-à-dire comme indiqué en gras dans le sujet,
    le Sommet en tête de la liste chainée créée.
    """
    s_a = Sommet(200, 25)
    s_b = Sommet(50, 284.8)
    s_c = Sommet(350, 284.8)
    s_a.suiv = s_b
    s_b.suiv = s_c
    s_c.suiv = s_a

    return s_a


def insere_apres(prec, sommet):
    """Insère le sommet dans polygone après le sommet prec.

    paramètres :
    - prec : le Sommet après lequel on va insérer sommet ;
    - sommet : le Sommet à insérer après prec.

    pré-conditions :
    - prec et sommet ne sont pas None.
    """
    sommet.suiv = prec.suiv
    prec.suiv = sommet


def recupere_couples_sommets(polygone, distance=1):
    """Retourne un itérateur sur tous les couples de sommets avec un pas de distance.

    paramètres :
    - polygone : le polygone à parcourir (= le Sommet en tête du chainage) ;
    - distance : le nombre de liens qui séparent les Sommet du couple (dans
                 le chainage s_a -> s_b -> s_c -> s_d, les sommets s_a et s_d
                 sont à une distance de 3).

    pré-conditions :
    - distance est un diviseur du nombre de sommets dans polygone.
    """
    sommet = polygone
    suivant = None
    while suivant is not polygone:
        suivant = sommet.suiv
        count = 1
        while count < distance:
            suivant = suivant.suiv
            count += 1
        yield sommet, suivant
        sommet = suivant


def calcule_coordonnees(s_a, s_e):
    """Calcule les coordonnées des sommets à ajouter entre s_a et s_e.

    paramètres :
    - s_a et s_e sont des Sommet et représentent les sommets du segment
    sur lequel on applique une transformation de Koch.

    Retourne les coordonnées des 3 nouveaux sommets à insérer entre s_a et s_e
    sous la forme d'un triplet de trois couples :
    ((x_b, y_b), (x_c, y_c), (x_d, y_d))
    """
    x_b = s_a.x + (s_e.x - s_a.x) / 3
    y_b = s_a.y + (s_e.y - s_a.y) / 3
    x_d = s_a.x + 2 * (s_e.x - s_a.x) / 3
    y_d = s_a.y + 2 * (s_e.y - s_a.y) / 3
    x_c = (x_b + x_d) * COS_60 - (y_d - y_b) * SIN_60
    y_c = (y_b + y_d) * COS_60 + (x_d - x_b) * SIN_60

    return (x_b, y_b), (x_c, y_c), (x_d, y_d)


def applique_transformation(s_a, s_e):
    """Applique une transformation de Koch sur l'arête [s_a; s_e].

    Cette fonction applique une transformation de Koch sur l'arête délimitée
    par les sommets s_a et s_e. Elle doit donc :
        - créer les sommets intermédiaires s_b, s_c, s_d : pour ce faire,
          on utilisera la fonction calcule_coordonnees(), qui retourne les
          coordonnées des points à créer (se référer à la docstring de la
          fonction pour plus d'informations) ;
        - les chaîner ensemble et avec les sommets s_a et s_e, de manière à obtenir
          le chaînage s_a -> s_b -> s_c -> s_d -> s_e.

    paramètres :
    - s_a, s_e : les Sommet délimitant l'arête sur laquelle appliquer la
    transformation de Koch.
    """

    # On calcule les coordonnées des sommets à ajouter.
    coords = calcule_coordonnees(s_a, s_e)

    # On crée ces sommets...
    s_b = Sommet(*coords[0])
    s_c = Sommet(*coords[1])
    s_d = Sommet(*coords[2])

    # Puis on les insère au bon endroit dans le chainage.
    # On aura donc 4 nouvelles arêtes :
    # [s_a; s_b], [s_b; s_c], [s_c; s_d] et [s_d; s_e]
    insere_apres(s_a, s_b)
    insere_apres(s_b, s_c)
    insere_apres(s_c, s_d)


def applique_transformations_rec(s_a, s_e, profondeur):
    """Applique profondeur transformations de Koch récursivement, en partant du segment [s_a; s_e].

    paramètres :
    - s_a, s_e : les Sommets entre lesquels appliquer la transformation de Koch ;
    - profondeur : la profondeur maximale de récursion.
    """
    # Condition d'arrêt
    if profondeur == 0:
        return

    # On applique la subdivision à l'arête [s_a; s_e]
    applique_transformation(s_a, s_e)
    s_b = s_a.suiv
    s_c = s_b.suiv
    s_d = s_c.suiv

    # Enfin, on rappelle cette fonction récursivement
    # pour créer les sommets intermédiaires de ces 4
    # nouvelles arêtes.
    applique_transformations_rec(s_a, s_b, profondeur - 1)
    applique_transformations_rec(s_b, s_c, profondeur - 1)
    applique_transformations_rec(s_c, s_d, profondeur - 1)
    applique_transformations_rec(s_d, s_e, profondeur - 1)


def cree_flocon_koch_v1(polygone, nb_etapes):
    """Version récursive de l'algorithme de création de flocon de Koch.

    Cette version appelle la procédure récursive applique_transformation_rec
    sur chaque arête du polygone passé en paramètre.

    Le flocon n'est donc pas construit étapes par étapes tel que décrit dans
    le sujet, mais arête par arête.

    paramètres :
    - polygone : le polygone sur lequel appliquer les nb_etapes étapes
                 de Koch (= le Sommet en tête du chainage) ;
    - nb_etapes : le nombre d'étapes de Koch à appliquer au polygone
                  passé en paramètre.
    """
    for s_1, s_2 in recupere_couples_sommets(polygone):
        applique_transformations_rec(s_1, s_2, nb_etapes)


def cree_flocon_koch_v2(polygone, nb_etapes):
    """Version itérative de l'algorithme de création de flocon de Koch.

    Cette version applique une transformation de Koch à la première arête du
    polygone passé en paramètre, puis passe à l'arête suivante, jusqu'à les
    traiter toutes.

    Cette opération est ensuite répétée jusqu'à l'obtention du polygone après
    nb_etapes étapes de Koch.

    Le flocon est donc dans cette version itérative construit étape par étape
    tel que décrit dans le sujet.

    paramètres :
    - polygone : le polygone sur lequel appliquer les nb_etapes étapes de
                 transformation de Koch (= le Sommet en tête du chainage) ;
    - nb_etapes : le nombre d'étapes de Koch à appliquer au polygone passé
                  en paramètre.
    """
    for _ in range(nb_etapes):
        for s_a, s_e in recupere_couples_sommets(polygone):
            applique_transformation(s_a, s_e)


def ecrit_fichier_svg(nom_fichier, polygone, nb_etapes, dump_all_steps=False):
    """Génère une ou plusieurs images SVG représentant le polygone donné.

    Paramètres :
    - nom_fichier : le chemin complet vers le fichier de sortie SVG ;
    - polygone : le polygone à parcourir (= le Sommet en tête du chainage) ;
    - nb_etapes : le nombre d'étapes appliquées au polygone passé en paramètre ;
    - dump_all_steps : si True, écrit un fichier par étape de l'algorithme de Koch.
    """
    def dump_flocon(nom_fichier, polygone, etape=0):
        """Génère un fichier SVG représentant le polygone à l'étape etape."""
        with open(nom_fichier, "w") as outfile:
            # Ecriture de l'entête SVG
            print(svg.genere_balise_debut_image(400, 400), file=outfile)

            # Ecriture dans le fichier
            for s_1, s_2 in recupere_couples_sommets(polygone, 4**etape):
                print(svg.genere_segment(s_1, s_2, LINE_COLOR), file=outfile)

            # Ecriture de la balise de fin SVG
            print(svg.genere_balise_fin_image(), file=outfile)

    if dump_all_steps:
        for etape in range(nb_etapes + 1):
            nom_f = f"{nb_etapes - etape}_{nom_fichier}"
            dump_flocon(nom_f, polygone, etape)
    else:
        dump_flocon(nom_fichier, polygone)


def affiche_usage():
    """Fonction d'usage du programme koch.py.

    Il est d'usage que la fonction d'usage d'un programme
    rappelle poliment à l'utilisateur comment lancer le
    programme.
    """
    print(*sys.argv, " ? Sérieux ? N'importe quoi !")
    print("C'est comme ça qu'on utilise ce programme, enfin...")
    print(main.__doc__)


def main():
    """Usage :
    ./koch.py profondeur fichier.svg

    avec :
    - nb_etapes le nombre d'étapes à appliquer sur le triangle initial
    - fichier.svg le nom du fichier de sortie SVG. Ce nom de fichier sera
    utilisé pour générer un fichier par étape
    (0-fichier.svg, 1-fichier.svg, ...).
    """
    args = sys.argv
    if len(args) < 2:
        affiche_usage()
        sys.exit(1)

    nb_etapes = int(sys.argv[1])
    outfile_name = sys.argv[2]

    # version récursive
    polygone = cree_polygone_initial()
    cree_flocon_koch_v1(polygone, nb_etapes)
    ecrit_fichier_svg(f"rec_{outfile_name}", polygone, nb_etapes)

    # version itérative
    polygone = cree_polygone_initial()
    cree_flocon_koch_v2(polygone, nb_etapes)
    ecrit_fichier_svg(f"iter_{outfile_name}", polygone, nb_etapes)

    # en créant un fichier par étape
    ecrit_fichier_svg(outfile_name, polygone, nb_etapes, dump_all_steps=True)


if __name__ == "__main__":
    main()

Pour la dernière question, le nombre de points est le suivant :

$3 + 3\times(3\times\sum{_{i=0}^{nbe}} 4^{i}) = 3\times4^{nbe}$