- Pangramme autodescriptif
-
Un pangramme autodescriptif est une phrase contenant toutes les lettres de l'alphabet (pangramme) et exprimant une proposition vraie sur elle-même (autodescriptif).
Sommaire
Exemples
« Ce pangramme autodescriptif en hommage à Douglas Hofstadter, Lee Sallows, Jacques Pitrat, Nicolas Graner et Éric Angelini contient exactement dix-sept a, un b, onze c, huit d, trente-cinq e, cinq f, neuf g, six h, vingt-quatre i, deux j, un k, sept l, six m, vingt-six n, onze o, huit p, huit q, onze r, quinze s, vingt-sept t, dix-sept u, quatre v, deux w, neuf x, un y, et cinq z. »
— oulipo
Comment trouver un pangramme autodescriptif ?
Le plus simple est d'utiliser un ordinateur, et un sous-programme ou une table qui puisse associer à chaque entier entre 0 et par exemple 50 son écriture en toutes lettres. Il suffit alors
- de tirer au hasard 26 nombres, soit 1 pour chaque lettre,
- de faire exprimer en lettres ce que l'on a tiré (« douze a, deux b », etc.)
- de compter le nombre d'occurrence de chaque lettre, et, s'il n'y a pas conformité, de recommencer l'opération avec ces 26 nouveaux nombres.
- s'il y a conformité, en revanche, imprimer le résultat.
Méthode empirique
Avec un peu de chance, on peut tomber ainsi sur un point fixe. Si on n'en a pas trouvé un au bout de, par exemple, 200 itérations, on peut soupçonner être dans un cycle. Le plus simple est de tirer à nouveau 26 autres valeurs et de retenter sa chance. En laissant travailler sa machine toute la nuit, on trouve quelques pangrammes autodescriptifs le matin en se levant. Se retrouve dans le domaine de l'électro-dynamique industrielle et relève un peu de la méthode essais et erreurs utilisée principalement pour trouver le PID (proportionnelle dérivée intégrale) de la machine.
Méthodes plus rigoureuses
Slow-fast
Il existe une méthode de détection de cycle qui se nomme méthode du slow-fast. Elle consiste grosso modo à faire le calcul en double à des vitesses différentes (le tableau A aura par exemple une itération par cycle et le tableau B deux itérations par cycle). Si à un moment quelconque A=B, comme 1 ne peut être égal à 2, cela signifie qu'à coup sûr on est entré dans un cycle.
Signatures
On peut calculer pour chaque tableau que l'on obtient une signature (par exemple CRC ou MD5), et conserver à la fois tous les anciens tableaux et toutes les signatures associées. On ne procèdera à une comparaison réelle de tableaux que si leurs signatures sont identiques. Si les tableaux sont également identiques, alors on tire d'autres valeurs pour le calcul.
Cette méthode est plus rapide à mettre en place comme à exécuter que le slow-fast, surtout dans un langage qui comme le Perl possède l'adressage associatif (hashs). Elle consomme davantage de place en mémoire aussi, mais les mémoires actuelles d'un gigaoctet et plus ne rendent pas cette question aussi critique que par le passé.
Voir aussi
Wikimedia Foundation. 2010.
