الجزء الاول cours d'algorithme pour TSDI

Présentation
Présentation informelle
Considérons les étapes qui interviennent dans la résolution problème quelconque :

1. concevoir une procédure qui une à fois appliquée amènera à une solution du problème ;

2. résoudre effectivement le problème en appliquant cette méthode.

Le résultat du premier point sera nommé un algorithme. Quant au deuxième point, c'est-à-dire la mise en pratique de l'algorithme, nous l'appellerons un processus.

Ces notions sont très répandues dans la vie courante. Un algorithme peut par exemple y prendre la forme :

· d'une recette de cuisine,

· d'un mode d'emploi,

· d'une notice de montage,

· d'une partition musicale,

· d'un texte de loi,

· d'un itinéraire routier.

Dans le cas particulier de l'informatique, une étape supplémentaire vient se glisser entre la conception de l'algorithme et sa réalisation à travers un processus : l'algorithme doit être rendu compréhensible par la machine que nous allons utiliser pour résoudre effectivement le problème. Le résultat de la traduction de l'algorithme dans un langage connu de la machine est appelé un programme.

Rapide historique
C'est un mathématicien perse du 8ème siècle, Al-Khowarizmi, qui a donné son nom à la notion d'algorithme. Son besoin était de traduire un livre de mathématiques venu d'Inde pour que les résultats et les méthodes exposés dans ce livre se répandent dans le monde arabe puis en Europe. Les résultats devaient donc être compréhensibles par tout autre mathématicien et les méthodes applicables, sans ambiguïté.

En particulier, ce livre utilisait une numérotation de position, ainsi que le chiffre zéro que ce type de représentation des nombres rend nécessaire. Par ailleurs, le titre de ce livre devait être repris pour désigner une branche des mathématiques, l'algèbre.

Si l'origine du mot algorithme est très ancienne, la notion même d'algorithme l'est plus encore : on la sait présente chez les babyloniens, 1800 ans avant JC.

En résumé, il doit être bien clair que cette notion d'algorithme dépasse, et de loin, l'informatique et les ordinateurs.

Langage de description
Instructions de sorties
On se donne une instruction Afficher pour afficher du texte, ainsi qu'une instruction ALaLigne pour poursuivre l'affichage à la ligne suivante.

Patron d'un algorithme
Le patron général est le suivant :

Algorithme Nom Algorithme

Début

... actions

Fin

La première ligne, appelée profil donne essentiellement le nom de l'algorithme. On trouve ensuite un délimiteur de début puis les différentes actions composant l'algorithme et enfin un délimiteur de fin.

Ainsi, l'algorithme suivant est valide :

Algorithme Bonjour

Début

Afficher( 'Hello world !!!')

ALaLigne

Fin

Si Alors Sinon
Algorithme QueFaireCeSoir

Début

Si Pluie

Alors

MangerPlateauTélé

SeCoucherTot

Sinon

MangerAuRestaurant

AllerAuCinema

Fin si

Fin

Boucle Tant que
Algorithme JusquAuMur

Début

Tant que Non (DevantMur) faire

Avancer

Fin tant que

Fin

Boucle Répéter
Algorithme JusquAuMurVersionRépéter

Début

Répéter

Avancer

jusqu'à DevantMur

Fin

À noter que, contrairement à la boucle tant que, on passe toujours au moins une fois dans une boucle répéter. Ainsi, dans l'exemple ci-dessus, on avancera forcément d'un case... il conviendrait donc de tester si l'on n'est pas devant un mur avant d'utiliser cet algorithme.

Variables et types
Une variable est constitué d'un nom et d'un contenu, ce contenu étant d'un certain type. Les types différents : booléen, caractère, chaîne de caractères, nombre entier, nombre réel, etc.

Une déclaration de variables et de types présente plusieurs intérêts :

· réservation de l'espace mémoire correspondant au type (lorsque l'algorithme sera codé sur une machine)

· contrôle de type

· précision sur le profil d'un algorithme

Boucle Pour
Dotés des variables, nous pouvons maintenant écrire un nouveau type de boucle, la boucle pour :

Algorithme CompteJusqueCent

Début

Pour i allant de 1 à 10 faire

Afficher (i)

ALaLigne

Fin Pour

Fin

Lorsque l'on sait exactement combien de fois on doit itérer un traitement, c'est l'utilisation de cette boucle qui doit être privilégiée.

Nouveau patron d'un algorithme
Nous allons maintenant préciser les variables utilisées par l'algorithme et leurs types, en distingant les paramètres externes et les variables internes à l'algorithme. Ainsi, le patron d'un algorithme devient

Algorithme NomAlgorithme (paramètres...)

Variable ...

Début

... actions

Fin

Par exemple,

Algorithme DessineEtoiles (n : entier)

Variable i : entier

Début

Pour i allant de 1 a n faire

Afficher ('*')

Fin pour

Fin

Comparaisons des boucles pour un problème simple
On reprend l'exemple précédent de la boucle pour

Algorithme CompteJusqueCentVersionPour

Variable i : entier

Début

Pour i allant de 1 à 100 faire

Afficher (i)

ALaLigne

Fin Pour

Fin

Et on écrit des algorithmes qui produisent la même sortie (les nombres de 1 à 100) mais en utilisant les différentes boucles.

D'abord, avec la boucle tant que (il faut initialiser i avant la boucle, et l'augmenter de 1 à chaque passage) :

Algorithme CompteJusqueCentVersionTQ

Variable i : entier

Début

i=1

Tant que (i <= 100) faire

Afficher (i)

ALaLigne

i = i+1

Fin tant que

Fin

De même avec la boucle répéter (noter que la condition d'arrêt est ici la négation de la condition du tant que):

Algorithme CompteJusqueCentVersionRepeter

Variable i : entier

Début

i = 1

Répéter

Afficher (i)

ALaLigne

i=i+1

Jusqu'à (i > 100)

Fin

Enfin, en utilisant la récursivité, on obtient :

Algorithme CompteJusqueCentRecursif (n : entier)

Début

Si (n <= 100)

Alors

Afficher (n)

ALaLigne

CompteJusqueCentRecursif (n+1)

Fin si

Fin