Voici un petit exemple d’algorithmie appliqué a une situation ou l’on doit jouer avec les nombres. J’espère que cette présentation permettra à quelque-uns de mieux comprendre le fonctionnement des logiciels, voir même donner des envies à d’autres !

Définition du problème

Dans un jeux de société, nous avons 3 paquets de cartes (un bleu, un jaune et un rouge). Lorsque un joueurs tombe sur une certaine case du jeux (imaginez un monopoly) il doit recevoir une carte parmi les trois paquets. Cependant nous souhaitons qu’il pioche sa carte d’un des trois paquets selon des probabilités:

• 10% de chances de recevoir une carte venant du paquet bleu
• 25% de chances de recevoir une carte venant du paquet jaune
• 65% de chances de recevoir une carte venant du paquet rouge

Pour savoir dans quel paquet le joueur devra piocher, nous devons insérer une part de hasard: imaginons donc que nous avons un dès a 100 faces. Nous établissons a l’avance ces plages de nombres afin de savoir dans quel paquet piocher quand nous aurons lancé le dé:

• de 1 à 10: paquet bleu
• de 11 à 35: paquet jaune
• de 36 à 100: paquet rouge

Le défis va être d’écrire un algorithme capable de simuler ce jet de dés permettant le choix du paquet de carte.

Visualiser nos chiffres

Pour mieux visualiser ces plages de nombres, imaginez une règle de 100 graduations:

• Les 10 premières graduations, de 1 à 10, représentes les 10%.
• Les 25 prochaines graduations, de 11 à 35, représentes les 25%
• Les 65 prochaines graduations, de 36 à 100, représentes les 65%

En fonction du nombre donné par le dé a 100 faces et selon la graduation, nous savons quel paquet de carte choisir tout en restant fidèle aux probabilités de 10, 25 et 65%. Nous allons désormais représenter ces plages de nombres comme ceci:

10%   |   25%   |   65%

[1 → 10] [11 → 35] [36 → 100]

Le modèle logique

Nous allons maintenant essayer de trouver un modèle logique la dedans. Un modèle qui, quelque soit le nombre de paquets de cartes et quelque soit les probabilités que nous avons, puisse toujours s’appliquer. Dans un soucis de lecture nous allons appeler les 10% « A« , les 25% « B » et les 65% « C« . On constate en premier lieux ce modèle:

[1 → 10] [10+1 → 10+25] [10+25+1 → 10+25+65]

[1 → A] [A+1 → A+B] [A+B+1 → A+B+C]

Si nous rajoutions des paquets de cartes et modifions les probabilités, ce modèle fonctionnerais toujours. Vous pouvez essayez chez vous, succès garantis.

Le modèle logique: 2ème étape

Nous allons maintenant vouloir appliquer ce modèle à un algorithme informatique. Pour pouvoir le traiter de manière informatique il faut aller un peu plus loin: Nous devons trouver le modèle logique de chaque plage de nombre ([ ]) car notre algorithme devra répéter ce modèle pour chaque paquets de cartes (pourcentages). Car en effet un algorithme est une suite d’instructions qui ne dévira pas de ce pour quoi elle a été programmé. On doit donc trouver un modèle logique, c’est a dire comment trouver les nombres a l’intérieur d’une plage de nombres ([ ]), qui fonctionne a tout les coups.

Voici le modèle logique que nous cherchons:

[ Probabilités précédentes + 1 → Probabilités précédentes+Probabilité en cours ]

Pour mieux comprendre, rien de vaut une mise en pratique! Nous avons trois paquets de cartes: nous allons donc effectuer le « calcul » trois fois. La première fois pour la première plage de dates correspondant aux 10% ([1 → 10] [11 → 35] [36 → 100])

• Modèle: [ Prob. préc. + 1 → Prob. préc. + Prob. en cours ]
• Probabilités en cours: 10
• Probabilités précédentes: 0
• [0+1 → 0+10] [ ] [ ]
• soit [1 → 10] [ ] [ ]

La deuxième fois pour la deuxième plage de dates correspondant aux 25% ([1 → 10] [11 → 35] [36 → 100])

• Modèle: [ Prob. préc. + 1 → Prob. préc. + Prob. en cours ]
• Probabilités en cours: 25
• Probabilités précédentes: 10
• [ ] [10+1 → 10+25] [ ]
• soit [ ] [11 → 35] [ ]

La troisième fois pour la troisième plage de dates correspondant aux 65% ([1 → 10] [11 → 35] [36 → 100])

• Modèle: [ Prob. préc. + 1 → Prob. préc. + Prob. en cours ]
• Probabilités en cours: 65
• Probabilités précédentes: 10 + 25
• [ ] [ ] [10+25+1 → 10+25+65]
• soit [ ] [ ] [36 → 100]

Et voilà, nous constatons avec cette mise en pratique que le modèle logique fonctionne. Vous pouvez vérifier chez vous en ajoutant des paquets de cartes et probabilités si vous voulez.

L’algorithme de génération des plages de nombres

Tout ceci nous permet maintenant d’écrire notre premier algorithme ! Il s’agit ici de transformer le modèle logique vu précédemment en un algorithme « textuel », c’est à dire lisible par n’importe qui et respectant le modèle d’un programme informatique: Sa lecture se fait de gauche à droite et de haut en bas: comme pour la lecture !

"probabilités" contient 10%, 25% et 65%
"somme_probabilités_précédentes" vaut 0
"plages_de_nombres" est vide
pour chaque "probabilité_en_cours" dans les "probabilités":
  ajouter la plage ["somme_probabilités_précédentes"+1 → "somme_probabilités_précédentes"+"probabilité_en_cours"] aux "plages_de_nombres"
  "somme_probabilités_précédentes" vaut maintenant "somme_probabilités_précédentes" + "probabilité_en_cours"

Comprenez que pour les lignes avec un alinéa (dans le « pour ») il est effectué le processus autant de fois qu’il y a de probabilités (10%, 25%, 65%) de la même façon que nous l’avons mis en pratique dans la section « Le modèle logique: 2ème étape ». Voici la décomposition du code pour mieux comprendre ce qu’il se passe: Lors de la première passe:

pour chaque "probabilité_en_cours" dans les "probabilités":
  #note: Premier coup c'est la probabilité de 10%
  #note: et somme_probabilités_précédentes vaut 0
  ajouter la plage [0+1 → 0+10] aux "plages_de_nombres"
  "somme_probabilités_précédentes" vaut maintenant 0 + 10

Deuxième passe:

pour chaque "probabilité_en_cours" dans les "probabilités":
  #note: Deuxième coup c'est la probabilité de 25%
  #note: et somme_probabilités_précédentes vaut actuellement 10
  ajouter la plage [10+1 → 10+25] aux "plages_de_nombres"
  "somme_probabilités_précédentes" vaut maintenant 10 + 25

Troisième et dernière passe:

pour chaque "probabilité_en_cours" dans les "probabilités":
  #note: Troisième coup c'est la probabilité de 65%
  #note: et somme_probabilités_précédentes vaut actuellement 35
  ajouter la plage [35+1 → 35+65] aux "plages_de_nombres"
  "somme_probabilités_précédentes" vaut maintenant 35 + 65

Après avoir effectué les 3 passes nous avons bien nos plages de nombres:

[ 0 +1 → 0 + 10 ] [ 10 + 1 → 10 + 25 ] [ 35 + 1 → 35 + 65 ]

soit [1 → 10] [11 → 35] [36 → 100]

Code python

Nous pouvons maintenant rédiger notre premier script, c’est a dire notre premier « logiciel ». Nous allons rédiger ce code en python: C’est un langage de programmation propre et facilement lisible, donc bien adapté a ce petit cours. L’algorithme « textuel » vu précédemment devient:

probabilites = [10, 25, 65]
somme_probabilites_precedentes = 0
plages_de_nombres = []
for probabilite_en_cours in probabilites:
  plages_de_nombres.append([somme_probabilites_precedentes+1, somme_probabilites_precedentes+probabilite_en_cours]) 
  somme_probabilites_precedentes = somme_probabilites_precedentes + probabilite_en_cours

Et voilà! Ce code peut être compris par un ordinateur comprenant le langage python: pour une démonstration cliquez ici. Lorsque l’algorithme arrive a sa fin « plages_de_nombres » contient bien nos plages de nombres!

[ [1, 10], [11, 35], [36, 100] ]

Code python: simuler l’ensemble

Il nous faut maintenant ajouter du code pour simuler le jet du dés et le choix du paquet de carte dans lequel le joueur devra piocher. Cette ligne permet d’obtenir un nombre au hasard entre 1 et 100:

jet = random.randint(1, 100)

Pour savoir a quel paquet de carte correspond le jet de dés, nous allons, pour chaque plages de dates, voir si le nombre obtenu au dés s’y trouve. Si il s’y trouve, c’est le paquet de cartes, correspondant a cette plage de dates qui sera notre résultat. Commençons avec l’algorithme « textuel » (rappelons nous que « plages_de_nombres » contient « [[1,10] [11,35] [36,100]] »):

pour chaque plage_de_nombre dans les plages_de_nombres:
  Si le jet est supérieur ou égal au premier nombre de cette plage_de_nombres 
  ET si le jet est inférieur ou égal aux deuxième nombre de cette plage_de_nombres:
    c'est cette plage_de_nombre a laquelle correspond le jet

Illustrons cet algorithme « textuel » dans un cas pratique comme nous l’avons déjà fait la fois précédente. Imaginons que notre jet de dés à fait 49. Nous faisons trois fois ce qui est écrit dans le « pour » (puisque nous avons 3 « plages_de_nombres »):

pour chaque plage_de_nombre dans les plages_de_nombres:
  #note: Premier coup c'est la plage [1, 10]
  Si 49 est supérieur ou égal à 1 
  ET si 49 est inférieur ou égal à 10:
    c'est cette plage_de_nombre a laquelle correspond 49

Les conditions de la phrase « Si » ne sont pas remplis, on passe à la suivante:

pour chaque plage_de_nombre dans les plages_de_nombres:
  #note: Deuxième coup c'est la plage [11, 35]
  Si 49 est supérieur ou égal à 11 
  ET si 49 est inférieur ou égal à 35:
    c'est cette plage_de_nombre a laquelle correspond 49

Les conditions de la phrase « Si » ne sont toujours pas remplis, on passe à la suivante:

pour chaque plage_de_nombre dans les plages_de_nombres:
  #note: Troisème coup c'est la plage [36, 100]
  Si 49 est supérieur ou égal à 36 
  ET si 49 est inférieur ou égal à 100:
    c'est cette plage_de_nombre a laquelle correspond 49

A la troisième passe les conditions du « Si » sont remplis, c’est donc bien la plage de nombres du paquet de cartes rouges qui correspond à 49 ! Le code adapté au langage python est le suivant :

jet = random.randint(1, 100)
plage_de_nombre_correspondant = None
for plage_de_nombre in plages_de_nombres:
  if jet >= plage_de_nombre[0] and jet <= plage_de_nombre[1]:
    plage_de_nombre_correspondant = plage_de_nombre

Une fois les deux portions de code associés, cela nous donne:

import random

probabilites = [10, 25, 65]
somme_probabilites_precedentes = 0
plages_de_nombres = []
for probabilite_en_cours in probabilites:
  plages_de_nombres.append([somme_probabilites_precedentes+1, somme_probabilites_precedentes+probabilite_en_cours]) 
  somme_probabilites_precedentes = somme_probabilites_precedentes + probabilite_en_cours

jet = random.randint(1, 100)
plage_de_nombre_correspondant = None
for plage_de_nombre in plages_de_nombres:
  if jet >= plage_de_nombre[0] and jet <= plage_de_nombre[1]:
    plage_de_nombre_correspondant = plage_de_nombre

Ne prêtez pas attention la ligne « import random », elle est juste nécessaire pour pouvoir utiliser random.randint. A la fin de l’exécution de ces lignes « plage_de_nombre_correspondant » contiendra la page de nombre correspondant au jet du dé. Pour voir le code s’exécuter, cliquez ici.

Code python final

Pour que le logiciel est un intérêt supplémentaire, nous devrions l’améliorer de sorte à ce que nous puissions rapidement et facilement lancer la procédure à plusieurs reprises. Comme ceci ne concerne plus de l’initiation a l’algorithmie mais plutôt de la simple programmation logicielle je ne m’attarderais pas sur comment à été construit le code suivant. Cependant il intéressera les plus curieux

import random

def generer_les_plages_de_nombres(probabilites):
  somme_probabilites_precedentes = 0
  plages_de_nombres = []
  for probabilite_en_cours in probabilites:
    plages_de_nombres.append([somme_probabilites_precedentes+1, somme_probabilites_precedentes+probabilite_en_cours]) 
    somme_probabilites_precedentes = somme_probabilites_precedentes + probabilite_en_cours
  return plages_de_nombres

def trouver_plage_de_nombres_correspondantte_au_jet(jet, plages_de_nombres):
  plage_de_nombre_correspondant = None
  for plage_de_nombre in plages_de_nombres:
    if jet >= plage_de_nombre[0] and jet <= plage_de_nombre[1]:
      return plage_de_nombre

def trouver_cle(plage_de_nombres_trouve, plages_de_nombres):
  if plage_de_nombres_trouve in plages_de_nombres:
    return plages_de_nombres.index(plage_de_nombres_trouve)

def lancer_simulation(probabilites, paquets_de_cartes):
  jet = random.randint(1, 100)
  plages_de_nombres = generer_les_plages_de_nombres(probabilites)
  plage_de_nombre_correspondant_au_jet = trouver_plage_de_nombres_correspondantte_au_jet(jet, plages_de_nombres)
  cle = trouver_cle(plage_de_nombre_correspondant_au_jet, plages_de_nombres)
  print "pour le jet "+str(jet)+" c'est dans le paquet "+paquets_de_cartes[cle]+" que le joueur doit piocher"

paquets_de_cartes = ['Bleu', 'Jaune', 'Rouge']
probabilites = [10, 25, 65]
lancer_simulation(probabilites, paquets_de_cartes)

Pour une démonstration, cliquez ici.

Conclusion

La programmation logicielle consiste a cela: Répondre a un problème et synthétiser sa solution en adaptant de contextes réels des modèles logiques de manière a ce qu’ils soient compréhensible par une machine. Vos ordinateurs, les appareils électroniques et même des système uniquement mécaniques (voir par exemple le métier à tisser Jacquard) sont constitués de quelques ou de millions voir milliards de morceaux de logiques comme celui que nous venons de voir. Complexe, mais pas sorcier !