MARDI 26 AVRIL 2022
14h00-18h00
FILIERE MP - Epreuve n
INFORMATIQUE A (XULSR)
Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Cette composition ne concerne qu'une partie des candidats de la filière MP, les autres candidats effectuant simultanément la composition de Physique et Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.
Différentiation algorithmique
Le sujet comporte 12 pages, numérotées de 1 à 12.
Début de l'épreuve.
Dans ce sujet, on s'intéresse au problème de la différentiation algorithmique. Il s'agit de calculer efficacement des différentielles d'expressions mathématiques vues comme des composées de fonctions élémentaires. C'est l'une des pierres fondatrices du calcul formel, ainsi que de la descente de gradient dans les réseaux de neurones.
Ce sujet est constitué de cinq parties. La première partie est formée de préliminaires utiles dans le reste du sujet, mais les fonctions qui y sont définies peuvent être admises pour traiter les parties suivantes. La troisième partie est largement indépendante de la deuxième, à l'exception de la question III.7. La quatrième partie nécessite d'avoir compris les enjeux de la troisième partie. Enfin, la cinquième et dernière partie est nettement indépendante du reste du sujet, seule les questions V. 1 et V. 2 font référence aux sujets abordés avant.
Notations et définitions
On note la base canonique de (pour un entier strictement positif), de sorte que pour tout .
Pour une fonction , on note pour la projection de sur la coordonnée .
Pour une fonction (avec ), on note la différentielle de la fonction en un point évaluée en un vecteur (cette notation présuppose que est différentiable en ). On rappelle que la fonction est linéaire en son argument .
On rappelle également la règle de la chaîne : pour et , on a :
où représente la composition de fonctions.
On note également la dérivée de en suivant le vecteur de la base canonique ; pour et par linéarité de la différentielle, on a donc :
On note l'ensemble des matrices à lignes, colonnes, et coefficients dans . On supposera toujours .
Pour , la matrice jacobienne d'une fonction en un point , notée , est la matrice de définie par :
En appliquant la règle de la chaîne, on observe que pour deux fonctions et et pour un point , on a : .
Complexité
Par complexité en temps d'un algorithme , on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc.) nécessaires à l'exécution de dans le cas le pire.
Par complexité en mémoire d'un algorithme , on entend l'espace mémoire total utilisé par l'exécution de dans le cas le pire, en supposant que l'espace mémoire occupé pour stocker une valeur d'un type de base (entier, booléen, flottant, caractère) est une constante.
Lorsque la complexité (en temps ou en espace) dépend d'un paramètre , on dit que a une complexité (en temps ou en espace) en s'il existe une constante telle que, pour toutes les valeurs de suffisamment grandes (c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètre , la complexité (en temps ou en espace) est au plus ; on dit que a une complexité (en temps ou en espace) en s'il existe une constante telle que, pour toutes les valeurs de suffisamment grandes, pour toute instance du problème de paramètre , la complexité (en temps ou en espace) est au moins . Enfin, on a une complexité en quand elle est à la fois en et en .
Quand l'on demande la complexité d'un algorithme, il s'agit de trouver une expression en la plus simple possible. On dit qu'un algorithme est linéaire en si sa complexité en temps est en .
Rappels OCaml
On rappelle les opérations de base sur les nombres en virgule flottante (ou flottants), que l'on utilisera pour représenter des nombres réels dans OCaml :
1.0 et 0.0 (ou 1 . et 0 .) représentent les nombres 1 et 0 respectivement.
L'addition entre deux flottants a et b s'écrit .
La multiplication entre deux flottants a et b s'écrit . b .
On rappelle quelques opérations de base sur les tableaux :
Array.length: 'a array -> int donne la longueur d'un tableau.
Array.make: int -> 'a -> 'a array permet de créer un tableau: Array.make m r crée un tableau de taille dont toutes les cases sont initialisées à .
Array.make_matrix: int -> int -> 'a -> 'a array array permet de créer une matrice : Array.make_matrix m n r crée une matrice de taille dont toutes les cases sont initialisées à .
Enfin, une opération de base sur les listes :
List.rev: 'a list -> 'a list renvoie le miroir de la liste passée en argument (cette fonction a une complexité linéaire en la taille de la liste).
Dans l'ensemble du sujet, il sera fréquemment question de matrices de flottants. Pour simplifier l'écriture du type des fonctions manipulant de telles matrices, nous définissons le type matrix :
type matrix = float array array;;
Partie I
Question I.1. Donner une fonction OCaml
identite: int -> matrix
prenant en entrée un entier et renvoyant la matrice identité de .
Question I.2. Donner une fonction OCaml
scalaire: float array -> float array -> float
prenant en entrée deux vecteurs et et renvoyant le produit scalaire .
Question I.3. Donner une fonction OCaml
mul_possible: matrix -> matrix -> bool
prenant en entrée deux matrices et et renvoyant true si et seulement si les dimensions de et sont telles que est bien définie.
Question I.4. Donner une fonction OCaml
mul: matrix -> matrix -> matrix
qui calcule le produit des deux matrices et de flottants passées en argument. Si est de dimension et de dimension , on impose que la fonction mul effectue multiplications de flottants.
Dans l'ensemble du sujet, on utilisera la fonction mul à chaque fois qu'il s'agit de calculer le produit de deux matrices, sans chercher à rendre ce calcul plus efficace.
Partie II
Dans cette partie, on s'intéresse à la multiplication d'une suite finie de matrices réelles . Soit la suite finie d'entiers tels que . On cherche à écrire un programme effectuant le parenthésage optimal sur les pour un calcul efficace de leur multiplication . Pour chaque , on note le produit de matrices , et le nombre minimum de multiplications de flottants nécessaires pour calculer . On rappelle que l'on réutilisera la fonction mul de la partie précédente implémentant la multiplication de deux matrices, que l'on ne cherchera pas à améliorer.
Question II.1. On suppose (dans cette question uniquement) . Comparer le nombre de multiplications de flottants effectuées en évaluant avec mul et en évaluant avec mul. Que faut-il en conclure sur l'ordre d'évaluation du produit ?
Question II.2. Donner une fonction OCaml
muld: matrix list -> matrix
qui prend en entrée une liste non vide de matrices ( ) et renvoie leur multiplication (en utilisant mul) via un parenthésage à droite : .
Question II.3. Donner une fonction OCaml
mulg: matrix list -> matrix
qui prend en entrée une liste non vide de matrices ( ) et renvoie leur multiplication (en utilisant mul) via un parenthésage à gauche : .
Question II.4. Donner une fonction OCaml min_mul: int array int, qui prend en entrée le tableau des tailles de chacune des matrices, et renvoie en faisant des appels récursifs pour calculer les , sans stockage d'information supplémentaire. Montrer que si, pour tout , la complexité en temps de min_mul est au moins exponentielle en , c'est-à-dire en .
Question II.5. Donner une fonction OCaml min_mul_opt: int array -> int qui calcule le même nombre, mais où une matrice auxiliaire de taille , initialement nulle, permet de stocker les valeurs de déjà calculées. Quelle est la complexité en temps de min_mul_opt en fonction de ? En espace?
Question II.6. Donner une fonction OCaml mul_opt: matrix array matrix qui prend en entrée le tableau des matrices et calcule en multiplications de flottants.
Partie III
On se propose d'étudier deux manières de calculer la différentiation de la composition d'une liste de fonctions. Soient des fonctions de type pour . On note . Il s'agit d'optimiser le calcul successif de la valeur de et de celle de sa différentielle en un point. On note la matrice jacobienne de en . Pour tout , on note la fonction
Question III.1. Pour une fonction avec , on note la fonction :
Si on impose que le domaine de la fonction est pour un certain , quels sont l'ensemble de départ (domaine) et l'ensemble d'arrivée (codomaine) de la fonction ? Montrer que l'opérateur vérifie :
Question III.2. Pour deux fonctions et et un point , montrer que .
Question III.3. Donner une fonction OCaml forward de type :
renvoyant la jacobienne d'une fonction en un point passé en argument, et calcule la matrice représentant via un parenthésage à droite de la forme . On s'appuiera sur la définition de et sur la propriété établie à l'aide de la question précédente. On pourra s'aider d'une fonction récursive auxiliaire. Prouver la correction de cette fonction.
Question III.4. Quelle est la complexité en temps de cette fonction dans le cas où ? Dans le cas où pour tout avec une constante quelconque? On supposera que les appels à la fonction diff se font en temps proportionnel à la taille de la matrice jacobienne renvoyée par cette fonction.
Question III.5. Donner une fonction backward de type identique à forward qui prend en entrée un point , une liste de fonctions de type , et une fonction
renvoyant la jacobienne d'une fonction en un point passé en argument, et calcule la matrice représentant via un parenthésage à gauche de la forme .
Question III.6. Pour une liste de fonctions de longueur arbitraire, donner un exemple de cas où backward est plus efficace que forward, ainsi que de cas où forward est plus efficace que backward.
Question III.7. Sans écrire explicitement de fonction, expliquer comment adapter les techniques des questions de la partie II pour écrire une fonction diff_opt qui prend en entrée , une liste de fonctions de type , et un tableau de fonctions et calcule avec un minimum de multiplications de flottants la matrice jacobienne de en .
Partie IV
La représentation d'une suite d'instructions mathématiques comme une composition de fonctions est assez peu concise. En particulier, elle ne tient pas compte des dépendances linéaires entre les instructions. Considérons par exemple la fonction :
On peut l'écrire comme une composition avec :
Propager la différentielle des fonctions pour est une perte de temps. En effet, on manipule des fonctions qui ne font pas usage de certaines de leur variables, et on différencie des fonctions potentiellement linéaires, comme la fonction . On peut représenter plus finement les suites d'instructions mathématiques comme des graphes acycliques. Par exemple, la fonction ci-dessus se dessine comme suit :
On décrit un tel graphe comme un tableau de sommets. Chaque sommet contient deux informations : la fonction élémentaire qu'il représente et le tableau de ses prédécesseurs (les sommets tels qu'il y a une arête de à ). Comme le graphe est acyclique, on peut faire l'hypothèse que s'il y a une arête de à , l'indice de dans est strictement inférieur à l'indice de dans . On suppose par ailleurs que l'on ne manipule que des fonctions élémentaires à valeurs réelles . Ces fonctions élémentaires sont alors représentées par une paire de type (float array float) * (float array -> float array), où le deuxième élément représente la différentielle du premier élément (comme la fonction est à valeurs réelles, sa différentielle en un point est représentée directement par un vecteur et non par une matrice). On définit donc les types OCaml suivants :
type fonction_elementaire =
(float array -> float) * (float array -> float array);;
type sommet_avant = {fct : fonction_elementaire; pred : int array};;
type graphe_avant = sommet_avant array;;
Lors du calcul par propagation avant de la différentielle d'une fonction, on parcourt le graphe de cette fonction de la gauche vers la droite, c'est-à-dire des sommets correspondant aux variables au sommet correspondant à la fonction complète, en traitant les prédécesseurs
d'un sommet avant celui-ci. On stocke dans un tableau de propagation avant, au fur et à mesure, les valeurs de chaque fonction élémentaire et de sa différentielle en les points pertinents. Pour les sommets d'un graphe de fonction correspondant aux variables, le contenu du champ fct n'importe pas, car ils n'ont pas de prédécesseurs.
On peut par exemple coder le graphe de la fonction exemple comme suit :
let mafonction =
let id t = t.(0) in
let did t = [|1.|] in
let cube t = (t.(0)) ** 3. in
let dcube t = [|3. *. ((t.(0)) ** 2.)|] in
let scaler t = sqrt 2. *. (t.(0)) in
let dscaler t = [|sqrt 2.|] in
let costab t = (cos (t.(0))) in
let dcostab t = [| -1. *. sin (t.(0)) |] in
let carre t = (t.(0)) ** 2. in
let dcarre t = [|2. *. t.(0)|] in
let mult t = t.(0) *. t.(1) in
let dmult t = [|t.(1);t.(0)|] in
let plus t = t.(0) +. t.(1) in
let dplus t = [|1.;1.|] in
let n0 : sommet_avant = {fct = (id,did); pred = [| |]} in
let n2 : sommet_avant = {fct = (costab, dcostab); pred = [|O|]} in
let n3 : sommet_avant = {fct = (carre , dcarre); pred = [|2|]} in
let n4 : sommet_avant = {fct = (cube, dcube); pred = [|2|]} in
let n5 : sommet_avant = {fct = (scaler, dscaler); pred = [|1|]} in
let n6 : sommet_avant = {fct = (mult , dmult); pred = [|4;5|]} in
let n7 : sommet_avant = {fct = (plus , dplus); pred = [|3;6|]} in
[|n0;n0;n2;n3;n4;n5;n6;n7|];;
Question IV.1. On souhaite calculer la valeur de la différentielle de la fonction en évaluée en le point . Pour ce faire, calculer à la main l'ensemble des valeurs du tableau de propagation avant en détaillant le calcul. Les trois premières lignes du tableau sont :
Indice
Fonction
Valeur
Différentielle
0
1
1
1
1
2
Question IV.2 Donner une fonction intermédiaire OCaml
prenant en entrée un tableau de propagation avant (c'est-à-dire un tableau de couples (valeur_fonction, valeur_différentielle)), un tableau de indices de sommets et renvoyant un couple formé :
d'un vecteur des valeurs de fonctions dans correspondant aux sommets de ;
d'un vecteur des valeurs de différentielles dans correspondant aux sommets de .
Pour l'exemple de la fonction , les trois premiers éléments du tableau sont de la forme :
prenant en entrée un graphe représentant une fonction , un tableau représentant un point , un tableau représentant un vecteur , et qui calcule par propagation avant le flottant .
Question IV.4. On voudrait traiter de manière particulière les fonctions linéaires, comme la dernière opération et la première opération dans l'exemple ci-dessus, car elles sont leur propres différentielles et peuvent donc être traitées plus simplement qu'une fonction arbitraire. Comment peut-on modifier la structure du graphe de la fonction dans ce sens?
Partie V
Une triangulation d'un polygone correspond à la partition du polygone en triangles dont les sommets sont des sommets du polygone.
Question V.1. On considère des polygones convexes dont chaque sommet est étiqueté par un poids (entier naturel non nul). On définit le coût d'un triangle comme le produit des poids des trois sommets, et le coût d'une triangulation d'un polygone comme la somme des coûts de tous ses triangles. Montrer que le nombre minimum de multiplications de flottants nécessaires pour calculer la multiplication de matrices (au sens de la partie II) est égal au coût minimum d'une triangulation d'un certain polygone convexe.
Question V.2. On reprend les notations de la partie II : soit une suite de matrices de flottants et la suite d'entiers tels que . On suppose de plus . Montrer que le nombre minimal de multiplications de flottants nécessaires au calcul de est égal au nombre minimal de multiplications de flottants nécessaires au calcul de .
Oublions désormais les poids sur les sommets de la triangulation d'un polygone. On représente un polygone comme un tableau de points dans . Il y a une arête entre deux sommets successifs du tableau, ainsi qu'entre la première et la dernière valeur.
type polygone = (float * float) array
Un polygone est dit simple si deux arêtes non consécutives ne se croisent pas, et deux arêtes consécutives n'ont en commun que l'un de leurs sommets. On ne considéra que des polygones simples et on ne cherchera pas à vérifier leur simplicité.
Polygone simple
Polygone non-simple
On formalise la triangulation d'un polygone comme une liste d'arêtes à ajouter au polygone. Les sommets du polygone sont désignés par leur place dans le tableau représentant le polygone : le premier sommet est celui en position 0 dans le tableau, etc. Une arête entre le -ème sommet du polygone et le -ème sommet est décrite comme un couple d'entiers ( ) avec .
Question V.3. Donner une fonction OCaml testant la convexité d'un polygone simple :
est_convexe: polygone -> bool.
Indication : On pourra utiliser l'orientation de produits vectoriels de vecteurs bien choisis.
Question V.4. Combien d'arêtes la triangulation d'un polygone convexe à cotés introduitelle? Justifier.
Question V.5. Donner une fonction OCaml
triangule_convexe: polygone -> (int * int) list
qui prend en entrée un polygone supposé convexe et renvoie une triangulation de ce polygone sous la forme d'une liste d'arêtes en un temps linéaire en le nombre de sommets du polygone.
On considère désormais des polygones non-convexes. Un polygone simple est dit strictement monotone par rapport à l'axe des ordonnées si toute ligne horizontale ne coupe le polygone qu'en au plus deux points.
Polygone simple strictement monotone
Polygone simple non strictement monotone
Ainsi, si on imagine un point se déplaçant le long d'un polygone simple, de son sommet le plus haut vers son sommet le plus bas, il ne fera que descendre ou se déplacer horizontalement, jamais il ne remontera.
Question V.6. Donner une fonction OCaml
separe_polygone: polygone -> int list * int list
qui prend en entrée un polygone simple strictement monotone et sépare ses sommets (représentés par leurs indices) en deux listes, l'une contenant les sommets du plus haut (inclus) vers le plus bas (exclus) en suivant l'un des deux chemins à partir du sommet le plus haut, l'autre les sommets du plus haut (exclus) vers le plus bas (inclus) en suivant l'autre chemin. Ainsi, tout sommet du polygone doit être classé une et une seule fois dans l'une des listes en sortie, et chaque liste est triée par ordre décroissant de deuxième coordonnée. La fonction donnée doit être linéaire en le nombre de sommets du polygone.
Question V.7. Proposer un algorithme qui prend en entrée un polygone supposé simple strictement monotone et renvoie une triangulation de ce polygone en un temps linéaire en le nombre de sommets du polygone. Cet algorithme pourra commencer par utiliser l'algorithme implémenté par la fonction separe_polygone.
Fin du sujet.
X ENS Option Informatique MP 2022 - Version Web LaTeX | WikiPrépa | WikiPrépa
