Agrégation informatique externe 2023, épreuve 3Sujet et rapport du jury

AGREGATION
CONCOURS EXTERNE

ÉPREUVE SPÉCIFIQUE SELON L'OPTION CHOISIE :

• -ÉTUDE DE CAS INFORMATIQUE
• -FONDEMENTS DE L'INFORMATIQUE

INFORMATION AUX CANDIDATS

• -Etude de cas informatique :
  

  

• -Fondement de l'informatique :
  

  

Épreuve spécifique

Étude de cas informatique

Préliminaires

Partie I. Déterminer les tournées de véhicules

Figure 1 - Exemple d'un graphe et sa représentation sous forme de matrice d'adjacence et sous forme de matrice des distances.

dist ← A
foreach vertex 
z ∈ V do
    foreach vertex 
x ∈ V do
        foreach vertex 
y ∈ V do
            if 
dist(x, z) ≠ ∞&dist(z, y) ≠ ∞&dist(x, z) + dist(z, y) < dist(x, y) then
                
dist(x, y) ← dist(x, z) + dist(z, y)
return dist

• 1.Appliquer l'algorithme naïf expliqué au dessus et donner les tournées avec leurs coûts en termes de nombre de kilomètres pour l'ensemble des véhicules. Le coût d'une tournée inclut le retour du véhicule à l'entrepôt via le plus court chemin.
• 2.En considérant l'objectif de minimiser la distance totale des kilomètres parcourus par tous les véhicules, peut-on trouver une meilleure solution? Si oui, quelle est-elle?

• 1.On commence avec n tournées : v_0 → v_i → v_0, pour tout i ≥ 1, c'est-à-dire chaque client est livré par un véhicule différent.
• 2.Calculer ensuite les économies s(i, j) (savings) pour fusionner deux clients v_i et v_j en une même tournée : s(i, j) = dist(i, 0) + dist(0, j) − dist(i, j), pour tout i, j ≥ 1 et i ≠ j;
• 3.Trier les économies par ordre décroissant ;

• 4.Commencer en tête de la liste (restante) des économies, fusionner les deux tournées associées avec l'économie (restante) la plus élevée, si :
  • (a)Les deux clients ne sont pas déjà dans la même tournée ;
  • (b)Aucun des deux clients n'est à l'intérieur de sa tournée : Les deux clients sont connectés directement à l'entrepôt dans leur tournée respective et donc sont livrés en premier ou en dernier dans leur tournée respective ;
  • (c)La somme des demandes des deux tournées à fusionner ne dépasse pas la capacité maximum du véhicule.
• 5.Répéter l'étape 4 jusqu'à ce que plus aucune économie ne puisse être faite.

• -distance(self, distance) : qui renvoie la longueur actuelle de la tournée,
• -fusionnable(self, autreTournee, clients, capacite) : teste si la tournée peut être fusionnée avec autreTournee. Elle teste notamment les différents cas du point (2) de l'algorithme de Clarke et Wright.
• -fusion(self, autreTournee, clients): qui prend en entrée la tournée avec laquelle elle doit faire la fusion et une liste de clients par lesquels la tournée fusionnée doit être reliée.
• -affiche(self) : affiche la tournée avec la liste des différents clients à parcourir et le chargement total de cette tournée.

tournee1.affiche() # tournee 0 2 3 4 0 chargement 8
tournee2 = Tournee(1,3) #client 1 demande 3 palettes
tournee1.fusionnable(tournee2, [3,1], 12) #False
tournee1.fusionnable(tournee2, [2,1], 12) #True
tournee1.fusion(tournee2, [2,1])
tournee1.affiche() # tournee 0 4 3 2 1 0, chargement 11
# le parcours 0-4-3-2-1-0 est equivalent a 0-1-2-3-4-0

Partie II. Prise en compte du réseau

Partie III. Archivage de la position, de la vitesse

• 1.Plusieurs lectures peuvent avoir lieu en même temps,
• 2.Les écritures sont exclusives (sans lecture ni écriture en même temps),
• 3.En cas de choix, priorité aux lecteurs.

import threading
class Acces:
    def __init__(self):
        self.mutex = threading.Semaphore(value = 1)
    def debut_lecture():
        self.mutex.acquire() # P
    def fin_lecture():
        self.mutex.release() # V
    def debut_ecriture():
        self.mutex.acquire()
    def fin_ecriture():
        self.mutex.release()

# Pour une lecture
...
synchro.debut_lecture()
valeur = lecture(...)
synchro.fin_lecture()
...
# Pour une ecriture
...
synchro.debut_ecriture()
ecriture(...)
synchro.fin_ecriture()
...

Partie IV. Gestion de tournées

Figure 2 - Schéma relationnel de la base de donnée Gestion de tournées.

VEHICULE(*No_immatriculation(char(10)), Type(text), Capacite(float),
Date_mise_en_service(date))
TOURNEE(*No_tournee(int), Date(date), No_immatriculation(char(10)),
Code_conducteur(char(8)), Distance(float))
CONDUCTEUR(*Code_conducteur(char(8)), Nom(char(30)),
Prenom(char(40)), Telephone(texte), Date_embauche(date),
Permis(texte))

Figure 3 - Les permis poids lourd pour le transport de marchandises.

Partie V. Utilisation des éléments mobiles

Figure 4 - Application web : Visualisation de tournée, heure actuelle : 14h13.

<!DOCTYPE html>
<html>
    <head>
        <style>
                .ontime {
                    background-color: white;
                }
                .hurry {
                    background-color:lightgrey;
                }
                .late {
                    background-color: dimgray;
                }
                .done {
                    background-color: black;
                }
        </style>
    </head>
    <body>
            <!-- TODO -->
    </body>
</html>

<script>
let hours = document.querySelectorAll('.heure')
const d = new Date()
let heureActuelle = d.getHours()
//TODO
</script>

<script>
let rows = document.querySelectorAll(".row")
//TODO
</script>

<script>
let buttonMAJ = document.getElementById("maj")
//TODO
</script>

Rappels

• -element.innerHTML : la propriété Element.innerHTML de Element récupère ou définit la syntaxe HTML décrivant les descendants de l'élément.
• -EventTarget.addEventListener() : la méthode addEventListener() d'un EventTarget attache une fonction à appeler chaque fois que l'évènement spécifié est envoyé à la cible.
• -document.querySelector : la méthode querySelector() de l'interface Document renvoie le premier Element dans le document correspondant au sélecteur - ou groupe de sélecteurs - spécifié(s), ou null si aucune correspondance n'est trouvée.

Fondements de l'informatique

Partie I. Le cas d'un neurone à seuil

1 Fonction booléennes linéaires à seuil

2 Cas de domaines bornées

3 Apprentissage d'un neurone à seuil

• -à seuil nul lorsqu'on cherche à déterminer s'il existe F, une fonction linéaire à seuil comme ci-dessus, avec de plus F à seuil nul.
• -à exemples négatifs lorsque l'on a y_i = 0 pour tous les 1 ≤ i ≤ N.

Procedure apprentissage 
(n, X)
    for 
i ∈ {1, 2, …, n} do
        
w_i:=0
    repeat
        fin 
:=1;
        for 
x = (x_1, …, x_n) ∈ X do
            if 
∑_(i = 1)^n w_i x_i ≥ 0 then
                fin 
:=0;
                for 
i ∈ {1, 2, …, n} do
                    
w_i:=w_i − x_i
    until fin 
= 1;
    return 
(w_1, w_2, …, w_n, 0)

type vecteur = float array

Partie II. D'un neurone à seuil à un réseau de neurones

Voici un circuit booléen sur G = G_(bool) à 3 entrées et 3 sorties, de taille 4. Si l'on numérote les sorties de gauche à droite, il calcule une certaine fonction f : B^3 → B^3; on a par exemple f(0, 1, 0) = (1, 1, 0).

4 Des circuits booléens aux réseaux de neurones à seuil

type sommet = int
type seuil = float
type poids = float
type reseau_adjacence = ((sommet * poids) list * seuil) array

ajoute_arc : reseau_adjacence -> sommet -> sommet -> poids -> reseau_adjacence

On dit qu'un réseau de neurones est bien formé si chaque arc (u, v) de E est tel que si u appartient à la couche i, alors v appartient à la couche i + 1. Par exemple, un réseau qui aurait l'architecture (c'est-à-dire le graphe sous-jacent, les poids et seuils ne sont pas représentés) suivante est bien formé.

Ainsi, si l'exemple suivant représente deux couches consécutives (les nombres indiqués à côté des sommets étant les seuils associés, ceux à côté des arêtes les poids associés), la matrice associée à la seconde couche sera alors (0, 2; − 1, 1; 0, 3) et le vecteur ((− 1)/1).

type vecteur = float array
type matrice = float array array
type reseau_matrice = (matrice * vecteur) list

5 À propos des circuits booléens

• -une unique sortie, étiquetée par une porte AND généralisée ;
• -les entrées, ou les portes 0 et 1, qui ont leur(s) arc(s) sortant(s) qui vont soit vers une porte NOT_1, soit vers l'une des portes OR généralisées ;
• -les portes NOT_1 qui ont leur(s) arc(s)sortant(s) qui va vers une porte OR généralisée ;
• -les portes OR généralisées ont leur arc sortant qui va vers la porte AND généralisée.

6 À propos des réseaux de neurones à seuil à poids unitaires

Partie III. Complexité de l'apprentissage d'un circuit

Prouver que l'architecture ci-dessous est compatible avec ces 8 tâches.

Partie IV. Réseaux de neurones récurrents et automates finis

Par exemple, en partant du réseau R représenté en haut de la page 23, en considérant p = 2 et n = 2, on obtient l'architecture suivante (les différents types des arêtes, ordinaire, épais, et pointillés, sont là pour améliorer la lisibilité du graphe et n'ont pas de sémantique particulière).