Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
274 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Parcours optimal de n-uplets

Envoyé par Jean-Armand Moroni 
Parcours optimal de n-uplets
il y a six semaines
Bonjour
Voici un problème d'optimisation, qui revient dans différents cas pratiques (application : cf. plus bas). J'espère être dans le bon forum.

On se place dans l'ensemble des $n$-uplets de booléens (ou des sommets d'un hypercube à $n$ dimensions si vous préférez), notés $(a_i)_{i=1..n}$.
Soit $p < 2^n$. On souhaite choisir $p$ éléments de cet ensemble, de façon à optimiser $\sum_{i=1}^n c_i d_i$,
où $c_i$ est une suite décroissante de poids (réels positifs), et $d_i$ est la somme des nombres de valeurs différentes prises par chaque $i$-uplet de $a_j$ dans les $n$-uplets choisis.
Comment choisit-on les $n$-uplets ? Dans quelle mesure ce choix optimal dépend-il des $a_i$ ? Au cas où on ne connaît pas $p$ à l'avance, peut-on construire une suite de $n$-uplets qui soit constamment optimale, ou au moins "pas trop mauvaise" ?

Exemple avec $n = 3$ et $p = 4$ :
On choisit $(0,0,1), (1,0,0), (1,0,1), (1,1,0)$, ça donne
$d_1 = 6$ : $a_1$, $a_2$, $a_3$ prennent chacun les deux valeurs 0 et 1
$d_2 = 9$ : on a 9 couples de $a_i a_{j\neq i}$ sur les 12 possibles : $(0,0,-), (1,0,-), (1,1,-), (0,-,1), (1, -, 0), (1, -, 1), (-, 0,0), (-,0,1), (-,1,0)$.
$d_3 = p = 4$.

Application : on teste un logiciel. On suppose que le fonctionnement du logiciel dépend de $n$ booléens (configuration des modules optionnels, flags de compilation...). On peut effectuer $p$ tests. On souhaite les répartir de manière à maximiser la probabilité de détecter un bug. On suppose que le comportement du logiciel dépend principalement (coeff $a_1$) de chaque booléen, un peu moins de leurs combinaisons 2 à 2 (coeff $a_2$ inférieur à $a_1$), encore moins de leurs combinaisons 3 à 3 (coeff $a_3$ inférieur à $a_2$), etc.

J'ai aussi une autre application en tête, un peu longue à expliquer.
Je pourrai vous dire dans un prochain message comment je choisis les $n$-uplets, mais vous ne perdez rien, ça ne repose sur rien de rigoureux. smiling smiley



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Parcours optimal de n-uplets
il y a six semaines
Bonjour,

C'est le vaste domaine des "plans d'expérience" : [fr.wikipedia.org]
S'il n'y a pas d'interactions entre tes facteurs, tu peux penser aux matrices de Hadamard.
Re: Parcours optimal de n-uplets
il y a six semaines
Merci !
Je ne connaissais pas l'expression "plans d'expérience", et donc je ne trouvais pas de référence.
Avec l'article Wikipedia et tout ce vers quoi il pointe, j'ai de la lecture. Parfait !
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 246, Messages: 1 507 403, Utilisateurs: 27 667.
Notre dernier utilisateur inscrit Setif.


Ce forum
Discussions: 889, Messages: 7 538.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page