Catégorie : Informatique

Les différentes décisions prises dans beaucoup de Pays sur le confinement, ou sur d’autres sujets (achats de masques médicaments, etc..) sont basées sur des projections, ces dernières sont obtenues par le biais de simulations, et ces simulations suivent un modèle mathématique, et sont pour la plupart fournies par le prestigieux Imperial College of London.

Cela montre en quoi les mathématiques associées à l’informatique peuvent être un merveilleux outil au service de l’humanité.

Dans le cas d’un virus comme le Covid-19, la croissance est en effet exponentielle au début. Mais il est clair que cela ne peut pas continuer éternellement. À un moment donné, le virus manquera de ressources, c’est-à-dire de personnes susceptibles d’être infectées, car une grande partie de la population l’est déjà ou l’a déjà été. Ensuite, le nombre de cas n’augmente que de façon linéaire, c’est-à-dire de façon constante chaque jour. Et, encore plus tard, la croissance de la courbe s’arrête complètement. C’est exactement ce que décrit l’équation logistique ci-dessus :

J’ai voulu comprendre le sens mathématique de ces simulations, pour les reproduire moi même en Python, en considérant les paramètres suivants :

• X indique le temps, supposons qu’il commence au jour 0 et s’arrête après 50 jours.
• X0 indique le moment où la croissance exponentielle s’arrête, disons après 30 jours.
• L indique la valeur maximale pouvant être par la courbe (nombre de cas), disons 4.5 10^-4 de la population française, soit 30000
• K indique la pente de la courbe : disons 0.5

Ceci est une projection, basée sur une seule simulation, autrement dit, un seul scénario, mais il est tout à fait possible d’en simuler plusieurs, ce qui est fait d’ailleurs par l’Imperial College of London.

Les résultats sont visibles ci-dessous :

Bien sûr, les simulations officielles sont basées sur beaucoup plus de détails et de paramètres, cet article est purement écrit dans un but pédagogique.

Code Python :

Le test du canard, est une forme d’inférence (une abduction) qui s’énonce ainsi :

« Si ça ressemble à un canard, si ça nage comme un canard et si ça cancane comme un canard, c’est qu’il s’agit sans doute d’un canard. »

L’expression est souvent attribuée au poète américain James Whitcomb Riley, où, dans un contexte anticommuniste, ce dernier aurait dit :

« Je ne peux pas prouver que vous êtes un communiste. Mais quand je vois un oiseau qui cancane comme un canard, qui marche comme un canard, qui a des plumes et des pieds palmés, et qui s’associe avec des canards, je vais certainement affirmer qu’il est un canard »

Le test du canard, a inspiré en Informatique un style de typage dynamique de certains langages de programmation (comme Python), ce style s’appelle le duck typing (typage canard).
Son principe repose sur le fait que, le type d’un objet, dans le contexte où il est utilisé, est déterminée par l’ensemble de ses méthodes et de ses attributs et non de manière définie et statique.

Ainsi, un objet de type A, peut être considéré dans certaines opérations comme étant un objet du type B, sans qu’il y ait aucun relation d’héritage entre A et B !

Exemple en Python :

Le théorème de Bézout affirme que les entiers a et b sont premiers entre eux (si et) seulement si l’équation au + bv = 1 admet au moins une solution.

L’algorithme d’Euclide, permet de trouver de façon efficace les entiers u et v.

Je m’intéresse à la preuve de ce théorème et à l’implémentation de l’algorithme d’Euclide en C.

Preuve : Comme il s’agit d’une équivalence ( <=>, si et seulement si), la preuve se fait en 2 temps.

1. a,b premiers entre eux => il existe un couple (u,v) tq : au + bv = 1

Rappelons que 2 nombres premiers entre eux, ont pour pgcd 1.
Donc dans notre cas, pgcd(a,b) = 1

Rappelons aussi l’égalité de Bézout :

• a,b deux entiers non nuls, D=pgcd(a,b)
• Il existe un couple (u,v) d’entiers relatifs tq :

au + bv = D

Puisque pgcd(a,b) = 1, l’égalité de Bézout permet de montrer qu’il existe bien un couple (u,v) tq au + bv = 1

Cette démonstration est un peu « facile » car j’utilise l’égalité de Bézout pour montrer le théorème de Bézout, le mieux serait de faire cette preuve, sans avoir recours aux outils donnés par Bézout.

1.2) a,b premiers entre eux => il existe un couple (u,v) tq : au + bv = 1

On suppose a,b premiers entre eux, donc pgcd(a,b) =1
pgcd(a,b) = 1; donc au moins un des entiers a,b est non nul

• Soit E l’ensemble des entiers de la forme au + bv, avec u et v des entiers.
• E est un ensemble non vide (car un des entiers a,b est non nul), de plus E contient un plus petit élément m, tq :
• m = au1 + bv1.
• La division euclidienne de a par m s’écrit : a = mq + r, avec r ∈ N. ( 0 <= r < m)
• On a alors : a = (au1 + bv1)q + r
• Donc : r = a – (au1 + bv1)q
• Donc : r = a (1-u1q) + b (-v1q)
• On voit bien que r est de la forme : r = au +bv
• Comme m est le plus petit élément de E, et que 0 <= r < m, on conclu donc que r = 0

r = 0 signifie que a est divisible par m
De la même manière, on démontre que b est divisible par m.

Donc m est un diviseur commun pour a, b, comme ils sont premiers entre eux, alors on déduit que m (qui est de la forme au +bv) = 1.

2) il existe un couple (u,v) tq : au + bv = 1 => a,b premiers entre eux

• Posons pgcd(a,b) = D, D divise a, et D divise b, D divise aussi au + bv.
• Ici nous avons au + bv = 1, donc D divise 1, donc D = 1.
• D =1, signifie que a,b sont bien premiers entre eux

Une autre façon de faire cette démonstration est de passer par sa contraposée, c’est à dire :

a,b ne sont pas premiers entre eux => il n’existe pas de couple (u,v) tq au + bv = 1

a,b non premiers entre eux, alors pgcd(a,b) = D, avec D > 1.

• D divise a, et D divise b, D divise aussi au +bv.
• 1 étant un nombre premier, son seul diviseur est lui même (1).
• D > 1, donc D ne divise pas 1, donc il n’existe pas de couple (u,v) tq au + bv = 1

Code C :