Agrégation informatique externe 2022, é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 16 ;
  • ○partie 1 de la page 3 à la page 8 ;
  • ○partie 2 de la page 9 à la page 11 ;
  • ○partie 3 de la page 12 à la page 16 ;
• -d'un dossier technique (DT) de la page 17 à la page 26 ;
• -d'un dossier réponse (DR) de la page 27 à la page 32.

• -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.

VISITES ENRICHIES D'UN MUSEE

Plan du musée Guimet (Lyon), Tony Blein architecte, 19 mars 1912 domaine public, archives municipales de Lyon

PARTIE 1. LOCALISATION DES VISITEURS

• -les cohortes de visiteurs, les attroupements et les déplacements majoritaires peuvent être facilement identifiés,
• -les algorithmes d'analyse d'image peuvent mettre en évidence les comportements à risques envers les œuvres d'art avec pour but de diriger rapidement la surveillance humaine.

Sous-partie 1.1. Observation des bornes Wi-Fi à proximité

• -l'affectation d'un SSID propre à chaque point d'accès (par exemple MUSEE-001, MUSEE-002...) est la plus simple à réaliser, le visiteur associe son terminal à chaque borne ;
• -la diffusion d'un SSID unique (par exemple MUSEE) sur tout l'espace du musée a pour conséquence la réalisation d'une association unique avec le réseau, l'association est automatiquement renouvellement par le terminal du visiteur pour chaque borne rencontrée.

• Q4.D'après cette description, le processus de connexion fait apparaître trois états. Tracer la machine à états correspondante pour le terminal détenu par le visiteur. Indiquer pour chaque état les actions associées et pour chaque transition la condition associée.

• Q5.Lister les protocoles d'authentifications cités dans ce document technique. Indiquer les principales étapes faisant suite à ces six échanges pour obtenir une connexion pleinement sécurisée. Nommer l'algorithme de chiffrement utilisé par le Wi-Fi.
• Q6.Discuter la faisabilité de la localisation d'un terminal du point de vue du réseau en se basant sur les requêtes émises par le terminal pour découvrir les points d'accès du réseau.

• Q7.Compléter le code du document réponse DR1 permettant d'obtenir le niveau de réception du point d'accès associé.
• Q8.Dans le document réponse DR1, préciser l'opération réalisée par la seconde ligne de code « WifiManager wifiManager = (WifiManager) service; ». Tracer le diagramme de classe correspondant.

La figure ci-dessous représente deux salles du musée couvertes par trois points d'accès Wi-Fi (numérotés de 1 à 3). Les cercles centrés sur chacune des trois bornes représentent la zone où le niveau de réception (RSSI) à -50 dBm est garanti. Ce niveau de puissance reçue permet une « bonne » qualité dans les communications et le terminal reste associé au point d'accès courant. Lorsque le niveau de réception est inférieur à -50 dBm , le système d'exploitation du terminal du visiteur scanne à nouveau tous les réseaux à proximité.

• Q9.Estimer la précision de la localisation du visiteur pour ces quatre points définis en se basant sur les trois bornes présentes.

Sous-partie 1.2. Analyse automatisée de la vidéosurveillance

Source : Chen, Ruei-Xi & Zhao, Wei & Fan, Jeffrey & Davari, A.. (2009). Vector Bank Based Multimedia Codec System-on-a-Chip (SoC) Design. 515-520. 10.1109/I-SPAN.2009.74.

• Q10.Proposer un type de données adapté à la représentation des déplacements horizontaux et verticaux stockés pour chaque élément de la matrice.

• Q11.En déduire l'occupation mémoire de cette matrice. Définir les fonctions de conversions f et g telles que i = f(c, l) et (c, l) = g(i).

• Q12.Dans le document réponse DR2, compléter le pseudocode de la fonction « coloriage ». Celleci associe une même couleur aux groupes adjacents ayant les mêmes déplacements.

• Q13.Dans le document réponse DR3, compléter le pseudocode parcourant toute la matrice de déplacement à la recherche d'objets non coloriés

• Q14.Evaluer la profondeur maximale des appels récursifs pour ce cas moyen. Evaluer la complexité de la fonction « coloriage » puis de l'algorithme vis-à-vis de la taille apparente de l'objet et du nombre d'objets.
• Q15.Critiquer la qualité des résultats issus de cet algorithme par rapport à l'allure des motion vectors extraits de l'image en début de cette sous-partie. En déduire le nombre d'objets effectivement détectés par cette technique par rapport au nombre réel de visiteurs. Proposer des pistes d'améliorations pour limiter les défauts de cet algorithme.

• • -sa validité, une surface apparente inférieure à 30 éléments est considérée comme seuil de rejet de cet objet,
  • -son centre comme étant la moyenne des coordonnées (x,y) des éléments ayant la couleur de cet objet.
• Q16.Dans le document réponse DR3, compléter le pseudocode d'estimation de la validité et de la position moyenne de chaque objet.

• Q17.Représenter la scène (salle, visiteur et caméra) par un schéma approprié. Justifier l'existence d'une position réelle pour certaines positions vues par la caméra. Préciser les hypothèses et les limites de votre modèle.

• Q18.Discuter de la linéarité de ce modèle. Proposer un protocole expérimental permettant d'étalonner les positions réelles des visiteurs en fonction des positions apparentes vues par la caméra.

• Q19.Proposer des améliorations à l'algorithme du document réponse DR3 lui permettant d'annoter les visiteurs détectés

Sous-partie 1.3. Recoupement des observations

• Q20.Discuter de la faisabilité technique et réglementaire du regroupement des informations entre les deux sources décrites dans cette partie

PARTIE 2. STOCKAGE DES INFORMATIONS

• -le musée est constitué d'un ou plusieurs complexes, nommés par un chiffre,
• -chaque complexe est constitué d'un ou plusieurs bâtiments, nommés par une lettre,
• -chaque bâtiment est constitué d'un ou plusieurs étages, nommés par un chiffre,
• -chaque étage est constitué d'une ou plusieurs salles, nommées par une lettre,
• -chaque salle est constituée d'une ou plusieurs zones d'intérêt (Rol = Region of Interest), nommés par un chiffre.

• -la colonne « identifiant » est un entier auto-incrémenté et est la clé primaire,
• -la colonne « parent » est un entier et est une clé étrangère faisant référence à la colonne « identifiant » de la table définissant le « parent ».

• -« identifiant », un identifiant unique pour cette localisation, c'est un entier auto-incrémenté.
• -« visiteur », une référence vers l'identifiant unique du visiteur (anonymisé) , défini comme un entier dans la colonne « identifiant » de la table « visiteur »,
• -« instant », un instant d'observation (TIMESTAMP) sous la forme d'une date et d'une heure (précis à la seconde près), ajouté automatiquement pour chaque insertion,
• -« zone », une référence vers l'identifiant unique de la zone d'intérêt, défini comme un entier dans la colonne « identifiant » de la table « zone ».

• Q27.Créer la vue « resume_localisation » en créant une requête de sélection capable de grouper les lignes similaires de la table « localisation » et d'extraire les instants d'entrée et de sortie.
• Q28.Evaluer le nombre d'enregistrements à l'année, proposer des améliorations à la structure pour favoriser la vitesse d'exécution des requêtes de sélection vues dans cette partie.

PARTIE 3. ANALYSE DES TRAJECTOIRES

• - Z est l'identifiant d'une zone d'intérêt du musée (c'est un entier «int »),
• - S est l'identifiant d'une salle du musée (c'est un entier « int »),
• - E est l'identifiant d'un étage du musée (c'est un entier « int »),
• - B est l'identifiant d'un bâtiment du musée (c'est un entier « int »),
• - C est l'identifiant d'un complexe du musée (c'est un entier « int »),
• -tstart est l'instant d'entrée d'un visiteur dans cette zone,
• -tend est l'instant de sortie d'un visiteur de cette zone,
• - A est une liste dynamique d'annotation de la présence de ce visiteur dans cette zone.

Sous-partie 3.1. Cohérence des traces

• Q32.Expliquer le rôle de l'opérateur « & » utilisé dans la déclaration du paramètre « t » de la fonction « corrige_trace » (dans le document réponse DR4). Justifier son emploi.
• Q33.Dans le document réponse DR4, compléter le code de la fonction « corrige_trace ».

• Q34.Dans le document réponse DR5, compléter le code de la fonction « interpole_trace »

Sous-partie 3.2. Exploitation directe des données

• -nombre de visiteurs pour les différentes parties du musée,
• -temps moyen pour les différentes parties,
• -temps moyen par visiteur,
• -fréquentation par tranche horaire pour les salles du musée...

int main()
{
    vector<trace> traj = charger_trajectoire();
    vector<seconds> t;
    vector<int> v;
    occupation_etage(traj, t, v);
    ...
    return 0;
}

Sous-partie 3.3 Exploration des données et prospective

constexpr size_t NB_ZONES 256; // nombre de zones considérées
typedef array<seconds,NB_ZONES> empreinte; // occupation par zone
int meilleur_profil(empreinte visiteur, vector<empreinte> profils);

• -« visiteur » liste tous les temps écoulés dans chacune des zones pour le visiteur,
• -« profils » liste toutes les empreintes des profils-types, chaque profil liste les temps écoulés dans chacune des zones
• -la valeur de retour est l'indice du profil le plus ressemblant (pour lequel le résultat de la corrélation est maximal)

DOSSIER TECHNIQUE

• -DT1. Attributs de la classe ScanResult, page 18 ;
• -DT2. Association Wi-Fi, page 19 et 20 ;
• -DT3. Structures de localisation, page 21 ;
• -DT4. Éléments de syntaxe SQL « CREATE TABLE », page 22 ;
• -DT5. Éléments de syntaxe SQL « CREATE VIEW », page 23 ;
• -DT6. Manipulations des flux et instants, page 24 ;
• -DT7. Manipulations des tableaux, page 25 ;
• -DT8. Indicateurs par étages, page 26 ;

Document technique DT1. Attributs de la classe ScanResult

public final class ScanResult extends Object

Document technique DT2. Association Wi-Fi

• -Not authenticated or associated.
• -Authenticated but not yet associated.
• -Authenticated and associated.

1. A mobile station randomizes its MAC address and sends probe requests to discover 802.11 networks within its proximity. Probe requests advertise the mobile stations supported data rates and 802.11 capabilities such as 802.11 n . Because the probe request is sent from the mobile station to the destination layer-2 address and BSSID of ff:ff:ff:ff:ff:ff all AP's that receive it will respond.
2. APs receiving the probe request check to see if the mobile station has at least one common supported data rate. If they have compatible data rates, a probe response is sent advertising the SSID (wireless network name), supported data rates, encryption types if required, and other 802.11 capabilities of the AP.

Document technique DT3. Structure des localisations

La figure ci-dessous est extraite de l'article : Kontarinis, A., Zeitouni, K., Marinica, C. et al. Towards a semantic indoor trajectory model: application to museum visits. Geoinformatica 25, 311-352 (2021). https://doi.org/10.1007/s10707-020-00430-x

Document technique DT4. Eléments de syntaxe SQL « CREATE TABLE »

• -les mots en majuscules sont des mots clés du langage
• -les mots en gras sont des identificateurs choisis par le programmeur,
• -les mots en italiques sont des références à d'autres éléments de syntaxe,
• -les parenthèses ( ) font partie de la commande,
• -les accolades { } limitent la portée des opérateurs suivants,
• -les crochets [ ] entourent une portion facultative de la syntaxe,
• -les points de suspension ... indiquent une répétition 1 ou + du bloc précédent,
• -la barre verticale | indique un choix entre plusieurs éléments de syntaxe.

CREATE TABLE [IF NOT EXISTS] tbl_name (create_definition
[create_definition , ...])
create_definition: col_name column_definition | index_definition
column_definition: data_type [NOT NULL | NULL] [AUTO_INCREMENT]
index_definition: {
    PRIMARY KEY (index_col_name)
| UNIQUE [INDEX|KEY] [index_name] (index_col_name)
| CONSTRAINT FOREIGN KEY (index_col_name) reference_definition }
reference_definition:
    REFERENCES tbl_name (index_col_name)
        [ON DELETE reference_option]
        [ON UPDATE reference_option]
reference_option:
    RESTRICT | CASCADE | SET NULL

• -RESTRICT la modification ou la suppression d'une valeur de la colonne est refusée si une référence existe vers cette valeur (comportement par défaut si reference_option est omis),
• -CASCADE la modification ou la suppression d'une valeur de la colonne est autorisée et automatiquement propagée aux références vers cette valeur,
• -SET NULL si la valeur nulle est autorisée pour toutes les références, la modification ou la suppression d'une valeur de la colonne est autorisée et les éventuelles références sont modifiées comme nulle ; sinon la modification ou la suppression est refusée.

CREATE [OR REPLACE] [DEFINER = { user | CURRENT_USER }] [SQL SECURITY {
DEFINER | INVOKER }] VIEW view_name [(column_list)] AS select_statement
column_list: column_name [, column_name ...]
select_statement: SELECT select_expr [, select_expr ...]
    FROM table_references WHERE where_condition
select_expr: column_name | table_name.column_name
table_references: table_name [, table_name ...]

Document technique DT6. Manipulations des flux et instants

#include <chrono> // types seconds, minutes, jours ainsi que suffixes
#include <sstream> // chaînes de caractères sous la forme de flux
#include <iostream> // flux standard cout vers la console d'exécution
using namespace std; // std::string peuvent être raccourci en string
using namespace std::chrono; // idem avec chrono::seconds...
// le type seconds a la documentation suivante :
// seconds = duration</*signed integer type of at least 35 bits*/>
// converti une chaîne de caractères HH:MM:SS en secondes
seconds seconds_from_string(string& str)
{
    istringstream is{str}; // flux en lecture seule pour lire str
    char unused; // pour extraire les caractères ":"
    unsigned int h,m,s;
    is >> h; // lecture des heures
    is >> unused; // élimination du séparateur
    is >> m; // lecture des minutes
    is >> unused; // élimination du séparateur
    is >> s; // lecture des secondes
    // calcul et retour du nombre équivalent de secondes
    // 1h utilise le suffixe "h", construit un objet "hours"
    // 1min utilise le suffixe "min", construit un objet "minutes"
    // 1s utilise le suffixe "s", construit un objet "seconds"
    return (h * 1h) + (m * 1min) + (s * 1s);
}
int main()
{
    // variable de type "seconds" initialisé par une constante
    seconds sec1 = 15h + 12min + 10s;
    // endl = end-of-line
    cout << "sec1=" << sec1 / 1s << endl; // affiche sec1=54730
    // constante chaîne de caractères
    string s = "15:12:09";
    // conversion de la chaîne de caractères en secondes
    seconds sec2 = seconds_from_string(s);
    cout << "sec2=" << sec2 / 1s << endl; // affiche sec2=54729
    seconds diff = sec1 - sec2;
    cout << "diff=" << diff / 1s << endl; // affiche diff=1
    // « seconds » peut être comparés avec les opérateurs habituels
    // if(sec1 > sec2) ...
    return 0; // retour de la fonction main, 0 = pas d'erreur
}

Document technique DT7. Manipulations des tableaux

#include <iostream> // flux standard cout vers la console d'exécution
#include <array> // définition des tableaux fixes
using namespace std; // std::array disponible simplement comme array
int main()
{
    // création d'un tableau de 5 entiers préinitialisés (facultatif)
    array<int,5> a{1,10,100,200,2};
    cout << "taille=" << a.size() << endl; // affiche taille=5
    // accès en lecture à un élément du tableau
    cout << "a[1]=" << a[1] << endl; // affiche a[1]=10
    int sum = 0;
    // itération sur toutes les valeurs du tableau (de 0 à size()-1)
    for(auto it = a.begin(); it != a.end(); it++)
        sum += *it; // accès à l'élément itéré (écriture possible)
    cout << "somme=" << sum << endl; // affiche Somme=313
    cout << "a[2]=" << a[2] << endl; // affiche a[2]=100
    a[2] = 18; // modification d'un élément d'un tableau
    cout << "a[2]=" << a[2] << endl; // affiche a[2]=18
    return 0; // retour de la fonction main, 0 = pas d'erreur
}

#include <iostream> // flux standard cout vers la console d'exécution
#include <vector> // définition des tableaux dynamiques
using namespace std; // std::vector disponible simplement comme vector
int main()
{
    // création d'un tableau de 2 entiers préinitialisés (facultatif)
    vector<int> v{2,5};
    cout << "taille=" << v.size() << endl; // affiche taille=2
    cout << "v[1]=" << v[1] << endl; // affiche v[1]=5
    int prod = 1;
    // itération sur toutes les valeurs du tableau (de 0 à size()-1)
    for(auto it = v.begin(); it != v.end(); it++)
        prod *= *it; // accès à l'élément itéré (écriture possible)
    cout << "produit=" << prod << endl; // affiche produit=10
    cout << "v[1]=" << v[1] << endl; // affiche v[1]=5
    v[1] = 10; // modification d'un élément du tableau
    cout << "v[1]=" << v[1] << endl; // affiche v[1]=10
    v.push_back(10); // ajout d'un élément à la fin du tableau
    cout << "taille=" << v.size() << endl; // affiche taille=3
    cout << "v[2]=" << v[2] << endl; // affiche v[2]=10
    return 0; // retour de la fonction main, 0 = pas d'erreur
}

Document technique DT8. Indicateurs par étage

#include <chrono> // définitions et calculs sur le temps
#include <algorithm> // pour ranges::fill
#include <vector> // pour les tableaux de type vector
using namespace std;
using namespace std::chrono;
// déclaration de annotation, presence et trace issues du DR4
constexpr size_t MAX_ETAGE = 100; // équivalent C++ du #define
void occupation_etage(
    vector<trace> trajectoires, // toutes déjà chargées en mémoire
    vector<seconds>& tcumul, // temps de cumul pour tous les étages
    vector<int>& vcumul) // visiteurs pour tous les étages
{
    // l'identifiant d'un étage est toujours entre 0 et MAX_ETAGE-1
    tcumul.reserve(MAX_ETAGE); // un élément par étage
    // remise à zéro de tous les temps cumulés pour tous les étages
    ranges::fill(tcumul.begin(), tcumul.end(), 0s);
    vcumul.reserve(MAX_ETAGE); // un élément par étage
    // remise à zéro de toutes les présences pour tous les étages
    ranges::fill(vcumul.begin(), vcumul.end(), 0);
    // les vecteurs sont correctement initialisés à zéro et peuvent
    // à présent stocker les cumuls pour tous les étages
    // pour toutes les trajectoires
    for(auto itt = trajectoires.begin();
        itt != trajectoires.end(); itt++)
    {
        // trajectoire courante
        trace& trajectoire = *itt;
        // pour toutes les présences de la trajectoire courante
        for(auto itp = trajectoire.begin();
            itp != trajectoire.end(); itp++)
        {
            // présence courante
            presence& p = *itp;
            // cumul du temps de visite pour cet étage
            tcumul[p.E] += p.tend - p.tstart;
            // cumul du nombre d'utilisateur pour cet étage
            vcumul[p.E] += 1;
        }
    }
}

DOSSIER REPONSE

• -DR1. Lecture niveau de réception RSSI, page 28 ;
• -DR2. Coloriage d'une zone, page 29 ;
• -DR3. Coloriage d'un objet, page 30 ;
• -DR4. Déclaration des types associés, page 31 ;
• -DR5. Interpolation des présences, page 32.

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

Document réponse DR1. Lecture niveau de réception RSSI

Object service = context.getSystemService(Context.WIFI_SERVICE);
WifiManager wifiManager = (WifiManager) service;

Document réponse DR2. Coloriage d'une zone

• -le fond de la vidéo, immobile, est caractérisé par la couleur (valeur numérique) 0,
• -chaque objet identifié correspond à une couleur (valeur numérique) unique.

Fonction coloriage( // colorie un objet de voisin en voisin
    Depl est un vecteur de 12288 n-uplets (x,y),
    Obj est un vecteur de 12288 couleurs,
    j est le point de départ du coloriage,
    Coul est la couleur de remplissage de l'objet
    // coloriage de la case courante
    (x,y) ← Depl(j)
    // x correspond au déplacement horizontal de la case courante
    // y correspond au déplacement vertical de la case courante
    Si( ) // la case de gauche existe
        (xg,yg) ← Depl( )
        // si non colorié et même déplacement
        Si( )
            // récursivité vers la gauche
        Fin Si
    Fin Si
    // coloriage vers la droite non-détaillé, semblable à la gauche
    Si( ) // la case du dessous existe
        (xb,yb) ← Depl( )
        // si non colorié et même déplacement
        Si( )
            // récursivité vers le bas
        Fin Si
    Fin Si
    // coloriage vers le haut non-détaillé, semblable au bas
Fin Fonction

Document réponse DR3. Coloriage d'un objet

Depl est un vecteur de 12288 n-uplets (x,y)
Res est un vecteur de 12288 couleurs, tout initialisé à 0, à calculer
Coul est un entier, initialisé à 0, à calculer
Pour i=0 jusqu'à 12287 avec un pas de 1,
    (x,y) ← Depl(i)
    Si( )
        // non colorié encore et déplacement est non-nul
            // allocation d'une nouvelle couleur
        // appel de la fonction de coloriage
    Fin si
Fin pour

Res est un vecteur de 12288 couleurs (entier), déjà calculées
Sx est un vecteur d'entiers (somme des positions x pour chaque objet)
Sy est un vecteur d'entiers (somme des positions y pour chaque objet)
N est un vecteur d'entiers (nombre d'éléments pour chaque objet)
Sx, Sy, N, V sont initialisés à zéro, à calculer
Pour i=0 jusqu'à 12287 avec un pas de 1,
    (x,y) ← Coord(i) // calcul coordonnée de l'élément courant
Fin pour
Mx, My sont des vecteurs de flottants
V est un vecteur de booléens (validité pour chaque objet)
Pour i=0 jusqu'à 255 avec un pas de 1,
Fin pour

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

Document réponse DR4. Déclaration des types associés

// annotation est une structure opaque, définie ultérieurement
typedef struct {} annotation;
typedef struct
{
} presence;

typedef trace;

// t représente la trace à vérifier/corriger
// la fonction n'a volontairement pas de valeur de retour
void corrige_trace(trace& t)
{
// t[i] ou *it permet d'accéder à une présence
// t[i].tstart ou it->tstart pour accéder aux champs d'une présence
// les éventuels indices sont à déclarer avec le type « size_t »
// les éventuels itérateurs sont à déclarer avec le type « auto »
}

Document réponse DR5. Interpolation des présences

// pour une zone donnée
// renvoie la salle S, l'étage E, le bâtiment B et le complexe C
void details_zone(int Z, int& S, int& E, int& B, int& C);
// renvoie la liste de zones à interpoler entre les zones données
// cette liste est vide si les zones Z1 et Z2 sont adjacentes
vector<int> interpole_zone(int Z1, int Z2);
trace interpole_trace(const trace t)
{
    // cette trace vide est à compléter avec les éléments de t,
    trace resultat; // éventuellement intercalés d'éléments interpolés
// t[i] ou *it permet d'accéder à une présence
// t[i].Z ou it->Z pour accéder aux champs d'une présence
// les éventuels indices sont à déclarer avec le type « size_t »
// les éventuels itérateurs sont à déclarer avec le type « auto »
    // la première présence est toujours ajoutée au résultat
    resultat.push_back(*it0);
    for(
    {
        vector<int> Z = interpole_zone(
        // si aucune zone à interpoler
        if(
        {
            // interpolation du temps dans chaque zone
            seconds tdelta = ( - ;
            seconds tstart = it0->tend; // temps de début
            // pour tous les éléments du vecteur Z
            for(
            {
                presence p; // champs non-initialisés sauf A vide
                p.Z =
                // récupération des détails de la zone
                details_zone(
                // interpolation du temps d'entrée
                // interpolation du temps de sortie
                // ajout de la présence interpolée
            }
        }
        // ajout de la présence suivante
    }
    return resultat;
}