La Gazette n°11
Modérateur : Politburo
-
- Fonctionne à 300 bauds
- Messages : 104
- Enregistré le : 22 juil. 2016 09:59
- Localisation : Vanves (92)
- Contact :
Re: La Gazette n°11
Le poulpe n'étant plus là pour aider, je suggère de lancer un avis de recherche pour un programme sur pocket qui le remplace. Donc:
« Vous qui avez un programme pour pocket qui dispose de talents divinatoires, au moins pour le Mondial, manifestez-vous ici »
« Vous qui avez un programme pour pocket qui dispose de talents divinatoires, au moins pour le Mondial, manifestez-vous ici »
TI-57… et plus par affinité
La seule chose qui me manque vraiment sur PC-1500, c'est VNC. Dommage que le code source ait été conservé à la grande bibliothèque d'Alexandrie.
La seule chose qui me manque vraiment sur PC-1500, c'est VNC. Dommage que le code source ait été conservé à la grande bibliothèque d'Alexandrie.
- Marge
- Fonctionne à 14400 bauds
- Messages : 6190
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: La Gazette n°11
En effet, au mieux les deux équipes se rencontreront en demi-finale... en effaçant respectivement la Belgique et l'Uruguay, ce qui n'est pas rien !
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- rogeroge
- Fonctionne à 9600 bauds
- Messages : 4254
- Enregistré le : 14 mai 2010 21:41
- Localisation : Entre Nancy et Bercy : à Torcy
Re: La Gazette n°11
Le Brésil quitte le Mondial, j'ai donc perdu à 50 pour 100.
Il reste donc la France pour l'éventuelle finale.
Je reviens sur la Gazette 11.
La mise à jour a (enfin) commencé.
J'ai supprimé les hôtesses des pages de couverture, sommaire et éditorial car je ne suis pas sûr que les images sont libres de droits.
L'hôtesse de la page de couverture est déjà remplacée par une image libre de droits.
Il reste donc la France pour l'éventuelle finale.
Je reviens sur la Gazette 11.
La mise à jour a (enfin) commencé.
J'ai supprimé les hôtesses des pages de couverture, sommaire et éditorial car je ne suis pas sûr que les images sont libres de droits.
L'hôtesse de la page de couverture est déjà remplacée par une image libre de droits.
Il faut être fou pour venir sur ce site mais encore plus fou pour ne pas y revenir !
Re: La Gazette n°11
Bonjour,
Je me permets une remarque au sujet de votre article que je viens de lire par hasard, dans le numéro 10 de la gazette (page 93 du PDF).
Je vous informe que les longues soirées d'hiver resteront ennuyeuses puisque le problème "PART 2 en nombres entiers" ou "du sac à dos en nombres entiers avec valeur = poids" (noms parfois donnés dans la littérature au "Subset Sum Problem") est NP-Complet dit "faible", c'est à dire qu'il existe une résolution dite "pseudo-polynomiale", et qu'on peut donc trouver un algorithme très efficace (et même "glouton" : temps proportionnel au nombre de données en entrée) si on peut manipuler les nombres exprimés d'une façon particulière (laquelle peut être très couteuse en temps). En gros, il faut que les nombres entiers du problème "ne soient pas trop grands" (en fait, pour être exact, c'est la "somme à atteindre" qui ne doit pas être trop grande).
L'article wikipédia traitant du "Problème de la somme de sous-ensembles" évoque une résolution pseudo-polynomiale sans la dévoiler pour ce cas précis (l'article lié ne traite que d'un autre exemple).
Je m'y colle donc.
C'était un problème qu'on pouvait rencontrer quand on cherchait par exemple à "bourrer au maximum la face A d'une cassette audio" avec des morceaux de musique "pris dans une playlist", pour faire une compilation : on avait la durée de chaque morceau en secondes ... et la durée de la face complète (en secondes aussi : on la chronométrait si on voulait !) était la somme à approcher (sans la dépasser).
Bon, c'était un problème assez théorique ... en réalité, du fait de blancs de durée variable entre les morceaux, il valait mieux remplir au hasard et couper la fin de la bande avec des ciseaux quand on se rendait compte que le dernier morceau était tronqué
Je reviens au problème ... et aux deux/trois concepts qu'il faut manipuler pour le résoudre.
1) Si, à la place de stocker un nombre entier n (imaginons la durée "123 secondes") dans une variable numérique (codée en binaire), on stocke celle-ci sous la forme d'un tableau de n bits à "0" suivi par un bit à "1", on a une représentation beaucoup plus volumineuse mais "adaptée à notre problème" de ce nombre. On appelle ça une représentation "unaire" ou "en base 1". Le nombre 0 est représenté par le premier bit à "1". Par convention, on va dire que le premier bit est de rang 0 (on a un tableau indicé dont l'indice commence à 0).
On ajoute un autre nombre m à une telle représentation unaire en décalant le tableau de m bits : ainsi, on ajoute 3 à 123 en insérant trois "0" au début du nombre. On peut soustraire des nombres aussi facilement ...
2) Il est possible de stocker des "multi-nombres" de la même façon : on peut par exemple stocker 123 et 250 dans le même tableau. Il suffit de mettre à "1" les seuls bits d'indice 123 et 250. On obtient un "multi-nombre". On peut faire plein de choses sur les multi-nombres. C'est un outil très précieux en algorithmie. Il en existe des variantes très nombreuses.
Par convention, on va écrire qu'un multi-nombre est l'union de ses nombres constitutifs : par exemple, on peut considérer la conjonction "123 UNION 250".
On peut remarquer que nos multi-nombres ne sont pas capables de stocker "123 UNION 123" différemment de "123". Ce n'est pas un problème pour ce qu'on veut en faire dans notre algorithme, mais parfois, pour d'autres cas d'emploi, on a recours à des multi-nombres d'une complexité supérieure (tableaux d'entiers à la place de tableaux de bits ... et 1000 autres variantes permettant de suivre précisément certaines évolutions : multi-nombres d'ordre 2 stockés dans des bitmaps, etc ... c'est tout un monde qui s'ouvre et qui permet de repousser très loin les limites de la recherche opérationnelle si on a des prix chez le marchand de paracétamol, voire d'opiacés). Le problème du sac à dos général n'y résiste pas (par exemple), et, même quand on échoue à trouver la solution optimale, les heuristiques qu'on peut accrocher à des transpositions pseudo-polynomiales pourraient s'avérer efficaces.
On peut facilement construire la conjonction de deux ou de plusieurs nombres, et même de plusieurs multi-nombres : il suffit de construire un tableau de bits résultat en calculant un "OU logique" des bits de rang/index identique issus des tableaux respectifs de tous les nombres/multi-nombres unaires qu'on veut "unir". Un multi-nombre est un ensemble de nombres (avec juste une limitation : chaque valeur n'est présente qu'une fois)
3) Je précise qu'en représentation unaire, le seul problème est le volume des données à manipuler (et on peut se retrouver en présence d'un algorithme "NP-espace" si on lâche trop la bride): il faut décider de la taille du plus grand nombre qu'on veut gérer (pour dimensionner le tableau de bits). Ici, pour cet algorithme, on peut tranquillement se limiter à la somme s qu'on cherche à obtenir (en sommant un sous-ensemble de l'ensemble de nombres E).
Exemple : si on a un ensemble de 7 termes E = { 34, 27, 18, 76, 12, 7, 27 } et si on cherche si on peut sommer un sous-ensemble de E pour obtenir la somme s=123, on peut limiter la précision de toutes nos représentations en base 1 à disons 128 bits (ou même 124 bits si on veut être économe). On se fiche des bits qui "tombent dehors", au delà de cette capacité maximum (à l'occasion d'une somme par exemple). Sur un PC, on prendra la limite de DWORD immédiatement supérieure (on traitera z DWORD successifs, avec z = INT(s/32)+1 ). On insérera les bits et on "unira" les multi-nombres en utilisant des opérations binaires de décalage et des opérations booléennes sur DWORD non signés (très facile en C/C++). On peut même pousser jusqu'à 64 bits ...
L'algorithme est alors le suivant :
Code : Tout sélectionner
- On suppose qu'on a un ensemble E composé de nombres entiers {e1, e2, e3, ..., e?}, et une valeur entière s à atteindre (la somme souhaitée).
- On gère un registre multi-nombre, que l'on appelle "Résultat" et qu'on initialise à 0 (donc on met juste le bit d'indice 0 à "1" et les autres à 0)
- Pour chaque nombre entier e pris successivement dans l'ensemble de nombres E, on réalise une seule opération :
Résultat = (Résultat + e) UNION Résultat
Ici, le symbole "=" est une affectation, et le "+" est l'addition par décalage déjà présentée ci-dessus.
Le "UNION" est la fonction permettant de combiner deux multi-nombres.
- Une fois la boucle terminée (tout l'ensemble E a été traité), il suffit de regarder si le bit d'indice s du Résultat vaut "1". Si oui, alors il existe bien une somme de nombres de E valant s.
- Il suffit de parcourir le registre Résultat courant "à l'envers" (en commençant par les indices élevés) avec un indice i qui démarre à la valeur (s-e) et qui descend jusqu'à 0 (inclu).
- On stocke Résultat(i+e) = Résultat(i+e) OU Résultat(i). "OU" étant la fonction logique "OU booléen"
Évidemment, si on a "packé" les bits en octets ou double mots, et si on souhaite profiter d'une possibilité de traitement à l'échelle de cet octet ou double mot, cette opération sera un peu plus complexe à programmer, mais rien d'insurmontable (il faudra juste débugger la chose soigneusement, sans aucun a priori).
Si on voulait paraphraser l'algorithme, on dirait qu'on "construit le multi-nombre unissant les valeurs-sommes de tous les sous-ensembles de E". Pour chaque nombre de E pris en compte (de façon gloutonne), on fusionne les sommes auxquelles il participe, avec celles auxquelles il ne participe pas. Et, évidement, à chaque itération, le multi-nombre résultat double de cardinalité (ce n'est pas tout à fait exact : on a vu qu'on n'avait qu'un bit par valeur, et que "123 UNION 123" donnait un multi-nombre de cardinalité 1).
Si on veut savoir quels nombres participent à la somme, il faut stocker les registres Résultat intermédiaires, et effectuer une "remontée" à la recherche de l'origine du bit qu'on trouve à "1" dans le dernier résultat (ça se fait facilement puisqu'il vient d'un coté ou de l'autre de l'opération "UNION" précédente ... et ça reste très rapide, il faut juste beaucoup plus de mémoire).
On a un registre Résultat final, avec un bit à "1" à l'indice s.
On a également stocké tous les registres Résultat des étapes précédentes.
On va donc commencer par chercher d'où vient le bit à 1 ... en examinant l'avant dernier Résultat.
- Si dans l'avant dernier résultat, le bit d'indice s valait déjà "1", cela signifie que le "1" du résultat final venait de la partie droite de l'opérateur "UNION". Le dernier nombre de l'ensemble E (qu'on appellera "e?") ne fait pas partie de la somme. Dans ce cas, on peut directement remonter chercher la provenance du bit d'indice s dans le résultat précédent.
- Si dans l'avant dernier résultat, le bit de rang (s-e?) valait "1", alors on sait que le "1" trouvé dans le résultat final venait de la partie gauche de l'opérateur "UNION". Le dernier nombre e? de l'ensemble E fait donc partie de la somme qu'on cherche. Dans ce cas, on continue la remontée en cherchant la provenance du bit (s-e?) à l'étape précédente.
- Si les bits d'indice s et d'indice (s-e?) étaient déjà tous les deux à "1" dans le résultat précédent, cela signifie qu'on peut librement choisir si on veut une solution incluant le nombre e? ou pas : il y a plusieurs solutions possibles. En fonction de ce qu'on décide, on se comporte en conséquence (cf. les deux tirets précédents).
On remonte ainsi jusqu'au premier résultat stocké (la valeur initiale du registre, soit 0) ... et on obtient donc l'un des sous-ensemble de E dont la somme vaut s (si on remonte par récurrence, en explorant toutes les remontées possibles, on peut avoir tous les sous-ensemble résultat).
Si vraiment on ne veut pas s'embêter (mais l'algorithme a alors une complexité en O(n²) ou encore O(card(E)²) ), on recommence l'algorithme en enlevant à chaque fois un nombre de l'ensemble E. Si on n'arrive plus à la somme s suite à ce retrait, alors on remet le nombre ... sinon, on le laisse enlevé.
On fait ça pour chaque nombre et, donc, à la fin, E vaut les seuls nombres dont la somme vaut s.
On peut aussi remarquer que si le bit d'indice s ne vaut pas "1" dans le dernier résultat, on peut s'amuser à chercher "aux alentours de la valeur s", pour trouver, par exemple, la somme immédiatement inférieure à s.
Pour vous donner une idée de l'efficacité, sur un ordinateur moderne, je dirais qu'on peut traiter des ensembles E de 10 000 nombres, pour un registre résultat stocké dans un bloc mémoire de 100 ou 200 Mo ... ça fait donc des sommes de l'ordre du milliard. Le tout traité en environ une minute. Il n'y a donc aucun problème réel ici. Si on veut la somme précise, il faut disposer d'un espace de stockage conséquent (de l'ordre du teraoctet) et il faut ajouter le temps d'écriture et de relecture de ce stockage (on choisira sans doute une solution à 100 Go ou moins, ne stockant qu'un registre sur 10 ou sur 20, parce qu'on perdra sans doute moins de temps à recalculer les étapes intermédiaires en mémoire, dans 1 à 2 Go de RAM, qu'à faire des accès disque). Bon, sur une calculatrice des années 80 ... sans possibilité de gérer des tableaux de bits de façon efficace, il ne faudra pas attendre des miracles ... mais sur un ordinateur moderne, c'est un problème "level peanuts" dans tous les cas.
Et, de façon générale, même quand les nombres sont énormes ou "pas entiers" (et qu'on a peur de stocker des tableaux de bits trop grands), on peut, en pratique, toujours réduire un peu la précision du problème, en divisant tous les nombres du problème, puis en les arrondissant à l'entier le plus proche (on le fait avec le même rapport pour les nombres de E et pour la somme à trouver) par 10, 100 ou 1000.
Cet exemple fait partie des "fausses idées" qu'on peut se faire en informatique sur la complexité réelle des problèmes. Wikipédia, et donc la plupart des informaticiens, n'ont pas toujours accès à ces solutions (pourtant connues depuis assez longtemps, mais pas toujours présentées d'une façon "digérable" par le programmeur lambda moyen).
Je viens de voir qu'on peut trouver l'algorithme (dans une version un tout petit peu plus tolérante : elle gère les nombres négatifs ... elle est donc adaptée à de la comptabilité !) dans la version en anglais de wikipédia (article "Subset sum problem", paragraphe "Pseudo-polynomial time dynamic programming solution"). Si je la comprends facilement, je trouve néanmoins cette façon de présenter l'algo "totalement imbitable pour celui qui vient chercher un bout de code" : on ne sait même pas comment utiliser ce qu'on construit ... bref, rien ne vaut un peu de pseudo-code.
Je ne suis pas chercheur. Ces petits problèmes ne me sont pas posés par des donneurs d'ordres. Ce ne sont que des hobbies pour moi comme pour vous. D'une façon générale, je déplore que des articles scientifiques importants ne soient pas publiés sur internet, avec un accès immédiat et libre. L'info se trouve dans les revues et les actes de conférences (payants). Les guguss (dans mon genre) qui s'y intéressent en solo n'y ont pas accès. Parfois, certaines bases ne diffusent même pas dans les écoles ou sur wikipedia.
Bref, les algorithmes pseudo-polynomiaux ont une diffusion limitée, les explications sont rares et les usages aussi.
De la même façon, on peut trier pas mal de choses plus vite qu'en O(n.log(n)) ... il suffit de prendre le temps de programmer un "radix sort" exploitant une façon d'exprimer les grandeurs à comparer (les postiers trient tout le courrier selon le code postal en commençant par faire 10 tas selon le dernier chiffre, puis ils empilent tous les tas en mettant le tas "0" au dessus ... et retournent tout le paquet (ils prennent la dernière lettre en premier), et refont un tri selon l'avant dernier chiffre ... etc ... et ils finissent par le premier chiffre : au total ils prennent 5 fois en main chaque lettre, quel que soit le nombre de lettres à trier).
(le jeu n'en vaut que rarement la chandelle, et on préfère souvent trier les choses "de l'extérieur", en ne manipulant qu'une fonction de comparaison indiquant si A est plus grand ou plus petit que B. Pour un tri, l'espoir de gain est trop faible pour qu'on décortique le problème.)
De la même façon encore, votre petit dessin d'illustration (les cercles rouges) me rappelle qu'on peut calculer en O(n²) la surface totale occupée par n disques de tailles quelconques (et différentes) arbitrairement disposés sur un plan (alors qu'on peut se croire face à un problème NP-complet, donc au dessus de O(exp(n)) ). On peut le faire sans recourir à une discrétisation du plan (pas de "bitmap" : l'algorithme travaille en précision maximum, sans passer par des nombres entiers, ce n'est pas une transformation pseudo-polynomiale).
Enfin, les algorithmes ne sont pas brevetables ...
Et vive la programmation un peu structurée !
Cordialement.
Modifié en dernier par fiduce le 16 août 2018 23:45, modifié 10 fois.
Re: La Gazette n°11
Je joins ci-dessous un code VBA (qu'on peut ajouter à un module ordinaire associé à un document Word ou Excel ... j'utilise encore la version 2003 de ces logiciels, mais VBA a très peu évolué depuis).
Il reste proche du code publié dans la gazette (même tirage au sort des problèmes) et supporte des recherches avec "Nb de Valeurs = 100" et une somme à atteindre qui vaut "50% de la somme totale des nombres" en 2 secondes sur mon PC.
Au delà, la taille mémoire peut devenir trop faible (c'est du à la façon de construire le problème ... et au fait que la mémoire nécessaire évolue grosso modo en fonction du cube de Nb Valeur).
Évidemment, c'est codé avec les pieds (je stocke les bits dans des booléens ! ; je calcule tous les registres du début à la fin sans réfléchir ! ; etc ; etc)... dans un langage interprété ... Dans l'idéal, il faudrait commencer par retirer de l'ensemble E les valeurs plus grandes que la somme qu'on cherche à trouver (sinon ça bug). J'ai supposé que personne n'aurait l'idée de sommer des nombres entiers positifs plus grands que le total à obtenir
(ça peut arriver si on choisit un "% de la somme" très faible ... par exemple 10% ou 20% pour de 10 à 30 valeurs).
L'algorithme n'est pas optimisé du tout (mais à quoi bon ??? 2 secondes pour 100 valeurs ...).
Si j'avais un cas difficile à supporter, je passerais en C/C++ optimisé, et il y aurait du potentiel à remanier !
On remarque que les temps de recherche sont constants, même en tirant des valeurs comme on le fait (jusqu'au carré du nombre de valeurs), plus le nombre de valeurs augmente, plus il est fréquent de trouver une solution (pour garder les mêmes taux d'échec, il faudrait "sans doute" tirer des valeurs au hasard jusqu'à une borne supérieure variant comme une fonction exponentielle, au lieu de juste (Nb Valeurs)²).
Mais bon, j'arrête là sur ce problème (sauf si quelqu'un avait une question à poser).
(Je suis arrivé sur le site pour me renseigner sur l'utilisation qu'avait fait Kraftwerk d'une Casio FX-502P ... chose que j'avais lue en commentaire d'une vidéo sur youtube ! j'ai encore un FX-702P et un PB-770 d'époque, mais je ne vais pas coder cet algorithme là dessus sans que ma vie en dépende !)
Je donne un exemple d'exécution aussi (On démarre la macro en mettant le curseur dans son code et en appuyant sur [F5] ; et la sortie se fait dans la fenêtre "Exécution" de VBA) :
(100 valeurs, 20 cycles, 20% du total)
La version "sans remontée" de ce code (sans stockage des multi-nombres Résultat intermédiaires) permet d'aller jusqu'à au moins NbValeur = 300 ... avec des temps de traitement d'environ 45 secondes pour des sommes à 50% (ce qui s'explique : des valeurs 9 fois plus grandes que ci-dessus, 3 fois plus de nombres et une somme en % 2.5 fois plus élevée ... 9 x 3 x 2.5 = environ 60 fois les temps ci-dessus).
Je finis par une petite remarque concernant la mise en œuvre de l'algorithme de la gazette (que j'avais "trouvé pareil" de mon coté il y a 27 ans, suite à une question d'un camarde de service militaire ... 2 ans avant que je ne trouve l'algorithme que je présente en remplacement ... bon je cherchais à raison d'un jour par an environ ... et ensuite j'ai vite vu que je n'étais pas le premier ! ).
Les taux supérieurs à 50% pouvaient être traités par "le problème complémentaire" : par exemple, au lieu de chercher une somme atteignant 90% de la somme des nombres, on peut se contenter de chercher une somme atteignant 10% du total. En effet, si on complémente l'ensemble résultat, on résoud le problème complémentaire.
On peut donc commencer l'algorithme en comparant S à (T/2) : si S > (T/2) ... soit un taux de plus de 50% ... alors il vaut mieux chercher la solution pour (T-S).
(le 544,45 du tableau des durées de traitement se change alors en 2,41 !!!)
Cette remarque est évidemment valable aussi pour mon implémentation ! (je pourrais complémenter le problème quand le % est élevé, ce qui diminuerait la taille du registre Résultat)
Il reste proche du code publié dans la gazette (même tirage au sort des problèmes) et supporte des recherches avec "Nb de Valeurs = 100" et une somme à atteindre qui vaut "50% de la somme totale des nombres" en 2 secondes sur mon PC.
Au delà, la taille mémoire peut devenir trop faible (c'est du à la façon de construire le problème ... et au fait que la mémoire nécessaire évolue grosso modo en fonction du cube de Nb Valeur).
Évidemment, c'est codé avec les pieds (je stocke les bits dans des booléens ! ; je calcule tous les registres du début à la fin sans réfléchir ! ; etc ; etc)... dans un langage interprété ... Dans l'idéal, il faudrait commencer par retirer de l'ensemble E les valeurs plus grandes que la somme qu'on cherche à trouver (sinon ça bug). J'ai supposé que personne n'aurait l'idée de sommer des nombres entiers positifs plus grands que le total à obtenir
(ça peut arriver si on choisit un "% de la somme" très faible ... par exemple 10% ou 20% pour de 10 à 30 valeurs).
L'algorithme n'est pas optimisé du tout (mais à quoi bon ??? 2 secondes pour 100 valeurs ...).
Si j'avais un cas difficile à supporter, je passerais en C/C++ optimisé, et il y aurait du potentiel à remanier !
On remarque que les temps de recherche sont constants, même en tirant des valeurs comme on le fait (jusqu'au carré du nombre de valeurs), plus le nombre de valeurs augmente, plus il est fréquent de trouver une solution (pour garder les mêmes taux d'échec, il faudrait "sans doute" tirer des valeurs au hasard jusqu'à une borne supérieure variant comme une fonction exponentielle, au lieu de juste (Nb Valeurs)²).
Mais bon, j'arrête là sur ce problème (sauf si quelqu'un avait une question à poser).
(Je suis arrivé sur le site pour me renseigner sur l'utilisation qu'avait fait Kraftwerk d'une Casio FX-502P ... chose que j'avais lue en commentaire d'une vidéo sur youtube ! j'ai encore un FX-702P et un PB-770 d'époque, mais je ne vais pas coder cet algorithme là dessus sans que ma vie en dépende !)
Code : Tout sélectionner
Option Explicit ' On déclare toutes les variables avant de les utiliser
Option Base 0 ' Les indices des tableaux doivent débuter à 0
Sub Part()
Randomize
Dim NbVal As Integer
NbVal = InputBox(Prompt:="Nb de val ?")
Dim NbCycles As Integer
NbCycles = InputBox(Prompt:="Nb de cycles ?")
Dim PourcentTotal As Long
PourcentTotal = InputBox(Prompt:="% Total ?")
ReDim E(NbVal - 1) As Long ' Tableau des valeurs à sommer
Dim eI As Long ' Valeur courante
Dim L As Integer ' num du cycle courant
Dim I As Integer ' Variable indice réutilisé plusieur fois
Dim J As Long ' Variable indice réutilisé plusieur fois
Dim S As Long ' Somme des nombres du problème
Dim T As Long ' Total à atteindre
Dim TDebCycle As Single ' Heure de départ absolue d'un cycle (en secondes arrondies au 1/20ème)
Dim TDebRech As Single ' Heure de départ du seul algorithme de recherche (en secondes arrondies au 1/20ème)
Dim TDebRem As Single ' Heure de départ du seul algorithme de remontée, permettant de trouver les nombres participant à la somme (en secondes arrondies au 1/20ème)
Dim TFinCycle As Single ' Heure de fin de cycle (en secondes arrondies au 1/20ème)
Dim TRecherche As Double ' Durée de la recherche (en secondes arrondies au 1/20ème)
Dim TRemontée As Double ' Durée de la remontée (en secondes arrondies au 1/20ème)
Dim MinTRecherche As Double ' Durée minimum d'une recherche
Dim MaxTRecherche As Double ' Durée maximum d'une recherche
Dim MinTRemontée As Double ' Durée minimum d'une remontée
Dim MaxTRemontée As Double ' Durée maximum d'une remontée
Dim CumulTRecherche As Double ' Cumul des temps de recherche
Dim CumulTRecherche2 As Double ' Cumul des temps de recherche au carré (pour calcul d'un écart type)
Dim NbTrouvé As Integer ' Nombre de cycles ayant généré un problème avec une solution possible
Dim R() As Boolean ' Multi-nombres résultats (réalloué dynamiquement à chaque cycle ... ce qui l'initialise aussi à False)
For L = 1 To NbCycles
TDebCycle = Timer ' Instant de départ du cycle
' Création du problème
S = 0
For I = 0 To NbVal - 1
E(I) = Int(Rnd() * NbVal * NbVal + 1)
S = S + E(I)
Next I
T = Int((S * PourcentTotal) / 100) ' Total à atteindre
ReDim R(NbVal, T) As Boolean ' Multi-nombre résultat : les changement de premier indice permettent de conserver le registre après chaque itération dans E
' Recherche
TDebRech = Timer ' Instant de départ de la recherche
R(0, 0) = True
For I = 0 To NbVal - 1
eI = E(I)
For J = T - eI To 0 Step -1 ' On pourrait avancer au lieu de reculer ... mais ça ne fonctionnerait plus si on ne stockait pas les versions successives du registre (cas où on se contenterait de savoir si une somme, sans réaliser la remontée)
R(I + 1, J + eI) = R(I, J + eI) Or R(I, J)
Next J
Next I
TDebRem = Timer ' Instant de départ de la remontée
TRecherche = TDebRem - TDebRech
If (MinTRecherche = 0) Or (MinTRecherche > TRecherche) Then MinTRecherche = TRecherche
If MaxTRecherche < TRecherche Then MaxTRecherche = TRecherche
CumulTRecherche = CumulTRecherche + TRecherche
CumulTRecherche2 = CumulTRecherche2 + TRecherche * TRecherche
Debug.Print "Cycle n°"; L; " - Temps de recherche = "; Int(TRecherche * 20) / 20; " --> Somme à trouver T = "; T; " - Valeur de R("; T; ") = "; R(NbVal, T);
' La suite n'a pas de sens s'il n'y a pas de solution ...
If Not R(NbVal, T) Then
Debug.Print " --> Raté"
Else
Debug.Print " --> Chk !"
NbTrouvé = NbTrouvé + 1
' Remontée
Dim SommeCible As Long
SommeCible = T
Dim SommeVérif As Long
SommeVérif = 0
For I = NbVal - 1 To 0 Step -1
eI = E(I)
If R(I, SommeCible) Then
' eI peut ne pas faire partie de la solution ... on ne fait rien
ElseIf R(I, SommeCible - eI) Then
' eI doit faire partie de la solution
Debug.Print eI;
SommeVérif = SommeVérif + eI
SommeCible = SommeCible - eI
Else
Debug.Print "BUG : on ne trouve pas de remontée valide !!!"
End If
Next I
If SommeVérif <> T Then ' Improbable ... pour ne pas dire impossible
Debug.Print "Somme vérif est diférent de T !!!"
Else
Debug.Print "--> Somme Ok ="; SommeVérif
End If
TFinCycle = Timer ' Instant de Fin du cycle
TRemontée = TFinCycle - TDebRem
If (MinTRemontée = 0) Or (MinTRemontée > TRemontée) Then MinTRemontée = TRemontée
If MaxTRemontée < TRemontée Then MaxTRemontée = TRemontée
Debug.Print " Temps de remontée = "; Int(TRemontée * 20) / 20
End If
DoEvents
Next L
Debug.Print "Moyenne du temps de recherche = "; Int(100 * CumulTRecherche / NbCycles) / 100
Debug.Print "Ecart type du temps de recherche = "; Int(Sqr((CumulTRecherche2 / NbCycles) - (CumulTRecherche * CumulTRecherche) / (1# * NbCycles * NbCycles)) + 0.5)
Debug.Print "Nombre de problèmes résolus = "; NbTrouvé; "/"; NbCycles
Debug.Print "Durée des recherches comprises entre "; Int(MinTRecherche * 20) / 20; "s et "; Int(MaxTRecherche * 20) / 20; "s"
If NbTrouvé > 0 Then
Debug.Print "Durée des remontées comprises entre "; Int(MinTRemontée * 20) / 20; "s et "; Int(MaxTRemontée * 20) / 20; "s"
End If
End Sub
(100 valeurs, 20 cycles, 20% du total)
Code : Tout sélectionner
Cycle n° 1 - Temps de recherche = 0,85 --> Somme à trouver T = 101557 - Valeur de R( 101557 ) = Vrai --> Chk !
7662 8864 7182 1880 4205 9702 2515 8154 4707 2685 9801 1729 5543 3133 4941 6017 7390 3369 2078 --> Somme Ok = 101557
Temps de remontée = 0
Cycle n° 2 - Temps de recherche = 0,75 --> Somme à trouver T = 94010 - Valeur de R( 94010 ) = Vrai --> Chk !
9386 9141 331 4326 6322 6283 9212 4534 7481 3890 8248 7200 2944 1502 3406 2284 3718 3802 --> Somme Ok = 94010
Temps de remontée = 0
Cycle n° 3 - Temps de recherche = 0,85 --> Somme à trouver T = 105872 - Valeur de R( 105872 ) = Vrai --> Chk !
2475 5282 9821 7941 9315 9511 4853 2728 5287 8053 439 7095 8476 8915 7983 2791 870 1964 2073 --> Somme Ok = 105872
Temps de remontée = 0
Cycle n° 4 - Temps de recherche = 0,8 --> Somme à trouver T = 97454 - Valeur de R( 97454 ) = Vrai --> Chk !
9371 4697 4937 6610 6371 2685 7519 6848 6828 2819 5637 9215 74 5385 9235 9223 --> Somme Ok = 97454
Temps de remontée = 0
Cycle n° 5 - Temps de recherche = 0,85 --> Somme à trouver T = 105411 - Valeur de R( 105411 ) = Vrai --> Chk !
2279 9174 8742 2587 4128 6057 7524 5845 6593 9684 6776 3441 5779 2531 6798 8706 8767 --> Somme Ok = 105411
Temps de remontée = 0
Cycle n° 6 - Temps de recherche = 0,75 --> Somme à trouver T = 90608 - Valeur de R( 90608 ) = Vrai --> Chk !
7882 3493 5847 2318 34 3407 4589 4221 1197 4990 5922 504 3249 4868 4386 3486 1154 6767 9742 3871 8681 --> Somme Ok = 90608
Temps de remontée = 0
Cycle n° 7 - Temps de recherche = 0,85 --> Somme à trouver T = 103987 - Valeur de R( 103987 ) = Vrai --> Chk !
4124 5588 6975 9805 3945 8440 6015 4689 7045 6679 4389 8048 8188 6118 6754 7185 --> Somme Ok = 103987
Temps de remontée = 0
Cycle n° 8 - Temps de recherche = 0,75 --> Somme à trouver T = 94464 - Valeur de R( 94464 ) = Vrai --> Chk !
5711 8123 9237 9147 8434 2104 5375 2856 8964 5797 4404 4508 540 2965 7414 7859 1026 --> Somme Ok = 94464
Temps de remontée = 0
Cycle n° 9 - Temps de recherche = 0,75 --> Somme à trouver T = 90783 - Valeur de R( 90783 ) = Vrai --> Chk !
3854 7405 7627 1866 8044 9367 7956 6837 6995 9306 317 6561 2298 6069 23 6258 --> Somme Ok = 90783
Temps de remontée = 0
Cycle n° 10 - Temps de recherche = 0,8 --> Somme à trouver T = 97399 - Valeur de R( 97399 ) = Vrai --> Chk !
2559 5922 5913 7559 3199 715 9852 5243 1041 4980 1502 119 6219 6264 7570 6764 6392 5435 8632 1519 --> Somme Ok = 97399
Temps de remontée = 0
Cycle n° 11 - Temps de recherche = 0,8 --> Somme à trouver T = 98356 - Valeur de R( 98356 ) = Vrai --> Chk !
6208 7736 1034 4291 4323 1231 8186 8134 2695 8403 1429 7965 9962 4697 9310 1334 7597 3821 --> Somme Ok = 98356
Temps de remontée = 0
Cycle n° 12 - Temps de recherche = 0,8 --> Somme à trouver T = 97156 - Valeur de R( 97156 ) = Vrai --> Chk !
3584 7233 3967 1906 6047 9853 8947 8642 6184 5591 4593 9379 2202 7080 5124 6824 --> Somme Ok = 97156
Temps de remontée = 0
Cycle n° 13 - Temps de recherche = 0,8 --> Somme à trouver T = 96640 - Valeur de R( 96640 ) = Vrai --> Chk !
2760 7761 1659 8752 307 5218 1007 8896 7615 1629 505 6433 7832 9380 8400 5447 5357 6062 1620 --> Somme Ok = 96640
Temps de remontée = 0
Cycle n° 14 - Temps de recherche = 0,85 --> Somme à trouver T = 104857 - Valeur de R( 104857 ) = Vrai --> Chk !
9309 5076 5186 6263 1436 5159 783 5578 7659 5978 357 9106 7600 9275 4506 8490 9961 3122 13 --> Somme Ok = 104857
Temps de remontée = 0
Cycle n° 15 - Temps de recherche = 0,8 --> Somme à trouver T = 98945 - Valeur de R( 98945 ) = Vrai --> Chk !
1827 4698 6463 9472 9151 9034 1995 6492 7679 5624 9709 646 2571 27 8581 2822 922 1398 9532 302 --> Somme Ok = 98945
Temps de remontée = 0
Cycle n° 16 - Temps de recherche = 0,85 --> Somme à trouver T = 104997 - Valeur de R( 104997 ) = Vrai --> Chk !
9745 1508 8605 5670 9923 4150 6762 2954 8328 143 4954 6410 8585 8917 8588 4193 5562 --> Somme Ok = 104997
Temps de remontée = 0
Cycle n° 17 - Temps de recherche = 0,9 --> Somme à trouver T = 105951 - Valeur de R( 105951 ) = Vrai --> Chk !
723 4680 7656 7091 3799 5402 8692 7165 6665 4975 8449 5557 7724 9726 3884 9339 4424 --> Somme Ok = 105951
Temps de remontée = 0
Cycle n° 18 - Temps de recherche = 0,8 --> Somme à trouver T = 99449 - Valeur de R( 99449 ) = Vrai --> Chk !
5072 1906 9214 6154 8942 7932 3184 9711 5957 8081 1040 3068 9235 5993 4124 5480 4356 --> Somme Ok = 99449
Temps de remontée = 0
Cycle n° 19 - Temps de recherche = 0,8 --> Somme à trouver T = 95721 - Valeur de R( 95721 ) = Vrai --> Chk !
6247 6574 8055 2101 1253 1438 3978 9556 7569 8025 5566 1724 2406 3836 4543 371 8699 2637 3695 7448 --> Somme Ok = 95721
Temps de remontée = 0
Cycle n° 20 - Temps de recherche = 0,9 --> Somme à trouver T = 109459 - Valeur de R( 109459 ) = Vrai --> Chk !
5445 7742 7157 9859 6126 9547 6920 3360 4706 9204 3873 9131 2447 9166 4110 1248 732 8686 --> Somme Ok = 109459
Temps de remontée = 0
Moyenne du temps de recherche = 0,83
Ecart type du temps de recherche = 0
Nombre de problèmes résolus = 20 / 20
Durée des recherches comprises entre 0,75 s et 0,9 s
Durée des remontées comprises entre 0 s et 0 s
Je finis par une petite remarque concernant la mise en œuvre de l'algorithme de la gazette (que j'avais "trouvé pareil" de mon coté il y a 27 ans, suite à une question d'un camarde de service militaire ... 2 ans avant que je ne trouve l'algorithme que je présente en remplacement ... bon je cherchais à raison d'un jour par an environ ... et ensuite j'ai vite vu que je n'étais pas le premier ! ).
Les taux supérieurs à 50% pouvaient être traités par "le problème complémentaire" : par exemple, au lieu de chercher une somme atteignant 90% de la somme des nombres, on peut se contenter de chercher une somme atteignant 10% du total. En effet, si on complémente l'ensemble résultat, on résoud le problème complémentaire.
On peut donc commencer l'algorithme en comparant S à (T/2) : si S > (T/2) ... soit un taux de plus de 50% ... alors il vaut mieux chercher la solution pour (T-S).
(le 544,45 du tableau des durées de traitement se change alors en 2,41 !!!)
Cette remarque est évidemment valable aussi pour mon implémentation ! (je pourrais complémenter le problème quand le % est élevé, ce qui diminuerait la taille du registre Résultat)
Modifié en dernier par fiduce le 20 août 2018 04:53, modifié 12 fois.
Re: La Gazette n°11
Salut,
Y'a d'autres potes qui peuvent suivre
ton fil, enfin peut-être, comme Pir2 que je cite par
exemple, qu'il me pardonne...
En parallèle, la vitesse des ordi Z-80 égalaient
celle d'une tortue malade avec une seule patte, nos chéris portables encore plus lent,
Amibe en vitesse, mais Je fais beaucoup de prog c'est temps sur PC-1211/12, super rapide,
cette magnifique machine...
ste
Y'a d'autres potes qui peuvent suivre
ton fil, enfin peut-être, comme Pir2 que je cite par
exemple, qu'il me pardonne...
En parallèle, la vitesse des ordi Z-80 égalaient
celle d'une tortue malade avec une seule patte, nos chéris portables encore plus lent,
Amibe en vitesse, mais Je fais beaucoup de prog c'est temps sur PC-1211/12, super rapide,
cette magnifique machine...
ste
- Administrateur
- Messages : 5957
- Enregistré le : 24 mai 2002 16:55
- Localisation : Toulouse
- Contact :
Re: La Gazette n°11
Bonjour et bienvenue fiduce,
Pense aussi à faire un passage ici : http://silicium.org/forum/viewforum.php?f=49
A+
Pense aussi à faire un passage ici : http://silicium.org/forum/viewforum.php?f=49
A+
Re: La Gazette n°11
Avec des interlocuteurs comme çà, je me sens capable de tout ...
Quand j'aurai pris le temps de le rédiger, je proposerai peut-être pour la gazette un algorithme s'attaquant à problème un peu plus difficile, et qui n'a pas d'équivalent publié (à ma connaissance, vu comment ça a encore l'air de ramer dans certains milieux). Juste un peu de relaxation Lagrangienne contextuelle et quelques richochets. Pour passer l'étape du comité de lecture, et augmenter le plaisir des éventuels lecteurs, je tenterai une implémentation sous un émulateur quelconque. Peut-être que le PB-770 reprendra sa juste place devant le GRID5000 grâce à une anti-thèse anti-Bogdanovienne ?
Quand j'aurai pris le temps de le rédiger, je proposerai peut-être pour la gazette un algorithme s'attaquant à problème un peu plus difficile, et qui n'a pas d'équivalent publié (à ma connaissance, vu comment ça a encore l'air de ramer dans certains milieux). Juste un peu de relaxation Lagrangienne contextuelle et quelques richochets. Pour passer l'étape du comité de lecture, et augmenter le plaisir des éventuels lecteurs, je tenterai une implémentation sous un émulateur quelconque. Peut-être que le PB-770 reprendra sa juste place devant le GRID5000 grâce à une anti-thèse anti-Bogdanovienne ?
Modifié en dernier par fiduce le 15 août 2018 16:05, modifié 3 fois.
- Marge
- Fonctionne à 14400 bauds
- Messages : 6190
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: La Gazette n°11
Très bonne idée, ta prose volubile (et riche) mérite mieux qu'un monologue consulté difficilement sur un mobile... quelques illustrations seraient aussi bienvenues.fiduce a écrit : ↑15 août 2018 15:11 Avec des interlocuteurs comme çà, je me sens capable de tout ...
Quand j'aurai pris le temps de le rédiger, je proposerai peut-être pour la gazette un algorithme s'attaquant à problème un peu plus difficile, et qui n'a pas d'équivalent publié (à ma connaissance, vu comment ça a encore l'air de ramer dans certains milieux). Juste un peu de relaxation Lagrangienne contextuelle et quelques richochets. Pour passer l'étape du comité de lecture, et augmenter le plaisir des éventuels lecteurs, je tenterai une implémentation sous un émulateur quelconque. Peut-être que le PB-770 reprendra sa juste place devant le GRID5000 ...
Cela dit, tu sembles avoir du temps, car la 11 n'est toujours pas officiellement publiée.
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- rogeroge
- Fonctionne à 9600 bauds
- Messages : 4254
- Enregistré le : 14 mai 2010 21:41
- Localisation : Entre Nancy et Bercy : à Torcy
Re: La Gazette n°11
Exact !
Le parachèvement de la Gazette 11 est toujours en gestation.
Je ne promets plus rien pour une date mais dès la fin des vacances, je me remets au clavier.
Il faut être fou pour venir sur ce site mais encore plus fou pour ne pas y revenir !
- rogeroge
- Fonctionne à 9600 bauds
- Messages : 4254
- Enregistré le : 14 mai 2010 21:41
- Localisation : Entre Nancy et Bercy : à Torcy
Re: La Gazette n°11
La Gazette 11 est ENFIN presque terminée :
Quoique exploitable en l'état, elle est confiée à TiPoucet et Marge pour les ultimes éventuelles corrections.
Les liens d'URL seront traités par zpalm.
La mise à disposition sur le site Silicium est donc imminente !
Place à la Gazette n°12 : qui ouvre le fil de discussion ?
Les liens d'URL seront traités par zpalm.
La mise à disposition sur le site Silicium est donc imminente !
Place à la Gazette n°12 : qui ouvre le fil de discussion ?
Il faut être fou pour venir sur ce site mais encore plus fou pour ne pas y revenir !
-
- Fonctionne à 300 bauds
- Messages : 104
- Enregistré le : 22 juil. 2016 09:59
- Localisation : Vanves (92)
- Contact :
Re: La Gazette n°11
Le bonheur !
Un grand merci à tous les participants aux finitions !
Un grand merci à tous les participants aux finitions !
TI-57… et plus par affinité
La seule chose qui me manque vraiment sur PC-1500, c'est VNC. Dommage que le code source ait été conservé à la grande bibliothèque d'Alexandrie.
La seule chose qui me manque vraiment sur PC-1500, c'est VNC. Dommage que le code source ait été conservé à la grande bibliothèque d'Alexandrie.
- phm
- Fonctionne à 2400 bauds
- Messages : 1365
- Enregistré le : 08 avr. 2016 18:36
- Localisation : Est Parisien
Re: La Gazette n°11
HEWLETT-PACKARD : The best
CANON X-07 X-730 X-711 XR-100 XM-101 XP-110F XP-120F XP-130F XP-140
AMSTRAD CPC-464 CPC-6128 ATARI STF DAI Indata
CANON X-07 X-730 X-711 XR-100 XM-101 XP-110F XP-120F XP-130F XP-140
AMSTRAD CPC-464 CPC-6128 ATARI STF DAI Indata
Re: La Gazette n°11
Je la lirai avec intérêt.
Quand à l'article que j'envisageais de rédiger sur un exemple d'algorithme efficace, je l'ai programmé sur PC et je l'ai fait tourner sur quelques exemples test diffusés par une université spécialisée en recherche opérationnelle. Vu que j'ai trouvé assez rapidement des solutions meilleures que celles qui sont déjà connues (et qu'ils diffusent avec leurs jeux de test), j'ai essayé de les contacter il y a 3 semaines par mail pour qu'ils mettent à jour les solutions. Je n'ai pas eu de réponse pour le moment. J'attends la "fin de la rentrée" pour aviser.
Quand à l'article que j'envisageais de rédiger sur un exemple d'algorithme efficace, je l'ai programmé sur PC et je l'ai fait tourner sur quelques exemples test diffusés par une université spécialisée en recherche opérationnelle. Vu que j'ai trouvé assez rapidement des solutions meilleures que celles qui sont déjà connues (et qu'ils diffusent avec leurs jeux de test), j'ai essayé de les contacter il y a 3 semaines par mail pour qu'ils mettent à jour les solutions. Je n'ai pas eu de réponse pour le moment. J'attends la "fin de la rentrée" pour aviser.
- rogeroge
- Fonctionne à 9600 bauds
- Messages : 4254
- Enregistré le : 14 mai 2010 21:41
- Localisation : Entre Nancy et Bercy : à Torcy
Re: La Gazette n°11
(le message a été récupéré sur un autre fil : Pocketicaires 9
J'attends les inévitables corrections mercredi et vais les traiter illico car je ne pourrais plus consacrer de temps important sur la Gazette 11 avant le 11 novembre.
Si les modifications restent mineures de type insertion d'un caractère ou même deux, je peux traiter directement sur le PDF.
S'il s'agit de la refonte d'une page, je dois me retaper manuellement toute la Pagination avec ses liens et ça demande du temps...
Sinon, comme zplam finalise cette gazette provisoire, il lui incombera, à l'aide de ses puissants outils, de produire le document définitif et en particulier les liens d'URL pour devenir exploitable en totalité.
Il faut être fou pour venir sur ce site mais encore plus fou pour ne pas y revenir !