مسابقة دكتوراه 2013 — Université Abdelhamid Mehri - Constantine 2 — الموضوع 02

Soit $X$ et $Y$ deux tableaux à $n$ éléments chacun ($X[1..n]$ et $Y[1..n]$) où $n = 2^k$ pour $k$ un entier naturel positif.

1. Ecrire une fonction $\textbf{SomProdPram}(X[1..n], Y[1..n], S)$ qui calcule en parallèle la somme des produits de deux tableaux unidimensionnels $A$ et $B$ en utilisant un PRAM (mémoire partagée). $S = X[1]^*Y[1] + X[2]^*Y[2] + \ldots + X[n]^*Y[n]$.

2. En utilisant la fonction $\textbf{SomProdPram}(\ldots)$, écrire une procédure $\textbf{ProdMatricePram}(A[1..n,1..p], B[1..p,1..m], C[1..n,1..m])$ qui calcule en parallèle le produit des deux matrices $A$ et $B$ dans la matrice $C$ en utilisant un PRAM (mémoire partagée).

Dans un laboratoire de recherche, on cherche à déterminer les concentrations de trois éléments $A$, $B$ et $C$ pour la fabrication d'un produit chimique. Les concentrations maximales et minimales des éléments sont comme suit :

Elément	Concentration maximale	Concentration minimale
A	1	45
B	2	45
C	1	30

La qualité du produit chimique dépend des concentrations utilisées et est régie par la fonction : $F = 0.78\alpha_1^2 + 0.52\alpha_2^2 + \alpha_1\alpha_2 + 1.2\alpha_3$ où $\alpha_1$, $\alpha_2$ et $\alpha_3$ sont les concentrations des éléments $A$, $B$ et $C$ respectivement. Des valeurs élevées de la fonction $F$ sont une indication de la bonne qualité du produit.

En utilisant un algorithme d'optimisation par essaim de particules, on se propose de déterminer les concentrations qui permettent d'obtenir un produit de la meilleure qualité possible. Formuler la tâche à résoudre comme un problème d'optimisation.

a. Proposer un codage de solution approprié. b. Ecrire un algorithme d'optimisation par essaim de particules permettant de résoudre ce problème en prenant soin de définir toutes les fonctions nécessaires devant être utilisées. c. Peut-on prédire à priori le résultat de l'algorithme ? Pourquoi ?