Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°45 - mai 2015 > La complexité c’est simple comme la dichotomie

La complexité c’est simple comme la dichotomie
Moteur de recherche
Mis en ligne le 19 avril 2015, par Guillaume Connan

Il ne s’agit pas d’une activité « clé en main ». L’orientation est plutôt vers la formation continue car nous avons besoin d’en savoir un peu plus que nos élèves avant de leur introduire une notion. Cependant, comme cela a déjà été évoqué dans un article de la revue Repères, l’étude de la complexité peut être abordée au lycée et les auteurs de cet article avaient proposé de nombreux exemples.

Nous proposons ici des approches théoriques et expérimentales de ce problème. On met ainsi en évidence qu’une notion mathématique importante (les suites numériques) )peut être illustrée par un problème informatique théorique et pratique et inversement, en cours d’ISN par exemple, on fait prendre conscience aux élèves que l’informatique, ce n’est pas taper sur des touches, c’est surtout noircir du
papier avec des raisonnements très proches des mathématiques.

Nous avons du mal en français à trouver des termes pour désigner les domaines gravitant autour de l’informatique. Ce dernier mot est souvent remplacé par Tice ( avec un T comme technologie...cela restreint le domaine et permet de comprendre pourquoi pendant si longtemps informatique rimait avec bureautique) ou bien par numérique et la dernière mode est de parler de code. Les anglo-saxons parlent de Computer Science, désignation qui a l’avantage de comporter le mot science. Computer Science est en relation avec les domaines Scientific Computing et Computer Engineering mais n’est pas du tout réduit à ces deux composantes proches.

Le département de Computer Science de l’Université de Boston s’adresse ainsi à ses futur(e)s étudiant(e)s :

Computer Science is about problem solving. Thus, the qualities of a good computer scientist include a passion for finding elegant solutions, an ability to use mathematical analysis and logical rigor to evaluate such solutions, creativity in modeling complex problems through the use of abstractions, attention to details and hidden assumptions, an ability to recognize variants of the same problem in different settings, and being able to retarget known efficient solutions to problems in new settings. If you like to solve puzzles, then computer science is for you !

Cela ressemble beaucoup à ce que l’on attend d’élèves étudiant les mathématiques !...

Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter l’auteur pour une utilisation commerciale) suivant la licence CC-by-nc-sa http://creativecommons.org/licenses/by-nc-sa/3.0/fr/legalcode

Une version papier de cet article a été repris dans le numéro 102 de Repères-IREM

L’article au format PDF (meilleur rendu et bibliographie) :

PDF - 546 ko

Le lancer de piano ou comment faire de l’informatique sans ordinateur...


L’expérience

Une entreprise de déménagement syldave veut réduire son personnel et rationnaliser ses méthodes de transport de piano. Elle engage un spécialiste de chez Dicho & Co qui propose l’approche scientifique suivante. L’entreprise achemine $k$ pianos en bas du bâtiment de l’Université de Klow qui a $N=2^n$ étages, le rez-de-chaussée portant le numéro 0.

Le but de l’expérimentation est de déterminer l’étage à partir duquel lancer un piano par la fenêtre lui est fatal.

On suppose qu’un tel étage existe et que le rez-de-chaussée n’est pas fatal.

On suppose également que tant que le piano survit au lancer, on peut le réutiliser. Pour économiser le temps et le dos des expérimentateurs, on va chercher un algorithme qui minimise le nombre d’essais effectués (et non pas le nombre de pianos détruits).

Une première idée serait de commencer au rez-de-chaussée et de lancer un piano de chaque étage jusqu’à atteindre l’étage fatal. Si jamais l’étage fatal est le dernier, cela nécessitera d’effectuer $N-1$ essais : c’est le pire cas.

Si l’on considère que tous les étages sont potentiellement fatals avec la même probabilité, on effectuera avec cette méthode $(N-1)/2$ essais en moyenne.

Mais on peut faire mieux....

Diviser pour régner

Nous allons diviser l’immeuble en deux parties égales en considérant l’étage du milieu : si cet étage est fatal, il suffira de chercher dans la moitié inférieure, sinon, dans la moitié supérieure de l’immeuble. Nous allons donc effectuer une recherche dichotomique de l’étage fatal.

Quand va-t-on s’arrêter de découper l’immeuble ? Lorsqu’il n’y aura plus d’ambiguité, c’est-à-dire lorsque l’étage supérieur sera juste au-dessus de l’étage inférieur.
La fonction devient :

On peut donner une version non récursive équivalente mais moins naturelle : se
dire « je recommence l’expérience dans la moitié supérieure » fait
clairement penser à un processus récursif.

Qu’a-t-on gagné ? Mais d’abord, est-ce que notre fonction nous renvoie l’étage attendu ? Et d’abord, renvoie-t-elle quelque chose ?

Déterminer les réponses à ces questions constitue les trois étapes indispensables de l’étude d’un algorithme :

  1. étude de la terminaison de l’algorithme : est-ce que la fonction renvoie effectivement une valeur ?
  2. étude le la correction de l’algorithme : est-ce que la fonction renvoie la valeur attendue (i.e. celle correspondant à la post-condition) ?
  3. étude de la complexité de l’algorithme : peut-on estimer la vitesse d’exécution de cet algorithme ?
  1. Pour répondre à la première question, il suffit de remarquer qu’au départ,
    l’intervalle d’étude est l’ensemble $\bigl\{0,1,2,...,N-1\bigr\}$ de
    longueur $N$ . Après
    chaque appel récursif, la longueur de l’intervalle est divisée par deux.
    Notons $\ell_i$ cette longueur après $i$ appels récursifs. La suite $\ell$ est
    géométrique de raison $1/2$ et de premier terme $N$.
    On a donc $\ell_i=\frac{N}{2^i}=\frac{2^n}{2^i}=2^{n-i}$. Ainsi $\ell_n=1$ et
    l’algorithme s’arrête.
  2. Vérifions d’abord que l’invariant est valide à chaque appel récursif :
    c’est vrai au départ car on précise qu’un étage fatal existe entre le
    rez-de-chaussée (non fatal) et le dernier étage.
    Par construction, on choisit inf et sup pour que le plus petit reste entre inf
    et sup et que la borne inférieure ne soit pas fatale.
    Quand la récursion s’arrête, l’intervalle est en fait $\bigl\{\mathrm{inf}, \mathrm{inf} + 1\bigr\}$ et inf
    n’est pas fatal donc $\mathrm{inf} + 1$ l’est et est la valeur cherchée, eh !
  3. Combien de temps nous a-t-il fallu ? Mais d’abord comment mesure-t-on le
    temps ?
    Nous ne sommes pas sur machine mais dans la grande université de Klow. Il faut
    compter le temps de chute, le temps de remontée des pianos encore en état, le
    temps de manipulation pour passer les pianos par la fenêtre, l’examen de
    l’état du piano ayant chu. Selon
    l’efficacité des muscles
    et l’état de santé des déménageurs, nous pouvons poser que ces temps sont
    proportionnels au nombre d’étages, mis à part le temps de passage par la
    fenêtre qui est constant ainsi que l’examen du piano par un
    expert [1].
    ...Mais c’est un peu compliqué...On va supposer que l’ascenseur est
    ultra-performant et que les pianos sont très lourds ce qui entraîne que tous
    ces temps sont à peu près constants, quelque soit l’étage\footnoteC’est ce
    qui correspondra par exemple en informatique au parcours d’un tableau
    statique.
    .
    Il suffit donc de compter combien de lancers ont été effectués. La réponse est
    dans l’étude faite pour prouver la terminaison : c’est à l’étape $n$ que l’on atteint la condition de sortie de l’algorithme.
    Que vaut $n$ ? On a posé au départ que le nombre d’étages était une puissance
    de 2 : $N=2^n$ . Ainsi, $n=\log_2N$ .
    Finalement, le nombre de tests effectués est égal au logarithme en base 2 du
    nombre d’étages. Et le temps ? Et bien, ce n’est pas ce qui nous intéressait
    puisqu’on nous demandait de mesurer le nombre de tests effectués mais cela
    nous a permis d’introduire la notion de complexité d’un algorithme
    dont la mesure va dépendre de l’unité choisie et sera plus ou moins difficile
    à déterminer.
    Si notre immeuble a 1024 étages, nous sommes donc passés de 1022 tests au
    maximum à 10 tests ce qui n’est pas négligeable, surtout pour le dos des
    déménageurs.

Le bug de Java

Pendant 9 ans, jusqu’en 2006, les fonctions de recherche dichotomique en Java
cachaient un bug...

Voici ce que l’on trouvait dans la bibliothèque java.util.Arrays

Regardez la ligne 6 : int mid    = (low + high) / 2;.

Tout va bien...mais en fait il faut se souvenir que le type int de Java est codé sur 32 bits et que le successeur de $2^{32}-1$ n’est pas $2^{32}$ mais son opposé car on représente les nombres relatifs sur machine d’une manière spéciale [2] Une activité sur ce sujet est proposée en annexe.

Le bug a été corrigé en remplaçant cette ligne par :

int mid = low + ((high - low) / 2);

Il faudra faire de même dans nos fonctions !

Questions subsidiaires

  1. Que se passe-t-il si nous avons moins de $n=\log_2(N)$ pianos pour
    tester ?
    Aïe ! Notre dichotomie ne peut aller jusqu’au bout. L’idée est de l’appliquer
    $k-1$ fois ($k$ étant le nombre de pianos à diposition). Il se peut que nous n’ayons pas abîmé de piano. Il se peut aussi que nous ayons cassé un piano à chaque fois si l’étage fatal est très petit. Il nous reste donc dans le pire des cas un piano et $N/2^{k-1}$ étages non testés.
    On va donc partir du plus bas et remonter jusqu’à casser notre dernier
    piano. Dans le pire des cas, ce sera le dernier testé.
    Ainsi, s’il nous reste assez de pianos (si l’étage fatal n’est pas trop bas),
    nous pourrons appliquer la dichotomie jusqu’au bout. Dans le pire des cas, il
    faudra effectuer $k-1+\frac{N}{2^{k-1}}-1$ tests.
    #-Que se passe-t-il si nous n’avons que 2 pianos et que n est pair ?
    Si l’on applique une fois la dichotomie, il nous restera N/2 tests à effectuer.
    On peut faire mieux...
    Il suffit de découper l’immeuble en $\sqrt{N}=2^{n/2}$ paquets de $\sqrt{N}$
    étages.
    On commence par tester l’étage $\sqrt{N}$ puis éventuellement $2\sqrt{N}$,
    etc. Bref, on effectue une recherche séquentielle du paquet fatal.
    Ensuite, il suffit d’utiliser le deuxième piano (le premier est cassé pour déterminer le paquet fatal) afin d’effecteur une recherche séquentielle de
    l’étage fatal cette fois. Dans le pire des cas, cela va nous demander
    $\sqrt{N}-1$ tests.
    Bref, dans le pire des cas, nous effectuerons $2\sqrt{N}-1$ tests.
  2. Que se passe-t-il quand N n’est pas une puissance de 2 ?
    Ce n’est pas grave car le nombre de tests croît avec le nombre
    d’étages dans limmeuble. Or, pour tout entier naturel N, il existe un entier
    $n$ tel que :
    $2^n \leqslant N < 2^{n+1}$
    Si on appelle T la fonction qui, au nombre d’étages, associe le nombre de
    tests par la méthode dichotomique, alors :
    $T(2^n)=n \leqslant T(N) < n+1$
    donc $T(N)=n=\lfloor \log_2(N)\rfloor$.
  3. Et si nous avions fait de la trichotomie
    On pourrait penser que diviser notre immeuble en 3 pourrait être plus
    efficace car on divise la taille de l’intervalle suivant par 3
    mais on effectue au pire deux tests à chaque fois.

Ainsi, dans le pire des cas on effectuera (en supposant que N est une
puissance de 3)
$2\log_3(N)=2\frac{\ln(N)}{\ln(2)}\times\frac{\ln(2)}{\ln(3)}\simeq 1,3\log_2(N)$ tests donc ce n’est pas mieux et ça ne fera qu’empirer si on augmente le nombre de divisions...
La division par 2 serait-elle magique ?

Diviser ne permet pas toujours de régner ?

Considérons un problème mathématique simple : la multiplication de deux entiers.

Vous savez additionner deux entiers de $n$ chiffres : cela nécessite $\lambda_1 n$ additions
de nombres de un chiffre compte-tenu des retenues avec $\lambda_1$ une constante positive.

Multiplier un entier de $n$ chiffres par un entier de 1 chiffre prend $\lambda_2 n$
unités de temps selon le même principe.

En utilisant l’algorithme de l’école primaire pour multiplier deux nombres de
$n$ chiffres, on effectue $n$ multiplications d’un nombre de $n$ chiffres par un
nombre de 1 chiffre puis une addition des $n$ nombres obtenus. On obtient un temps de calcul en $\lambda_3 n^2$.

On peut espérer faire mieux en appliquant la méthode diviser pour régner.

On coupe par exemple chaque nombre en deux parties de $m=\lfloor n/2\rfloor$
chiffres :

$$xy=(10^mx_1+x_2)(10^my_1+y_2)=10^{2m}x_1y_1+10^m(x_2y_1+x_1y_2)+x_2y_2$$

Les divisions et les multiplications par des puissances de 10 ne sont que des
décalages effectués en temps constant.

L’addition finale est en $\lambda n$ donc le temps d’exécution est défini par :

$$T(n)=4T(\lfloor n/2\rfloor) +\lambda n \qquad T(1)=1$$

Peut-on exprimez $T(n)$ explicitement en fonction de $n$ sans récursion ?

Si nous avions une idée de la solution, nous pourrions la démontrer par
récurrence.

Ça serait plus simple si $n$ était une puissance de
2. Voyons, posons $n=2^k$ et $T(n)=T(2^k)=x_k$.

Alors la relation de récurrence devient :

$$x_k=4x_{k-1}+\lambda 2^k \qquad x_0=1$$

On obtient :

$$x_k=4(4x_{k-2}+\lambda’ 2^{k-1})+\lambda 2^k = 4^kx_0+\sum_{i=1}^k\Lambda_k 2^k =4^k+k\Lambda_k 2^k =n^2 + \Lambda_kn \log n \sim n^2 $$

Car nous verrons que l’on peut encadrer ce $\Lambda_k$ entre deux constantes
positives dans la dernière section.

On montre alors par récurrence forte que ce résultat est vrai pour tout
entier naturel non nul $n$.

Bref, tout ça pour montrer que l’on n’a pas amélioré la situation...

Le grand Андрей Николаевич КОЛМОГОРОВ finit même par conjecturer dans les années 1950 que l’on ne pourra jamais
trouver un algorithme de multiplication d’entiers en $o(n^2)$.

Lors d’un séminaire sur ce sujet en 1960, un jeune étudiant soviétique, Анатолий Алексеевич КАРАЦУБА propose cependant au Maître une solution plus simple et navrante de
simplicité...

Il fait remarquer à КОЛМОГОРОВ que :

$$bc + ad = ac+bd -(a-b)(c-d)$$

En quoi cela simplifie le problème ? Quelle est alors la nouvelle complexité ?

$ \begin{eqnarray*} xy&=&(10^mx_1+x_2)(10^my_1+y_2)=10^{2m}x_1y_1+10^m(x_2y_1+x_1y_2)+x_2y_2\\ &=&10^{2m}x_1y_1+10^m(x_1y_1+x_2y_2-(x_1-x_2)(y_1-y_2))+x_2y_2\\ \end{eqnarray*} $

On voit alors que l’on n’a plus que trois produits différents à calculer au lieu
de quatre ce qui va améliorer notre complexité.

Alors la relation de récurrence devient :

$$x_k=3x_{k-1}+\lambda 2^k \qquad x_0=1$$

On obtient :

$$x_k=3(3x_{k-2}+\lambda’ 2^{k-1})+\lambda 2^k = 3^kx_0+\sum_{i=1}^k\Lambda_k 2^k =3^k+k\Lambda_k 2^k =n^{\log_2(3)} + \Lambda_kn \log n \sim n^{\log_2(3)} $$

ce qui est mieux car $\log_2(3)\approx 1,6$. Bref, avec un peu de réflexion, on
peut améliorer parfois certains algorithmes et les plus grands esprits peuvent
se tromper...

Et la recherche dichotomique d’une solution d’une équation réelle ?

Quel rapport entre la recherche dichotomique dans un tableau (ou un immeuble) et
la recherche des solutions d’une équation $f(x)=0$ dans ${R}$ ?

Pour mettre en œuvre une telle méthode, il faut donner une précision. On ne
travaille que sur des approximations décimales ou plutôt à l’aide de nombres à
virgule flottante en base 2.

Par exemple, si nous cherchons une approximation de $x^2-2=0$ par la méthode de dichotomie avec
une précision de $2^{-10}$ entre 1 et 2, il va falloir chercher un nombre (un
étage) dans un tableau (un immeuble) de $2^{10}$ nombres (étages) :

$1$ $1+2^{-10}$ $1+2\times 2^{-10}$ $1+3\times 2^{-10}$ $\cdots$ $1+2^{10}\times 2^{-10}$

Notre fonction booléenne « estFatal » {} est alors le test $x \mapsto \mathtt{x*x <= 2}$ et l’on va chercher une cellule de ce tableau par dichotomie comme on cherchait un étage dans un immeuble.

Nous obtenons :

Attention ! Il faudra s’arrêter à la précison $2^{52}$ compte-tenu de la représentation des nombres sur machine. N’hésitez pas à parcourir
ce diaporama ou ce poly pour plus de...précisions.

On « voit » {} que le nombre de tests correspond à la longueur de l’intervalle exprimé en « logarithme de la précision » {} : ici, l’intervalle est de longueur 1.

La complexité sur machine : approche expérimentale et théorique

Le problème

On dispose d’une liste de N nombres. Déterminez les triplets dont la somme est nulle.

Ici, diviser va difficilement nous permettre de régner. Intuitivement, on peut facilement diviser notre liste en 2 et rechercher les triplets annulateurs dans chaque moitié mais il faudra recommencer sur toute la liste pour chercher des triplets d’éléments appartenant à des moitiés différentes donc on a peu de chance de gagner du temps.

La complexité théorique est elle-même facile à calculer : nous en parlerons
ensuite. Nous allons plutôt commencer par une approche \og expérimentale\fg{}
pour savoir si elle se rapproche des résultats théoriques et si elle dépend du
langage utilisé.

On essaiera ensuite d’améliorer un peu l’algorithme et voir si cela a une
influence sur la complexité au sens où nous allons la calculer.

Méthode scientifique

Utilisons la force brute (pour le lecteur impatient : nous ferons mieux plus tard...) :

Comparons les temps pour différentes tailles :

On aurait plus être plus concis en utilisant des listes par compréhension :

Mais les temps sont les mêmes :

Bon, il semble que quand la taille double, le temps est multiplié par $2^3$ .

Il ne semble donc pas aberrant de considérer que le temps de calcul est de
$aN^3$ mais que vaut $a$  ?

$1,39 = a\times 400^3 $ donc $a\approx 2.17\times 10^{-8}$

Donc pour $N=1000$, on devrait avoir un temps de $2.17\times 10^{-8}\times10^9=21.7s$

Ça marche

Voici la même chose en C, sans vraiment chercher à optimiser le code.

Et on obtient :

On a la même évolution en $N^3$ avec un rapport de 8 entre chaque doublement de
taille mais la constante est bien meilleure :

$39,42 = a\times 6400^3$ d’où $a\approx 1,50\times10^{-10}$

$315,24 = a\times 12800^3$ d’où $a\approx 1.50\times 10^{-10}$

En Haskell :

et on observe :

Encore un rapport de 8 pour chaque doublement de taille mais Haskell est 60 plus
rapide que Python.

Conclusion : Python, Haskell ou C, l’algo est le même et on constate la même
progression selon le cube de la taille.

Ce qui nous intéresse en premier lieu est donc un ORDRE DΕ CROISSANCE.

Cependant, les temps sont bien distincts : ici, C va 200 fois plus vite que
Python ;-)

On a donc une approche expérimentale et les expériences sont plus facilement
menées que dans les autres sciences et on peut en effectuer de très grands
nombres.

La mauvaise nouvelle, c’est qu’il est difficile de mesurer certains facteurs
comme l’usage du cache, le comportement du ramasse-miettes, etc.

En C, on peut regarder le code assembleur généré mais avec Python, c’est plus
mystérieux.

La bonne nouvelle, c’est qu’on peut cependant effectuer une analyse mathématique
pour confirmer nos hypothèses expérimentales.


Loi de Brooks [prov.]

« Ajouter des personnes à un projet informatique en retard accroît son retard »
Cela vient du fait que partager le travail entre $N$ programmeurs permet
d’espérer un gain en $O(N)$ mais le coût associé au temps de
communication dû à la coordination et à la fusion de leurs travaux est en $O(N^2)$

in « Le nouveau dictionnaire Hacker »

Par exemple, si l’on considère l’expression :

$$f(n)=n+1+\frac{1}{n}+\frac{75}{n^2}-\frac{765}{n^3}+\frac{\cos(12)}{n^{37}}-\frac{\sqrt{765481}}{n^{412}}$$

Quand $n$ est « grand » {}, disons $10000$, alors on
obtient :

$$f(10000)=10000+1+0,0001+0,00000000075-0,0000000000000765+\text{ peanuts}$$

Tous les termes après $n$ comptent pour du beurre quand $n$ est « 
grand » {}. Donnons une définition pour plus de clarté :

« Grand O »
Soit $f$ et $g$ deux fonctions de $\mathbb{N}$ dans $\mathbb{R}$. On dit que $f$
est un « grand O » {} de $g$ et on note $f=O(g)$ ou $f(n)=O(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $|f(n)|\leqslant C|g(n)|$ pour tout $n\in \mathbb{N}$

Dans l’exemple précédent, $\frac{1}{n} \leqslant \frac{1}{1}\times 1$
pour tout entier $n$ supérieur à 1
donc $\frac{1}{n}=O(1)$.

De même, $\frac{75}{n^2} \leqslant \frac{75}{1^2}\times 1$ donc
$\frac{75}{n^2}=O(1)$ mais on peut dire mieux :
$\frac{75}{n^2}\leqslant \frac{75}{1}\times\frac{1}{n}$ et ainsi on
prouve que $\frac{75}{n^2}=O \left(\frac{1}{n}\right)$.

En fait, un grand O de $g$ est une fonction qui est au maximum majorée
par un multiple de $g$.

On peut cependant faire mieux si l’on a aussi une
minoration.

C’est le moment d’introduire une nouvelle définition :

« Grand Oméga »
Soit $f$ et $g$ deux fonctions de $\mathbb R$ dans lui-même. On dit que $f$
est un « grand Oméga » {} de $g$ et on note $f=\Omega(g)$ ou $f(n)=\Omega(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $|f(n)|\geqslant C|g(n)|$ pour tout $n\in \mathbb N^*$

Comme $\Omega$ est une lettre grecque, on peut, par esprit
d’unification, parler de « grand omicron » {} au lieu de « grand O » {}...

Si l’on a à la fois une minoration et une majoration, c’est encore plus précis et nous incite à
introduire une nouvelle définition :

Grand Théta
$f=\Theta(g)\Longleftrightarrow f=O(g)\ \ \wedge \ \ f=\Omega(g)$

Analyse mathématique

Le temps d’exécution est la somme des produits (coût $\times$ fréquence) pour
chaque opération.

  • le coût dépend de la machine, du compilateur, du langage ;
  • la fréquence dépend de l’algorithme, de la donnée en entrée.

Dans un langage comme C, on peut avoir le code assembleur associé et donc
estimer le coût en cycles du processeur.

Dans des langages de plus haut niveau comme Python, c’est beaucoup moins
immédiat mais dans le cas de l’accès à un élément d’une liste on peut en gros le
savoir car une liste de Python est construite en...C. Voici par exemple le code
permettant d’accéder à un élément dans une liste Python :

Dans notre algorithme des 3 sommes en python, on peut donc gagner du temps :

C’est mieux mais le rapport est toujours de 8 entre chaque doublement :

En C, ça ne changera rien, car le compilateur est intelligent et a remarqué tout
seul qu’il pouvait garder en mémoire certains résultats.

On peut changer la taille des nombres utilisés. Cela ralentira le traitement
mais le rapport de 8 est toujours mis en évidence :

On peut visualiser en échelle log-log :

JPEG - 27.2 ko

C’est assez rectiligne.

Regardons de nouveau le code des trois sommes et comptons le nombre d’opérations élémentaires :
ces opérations élémentaires représentent notre
unité de temps théorique. Dans certains cas, il est difficile de les
distinguer.

Ici, notre algorithme est suffisamment basique pour pouvoir distinguer des
opérations que nous considèrerons à coût constant : une déclaration de variable,
une affectation, l’accès à un élément d’une liste, une somme d’entiers ou un
incrément.

Chacune de ces actions va compter pour une unité. Il ne reste plus qu’à
déterminer leurs fréquences dans l’algorithme.

OPÉRATION FRÉQUENCE
Déclaration de la fonction et du paramètre (l. 1) 2
Déclaration de N, cpt et i (l. 2, 3 et 4) 3
Affectation de N, cpt et i (l. 2, 3 et 4) 3
Déclaration de xi (l. 5) N
Affectation de xi (l. 5) N
Accès à xs[i] (l. 5) N
Déclaration de j (l.6) N
Calcul de l’incrément de i (l. 6) N
Affectation de j (l.6) N
Déclaration de sij (l. 7) $S_1$
Affectation de sij (l. 7) $S_1$
Accès à xs[j] (l.7) $S_1$
Somme (l.7) $S_1$
Déclaration de k (l.8) $S_1$
Incrément de j (l. 8) $S_1$
Affectation de k (l.8) $S_1$
Accès à x[k] (l.9) $S_2$
Calcul de la somme (l.9) $S_2$
Comparaison à 0 (l.9) $S_2$
Incrément de cpt (l.9) entre 0 et $S_2$
Affectation de la valeur de retour (l.11) 1

Que valent $S_1$ et $S_2$  ?
Pour $S_1$ il s’agit du nombre d’itérations de la
boucle incrémentée par j et
pour $S_2$ ce sera k.

Cela implique un petit travail classique sur les sommes voire les doubles sommes d’entiers.

$$S_1=\sum_{i=0}^{N-1}N-(i+1)=\sum_{i’=0}^{N-1}i’=\frac{N(N-1)}{2}$$

$ \begin{eqnarray} S_2&=&\sum_{i=0}^{N-1}\sum_{j=i+1}^{N-1}N-(j+1)\\ &=&\sum_{i=0}^{N-1}\sum_{j’=0}^{N-(i+2)}j’\\ &=&\sum_{i=0}^{N-2}\frac{(N-(i+2))(N-(i+1))}{2} \\ &=&\sum_{i’=1}^{N-2}\frac{i’(i’+1)}{2}\\ &=&\frac{1}{2}\left(\sum_{i=1}^{N-2}i^2+\sum_{i=1}^{N-2}i\right)\\ &=&\frac{1}{2}\left(\frac{(N-2)(2N-3)(N-1)}{6}+\frac{(N-2)(N-1)}{2}\right)\\ &=&\frac{N(N-1)(N-2)}{6} \end{eqnarray} $

Notons $a$ le temps constant d’affectation, $d$ le temps constant de
déclaration, $x$ le temps constant d’accès à une cellule, $s$ le temps constant
d’une somme, $c$ le temps constant d’une comparaison.

Le temps d’exécution vérifie :

$\tau(N) \leqslant (2d+3d+3a+a) + (d+a+x+d+s+a)N+(d+a+x+s+d+s+a)S_1 +(x+s+c+s)S_2$

Or $S_1\sim N^2$ et $S_2\sim N^3$ quand $N$ est « grand » {}.

Finalement...

$$\tau(N)=O(N^3)$$

...et ce, que l’on utilise C, Python, BrainFuck, etc.

C’est aussi ce que l’on a observé expérimentalement

Moralité, on ne s’occupe que de ce qu’il y a dans la boucle la plus profonde et
on oublie le reste....

Plus fort que la dichotomie : l’algorithme de Héron

La dichotomie est peu efficace [3] pour trouver la solution d’une équation numérique
par rapport à l’algorithme de Héron. Pour démontrer cette supériorité du point
de vue de la complexité, il nous faut introduire aux élèves quelques outils mathématiques.

Le mathématicien Héron d’Alexandrie n’avait pas attendu Newton et le
calcul différentiel pour trouver une méthode permettant de déterminer
une approximation de la racine carrée d’un nombre entier positif puisqu’il a
vécu seize siècles avant Sir Isaac.

Si $x_n$ est une approximation strictement positive par défaut de
$\sqrt{a}$, alors $a/x_n$ est une approximation par excès de $\sqrt{a}$
et vice-versa.

La moyenne arithmétique de ces deux approximations est
$\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$ et constitue une meilleure
approximation que les deux précédentes.

On peut montrer c’est une approximation par excès (en développant
$\left(x_n-\sqrt{a}\right)^2$ par exemple).

En voici deux versions, une récursive et une itérative.

%\beginmulticols2

Ce qui donne par exemple :

Est-ce que la suite des valeurs calculées par la boucle converge vers $\sqrt{2}$ ?

Nous aurons besoin de deux théorèmes que nous admettrons et dont nous ne
donnerons que des versions simplifiées.

Théorème de la limite monotone
Toute suite croissante majorée (ou décroissante minorée) converge.

Un théorème fondamental est celui du point fixe. Il faudrait plutôt parler des
théorèmes du point fixe car il en existe de très nombreux avatars qui portent
les noms de mathématiciens renommés : Banach, Borel, Brouwer, Kakutani,
Kleene,…Celui qui nous intéresserait le plus en informatique est celui de
Knaster-Tarski. Ils donnent tous des conditions d’existence
de points fixes (des solutions de $f(x)=x$ pour une certaine fonction). Nous
nous contenterons de la version light vue au lycée.

Un théorème light du point fixe
Soit I un intervalle fermé de $\mathbb R$ , soit $f$ une fonction continue de Ι vers I
et soit $(r_n)$ une suite d’éléments de I telle que $r_{n+1}=f(r_n)$ pour tout
entier naturel $n$ . SI $(r_n)$ est convergente ALORS sa limite est UΝ point
fixe de $f$ appartenant à I.

Cela va nous aider à étudier notre suite définie par $r_{n+1}= f(r_n)=\frac{r_n + \frac{2}{r_n}}{2}$ et $r_0=1$ . On peut alors démontrer par récurrence que

  • pour tout entier naturel non nul $n$, on a $r_n \geqslant \sqrt{2}$ ;
  • la suite est décroissante ;
  • $\sqrt{2}$ est l’unique point fixe positif de $f$.

On peut alors conclure et être assuré que notre algorithme va nous permettre d’approcher $\sqrt{2}$.

Quelle est la vitesse de convergence ?

Ici, cela se traduit par « combien de décimales obtient-t-on en plus à chaque itération ? » . Introduisons la notion d’ordre d’une suite :

Ordre d’une suite - Constante asymptotique d’erreur
Soit $(r_n)$ une suite convergeant vers $\ell$ . S’il existe un entier $k>0$
tel que :

$$ \displaystyle\lim_{n\to +\infty}\frac{|r_{n+1}-\ell|}{|r_n-\ell|^k}=C $$

avec $C\neq 0$ et $C\neq +\infty$ alors on dit que $(r_n)$ est d’ordre $k$ et que C est la constante
asymptotique d’erreur.

Déterminons l’ordre et la constante asymptotique d’erreur de la suite de
Babylone donnant une approximation de $\sqrt{2}$ .
On démontre que

$$ \left|r_{n+1} - \sqrt{2}\right| = \left| \frac{(r_n-\sqrt{2})^2}{2r_n}\right| $$

Ainsi la suite est d’ordre 2 et sa constante asymptotique est
$\frac{1}{2\sqrt{2}}$ . Ici, on peut même avoir une idée de la vitesse sans étude
asymptotique.

En effet, on a $r_n \geqslant 1$ donc

$$ \left|r_{n+1} - \sqrt{2}\right| \leqslant \left| (r_n-\sqrt{2})^2\right| $$

Le nombre de décimales d’un
nombre positif plus petit que 1 est $-\log_{10}x$ . En posant
$d_n=-\log_{10}|r_n-\sqrt{2}|$ on obtient donc que $d_{n+1} \geqslant 2d_n$  : à
chaque tour de boucle, on double au minimum le nombre de bonnes décimales.

La
précision de la machine étant de 16 décimales si les nombres sont codés en
binaires sur 64 bits, il faut au maximum 6 itérations pour obtenir la précision
maximale
.

Annexe : exemple de TP sur les relatifs et le complément à 2 puissance n

Le monde se sépare en 10 catégories : ceux qui comprennent cette phrase
et les autres.

Nous allons, pour favoriser la compréhension et simplifier les
écritures, travailler sur 8 bits. Cela signifie que nos nombres
entiers peuvent être codés avec 8 chiffres égaux à 0 ou 1 en base 2.

  1. Écrivez les nombres de 0 à 17 en base 2. Quel est le plus grand
    nombre que l’on peut écrire avec 8 bits ?
  2. En fait, on aimerait avoir des entiers signés, c’est-à-dire
    pouvoir représenter des entiers tant positifs que négatifs avec
    cette contrainte.

On va donc réserver un bit (le plus à gauche) pour indiquer le signe
du nombre : on mettra un 0 s’il est positif et un 1 s’il est négatif.

Écrivez en compréhension l’ensemble des nombres que l’on peut ainsi
représenter et qui se note sur Haskell Int8.

  1. Bon, pas de problème...enfin si quand même un peu. Que
    pensez-vous de ces deux nombres :
  1. On voudrait additionner facilement ces nombres. Une idée serait
    d’utiliser l’addition posée comme à l’école primaire. Par exemple
    pour calculer 5 + 9

On trouve bien 14.

Et maintenant si on veut calculer 5 + (-9), qu’est-ce que cela donne avec ce système ?

  1. Considérez maintenant le nombre m = 11111111 et
    ajoutez-lui 1 (vous n’avez que 8 bits à disposition). Que vaut
    m+1 ? Que cela vous donne-t-il comme idée ?

Considérez n=11111110 et calculez n+2.

Considérez p=11111100 et calculez n+4.

Considérez p=11111000 et calculez n+8.

Considérez p=11111010 et calculez n+6.

Des idées ?

  1. Si l’on considère que $ 2^8$ vaut 0 en Int8, ce qui
    est d’ailleurs le cas :

Que pensez-vous alors de x et de $2^8-|x|$ si x est négatif ?

Comment s’écrit $2^8-|x|$ sur 8 bits ?

Bon, vous commencez à voir ce qui se passe ?

Alors expliquez ce qui se passe ici (illustration en Haskell pour faciliter
l’utilisation d’enteirs 8 bits) :

Généralisez, énoncez votre norme de représentation des entiers sur 8
bits, énoncez un « truc » pour trouver facilement de tête le
complément à $ 2^8$.


notes

[1C’est ce qui correspondra par exemple en informatique au
parcours d’une liste chaînée.

[2Voir par exemple le bug de l’an 2038.

[3Pour visualiser un algorithme
dichotomique très efficace, on peut regarder le tri rapide dansé

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