Introduction à l'algorithmique et à la complexité

Introduction l’algorithmique et à la complexité

Frédéric Herbreteau, Bordeaux INP/LaBRI (frederic.herbreteau@bordeaux-inp.fr)

Qu’est-ce qu’un algorithme?

Si l’on veut résoudre un problème à l’aide d’un ordinateur, il est indispensable d’avoir recours à un algorithme car un ordinateur ne peut exécuter que des ordres précis et sans ambiguïté (Stockmeyer et Chandra, “Les problèmes intrinsèquement difficiles”)

Définition:

Procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une séquence d’étapes de calcul qui transforment l’entrée en sortie (Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, “Introduction à l’algorithmique”)

Origine de l’algorithmique

bg right:30% fit

  • “Algorithme” vient de Al-Khwarizmi (mathématicien, astronome, géographe du IXè siècle, Bagdad)
  • Deux ouvrages notables:
    • “al-Kitāb al-Mukhtaṣar fī Ḥisāb al-Jabr wal-Muqābalah”: résolution d’équation du 2nd degré ($ax^2 + bx + c = 0$)
    • “kitab al-jam’ wa’l-tafriq al-ḥisāb al-hindī”: arithmétique en numération indienne
\[\begin{array}{r} CXLIII \\ \times \ \ \ \ \ \ \ \ XVI \\ \hline \end{array} \qquad \text{ vs. } \qquad \begin{array}{r} 143 \\ \times \ \ 16 \\ \hline \end{array}\]

Problèmatiques

  • L’algorithme fonctionne-t-il? (terminaison, correction)
  • Est-il efficace? (complexité)
  • Peut-on faire mieux?

Exemple: deviner un nombre choisi entre 1 et 1000

  • algorithme trivial: jusqu’à 1000 questions
  • algorithme optimal: au plus 10 questions

Un premier problème: $f(x)=0$

bg right:40% fit

On cherche à résoudre numériquement une équation de la forme:

\[f(x) = 0 \qquad \text{ avec } \ f \, : \, \mathbb{R} \to \mathbb{R} \text{ continue}\]

Les solutions, ou zéros, ne sont généralement pas calculables, ni même représentables en machine.

On va approximer finement une solution $\alpha$:

  • étant donnée une constante réelle $\epsilon > 0$,
  • calculer $x$ tel que $\vert x - \alpha\vert \le \epsilon$

Résolution par balayage

Principe algorithmique

On suppose connus:

  • un intervalle $[a; b]$,
  • une fonction $f$ continue sur $[a; b]$,
  • et une constante réelle $\epsilon > 0$.

Si $f$ admet un zéro $\alpha \in [a; b]$, on veut calculer $x \in [a; b]$ tel que $\vert x - \alpha\vert \le \epsilon$.

Principe:

  • Balayage de l’intervalle $[a; b]$ par pas de $\epsilon$;
  • Une valeur $x$ telle que $f(x) \cdot f(x + \epsilon) \le 0$ est une approximation à $\epsilon$ près de $\alpha$ (par le théorème des valeurs intermédiaires).

Est-ce que l’algorithme termine?

def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None:
    x: float = a
    while x <= b:
        xx: float = min(b, x + eps)
        if f(x) * f(xx) <= 0:
            return x
        x += eps
    return None # pas de zéro trouvé

Soit $(x_k)_{k \in \mathbb{N}}$ la suite définie par $x_k = a + k \cdot \epsilon$.

findZeroLinear calcule successivement les termes de la suite $(x_k)_{k \in \mathbb{N}}$ tels que $x_k \le b$

Donc, nombre d’itérations maximum: $\frac{1}{\epsilon}(b - a) + 1$

Qu’aimerait-on que cet algorithme calcule?

def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None:
    x: float = a
    while x <= b:
        xx: float = min(b, x + eps)
        if f(x) * f(xx) <= 0:
            return x
        x += eps
    return None # pas de zéro trouvé
  • POSTCOND souhaitée:
    • si $f$ admet un zéro $\alpha \in [a; b]$, alors findZeroLinear retourne $x \in [a;b]$ tel que $\vert x - \alpha\vert \le \epsilon$
    • sinon, findZeroLinear retourne None

Exercice: que se passe-t-il pour $f(x)=x^2$ et $[a; b] = [-1; 1]$ et $\epsilon = 0.15$?

Que calcule réellement cet algorithme?

def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None:
    x: float = a
    while x <= b:
        xx: float = min(b, x + eps)
        if f(x) * f(xx) <= 0:
            return x
        x += eps
    return None # pas de zéro trouvé
  • POSTCOND réelle:
    • si findZeroLinear retourne $x \neq$ None, alors $f$ admet un zéro dans $[x; x+\epsilon]$
    • si, findZeroLinear retourne None, on ne sait pas si $f$ a un zéro dans $[a; b]$

Évaluation expérimentale de la complexité

Temps de calcul inversement propositionnel à $\epsilon$: jusqu’à $\frac{1}{\epsilon}(b - a) + 1$ itérations.

Exemple: $f(x) = \cos(x)-x$ et $a=0$ et $b=2.5$

$\epsilon$ temps (s.) Itérations
$10^{-1}$ $0.00007$ 8
$10^{-3}$ $0.00164$ 740
$10^{-5}$ $0.06923$ 73909
$10^{-7}$ $6.53705$ 7390852

Pour passer à $\epsilon = 10^{-14}$, il faut 10 millions de fois plus de temps $\sim 2$ ans

Bilan

  • Algorithme partiel pour le problème $f(x)=0$
    • qui termine
    • qui détecte certains zéro (inversion de signe de $f$)
  • La complexité de l’algorithme
    • dépend du nombre d’itérations de la boucle while
    • qui correspond aux nombres de termes de la suite $(a_k)_{k\in\mathbb{N}}$ tels que $a_k \le b$.
    • c’est à dire: $\frac{1}{\epsilon}(b - a) + 1$

Accroître la précision d’un facteur $10$ multiplie le temps de calcul par $10$

Peut-on faire mieux?

Recherche dichotomique

Principe algorithmique

  • On suppose que $f(a)$ et $f(b)$ n’ont pas le même signe
  • Par le théorème des valeur intermédiaires, $f$ admet un zéro dans $[a; b]$
  • On examine la valeur $f(p)$ pour $p$ au milieu de $[a; b]$
    • si $f(a)$ et $f(p)$ n’ont pas le même signe, alors $f$ a un zéro dans $[a; p]$
    • sinon, $f(p)$ et $f(b)$ n’ont pas le même signe, et $f$ admet un zéro dans $[p; b]$
  • On recommence jusqu’à avoir un intervalle de largeur inférieure à $\epsilon$

NB: si $f(a)$ et $f(b)$ ont le même signe, $f$ peut néanmoins avoir un zéro dans $[a; b]$

Terminaison de l’algorithme

def findZeroBin(f: Function, a: float, b: float, eps: float) -> float | None:
    l: float = a; r: float = b
    while r - l > eps:
        p: float = (l + r) / 2
        if f(a) * f(p) <= 0:
            r = p
        else:
            l = p
    return l

Chaque itération divise par $2$ la taille de l’intervalle $[l; r]$.

Nombre d’itérations de la boucle while: plus petit entier $k \in \mathbb{N}$ tel que $\frac{(b-a)}{2^k} \le \epsilon$.

Donc $k = \log_2\left(\frac{(b-a)}{\epsilon}\right) = \log_2(b-a) - \log_2(\epsilon)$ itérations au plus.

Correction de l’algorithme

def findZeroBin(f: Function, a: float, b: float, eps: float) -> float:
    l: float = a; r: float = b
    while r - l > eps:
        p: float = (l + r) / 2
        if f(a) * f(p) <= 0:
            r = p
        else:
            l = p
    return l
  • PRECOND: $f(a) \cdot f(b) < 0$
  • POSTCOND: findZeroBin retourne $x \in [a;b]$ tel que $\vert x - x_0\vert \le \epsilon$ où $x_0 \in [a; b]$ est un zéro de $f$
  • INVARIANT: $f$ admet un zéro dans $[l; r]$

Évaluation expérimentale de la complexité

  • recherche linéaire: temps proportionnel à $\frac{1}{\epsilon} \cdot (b - a)$
  • recherche dichotomique: temps proportionnel à $\log_2(b - a) - \log_2(\epsilon)$

Exemple: $f(x) = \cos(x)-x$ et $a=0$ et $b=2.5$

$\epsilon$ Balayage (s.) Itérations Dichotomie (s.) Itérations
$10^{-1}$ $0.00007$ $8$ $0.000007$ $5$
$10^{-3}$ $0.00164$ $740$ $0.000011$ $12$
$10^{-5}$ $0.06923$ $73909$ $0.000016$ $18$
$10^{-7}$ $6.53705$ $7390852$ $0.000023$ $25$

Bilan

  • la recherche dichotomique de zéro suppose que $f(a)$ et $f(b)$ sont de signes opposés
  • elle encadre un zéro de $f$ par un intervalle $[l; r]$ dont la taille est divisée par $2$ à chaque itération
  • la convergence est rapide: $\log_2(b-a) - \log_2(\epsilon)$

Peut-on faire mieux?

La méthode de Newton

Principe algorithmique

bg right:30% fit

La méthode de Newton consiste à approximer un zéro $\alpha$ de $f$ par calcul d’une suite $(x_k)_{k \in \mathbb{N}}$ qui coverge vers $\alpha$.

  • À partir de $x_0=a$ (une valeur choisie)
  • On approxime $f$ en $x_0$ par sa tangente $t_0$ en $x_0$
  • La solution de $t_0(x)=0$ donne $x_1$
  • On recommence à partir de $x_1$, jusqu’à obtenir $\vert x_{k+1} - x_k\vert \le \epsilon$

Caractérisation mathématique

bg right:30% fit

On suppose que $f$ est dérivable

La tangente en $x_k$ est la droite d’équation:

\[t_k(x) = f(x_k) + f'(x_k) \cdot (x - x_k)\]

Le point $x_{k+1}$ est la solution de $t_k(x)=0$.

La méthode de Newton calcule la suite $(x_k)_{k \in \mathbb{N}}$:

\[\begin{cases} x_0 = a & \\ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \end{cases}\]

jusqu’à $\vert x_{k+1} - x_k\vert \le \epsilon$

Conditions et vitesse de convergence

!!! La méthode de Newton ne converge pas toujours !!!

Si $f$ est 2 fois dérivable, et $\frac{1}{f’}$ et $f’’$ sont bornées, il existe une constante $K > 0$ tq:

\[K \cdot \vert x_n - \alpha\vert \le (K \cdot \vert x_0 - \alpha\vert)^{2^n}\]

On obtient une convergence quadratique si $x_0 = a$ est proche de $\alpha$: $\vert a - \alpha\vert < \frac{1}{K}$

En passant au logarithme, on garantit une précision $\epsilon > 0$ avec $n$ itérations:

\[n > \log_2 \left(\frac{\log (K \epsilon)}{\log (K \vert a - \alpha\vert)}\right) - 1\]

$\to$ le nombre d’itérations dépend du double logarithme de $\epsilon$

$\to$ le nombre de chiffres significatifs double à chaque itération

Évaluation expérimentale de la complexité

  • recherche linéaire: temps proportionnel à $\frac{1}{\epsilon}\cdot (b-a)$
  • recherche dichotomique: temps proportionnel à $\log_2(b-a) - \log_2(\epsilon)$
  • méthode de Newton: temps propositionnel à $\log_2(\frac{\log(\epsilon)}{\log(\vert a-\alpha\vert)})$

Exemple: $f(x) = \cos(x)-x$ et $a=0$ et $b=2.5$

$\epsilon$ Balayage (s.) Iter. Dichotomie (s.) Iter. Newton (s.) Iter.
$10^{-1}$ $0.00007$ $8$ $0.000007$ $5$ $0.000006$ $3$
$10^{-3}$ $0.00164$ $740$ $0.000011$ $12$ $0.000005$ $4$
$10^{-5}$ $0.06923$ $73909$ $0.000016$ $18$ $0.000007$ $5$
$10^{-7}$ $6.53705$ $7390852$ $0.000023$ $25$ $0.000007$ $5$

Conclusion

Un algorithme pour $f(x)=0$

On peut combiner les 3 algorithmes pour obtenir une solution efficace:

  1. findZeroLinear pour trouver un intervalle où $f$ change de signe $\to$ il contient un zéro $\alpha$ de $f$;
  2. puis findZeroBin pour trouver un plus petit intervalle autour de $\alpha$ où $f$ remplit les critères de la méthode de Newton;
  3. enfin findZeroNewton pour approximer $\alpha$ avec une très grande précision.

Chaque algorithme a des propriétés propres: terminaison, correction, complexité,… à exploiter au mieux.

Limites de l’évaluation expérimentale de la complexité

Exemple: findZeroLinear avec $f(x) = \cos(x)-x$ et $a=0$ et $b=2.5$

$\epsilon$ Python temps (s.) C (-O0) temps (s.) C (-O3) temps (s.)
$10^{-1}$ $0.00007$ $0.005$ $0.005$
$10^{-3}$ $0.00164$ $0.005$ $0.005$
$10^{-5}$ $0.06923$ $0.007$ $0.005$
$10^{-7}$ $6.53705$ $0.083$ $0.051$
  • le temps mesuré dépend: de l’architecture, de l’OS, du langage, du compilateur,…
  • mais la tendance est la même: temps proportionnel à $\frac{1}{\epsilon} \cdot (b - a)$

Limites du calcul numérique

Les nombres réels ont une représentation approchée en machine:

  • erreurs d’arrondis qui se propagent
  • test d’égalité impossible: tester la proximité à $\epsilon$ près
  • …

Exemple: findZeroLinear avec $f(x) = x^2$, sur $[-1; 1]$ avec $\epsilon = 0.1$ retourne None

x=-0.3 
x=-0.19999999999999998
x=-0.09999999999999998
x=2.7755575615628914e-17

Bilan

  • La programmation d’algorithmes numériques doit tenir compte de la limitations de la représenation des nombres

Exemples:

  • Python: nombres flottants représentés sur 53 bits (16 chiffres significatifs)
  • C: float 32 bits et double 64 bits (IEC 60559)
  • Bibliothèques et outils avec flottants “multi-précision” (mpmath en Python, matlab)
  • En pratique, l’évaluation expérimentale de la complexité est cruciale pour optimiser une implémentation donnée
  • L’analyse d’algorithme permet de choisir un algorithme adéquat pour un problème donné (terminaison, correction, complexité théorique,…)

Exercices supplémentaires

Exercice 1

def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None:
    x: float = a
    while x <= b:
        xx: float = min(b, x + eps)
        if f(x) * f(xx) <= 0:
            return x
        x += eps
    return None # pas de zéro trouvé

Montrer que sous hypothèse $f(a) \cdot f(b) \le 0$, l’algorithme findZeroLinear satisfait:

  • si findZeroLinear retourne None, alors $f$ n’a pas de zéro dans $[a; b]$
  • sinon, elle retourne $x \in [a; b]$ tel que $f$ admet un zéro dans $[x; x+\epsilon]$

Exercice 2

En utilisant le notebook Jupyter:

  1. tester les algorithmes sur les fonctions suivantes:
    1. $f(x) = x^2$
    2. $f(x) = x^3 − 2x + 2$
  2. Reproduire le problème de convergence décrit sur cette page. Que se passe-t-il?