La Gazette n°11

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
ChocolatCroissant
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 104
Enregistré le : 22 juil. 2016 09:59
Localisation : Vanves (92)
Contact :

Re: La Gazette n°11

Message par ChocolatCroissant »

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 »
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.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: La Gazette n°11

Message par Marge »

rogeroge a écrit : 03 juil. 2018 12:06
ChocolatCroissant a écrit : 03 juil. 2018 12:01 Le mondial 2018, le 2022, le… ?
Celui de la finale Brésil-France de cette année ! :lol: :lol: :lol:
Mais je peux me tromper... :mrgreen:
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é.
Avatar du membre
rogeroge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4227
Enregistré le : 14 mai 2010 21:41
Localisation : Entre Nancy et Bercy : à Torcy

Re: La Gazette n°11

Message par rogeroge »

Le Brésil quitte le Mondial, j'ai donc perdu à 50 pour 100. :?
Il reste donc la France pour l'éventuelle finale. :roll:
Je reviens sur la Gazette 11. 8)
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 !
fiduce
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 7
Enregistré le : 11 août 2018 18:24

Re: La Gazette n°11

Message par fiduce »

caloubugs a écrit : 16 mai 2018 11:24 mes articles ne me plaisent pas pour le moment et je les garde pour la n°12. 88 pages, c'est déjà pas mal de lecture !
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.
Avant toute chose, on peut remarquer que le codage de la seule opération de cet algorithme peut se faire sans registre intermédiaire ... et même sans rien décaler du tout :
- 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.
fiduce
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 7
Enregistré le : 11 août 2018 18:24

Re: La Gazette n°11

Message par fiduce »

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 !)

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

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)

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
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)
Modifié en dernier par fiduce le 20 août 2018 04:53, modifié 12 fois.
Avatar du membre
steste
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 551
Enregistré le : 18 sept. 2015 18:59

Re: La Gazette n°11

Message par steste »

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
Avatar du membre
Pocket
Administrateur
Administrateur
Messages : 5941
Enregistré le : 24 mai 2002 16:55
Localisation : Toulouse
Contact :

Re: La Gazette n°11

Message par Pocket »

Bonjour et bienvenue fiduce,

Pense aussi à faire un passage ici : http://silicium.org/forum/viewforum.php?f=49

A+
Pocket, voit tout, sait tout, lit l'avenir dans les entrailles d'une base phpBB ...
Image
fiduce
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 7
Enregistré le : 11 août 2018 18:24

Re: La Gazette n°11

Message par fiduce »

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 ?
Modifié en dernier par fiduce le 15 août 2018 16:05, modifié 3 fois.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: La Gazette n°11

Message par Marge »

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 ...
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.
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é.
Avatar du membre
rogeroge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4227
Enregistré le : 14 mai 2010 21:41
Localisation : Entre Nancy et Bercy : à Torcy

Re: La Gazette n°11

Message par rogeroge »

Marge a écrit : 15 août 2018 15:50 .........
Cela dit, tu sembles avoir du temps, car la 11 n'est toujours pas officiellement publiée.
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 !
Avatar du membre
rogeroge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4227
Enregistré le : 14 mai 2010 21:41
Localisation : Entre Nancy et Bercy : à Torcy

Re: La Gazette n°11

Message par rogeroge »

La Gazette 11 est ENFIN presque terminée :
IconeCouvertureOctobre.jpg
IconeCouvertureOctobre.jpg (11.51 Kio) Vu 9850 fois
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 ?
Il faut être fou pour venir sur ce site mais encore plus fou pour ne pas y revenir !
ChocolatCroissant
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 104
Enregistré le : 22 juil. 2016 09:59
Localisation : Vanves (92)
Contact :

Re: La Gazette n°11

Message par ChocolatCroissant »

Le bonheur !
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.
Avatar du membre
phm
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1361
Enregistré le : 08 avr. 2016 18:36
Localisation : Est Parisien

Re: La Gazette n°11

Message par phm »

:D
:slime:
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
fiduce
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 7
Enregistré le : 11 août 2018 18:24

Re: La Gazette n°11

Message par fiduce »

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.
Avatar du membre
rogeroge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4227
Enregistré le : 14 mai 2010 21:41
Localisation : Entre Nancy et Bercy : à Torcy

Re: La Gazette n°11

Message par rogeroge »

Marge a écrit : 14 oct. 2018 23:55 .....
Désolé de ne pas encore avoir terminé la correction de la Gazette 11 qui aurait pu compenser l'absence de beaucoup à ce grand rendez-vous, j'espère livrer ma version vers mercredi.
.....
@+
(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 !
Répondre

Retourner vers « Tous les Pockets »