Agrégation informatique externe 2023, épreuve 3, option ingénierie informatiqueSujet et rapport du jury

AGRÉGATION
CONCOURS EXTERNE

CONCEPTION PRÉLIMINAIRE D'UN SYSTÈME, D'UN PROCÉDÉ OU D'UNE ORGANISATION

INFORMATION AUX CANDIDATS

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

• -d'un dossier questionnement de la page 1 à la page 14 ;
  • -présentation de la page 2 à la page 3 ;
  • -partie 1 de la page 4 à la page 7 ;
  • -partie 2 de la page 8 à la page 11 ;
  • -partie 3 de la page 12 à la page 14 ;
• -d'un dossier technique (DT) de la page 14 à la page 31 ;
• -d'un dossier réponse (DR) de la page 32 à la page 37.

• -les trois parties du questionnement sont indépendantes ;
• -un parcours attentif de l'ensemble du document est conseillé avant de composer ;
• -la présentation des programmes doit respecter les mots clés du langage cible ainsi que l'indentation des structures algorithmiques ;
• -les réponses doivent être présentées avec clarté, rigueur et concision.

Présentation

• -adaptés aux Personnes à Mobilité Réduite (PMR dans la suite) ;
• -véhicules de tourisme non-adaptés aux PMR.

• -réduire la congestion routière en permettant le partage de trajets et l'augmentation des taux de remplissage des véhicules en circulation ;
• -favoriser l'intermodalité et l'usage des transports collectifs, puisque le service de Flex-e-Trans peut servir comme un service de rabattement vers les transports en commun ;
• -résoudre le problème du premier et du dernier kilomètre, qui sont parmi les raisons de la préférence de la voiture privée ;
• -améliorer l'accessibilité à moindre coût pour les PMR.

• -une application Web ou mobile destinée aux passagers ;
• -une application Web destinée aux administrateurs du système ;
• -une application serveur permettant la communication avec les véhicules, l'optimisation des missions des véhicules, l'intégration des nouvelles demandes en temps-réel et la supervision des missions en cours.

• -une flotte de véhicules de deux types (adaptés aux PMR ou non) ;
• -un dépôt pouvant contenir l'ensemble de la flotte, et équipé de bornes de recharge permettant de recharger en charge rapide un quart de la flotte de véhicules simultanément.

• -l'adresse d'origine et l'adresse de destination ;
• -les informations sur le passager (PMR ou non) ;

• -l'horaire de départ au plus tôt à l'adresse d'origine et l'horaire d'arrivée au plus tard à l'adresse de destination.

Figure 1: Système Flex-e-Trans

• -la partie 1 est relative à la conception du système d'information et au mode d'accès par code QR aux véhicules ;
• -la partie 2 traite de certaines parties matérielles et des protocoles réseau des unités mobile ;
• -la partie 3 traite de l'algorithme d'optimisation des missions des véhicules.

Partie 1 : Syst. d'information et accès véhicule

• -un point de départ, un point d'arrivée ;
• -des horaires limites pour le départ (horaire au plus tôt) et pour l'arrivée (horaire au plus tard) ;
• -le fait que le passager soit une personne à mobilité réduite ou non.

Sous-partie 1.1 : Modes de paiement et trajets

Figure 2: Schéma relationnel d'une partie du système d'information

• -un paiement par carte bleue (on doit stocker le numéro de la carte (16 chiffres), le nom du porteur (ce n'est pas nécessairement le nom du client), la date d'expiration (mois et année) et le cryptogramme de 3 chiffres (Card Validation Value, CVV) ;
• -un paiement par prélèvement bancaire (on doit alors stocker l'IBAN du compte bancaire du client qui est une série de 32 symboles alphanumériques).
• Q1.Proposer des modifications / des ajouts au schéma relationnel précédent (refaire un schéma similaire à celui de la figure 2) pour intégrer ces deux types de paiements possibles en prenant en compte les éléments suivants :
  • -Un client peut posséder plusieurs cartes bleues et / ou comptes pour prélèvement.
  • -Si deux personnes ont renseigné la même carte ou le même compte, alors les informations sont doublées dans le système d'information. Par exemple, si deux clients utilisent la même carte bleue, la carte en question sera stockée deux fois dans la base.

Accès à la base de données

• Q2.Donner la requête SQL (SELECT) qui permet de récupérer uniquement le nom et le prénom d'un client, connaissant son email : [email protected]
• Q3.Donner la requête SQL (SELECT) qui permet de récupérer (uniquement) tous les couples latitude / longitude des points de départs des trajets que John Smith (identifié par son email [email protected]) a déjà réalisé (les trajets planifiés ou en cours ne doivent donc pas être inclus).
• Q4.Donner la requête SQL (SELECT) qui permet de récupérer toutes les informations sur le prochain (au sens de l'horaire de départ) trajet planifié par un client, à partir de son email. La requête ne devra donc donner qu'une seule réponse au maximum, contenant exactement 6 colonnes : les coordonnées géographiques et les horaires des points de départ et d'arrivée.

• Q5.En s'inspirant de la méthode Database.get_hashed_password, donner le code de la méthode Database.get_client_name_from_email (prototype visible dans le DT2).

Authentification des clients

• Q6.Expliquer en 10 lignes maximum pourquoi les mots de passe sont hachés avant d'être stockés dans la base de données ?
• Q7.Expliquer en 10 lignes maximum pourquoi les mots de passe sont salés avant d'être hachés ?
• Q8.La méthode Database.store_password (voir DT2) reçoit en paramètres un email et une chaîne de caractères arbitraire (le mot de passe), et doit stocker le mot de passe salé et haché dans la base. Elle renvoie True si l'insertion de la nouvelle donnée s'est déroulé correctement et False sinon. Cette fonction utilise une fonction annexe du module outils, nommée hash_with_salt. Compléter le code de la méthode et de la fonction sur le document réponse DR1.
• Q9.Compléter sur le document DR2 la méthode Database.check_password qui indique en renvoyant un booléen si un couple login / mot de passe est valide ou non.

Sous-partie 1.2 : Génération du code QR

• -un utilisateur ne doit pas pouvoir forger un faux code QR, et prétendre ainsi qu'il a réservé un trajet ;
• -un utilisateur ne doit pas pouvoir modifier les horaires, lieux ou tout autre chose dans son code QR, sans que ce soit immédiatement décelable à la lecture du code ;
• -lorsque l'utilisateur se présente devant le véhicule, ce dernier doit être en mesure de vérifier que le code QR est correct, même s'il n'a aucun accès réseau, et ne peut pas joindre sa centrale.

• 1.Organiser les données selon un format binaire compact.
• 2.Calculer la signature numérique de la séquence d'octets obtenue.
• 3.Encoder en base 45 les données signées (séquence d'octets + signature).
• 4.Générer le code QR à partir de la chaîne contenant les données en base 45, préfixée par un entête qui permet d'identifier le type de code

• Q10.Dans le document réponse DR3 compléter la méthode de classe CourseClient.from_bytes qui réalise l'opération inverse.
• Q11.La fonction sign du module outils permet d'obtenir un bloc signé à partir d'un bloc de données. Dans la fonction sign, pourquoi la valeur de n est-elle comparée à 0xffff ?
• Q12.Sur le document réponse DR4, compléter la fonction check_sign du module outils qui prend en paramètre des données signées, et indique en renvoyant un booléen si la signature est valide.

• Q13.Sur le document réponse DR5, compléter la fonction base45_encode et les fonctions annexes utilisées.
• Q14.Écrire la méthode CourseClient.create_qr_code dont le prototype est donné dans le document DT2, qui renvoie l'image du code QR. Toutes les fonctions mentionnées dans le document DT2 sont utilisables.
• Q15.Écrire la méthode de classe CourseClient.read_qr_code dont le prototype est donné dans le document DT2. Cette méthode prend en paramètre l'image du code QR, et renvoie :
  • -None si le code QR n'est pas valide (signature erronée) ou n'est pas reconnu ;
  • -un objet de type CourseClient sinon.

Partie 2 : Équipement et communications

• -les stations sont mobiles, modifiant en continue la topologie du réseau ;
• -les couches basses de communication peuvent être très diverses (Bluetooth, Wifi, GSM...) ;
• -on trouve aussi une grande diversité dans les terminaux (véhicule lui-même, station de bord de route, smartphone, centrale...) et les applications (routage, régulation du traffic, conduite autonome, système d'appel d'urgence...).

Sous-partie 2.1 : Système eCall

• Q16.Le type d'une trame NMEA 0183 est donné par 3 caractères contenus dans la trame. Parmi les types présentés dans le document DT7, quel est celui qui sera utilisé pour récupérer la position du véhicule ?
• Q17.Quels sont les deux caractères manquants à la fin de la trame donnée ci-dessous ? Une table ASCII est donnée dans le document technique DT8.
  $GPGSA, A, 3, 06, 07, 16, 20, 14,,, 24,, 07,,, 2.5, 1.3,2.1*

typedef struct {
    float latitude, longitude;
    int heures, minutes;
    float secondes;
} position;

• Q18.L'objectif est maintenant, étant donnée une trame NMEA 0183 (chaîne de caractères), de l'analyser et de renvoyer une structure contenant les informations d'horodatage et de position. Une partie du code est donnée dans le document DR6. Compléter les différentes fonctions, dont la fonction C int get_position(char * nmea_frame, position * pos) qui prend en paramètres une trame NMEA 0183 et un pointeur vers une structure position, et remplit la structure avec les informations si la trame NMEA 0183 le permet. En cas de succès, la fonction devra renvoyer 1. Si la trame NMEA 0183 ne permet pas de connaître ces informations (si ce n'est pas le bon type de trame par exemple) ou si la trame contient une erreur (lecture impossible, checksum incorrect...), la fonction devra renvoyer 0. Il sera admis que si le checksum est correct, alors les différents éléments de la trame sont corrects : il sera par exemple inutile de vérifier que la latitude contient le bon nombre de chiffres.

Sous-partie 2.2 : Couche réseau et transports - GeoNetworking

• -GeoUnicast : on cible un destinataire avec son adresse (figure 3) ;
• -GeoBroadcast : on cible tous les nœuds d'une zone géographique délimitée (figure 4) ;
• -GeoAnycast : on cible un des nœuds d'une zone géographique délimitée ;
• -TSB (Topologically Scoped Broadcast): diffusion aux n plus proches voisins (figure 5).

Figure 3: Diffusion de type GeoUnicast

Figure 4: Diffusion de type GeoBroadcast

Figure 5: Diffusion de type TSB

Adressage GeoNetworking

• Q19.On donne le début d'une adresse en notation hexadécimale pointée : 15.0C.xx.xx.xx.xx.xx.xx
  Indiquer le type de station (véhicule ou bien unité de bord de route ? feu de signalisation, vélo, voiture...?), le caractère privé ou public de la station, ainsi que le nom du pays correspondant à la station.

Vecteurs de Position

• 1.une station peut informer les stations environnantes de sa position, en utilisant un Long Position Vector ou un Short Position Vector
• 2.une zone peut être ciblée, en donnant un point ou une aire géographique (possibilité offerte dans l'entête des trames GeoNetworking)

• Q20.Le champs TST propose un horodatage des données de position. Du fait du nombre de bits utilisés pour encoder ce champs, la valeur TST cycle et repasse régulièrement par la valeur 0. Avec quelle période, exprimée en jours, ce phénomène se produit-il ?

Trames GeoNetworking

• Q21.En supposant que l'unité est la seconde, si le champ LT de l'entête code un nombre entier sur un octet, quelle est la durée maximum représentable (vmax) et quelle est la plus petite durée non nulle représentable (vmin) ?

• -les 6 bits de poids fort de LT représentent un nombre entier nommé multiplieur
• -les 2 bits de poids faible de LT encodent la base :

• Q22.En utilisant ce codage, quelles sont les nouvelles valeurs de vmin et vmax ? Quels octets (donner des nombres entiers en base 10) permettent de représenter ces deux valeurs extrêmes ?

Algorithmes de routage

• - F(x, y) = 1 si M(x, y) = C
• - F(x, y) > 0 si M(x, y) appartient au disque ouvert de centre C et de rayon r
• - F(x, y) = 0 si M(x, y) appartient au cercle de centre C et de rayon r
• - F(x, y) < 0 si M(x, y) n'appartient pas au disque fermé de centre C et de rayon r

• Q24.Sur le document réponse DR7, sont représentés différents nœuds d'un réseau GeoNetworking. La distance entre chaque nœud est donnée par un tableau du document DR7. Une trame GeoBroadcast (figure 4) est émise depuis le nœud LPV, à destination d'une zone de rayon 3, centrée autour de A. Quel sera le trajet suivi par la trame pour atteindre le premier nœud destination si elle est routée en utilisant les algorithmes du document DT12, en supposant que le voisinage correspond à une distance de 4 ? Autrement dit, (i.IS_NEIGHBOUR) est vrai si le point i est à une distance inférieure ou égale à 4 du point considéré. Indiquer clairement la liste des nœuds par lesquels l'information transite et expliquer la construction du tracé.
• Q25.La solution obtenue avec les algorithmes du DT12 est-elle optimale en nombre de sauts ? Si ce n'est pas le cas, trouver un trajet optimal de LPV à sa destination.
• Q26.Dans le document DT12, l'algorithme nommé GF ALGORITHM est qualifié de glouton (greedy en anglais). Pour quelle raison (texte libre, moins de 10 lignes) ?
• Q27.Pour quelle(s) raison(s) (texte libre, moins de 10 lignes) le protocole IP n'est-il pas suffisant pour assurer les services de la couche réseau et en quoi le protocole GeoNetworking permet-il de régler ce problème ?

Partie 3 : Système d'optimisation des missions

• -minimiser le nombre de requêtes rejetées pour violation des contraintes temporelles (impossibilité de respecter l'horaire de départ au plus tôt à l'adresse d'origine ou l'horaire d'arrivée au plus tard à l'adresse de destination) ;
• -minimiser le nombre de véhicules mobilisés pour desservir les passagers ;
• -minimiser les temps de parcours de l'ensemble des véhicules ;
• -minimiser les distances totales parcourues par tous les véhicules ;
• -minimiser le temps d'attente des passagers (le temps d'attente est égal à la différence entre l'horaire de départ au plus tôt et l'horaire de passage effectif du véhicule à l'adresse d'origine).

• -la congestion qui peut violer les contraintes temporelles des passagers :
• -I'annulation d'une demande ou l'absence d'un passager à l'adresse d'origine ;
• -la panne d'un véhicule.

• Q30.Donner en pseudo-code l'algorithme de insertion_missions permettant le traitement d'une nouvelle requête passager selon l'heuristique décrite plus haut. L'algorithme résoudra l'insertion d'une seule requête reçue. On pourra supposer la pré-existence de la fonction insertion(r, veh) et donc l'utiliser dans le pseudo-code.

• Q31.Proposer une idée de modification de l'algorithme insertion_missions, qui serait plus efficace selon vous en limitant sa myopie (argumenter).

• 1.une congestion (augmentation des temps de parcours) ;
• 2.une panne d'un véhicule autonome ;
• 3.une annulation de requête.
• Q32.Décrire (en texte libre, moins de 10 lignes) une solution permettant de déterminer si un re-calcul de missions est nécessaire ou non dans chacun des trois cas précédents.
• Q33.Proposer une solution (description en texte libre, moins de 10 lignes) permettant de recalculer les missions en cas de congestion. On ne considère que les requêtes qui ne sont pas en cours d'exécution (i.e. on ne considère pas les passagers à bord des véhicules).
• Q34.Proposer une solution (description en texte libre, en moins de 10 lignes) permettant de recalculer les missions en cas de panne.
• Q35.Proposer une solution (description en texte libre, en moins de 10 lignes) permettant de recalculer les missions en cas d'annulation de requête.

• Q36.Proposer une manière d'intégrer cette information dans l'algorithme insertion(r, veh), pour minimiser les recalculs d'itinéraires à cause de la congestion (description en texte libre en moins de 10 lignes).

• Q37.Comment peut-on utiliser cette possibilité pour améliorer l'efficacité du système d'optimisation ?

• Q38.Proposer au moins deux idées pour optimiser l'autonomie énergétique des véhicules. Quels véhicules recharger au dépôt et quand ?

Documents techniques

DT1 : Exemples de requêtes SQL sur une base de données fictive

SELECT commandes.total, clients.nom
    FROM commandes JOIN clients ON clients.id = commandes.id_client
    WHERE commandes.date_livraison > NOW()
    ORDER BY commandes.date_livraison
    LIMIT 5

SELECT clients.nom, sum(commandes.total)
    FROM commandes, clients
    WHERE clients.id = commandes.id_client
    GROUP BY clients.id

DT2 : modules database.py, course_client.py et outils.py

class DatabaseValueError(Exception): pass
class Database:
    """
    Utilisation de la base de données Flex-e-trans,
    """
    def __init__(self, type_: int, params: dict):
        """
        :param type_: 0 pour sqlite, 1 pour mariadb
        :param params: dict. contenant les informations de connection
            pour sqlite3
                {'filename' : <nom_fichier> }
            pour mariadb
                {'host': <host>, 'database': <dbname>, 'username': <user>,
                    'password': <password>}
        """
        self.type: int = type_
        self.params: dict = params
        self.is_connected: bool = False
    def _connect(self):
        ⋯
        self.is_connected = True
    def _select(self, request: str, params: tuple=None) -> list:
        " Méthode utilisée pour l'exécution d'une requête SELECT "
        if not self.is_connected:
            self._connect()
        cursor = self.conn.cursor()
        if params is not None:
            cursor.execute(request, params)
        else:
            cursor.execute(request)
        rows = cursor.fetchall()
        result = list(rows)
        cursor.close()
        return result
    def _change(self, request: str, params: tuple = None) -> int:
        """
        Méthode utilisée pour l'exécution d'une requête
        UPDATE, INSERT, DELETE. Renvoie le nombre de lignes
        modifiées par la requête
        """
        ... # Code non donnée ici
        return rowcount

def get_hashed_password(self, email: str) -> str:
    """
    Récupération du mot de passe haché stocké dans la base à partir
    de l'email
    """
    req = "SELECT password FROM Client where email=?"
    res = self._select(req, (email,))
    if not res:
        raise DatabaseValueError("Utilisateur inconnu")
    if len(res) > 1:
        raise DatabaseValueError("Utilisateur en double")
    return res[0][0] # Renvoie le 1er champ de la 1ère ligne
def update_pwd(self, client_email: str, hashed_passwd: str) -> bool:
    """
    Met à jour le champs password associé à un email.
    Renvoie True si la mise a jour a pu être faite.
    """
    req = "UPDATE Client SET password=? WHERE email=?"
    r = self._change(req, (hashed_passwd, client_email))
    return r == 1
def get_client_name_from_email(self, email: str) \
        -> Optional[Tuple[str, str]]:
    """
    Renvoie le nom et le prénom d'un client à partir de son email.
    Si le client n'est pas trouvé, renvoie None
    >>> db.get_client_name_from_email("[email protected]")
    ("Smith", "John")
    """
    ⋯
def get_next_travel(self, email: str) -> dict:
    ...
def store_password(self, client_email: str, password: str) -> bool:
    ...
def check_password(self, client_email: str, password: str) -> bool:
    ⋯

from typing import Optional, Union, Tuple
import datetime
import struct
from dataclasses import dataclass
from PIL import Image
import outils
class CourseClient:
    def __init__(self, course: int, client: int, pos_depart: Position,
            heure_depart: Position, pos_arrivee: datetime.datetime,
            heure_arrivee: datetime.datetime):
        self.course_id: int = course
        self.client_id: int = client
        self.depart: Position = pos_depart
        self.arrivee: Position = pos_arrivee
        self.hdepart: datetime.datetime = heure_depart
        self.harrivee: datetime.datetime = heure_arrivee
    def to_bytes(self) -> bytes:
        """ renvoie une forme binaire compacte de "CourseClient' """
        # int 4 octets pour course_id + int 4 octets pour client_id
        cc_id = struct.pack(">ii", self.course_id, self.client_id)
        # 4 + 4 octets pour depart
        depart = self.depart.to_bytes()
        # 4 + 4 octets pour arrivee
        arrivee = self.arrivee.to_bytes()
        # 2 octets pour year, month, day, hour, minute
        dep_heure = struct.pack(">hhhhh",
                self.hdepart.year, self.hdepart.month,
                self.hdepart.day, self.hdepart.hour,
                self.hdepart.minute)
        # 2 octets for year, month, day, hour, minute
        arr_heure= struct.pack(">hhhhh",
                self.harrivee.year, self.harrivee.month,
                self.harrivee.day, self.harrivee.hour,
                self.harrivee.minute)
        return cc_id + depart + dep_heure + arrivee + arr_heure
    @classmethod
    def from_bytes(cls, b: bytes) -> "CourseClient":
        ...
    def create_qr_code(self) -> Image:
        """ Crée l'image d'un code QR signé à partir des informations
        d'un trajet (CourseClient) """
        ...

    # suite classe CourseClient
    @classmethod
    def read_qr_code(cls, img: Image) -> Optional["CourseClient"]:
        """ Si l'image du code QR est valide, et que le code QR est
        correctement signé, renvoie l'objet CourseClient contenu
        dans le code QR. Sinon, renvoie None
        """
        ⋯
@dataclass
class Position:
    latitude: float
    longitude: float
    def to_bytes(self) -> bytes:
        # 4 octets (IEE754 single) pour latitude, 4 octets pout longitude
        return struct.pack(">ff", self.latitude, self.longitude)
    @classmethod
    def from_bytes(cls, data: bytes) -> "Position":
        lat, long = struct.unpack(">ff", data)
        return cls(lat, long)

import random
import hashlib
import datetime
import hmac
import string
from PIL import Image
from typing import Optional, Union, Tuple
SECRET_KEY = bytes.fromhex("043372332e372272153e352f3d2b6760")
def to_python_datetime(dt: str) -> datetime.datetime:
    """ Convertit une date issue de la base de donnée en objet
    datetime.datetime de Python
    >>> to_python_datetime("2023-06-20 10:30:00")
    datetime.datetime(2023, 6, 20, 10, 30, 0)
    """
    dtformat = "%Y-%m-%d %H:%M:%S"
    return datetime.datetime.strptime(dt, dtformat)
def random_chars(n: int) -> str:
    """ Renvoie une chaîne de n caractères pseudo-aléatoires
    (lettre ou chiffres) """
    chars = string.ascii_letters + string.digits
    lst = [random.choice(chars) for _ in range(n)]
    return "".join(lst)

def sign(data: bytes) -> bytes:
    """ Renvoie les données signées (données + signature) au format :
    - 1 octet pour le type de signature
    - 2 octets pour la taille des données
    - X octets pour les données
    - la signature
    """
    sig_type = 1 # Évolution possible vers d'autres signatures
    n = len(data)
    if n > 0xffff:
        raise ValueError("Too large data")
    sig = hmac.HMAC(SECRET_KEY, msg=data, digestmod=hashlib.sha256).digest()
    return bytes([sig_type, n // 256, n % 256]) + data + sig
def hash_with_salt(salt: str, password: str) -> str:
    ...
def check_sign(data_sig: bytes) -> bool:
    ...
def to_b45(a: int, b: Optional[int] = None) \
        -> Union[Tuple[int, int], Tuple[int, int, int]]:
    ⋯
def b45_to_str(b45lst: list) -> str:
    ...
def base45_encode(data: bytes) -> str:
    ...
def base45_decode(sdata: str) -> bytes:
    " Décode une chaîne Base45 en séquence d'octets "
    # Fonction non détaillée ici
    ...
def qrencode_alpha(sdata: str) -> Image:
    " Renvoie l'image d'un code QR à partir d'une chaîne Base45 "
    # Fonction non détaillée ici
    ...
def qrdecode_alpha(im: Image) -> Optional[str]:
    """ Décode l'image du code QR.
    Renvoie None si l'image n'est pas celle d'un code QR
    alphanumérique (mode 2). Renvoie la chaîne Base45 sinon"""
    # Fonction non détaillée ici
    ...

DT3 : Fonction de hachage

Principe général

Application au contrôle d'accès

• -attaque par dictionnaire ;
• -attaque par force brute ;
• -attaque par table arc-en-ciel.

Figure 6: Exemples de hachages de textes par la fonction MD5; (a) le texte utilisé est la version libre de Vingt mille lieues sous les mers du projet Gutenberg2 ; (b) la version modifiée est le même fichier texte, le 10e caractère de la 1000e ligne ayant été remplacé par le caractère *.

DT4 : Salage des mots de passe

Objectif du salage

Initialisation

identifiant | hachage(sel + mot de passe) | sel

Utilisation

DT5 : Signature HMAC SHA-256

DT6 : The Base45 Data encoding

When to Use and Not Use Base45

The Alphabet Used in Base45

Encoding examples

$<talker ID><trame type>[,<data>,<data>]*<checksum>

• -GGA : horodatage, position et informations sur le fix
• -GSA : mode opératoire, nombre de satellites utilisés, et valeurs de dilution de précision
• -GSV : position (élévation, azimuth...) des satellites visibles

• -064036.289 : horaire d'émission de la trame, ici 06 h 40 min 36.298 s
• -4836.5375 : latitude ddmm.mmmm, ici 48^∘36.5375^′. Si la latitude vaut x^∘y^′ (degrés, minutes), le nombre dans la trame vaudra x × 100 + y
• -N : latitude Nord (ou pourrait trouver un S)
• -00740.9373 : longitude dddmm.mmmm, ici 7° et 40.9373'
• -E : longitude Est (ou pourrait trouver un W pour West)
• -les 9 champs suivants n'ont pas d'importance ici
• -* : séparateur de checksum
• -OE : Somme de contrôle de parité, un simple XOR sur les caractères situés strictement entre $ et *

• -A : sélection Automatique 2D ou 3D du FIX (A=automatique, M = manuel)
• -3 : fix 3D
• - 04, 05… : numéros des satellites utilisés pour le FIX (12 champs car 12 satellites maximum)
• -2.5 : dilution de précision (PDOP)
• -1.3 : dilution de précision horizontale (HDOP)
• -2.1 : dilution de précision verticale (VDOP)
• -* : séparateur de checksum
• -39 : somme de contrôle de parité, un simple XOR sur les caractères situés strictement entre $ et *

• -2 : nombre de trames GSV pour obtenir les données complètes (1, 2 ou 3)
• -1 : ici, trame 1 sur les 2 trames attendues
• -08 : Nombre de satellites visibles en tout
• -données sur le premier satellite :
  • -01 : N° d'identification du 1er satellite.
  • -40 : Élévation en degrés du 1er satellite.
  • -083 : Azimut en degrés du 1er satellite.
  • -46 : Force du signal du 1er satellite (Plus grand=meilleur)
• -données sur le deuxième satellite : 02,17,308,41
• -données sur le troisième satellite : 12,07,344,39
• -données sur le quatrième satellite : 14,22,228,45
• -* : séparateur de checksum
• -75 : somme de contrôle de parité, un simple XOR sur les caractères situés strictement entre $ et *

DT8 : Table ASCII

DT9 : adresse GeoNetworking

Dans cette description, le bit 0 est le bit de poids fort.
La table suivante détaille la composition d'une adresse GeoNetworking (8 octets).

• -M (1 bit) : 1 if address is manually configured
• -ST (4 bits) : ITS Station type
  • -bit 1
    • *0 : Vehicle ITS station
    • *1 : Roadside ITS station
  • -bits 2,3,4
    • *for roadside ITS station:
      • -0 : Traffic light
      • -1 : Ordinary roadside ITS station
    • *for vehicle ITS station:
      • -0 : Bike
      • -1 : Motorbike
      • -2 : Car
      • -3 : Truck
      • -4 : Bus
• -S (1 bit) : Public (0) or Private (1) ITS station
• -SCC (10 bits) : ITS Country Code (voir plus loin)
• -MID (48 bits) : address (LL_ADDR)

DT10 : Long position vector

Dans cette description, le bit 0 est le bit de poids fort.

• -GN_ADDR : Network address (8 bytes)
• -TST : Express the time in milliseconds at which position of the ITS station was acquired. Time is encoded as : TST = TST(UET) mod2^∧32 where TST(UET) is the number of milliseconds since 1970-01-01T00:00
• -Latitude : Latitude expressed in 1/10 micro degree
• -Longitude : Longitude expressed in 1/10 micro degree
• -S : Speed expressed in units of 0.1 meters per second
• -H : Heading expressed in 0.1 degrees from North
• -Alt : Altitude (meters)
• -TAcc : Accuracy indicator (4 bits)
• -PosAcc : Accuracy indicator (4 bits)
• -Sacc : Speed accuracy indicator (3 bits)
• -HAcc : Heading accuracy indicator (3 bits)
• -Acc : Altitude accuracy indicator (2 bits)

DT11 : Entête étendu GeoNetworking

Dans cette description, le bit 0 est le bit de poids fort.
Le contenu détaillé est l'entête d'un paquet de type GeoBroadcast.

• -Version (4 bits) : version of the GeoNetworking Protocol
• -NH (4 bits) : type of header following the GeoNetworking header
• -HT (4 bits) : type of GeoAdhoc header (4 for GeoBroadcast)
• -HST (4 bits) : subtype of GeoAdhoc header (0 for a Circular Area)
• -Flags : Type of ITS station (bit 6), other bits set to zero
• -PL : Length of the network header payload
• -TC : Traffic class
• -HL : Time to live decremented by 1 each router
• -SE PV : Long position vector of the sender
• -SN : Sequence Number
• -LT : Lifetime field : maximum tolerable time a packet can be buffered until it reaches its destination
• -SO PV : Long position vector of the source
• -GeoAreaPos Latitude : WGS-84 latitude of the area in 1/10 micro degree
• -GeoAreaPos Longitude : WGS-84 longitude of the area in 1/10 micro degree
• -Distance a : distance a of the geometric shape
• -Distance b : distance b of the geometric shape
• -Angle : angle of the geometric shape

DT12 : Simple GeoBroadcast forwarding algorithm with line forwarding

SIMPLE GEOBROADCAST FORWARDING ALGORITHM
==========================================
-- P is the GeoNetworking packet to be forwarded
-- LAT and LONG are latitude and longitude of the LPV, respectively
-- DAp is the destination area in the GeoNetworking packet to be forwarded
-- A is the centre point of the destination area DAp
-- LL_ADDR is the link layer address that identifies the next hop
-- of the GeoNetworking packet
-- BCAST is the broadcast LL address
-- GREEDY() is the GF algorithm
LL_ADDR = 0
Calculate F(LAT, LONG)
IF (F 2 0) THEN
    RETURN LL_ADDR = BCAST
ELSE
    RETURN LL_ADDR = GREEDY(A) or 0
ENDIF

GF ALGORITHM
==============
-- P is the GeoUnicast packet to be forwarded
-- i is the i-th LocTE
-- NH is the LocTE identified as next hop
-- NH_LL_ADDR is the link layer address of the next hop
-- LPV is the local position vector
-- PVp is the destination position vector in the GeoNetworking
-- packet to be forwarded
-- PVi is the position vector of the i-th LocTE
MFR = DIST(PVp, LPV)
FOR (i E LocT)
    IF (i.IS_NEIGHBOUR) THEN
        IF (DIST(PVp, PVi) < MFR) THEN
            NH ← i
            MFR ← DIST(PVp, PVi)
        ENDIF
    ENDIF
ENDFOR
IF (MFR < DIST(PVp, LPV)) THEN
    SET NH_LL_ADDR = NH.LL_ADDR
ELSEIF
    LOCAL OPTIMUM
    SET NH_LL_ADDR = 0
ENDIF

Tous les documents réponses sont à rendre, même non complétés.

Document réponse DR1

# dans outils.py
def hash_with_salt(salt: str, password: str) -> str:
    """
    >>> hash_with_salt("S_8u", "Wikipedia")
    'S_8u:33bf32c0e27f6361d21287df83f19a23c5b2d0e7f25e1899ef8c3621640f8907'
    """
    b_password = password.encode("utf8")
    b_salt = ........................
    hashed_password = hashlib.sha256(b_salt + ..........).hexdigest()
    return salt + ":" + .......................
# dans database.py
class Database:
    def store_password(self, client_email: str, password: str) -> bool:
        salt = outils.random_chars(16)
        return self.update_pwd(client_email, ............................)

Document réponse DR2

class Database:
    def check_password(self, client_email: str, password: str) -> bool:
        try:
            stored_hashed_password = .............................
        except DatabaseValueError:
            return False
        ....... = stored_hashed_password.split(":")[0]
        return ..........................== stored_hashed_password

Document réponse DR3

class CourseClient:
    @classmethod
    def from_bytes(cls, b: bytes) -> "CourseClient":
        """
        Méthode de classe qui renvoie un nouvel objet ˋCourseClientˋ
        à partir de sa représentation compacte
        """
        course, client = struct.unpack(">ii", b[:8])
        pos_depart = Position.from_bytes(.....................)
        h_depart = .......................
        pos_arrivee = ...................
        h_arrivee = ......................
        heure_depart = datetime.datetime(*h_depart)
        heure_arrivee = datetime.datetime(*h_arrivee)
        return cls(............................)

Document réponse DR4

def check_sign(data_sig: bytes) -> bool:
    """
    Vérifie que les données sont correctement signées
    (ont été correctement produites par ˋsignˋ)
    """
    sig_type = data_sig[0]
    if sig_type == 1:
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    else:
        return False

Document réponse DR5

def to_b45(a: int, b: Optional[int]=None) -> Union[Tuple[int, int],
            Tuple[int, int, int]]:
    if b is None:
        n = a
        c, d = n % 45, n // 45
        return (c, d)
    else:
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        .........................................................
        return (c, d, e)
def b45_to_str(b45lst: list) -> str:
    chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"
    return "".join(chars[k] for k in b45lst)
def base45_encode(data: bytes) -> str:
    """
    Encode une séquence d'octets en chaîne Base45
    """
    lst_res = []
    lst_bytes = list(data)
    if len(data) % 2 == ...........:
        lst_bytes.append(None)
    for a, b in zip(lst_bytes[0::2], lst_bytes[1::2]):
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    return "".join(lst_res)

Tous les documents réponses sont à rendre, même non complétés.

Document réponse DR6

typedef struct {
    float latitude, longitude;
    int heures, minutes;
    float secondes;
} position;
float read_deg(char str[]) {
        float tmp;
        int deg;
        float minutes;
        sscanf(str, "%f", &tmp);
        deg = tmp / 100;
        minutes = tmp - deg * 100;
        return deg + minutes / 60;
}
void read_latitude(char str[], float * latitude) {
        *latitude = read_deg(str);
        if (str[10] == 'S') *latitude = -*latitude;
}
void read_longitude(char str[], float * longitude) {
        ........................................................
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        .....................................................
}
void read_timestamp(char str[], int * h, int * m, float *s) {
        .........................................................
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        ......................................................
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        ......................................................
}

int check_crc(char str[]) {
    .........................................................
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
}
/* Fonction principale, prenant en paramètre une trame NMEA
    complète et un pointeur vers une structure de position.
    Cette structure est remplie par la fonction, qui renvoie 1
    si un décodage a été effectué, et 0 sinon (par exemple si
    ce n'est pas une trame du bon type)
*/
int get_position(char nmea_frame[], position * pos) {
    if (nmea_frame[0] != '$') return 0;
    if (!check_crc(nmea_frame)) return 0;
    .........................................................
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    ....................................................
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
}

Le premier cercle est déjà tracé (en pointillés).