Challenge mathématique #41 : Réduction d’amplitude d’un signal

[emmanuel-fr]

Voici le défi de février basé sur une réflexion par algorithme. Le but est de réduire l’amplitude d’un signal venant d’une suite de nombres que l’on ajoute.

Voici une suite de valeurs de départ [1, -6, -2, -1, 4, 4, -3]. A chaque instant vous ne pouvez prendre uniquement que la valeur la plus à droite ou la plus à gauche pour l’ajouter à la précédente. Au départ le signal est à 0. Le but est de faire en sorte que l’amplitude maximale soit la plus faible en ajoutant toutes les valeurs.

Par exemple si on prend comme valeurs [1, -6, -3, 4, 4, -2, -1] en les ajoutant dans ordre nous avons a+1, a-5, a-8, a-4, a, a-2, a-3 soit au maximum a-8 et a+1 et une amplitude minimale de 9.

Il faudra donc prendre les bonnes décisions pour les choix des valeurs extrêmes de droite et gauche pour avoir une suite dans un ordre bien précis. Pour [1, -6, -2, -1, 4, 4, -3] la solution est [-3, 4, 1, -6, 4, -1, -2] ce qui donne a-3, a+1, a+2, a-4, a, a-1, a-3 et une amplitude de 6. Plusieurs solutions sont possibles qui donne des amplitudes minimales identiques, aussi il faudra toujours sélectionner la valeur la plus à droite dans les choix avant de retourner le résultat final. (Essayez en commençant par 1).

Pour LabVIEW, les valeurs seront des entiers entre -99 et 99 et la liste d’entrée un tableau de maximum 50 valeurs. La sortie sera donc un tableau mis dans l’ordre ainsi qu’un indicateur avec l’amplitude minimale en entrée et sortie.

La valeur de vérification, autre que celle proposée en exemple sera donnée ultérieurement.

Vous pouvez vous servir du code joint comme point de départ (Version LabVIEW 2010)

Un Livre LabVIEW  2eme édition est à gagner. Le gagnant sera tiré au sort (basé sur les sorties du loto) sur les codes validés.

Envoyez votre code renommé Ch41_Amplitude_votre pseudo_ici.vi à emmanuel.roset@ni.com avant le 28 février. Et postez sur la communauté « code envoyé » pour vérifier la boite email en cas de non réception.

Bon défi remue-méninges

[Sebastien_D]

Bonjour à tous,

Voilà en effet un beau défi algorithmique ! J'ai déjà une petite question :

Si je comprends bien, on peut décaler les éléments du tableau d'entrée à souhait afin que l'amplitude finale soit minimale. Dans ce cas-là, quel est l'intérêt de pouvoir additionner à l'amplitude (à l'instant t) soit le chiffre tout à gauche, soit le chiffre tout à droite ? Autant les placer dans le bon ordre, de gauche à droite, directement, non ?

Et du coup je ne comprends pas trop la condition du choix de la "bonne" solution dans le cas de multiples solutions.

Voilà, merci d'avance pour les réponses et bonne chance !

[Michael.C]

Ouch, effectivement celui là promet encore de bonnes entorses neuronales 😄

[emmanuel-fr]

Ca parait compliqué à la lecture mais en le faisant sur papier on se rend compte que c'est faisable car on ne prend que les extrêmes et et il n'y a pas à tout réorganiser.

[emmanuel-fr]

Sebastien_D

Pour répondre a votre question, en effet en théorie on pourrait manipuler n'importe quel élément mais ce n'est pas ce qui est demandé. Il s'agit d'un exercice qui oblige a sélectionner soit l'élément le plus a droite soit le plus a gauche et à l'additionner au résultat précédent. Si on additionne plusieurs éléments négatifs de suite par exemple on va s'éloigner du minimal qui est zéro, mais stratégiquement cela peut être une bonne chose pour compenser une grosse valeur positive par la suite.

[Sebastien_D]

Bonjour,

Merci pour les précisions, je m'étais embarqué dans quelque chose de différent effectivement ! Une autre question me vient alors concernant ce passage :

"Plusieurs solutions sont possibles qui donne des amplitudes minimales identiques, aussi il faudra toujours sélectionner la valeur la plus à droite dans les choix avant de retourner le résultat final. (Essayez en commençant par 1)."

je ne suis pas sûr de bien comprendre ce passage. Si l'on reprned l'exemple donné (input [1, -6, -2, -1, 4, 4, -3], solution  [-3, 4, 1, -6, 4, -1, -2]), on pourrait aussi noter la solution DDGGDDD (D=chiffre pris à droite, G=chiffre pris à gauche).

Qu'est ce que signifie "valeur la plus à droite" ? La solution avec le plus de "D" dans la combinaison ? Et s'il y en a plusieurs qui ont le même nombre de D (je ne sais pas si c'est possible, mais à priori oui), laquelle privilégier ?

Merci d'avance pour la réponse, je crois que j'aurai tout compris après 😄

[emmanuel-fr]

Pas de soucis pour les questions et merci de relever le défi !

Si on commence par 1 et non pas par -3 au départ avec [1, -6, -2, -1, 4, 4, -3] le résultat serai [1, -3, 4, -6, 4, -1, -2] avec  a+1, a-2, a+2, a-4, a, a-1, a-3 et donc une amplitude également de 6. Comme le résultat est identique il est demandé de choisir l'ordre qui privilégie le choix le plus à droite, idem pour les deux dernières valeurs -1, -2 qui sont égales à -2, -1.

Ceci pour permettra d'avoir le même résultat pour tous afin de comparer plus facilement les tableaux.

[Michael.C]

Bonjour, Tout d'abord merci aux équipes d'avoir remis un peu d'ordre dans la rubrique challenge :), plus qu'à corriger le retour à la ligne, juste pour être sur d'avoir bien compris par rapport au calcul d'amplitude, quand j'ouvre ton VI d'exemple, je trouve une amplitude maximum de 8 et non 9 comme enregistré par défaut. J'ai bon ? Ou c'est que je comprends même pas le cas de base ^^

[emmanuel-fr]

En fait il ne s'agit pas de la valeur maximale négative ou positive mais l'amplitude entre les extrêmes. Si on prend [1, -6, -2, -1, 4, 4, -3] l'amplitude résultante dans l'ordre est [+1, -5, -7, -8, -4, 0, -3] soit de +1 à -8 donc une amplitude de 9. Dans la solution on va de +2 à -4 donc l'amplitude est 6.

Chez moi le retour à la ligne ne pose pas de problème.

[Michael.C]

Ok, donc j'ai bien fait de poser la question, j'avais pas compris cela :D. Ben moi ça ne veut toujours pas aller à la ligne, sachant que je n'ai pas ce souci dans les autres sections du forum.

[PhilB58]

Bingo, j'ai une solution
Quelqu'un a-t-il une autre série de valeurs en entrée pour comparer les résultats en sortie????

[Sebastien_D]

@PhilB58, j'ai déjà un programme fonctionnel à 90% qui teste toutes les possibilités en brute-force et renvoie l'amplitude minimale et pour quelles combinaisons elle est atteinte. Il ne me reste pas grand chose à faire pour trouver LA bonne solution spécifiée dans les consignes. Mais avant de continuer, je voulais savoir, est ce que tu utilises la brute-force ( est dans ce cas là je finis mon programme) ou une méthode plus subtile (à laquelle je n'ai pas encore pensé du coup 😞 ).

[Sebastien_D]

En fait je viens de finir mon programme, et mes résultats lèvent une nouvelle question. Si j'avais bien compris, lorsqu'il y a plusieurs solution, il convient de choisir celle qui comporte le plus "d'additions par la droite" (je me suis peut-être trompé là-dessus, je ne suis pas sûr d'avoir bien interprété ce qu'Emmanuel avait dit "choisir l'ordre qui privilégie le choix le plus à droite").
Donc si je continue sur cette hypothèse, mon programme a trouvé une autre solution, qui est 1, -3, 4, -6, 4, -1, -2, qui a bien pour amplitude 6 et qui comporte 5 additions par la droite, comme la solution donnée par Emmanuel [-3, 4, 1, -6, 4, -1, -2]. 
Voilà, soit je n'ai toujours pas compris le but, soit il y a effectivement des doublons (voire des triplons, des quadruplons...) de solution !

[PhilB58]

Bon, j'ai crié bingo trop tôt
Je me suis fait une série de nombres (positifs et négatifs) et j'ai fait tourner mon programme, je n'obtiens pas la meilleure solution (trouvée mentalement), donc, je dois revoir ma copie et ajouter des critères dans les choix successifs.

De plus, l'info est dans un message d'Emmanuel mais je l'avais zappée, il faut privilégier TOUS les nombres les plus à droite, pour autant que la réduction d'amplitude reste maximale, j'ai donc encore du taf!

Sebastien_D, je ne sais pas à quoi tu fais allusion par "la brute-force", et non, je ne frappe pas sur mon ordi
Et pour ajouter une info, oui, sans doute existe-t-il des doublons, mais pas beaucoup à mon sans car le challenge impose de prendre les nombres les plus à droite, ça réduit grandement la marge de manoeuvre.

[Sebastien_D]

Par brute-force, j'entends, tester toutes les combinaisons possibles avec une séquence de N nombres (donc 2^N) jusqu'à trouver la bonne, sans réelle "intelligence" dans la recherche.

Une fois de plus, je pense que je n'ai pas compris le critère de sélection de la solution, mais d'après moi il y a (au moins) trois solutions pour l'exemple d'Emmanuel [1, -6, -2, -1, 4, 4, -3], qui sont
1, -3, 4, -6, -1, -2

1, -3, 4, -6, 4, -1, -2

-3, 4, 1, -6, 4, -1, -2

Les trois donnent une amplitude de 6, et utilisent toutes 5 additions par la droite (et donc 2 additions par la gauche). D'après ce que j'ai compris, il s'agit normalement de prendre la solution qui comporte le plus d'aditions par la droite, mais apparemment je me trompe complètement!

[PhilB58]

Pas évident en effet, d'autant plus que le tableau dans le Vi proposé est vertical, difficile dans ces conditions de trouver une valeur plus à droite que l'autre
Cela dit, il faut comprendre que les valeurs les plus à droite sont celles vers la fin du tableau d'entrée, enfin, si j'ai bien compris.

Pour la réponse, s'il en existe plusieurs, il faut préivilégier celle(s) qui commence(nt) par le dernier chiffre du tableau (condition élémentaire, le plus à droite), et ensuite, s'il y en a plusieurs (de solutions), celles(s) qui utilisent en addition de préférence les chiffres en fin de tableau (à droite donc), sachant qu'inévitablement, il faudra utiliser les chiffres en début de tableau (à gauche) à un moment ou un autre

Maintenant, la solution qui privilégie une addition en commencant à gauche et allant vers la droite ne donnera jamais un résultat acceptable de réduction de signal, sauf si les chiffres du tableau d'entrée sont déjà optimisés en terme de position.

Maintenant, j'ai peut-être pas tout compris non plus

[emmanuel-fr]

Je pense qu'il ne faut pas chercher à faire encore plus complexe. Et il n'est pas possible de changer les positions des valeurs du tableau. (en effet gauche = haut dans l'exemple et droite = bas). En commencant par 1 les choix qui suivent sont uniquement de 2 valeurs possibles donc on choisi celle qui s'éloigne le moins du minimum possible. Puis en cas de choix identique sur le résultat du minimum en cours, choisir la valeur la plus a droite... Tout est comme fait à la main (et à l'esprit). Par contre la valeur de départ compte dans le choix le plus a droite ou pas.

Les essais par force brute peut marcher aussi mais je pense que le temps de recherche peut être beaucoup plus long.

Maintenant, il est encore possible d'optimiser avec les N+c (coups d'avance). Et ainsi voir si la valeur minimale est encore optimisable ou pas suivant les décisions faites N-c. Mais ceci sera compté comme un challenge optionnel. Le défi est remporté déjà si les valeurs de sortie sont identiques pour tous et comparables à coup sur. Il n'y a qu'une seule séquence de résultat pour cet algorithme.

J'espère avoir aidé

[PhilB58]

Bonjour Emmanuel,

ne pourrait-on pas prolonger ce challenge de 2 ou 3 jours, ce mois-ci étant plus court

J'ai eu du mal pour ce challenge, déjà qu'il n'est pas simple (enfin, je ne l'ai pas trouvé simple), mais j'ai eu une charge de travail très importante ce mois-ci, et je n'avais plus LabView chez moi, ayant changé de pc, je n'ai pu l'installer que ce we

J'ai une idée à essayer pour finaliser mon code, peut-être que j'y arriverai pas, mais pour aujourd'hui, faut oublier je n'aurai de toute façon pas le temps

Merci

[emmanuel-fr]

Oui bien sur pas de problème, on repousse jusqu'à vendredi soir le 4. Le mois prochain il sera plus facile

[PhilB58]

Merci
J'espère y arriver, mais c'est pas encore certain, des fois, on a une idée qui se profile, mais pour concrétiser en terme de code, c'est pas toujours évident!

[Michael.C]

Bon, j'ai eu un peu de temps libre aujourd'hui, j'ai trouver un code, qui donne une solution, mais pas celle en priorisant la droite :D aller on va voir si on a le temps de pousser un peu sur la dernière ligne droite.

[Michael.C]

Code envoyé. Si quelqu'un a une autre valeur de départ à proposer pour être sur de mon code, je suis preneur.

[PhilB58]

Mon code est bouclé, j'ai eu un peu de temps cet après-midi et je crois que je le tiens 🙂 avec priorisation des valeurs de droite 🙂 (ce fut l'aspect le plus difficile).

Désolé Michael.C, je n'ai pas repris mon vi avec moi (il est resté au boulot), je ne peux donc pas faire de test pour comparaison, mais ça m'aurais arrangé car, si mon code semble tenir la route, il reste un doute tout de même

On voit ça jeudi (je suis en congé demain), il me restera ce test comparatif, et puis aussi de la cosmétique, surtout pour le diagramme, le commenter correctement et passer le message pour que tout le monde comprenne ce que j'ai voulu faire 🙂
Mais curieusement, je trouve que le diagramme est plus simple que tout ce que j'ai essayé auparavant pour m'en sortir  comme quoi, parfois, laisser de côté un peu pour décanter, c'est bénéfique 

[Michael.C]

Personnellement, je me suis excusé dans le mail de la qualité du diagramme, j'ai pondu ça en 30 min dans une pause au boulot, et la qualité du code est lien d'être exemplaire.

[PhilB58]

Voilà, j'ai testé avec d'autres valeurs d'entrée:
[5, -3, 1, 2, 3, -5, 6] et j'obtiens pour solution [6, 5, -5, 3, 2, -3, 1] avec une amplitude en entrée de 7 et en sortie de 5 (en ne tenant pas compte de la valeur 0 initiale puisque ne faisant pas partie du signal d'entrée, mais je peux corriger si nécessaire)

[PhilB58]

Une petite copie d'écran ...

[Michael.C]

Merci de l'information, ça montre que mon code est faux :(... Si j'ai le temps j'essayerais de corriger avant la date de fin.

[emmanuel-fr]

En effet c'est troublant au début mais les valeurs résultantes sont toutes positives dans l'exemple et l'amplitude est le delta entre le min et le max de a. Pas évident à réaliser et a tester. J'ai hâte de voir le code

[PhilB58]

Houla, ne t'emballe pas trop, c'est peut-être moi qui ai tout faux

Je ne tiens pas compte du 0 initial, je fais peut-être déjà une erreur (Emmanuel pourrait lever le doute), puis je suis loin d'avoir épuisé toutes les possibilités en entrée, donc, je peux encore tomber sur un os!!!

[PhilB58]

Code envoyé

[Michael.C]

Non je suis sur que mon code est faux, j'ai une amplitude de sortie plus grande que l'amplitude de départ :D, et personnellement, je suis d'accord avec le fait qu'il ne faut pas tenir compte du zéro.

[PhilB58]

Attention tout de même, si je tiens compte du 0 initial, j'ai aussi une amplitude supérieure en sortie, donc, mon code est faux également!
Mais si tu n'en tiens pas compte et que ton amplitude est plus grande, oui, il doit y avoir un soucis quelque part.

PS: je suis content, on peut modifier un message maintenant, si j'avais su ça avant, j'aurais éviter les doublons successifs!! Enfin, le formum évolue, et en bien

[PhilB58]

Pas de gagnant pour ce challenge??
C'est quand le tirage au sort??

[Michael.C]

Ca sera pas moi c'est sur 😄

[emmanuel-fr]

A priori j'ai reçu 2 codes. Celui de PhilB58 et celui de Michael C.

Exact ?

[PhilB58]

oui, je pense, j'avais fait une fouille pour recenser les code envoyés, j'étais étonne du peu 

[Michael.C]

J'en ai l'impression aussi, sachant que mon code n'a rien à sauver.... Il fonctionne pas et la qualité du diagramme est .... Donc pas de temps à perdre dessus.

[PhilB58]

Bon, le tirage au sort va être facile alors

[emmanuel-fr]

Michael C et Phil58. Comme vous avez beaucoup travaillé tous les deux (même si le code n'est pas parfait), et que je dispose de deux livres, alors vous méritez tous les deux un exemplaire.

Envoyez moi une adresse de livraison sur mon email : emmanuel.roset@ni.com

Maintenant les défis ont un autre gain avec un abonnement d'un an au magasine Programmez

[PhilB58]

Merci Emmanuel, c'est sympa
Je t'envoie mon adresse!!!

[Michael.C]

Merci du geste :), j'essayerais quand même de plancer encore à l'occasion sur la question pour trouver une réponse 😄