Rappels du collège
Notion de variable
Quand une calculatrice ou un ordinateur exécutent un programme, ils doivent stocker des informations en mémoire et éventuellement les récupérer pour faire des tests et des opérations. La machine a donc besoin de variables.
Variable
En algorithmique, une variable est un espace mémoire où la machine (calculatrice ou ordinateur) peut stocker ou récupérer une valeur (nombre, texte, résultat vrai ou faux d'un test).
Pour différencier les différentes variables, on leur donne un nom.
Affecter une valeur à une variable
Affecter une valeur à une variable signifie qu'on stocke cette valeur dans la variable.
Pour ce faire, on utilise la syntaxe suivante :
- en langage naturel : nom_de_la_variable <- valeur
\text{nom_de_la_variable} \xleftarrow{\text{}} \text{valeur}
- en Python : nom_de_la_variable=valeur
\text{nom_de_la_variable}= \text{valeur}
On souhaite stocker une chaîne de caractères "Vous avez réussi !", le nombre 15,2 ; et stocker le résultat du carré de 15,2 dans une troisième variable.
Les trois lignes suivantes permettent de créer (si elles ne l'étaient pas déjà) et de nommer trois variables et d'y affecter une valeur :
On crée, on nomme les variables et on y affecte des valeurs dans la même instruction.
Quand on affecte une valeur dans une variable, on écrase (efface) automatiquement la valeur qui y était précédemment.
En Python, une variable peut être de différents types :
- du type int quand elle contient un entier relatif ;
- du type float quand elle contient un nombre décimal ;
- du type str quand elle contient un texte, autrement appelé une chaîne de caractères ;
- du type bool quand elle contient les valeurs booléennes vrai ou faux.
Du type de variable, dépend la taille de l'espace mémoire utilisé par la variable et l'utilisation que la machine peut en faire.
- L'instruction \text{a}=15.2 donne à la variable a le type float.
- L'instruction \text{message}=\text{"Vous avez réussi !" } donne à la variable message le type str.
- Dans le programme suivant, la machine teste si la variable \text{b} est positive et affecte la valeur true dans la variable \textcolor{Purple}{\text{test}} si c'est le cas :
La variable \text{b} est de type int ; et la variable test est de type bool.
Instructions conditionnelles
En algorithmique, on a souvent besoin d'exécuter des instructions en fonction de la réalisation ou non d'une condition. On utilise alors des instructions conditionnelles.
Opérateurs de comparaison
Pour comparer deux variables de type int ou float, on utilise des opérateurs de comparaison.
La syntaxe est différente du langage naturel ou des symboles utilisés en mathématiques.
La structure d'une instruction conditionnelle est la suivante :
On peut également avoir besoin de rajouter une instruction au cas où la condition est fausse.
Dans ce cas, le code est le suivant :
Soit n un entier naturel.
On veut afficher la partie entière de \dfrac{n}{2}.
On sait que :
Si n est pair alors sa partie entière est \dfrac{n}{2} ; si n est impair, sa partie entière est \dfrac{n-1}{2}.
Pour automatiser ce calcul, on peut écrire l'algorithme suivant en Python :
Dans l'instruction conditionnelle, la machine teste si le reste de la division euclidienne de la valeur dans n par 2 (codé n%2) est égale à 0 - autrement dit, elle teste la parité de n.
En fonction du résultat, elle affecte à la variable m le bon calcul pour trouver la partie entière de n.
En Python :
- Les lignes de code où sont écrites les instructions à réaliser doivent être précédées d'un espace : on parle d'indentation.
Cette indentation permet à l'ordinateur de distinguer toutes les lignes qui sont à exécuter au sein d'un bloc if ou d'un bloc else.
Généralement, la machine met automatiquement cette indentation mais il est préférable de le vérifier.
- On ne doit pas oublier les deux points après le if ou le else.
Dans le code ci-dessous, l'instruction print(m) est exécutée uniquement si la condition m<10 est vraie.
La console n'affichera rien puisque la série d'instructions après le if n'est pas réalisée.
Dans le code suivant, au contraire, l'instruction print(m) est exécutée quelle que soit la valeur dans la variable m.
La série d'instructions après le if n'est pas réalisée donc la console affichera la valeur de la variable m qui est 60.
Boucles
Dans bon nombre de programmes, la machine doit répéter plusieurs fois un même groupe d'instructions. On écrit alors ce groupe d'instructions en les plaçant dans une boucle qu'on fait répéter.
Boucle bornée
Une boucle bornée est une boucle qui indique qu'on répète un groupe d'instructions un nombre fini de fois.
Pour cela, on utilise une variable interne à la boucle qui sert de compteur.
Quand le nombre de répétitions à faire est atteint, la machine sort de la boucle et exécute le reste de l'algorithme.
La structure d'une boucle bornée est la suivante :
En Python :
On utilise une boucle for pour écrire une boucle bornée.
Le terme range (zone ou fourchette en anglais) indique le nombre de répétitions de la boucle.
Le compteur est une variable. On peut la nommer k, i, j... Cette variable n'existe que pour la boucle donc il est inutile de la définir avant la boucle.
On veut calculer la somme des 5 premiers termes de la suite (u_{n}) définie pour tout entier naturel par u_{n}=e^{-n}.
Le programme à écrire consiste en répéter 5 fois :
- calculer le terme suivant de la suite ;
- l'ajouter à la somme des précédents.
On utilise une boucle for pour ne pas répéter le code 5 fois.
Ce que fait la machine :
- elle affecte 0 à la variable s ;
- elle rentre dans la boucle qui est une répétition du groupe d'instructions "u= exp(-k)" et "s=s+u".
Ainsi, elle calcule :
Pour k=0 : u=exp(-0) et elle l'ajoute à s.
Pour k=1 : u=exp(-1) et elle l'ajoute à s.
Pour k=2 : u=exp(-2) et elle l'ajoute à s.
Pour k=3 : u=exp(-3) et elle l'ajoute à s.
Pour k=4 : u=exp(-4) et elle l'ajoute à s.
À la fin de la boucle, la variable s contient bien la somme des 5 premiers termes de la suite.
- La machine sort de la boucle et exécute la fin du programme : afficher la valeur contenue dans la variable s.
Attention à la syntaxe dans la boucle for :
- ne pas oublier les deux points à la fin de la ligne de code commençant par for ;
- les instructions à réaliser dans la boucle sont précédées d'une indentation.
On remplace le programme précédent par celui-ci :
L'instruction "print(s)" est dans la boucle donc le programme va afficher les valeurs successives de s.
Boucle non bornée
Une boucle non bornée est une suite d'instructions qui se répète tant qu'une condition initiale est vraie.
La structure d'une boucle non bornée est la suivante :
En arrivant dans la boucle, la machine teste la condition initiale.
Si la condition est vraie, la machine exécute le bloc d'instructions et revient tester la condition initiale.
Si la condition est fausse, la machine quitte la boucle et exécute la suite du programme.
On considère le programme suivant :
Ce que fait la machine qui exécute ce programme :
a/ Elle affecte 11 à la variable p.
b/ Elle rencontre la boucle while :
- Elle teste la condition p2<130.
- 11^2=121 donc la condition est vraie. La machine exécute donc l'instruction qui suit : elle affecte à p la valeur 11+0{,}1=11{,}1.
c/ Elle répète les opérations précédentes :
- Elle teste la condition p2<130.
- 11{,}1^2=123{,}21 donc la condition est vraie. La machine exécute donc l'instruction qui suit : elle affecte à p la valeur 11{,}1+0{,}1=11{,}2.
d/ Elle répète cette boucle tant que p2<130.
e/ Lorsque à la fin d'une boucle p2 devient supérieur ou égal à 130, la machine quitte la boucle et envoie sur la console la dernière valeur dans p.
En conclusion, ce programme permet de trouver une valeur approchée au dixième d'un nombre réel p tel que p2=130.
La console renvoie 11.499999999999998.
Ainsi, une valeur approchée au dixième de \sqrt{130} est 10,5.
Comme dans la boucle non bornée for, attention à la syntaxe dans la boucle while :
- ne pas oublier les deux points à la fin de la ligne de code ;
- les instructions à réaliser dans la boucle sont précédées d'une indentation.
De plus, la boucle while ne s'arrête que lorsque la condition de la boucle est fausse : il faut donc faire attention à ce que cela arrive !
Dans le cas contraire, la boucle va tourner indéfiniment, nécessiter beaucoup de ressources et éventuellement provoquer des bugs.
Les fonctions en algorithmique
Les fonctions sont très utiles en programmation. Elles fonctionnent comme des sous-programmes qu'on peut appeler dans le programme principal pour exécuter un bloc d'instructions souvent utilisé.
Fonction sans paramètre
Dans un algorithme, on appelle fonction sans paramètre un bloc d'instructions auquel on donne un nom et qui ne nécessite pas l'entrée d'une valeur pour fonctionner.
Lorsqu'on appelle la fonction par son nom, elle renvoie un résultat (message ou valeur numérique) en sortie.
En Python, la structure d'une fonction sans paramètre est la suivante :
Il y a une indentation devant le bloc d'instructions à réaliser à l'appel de la fonction.
Il ne faut pas oublier les deux points après la ligne de code def nom_de_la_fontion() :
On définit une fonction Hello qui "salue" l'utilisateur du programme et lui dit "Vous avez choisi".
La fonction hello() est définie dans le bloc def hello():
Elle a pour sorties les variables message1 et message2, suivie d'une chaîne de caractères donnant l'entier choisi.
Cette fonction est appelée dans la suite du programme par la commande hello(), la commande print servant à afficher le résultat.
Fonction avec paramètre
Dans un algorithme, on appelle fonction avec paramètre un bloc d'instructions avec une valeur transmise en entrée.
Dans le bloc d'instructions, ce paramètre est traité comme une variable qui n'existe que dans le bloc.
Lorsqu'on appelle la fonction par son nom, elle renvoie un résultat (message ou valeur numérique) en sortie.
Des fonctions sont déjà programmées dans l'environnement Python utilisé en mathématiques :
- la fonction print(n) a pour argument n.
C'est un sous-programme qui permet à la machine d'aller chercher la valeur dans la variable n et de l'afficher sur la console.
- la fonction exp(x) a pour argument la variable x.
C'est un sous-programme qui permet de calculer une valeur approchée de l'exponentielle d'une valeur stockée dans la variable x.
La valeur d'entrée est de type float.
La valeur de sortie donnée par la fonction est de type float.
En Python, la structure d'une fonction avec paramètre est la suivante :
Il y a une indentation devant le bloc d'instructions à réaliser à l'appel de la fonction.
Il ne faut pas oublier les deux points après la ligne de code def nom_de_la_fontion(nom_paramètre) :
On considère le programme suivant :
Dans cet algorithme, la fonction u est définie par la ligne def u(n):
Elle a pour entrée la variable n ; elle a pour sortie la valeur obtenue par le calcul n^{2}+n-1.
Dans la suite du programme, on a une boucle for.
La fonction u(n) est appelée 20 fois dans cette boucle pour calculer les u(k) pour k allant de 0 à 19.
On calcule donc les 20 premiers termes de la suite u_{n}=n^{2}+n-1.
Les listes
Dans un algorithme, on peut avoir besoin de stocker plusieurs valeurs, par exemple les résultats de la répétition d'une expérience aléatoire ou les données d'une étude statistique. On utilise alors des listes.
Définition
Liste en algorithmique
Une liste sert à stocker plusieurs valeurs dans un programme.
Les valeurs peuvent être de différents types dans une même liste.
Génération d'une liste par extension
Générer une liste par extension c'est donner tous les éléments de cette liste.
Pour générer une liste par extension, on utilise la syntaxe suivante :
Les éléments de la liste sont placés entre crochets [ ] et séparés par des virgules.
On peut également définir une liste vide que l'on utilisera et remplira dans la suite du programme.
Dans ce cas on écrit l'instruction nom_liste=[ ].
Rang d'un élément dans une liste
Dans une liste, un élément est repéré par sa position en partant du premier élément, ce qu'on appelle son rang.
En Python, le premier élément d'une liste est de rang 0.
On définit une liste nommée L par extension avec la ligne de code :
L=[3,5,8,13,21]
L'élément de rang 0 de la liste L est 3.
L'élément de rang 4 de la liste L est 21.
Utilisation des listes
On peut accéder à un élément d'une liste, le supprimer, en ajouter de nouveaux.
On peut également connaître la longueur d'une liste.
Les syntaxes en Python pour ces actions sont données dans le tableau ci-dessous.
On définit une liste nommée L par extension avec la ligne de code :
L=[3,5,8,13,21]
- On veut accéder à l'élément de rang 1.
On code L[1]
- On veut supprimer l'élément de rang 3.
On code del(L[3])
- On veut ajouter le texte "fin" à la fin de la liste.
On code L.append('fin')
- On veut accéder à la longueur de la liste.
On code len(L)
- On veut accéder à la liste complète.
On code L
À la fin de ces actions, la liste L est :
[3,5,8,21, 'fin']
Génération d'une liste par ajouts successifs
Générer une liste par ajouts successifs, c'est ajouter ses éléments au fur et à mesure.
On tire un dé à 6 faces équilibré une dizaine de fois.
On veut générer la liste des nombres obtenus par ajouts successifs.
On nomme cette liste tirages.
On utilise la fonction randint(n,m) de paramètres les entiers n et m. Cette fonction donne un nombre entier aléatoire entre n et m.
Ce que fait la machine :
- Elle crée une liste vide nommée tirages.
- Elle répète 10 fois la séquence d'instructions suivantes :
a/ Elle affecte à n un nombre aléatoire entre 1 et 6.
b/ Elle ajoute cet élément à la liste tirages.
Si on passe la commande tirages dans la console, on peut obtenir :
Génération d'une liste en compréhension
Générer une liste en compréhension, c'est coder la liste en indiquant comment sont générés les éléments de cette liste.
On tire un dé à 6 faces équilibré une dizaine de fois.
On veut générer la liste des nombres obtenus en compréhension.
On nomme cette liste tirages.
On utilise la fonction randint(n,m) de paramètres les entiers n et m. Cette fonction donne un nombre entier aléatoire entre n et m.
Les exemples du programme
Calcul des termes d'une suite récurrente
À l'aide d'un programme en Python comprenant une boucle, on peut obtenir très rapidement les premiers termes d'une suite définie par son premier terme et la relation de récurrence u_{n+1}=f(u_{n}). Cet outil permet donc de faire des hypothèses probables sur le comportement (croissance, limites, etc.) de ces suites.
Soit la suite réelle (u_{n}) définie par son premier terme u_{0}=3 et, pour tout entier naturel n par la relation de récurrence : u_{n+1}=0{,}5u_{n}+1.
Afin de conjecturer l'existence et la valeur de sa limite, on veut écrire un programme qui permet de calculer et d'afficher les 20 termes suivants de cette suite.
Si on crée 20 variables pour chacun de ces termes, le programme va être lourd et ne sera pas optimisé.
- On note u la variable qui contient la valeur d'un terme de la suite.
Initialement la variable u contient la valeur 3 car u_{0}=3.
- La suite est définie de proche en proche : la formule u_{n+1}=0{,}5u_{n}+1 va être répétée 20 fois.
On utilise donc une boucle bornée for.
Les instructions de la boucle seront de :
- calculer le terme suivant et l'affecter à u ;
- afficher ce terme à chaque itération.
La console affiche les 20 termes suivant u_{0} :
On peut conjecturer que la suite est décroissante et converge vers 2.
Recherche de seuils
En mathématiques, on est souvent amené à chercher à partir de quelle valeur de la variable une fonction ou une suite remplit telle condition. Les algorithmes permettent de trouver une valeur approchée de ce seuil avec une boucle while.
Soit f la fonction définie sur [3 ; +\infty[ par f(x)=\dfrac{\ln\left(x\right)}{x}.
On admet que \lim\limits_{x \to +\infty} f(x)=0 et que la fonction est décroissante sur [3 ; +\infty[.
On cherche, avec une précision au centième, à partir de quelle valeur de x, on a f(x)\leqslant0{,}2.
On écrit un algorithme de seuil.
Remarque : en Python pour calculer \ln\left(x\right) on écrit log(x,e).
Ce que fait la machine :
- Elle affecte la valeur 3 dans la variable x.
- Elle teste la condition log(x,e)/x>0.2.
Ici \dfrac{\ln\left(3\right)}{3}\approx0{,}4 qui est strictement supérieur à 0,2.
La condition est vraie donc la machine rentre dans la boucle : elle affecte à x la valeur 3+0{,}01=3{,}01.
- La machine teste ensuite la condition pour x=3,01.
\dfrac{\ln\left(3{,}01\right)}{3{,}01}\approx0{,}4 qui est strictement supérieur à 0,2 donc elle affecte à x la valeur 3{,}01+0{,}01=3{,}02.
- La machine reste dans la boucle tant que la condition est vraie. Elle en sort lorsqu'on a \dfrac{\ln\left(x\right)}{x}\leqslant 0{,}2.
- Sur la console s'affiche 12.719999999999793.
En conclusion, f(x)\leqslant0{,}2 à partir de x\approx12{,}72.
On peut également définir une fonction seuil qui permet à l'utilisateur du programme de choisir la précision voulue ou la valeur du seuil.
On considère la suite définie par son premier terme u_{0}=3 et pour tout entier naturel n par u_{n+1}=0{,}5u_{n}+1.
On admet qu'on a démontré que \lim\limits_{n \to +\infty} u_{n}=2.
On cherche le premier rang n à partir duquel la différence u_{n}-2 est en valeur absolue strictement inférieure à 10^{-p}.
- L'entier naturel p peut être changé et choisi sans réécrire l'algorithme si on définit une fonction algorithmique de paramètre p.
- Comme on cherche le rang du terme de la suite tel que \left| u_{n}-2 \right|\lt 10^{-p}, la sortie de la fonction est le rang n.
Sur la console, on appelle seuil(2).
Ce que fait alors la machine :
- Elle affecte 3 à la variable u et 0 à la variable n.
Cela correspond à définir le premier terme de la suite u_{0}=3.
- Elle teste la condition abs(u-2)>=10**(-2).
Ici, 3-2=1 est strictement supérieur à 10^{-2} donc la machine rentre dans la boucle et exécute les instructions :
a) Elle calcule le terme suivant de la suite.
b) Elle augmente l'indice n de 1.
- La machine reste dans la boucle tant que la condition est vraie. Elle en sort lorsqu'elle trouve un terme u_{n} tel que \left| u_{n}-2 \right|\lt 10^{-2}
- La console affiche la valeur de n : 7.
En conclusion, \left| u_{n}-2 \right|\lt 10^{-2} pour la première fois pour n=7.
Valeur approchée d'une solution d'équation du type f(x)=k
Le théorème des valeurs intermédiaires et son corollaire permettent de démontrer l'existence d'une solution d'équation du type f(x)=k sous certaines hypothèses. Les algorithmes sont des outils efficaces pour trouver les valeurs approchées de ces solutions.
Soit f la fonction définie sur \mathbb{R} par f(x)=e^{x}-x^{2}-5.
On admet avoir démontré que la fonction est strictement croissante sur l'intervalle [0;3] et que l'équation f(x)=0 admet une solution unique sur cet intervalle.
En particulier, on sait que f(0) \lt 0 et f(3) \gt 0.
On veut écrire un programme permettant de trouver une valeur approchée de cette solution avec une précision à 10^{-p}.
L'idée est de tester les valeurs de f(x) par balayage à partir de 0.
Sur la console Python, on passe la commande balayage(2).
Ce que fait la machine :
- Elle affecte 0 à la variable a. C'est la borne inférieure de l'intervalle [0;3].
- Elle rencontre while : elle teste la condition f(a)<0.
Dans notre cas, on a f(0) \lt 0 donc la condition est vraie : la machine entre dans la boucle.
Elle affecte à la valeur 0+ 10^{-2} puis elle teste de nouveau la condition, jusqu'à ce qu'elle rencontre un réel a de [0;3] tel que f(\text{a})\geqslant 0.
- La machine renvoie alors ce nombre.
Méthode des rectangles
Dans certains cas, on ne peut pas calculer la valeur exacte d'une intégrale donc on utilise la méthode des rectangles pour en trouver une valeur approchée. Un algorithme permet de trouver un encadrement de la valeur exacte.
Soit f la fonction définie sur [0;2] par f(x)=x^2+1.
Cette fonction est continue et positive sur l'intervalle.
On cherche une valeur approchée de \int_{0}^{2} x^2+1\ \mathrm dx par la méthode des rectangles.
La fonction precision(a) renvoie un encadrement de la valeur approchée de l'intégrale avec une précision de 10^{-a} .
Simulation d'un lancer de dé
Parmi les expériences aléatoires fréquemment utilisées en probabilités, on peut simuler un lancer de dé avec un algorithme.
Le code suivant en Python permet de procéder à un tirage aléatoire d'un entier entre 1 et 6 inclus.
On peut procéder à plusieurs tirages successifs et stocker les résultats obtenus dans une liste appelée tirage.
Simulation d'une variable aléatoire suivant une loi binomiale
Avec un algorithme, on peut également simuler les valeurs prises par une variable aléatoire suivant une loi binomiale.
Une urne contient 2 boules vertes et 3 boules rouges indiscernables au toucher.
1. On tire une boule de l'urne et on s'intéresse à sa couleur.
Il n'y a que deux issues possibles à cette expérience aléatoire. C'est un schéma de Bernoulli.
On cherche à modéliser cette expérience avec un algorithme :
- On associe aux boules des nombres entiers.
Pour cela, on peut placer les 5 boules comme éléments d'une liste. Une boule sera alors représentée par son rang dans la liste.
- On assimile le tirage de la boule à un tirage aléatoire sur le rang de la liste.
Quand on exécute ce programme, la console retourne "vert" ou "rouge" suivant le résultat de son tirage aléatoire.
2. On répète maintenant 10 fois cette expérience aléatoire et on note X la variable aléatoire qui donne le nombre de boules vertes obtenues.
X suit la loi binomiale de paramètres 10 et \dfrac{2}{5}.
On cherche à simuler cette variable aléatoire.
- Pour simuler X , on doit répéter dix fois le schéma de Bernoulli précédent : on utilise une boucle for.
- À chaque tirage, l'algorithme doit compter 1 si on obtient une boule verte et 0 sinon : on doit utiliser également une instruction conditionnelle.
On modélise la situation en faisant un tirage aléatoire sur {0;1;2;3;4} : les entiers 0 et 1 représentent les boules vertes et les entiers 2, 3 et 4 les boules rouges.
