Algorithmique

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, …
Les deux derniers, javascript et php, sont dédiés spécifiquement à la programmation et la gestion de pages web. Dans la suite, les exemples de programmes sont ainsi naturellement donnés dans ces deux langages.
Des ressources sont aussi disponibles pour Matlab, Scilab et python.

Variables

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
6x5→cp : on affecte le résultat du calcul 6x5, soit 30, dans la variable cp
y+cp→z : on affecte le résultat du calcul de la somme des valeurs des variables y et cp dans la variable z

Très souvent, les langages de programmation utilisent le = pour désigner cette opération d'affection, par exemple y=t+2 : on affecte à la variable y;le résultat de la somme de la valeur de la variable t et 2.

Somme de termes

Code php:

<?php $compteur=$_POST['compteur'];
echo "Compteur=",$compteur;
$compteur=$compteur+1; ?>
<form method="POST" action="">
<button name="compteur" value="<?php echo $compteur;?>">+1 au compteur !</button>
</form>

Exécution/affichage:

Compteur=

Code javascript:

<script>
var i=0;
function plusun() {
  i=i+1;
  document.getElementById("Affich").innerHTML="Compteur="+i;
}
</script>
<div id="Affich"></div>
<button onclick="plusun()">+1 au compteur !</button>

Exécution/affichage:

Cet algorithme simple est par exemple utilisé sur toutes les pages où on rencontre un compteur du nombre de visiteurs.

Instruction conditionnelle: "if…"

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

\[\psset{unit=.9cm,linewidth=1.5pt,arrowsize=8pt}
\begin{pspicture}(-.2,-5.1)(5.7,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)(4,1)(4,-1)
\pspolygon(2.5,-1)(5.5,-1)(5.5,-2)(2.5,-2)
\rput(4,-1.5){\blue Instructions}
\psline{->}(4,-2)(4,-3)(1,-3)
\psline(1,0)(1,-1.3)\psline{->}(1,-1.75)(1,-5)
\rput(2.9,1){\blue Vrai}
\rput(1,-1.5){\red Faux}
\end{pspicture}\]

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.
Code php:

<?php $Valid=$_POST['Valid'];
$Nom=$_POST['Nom'];
if ($Valid==1) {
  if ($Nom=="") {echo "Vous devez entrer un nom...";}
  else {echo "Votre nom:",$Nom," est maintenant bien enregistré";}
  }
  else {echo "Entrez votre nom";}
  ?>
  <form method="POST" action="">
  <input type="text" name="Nom" value=""/>
  <button name="Valid" value="1">Valider</button>
  </form>

Exécution/affichage:

Entrez votre nom

Boucle itérative: "for…"

Code php

<?php if (isset($_POST['AfficheCarres'])) {
for ($i=0;$i<=6;$i++) {
 echo $i*$i," - ";
}
}?>
<form method="POST" action="#for">
<button name="AfficheCarres" value="1">Carrés ?</button>
</form>

Exécution/affichage:

Code Javascript:


<script>
function AfficheCarres() {
 for (var i=0;i<=6;i++) {
  s=document.getElementById("AffichageCarres").innerHTML;
  s=s+" "+i*i;
  document.getElementById("AffichageCarres").innerHTML=s
 }
}
</script>
<div id="AffichageCarres"></div>
<button onclick="AfficheCarres()">Carrés ?</button>

Exécution/affichage:

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}\]

Jeu du nombre mystérieux

Ce petit jeu 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. Code javascript:


<input type="text" id="prop" value=""/>

<button onclick="Testnb()">Valider</button>

<div id="Reponse"></div>

<script>

nbSecret=Math.floor(Math.random() * 100)

nbCoups=0;

function Testnb() {

 nbCoups+=1

 p=document.getElementById("prop").value

 if (p<nbSecret) {

  document.getElementById("Reponse").innerHTML="Trop petit"

 }

 else if (p>nbSecret) {

  document.getElementById("Reponse").innerHTML="Trop grand"

 }

 else {

  document.getElementById("Reponse").innerHTML="Gagné !!! en "+nbCoups+" coups"

 }

}

</script>

Exécution/affichage: