RUDIMENTS D'ALGORITHMIE

On commencera par se procurer un environnement de développement pour Python, par exemple ici. Quelle que soit la version choisie, on a sous une forme ou une autre deux zones : la console, pour effectuer les calculs, et l'éditeur, pour écrire les programmes.


1 - Programmes, entrées, sorties


En Python, un programme, ça commence par def, suivi du nom du programme, d'une paire de parenthèses, et de deux points : c'est l'en-tête du programme. Le corps du programme est indenté (de quatre espaces vers la droite) par rapport à cet en-tête.

def MonPremierProgramme() :
    return "Bonjour le Monde !"

Testons ce programme (qu'on a donc écrit dans l'éditeur) dans la console. Pour utiliser un programme, on écrit son nom suivi des parenthèses.

>>> MonPremierProgramme()
"Bonjour le Monde !"

Le programme ci-dessus n'a pas d'entrée. Lorsqu'il y en a, on les indique, dans l'ordre, à l'intérieur des parenthèses.

def Successeur(x, pas) :
    return x + pas

>>> Successeur(4, 1)
5

On peut donner des valeurs par défaut aux dernières entrées.

def Successeur(x, pas = 1) :
    return x + pas

Dans ce cas, on n'est pas obligé, lorsqu'on utilise le programme, de préciser ces entrées : on dit qu'elles sont facultatives. Lorsqu'on ne les précise pas, elles prennent leurs valeurs par défaut ; si on les précise, elles prennent les valeurs qu'on a précisé (évidemment).

>>> Successeur(10, 3)
13
>>> Successeur(41)
42

Enfin, la plupart des programmes ont une (ou plusieurs) sortie(s). Elles sont précédées du mot-clé return. On ne l'a pas encore dit, mais les programmes sont des suites d'instructions, exécutées dans l'ordre où elles sont écrites ; l'instruction return arrête (irrémédiablement) le programme (même s'il reste des lignes après) et produit le résultat (c'est-à-dire ce qui est écrit après le return).
    Les programmes ci-dessus ont tous une sortie, et on l'a vu à chaque fois s'afficher dans la console lorsqu'on utilise le programme. Mais on peut aussi utiliser un programme au milieu d'un calcul.

>>> Successeur(10) - 5
6

Dans l'exemple ci-dessus, le résultat du programme Successeur, appliqué à l'entrée 10, n'est pas affiché (c'est \(11\)), mais il est utilisé dans le calcul \(11 - 5 = 6\) et c'est ce résultat final qui est affiché.
    En fait, il n'y a pas de différence entre un programme et un calcul, et évidemment on peut imbriquer autant de calculs/programmes qu'on le souhaite.

>>> Successeur(10, Successeur(Successeur(1) + 4) - 2)
15

?


2 - Variables


Dans un programme on utilise en général des variables. N'importe quelle suite de caractères (lettres, chiffres ou tiret-du-bas), ne commençant pas par un chiffre, peut servir de variable. Seuls sont interdits les mots-clés (on en a déjà rencontré deux : def et return).
    Alors les variables servent dans trois cas. Commençons par celui qu'on a déjà rencontré : pour désigner des objets dont on ne connaît pas la valeur au moment où l'on écrit le programme. C'est le cas des entrées : dans l'exemple ci-dessous, on ne connaît pas les valeurs de a, b et c. Celles-ci seront précisées lorsqu'on fera un calcul avec le programme.

def PetiteSomme(a, b, c) :
    return a + b + c

Deuxième utilisation (la plus évidente) : les variables servent, comme leur nom l'indique, à désigner des quantités dont la valeur est amenée à changer au cours du temps. Imaginons le problème suivant : on part de zéro, et cinq fois de suite on ajoute un et on multiplie par deux. Qu'obtient-on ?

def MonDeuxièmeProgramme() :
    x = 0
    for _ in range(5) :
        x += 1
        x *= 2
    return x

>>> MonDeuxièmeProgramme()
62

On parlera du nouveau mot-clé for plus tard. Indiquons ici seulement l'opérateur d'affectation, noté =, qui sert à définir ou à changer la valeur d'une variable ; et les opérateurs de modification, qui sont des raccourcis pour changer la valeur. On peut indifféremment écrire x *= 2 ou x = x * 2, par exemple.

Troisième utilisation des variables : elles peuvent servir de mémoire, pour éviter d'effectuer des calculs plusieurs fois (si on écrit le même calcul trois fois, l'ordinateur l'effectuera trois fois, et ça c'est mal).

from numpy import sqrt
def RésoudreSecondDegré(a, b, c) :
    \(\Delta\) = b ** 2 - 4 * a * c
    x0 = -b / (2 * a)
    h = sqrt(\(\Delta\)) / (2 * a)
    return (x0 - h, x0 + h)

Testons avec l'équation \(x^2 - 6x + 5 = 0\).

>>> RésoudreSecondDegré(1, -6, 5)
(1.0, 5.0)

?


3 - Tests et branchements conditionnels


Un test est un calcul dont le résultat est vrai ou faux, c'est-à-dire True ou False en Python. La plupart des tests font intervenir un opérateur de comparaison ; ces derniers sont au nombre de six.

opérateursignification
==égal à
!=différent de
<=au plus égal à/inférieur ou égal à
<plus petit que/strictement inférieur à
>=au moins égal à/supérieur ou égal à
>plus grand que/strictement supérieur à

Mais on peut aussi écrire des programmes qui sont des tests. Par exemple, avec l'opérateur modulo, qui se note % et qui renvoie le reste dans la division euclidienne, on peut tester si un nombre est pair (les nombres pairs étant ceux dont le reste dans la division par deux est nul).

def EstPair(x) :
    return x % 2 == 0

Avec un test, on peut réaliser un branchement conditionnel, c'est-à-dire un morceau de programme qui n'est exécuté que dans certains cas. Premier exemple, où l'on distingue deux cas (avec les mots-clés if et else).

def ValeurAbsolue(x) :
    if x >= 0 :
        return x
    else :
        return -x

Deuxième exemple, où l'on distingue trois cas (avec les mots-clés if, elif et else). On pourrait distinguer quatre cas ou plus en rajoutant d'autres clauses elif.

def Signe(x) :
    if x > 0 :
        return 1
    elif x == 0 :
        return 0
    else :  # donc x < 0
        return -1

Au passage encore une nouveauté : sur une ligne, tout ce qui suit un croisillon (c'est le caractère #, avec deux barres horizontales, que merci pour lui on n'appellera pas « hachetague », et encore moins dièse qui lui a deux barres verticales ♯) est un commentaire, c'est-à-dire un morceau de programme qui n'est pas exécuté. On s'en sert pour donner des explications ou pour se rappeler de quelque chose, si un jour on relit le programme (et qu'on ne se souvient plus comment il marche).

On peut évidemment imbriquer des tests. Par exemple pour obtenir le maximum de trois nombres, on peut faire ceci...

def Max_3(a, b, c) :
    if a >= b :
        if a >= c :
            return a
        else :
            return c
    else :
        if b >= c :
            return b
        else :
            return c

...mais cela devient rapidement peu lisible. Plus élégamment on obtient le même résultat avec cette solution (qui est en fait rigoureusement identique : le programme précédent contient deux fois le même code, qu'on regroupe dans un programme auxiliaire et on utilise ce dernier deux fois ; c'est pareil mais c'est plus court à écrire, et plus facile à comprendre).

def Max_2(a, b) :
    if a >= b :
        return a
    else :
        return b
def Max_3(a, b, c) :
    return Max_2(Max_2(a, b), c)

?


4 - Boucles inconditionnelles (« POUR »)


Les boucles servent à répéter plusieurs fois un même bloc d'instructions. Il y en a deux sortes : voyons d'abord celles pour lesquelles on connaît à l'avance le nombre de répétitions.

# Calcul de 1 + 2 + 3 + 4 + ... + 1000
def Somme_1() :
    s = 0
    for i in range(1, 1000 + 1) :
        s += i
    return s

>>> Somme_1()
500500

La fonction range(a, b, pas = 1) indique l'intervalle dans lequel va varier le compteur. Le premier paramètre a est la valeur de départ (incluse), le deuxième paramètre est la valeur d'arrivée (exclue). Le troisième paramètre est facultatif : par défaut il vaut \(1\) et on n'est pas obligé de le préciser.
    Attention à la subtilité : la valeur d'arrivée est toujours exclue. Dans l'exemple ci-dessus, pour aller jusqu'à \(1000\), il faut donc donner \(1000 + 1\) comme valeur d'arrivée. On peut bien sûr écrire \(1001\), mais je préfère écrire \(1000 + 1\) pour insister sur le fait qu'on va jusqu'à \(1000\).

Abordons des choses plus subtiles : écrivons un programme qui calcule la somme des nombres impairs entre \(a\) et \(b\). Il y a une première difficulté : il faut savoir si l'on commence de \(a\) (parce qu'il est lui-même impair) ou bien de \(a + 1\).

def SommeImpairsEntreBornes(a, b) :
    s = 0
    if a % 2 == 0 :  # on regarde la parité de a
        début = a + 1
    else :
        début = a
    for i in range(début, b + 1, 2) :
        s += i
    return s

Variante : calculons la somme des \(n\) premiers nombres impairs. Le \(i\)-ème nombre impair étant bien sûr \(2i - 1\).

def SommeImpairs(n) :
    s = 0
    for i in range(1, n + 1) :
        s += 2 * i - 1
    return s

On teste, et on remarque cette propriété importante (qu'on va ré-utiliser dès la section suivante) : la somme des \(n\) premiers nombres impairs est égale à \(n^2\).

>>> SommeImpairs(0)
0
>>> SommeImpairs(1)
1
>>> SommeImpairs(2)
4
>>> SommeImpairs(3)
9
>>> SommeImpairs(4)
16
>>> SommeImpairs(5)
25

Continuons à compliquer les choses. On veut calculer, pour un nombre \(x\) donné, la somme \[ 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + \dots + \frac{x^n}{n!}. \] Numérotons les termes de cette somme à partir de \(i = 0\). Ainsi \(1\) a le numéro zéro, \(x\) correspond à \(i = 1\), puis \(x^2/2\) à \(i = 2\), et plus généralement \(x^i/i!\) est le terme numéro \(i\). On remarque qu'on passe du terme numéro \(i\) au terme numéro \(i + 1\) en multipliant par \(x\) et en divisant par \(i + 1\).

def Exp(x, n) :
    s = 0 ; terme = 1
    for i in range(0, n + 1) :
        s += terme
        terme *= x / (i + 1)
    return s

>>> Exp(1, 20)
2.7182818284590455
>>> Exp(2, 30)
7.389056098930649

Un dernier exemple pour la route. Écrivons un programme qui calcule la somme \[ x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040} + \dots + (-1)^n \times \frac{x^{2n + 1}}{(2n + 1)!}. \] Si l'on numérote les termes à partir de \(i = 0\), le terme numéro zéro est \(x\), le terme pour \(i = 1\) est (oublions les signes pour l'instant) \(x^3/6\), et d'une manière générale le terme numéro \(i\) est \(x^{2i + 1}/(2i + 1)!\). On aura compris que le dernier terme de la formule, en remplaçant \(n\) par \(i\), donne la formule pour tous les \(i\). On aura également compris que le programme prend deux entrées \(x\) et \(n\), puisqu'il y a deux paramètres \(x\) et \(n\) dans la formule.
    Voyons les détails techniques : on passe du terme numéro \(i\) au suivant en multipliant par \(x^2\) et en divisant par \((2i + 2)(2i + 3)\) (on réfléchit un peu et on essaie sur des exemples pour trouver ça). Enfin pour cette histoire de signes, on utilise une variable sgn dont la valeur alternera entre \(1\) et \(-1\).

def Sin(x, n) :
    s = 0 ; sgn = 1 ; terme = x
    for i in range(0, n + 1) :
        s += sgn * terme
        terme *= x ** 2
        terme /= (2 * i + 2) * (2 * i + 3)
        sgn = -sgn
    return s

>>> Sin(1, 10)
0.8414709848078965
>>> Sin(0.5, 10)
0.479425538604203

?


5 - Boucles conditionnelles (« TANT QUE »)


Voici maintenant la deuxième sorte de boucles : celles pour lesquelles on ne connaît pas à l'avance le nombre de répétitions. On les arrête lorsqu'une certaine propriété n'est plus vraie.
    Commençons par un programme qui calcule la partie entière des racines carrées, c'est-à-dire \(\left\lfloor\sqrt{x}\right\rfloor\).

def Racine(x) :
    r = 0
    while (r + 1) ** 2 <= x :
        r += 1
    return r

Le programme précédent cherche le plus grand nombre \(r\) tel que \(r^2 \leq x\). Pour le trouver, on regarde le carré suivant (c'est-à-dire \((r + 1)^2\)) et tant qu'il ne dépasse pas \(x\), on remplace \(r\) par \(r + 1\).
    Variante de la même idée, peut-être plus intuitive pour certains : on compare \(r^2\) et \(x\), et tant que ça ne dépasse pas on remplace \(r\) par \(r + 1\). À la sortie de la boucle \(r\) est donc le plus petit nombre qui ne convient pas, et on retombe sur le plus grand qui convient « en reculant de un ».

def Racine(x) :
    r = 0
    while r ** 2 <= x :
        r += 1
    return r - 1

Une curiosité : on peut en fait se passer de calculer les carrés dans cet algorithme. On a vu plus haut qu'en additionnant les nombres impairs, on obtient, dans l'ordre, tous les carrés. Utilisons une variable m qui parcourt les nombres impairs (elle sera donc incrémentée de deux à chaque étape), et faisons la somme des valeurs de m dans une variable r_plus_un_au_carré qui comme son nom l'indique sera à chaque étape égale à \((r + 1)^2\). Voici ce qu'on obtient.

def Racine(x) :
    r = 0 ; r_plus_un_au_carré = 1 ; m = 3
    while r_plus_un_au_carré <= x :
        r += 1
        r_plus_un_au_carré += m
        m += 2
    return r

Et maintenant testons. Avec \(2\) on obtient \(1\), puisque \(\sqrt{2} \simeq 1,4\dots\). Les choses deviennent plus intéressantes avec \(2 \times 10^{16}\), dont la racine carrée est égale à \(10^8 \times \sqrt{2}\).

>>> Racine(2)
1
>>> Racine(2 * 10 ** 16)
141421356

En divisant par \(10^8\), c'est-à-dire en plaçant une virgule après le premier \(1\), on obtient donc la valeur approchée \(\sqrt{2} \simeq 1,\!414\,213\,56\) avec sept chiffres après la virgule, et nous avons utilisé un programme qui n'effectue que des additions. On verra bientôt des algorithmes beaucoup plus efficaces pour calculer autant de chiffres après la virgule qu'on le souhaite.

Essayons les logarithmes. Si \(x\) est un entier strictement positif, et si \(\mathrm{B}\) est un entier au moins égal à deux, il existe un unique exposant \(r\) tel que \[ \mathrm{B}^r \leq x < \mathrm{B}^{r + 1}. \] Ce nombre est la partie entière de \(\log_{\mathrm{B}}(x) = \ln(x)/\ln(\mathrm{B})\). Écrivons un programme qui le calcule. Ci-dessous la variable B_puissance_r_plus_un est à chaque étape égale à \(\mathrm{B}^{r + 1}\).

def Log(x, B) :
    r = 0 ; B_puissance_r_plus_un = B
    while B_puissance_r_plus_un < x :
        r *= B
        B_puissance_r_plus_un *= B
    return r

Testons : avec \(x = 3\) et \(\mathrm{B} = 10\) on trouve bien sûr zéro, mais avec \(x = 3^100000\) on obtient un résultat plus intéressant.

>>> Log(3, 10)
0
>>> Log(3 ** 1000000, 10)
477121

Les propriétés des logarithmes donnent \(\log_{10}(3^{1000000}) = 10^6 \times \log_{10}(3)\). En divisant le résultat ci-dessus par un million, c'est-à-dire en décalant la virgule de six rangs, on trouve la valeur approchée \(\log_{10}(3) \simeq 0,\!477\,121\). Là encore, on verra plus tard des méthodes beaucoup plus efficaces pour calculer les logarithmes.

?


6 - Compléments

a) Variables globales

Une variable définie en dehors de tout programme (c'est-à-dire sans indentation en début de ligne) est dite globale, et on peut s'en servir dans n'importe quel programme.

On peut bien sûr modifier, à l'intérieur d'un programme, une variable globale (sinon ce ne serait pas une variable mais une constante...). Pour ce faire il faut explicitement indiquer, à l'intérieur du programme concerné, qu'on va modifier une variable définie en dehors du programme. Ceci se fait avec le mot-clé global.
    Voyons un premier exemple, avec un programme qui compte le nombre de fois qu'il est utilisé (ici c'est le programme qui calcule la fonction \(x \mapsto x + 1\)).

NB_succ = 0
def succ(x) :
    global NB_succ
    NB_succ += 1
    return x + 1

Dans la console, ceci donne cela.

>>> NB_succ
0
>>> succ(1)
2
>>> succ(13)
14
>>> NB_succ
2

Autre exemple : écrivons un petit générateur de nombres aléatoires. On utilise une graine, comprise dans \(\left[0\,;\,1\right[\), qui à chaque étape subit la transformation \[ x \mapsto \frac{(10^8 \times x)^2\;\mathrm{mod}\; 10^{12}}{10^{12}}. \]
GRAINE = 0.12345678
def Aléa() :
    global GRAINE
    GRAINE *= 1e8
    GRAINE **= 2
    GRAINE %= 1e12
    GRAINE /= 1e12
    return GRAINE

>>> Aléa()
0.415765279684
>>> Aléa()
0.6076779071475
>>> Aléa()
0.724388351656
>>> Aléa()
0.384840148967
>>> Aléa()
0.019402569427
>>> Aléa()
0.7645970036955513

Ce n'est pas totalement satisfaisant : puisqu'on sait avec quelle valeur on a initialisé la graine, on peut théoriquement calculer à l'avance tous les nombres qui vont être produits. Or la moindre des choses avec un générateur aléatoire, c'est qu'il produise des résultats imprévisibles. On résout ce problème en initialisant la graine avec l'heure. Il faut un nombre entre zéro et un, prenons arbitrairement la valeur absolue du sinus du temps écoulé (au moment de l'initialisation), en secondes, depuis le 1er janvier 1970.

from time import time as Maintenant
from numpy import sin
def Initialiser() :
    global GRAINE
    GRAINE = abs(sin(Maintenant()))

>>> Initialiser()
>>> Aléa()
0.7683681471596563
>>> Aléa()
0.896095695632
>>> Aléa()
0.874957301979
>>> Aléa()
0.502802863709
>>> Aléa()
0.107197539712

?


b) Programmes imbriqués

?


c) Portée des variables

?