1- Origine du mot

Le mot « algorithme » vient de la déformation du surnom du mathématicien persan Al-Khuwarizmi (né vers 780 - mort vers 850)

2- Une définition

Un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini d’étapes, à un certain résultat, et cela, indépendamment des données.

algorithme schema
On parle aussi de langage naturel pour qualifier un algorithme.
 

Il est important de comprendre qu'un algorithme doit se terminer puisqu'il doit y avoir un nombre fini d'étapes !

En effet, si l'algorithme est mal conçu, il peut partir dans une boucle infinie.

 

Exemple

Imaginons un algorithme qui compare 2 variables a et b afin de réaliser une soustraction de telle sorte qu'il faut retirer au plus grand nombre la valeur du plus petit.

Cela donne en langage naturel et l'équivalent en Python :

 

Algorithme Python
Si a>b alors
     d  ← a - b
Sinon
     d ← b - a
Fin Si		 if a>b :
     d = a - b
else
     d = b - a
 
Noter bien que :

- cette structure est de type Si ... Alors ... Sinon .... Fin si

- l'affectation d'une variable n'utilise pas le signe égal, mais une flèche indiquant que le résultat doit être rangé dans une variable,

- le fin d'un test doit être signalé par Fin Si. 

Vous allez vite vous rendre compte que le langage python est très proche dans la syntaxe hors mis la langue !

3- Notion de complexité

Suivant l'enchaînement des règles, le nombre d'étapes de l'algorithme peut être plus ou moins important, et sera fonction directement du nombre d'opérations élémentaires à réaliser pour obtenir le résultat.

La complexité permet donc de savoir si un algorithme est efficace ou pas.

Par exemple,
Une boucle dans laquelle il faut répéter 5 fois 2 opérations élémentaires aura comme complexité un nombre entier, ici 10.
Mais pour déterminer la complexité d'un algorithme, on va pousser le traitement vers de grandes valeurs : on tend vers l'infini le traitement.
Donc au lieu de retenir une boucle qui se répète 5 fois, on dit qu'elle se répète n fois : On parlera de complexité d'ordre n.
 

Une approche mathématique simplifiée peut aussi être faite

Par exemple, on analyse un algorithme qui doit faire 6n2+3n+10 opérations élémentaires.

On dira que l'algorithme est de complexité n2 :

Pour déterminer la complexité, on prend des valeurs de n tendant vers l'infini, dans ce cas, 3n+10 devient négligeable devant n2. 

On a éliminé les constantes, on conserve la puissance la plus élevée et on supprime le coefficient devant la puissance la plus grande.

L'objectif de déterminer la complexité est d'arriver à concevoir des algorithmes efficaces : résoudre un problème le plus rapidement possible.

4- Quelques règles d'écritures

Afin de pouvoir travailler pour la suite, vous allez trouver la correspondance entre l'écriture en langage naturel et en python en complétant le tableau ci-dessous :

 
  Algorithme Python
Demander une saisie de l'utilisateur Lire a

Afficher une variable ou valeur Ecrire d
  
Conditions : ET - OU - NON Si a=b OU a>b alors  
Test Si Temp =< 5 Alors
     Ecrire "Il fait froid"
SinonSi Temp < 30 Alors
     Ecrire "Température normal"
Sinon
     Ecrire "Il fait trop chaud"
Finsi		  
Boucle 1 Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
      Lire Rep
FinTantQue		  
 Boucle 2 Truc ← 0
TantQue Truc < 15
     Truc ← Truc + 1
     Ecrire "Passage numéro : ", Truc
FinTantQue		  
Boucle 3 Pour Truc ← 1 à 15
  Ecrire "Passage numéro : ", Truc
  Truc Suivant
FinPour
  

Créer, utiliser des tableaux

A noter que l'indice commence à 0

 tab( ) ou tab[ ]
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Faire les exercices : 6.5 - 6.9 - 6.13

Pour chacun d'eux, vous le taperez dans le code python et le testerez.

Source des exemples : https://pise.info/algo/codage.htm