Exprimer ... autrement

Je n'ai pas eu le temps de remettre cette activité au goût du jour depuis plusieurs années, mais il demeure que certains trucs intéressants peuvent être trouvés sur la présente page.

Cliquez ici pour le problème de la session H2006. Des données complémentaires sur les palindromes (ou en périphérie) sont gracieusement offertes ici (merci à Michel Séguin!). Pour voir les solutions proposées à ce petit défi, cliquez ici.

Cliquez ici pour le problème de la session H2004. Pour voir les solutions proposées à ce petit défi (même livrées après échéance), cliquez ici.

Ce qui suit détaille un petit concours que je vous propose, comme ça, juste pour le plaisir. Pour en connaître l'inspiration, cliquez ici. Mon chic, brillant et stimulant collègue Michel Séguin (aujourd'hui à la retraite... Snif!) me souligne qu'il y a des corrélations à faire entre les idées exprimées ici et l'intéressante stratégie de pensée latérale (Lateral Thinking), sur laquelle je vous invite à lire.

Il existe plusieurs manière d'exprimer une idée. Un algorithme peut en être une; une équation ou une inéquation en sont d'autres; un poème; de la prose; une peinture; un chant; une danse; une sculpture sont tous des moyens d'expression.

Supposons par exemple qu'on désire résoudre le problème suivant : calculer la somme de un à N où N est un entier strictement positif. De prime abord, un certain nombre de solutions peuvent être proposées (question : selon vous, parmi les solutions B, C, D et E, laquelle sera la plus rapide à l'exécution? Laquelle sera la moins coûteuse en espace?) :

(A)

Pseudocode

 
Fonction somme_un_a(N)
   Si N = 1 Alors
      Résultat ← 1
   Sinon
      Résultat ← N + somme_un_a(N-1)
   somme_un_a ← Résultat
(B)

Code C++ récursif

 
int somme_un_a(int n) {
   int resultat;
   if (n == 1)
      resultat = 1;
   else
      resultat = n + somme_un_a(n-1);
   return resultat;
}
(C)

Code C++ récursif compact

 
int somme_un_a(int n) {
   return n == 1? 1 : n + somme_un_a(n-1);
}
(D)

Code C++ itératif

 
int somme_un_a(int n) {
   int resultat = 0;
   for(int i = 1; i <= n; ++i)
      resultat += i;
   return resultat;
}
(E)

Code C++ récursif à la compilation (un peu de métaprogrammation)

 
template <int N>
   struct somme_un_a {
      enum {
         value = N + somme_un_a<N-1>::value
      };
   };
template <>
   struct somme_un_a<1> {
      enum { value = 1 };
   };
(F)

Compact et rapide; merci à Carl Friedrich Gauss.

Merci aussi à Simon Renaud-Deputter, étudiant en informatique de gestion au Collège Lionel-Groulx à l'hiver 2007 qui m'a souligné une erreur de parenthèses dans la formulation originale

 
int somme_un_a(int n) {
   return (1 + n) * n / 2;
}
(G)

Équation mathématique

 \[ f(n) = \frac{(n)(n+1)} {2}\]
(H)

Description en français... Croyez-le ou non, historiquement, les démonstrations mathématiques verbeuses comme l'expression à droite étaient la norme

Pour résoudre le problème du calcul de la somme de un à N, N étant un entier strictement positif, il convient de vérifier la valeur de N; en effet, si N vaut un, alors le résultat du calcul est aussi clairement un. Dans le cas où N diffère de un, on dira que le résultat du calcul est la valeur de N à laquelle on ajoute le résultat du calcul de la somme de un à N moins un.
(I)

Morphogramme (de la version itérative de la solution)
(J)

Petit simili poème en anglais (je n'ai pas de prétention littéraire ici, on s'entend; je donne des exemples).

Dear N. If you are one, then let it all be one and no more but should you be more than one, then, dear N, let it be you, of course, plus the sum of those that came before.
(H)

Michel Séguin m'envoie cette chouette note :

« Le Triangle de Pascal, utilisé pour décrire le nombre de chemins allant de (A) à une intersection donnée, sans remonter de niveau, présente une configuration dont les valeurs témoignent de la somme des premiers entiers.  »

La note était accompagnée du schéma à droite (remarquez que chaque ligne constitue un palindrome).

 
         Départ A
            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1
1   6  15  20  15   6   1

Comme on peut le constater, la plupart des solutions proposées ci-dessus sont de nature informatique (parfois à la frontière des mathématiques), mais pas toutes. On peut, clairement, exprimer une même idée de plusieurs manières différentes. Ce que je vous propose, donc, est un petit défi intellectuel.

Michel Séguin, toujours alerte, me signale ce charmant poème qui constitue une illustration merveilleuse de ce que nous cherchons à explorer ici.

Problème de la session H2006

Soit l'algorithme ci-dessous pour vérifier si une séquence déterminée par les itérateurs premier et dernier (ne tenez compte que de la fonction générique en caractères gras) constitue un palindrome :

// ref.: http://public.research.att.com/~bs/popl06.pdf
// prudence: fin de séquence hors norme (dernier doit être
// un élément valide de la séquence).
template <class It>
   bool palindrome(It premier, It dernier) {
      if (dernier <= premier) // point milieu
         return true;
      else if (*premier != *dernier) // asymétrie
         return false;
      else
         return palindrome(++premier, --dernier); // récursivité
   }

template <class It, class E>
   It trouver_element(It it, const E &elem) {
      while (*itt != elem) ++it;
      return it;
   }

#include <iostream>
#include <algorithm>
void afficher_palindrome(const char *p) {
   using namespace std;
   if (palindrome(p, trouver_element(p, '\0')-1))
      cout << p << endl;
}

int main() {
   using namespace std;
   const char *mots[] = {
      "laval",
      "roger",
      "cesar -- rasec"
   };
   for_each(begin(mots), end(mots), afficher_palindrome);
}

Pouvez-vous exprimer le même algorithme dans une langue ou à l'aide d'un moyen d'expression qui :

Pour que votre soumission soit recevable, il faut que la conformité avec l'algorithme puisse être vérifiée par un professeur du département d'informatique du Collège (moi, probablement) et que la qualité artistique, esthétique, linguistique ou autre associée à votre oeuvre puisse être validée par un professeur du Collège dans la discipline correspondante (p.ex. si vous faites une sculpture, il faut qu'un professeur au département d'arts plastiques confirme que votre oeuvre a des qualités en tant que sculpture et il faut que je sois capable de reconnaître l'algorithme demandé dans l'objet en question).

On essaie ce petit concours à titre expérimental. Si je reçois quelques soumissions de qualité, on va trouver le moyen de faire tirer un bouquin d'algorithmique, de schémas de conception (Design Patterns) ou un truc du genre entre les concurrent(e)s méritant(e)s.

Date limite pour participer : à déterminer. Disons jusqu'au dernier lundi de mai 2006.

Une solution charmante mais par programmation au problème palindrome(), trouvée dans une présentation de Sasha Goldshtein en 2014, serait :

#include <algorithm>
bool palindrome(const string &s) {
   using namespace std;
   return equal(
       begin(s),
       begin(s) + s.size()/2,
       s.rbegin()
   );
}

Complément sur les palindromes

Les pistes qui suivent m'ont été gracieusement suggérées par Michel Séguin, dont la contribution est fortement appréciée :

Solutions proposées au problème de la session H2006

Michaël St-Georges, étudiant en informatique S2 à la session H2006 au Collège Lionel-Groulx, m'a soumis ceci.

Le texte explicatif va comme suit :

C'est pas une soumission officielle, mais je voudrais savoir ce que tu en pense à date... J'ai d'autres idées aussi, j'explore ça, mais celle là était facile à commencer ici...

Chaque couleur est codée sur trois octets. On rassemble les octets en ordre RGB, et ça fait une belle fonction compilée pour déterminer si un nombre est un palindrome... Mais j'ai pensé à plein d'autres trucs... Peut-être en mélanger quelques uns. Je vais te tenir au courant des développements.

Je dois indiquer que le fichier original était en format bitmap (.BMP). La version montrée à droite est un Portable Network Graphics (.PNG) pour fins d'économie de bande passante. Cela influence un peu le travail de Michaël puisque les données dans le fichier dépendent du format, alors il est important de le mentionner.

Notez qu'il serait possible d'exprimer un algorithme sous forme d'image Bitmap, comme en fait foi http://www.iquilezles.org/blog/?p=1426

Mathieu Fournier, étudiant en informatique S2 à la session H2006 au Collège Lionel-Groulx, m'a soumis ceci.

Je ne peux pas l'accepter en tant que soumission officielle, du fait que :

  • Il s'agit d'un algorithme
  • L'algorithme est le mien, et
  • Le mot LAVAL est un cas particulier de palindrome plutôt qu'une solution générale au problème Est-ce que cette séquence est, ou non, un palindrome

Ceci ne respecte donc pas les règles du concours. Cela dit, c'est joli (malgré les fautes de français) et Mathieu est un drôle de personnage. Je considère donc cette soumission comme étant digne d'une mention honorable.

Problème de la session H2004

Soit l'algorithme ci-dessous pour calculer le pgcd de deux entiers strictement positifs a et b (ne tenez compte que de la fonction pgcd() elle-même) :

//
// pgcd(a,b)
// Intrants: a et b, deux entiers (positifs)
// Extrant:  le plus grand commun diviseur de a et de b
// Calcule et retourne le plus grand commun diviseur
// de a et de b.
//
int pgcd(int a, int b) {
   return b? pgcd(b, a % b) : a;
}

//
// Petit programme de démonstration
//
#include <iostream>
int main() {
   using namespace std;
   int a, b;
   if (cin >> a >> b)
      cout << "PGCD (" << a << "," << b << "): "
           << pgcd (a, b) << endl;
}

Pouvez-vous exprimer le même algorithme dans une langue ou à l'aide d'un moyen d'expression qui :

Pour que votre soumission soit recevable, il faut que la conformité avec l'algorithme puisse être vérifiée par un professeur du département d'informatique du Collège (moi, probablement) et que la qualité artistique, esthétique, linguistique ou autre associée à votre oeuvre puisse être validée par un professeur du Collège dans la discipline correspondante (p.ex. si vous faites une sculpture, il faut qu'un professeur au département d'arts plastiques confirme que votre oeuvre a des qualités en tant que sculpture et il faut que je sois capable de reconnaître l'algorithme demandé dans l'objet en question).

On essaie ce petit concours à titre expérimental. Si je reçois quelques soumissions de qualité, on va trouver le moyen de faire tirer un bouquin d'algorithmique, de schémas de conception (Design Patterns) ou un truc du genre entre les concurrent(e)s méritant(e)s.

Date limite pour participer : à déterminer. Disons jusqu'au dernier lundi de mai 2004. J'accepte les soumissions en retard (pour les afficher), mais je ne peux les considérer pour un prix.

Solutions proposées au problème de la session H2004

Michael Blondin, étudiant en informatique de gestion S4 à la session H2006 au Collège Lionel-Groulx, m'a soumis ceci (et il a raison de critiquer : je n'ai pas tenu à jour mon petit concours ci-dessus, faute d'avoir reçu des soumissions). Ceci nous donne un joli exemple de ce qui peut être fait.

Le texte est verbatim de Michael (je n'ose pas appliquer de correctifs orthographiques ou grammaticaux à une construction poétique; j'espère que vous me le pardonnerez).

Voici ce qui arrive quand on mélange ennui et oubli d'effacer un vieux défi visant à imager un algorithme de notre site :

Soit deux entités; moi et elle

Que serait ma plus grande passion m'y reliant?

Je m'associerai à son antagoniste

Et avec le recule,

Je rangerai tous nos différends de côté

Jusqu'à ce qu'ils n'existent plus,

Je la porterai sur mon dos puissant

Mais, elle devra les porter sur ses ailes.

Je m'associerai à son antagoniste

Et avec toujours plus de recule,

Je rangerai tous nos différends de côté

Jusqu'à ce qu'ils n'existent nul !

Et cette passion, c'est toi !

L'inspiration de ce projet

Le 24 janvier 2000, un jeune norvégien de 16 ans (alors) dénommé Jon Lech Johansen, mieux connu aujourd'hui sous le nom de DVD Jon, a reçu la visite des autorités policières locales pour avoir brisé, en 1999, les techniques par lesquelles on protège un DVD contre le piratage avec un algorithme nommé DeCSS.

Le tout fut fait dans le but de rédiger et d'offrir un système permettant de lire des DVD sous Linux, mais si on sait comment décoder le contenu d'un DVD, il devient relativement facile de le traduire en un autre format et de le pirater.

Jon (ou ses collègues et amis, ce qui n'est pas très clair) a par la suite publié l'algorithme DeCSS sur Internet. Une loi américaine, la Digital Millenium Copyright Act (DMCA), interdit entre autres de briser ce code, et a un effet pervers en ce que, selon elle, un programme n'est pas une forme d'expression qui soit protégé au même titre que le droit de parole et de libre expression auquel nous sommes habitué(e)s.

Évidemment, la liberté d'expression et une opposition de fond à la censure étant au coeur de la philosophie de la plupart des informaticiens, la notion selon laquelle programmer ne serait pas s'exprimer au sens protégé par la charte des droits en a choqué et en a offusqué plus d'une et plus d'un. Une montée aux barricades fut faite pour montrer au monde entier en quoi et pourquoi il est ridicule de prétendre que programmer n'est pas une forme valide et normale d'expression.

Parmi les réactions, l'une de mes préférées fut celle exprimée à l'aide du site http://www-2.cs.cmu.edu/~dst/DeCSS/Gallery/, où l'algorithme DeCSS apparaît exprimé dans plusieurs langues et de plusieurs manières différentes, ce qui pose la question fort pertinente qu'est Quel est le point à partir duquel la liberté d'expression devient limitée. Attention : les premiers exhibits y sont surtout des programmes dans différents langages, mais ça varie un peu plus par la suite.

La section http://www-2.cs.cmu.edu/~dst/DeCSS/Gallery/Stego/index.html du site liste des exemples de stéganographie, ce qui peut être plus divertissant pour les non informaticiennes et les non informaticiens. Vous pouvez aussi aller consulter http://www.loyalty.org/~schoen/haiku.html pour en savoir plus sur l'une des soumissions les plus intéressantes sur le plan poétique.

à titre connexe, vous trouverez sur http://java.sun.com/features/2002/11/gabriel_qa.html une entrevue avec Richard Gabriel, un informaticien de renom qui souhaite la mise sur pied d'un programme universitaire de type Beaux-Arts mais en programmation. Son optique est différente (et très loin de l'ingénierie, ce qui donne un son de cloche divergent de la norme) et peut démarrer une réflexion intéressante.

Dans le même ordre d'idées, le site http://www.guillermito2.net/stegano/index.html d'un français du nom de Guillermito (je ne connais pas son nom de famille) liste des techniques et des technologies de stéganographie, de même que des faiblesses d'outils existants. La liberté d'expression est l'une des conditions premières de toute théorie de la sécurité, à plus forte partie de toute théorie de sécurité informatique; malgré tout, Guillermito est porté devant les tribunaux pour avoir publié ses analyses sur Internet. Un dossier à suivre...

Pour les gens familiers avec Alice au pays des merveilles, vous trouverez ici une version programmée de Jabberwocky.

L'éminent Michel Séguin, chic et éveillé professeur au département de mathématiques du Collège Lionel-Groulx, m'a indiqué un cas intéressant remarqué dans le livre Time Travel and Other Mathematical Bewilderments de Martin Gardner, soit celui de The Schillinger System of Musical Composition (page 92 de l'édition de 1988), où une pièce sur la ville de New York (New York Set To Music) était exprimée sous la forme d'un panorama composé de gratte-ciels, la forme du panorama correspondant à l'expression de la pièce. Je n'ai pas retrouvé de lien sur Internet montrant cette image (faut dire que j'ai pas vraiment eu le temps de chercher), mais si l'une ou l'un d'entre vous le retrouve ce serait bien gentil de m'en faire parvenir lURL.

Je suis tombé sur deux liens menant vers un blogue décrivant une stratégie poétique reposant sur la séquence de Fibonacci: http://gottabook.blogspot.com/2006/04/fib.html et http://gottabook.blogspot.com/2006/04/more-fibbery.html.

Chic truc dans une veine semblable : des sculptures mathématiques en blocs Légo.

Amusant : des objets réels inspirés de la géométrie de M. C. Escher (pour d'autres liens amusants: ceci, ceci, ceci, ceci, ceci ou son site officiel). Aussi, ceci. En périphérie : M. C. Escher inspire... faut le voir, je pense. Ceci aussi, d'ailleurs. D'ailleurs, un site parle d'Escherisation (traduction libre d'escherization), un processus algorithmique amusant. Pour une analyse à saveur mathématique de l'une de ses oeuvres, voir ceci. Et pour une surprise, voir ceci : http://laughingsquid.com/real-life-model-of-m-c-eschers-waterfall/

Dans la catégorie des idées novatrices et un peu perverses, que dites-vous d'un individu générant de l'art informatisé à partir de pourriel?

À propos de π :

À propos de la musique et de la chanson :

Résoudre un sudoku avec un logiciel d'installation.

Identifier des nombres premiers à l'aide d'une expression régulière (mais ça a ses limites : http://zmievski.org/2010/08/the-prime-that-wasnt?).

Expression de la suite de Fibonacci avec... une requête SQL, un langage qui ne permet pas la récursivité : http://progopedia.com/example/fibonacci/13/

Un programme de démineur, écrit en T-SQL : http://www.simple-talk.com/sql/t-sql-programming/minesweeper-in-t-sql/

Dans la même veine, un Tetris écrit avec sed : http://uuner.doslash.org/forfun/

Représenter des algorithmes de tri par des danses : http://www.i-programmer.info/news/150-training-a-education/2255-sorting-algorithms-as-dances.

Représenter un brevet par une équation mathématique : http://paulspontifications.blogspot.com/2011/04/patent-5893120-reduced-to-mathematical.html

Écrire un célèbre Hello World en construisant un bitmap : http://i.minus.com/ikq8hS.gif

Des équations mathématiques représentées par des objets tridimensionnels :

Utiliser (programmatiquement) Tetris comme une sorte d'outil de type Paint, par Mike Szczys en 2014 : http://hackaday.com/2014/11/08/using-tetris-like-ms-paint/

Un poème suivant une structure de Fibonacci : https://boingboing.net/2017/07/24/delightful-fibonacci-sequence.html

Un cube de M. C. Escher, mais dans la vraie vie : https://vimeo.com/120223777

S'inspirer d'un problème difficile comme le problème du commis voyageur :

Valid XHTML 1.0 Transitional

CSS Valide !