# Algorithme --- ## Définitions --- ### Larousse Ensemble de règles opératoires dont l'application permet de résoudre un problème énoncé au moyen d'un **nombre fini d'opérations**. Un algorithme peut être **traduit**, grâce à un langage de programmation, en un **programme exécutable** par un ordinateur. --- ### Wikipedia Un algorithme est une **suite finie et non ambiguë d’opérations** ou d'instructions permettant de résoudre une **classe de problèmes**. --- ### Académie Méthode de calcul qui indique la démarche à suivre pour résoudre une **série de problèmes équivalents** en appliquant dans un ordre précis une suite finie de règles.

Rachid Guerraoui

“ Certains individus sont plus capables que d'autres de faire les calculs, ce sont des mathématiciens. Certains d'eux sont altruistes parce qu'ils donnent aux autres des méthodes pour résoudre des problèmes. L'utilisateur n'a pas besoin de comprendre la méthode, il l'utilise c'est tout. C'est un algorithme.”

 ## Al Kwarizmi Le mot **algorithme**, comme le mot **algèbre**, vient du nom d'un mathématicien perse du IXe siècle, Al Kwarizmi. ---  L'une de ses œuvres principales est **Abrégé du calcul par la restauration et la comparaison** publié entre 813 et 833. Ce livre est le point de départ de l'algèbre, Al Kwarizmi y raisonne sur des équations en donnant des méthodes de résolution, c'est à dire des algorithmes.

### Exemple d'algorithme “ Les **carrés** plus les **racines** égaux à un **nombre**, c'est par exemple lorsque tu dis : un carré plus dix racines sont égaux à trente-neuf dirhams, c'est-à-dire que si on ajoute à un carré quelconque une quantité égale à dix racines, le tout sera trente-neuf. ” “carré” $=x^2$ ; “racine” $=x$ **exemple :** $x^2 + 10x = 39$. --- $x^2 + 10x = 39$ n'est qu'un exemple. Al-Kwarizmi propose de résoudre une **classe de problèmes**. Sa méthode permet de résoudre toute équation de forme $$x^2 + a\cdot x = b$$ --- ### la méthode $$x^2 + 10x = 39$$ “Partage en deux moitiés le nombre des racines ; il vient, dans ce problème, cinq, que tu multiplies par lui-même ; on a vingt-cinq ; tu l'ajoutes à trente-neuf, on aura soixante-quatre ; tu prends la racine qui est huit, de laquelle tu soustrais la moitié du nombre des racines, qui est cinq. Il reste trois, qui est la racine du carré que tu veux, et le carré est neuf.”

En langage moderne

ENTRÉES : a, b
SORTIE : solution de x^2 + a * x = b
DÉBUT
    diviser a par 2
    mettre au carré
    ajouter b
    prendre la racine carrée
    soustraire a/2
    RENVOYER résultat
FIN

À faire : exécutez l'algorithme pour

$$x^2 + 10x = 39 \quad ; \quad x^2 + 12x = 133$$

### Très important La méthode est énoncée en toute généralité. On peut énoncer la méthode sans connaître les valeurs de $a$ et $b$. Au moment d'**exécuter** l'algorithme, on connaîtra les valeurs de $a$ et $b$. --- ### Remarques * Al Kwarizmi n'avait pas d'ordinateur ! On peut raisonner sur un algorithme sans pour autant l'exécuter sur une machine. * L'algorithme proposé n'est pas encore un programme. Il faudra le traduire par exemple en **Python**. --- ### Préconditions et postconditions * Vérifiez que $-13$ est également solution de $$x^2 + 10x = 39$$ * Essayez d'appliquer la méthode pour $$x^2 + 10x = -26$$ Quel est le problème ? --- Du temps d'Al Kwarizmi, on n'utilisait pas de nombres négatifs. La solution et les nombres $a$ et $b$ sont supposés positifs. Il faut éviter ces implicites en explicitant ces règles supplémentaires : * **précondition :** a et b sont positifs * **postcondition :** l'algorithle renvoie la solution positive de $x^2+a\cdot x = b$

Solution plus générale

ENTRÉES : a et b, réels
SORTIE : solutions réelles de x^2 + a * x = b, si elles existent
DÉBUT
    calculer delta = a^2 + 4*b
    SI delta > 0 ALORS
        x1 = (-a - racine(delta)) / 2
        x2 = (-a + racine(delta)) / 2
        RENVOYER x1 et x2
    SINON, SI delta = 0 ALORS
        x1 = -a/2
        RENVOYER x1
    SINON
        RENVOYER rien
FIN

Compléter la fiche avec les exemples proposés

* L'algo contient des instructions simples (des calculs). On suppose que tous ces calculs sont faisables par l'exécuteurs (notamment la racine) * L'algo utilise des structures de contrôles (SI, SINON...)