Chapitre XII - Algorithmique

Définition

Un algorithme est une suite finie et ordonnée d’opérations ou d'instructions permettant de résoudre un problème ou d'obtenir un résultat. Ainsi, faire une recette de cuisine ou encore effectuer une division euclidienne à la main sont des exemples d'algorithmes.

Nous ne travaillerons dans ce cours qu'avec des algorithmes type BAC.

Instructions

Création de variables

Créer une variable permet de réserver un espace pour y stocker des données quelconques.
On donne un nom à chaque espace pour le repérer : ce sont les noms de variables. On leur donne également un type (entier, réel, ...) pour travailler avec.

Exemple (tiré du sujet de Pondichéry 2017) :

Exemple d'algorithme

Ici nous avons quatre variables : $R$ et $S$ qui sont des réels et $n$ et $k$ qui sont des entiers.

Affections de valeurs

Comme dit précédemment, les variables sont des espaces dans lequel il est possible de stocker des informations.
Cependant, après avoir créé cet espace, celui-ci est encore vide. C'est pourquoi on doit le remplir : c'est l'affectation d'une valeur à une variable.

Il existe plusieurs manières d'affecter une valeur à une variable : soit on lui donne directement sa valeur dans l'algorithme, soit on demande à l'utilisateur d'entrer une valeur (il faut garder à l'esprit que les algorithmes sont faits pour être utilisés par des utilisateurs).

Exemple (tiré du sujet de Pondichéry 2017) :

Exemple d'algorithme

Ici on donne à $S$ la valeur $0$, mais on demande à l'utilisateur d'entrer la valeur de la variable $n$ (l'utilisateur entrera un entier, car la variable $n$ ne peut contenir que des entiers).

Une fois que l'on a affecté une valeur à une variable, il est encore possible de la changer !

Affichage de variables

Les algorithmes étant faits pour être utilisés, il faut donc retourner un résultat sinon ceux-ci seraient inutiles.
C'est pourquoi, on peut afficher les valeurs des variables (les montrer à l'utilisateur).

Exemple (tiré du sujet de Métropole 2017) :

Exemple d'algorithme

Une fois l'algorithme terminé, on affiche la valeur de la variable $N$ (on remarque que $N$ a pris plusieurs valeurs différentes au cours de l'algorithme mais qu'on affiche uniquement la valeur finale de la variable).

Blocs d'instructions

Définition

Les blocs d'instructions sont des parties de l'algorithme (ce sont des algorithmes dans l'algorithme) qui s'exécutent suivant certaines conditions propres aux différents blocs d'instructions.

Les blocs SI et SINON

Les blocs SI et SINON sont des blocs d'instructions très utilisés qui permettent de tester une condition : si elle est réalisée, on va exécuter les instructions se situant sous le bloc SI et sinon, on va exécuter celles se situant sous le bloc SINON.

Exemple (test de parité) :

Exemple d'algorithme

Si la partie entière de $\frac{N}{2}$ est égale à $\frac{N}{2}$ (ce n'est vrai que pour les entiers pairs), alors on donne à $R$ la valeur 0. Sinon on lui donne la valeur 1.
En fin d'algorithme, on affiche la valeur de $R$ : soit 0 si $N$ est pair, soit 1 si $N$ est impair.

La boucle POUR

La boucle POUR est un bloc d'instruction qui s'exécute et qui va prendre à une variable toutes les valeurs comprises dans un ensemble d'entiers.

Exemple (calcul des termes d'une suite) :

Exemple d'algorithme

Cet algorithme permet de calculer les termes d'une suite définie par récurrence $u_n$ : $\begin{cases} u_0 = 1\\ u_{n+1} = u_n + \frac{1}{n}\end{cases}$ pour $n$ entier.
On demande à l'utilisateur d'entrer une variable $N$, et pour $n$ variant de 1 jusqu'à $N$ ($n$ prendra tour à tour les valeurs 1, 2, 3, ..., $N-1$, $N$), on va calculer les termes de la suite.

La boucle TANT QUE

Cette boucle, différente de la boucle POUR permet d'exécuter son bloc d'instructions tant qu'une certaine condition est valable.

Exemple (tiré du sujet de Métropole 2017) :

Exemple d'algorithme

Ici, tant que $N - ln(N^2 + 1)$ est inférieure à $A$, on affecte une nouvelle valeur à la variable $N$.

Algorithmes sur l'ordinateur

Il est possible de tester et de vous entraîner aux algorithmes sur votre ordinateur, voire directement sur votre smartphone !
Divers logiciels à télécharger, dont certains ne nécessitant pas d'installation sont disponibles :

Annales en rapport avec le sujet

Sujets et corrigés fournis par Math France.