Algorithmique et python

Introduction, programmes et structures de base

Généralités sur les algorithmes

Algorithme

Un algorithme est une suite finie d'instructions permettant la résolution systématique d'un problème donné.

Un algorithme peut-être utilisé pour

décrire par une suite d'instructions ou de procédures la marche complète à suivre pour résoudre un problème;
automatiser une tâche complexe; on sait déjà dans ce cas résoudre le problème posé et on cherche à tirer parti de moyens informatiques pour effectuer automatiquement toutes les étapes et tous les calculs intermédiaires qui permettent d'aboutir au résultat;
chercher la solution d'un problème: on ne sait pas a priori résoudre le problème posé mais on peut tirer parti d'un système informatisé pour explorer l'ensemble des possibilités, et ainsi tenter de trouver la solution, ou du moins une bonne approximation de celle-ci.

Des exemples courants d'algorithmes sont donnés par les notices d'utilisation.
L'objectif dans ce cas est la description du problème à résoudre: le problème étant pour l'utilisateur d'utiliser correctement le produit concerné.
Si la notice est bien faite, c'est-à-dire, si l'algorithme donné est correcte, il ne doit y avoir aucune ambiguité lors de l'exécution des étapes successives, et, arrivé au bout de la notice, le produit visé doit être correctement utilisé.

Par exemple, voici la notice d'utilisation que l'on peut trouver au dos d'un bidon d'huile destinée à l'entretien de mobiliers en bois exotique (type teck):

Vérifier que la surface est bien du teck ou un bois exotique
Bien agiter avant emploi
Imprégner le bois généreusement
20 minutes après, essuyer l'excédent à l'aide d'un chiffon
Laisser sécher 6 heures
Recommencer à partir de l'étape 2
Laisser couler quelques gouttes d'eau sur la surface traitée

Si les gouttes perlent à la surface,

Alors le bois est correctement huilé et imperméabilisé

Sinon, recommencer à l'étape 2.

Cet algorithme est ici incorrect: à l'étape 6 on recommence à l'étape 2 systématiquement. En particulier, en suivant celui-ci scrupuleusement, on n'arrive jamais à l'étape 7, et donc on ne finit jamais cet algorithme.
La notice laisse ici apparemment le soin à l'utilisateur de juger par lui-même lorsqu'il a appliqué assez de produit.
Un algorithme correct doit éviter justement cela. Il ne doit pas laisser de place à l'interprétation du l'utilisateur, et doit être sans ambiguïté: l'utilisateur est un ordinateur qui n'interprète pas mais calcule.

L'algorithme précédent est écrit en français. Il aurait pu être écrit dans n'importe quelle langue vivante (on trouve d'ailleurs en général les notices écrites dans un certain nombre d'autres langues).
Si on veut faire exécuter un ensemble de tâches à un système automatisé (un ordinateur ou tout système electronique par exemple), une autre langue doit être utilisé. On parle alors de langage de programmation (d'une certaine façon la langue vivante comprise par le système automatisé), et de programme (la traduction de l'algorithme dans cette langue).

Langage de programmation & programme

Un langage de programmation est un ensemble d'instructions et de règles syntaxiques compréhensibles par un système automatisé (calculatrice, ordinateur, puce électronique,…).

Un programme est la traduction d'un algorithme dans un langage de programmation particulier.

Il existe de très nombreux langages de programmation tels que, parmi bien d'autres, Basic, Fortran, Python, C, C++, Matlab, assembleur, ceux implantés dans les calculatrices (alors dites "programmables"…), javascript, php, …
Des ressources sont aussi disponibles pour Matlab, Scilab et python.

Variables

Variable

On appelle variable tout emplacement de la mémoire dans lequel une information peut-être stockée.
Une variable est constituée de :

un nom qui permet à l'ordinateur de la localiser dans sa mémoire
une valeur: l'information qu'elle contient.

La valeur d'une variable peut évidemment changer (d'où son nom !) au cours de l'exécution de l'algorithme.

Dans un algorithme, on note souvent avec une flèche l'affectation d'une valeur à une variable: 3→x : on affecte (ou stocke) la valeur 3 dans la variable x.

En Python, le symbole mathématique égal "=" est utilisé: x=3 signifie qu'à partir de cette instruction la variable (nommée) x a pour valeur 3.

Les variables sont les éléments les plus essentiels et fondamentaux de tout algorithme / programme.
Pour pouvoir maintenant effectuer des opérations sur ces variables, et surtout des opérations automatisées, il faut se munir de quelques structures:

une structure conditionnelle, permettant d'indiquer que certains calculs ou certaines instructions ne sont à effectuer que sous certaines conditions
des boucles, permettant d'effectuer automatiquement un certain nombre de calculs.

Instruction conditionnelle: "if…"

Le traitement d'une condition peut se représenter par l'algorithme

En python, cette structure s'écrit:

if test:
    # instruction(s)
    # si le test est vrai

Un exemple d'instruction conditionnelle est le suivant, en français:

Demain, si il fait beau, alors je vais à la plage et je fais des maths.

Cette (simple) instruction conditionnelle est en fait ambigüe: imaginons que demain il pleuve, vais-je faire des maths ??
On peut en effet comprendre cette phrase de deux façons:

Demain, si il fait beau, alors (je vais à la plage et je fais des maths).
ou, en deux temps
(Demain, si il fait beau, alors je vais à la plage).
(Ensuite (qu'il fasse beau ou non), je fais des maths).

Ces deux algorithmes se représentent, comme précédemment:

et les programmes en pseudo-python correspondants:

if beau:
    plage
    maths

if beau:
    plage
maths

Plus généralement, on peut compléter la structure conditionnelle précédente en indiquant aussi quoi faire si la condition n'est pas vraie, sinon (else en anglais),

\[\psset{unit=.9cm,linewidth=1.5pt,arrowsize=8pt}
\begin{pspicture}(-.6,-5.1)(6.6,3)
\psline{->}(1,2.8)(1,2)
\pspolygon(0,1)(1,2)(2,1)(1,0)
\rput(1,1){Test ?}
\psline(2,1)(2.5,1)\psline{->}(3.4,1)(5,1)(5,-1.5)
\pspolygon(3.5,-1.5)(6.5,-1.5)(6.5,-2.5)(3.5,-2.5)
\rput(5,-2){\blue Instructions}
\psline{->}(5,-2.5)(5,-3.5)(1,-3.5)
\rput(2.9,1){\blue Vrai}
\pspolygon(-.5,-1.5)(2.5,-1.5)(2.5,-2.5)(-.5,-2.5)
\rput(1,-2){\red Instructions}
\rput(1,-.6){\red Faux}
\psline(1,0)(1,-.5)\psline{->}(1,-.8)(1,-1.5)\psline{->}(1,-2.5)(1,-5)
\end{pspicture}\]

voire même imbriquer plusieurs sinon. En python, on complète la structure précédente par un else (sinon):

if test:
    # instruction(s)
    # si le test est vrai
else: 
    # instruction(s)
    # si le test est faux

Boucle itérative conditionnelle: "while…"

Le traitement d'une boucle conditionnelle, c'est-à-dire d'une boucle qui s'effectue sous certaines conditions, peut se représenter par l'algorithme

\[\psset{unit=.9cm,linewidth=1.5pt,arrowsize=8pt}
\begin{pspicture}(-.2,-2.2)(5.6,5.6)
\psline{->}(1,5.5)(1,2)
\pspolygon(0,1)(1,2)(2,1)(1,0)
\rput(1,1){Test ?}
\psline(2,1)(2.5,1)\rput[l](2.6,1){\blue Vrai}\psline{->}(3.5,1)(4,1)(4,2.5)
\pspolygon(2.5,2.5)(5.5,2.5)(5.5,3.5)(2.5,3.5)
\psline{->}(4,3.5)(4,4.5)(1,4.5)
\rput(4,3){\blue Instructions}
\rput(1,-.6){\red Faux}
\psline(1,0)(1,-.4)\psline{->}(1,-.85)(1,-2)
\end{pspicture}\]

En python, cette structure s'écrit:

while test:
    # instruction(s)
    # si le test est vrai

Deux programmes complets et détaillés pour commencer

Par la suite, et avant de s'attaquer à plus d'éléments théoriques et généraux, deux programmes sont construits et détaillés pas à pas: Calcul d'aire et quadrature du cercle numérique et le jeu du nombre mystérieux. Le jeu du nombre mystérieux se joue à deux personnes de la manière suivante: un des deux joueurs choisit un nombre entier au hasard compris entre 1 et 100. Le but du deuxième joueur est de trouver ce nombre.
Pour cela il propose un nombre au premier joueur qui lui fournit une des trois réponses:

"Gagné", si le nombre proposé est le bon;
"Trop grand", si le nombre proposé est plus grand que le nombre mystérieux;
"Trop petit", si le nombre proposé est plus petit que le nombre mystérieux;

Si le nombre proposé n'est pas le bon, le deuxième joueur propose un autre nombre, et le jeu se poursuit jusqu'à ce qu'il trouve le nombre exact. Le but du jeu est de trouver le nombre mystérieux avec le moins de tentatives possible.
Essayer ! avant de le programmer !


Entrer un nombre:

Initiation / introduction à la programmation, en python: deux programmes construits et détaillés pas à pas: Jeu du nombre mystérieux