Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°59 - En cours d’élaboration - Mars 2018 > Le calcul formel, la logique et le binaire (...)

Le calcul formel, la logique et le binaire dans Sofus
Moteur de recherche
Mis en ligne le 7 février 2018, par Alain Busser

Article placé sous licence CC-by-SA : http://creativecommons.org/licenses/by-sa/3.0/fr/legalcode

Sofus est un outil de programmation visuelle, permettant de construire et tester des programmes mathématiques de la même manière que Scratch, à ceci près que dans Scratch il n’y a guère de mathématiques. Notamment

Cet article vise à décrire certaines nouvelles fonctionnalités de Sofus pouvant donner lieu à de nouvelles activités en classe :

  1. Les calculs exacts sur les fractions permettent de combiner les révisions sur les fractions avec des activités plus algorithmiques ; et les transformations de matrices permettent de rapidement programmer les corrigés des exercices de "spé maths" du bac S ;
  2. Le calcul formel intégré à Sofus permet de faire des preuves de programmes de calcul notamment pour corriger certains exercices du brevet ;
  3. Sofus permet aussi de transformer du texte et se prête à des exercices sur les "strings" (type au programme de 2nde) ; on va montrer comment on peut se servir de ces transformations textuelles pour dessiner des fractales sans faire appel à la récursivité ;
  4. On rendra également hommage à Smullyan avec un micromonde de logique modale permettant, par le biais de la théorie du mensonge, de mieux appréhender la négation et ses liens avec l’implication
  5. Enfin on décrira brièvement le version espagnole

Partie 1 : Calcul sur les fractions et les matrices

Voici un programme de calcul du nombre d’Or :

Approximations décimales

Il donne ce résultat :

2
1.5
1.6666666666666665
1.6
1.625
1.6153846153846154
1.619047619047619
1.6176470588235294
1.6181818181818182
1.6179775280898876

Très bien : On a un programme de calcul court qui fait quelque chose d’intéressant. Mais on ne voit pas que les étapes successives du calcul sont des fractions, parce que les valeurs (initiale et incrément) sont entrés comme des nombres décimaux (comme le montre leur couleur bleue).

Calcul exact 1ère version

On peut maintenant refaire ce programme avec des fractions (menu Sofus, sous-menu fractions), comme on le voit à la couleur marron qui, dans Sofus, est celle des fractions :

On a alors ceci :

2
3/2
5/3
8/5
13/8
21/13
34/21
55/34
89/55
144/89

Il y a un bloc arrondi de dans la catégorie fractions qui permet de retrouver le résultat précédent. Mais si on n’arrondit pas les fractions on a leurs valeurs exactes, et on peut par exemple préférer n’afficher que leurs dénominateurs, pour un résultat qui n’eût pas déplu à Fibonacci...

Calcul exact 2ème version

Ceci est probablement destiné à disparaître dans une version future de Sofus, parce que le calcul formel permet aussi de calculer sur les fractions (dans le menu texte pour des raisons évoquées ci-dessous) :

La raison pour laquelle ce script donne l’affichage en fractions est que ces blocs verts (comme ceux du texte dans Blockly) opèrent sur des chaînes de caractère représentant des expressions formelles, et que le calcul formel de Sofus transforme automatiquement les nombres (en bleu) en des expressions formelles (c’est-à-dire du texte).

Algèbre linéaire

Dans la catégorie Sofus il y a aussi une sous-catégorie Matrices qui contient elle aussi (comme les fractions et le texte) des blocs ressemblant étrangement à ceux de Sofus (augmenter etc.). Eux aussi sont à part, parce qu’ils n’agissent pas sur des nombres mais sur des vecteurs et autres matrices. Par exemple ils permettent

  • d’augmenter un vecteur d’un autre vecteur (ce qui revient à appliquer une translation) ;
  • de multiplier un vecteur par un nombre (ce qui revient à appliquer une homothétie) ;
  • de tripler un vecteur (là aussi il s’agit d’une homothétie) ou une matrice ;
  • de multiplier un vecteur ou une matrice, par une matrice.

Mais la multiplication des matrices n’est pas commutative ce qui crée quelques surprises ! Ainsi, si A est une matrice ayant un terme non nul en dehors de sa diagonale, multiplier par A et multiplier à gauche par A, n’ont pas le même effet ! De plus, multiplier une matrice par un vecteur produit un vecteur (et on ne peut donc pas répéter cette opération en boucle), alors que multiplier un vecteur à gauche par une matrice, aboutit à un vecteur de même dimension, ce qui permet de s’en servir pour les exercices du bac S. C’est avec une confortable facilité que ces blocs ont servi à faire les corrigés des exercice de spécialité

Fibonacci et les matrices

Comme la multiplication des matrices n’est pas commutative, il n’est plus nécessaire d’inverser la matrice pour calculer le nombre d’Or :

Les fractions de tout-à-l’heure sont codées dans les vecteurs colonne successifs de la matrice F (puissances d’une matrice constante), le numérateur étant son abscisse et le dénominateur, son ordonnée. On a l’affichage suivant :

[1, 0]
[1, 1]
[2, 1]
[3, 2]
[5, 3]
[8, 5]
[13, 8]
[21, 13]
[34, 21]
[55, 34]

Partie 2 : Calcul formel

On va maintenant voir à quoi peut servir le calcul formel de Sofus, en commençant par cet exemple :

On augmente un nombre de 20 pourcents puis on diminue le résultat de 25 pourcents. Quelle proportion du nombre initial reste-t-il alors ?

Programmes de calcul formel

Dans le cas où le nombre est entré comme un prix, on trouve un passage, par exemple, de 100 à 90, soit une diminution de 10% :

Remarquer la couleur verte des blocs de Sofus : Ce ne sont pas ceux de base, mais ceux qui se trouvent dans la catégorie calcul formel (sous-catégorie de texte). En effet, il suffit de prendre 1 comme valeur initiale pour avoir maintenant la valeur finale comme fraction de la valeur initiale (ici, 9/10) :

Mais pourquoi cette nouvelle version de Sofus se trouve-t-elle dans la catégorie texte ? Parce qu’avec cette version il est possible de remplacer la valeur initiale du nombre par une valeur formelle (donc, du texte) et plus numérique cette fois-ci :

L’affichage obtenu est (9/10)*x ce qui confirme qu’on a bien, indépendamment de la valeur initiale x du nombre, une diminution de 10%.

Et si on essayait avec une augmentation de 4t pourcents suivie d’une diminution de 5t pourcents ?

L’affichage "embelli" est 1 - t/100 - t²/500 soit une diminution de t+t²/5 pourcents (t étant lui-même en pourcents). On peut d’ailleurs vérifier que pour t=5, ça donne 10 pourcents trouvés ci-dessus mais généralisés ici.

Les programmes de calcul du brevet des collèges peuvent être prouvés par la théorie des anneaux (d’ailleurs le nombre d’entrée est souvent un entier), c’est-à-dire qu’on combine les additions, soustractions, multiplications et élévations à une puissance (pas de divisions). C’est justement ce pour quoi le calcul formel de Sofus est à l’aise.

Par exemple pour montrer qu’en incrémentant un nombre, puis en élevant le résultat au carré, puis en soustrayant au résultat le carré du nombre de départ, on a une fonction affine, on peut faire

qui donne 1+2*x comme résultat final.

Suites de polynômes

Les programmes de calcul formel permettent d’inventer des suites de polynômes de ce genre :

Les 4 premiers polynômes ainsi calculés sont

1 + x**2 - 2*x
x**4 - 4*x**3 + 4*x**2
1 + x**8 - 32*x**5 - 8*x**2 - 8*x**7 + 8*x**3 + 14*x**4 + 24*x**6
x**16 - 1744*x**11 - 700*x**8 - 448*x**13 - 384*x**9 - 160*x**6 - 128*x**5 - 16*x**15 + 64*x**4 + 112*x**14 + 736*x**7 + 1116*x**12 + 1552*x**10

Cette suite de polynômes a-t-elle des propriétés particulières ? Que peut-on dire des coefficients ?

Il n’est pas étonnant que le degré monte aussi vite, puisqu’on élève au carré à chaque passage dans la boucle. On peut réduire ce degré en dérivant le polynôme P :

Du coup, toutes les fonctions sont affines :

- 2 + 2*x
- 12 + 8*x
- 208 + 128*x
- 53504 + 32768*x
- 3506503680 + 2147483648*x
- 15060318633198617000 + 9223372036854776000*x

Mais du coup ce sont les coefficients directeurs qui sont grands ; on peut les diminuer par des divisions par 2 :

Et là, les fonctions affines sont beaucoup plus simples, au point qu’on laisse le lecteur deviner les valeurs, voire montrer la conjecture ainsi faite.

Équations

Lorsqu’on demande à Sofus de développer une expression, cela a pour effet de la modifier :

En effet alors qu’au départ l’expression était égale à

(2*x+1)*(4*x-5)

(ainsi que le prouve l’affichage de sa valeur), ensuite elle est devenue

- 5 - 6*x + 8*x**2

Sofus ne sait pas factoriser (la simplification aboutit à un développement) mais on peut résoudre une équation :

Mais le résultat peut être amélioré :

3/8 + (sqrt(196))/-16,        3/8 + (sqrt(196))/16

En effet l’exemple a été construit pour que les solutions soient -1/2 et 5/4 ; mais sachant que √196 = 14, les solutions peuvent s’écrire 3/8-14/16 et 3/8+14/16 soit -1/2 et 5/4 comme le montre ce script :

Sofus sait aussi résoudre les équations du premier degré :

Lambda-calcul

Juste après le calcul formel dans la partie texte, il y a des possiblités d’introspection avec les blocs JavaScript et CoffeeScript. On peut donc programmer des blocs directement en JavaScript ou en CoffeeScript :

On peut aussi faire directement en JavaScript :

Ou en CoffeeScript :

Ou même directement avec la notation du λ-calcul :

Sofus est donc bien adapté au programme de Seconde qui insiste sur les fonctions et la concision du langage, juste, c’est de la programmation visuelle... Mais les blocs JS permettent d’insérer du programme textuel dans les blocs, aussi ridicule que puisse paraître l’idée !

Ce film en montre un peu plus sur le sujet :

Partie 3 : Des nouveaux mots sur les mots

Dans la catégorie texte, et surtout dans la sous-catégorie Sofus de celle-ci, se trouvent des nouveaux mots permettant de faire des opérations sofusiennes sur les mots.

Fabrication d’un mot long

Il y a notamment la possibilité

  • de concaténer deux morceaux de texte à la manière de Sofus, soit en ajoutant le suffixe à un texte qui va, du coup, changer [1] ;
  • de faire compter par Sofus le nombre d’occurences d’une lettre (ou d’un sous-mot) dans du texte ;
  • de mettre un mot à l’envers (utile pour détecter les palindromes) ;
  • de remplacer la première occurence d’une lettre (ou d’un sous-mot) par un mot ;
  • et de remplacer toutes les occurences d’une lettre par un mot :

L’exécution de ce script donne le mot suivant :

agadagagagadagadagadagagagadaga

Il y a beaucoup de "a" dans ce mot ! Combien ? La variante du script que voici

donne 16 lettres "a". En fait comme le nombre de "a" quadruple à chaque remplacement, on peut faire un mot très long assez rapidement, en recommençant plusieurs fois l’opération, et le nombre de "a" dans ce long mot tend rapidement vers l’infini. Par exemple ce script écrit un mot de 511 lettres :

parmi lesquelles 256 sont des "a" (en gros, la moitié des lettres du mot).

Lecture du mot long

Mais pourquoi tous ces "a" ? Ah ? Haha, c’est "a" comme "avancer", et la tortue va être sollicitée avec ce bloc, créé à cette occasion :

Il réalise les opérations suivantes sur un mot :

  • créer une liste des lettres du mot ;
  • parcourir par une boucle sur la liste, les lettres du mot ; dans cette boucle, regarder la lettre :
    • si la lettre est un "a", demander à la tortue d’avancer ;
    • si la lettre est un "g", demander à la tortue de tourner à gauche (de 60°) ;
    • sinon c’est que la lettre est un "d", et la tortue devra tourner vers la droite (de 120° pour le coup)

Ceci permet de considérer le mot initial "a" comme un programme demandant à la tortue d’avancer, et sa première transformation "agadaga" comme un programme demandant à la tortue de tracer un quadrilatère ouvert (un triangle équilatéral dont il manque la base, assorti de deux segments latéraux).

En fait les transformations du mot aboutissent à un programme de 511 instructions pour la tortue, lequel lui fait dessiner un côté du flocon de Von Koch.

Résultat obtenu

Le script pour dessiner une fractale est finalement assez court, avec cette méthode :

Il permet de dessiner le flocon de Von Koch et d’autres fractales à relativement peu de frais. En particulier on évite d’avoir recours à la récursivité et on connaît facilement le périmètre du flocon à partir du comptage de lettres vu ci-avant.

Le mot long donne le motif que voici :

Partie 4 : Les Transylvaniens aux origines crétoises et les chiffres indiens

Smullyan étant logicien, il est logique que les blocs décrits ci-dessous soient dans la catégorie Logique de Sofus. Dans la Transylvanie de Smullyan, on ne peut distinguer par leur aspect ou leur voix, les humains des vampires. Mais alors que les humains ne disent que la vérité, les vampires, au contraire, mentent systématiquement.

Théorie du mensonge

Le docteur Victor F. est connu des lecteurs de Mary Shelley, mais est-il humain ou vampire ? Pour le savoir, créons une variable de type médecin dans Sofus :

Demander à Victor s’il est humain, ne fonctionnerait pas : Soit il est effectivement humain et répondra oui, soit il est vampire et prétendra être humain. Mais on peut poser à Victor une question dont on connaît (ainsi que lui) la réponse :

Sofus répond "true" ce qui indique que Victor est humain. Pour en avoir confirmation, Sofus permet de déclencher une catastrophe : La morsure de Victor par Drakula ce qui transforme Victor en vampire :

Et maintenant Victor prétendra que 2+2 n’est pas égal à 4, parce que, devenu vampire, il mentira.

Pour résoudre certains problèmes sur les transylvaniens, il est parfois nécessaire de poser des questions sur autre chose que les maths :

Comme on l’a évoqué ci-dessus, Victor continuera, une fois devenu vampire, à prétendre être humain, par mensonge [2]. Mais Nelson Goodman a fait une constatation : De façon similaire, aucun transylvanien ne pourra dire qu’il est vampire :

Effectivement Sofus affiche false quelle que soit la nature de Victor :

  • Si Victor est humain, il mentirait en prétendant être vampire, et cela serait contraire à sa nature humaine ;
  • Si Victor est vampire, avouer qu’il l’est serait dire la vérité, ce qu’un vampire ne peut pas faire.

On peut alors remarquer avec Goodman (et Smullyan) que l’on a maintenant une proposition tout aussi fausse que 2+2=5 : Qu’un transylvanien dise être vampire. Alors il n’y a qu’à lui demander s’il est capable de dire qu’il est vampire :

  • S’il dit qu’il dit être vampire, c’est qu’il dit quelque chose de faux, et alors c’est un vampire ;
  • S’il dit qu’il ne dit pas être vampire, alors il dit quelque chose de vrai et c’est un humain.

Autrement dit, l’opérateur modal "dit que" est, en transylvanie, un opérateur dont le carré est la négation. Si vous avez trouvé ça tout seul, peut-être serez-vous prêt à affronter l’Énigme la plus difficile du monde...

Logique doxastique

Dans Quel est le titre de ce livre ?, Smullyan raconte une catastrophe survenue en Transylvanie : Une épidémie de folie atteignant tant les humains que les vampires, et telle que dès qu’un transylvanien devient fou, il l’est totalement : Tout ce en quoi il croit, est faux.

On va commencer par enquête sur un fou prénommé Hector :

En fait Hector est humain, et pourtant il prétend ne pas l’être. Pourquoi ? Parce qu’il est fou ! En effet, de par sa folie, Hector se prend pour un vampire (qu’il n’est pas). Et comme il est humain (bien que ne le sachant pas), il dit ce qu’il pense être la vérité, en affirmant être vampire. De même, si on lui demande s’il est vampire (ce qu’il n’est pas) il répondra que oui :

Smullyan se demandait d’ailleurs s’il convient de traiter de menteur quelqu’un qui affirme des faussetés (comme Hector ci-dessus) sans savoir que ce sont des faussetés. Pour Smullyan, n’est vraiment menteur, que celui qui ment sciemment.

Après Hector et Victor, voici Igor, c’est un vampire :

Il va donc dire que 2+2 n’est pas égal à 4, parce que comme c’est un vampire, il ment (on en déduit qu’il est sain d’esprit, d’ailleurs). On peut vérifier, à l’aide de Sofus, qu’Igor est bon arithméticien :

Mais las ! L’épidémie de folie finit par atteindre Igor :

Du coup il a perdu sa foi en l’arithmétique, et maintenant si on lui demande si 2+2=4, il répondra oui, parce qu’il ment sur sa croyance en le fait que 2+2 n’est pas égal à 4 :

Igor sait-il au moins qu’il est fou ?

Bien entendu, c’est comme la théorie du mensonge : Personne en transylvanie ne croit être fou : Les sains d’esprit parce qu’ils ne peuvent pas croire en quelque chose de faux (leur folie) et les fous parce qu’ils ne peuvent pas croire en quelque chose de vrai (leur folie). Mais un fou, qu’il soit humain ou vampire, croit qu’il croit en sa folie :

Et fous ? Pardon, et vous ? Croyez-vous être fou ? Croyez-vous que vous croyez être fou ? La logique doxastique est quelque chose de complexe puisque comme on le voit, il est possible de croire en une croyance qu’on n’a pas.

Sofus permet de deviner ce que dira Igor à propos des croyances qu’a Victor en la folie d’Hector, et d’aller beaucoup plus loin : Il y a aussi des patients, et rien n’exclut qu’un patient soit sain d’esprit ou qu’un médecin soit fou, dans la Transylvanie de Smullyan... Lire aussi le livre qui rend fou, du même auteur.

Kaprekar

Dans le livre qui rend fou, Smullyan s’amuse à faire des concaténations entre nombres entiers [3] et des blocs permettant d’explorer les opérations qu’il décrit dans le livre, ont été incorporés à Sofus. Ces blocs permettent aussi d’implémenter facilement l’algorithme de Kaprekar :

Itéré 6 fois sur un entier de 4 chiffres, l’algorithme arrive à l’un des points fixes suivants :

  • 495 (cas où le nombre de départ comprenait le chiffre 0)
  • 6174 (la constante de Kaprekar)
  • plus rarement 0 (si à un moment tous les chiffres sont égaux entre eux comme 3333)

Binaire

Sofus peut maintenant convertir en écriture binaire un entier :

Et inversement, on peut y entrer un entier entre 0 et 255 en cochant des cases (les chiffres binaires de cet entier) :

Partie 5 : Viva Espana !

Grâce à José Manuel Ruiz Guttierez, Sofus est traduit en espagnol et un mode d’emploi de Sofus pour débutants en programmation a été rédigé par ses soins ; il est ici.

Du coup une version anglaise a (enfin !) été écrite.


notes

[1L’équivalent en Python est += qu’on place entre le texte à modifier et le suffixe à lui rajouter

[2toute ressemblance avec les politiciens qui affirment qu’ils disent la vérité, est purement fortuite, cela va de soi !

[3le caractère profondément arithmétique de ces concaténations l’a amené à découvrir des résultats alors inédits sur le théorème de Gödel au début des années 1960

Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197