Maison des Arts et des Sciences Informatiques

Introduction à l'Algorithmique

 

  1. Langages de programmation et Algorithmes
  2. Recherche d'un élément dans un tableau trié
  3. Recherche dans un tableau non trié à l'aide d'une sentinelle
  4. Tirage aléatoire de NA nombres parmi NT nombres
  5. Les carrés magiques d'ordre impair
  6. Création de labyrinthes
  7. Le jeu de NIM

1. Langages de programmation et Algorithmes

Écrire un programme, c'est expliquer la suite d'actions à entreprendre pour obtenir un résultat. Différents langages de programmation existent. S'exprimer avec certains sera plus aisé pour résoudre un problème donné. Ce qui importe avant tout est de savoir expliquer ce qu'il y a à faire.

Écrire un programme, c'est décrire ce que le programme doit faire à l'aide d'un langage de programmation. Un bon programme :

  • accomplit la tâche prévue
  • peut être lu et compris
  • peut être modifié, si nécessaire, sans aucune difficulté
  • respecte les délais et le budget fixés

La technique de programmation est importante. Il faut maîtriser le vocabulaire et la grammaire: les structures de contrôle et l'art d'écrire des sous-programmes. Il faut définir et décrire les entrées et les sorties de chaque composante du programme (type, structure, etc), et aussi les variables temporaires utilisées. Dans le cas où des contraintes spéciales (temps de réponse, performance, volume de données important, etc) existent, une analyse plus élaborée est nécessaire pour décider la manière d'obtenir le résultat demandé.

Différentes techniques de programmation existent : méthode ascendante, méthode descendante, ordinogramme, etc. La méthode descendante (affinage graduel ou « diviser pour régner » ) décompose le problème en plusieurs grandes tâches elles mêmes divisées en tâches plus petites, lesquelles seront à leur tour décomposées en sous-tâches, etc.

Cependant avant d'écrire un programme, il faut réfléchir à la manière de résoudre le problème posé. Mille et une manière existent ! On appelle algorithme une méthode pour parvenir à un résultat ou un objectif donné en un temps fini.

Pour un problème donné, beaucoup d'algorithmes existent. On peut en inventer autant qu'on veut. Un algorithme est une manière particulière de résoudre un problème. Les algorithmes performants sont les plus séduisants. Cependant les algorithmes les plus simples sont souvent les plus beaux même s'ils ne sont pas les plus performants.

Pour un algorithme donné, de nombreuses structures de données peuvent être utilisées : les tableaux, les listes, les arbres, etc. Mais lorsque l'on réfléchit à l'algorithme à utiliser, on doit faire abstraction des structures de données.

Un problème bien posé est à moitié résolu. Rédiger l'idée de la résolution est déjà une manière de mettre ses idées en place. Et il faut rédiger de telle manière qu'une autre personne ignorante du problème sache à son tour comprendre le problème et comment elle peut le résoudre.

 

2. Recherche d'un élément dans un TABLEAU trié

La nécessité de trier des données résulte du besoin de les retrouver rapidement. Par exemple, pour chercher l'adresse et le numéro de téléphone d'une personne, on parcours un fichier jusqu'à trouver l'enregistrement qui la concerne.

Pour rechercher séquentiellement un élément dans un tableau, on passe en revue tous les éléments de ce tableau, un à un, jusqu'à trouver la position de l'élément recherché (appelée encore indice). Un recherche séquentielle est plus ou moins rapide selon que l'élément recherché est situé au début ou en fin du tableau. En moyenne, on passe en revue la moitié des éléments. Si N est le nombre d'élément du tableau, le nombre moyen de comparaisons sera N/2.

Lorsque le tableau est trié numériquement ou alphabétiquement, la méthode de recherche dichotomique permet de diviser le temps de recherche par 2 à chaque étape. L'algorithme est le suivant :

  1. Initialiser la section de recherche à l'ensemble du tableau
  2. Comparer le nom cherché au nom de l'élément situé au milieu de la section de recherche
    • Si le nom cherché est plus petit que le nom de l'élément situé au milieu, on recommence la recherche dans la première moitié
    • Si le nom cherché est plus grand que le nom de l'élément situé au milieu, la recherche se poursuit dans la seconde moitié.
    • Sinon on a trouvé l'élément recherché
  3. Recommencer au point (2) tant que l'élément cherché n'est pas trouvé et si la section de recherche est constituée d'au moins un élément.

Lorsqu'il y a par exemples 1024 éléments, on retrouve l'élément recherché après au plus 10 comparaisons (210 = 1024) alors qu'il en faut en moyenne 512 dans le cas d'une recherche séquentielle. Comme on le voit, l'algorithmique a une très grande importance dans la programmation.

 

3. Recherche dans un tableau non trié à l'aide d'une sentinelle

A paraître...

 

4. Tirage aléatoire de NA nombres parmi NT nombres

Soit le tableau TAB de NT éléments.

Chaque élément du tableau a pour valeur un des nombres sur lesquels le tirage a lieu.

L'ordre de rangement de ces NT nombres dans le tableau importe peu.

Le tirage aléatoire s'effectuera sur la position c'est à dire l'indice de rangement dans le tableau.

 

Prenons par exemple le tableau suivants à NT = 9 éléments :

11 33 22 55 44 66 88 99 77

Rappelons que pour un tableau de 9 éléments, les indices varient de 0 à 8.

 

Effectuons un tirage aléatoire d'un valeur KA comprise entre 0 et 8 (NT-1).

Soit par exemple, KA = 3 le résultat obtenu. Comme KA est l'indice, c'est en fait le nombre 55 qui a été tiré.

Rangeons ce nombre au début de tableau en le permutant avec l'élement d'indice 0 dont la valeur est 11.

On obtient :

55 * 33 22 11 44 66 88 99 77

Le début du tableau (1 élément) contient le premier nombre tiré, le reste du tableau contient les 8 nombres restants sur lesquels on continuera le tirage.

Le caractère * a été ici utilisé pour délimiter le début du tableau avec le reste du tableau.

 

Effectuons alors un tirage aléatoire d'un valeur KA comprise entre 1 et 8 (NT-1).

Soit par exemple, KA = 5 le résultat obtenu. Comme KA est l'indice, c'est en fait le nombre 66 qui a été tiré.

Rangeons ce nombre en 2e position du tableau en le permutant avec l'élément d'indice 1 dont la valeur est 33.

On obtient :

55 66 * 22 11 44 33 88 99 77

Le début du tableau (2 éléments) contient les 2 premiers nombres tirés, le reste du tableau contient les 7 nombres restants sur lesquels on continuera le tirage.

...

Pour effectuer NA tirages parmi NT (cela peut être 7, 8 et même 9 sur 9!), nous allons utiliser une boucle.

Les variables utilisées sont :

  • le tableau TAB[ NT ] est supposé déjà initialisé
  • la variable NT est le nombre de valeurs du tableau
  • la variable K est le nombre de valeurs du tableau déjà tirées
  • la variable NA est le nombre de tirage à effectuer
  • la variable KA est l'indice de la valeur de l'élément tiré
  • la variable TMP est une variable utilisée pour effectuer la permutaion des valeurs

Nous aurons la boucle suivante pour le tirage de NA nombres parmi NT :

Nous aurons la boucle suivante pour l'affichage de valeurs tirées :

Cette méthode s'inspire du tri par sélection directe utilisant un seul tableau dont les premiers éléments sont les éléments déjà triés (tous plus petits que les éléments restants).

Cette méthode est à comparer avec d'autres méthodes testant si l'élément tiré n'a pas été déjà tiré précédemment. Comme ces méthodes recommencent le tirage tant que l'on n'a pas obtenu un élément non déjà tiré, cela peut prendre un certain temps, voire un temps infini !

Par exemple si NA=999 et NT=1000, la probabilité de tirer du premier coup le 999e éléments parmi, en fait, les 2 éléments restants est de 2/1000.

Ce qui donne 998/1000 chances de refaire un tirage, et cela un certain nombre de fois...

A noter : Le tableau modifié résultant d'un tirage de NA nombres peut être utilisé tel quel pour un autre tirage de NA nombres parmi NT, l'ordre des valeurs n'ayant aucune importance.

Cliquez sur un élément en VERT, il sera permuté en début de tableau après les nombres déjà choisis qui en sont ROUGE.

Au départ, aucun élément n'est encore choisi : tous les éléments sont en VERT.

 

5. Les carrés magiques d'ordre impair

Rappelons qu'un carré magique d'ordre N est un tableau de N*N cases comportant dans chacune d'entre elles un nombre différent et tel que la somme des nombres de chaque ligne, de chaque colonne ou de chaque grande diagonale soit la même.

Si N est égal à 5, le carré comportera 25 cases. Prenons les nombres de 1 à 25 pour remplir le carré.

Une méthode simple pour obtenir un carré magique est d'essayer toutes les combinaisons possibles de mettre ces 25 nombres dans les 25 cases du carré et de vérifier si les sommes des lignes, des colonnes et des 2 grandes diagonales sont identiques. Malheureusement il y a environ

4 000 000 000 000 000 000 000 000 carrés à tester !

Même avec un ordinateur très puissant, on ne peut garantir de trouver la première solution en un temps fini.

On a démontré que la méthode suivante permettait quant à elle d'obtenir un carré magique quel que soit l'ordre à condition que celui-ci soit impair (nombre de cases impair). Les nombres de 1 à N2 doivent être déposés dans les cases du carré comme indiqué ci-dessous:

  1. Mettre le chiffre 1 au milieu de la dernière colonne
  2. Mettre le chiffre suivant dans la case en dessous à droite :
    • Si on est sur un bord du tableau, alors on juxtapose le même tableau à côté de telle manière qu'il y ait toujours une case située en dessous à droite
    • Si la case pour le chiffre suivant est déjà occupée, alors on choisit la case située à gauche
  3. On recommence au point 2 tant qu'il y a des cases libres.

 

                          

                          

                          

                          

                          

                          

                          

                          

                          

Cliquer sur une case vide de la grille pour trouver la suivante...

 

Les questions que l'on peut se poser sont : Y a-t-il toujours une case de libre à gauche quand la case située en dessous à droite est occupée ? L'algorithme marche-t-il quel que soit l'ordre impair du carré ? Compte tenu des symétries et des rotations possibles, obtient-on tous les carrés magiques possibles ? Cet algorithme permet-il d'obtenir des carrés magiques d'ordre pair ?

 

6. Création de labyrinthes

Citons deux méthodes pour la construction de labyrinthes :

  1. On part d'une situation avec des murs partout. Les murs sont supprimés et des galeries construites de telle manière qu'il y ait un chemin unique entre 2 cases quelconques du labyrinthe (pas de boucle). Au cours d'un parcours aléatoire du labyrinthe partiel, on abat des murs vers des cases non déjà visitées. Régulièrement afin d'éviter des errances dans le labyrinthe en cours de construction, on part de la première case non visitée. Celle-ci est forcément à côté d'une case déjà visitée. Le mur de séparation est abattu et un nouveau parcours aléatoire commence.
  2. On part d'un situation avec aucun mur à l'intérieur (seuls les murs externes existent). A partir des murs existants d'autres murs sont engendrés de telle manière qu'il existe toujours un chemin entre 2 cases quelconques du labyrinthe. La jonction de 2 pans de murs est interdite car elle sépare le labyrinthe en 2 régions distinctes.

 

Exercice 1: Appliquer un des deux algorithmes, au choix, pour construire un labyrinthe sur une feuille de papier (à l'aide d'un dé, d'un crayon et d'une gomme).

Exercice 2: Réfléchir comment représenter un labyrinthe à l'aide d'un tableau ou de plusieurs tableaux à deux dimensions. Il y a les murs et les cases à représenter.

 

7. Le jeu de Nim

Principe: Il y a 3 rangées de jetons. On prend à tour de rôle autant de jetons qu'on veut mais tous de la même rangée. Celui qui prend le dernier jeton est le vainqueur.

Stratégie gagnante: Si la situation avant de jouer n'est pas perdante, il n'y a une façon de la rendre perdante. Il suffit de prendre des jetons dans une rangée de telle manière que la position du jeu laissée soit perdante. Pour cela on étudie la parité de la décomposition en système binaire du nombre de jetons de chaque rangée. Exemple avec 3 piles de 2, 13 et 4 jetons:

  Nombre de jetons Colonnes des 8 Colonnes des 4 Colonnes des 2 Colonnes des 1
Pile 1 2 0 0 1 0
Pile 2 13 1 1 0 1
Pile 3 4 0 1 0 0
Parités   TRUE FALSE TRUE TRUE

Une position est perdante lorsque les parités sont toutes paires (FALSE).

Résolution possible :

  1. Essayer d'enlever 1 jeton, puis 2, puis 3, etc tour à tour dans chaque rangée afin de trouver une solution perdante à laisser à l'adversaire. Il y a au plus autant d'essais à faire que de jetons au total. (Cette démarche est facile pour une machine et moins pour une personne).

Autre démarche :

  1. Rechercher la première colonne impaire en commençant par celle des 8, puis des 4, puis des 2, puis des 1;
  2. Rechercher pour cette colonne la première pile avec un 1;
  3. À partir de cette colonne et jusqu'à la colonne des 1, ajouter ou retrancher des 1 de façon à rendre toutes les parités paires (FALSE).

Dans l'exemple : la première colonne est celle des 8 et la première pile avec un 1 est la pile 2. Le 1 de la colonne des 8 est enlevé (-8 jetons), un 1 est ajouté dans la colonne des 2 (+2 jetons) et le 1 de la colonne des 1 est enlevé (-1 jeton).

Au total on enlèvera 7 jetons (+8-2+1) de la pile 2 :

  Nombre de jetons Colonnes des 8 Colonnes des 4 Colonnes des 2 Colonnes des 1
Pile 1 2 0 0 1 0
Pile 2 13 - 7 = 6 0 1 1 0
Pile 3 4 0 1 0 0
Parités   FALSE FALSE FALSE FALSE

Une fois que le problème est dégrossi, il primordial de décomposer la suite d'actions à entreprendre.

Exemple pour le jeu de NIM :


Afficher la règle du jeu

REPETER

Tirage aléatoire des jetons

REPETER

Affichage des jetons
Prise en compte du coup de l'utilisateur

SI ( Fin de partie ) Alors

Félicitations

SINON

Affichage des jetons
Calcul du coup de l'ordinateur
Si NON( Fin de partie) Affichage des jetons

Fin SI

Fin REPETER si fin de partie

Fin REPETER si pas de partie suivante

Cette décomposition donne la forme du programme et fait apparaître les actions de bases (exemples: affichage des jetons, calcul du coup de l'ordinateur, test fin de partie, etc). Isoler ces actions en procédure ou fonction permet de gagner du temps à l'écriture et surtout à la mise au point. En effet chaque procédure sera testée sans attendre la fin complète du programme. Exemple de démarche:

  • Tirage aléatoire des jetons
  • Affichage des jetons
  • Afficher résultat du Test Fin de partie

De même que le programme s'appuie sur des actions fiables pré programmées et enregistrées sous formes de procédures ou fonctions dans une bibliothèque, le programme se constitue sa propre boite à outils.

Constituer sa propre bibliothèque de procédures et les collectionner pour les réutiliser sans avoir à les réinventer c'est programmer avec un langage encore plus évolué que le langage de départ.

Nommer ses procédures judicieusement permet d'être plus précis et plus efficace dans la décomposition du problème. Décrire le mode d'emploi de ses procédures est nécessaire et permet de s'assurer de la validité du choix des paramètres passés en arguments. En effet une procédure se doit avant tout d'être réutilisable, les arguments en entrée et en sortie doivent être décrits, ainsi les variables globales utilisées.

Une fois les actions de base définies, écrites, documentées et testées, il y a toujours 1 ou 2 procédures plus compliquées à écrire pour résoudre les sous problèmes particuliers du problème de départ. En général, il s'agit de passer en revue des données numérotées (tableaux) ou non (listes).

Exemple d'itération pour le jeu de NIM:

REPETER pour la rangée 1 à la rangée 3

REPETER pour 1 jeton au maximum de jetons

Retirer les jetons à la rangée
Si position perdante: enregistrer numéro de rangée et nombre de jetons
Remettre les jetons à la rangée

Fin REPETER jeton

Fin REPETER rangée

On remarque ici que toutes les combinaisons sont passées en revue et seule la dernière position perdante trouvée (supposée existante) est mémorisée. Suivant les langages utilisés, il est possible de sortir d'une boucle prématurément (break en langage C; exit en Turbo-pascal si la boucle a été mise dans une procédure).

L'itération se prête bien au passage en revue d'éléments rangés en tableaux. La répétition conditionnelle peut aussi être utilisée et peut permettre de prendre un compte un double test d'arrêt (position perdante trouvée ou fin de recherche).

Exemple de boucle conditionnelle pour le jeu de NIM:

Numéro de rangée = 1

Nombre de jetons = 0

REPETER

Si Nombre de jetons < Nombre Max Alors

Prendre un jeton de plus

Sinon

Passer à la rangée suivante
Mettre nombre de jeton à 1

Fin Si

Tester Numéro de rangée  et Tester si position perdante

Fin REPETER Si Numéro de rangée > Nombre de rangées ou Si Position perdante trouvée

 

ANNEXE: EXEMPLE DE DESCRIPTION DU PROGRAMME NIM

Description : Jeu de logique contre l'ordinateur. Il y a 3 rangées de jetons. On prend à tour de rôle autant de jetons qu'on veut mais tous de la même rangée. Celui qui prend le dernier jeton est le vainqueur.

Déroulement : Les 3 rangées de jetons sont affichées à l'écran. L'utilisateur commence le premier. Il indique le numéro de rangée puis le nombre de jetons à retirer. Les rangées sont ensuite de nouveau affichées avec les jetons restant. C'est au tour de l'ordinateur de jouer. Celui-ci annonce le numéro de rangée et le nombre de jetons qu'il supprime. Le joueur appuie sur la touche ENTREE pour signaler qu'il a lu le coup de l'ordinateur. Les rangées sont remises à jour. C'est ensuite au tour de l'utilisateur.

Algorithme : Comment doit jouer l'ordinateur pour gagner ? Le principe est simple à mettre en oeuvre. Si la situation avant de jouer n'est pas perdante, il n'y a qu'une façon de la rendre perdante. Il suffit de prendre des jetons dans une rangée de telle manière que la position du jeu laissée soit perdante. Pour cela on étudie la parité de la décomposition en système binaire du nombre de jetons de chaque rangée. Exemple avec 3 piles de 2, 13 et 4 jetons:

  Nombre de jetons Colonnes des 8 Colonnes des 4 Colonnes des 2 Colonnes des 1
Pile 1 2 0 0 1 0
Pile 2 13 1 1 0 1
Pile 3 4 0 1 0 0
Parités   TRUE FALSE TRUE TRUE

Si la parité est partout paire (FALSE), la situation est perdante et l'ordinateur joue au hasard. Sinon :

  • il recherche la 1ère colonne impaire en commençant par celle des 8, puis des 4, puis des 2, puis des 1.
  • puis il recherche pour celle-ci la première pile avec un 1.
  • à partir de cette colonne et jusqu'à la colonne des 1, il ajoute ou retranche des 1 de façon à rendre toutes les parités paires (FALSE).

Dans l'exemple : la première colonne impaire est celle des 8. La première pile avec un 1 est la 2. Le 1 de la colonne des 8 est enlevé, un 1 est ajouté dans la colonne des 2 et le 1 de la colonne des 1 est enlevé.

On enlèvera 7 jetons de la pile 2:

  Nombre de jetons Colonnes des 8 Colonnes des 4 Colonnes des 2 Colonnes des 1
Pile 1 2 0 0 1 0
Pile 2 13 - 7 = 6 0 1 1 0
Pile 3 4 0 1 0 0
Parités   FALSE FALSE FALSE FALSE

Décomposition du programme : Les variables principales sont les nombres de jetons par pile. Il n'y a pas de structure de données particulière. Le programme principal se décompose en plusieurs appels de procédures :

Répéter

GrOPEN : initialisation de l'affichage graphique

INITNIM: tirage aléatoire du nombre de jetons par pile entre 6 et 15 (nombre strictement inférieur à 16)

Répéter

DISPLAY : (ré-)affichage des rangées de jetons
USERMOVE : prise en compte du coup de l'utilisateur

Si partie finie (GAMEOVER) alors

félicitation!

Sinon :

DISPLAY : ré-affichage des jetons
ORDIMOVE : l'ordinateur joue, si partie
finie: il a gagné!

Fin_Test

Fin_Répéter: si partie finie

Fin_Répéter: si l'utilisateur ne veut plus jouer