L'algorithmique existe dans les programmes de mathématiques depuis très peu d'année. Il joue un rôle de plus en plus important dans notre société, ce qui explique son apparition dans les programmes.
En effet, nous utilisons de plus en plus de site Internet, d'applications sur les smartphone ou sur les tablettes et nos matériels multimédia et même culinaires deviennent de plus en plus connectés. Derrière ces appareils, se cachent des programmes sophistiqués conçus par des ingénieurs de haut niveau.
Il devient ainsi important à l'école de s'initier à concevoir et comprendre la structure de ces langages. Cette compréhension joue un double rôle : celui de connaître la qualité et les limites de l'outil informatique, et d'autre part de développer son esprit logique.
Pour introduire cette séquence, nous allons commencer par faire le point sur ce qui a été apperçu au collège par l'activité suivante : activité n°2.
Cet algorithme, écrit en français n'est compréhensible que par français ou plutôt un être humain capable de traduire le français. Ce qui n'est pas le cas d'un ordinateur ou d'une machine qui n'est supposé que de comprendre un unique langage universel : le langage binaire composé de deux caractères le 0 et le 1.
Il a fallut alors inventer un langage universel permetant de passer du langage courant au langage binaire. Ce sont les langages de programmation. Il en existe différents, selon les applications et les domaines d'utilisation. Pour cette simple page Internet que vous lisez, je n'utilise que quatre langages différents : le langage H.T.M.L., le langage C.S.S., le langage S.Q.L. et le langage P.H.P. Pour l'écriture informatique, j'ajoute le langage Tex (se prononce tek).
En classe de seconde, nous allons nous initier à un langage de programmation très répendu : le langage Python.
Un début des années 1970, un groupe d'humoristes anglais animait une émission à la télévision sur la chaine B.B.C.. Cette émission s'appelle Monthy Python's flying Circus.
En 1986, le mathématicien hollandais Guido Van Rossum était passionné d'informatique et était fan incontestable de l'humour dégagé par la troupe des Monthy Python. Il concevait des programmes informatiques et, par humour, un an plus tard, il en nomma un , appelé Python, juste par humour et hommage à la troupe.
Depuis, le nom est reste et la première version publique de Python débuta en 1991.
Comment pourrait-on définir un algorithme ?
On définit un algorithme de la façon suivante :
Définition : Un algorithme est une suite finie d'instructions élémentaires dont l'objectif est de résoudre en temps fini et de manière automatique un problème donné ou d'effectuer un calcul.
Tout algorithme doit être traduit dans un langage de programmation avant d'être exécuté. Il existe deux modes de rédaction d'un algorithme :
- Sous forme d'un organigrame (méthode graphique)
- Sous forme textuelle (pseudo code). C'est la méthode qui sera étudiée ici dans cette séquence.
Un algorithme est toujours structuré via la définition suivante :
Définition : Un algorithme, destiné à être implémenté sur ordinateur via un langage de programmation, est constitué de trois parties :
- Les déclarations des variables
- Le corps de l'algorithme
- La restitution des résultats
Les déclarations des variables consiste à faire la liste des variables informatiques et d'en informer l'ordinateur. La variable informatique est un emplacement mémoire qui peut contenir différents types de données : un nombre réel, une chaîne de caractère, etc. Cette déclaration est située en début d'algorithme et le simple fait de réaliser cette déclaration permet à l'ordinateur de réserver de la mémoire pour le contenu de la variable et de réserver son emplacement.
- Le corps de l'algorithme est en réalité le coeur de l'algorithme. Il contient toutes les instructions pour la résolution automatique du problème posé et effectuer les calculs attendus, les demandes de données par l'utilisateur et toutes les séquences arithmétiques pour le traitement de ces données.
- La restitution des résultats consiste finalement à retourner dans un format adéquat les résultats ou les solutions du problèmes. Le format peut être sous forme de texte, de graphique, d'image ou de tableau. Les résultats pourront simplement être affichés sur un écran, ou imprimés ou enregistrés dans un fichier.
Remarque : Suivant le langage utilisé, la première partie (déclaration des variables) est déjà introduite dans la plateforme d'execution du programme. C'est le cas du langage Python où il ne sera donc pas nécéssaire de faire cette déclaration de variables. Cette absence est due à l'évolution importante des technologies des nouveaux appareils qui disposent de capacité de mémoire très importante. Il n'est ainsi plus nécessaire de déclarer systématiquement les variables.
On rappelle que les variables sont nommés par des lettres ou des mots. Souvent, la lettre utilisée ou le mot choisi pour nommer la variable est en rapport avec la nature de la variable. Par exemple, s'il s'agit de calculer une hauteur, la variable pourra s'écrire hauteur ou encore h.
Lorsqu'on souhaite enregistrer la valeur «Bonjour !» à l'emplacement désigné par une variable que nous pourrions appeler chaine, on dit qu'on affecte la valeur «Bonjour !» à la variable chaine.
On note cette opération :
\(\displaystyle chaine\longleftarrow \text{ "Bonjour!" } \)
On peut aussi comparer deux variables pour effectuer des tests notamment. Si \(\displaystyle a\) et \(\displaystyle b\) sont deux variables, l'instructions \(\displaystyle a=b\) prendra la valeur VRAI si les contenus des variables coincident et FAUX sinon.
De la mêmem façon qu'une recette de cuisine, un programme est structuré.
Proposition : Tout algorithme peut être écrit en utilisant uniquement les trois structures suivantes :
- La structure séquentielle : elle traduit simplement une suite d'instruction élémentaires.
- La structure alternative : elle est de la forme « SI condition ALORS traitement »
- La structure itérative : elle est de la forme « REPETER instructions TANT QUE condition »
Cette structure consiste à écrire les instructions à la suite, l'une après l'autre. L'exécution de l'algorithme se fera alors dans l'ordre d'apparition des instructions.
Il est possible d'enchainer des séquences de plusieurs instructions. Cet enchainement s'appelle un bloc d'instructions.
La structure alternative, appelée aussi structure conditionnelle, permet d'effectuer une ou plusieurs instructions différentes, suivant que le résultat d'un test (ou condition) est positif ou négatif.
La structure est la suivante :
\(\displaystyle \begin{align*} \text{ SI } & condition(s) & \text{ ALORS } & \text{ bloc1 d'instructions} \\ & & \text{ SINON } & \text{ bloc2 d'instructions} \\ \text{ FINSI} &\\ \end{align*} \)
Cette structure consiste à répéter en boucle un nombre fini de fois un bloc d'instructions avec une information supplémentaire qui permettra d'arreter la boucle.
Il existe pour cela deux types de boucles itératives suivant que le nombre d'itérations est connu à l'avance ou pas :
- Les boucles inconditionnelles seront utilisées lorsque le nombre d'itération est connu.
- Les boucles conditionnelles seront utilisées lorsqu'une condition de sortie de boucle est connue.
Définition : La boucle inconditionnelle est une instruction permettant la répétition d'une tâche quelconque, un nombre de fois déterminé à l'avance.
La syntaxe d'une boucle inconditionnelle en pseudo-code est :
\(\displaystyle \begin{align*} &\text{ POUR } i \text{ variant de } debut \text{ à } fin \text{ FAIRE } \text{ bloc d'instructions} \\ &\text{ FINPOUR } \\ \end{align*} \)
Remarque : La variable \(\displaystyle i\) qui prend des valeurs entières partant de la valeur initiale \(\displaystyle debut\) et qui augmente régulièrement pour aboutir à une valeur finale \(\displaystyle fin\), est appelé un compteur. Par défaut, le compteur \(\displaystyle i\) augmente d'une unité, mais il est possible de choisir une valeur différente, appelée le pas de la boucle.
Définition : La boucle conditionnelle est une instruction permettant la répétition sous condition, d'un bloc d'instruction.
La syntaxe d'une boucle conditionnelle en pseudo-code est :
\(\displaystyle \begin{align*} &\text{ TANT QUE } condition(s) \text{ FAIRE } \text{ bloc d'instructions} \\ &\text{ FINTANTQUE } \\ \end{align*} \)
Comme évoqué dans le paragraphe I, le langage Python est un langage qui permet de traduire l'algorithme en instructions compréhensibles par la machine (ordinateur, smartphone, etc).
Pour cela, il faut que l'appareil dispose d'une application ou d'un logiciel qui permettent de traiter ce langage. On appelle cela une distribution.
Il devient donc nécessaire d'installer une distribution Python sur la machine :
- EduPython pour les PC
- Idle sur Mac
- Pydroid 3 sur tablette
Quelque soit la distribution, le principe est le même : on dispose d'une console Python, une fenêtre dans laquelle on peut effectuer des calculs, appliquer des fonctions et observer les résultats de sortie des programmes, ainsi que d'un éditeur de programmes, une fenêtre où l'on saisit les programmes.
En langage Python, un identificateur est un mot dont les seuls caractères sont les lettres minuscules de \(\displaystyle a\) à \(\displaystyle z\). Quelques caractères sont autorisés comme _ ainsi que les chiffres. Bien que les caractères soient possibles, il n'est pas conseillé de les utiliser.
Une variable est un identificateur faisant référence à un emplacement dans la mémoire de l'ordinateur contenant un objet. On dit que cet objet est la valeur de la variable, ou encore que la variable est liée à cet objet.
Pour affecter une valeur à une variable, en langage Python, on utilise le signe =. Ainsi, si on considère la variable \(\displaystyle longueur\), pour y affecter la valeur 5, l'instruction est :
\(\displaystyle \begin{align*} longueur&=5\\ \end{align*} \)
Les valeurs 2 et -5 sont des nombres entiers. On dit que ces valeurs sont typées. De la même façon, la valeur -3,546 est décimale. C'est aussi une valeur typée, mais de type différent que le 2 et le -5/
Les valeurs entières sont de type INT.
Les valeurs décimales ou autres valeurs approchées sont des nombres appelés flottant. Le type est donc FLOAT.
Nous venons de voir des exemples de variables à valeur numérique. Une variable peut aussi contenir une chaine de caractère comme par exemple :
\(\displaystyle \begin{align*} texte&=\text{ "Bonjour !"}\\ \end{align*} \)
Dans les exercices, nous seront confrontés à voir d'autres types de variables que l'on rencontre inconsciemment dans la vie courante mais surtout dans la programmation informatique : le type de variable qui ne donne que deux résultats : VRAI ou FAUX. C'est le type booléen qui vient du mathématicien et philosophe Georges BOOLE pendant le 19ème siècle. En Python, le type est écrit BOOLEAN.
Pour terminer avec la première liste de type de variables, on peut transformer une variable en une fonction. C'est ce que nous verrons dans le paragraphe suivant. Le type est FUNCTION.
Une variable est un identificateur faisant référence à un emplacement dans la mémoire de l'ordinateur contenant un objet. On dit que cet objet est la valeur de la variable, ou encore que la variable est liée à cet objet.
Pour terminer, l'instruction qui permet de déterminer le type d'une variable est :
\(\displaystyle \begin{align*} & longueur=-5\\ & type(longueur)\\ & \text{ INT}\\ \end{align*} \)
Notez qu'en langage Python, on ne parle pas de type mais plutôt de classe.
Pour écrire une fonction, par exemple la fonction \(\displaystyle f\left(x\right)=2x+1\), on utilise au départ les lambda-expressions de la façon suivante :
\(\displaystyle \begin{align*} fonction &= \text{lambda x : 2*x+1}\\ \end{align*} \)
Si par la suite, nous souhaitons calculer \(\displaystyle f\left(5\right)\), il suffira d'écrire :
\(\displaystyle \begin{align*} & fonction = \text{ lambda x : 2*x+1 }\\ & calcul(5)\\ 11 \end{align*} \)
Le soucis avec cette syntaxe est que si nous avons des fonctions plus soffistiquées comme \(\displaystyle g\left(x\right)=x^2+\left(x^2+1\right)^3\), la fonction fonction va calculer une première fois \(\displaystyle x^2\) puis va reprendre le nouveau résultat pour \(\displaystyle x^2\), ce qui implique que nous aurons deux résultats différents pour \(\displaystyle x^2\), ce qui apportera un résultat erroné à la fin pour la fonction. Il devient donc nécessaire de procéder différemment :
\(\displaystyle \begin{align*} & \text{ def } &g(x)\\ & &a=x*x \\ & &\text{ return a+(a+1)**3}\\ 11 \end{align*} \)
L'écriture de la puissance par le double * sera vu au prochain parragraphe.
Les opérations de base sont inclues dans la console Python :
- Pour l'addition : +
- Pour la soustraction : -
- Pour la multiplication : *
- Pour la division approchée : /
- Pour la division entière : //
La fonction valeur absolue est inclue dans la console Python alors que d'autres fonctions ne le sont pas comme par exemple le cosinus ou la racine carrée. Il faut alors importer un module avant de faire appel à de telles fonctions. Cet appel s'exécute par l'instruction :
\(\displaystyle \begin{align*} & \text{ from math import }\\ \end{align*} \)
En classe de seconde nous aurons besoins alors des fonctions suivantes :
| Fonction | Syntaxe en Python | Fonction | Syntaxe en Python |
| racine carré | math.sqrt() | cosinus | math.cos() |
| sinus | math.sin() | tangente | math.tan() |
| arccosinus | math.acos() | arcsinus | math.asin() |
| arctangente | math.atan() | partie entière | math.floor() |
| exposant n | **n | reste d'une division | \% |
Pour n'avoir recourt qu'à une seule fonction dans un petit programme, il est utile d'avoir recourt à la syntaxe suivante en prenant par exemple la racine carré :
\(\displaystyle \begin{align*} & \text{ from math import sqrt}\\ & sqrt(2) \\ &1,4142135623730951 \end{align*} \)
Le mot clé important pour vérifier un test selon une condition est le mot IF. Dans sa forme la plus simple, c'est IF ... ELSE ...
Partons de l'exemple où nous souhaitons calculer la racine carrée d'un nombre. Le problème ici réside dans le fait que le nombre choisi doit être positif. Sinon, l'ordinateur ne sera pas capable, tout comme vous, de calculer la racine carrée d'un nombre strictement négatif. Il devient alors nécessaire de procéder auparavant à un test sur le nombre que vous allez choisir :
\(\displaystyle \begin{align*} & \text{ from math import sqrt } &\\ &x=-5 & \\ & if & x>=-5 \\ & & r=math.sqrt{-5} \\ & & print(r) \\ & \text{ else} & \text{print('x est négatif')} \\ \end{align*} \)
En exécutant ce programme, il affichera « x est négatif »
Pour procéder au test de la condition, on utilise certains symboles :
| Fonction | Syntaxe en Python | Fonction | Syntaxe en Python |
| = | == | \(\displaystyle \leqslant\) | <= |
| \(\displaystyle \geqslant\) | >= | \(\displaystyle \neq \) | != |
Nous avons vu dans le paragraphe 1 qu'il existe deux types de fonctions, selon si nous connaissons ou pas la valeur de condition de l'arrêt de la boucle.
Pour la syntaxe de boucle inconditionnelle, il faut utiliser la boucle FOR.
Pour la syntaxe de boucle conditionnelle, il faut utiliser la boucle WHILE.
Exemple d'utilisation de la boucle FOR en voulant calculer la somme des carrés des 100 premiers nombres :
\(\displaystyle \begin{align*} & n=100 &\\ & s=0 &\\ & \text{for i } & \text{ in range(1,n):} \\ & & s=s+i**2 \\ & \text{ print(s)} & \\ \end{align*} \)
Exemple d'utilisation de la boucle WHILE en voulant calculer la somme des carrés des 100 premiers nombres :
\(\displaystyle \begin{align*} & n=1 &\\ & s=0 &\\ & \text{ while n<=100:} \\ & & s=s+n**2 \\ & & n=n+1 \\ & \text{ print(s)} & \\ \end{align*} \)