Algorithmique impérative/Version imprimable

Algorithmique impérative

Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Algorithmique_imp%C3%A9rative

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

Avant-propos

Introduction

« Les ordinateurs sont inutiles, ils ne savent que donner des réponses. » (Pablo Picasso).

À qui s'adresse ce livre ?

Ce livre s'adresse aux étudiants démarrant une formation autour de l'informatique théorique, c'est à dire principalement dans un cadre universitaire, en début de premier cycle.

Ce livre n'a pas pour objectif d'enseigner la programmation vite fait bien fait, à des lecteurs qui voudraient obtenir des résultat rapidement. Si vous souhaitez apprendre à programmer et être vite opérationnel, la présente lecture vous ennuiera et ne vous mènera pas là où vous voulez aller. Nous vous recommandons particulièrement de vous tourner vers un ouvrage tel que « Programmation Python » qui devrait parfaitement convenir.

Conseils de lecture

Selon vos motivations, vous n'aborderez pas le sujet de la même façon :

aux étudiants débutant une licence universitaire en informatique

il s'agit ici d'aborder les fondations du savoir que vous allez acquérir tout au long de votre cursus. Ne le négligez à aucun prix (au niveau international, on peut parler des formations en Computer sciences)

aux étudiants débutant une formation d'ingénieur ou une préparation aux écoles d'ingénieurs

pour ces étudiants : l'importance de notre sujet dépend de la proximité de la formation avec l'informatique.

aux étudiants universitaires des formations scientifiques "pures"

mathématiciens, physiciens, chimistes, biologistes... : vous aborderez peut-être ce sujet comme première approche de l'informatique. Il ne vous sera pas familier de prime abord mais c'est néanmoins un sujet scientifique qui ne devrait donc pas vous dérouter étant donné votre bagage mathématique. Il y a sûrement des étudiants en informatique sur votre lieu de formation (UFR, faculté...) : profitez de leur caractère habituellement accueillant ; vous pourrez sûrement trouver des étudiants informaticiens qui seront ravis de vous aider. Si vous avez accès à une bibliothèque universitaire, elle contient sûrement des ouvrages qui peuvent vous servir.
Conseil : certains problèmes posés seront peut-être trop « matheux » pour vous. Travaillez plutôt les exercices proposés dans votre formation qui traiteront de notions plus familières.

aux linguistes

vous allez surement être rebutés par ces lectures bien éloignées de votre littérature habituelle. Néanmoins, sachez qu'il n'y a que peu de prérequis à cette étude et que vos « faibles » acquis mathématiques (disons de niveau baccalauréat Série L pour la France) seront suffisants.
Conseil : jetez un œil aux premiers problèmes posés mais ne vous souciez pas des suivants trop « matheux » pour vous. Attachez-vous cependant à bien comprendre ce nouveau langage, sa syntaxe et sa sémantique en insistant sur la partie « Théorie de l'algorithmique impérative ».

aux étudiants de formations professionalisantes BTS, DUT en rapport direct avec l'informatique

vous allez en fait apprendre un (plusieurs ?) langage(s) impératif(s) dans votre formation. Cependant, vous allez surtout aborder l'aspect « pratique » des choses. Ce wikilivre vous permettra de prendre de la hauteur par rapport à vos programmes et de les voir de façon plus abstraite. Concrètement, vous utiliserez votre langage au mieux parce que vous verrez mieux les simplifications possibles : cela allégera d'autant votre travail.
Conseil : ne vous concentrez pas trop sur la syntaxe du langage théorique qui sera présenté dans cette ouvrage (vous aurez tôt fait de l'oublier). En effet, vous apprendrez sûrement un ou plusieurs langages dans votre formation (apprenez-les bien, car buter sur des questions de syntaxe est aussi tragique que buter sur des fautes de français au cours d'une dissertation de philosophie). Concentrez-vous donc plutôt sur l'aspect algorithmique des problèmes : comment cela se déroule, comment obtient-on le résultat (...simplement) sans vous soucier du langage que nous allons utiliser. Prenez quand même le temps de faire le parallèle entre les deux langages : cela ne devrait pas prendre trop de temps ni être trop difficile, étant donné que les langages reprennent des concepts les uns aux autres (concepts que nous avons généralisés ici dans notre langage théorique : les similitudes devraient être assez flagrantes).

À propos de cet ouvrage

L'algorithmique impérative est souvent la première forme d'algorithmique que l'on aborde car elle est la plus intuitive. C'est en fait l'abstraction des concepts propres aux langages de programmation impératifs. L'étude de l'algorithmique impérative permet donc d'aborder les langages typiquement impératifs d'une façon plus rigoureuse.

Afin d'aborder le sujet de façon complète, ce document se compose de trois parties :

1. Une partie théorique qui présente les divers aspects de l'algorithmique impérative et la façon de les exploiter.
2. Une partie sur les outils de travail de l'algorithmicien.
3. Des problématiques concrètes, une analyse simple puis approfondie du problème et de ses solutions.

Petit historique

Comme dans tout cours scientifique qui se respecte, il serait judicieux de contextualiser ce que nous allons aborder dans cet ouvrage. L'étude étant assez fastidieuse, nous allons la réduire au strict minimum. Surtout pour une science si jeune et si vieille à la fois. Ce que nous abordons exploite des concepts dont le plus récent est la Programmation structurée, concept d'Edsger Dijkstra qui publia à ce sujet en 1968. La justesse de ses conclusions rendit la programmation structurée populaire dès 1970. Bien qu'aujourd'hui de nouveaux concepts soient apparus, les conclusions d'Edsger Dijkstra n'ont jamais été remises en cause et ces principes sont encore en œuvre dans les langages de programmation actuels. Nous voici satisfaits pour la partie humaine, quitte à ne retenir qu'une date et un nom, en voici de bons.

Pour la partie technique maintenant, le langage de programmation Pascal, que nous aborderons tout au long de l'ouvrage, a été développé par Niklaus Wirth dans les années 1970 pour suivre dans les faits les théories de Dijkstra. Il a été créé avant tout, à des fins pédagogiques, afin d'éviter d'enseigner la programmation structurée avec un langage de l'époque, qui ne respecterait pas ces concept alors nouveaux. Pour l'anecdote, vous vous en doutiez sûrement, ce nom a été choisi en hommage au mathématicien français Blaise Pascal.

Désolé d'avoir fait si court, nous vous invitons à lire les articles Programmation impérative et Pascal sur Wikipédia.

Qu'est ce qu'un algorithme impératif

Première approche

On peut faire le parallèle entre un algorithme et une recette de cuisine. La recette donne les indications nécessaires pour transformer, étape par étape, des ingrédients de départ en un plat prêt à servir. En suivant la recette, le cuisinier en transpose le texte en actions concrètes. Il en va de même pour l'algorithme : une fois qu'on l'a écrit, on le donne à l'ordinateur qui va le suivre étape par étape, cette fois-ci pour transformer des données de départ en données d'arrivée : les résultats.

Attention toutefois, ce parallèle donne une idée générale mais cache quelques subtilités. En effet, si le cuisinier peut faire deux choses en même temps (faire cuire quelque chose au four pendant qu'il épluche autre chose), l'ordinateur, lui, ne fait qu'une seule chose à la fois.

L'objectif de ce livre est donc d'apprendre à écrire des recettes qu'un ordinateur pourra comprendre. Cela implique le respect des règles d'un langage que nous allons apprendre. Nous pourrons ainsi écrire des recettes qui seront en fait des méthodes pour résoudre des problèmes ou calculer des résultats. L'ordinateur pourra alors suivre la recette et donner les résultats, après avoir effectué tous les calculs (fastidieux) à votre place. Un objectif concret est tout simplement de pouvoir assigner à un ordinateur une tâche trop rébarbative pour en débarrasser un humain.

Définition

Tout d'abord, un algorithme impératif est une séquence d'actions. C'est une séquence car les actions s'effectuent les unes après les autres et non en même temps.

Un algorithme a une fonction, un objectif. Pour cela, il transforme des entrées (aucune, une ou plusieurs) en sorties (une ou plusieurs) : vous lui entrez des données, il vous en sort d'autres.

Distinction algorithme / programme : de l'algorithme découle un programme informatique que l'on peut exécuter sur une machine. Le programme informatique est une traduction de l'algorithme dans un langage de programmation (par exemple Pascal). On peut créer plusieurs programmes informatiques différents à partir d'un même algorithme car chaque langage de programmation a ses particularités. On peut donc dire que l'algorithme est théorique, il est l'abstraction du programme informatique.

Par exemple, l'algorithme par lequel on entre deux nombres entiers et qui donne en sortie la somme de ces deux nombres a pour objectif de faciliter le calcul des sommes de deux nombres, opérations qui peuvent être fastidieuses à faire de tête pour un humain.

Il y a dans la vie courante de nombreux exemples d'algorithmes impératifs qui nous donnent des marches à suivre (mathématiques, recettes de cuisine, ...).

Un algorithme complet, pris ci-dessous comme exemple, donne une idée simple de ce qu'on pourra produire à la fin de l'étude de l'algorithmique impérative. Tous les concepts mis en œuvre dans cet algorithme sont expliqués plus loin, ne vous inquiétez donc pas si certains aspects vous échappent pour l'instant.

Cet algorithme calcule et affiche le périmètre, l'aire et le volume du cercle ou de la sphère dont le rayon est donné par l'utilisateur :

Algorithme cercle
Constantes
  pi = 3,1416
Lexique
  rayon     : réel (* le rayon donné par l'utilisateur *)
  périmètre : réel (* le périmètre du cercle *)
Début
  Afficher("Donner le rayon : ")
  Lire(rayon)
  périmètre ← 2 * pi * rayon
  Afficher("Le périmètre est de : ", périmètre)
  Afficher("L'aire du cercle est de ", pi * rayon²)
  Afficher("Le volume de la sphère est de ",(4/3) * pi * rayon³)
Fin

À la fin de l'apprentissage proposé dans ce livre, vous serez à même de créer ce genre d'algorithme et d'autres bien plus complexes.

Les types, les opérateurs et les expressions

Nous entrons maintenant dans le vif du sujet. Cette première partie est plutôt abstraite et une fois que vous l'aurez étudiée, peut entrainer une sensation de confusion sans application pratique concrète. À cet effet, vous trouverez en fin de document une partie « Ce qu'il faut retenir ». Lors de votre première lecture, n'essayez pas de comprendre mais plutôt d'admettre. Une seconde lecture vous permettra d'avoir une vue d'ensemble et de constater qu'en fait, tout se tient.

Première approche

Un type est la façon de comprendre la signification d'une donnée. Prenons la donnée 4 : elle peut être de type entier (de valeur 4 : 3+1), de type caractère (le caractère "4"), est-ce un réel... ?

Un opérateur transforme des données. Par exemple, la somme est un opérateur qui transforme des données en une autre donnée. Il convient de se demander sur quel(s) type(s) un opérateur fonctionne. Par exemple, la somme de deux données de type "entier" est de type "entier". On peut donc supposer que la somme de deux données de type "réel" sera de type "réel" (rassurez-vous : ce sera le cas). Qu'en est-il de la somme de deux données de type "caractère" et de la somme d'une donnée de type "réel" et d'une autre de type "entier" ?

Une expression est une combinaison d'opérateur et de données. Par exemple "4+3" est une expression comportant un opérateur et deux données de type "entier". Toutes les expressions ont une valeur, "4+3" a la valeur 7 ; 7 est une donnée de type "entier".

Nous avons donc trois notions différentes, mais liées entre elles par des règles que nous allons voir.

Spécification

Chaque type a donc son ensemble de valeurs possibles et des opérateurs qui lui sont propres. Par exemple, le type entier qui peut prendre des valeurs telles que 10 ou 12345...

Les opérateurs sont des fonctions mathématiques et à ce titre, ils ont un espace de départ et un espace d'arrivée. Cette propriété s'étend aux opérateurs puisque chaque opérateur à un ou plusieurs types de départ (fonction à une ou plusieurs variables) et un type d'arrivée.

Prenons la fonction mathématique « somme ». On pourrait noter : somme : ℕ² → ℕ : x,y → x+y. De la même façon, l'opérateur somme ajoute deux données de type "entier" et renvoie un "entier". Remarquez que "a+b" est une notation de somme(a,b).

Pour chaque opérateur que vous découvrez ou utilisez, demandez-vous toujours quels sont les types de départ et d'arrivée. Beaucoup d'erreurs sont dues à des opérateurs mal utilisés.

Une expression est donc une suite d'opérateurs et de données qui doit respecter les règles imposées par l'usage des opérateurs.

Dans notre cours nous allons introduire cinq types, les plus couramment utilisés en informatique :

• entier
• réel
• caractère
• chaîne de caractères
• booléen

Ce(s) dernier(s) vous est (sont) probablement étrangers : ne vous inquiétez pas, nous allons y revenir.

Les entiers et les réels

Voici deux types fidèles à leur définition mathématique.

Les opérateurs sur les entiers sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division entière. Un dernier opérateur est l'opérateur mod, donnant le reste de la division entière. Tous ces opérateurs prennent deux données de type "entier" pour en renvoyer une autre du même type. (Rappel : a = (a / b)*b + a mod b)

Les opérateurs sur les réels sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division. Tous ces opérateurs prennent deux données de type "réel" pour en renvoyer une autre du même type.

Il convient de se demander ce qu'il se passe quand on considère l'expression "a+b" avec a entier et b réel. Cela est censé ne jamais arriver. Néanmoins, on pourra considérer que l'entier se transforme en réel avant l'opération.

Les caractères et les chaînes de caractères

Un caractère est tout simplement une lettre, un chiffre ou un symbole : par exemple, "1", "a", "A", "|" sont des caractères.

Aucun opérateur n'existe sur les caractères, ayant un caractère pour résultat. Dans certains langages de programmation, il peut exister des opérateurs pour ajouter un caractère à une chaîne de caractères.

Une chaîne de caractères est une suite de caractères telle que décrite précédemment. "1", "1abc" (par exemple) sont des chaînes de caractères. À noter que "" est une chaîne de caractères (la seule comportant 0 caractère).

Il n'existe qu'un seul opérateur sur les chaînes. Il s'agit de l'opérateur de concaténation qu'on notera "+". La concaténation revient à mettre la seconde chaîne à la suite de la première.

Par exemple "abc"+"def" est équivalente a "abcdef". Remarquez que l'opérateur de concaténation, même s'il est noté "+", n'est pas commutatif comme l'est la somme, nous n'avons évidemment pas a+b=b+a.

Attention, par la suite, à ne pas confondre 1+2 qui est l'entier de valeur 3 avec "1"+"2" qui est la concaténation des chaînes "1" et "2" qui vaut "12" (et sûrement pas "3").

Il n'existe pas de convention pour désigner l'opérateur de concaténation. Nous pourrons également utiliser la notation ".".

Bien que cela ne doive pas arriver, nous pouvons considérer que l'opération de concaténation effectuée sur des caractères fonctionne et donne une chaîne de caractères.

Introduction à l'arithmétique booléenne

En informatique on introduit un nouveau type un peu moins familier : le booléen. Au même titre que les entiers ou les réels : un booléen peut prendre un ensemble de valeurs et possède ses propres opérateurs.

Il n'est donné ici que quelques explications (nécessaires et suffisantes pour la suite du cours) sur le booléen. Il existe cependant toute une algèbre permettant de travailler sur les booléens. Un complément essentiel de ce cours d'algorithmique impérative est l'étude de l'algèbre de Boole.

Première approche

En mathématiques, les entiers ont été invités pour dénombrer, les réels pour représenter les distances, les volumes, etc... Le booléen a également pour utilité de représenter le réel. Il sert à représenter la véracité, c'est à dire à déclarer si une chose est vraie ou fausse.

L'ensemble des valeurs possibles d'un booléen est de deux (!). Ces deux valeurs sont notées VRAI et FAUX.

Voici deux exemples comportant des informations représentées par des booléens :

Premier exemple : Supposons que E soit en ensemble qui contient les éléments a, b, c et d.

1. L'information cardinal de E est une information qui peut être représentée par un entier (ici 4).
2. L'information b appartient à E est une information qui peut être représentée par un booléen (ici VRAI).
3. L'information e appartient à E est une information qui peut être représentée par un booléen (ici FAUX).
4. L'information 'E comporte au moins 2 éléments est une information qui peut être représentée par un booléen (ici VRAI).

Second exemple : Prenons l'ascenseur d'un immeuble.

1. L'information nombre de personnes dans l'ascenseur peut être représentée par un entier.
2. L'information il y a au moins une personne dans l'ascenseur peut être représentée par un booléen.
3. L'information l'ascenseur est au premier étage peut être représentée par un booléen.
4. etc.

Vous voyez donc qu'un booléen peut servir à représenter une multitude d'informations différentes mais ne remplace pas les entiers, les réels ou tout autre type. Chaque type à un usage et il convient d'user du booléen a bon escient tout comme on ne représente pas une distance avec un entier ou un dénombrement avec un réel.

Opérateurs booléens

Au même titre que pour les autres types, il existe des opérateurs sur les booléen. Nous avons vu que la somme était un opérateur qui prenait deux entiers et renvoyait un résultat de type entier également. Il en va de même pour les booléen.

Opérateur	noté	Type des paramètres	Type du résultat	Valeur du résultat	Exemple	Remarque
négation	non ou ¬	un booléen	un booléen	Si VRAI alors FAUX. Si FAUX alors VRAI	non(VRAI) a pour résultat FAUX non(FAUX) a pour résultat VRAI	non() est une fonction mathématique dite réciproque : non(non(truc)) vaut truc.
conjonction	et	deux booléens	un booléen	Le résultat vaut VRAI seulement si les deux paramètres sont VRAI. FAUX sinon.	VRAI et VRAI a pour résultat VRAI VRAI et FAUX a pour résultat FAUX	On pourra aussi dire "Pour que le résultat soit VRAI il faut que tous les paramètres soient VRAI".
disjonction	ou	deux booléens	un booléen	Le résultat vaut VRAI si au moins un des deux paramètres est VRAI. FAUX si tous les paramètres sont FAUX	VRAI ou VRAI a pour résultat VRAI VRAI ou FAUX a pour résultat VRAI

Vous en serez déjà arrivé à ces conclusions : si b est un booléen,

• b et FAUX vaut FAUX quel que soit b
• b ou VRAI vaut VRAI quel que soit b

Ces opérateurs peuvent bien sûr former des expressions. Quelques exemples :

• non(non(FAUX)) vaut FAUX
• ((VRAI et FAUX) ou VRAI) vaut VRAI

La négation est prioritaire sur la conjonction. La conjonction est prioritaire sur la disjonction.

Tableau récapitulatif

Tableau récapitulatif des types et de leurs opérateurs

Type	Ensemble de valeurs	Opérateurs
Entier	ℕ	+ (somme), - (différence), * (multiplication), / (division entière)
Réel	ℝ	+ (somme), - (différence), * (multiplication), / (division)
Booléen	{VRAI ; FAUX}	¬ (négation), et (conjonction), ou (disjontion)
Caractère
Chaîne de caractères		Concaténation

Ce qu'il faut retenir

Ce chapitre est abstrait et ne donne rien de concret. N'apprenez pas par cœur, tout ceci se tient et est assez cohérent par rapport à ce que vous avez appris sur les mathématiques. Voici ce qui doit retenir votre attention :

• Retenez les noms des différents types et de leurs opérateurs en retenant bien quel opérateur fait quoi et avec quoi. Vous devriez pouvoir reconstruire de tête le tableau récapitulatif (encore une fois, vous ne devriez pas avoir à l'apprendre, vous devriez pouvoir le déduire des types).
• Retenez que les booléen, les caractères et les chaînes de caractères et leurs opérateurs fonctionnent exactement de la même façon que les entiers et les réels. Ce sont des types, qui ont un ensemble de valeurs possibles et des opérateurs spécifiques. On peut écrire des expressions à condition de respecter certaines règles.
• Essayez de voir un peu comment on manipule cette arithmétique booléenne qui, comme l'arithmétique entière, vous permet de calculer des expressions et d'en simplifier d'autres. Remarquez que cette arithmétique est plus simple puisque vous n'avez que deux valeurs possibles (c'est peu par rapport à l'infinité d'entiers...).
• Vous pouvez déjà faire les exercices sur ce chapitre. Si vous avez su les résoudre sans relire ce cours.

Les constantes, les variables

Dans un algorithme, il faut stocker les données à traiter. Certaines de ces données sont connues et ne varieront pas tout le long de l'algorithme : il s'agit des constantes. D'autres données peuvent être inconnues (elle seront fonction du choix de l'utilisateur, ou du temps...) ou susceptibles d'évoluer au cours de l'algorithme : il s'agit des variables.

Les variables

Toutes les variables ont un type. Dans chaque algorithme, toutes les variables et leurs types sont explicitées dans le lexique. On dit que la variable est déclarée.

D'un point de vue mathématique, la déclaration revient à l'expression "Soit ... un ...".

Le lexique est noté comme suit :

Variables
 identifiant_de_la_variable : type de la variable;
 ...

Un exemple

Variables
     n : entier
     1 : réel
 une réponse : booléen
 un nom de famille : chaîne de caractère

Dans cet exemple, nous avons cinq variables.

Du point de vue mathématique, on aurait pu énoncer "Soit n un entier", "Soit 1 un réel", "Soit vrai ou faux booléen", etc.

Les constantes

De la même façon, les constantes sont déclarées dans une partie Constantes de cette façon :

Constantes
  nom_de_la_constante = valeur

Un exemple

À priori, on peut considérer que PI ne risque pas de changer de valeur pendant un algorithme. On peut donc déclarer PI en tant que constante.

Constantes
  pi = 3.14
  ...

Une seule constante est déclarée.

Les instructions, les blocs d'instructions

Nous avons vu qu'un algorithme est une séquence d'instructions ; de quoi s'agit-il exactement ? Les instructions sont les actions devant être effectuées par l'algorithme. Elle peuvent requérir que l'on précise certaines informations.

Deux instructions de base

Voici expliquées deux instructions que l'on retrouvera très fréquemment dans des algorithmes. Il s'agit des instructions Afficher et Lire.

Afficher

Afficher permet d'afficher des données à l'écran et ainsi de communiquer avec l'utilisateur. Pour cette instruction, on doit préciser une expression qui sera évaluée avant d'être affichée.

Quelques exemples :

Afficher ("ceci est un exemple : on affiche une chaîne, sans utiliser de variables")

Ce programme affiche :

ceci est un exemple : on affiche une chaîne, sans utiliser de variables

Si l'algorithme contient

Constantes
  PI = 9

Le programme

Afficher(PI)

affiche

9

Lire

La fonction Lire permet de demander à l'utilisateur de fournir des informations. Chaque information donnée par l'utilisateur est stockée dans une variable (attention au type !). Vous précisez cette variable dans les parenthèses.

Un exemple : nous réalisons un algorithme qui demande à l'utilisateur d'entrer son âge. Tout d'abord il apparaîtra dans le lexique :

Lexique
  age : entier (* l'âge donné par l'utilisateur *)

Pour demander l'âge :

Lire(age)

Les blocs d'instructions

Souvent, l'exécution d'une seule instruction ne suffit pas pour faire un algorithme complet. Nous pouvons faire en sorte que plusieurs instructions soient considérées comme une seule. Pour cela, il faut créer un bloc d'instructions. Partout où l'on peut mettre une instruction, on peut mettre un bloc d'instructions.

Concrètement, on procède ainsi : les instructions sont séparées par un saut de ligne ou par ;. Le bloc d'instruction est précédé de Début et suivi de Fin.

Un exemple :

Début
  instruction1
  instruction2
  Afficher("Cet affichage est la troisième instruction")
  instruction4
Fin

Une autre notation, courante dans les langages de programmation, est plus courte. Les instructions formant un bloc sont entre { et }.

L'assignation

L'assignation est une instruction qui consiste à inscrire dans une variable une valeur calculée depuis une expression. Attention : la nouvelle valeur affectée « écrase » la précédente.

C'est donc la deuxième façon que nous apprenons de donner une valeur à une variable. La première était d'utiliser l'instruction Lire qui permet de demander la valeur à l'utilisateur. On peut dire que l'instruction Lire est une forme particulière d'affectation.

Pour effectuer une assignation, on utilise l'instruction Assigner. On précise entre parenthèses la variable affectée ainsi que l'expression de la valeur de l'affectation.

On pourra également noter l'affectation ← ou :=. Ce symbole peut être énoncé « prend pour valeur ». Attention toutefois à ne pas la noter = bien que certains langages utilisent cette notation. Ce serait un dangereux raccourci de pensée avec les mathématiques (voir la mise en garde ci-dessous).

Un exemple : voici notre lexique

Lexique
  n : entier

On assigne n :

Assigner(n, 12)

À partir de maintenant la variable n vaut 12. Ainsi, l'instruction

Afficher(n)

provoquera l'affichage suivant :

12

Dans la suite du cours, nous utiliserons la notation ←, moins lourde.

Mise en garde sur le parallèle avec les mathématiques

Au moment de l'affectation, la valeur affecté est évaluée, c'est-à-dire calculée, les constantes et les variables sont donc remplacées par leurs valeurs respectives.

Exemple : dans le lexique nous avons :

Lexique
  a,b,c : entiers

a←1
b←2
c←a+b (* équivaut à c←2+1 et à c←3 *)
afficher(c) (* affiche 3 *)
b←5
afficher(c) (* affiche toujours 3 et non 6 *)

c conserve sa valeur tant qu'elle n'a pas été affectée, le changement de la valeur de b n'affecte pas la valeur de c.

Certains seraient tentés de noter l'affectation avec l'opérateur "=", elle est d'ailleurs notée ainsi dans le langage de programmation C. C'est pourtant une erreur vis-à-vis du sens mathématique de ce symbole. En effet, cette expression :

x = x+1

est tout à fait correcte en informatique si on considère l'affectation notée ainsi ; cela revient à incrémenter x. Mais du point de vue mathématique c'est une aberration. Voyons cela en appliquant une résolution d'équation du premier degré :

$x=x+1$

par soustraction de x dans les deux membres :

$x-x=1$

donc

$0=1$

En revanche, l'affectation notée := est valide en mathématique comme en informatique. En prenant cette convention, tout le monde est content...

Les exécutions conditionnelles

Vous savez que les instructions s'exécutent les unes après les autres. C'est intéressant mais insuffisant pour élaborer des algorithmes complexes. En effet, nous pourrions avoir besoin d'exécuter certaines instructions seulement dans un certain contexte. Les structures permettant d'imposer la succession des instructions sont appelées structures de contrôles. L'exécution conditionnelle, que nous allons voir ici, est la plus simple de ces structures de contrôles.

SI...ALORS...

L'exécution conditionnelle permet de n'exécuter une instruction que si une certaine condition est remplie. La syntaxe est la suivante :

SI condition
  ALORS instruction
FINSI

• condition est une expression booléenne. L'instruction n'est exécutée que si cette l'expression booléenne est évaluée à VRAI. Si condition est évaluée à FAUX aucune instruction n'est exécutée. Dans les deux cas, le programme poursuit son exécution par ce qui se trouve après le FINSI.
• instruction est une instruction normale. Vous pouvez bien sûr exécuter plusieurs instructions : il suffit pour cela d'un bloc d'instructions.

Exemples

 SI FAUX
   ALORS Afficher("Cet affichage ne se produira jamais, la condition n'étant jamais VRAI")
 FINSI

Cet extrait d'algorithme n'a aucun intérêt. S'il est effacé du programme, on obtient un programme équivalent.

SI VRAI
  ALORS Afficher("Cet affichage se produit toujours")
FINSI

Cet extrait d'algorithme n'a aucun intérêt. Il aurait évidemment suffit d'écrire :

Afficher ("Cet affichage se produit toujours")

...SINON

Il est possible de préciser une instruction à exécuter si la condition n'est pas vérifiée, c'est-à-dire si elle est évaluée à FAUX. Il suffit pour cela d'ajouter une partie SINON entre ALORS et FINSI. Cette partie SINON n'est pas toujours utile, elle est donc facultative.

SI condition
  ALORS instruction
  SINON instruction
FINSI

Exemples

SI condition
  ALORS Afficher("La condition vaut VRAI")
  SINON Afficher("La condition vaut FAUX")
FINSI

Une équivalence utile

Remarquez que ces deux blocs conditionnels sont équivalents :

SI condition
  ALORS instruction_A
  SINON instruction_B
FINSI

SI non(condition)
  ALORS instruction_B
  SINON instruction_A
FINSI

Les structures itératives

Les structures de contrôle itératives permettent d'exécuter plusieurs fois de suite une ou plusieurs instructions. Il en existe trois distinctes.

Structure POUR

La structure POUR permet d'exécuter une instruction un nombre connu de fois. Voici la syntaxe :

POUR i DE deb A fin FAIRE
  instruction
FINPOUR

i est l'identifiant d'une variable (qui doit bien sûr être déclarée). deb et fin sont deux expressions de même type que i : ce sont les valeurs entre lesquelles i va parcourir l'ensemble des valeurs intermédiaires.

La structure s'exécute de la façon suivante :

1. i est affecté à la valeur de deb (i←deb)
2. si i est différent de fin alors on exécute instruction
3. incrémenter i (i←i+1)
4. revenir au point 2

Il est évident que pour que le programme fonctionne deb<fin.

Exemples

Dix itérations

Lexique
  i : entier
Début
  POUR i de 1 à 10 FAIRE
    Afficher(i);
  FINPOUR
FIN

Ce programme va afficher :

1
2
3
4
5
6
7
8
9
10

Structure TANTQUE

TANTQUE condition
  instruction
FINTANTQUE

condition est une expression booléenne, comme dans la structure SI condition ALORS...

Cette structure est exécutée comme suit :

1. si condition est vraie : exécuter instruction sinon, continuer après FINTANTQUE
2. reprendre au point 1

La boucle infinie

Il est possible grâce à cette structure de créer une boucle infinie :

TANTQUE VRAI
 instruction
FTQ

Une boucle POUR

Il est possible de simuler une boucle POUR à l'aide d'un TANTQUE

i←deb
TANTQUE i <= fin
  instruction
  i←i+1
FTQ

Structure REPETER

REPETER
  instruction
JUSQU'A condition

condition est une expression booléenne.

Cette structure s'exécute comme suit :

1. exécuter instruction
2. si condition est vrai : continuer au point 3 sinon, reprendre au point 1
3. exécuter ce qui suit le JUSQU'A

La boucle infinie

Il est possible grâce à cette structure de créer une boucle infinie :

REPETER
 instruction
JUSQU'A FAUX

Une boucle POUR

Il est possible de simuler une boucle POUR à l'aide d'un REPETER

i←deb
REPETER
  instuction
  i←i+1
JUSQU'A i=fin

Comment déterminer la structure à utiliser ?

Le choix de la structure de contrôle se fait en fonction du nombre d'itérations à effectuer :

• si le nombre d'itérations est déterminé à l'avance, une boucle POUR est la plus appropriée,
• sinon :
  • si la condition de boucle ne peut être évaluée avant la première itération, ou si au moins une itération doit être exécutée, la boucle REPETER est la plus appropriée,
  • sinon la boucle TANT QUE est la plus appropriée.

Les tableaux

Première approche

Le tableau est un nouveau type. Il contient un ensemble d'éléments indicés par des entiers ; on peut donc utiliser des variables tableaux.

Nous n'étudierons que les tableaux à une dimension également appelés vecteurs.

Spécification

Les tableaux sont déclarés comme suit :

Lexique
  tab : tableau DEBUT à FIN de TYPE

• tab est l'identifiant de la variable tableau
• DEBUT est un entier : l'indice du premier élément du tableau, généralement 0 ou 1.
• FIN est un entier : l'indice du dernier élément, cela peut être un entier fixé ou, plus intéressant, une constante déclarée.
• On a évidemment FIN > DEBUT
• TYPE est le type de chacun des éléments du tableau.

Par exemple, un tableau d'entiers de 10 cases

Lexique
  tab : tableau 1 à 10 de entier

On accède au i^ème du tableau comme suit

tab[i]

• i est un entier qui doit évidemment être compris entre DEBUT et FIN (précisés dans la déclaration de tab)
• la variable tab[i] est donc du type TYPE (précisé dans la déclaration de tab)

Utilisation

La tableau est utilisé lorsqu'il faut stocker des suites de variables de même rôle. Par exemple, les notes d'un groupe d'étudiants en algorithmique impérative.

La structure POUR se prête très bien au parcours d'un tableau. En supposant le tableau tab déclarer comme suit :

Lexique
  tab : tableau MIN à MAX de TYPE

Il suffit pour afficher ses éléments de

Pour i de MIN à MAX
  Afficher(tab[i])
FP

Les procédures et les fonctions

Première approche

Les procédures et les fonctions sont des sous-programmes qui permettent une réutilisation du code plus facile. En effet, si par exemple on code l'algorithme de calcul de T.V.A. et qu'on l'utilise à divers endroits du programme, plutôt que de recopier le code à chaque fois, il est préférable de créer un sous-programme de calcul. La recopie a toutefois les inconvénients suivants :

• La recopie du code s'accompagne souvent d'un changement des noms de variables, voire de la valeur de certains paramètres,
• Chaque copie du code augmente la taille des programmes source et compilé,
• La maintenance est plus difficile : s'il faut modifier l'algorithme, il faut modifier toutes les copies sans en oublier une seule.

L'utilisation d'un sous-programme évite tous ces problèmes :

• Les sous-programmes utilisent des variables locales et des paramètres formels, c'est-à-dire qu'on leur passe les valeurs (voire les variables, par adresse ou référence) qu'ils doivent utiliser.
• L'algorithme n'est codé qu'une seule fois, ce qui n'augmente pas la taille du programme.
• La maintenance est facilitée par le point précédent : s'il faut modifier l'algorithme, la modification n'a lieu qu'en un seul endroit.

Procédure et fonction : quelle différence ?

Une procédure traite les informations qu'on lui passe, mais ne retourne, en général, aucun résultat. En général, cette procédure a un effet de bord.

Une fonction traite les informations qu'on lui passe, et retourne un résultat. Si la fonction n'a aucun effet de bord, on peut la comparer à une fonction mathématique.

Effet de bord

un sous-programme avec effet de bord modifie l'état global de l'application. En général, appeler deux fois un même sous-programme avec effet de bord en lui passant les mêmes paramètres ne produit pas le même résultat.

Le type enregistrement

Première approche

L'enregistrement est une façon de créer un nouveau type, ou encore un méta-type, c'est-à-dire un type qui contient d'autres variables de types déjà définis.

Spécification

On déclare un nouveau type dans la partie Types comme suit :

identifiant_du_type = enregistrement
  identifiant_première_sous_valeur : type_de_la_première_sous_valeur
  identifiant_deuxième_sous_valeur : type_de_la_deuxième_sous_valeur
  ...
fin

on peut ensuite déclarer normalement les variables de ce nouveau type :

identifiant_variable : identifiant_du_type

Pour accéder à une sous-valeur de la variable, nous utiliserons l'expression :

identifiant_variable.identifiant_sous_valeur

Cette expression est du type de identifiant_sous_valeur.

Exemple

Supposons que nous voulions un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :

couple = enregistrement
  a : entier
  b : entier
fin

Supposons maintenant que nous avons le lexique suivant :

Lexique
  c : couple

Si nous assignons :

c.a ← 1
c.b ← 2
afficher(c.a) (* affichera 1 *)

Le projet sur les dates propose un travail complet sur le sujet.

Utilisation

Cela n'est pas obligatoire en algorithmique impérative, mais pour travailler sur un nouveau type , il convient de définir quelques fonctions élémentaires pour créer une variable à partir de ses sous-valeurs. Remarquez que les types de paramètres seront semblables aux types des sous-variables de nouveau type (exception faite dans le cas de sous-valeurs par défaut...).

Exemple

Pour reprendre notre exemple, nous pourrions créer une fonction :

fonction creerCouple(m, n : entiers)
(* créer un couple à partir de ses deux éléments *)
lexique
  NouveauCouple : couple
debut
  NouveauCouple.a ← m
  NouveauCouple.b ← n
  renvoyer NouveauCouple
fin

L'algorithme au final : vue d'ensemble

Au final, l'algorithme se compose de la façon suivante :

1. Algorithme suivi du nom de l'algorithme
2. De la déclaration des procédures et des fonctions
3. De la déclaration des constantes de l'algorithme principal
4. De la déclaration des variables de l'algorithme principal
5. De l'algorithme principal

Algorithme nom_de_l'algorithme
Fonction1(paramètre1 : type du paramètre 1 (* objet du paramètre1 *)
          paramètre2 : type du paramètre 1 (* objet du paramètre2 *))
         : type de la valeur de retour
Constantes locales de la Fonction1
  constante1 = valeur_de_la_constante1
  constante2 = valeur_de_la_constante2
  constante3 = valeur_de_la_constante3
Variables locales de la Fonction1
  variable1 : type_de_la_variable1
  variable2 : type_de_la_variable2
  variable3 : type_de_la_variable3
Début
  instruction1
  instruction2
  Retourner valeur
Fin

Procédure1(E|S|ES paramètre1 : type du paramètre 1 (* objet du paramètre1 *)
           E|S|ES paramètre1 : type du paramètre 2 (* objet du paramètre2 *)
           E|S|ES paramètre1 : type du paramètre 3 (* objet du paramètre3 *))
Constantes locales de la Procédure1
  constante1 = valeur_de_la_constante1
  constante2 = valeur_de_la_constante2
  constante3 = valeur_de_la_constante3
Variables locales de la Procédure1
  variable1 : type_de_la_variable1
  variable2 : type_de_la_variable2
  variable3 : type_de_la_variable3
Début
  instruction1
  instruction2
Fin

Constantes de l'algorithme principal
  constante1 = valeur_de_la_constante1
  constante2 = valeur_de_la_constante2
  constante3 = valeur_de_la_constante3

Variables de l'algorithme principal
  variable1 : type_de_la_variable1
  variable2 : type_de_la_variable2
  variable3 : type_de_la_variable3

Début
  instruction1
  instruction2
Fin

Exercices

Types, expressions et opérateurs

Questions théoriques

1. Citez des exemples de types
2. Donnez un opérateur polymorphe
3. Écrire un programme qui saisit trois nombres dans un ordre donné et les fait sortir dans l'ordre inverse d'entrée.

Solutions :

1. booléen, entier, réel, caractère, chaîne de caractères
2. + (polymorphe car fonctionne avec des entiers et des réels)

Types et valeurs

Donner le type des expressions suivantes et leur valeur

1. 0
2. 1+2
3. 0.0+1.0
4. "a"
5. "a"."b"="b"
6. "a"."b"

Donner le type de a et de l'expression :

1. a+1
2. a."b"
3. a=1.0

Solutions

1. entier : 0
2. entier : 3
3. réel : 1.0
4. caractère : "a"
5. booléen : FAUX
6. chaîne de caractères : "ab"

Questions avec la variable a :

1. entier ; a entier
2. chaîne de caractères : a caractère ou chaîne de caractères
3. booléen : a réel

Calcul booléen

Quelle est la valeur de ces expressions booléennes ?

1. non(VRAI)
2. VRAI et FAUX
3. FAUX ou FAUX
4. VRAI et VRAI
5. non(FAUX ou VRAI)
6. FAUX et ((VRAI et VRAI) ou (VRAI et (FAUX ou (VRAI et FAUX)))))
7. VRAI ou (VRAI et (FAUX ou ((FAUX et VRAI) ou VRAI)))

a et b sont des booléens, simplifier les expressions :

1. non(non(a))
2. non(non(non(b)))
3. faux ou a
4. faux et a
5. vrai et a
6. vrai ou a
7. a et non(a)
8. a ou non(a)
9. non(a=b) et (a=b)

Solutions

1. FAUX
2. FAUX
3. FAUX
4. VRAI
5. FAUX
6. Il suffit de lire "FAUX et ..." au début de l'expression pour savoir tout de suite le résultat. Quel que soit ce qu'il y avait après le et cela aurait été FAUX.
7. De même, il suffit de lire "VRAI ou ..." au début de l'expression pour savoir tout de suite le résultat : peu importe ce qu'il y a après le ou, cela aurait été VRAI
8. ...

Simplifications :

1. a
2. non(b)
3. a
4. faux
5. a
6. vrai
7. faux
8. vrai
9. faux

Condition

Donner un extrait d'algorithme équivalent à celui-ci sans utiliser de sinon :

si condition
  alors instruction1
  sinon instruction2

Solution

si condition
  alors instruction1
finsi
si non(condition)
  alors instruction2
finsi

Boucles

13 à 47

Donner une boucle qui affiche les entiers de 13 à 47

Solution:

Pour i de 13 à 37
  Afficher(i)
FP

de 5 en 5

Donner une boucle affichant les entiers de 5 en 5 et de 5 à 100

Solutions :

i←0
Répéter
  i←i+5
  afficher(i)
Jusqu'à i=100

i←5
Répéter
  afficher(i)
  i←i+5
Jusqu'à i=105

pour i de 5 à 100
  si i mod 5 = 0 alors afficher i
fp

pour i de 1 à 20
  afficher(5*i)
fp

Remarque : ces algorithmes fonctionnent tous mais certains sont plus efficaces que d'autres. Cette réflexion est laissée au lecteur.

Tableaux

Selon la déclaration suivante

tab : tableau 0 à 10 de T

Combien le tableau a-t-il d'éléments ? 9, 10, 11 ?

Le tableau contient 11 éléments.

Procédures et fonctions

Écrire des fonctions en procédures, des procédures en fonctions.

La rédaction d'un algorithme

Lorsqu'on rédige un algorithme, il faut toujours garder à l'esprit qu'il doit pouvoir être lu et compris par quelqu'un d'autre. Au fur et à mesure de la pratique, les rédacteurs ont dégagé quelques principes dont les plus simples sont expliqués ici. Il convient de respecter ces principes d'une façon rigoureuse.

Remarque pour les étudiants : il est parfaitement admis que le respect de ces règles de rédaction soit pris en compte dans la note finale. Quand vous écrivez une dissertation, il convient de respecter la grammaire et l'orthographe même si ce n'est pas ce qui doit être évalué, il en est de même ici.

Indenter son code

L'indentation d'une ligne est l'espace qui la sépare de la marge gauche.

Problème

Considérons l'algorithme (incomplet) suivant :

Début
  si condition1 alors
    instruction1
  sinon
    si condition2 alors
      instruction2
    sinon
      instruction3
    finsi
  finsi
Fin

Voici le même algorithme mais sans l'indentation :

Début
si condition1 alors
instruction1
sinon
si condition2 alors
instruction2
sinon
instruction3
finsi
finsi
Fin

Il est déjà moins évident de comprendre le fonctionnement de l'algorithme. Ce dernier est toutefois plus abordable que :

Début
si condition1 alors instruction1 sinon si condition2
alors
      instruction2 sinon instruction3
finsi finsi
Fin

et pourquoi pas...

 Début si condition1 alors instruction1 sinon si condition2 alors instruction2 sinon instruction3 finsi finsi Fin

Comment faire

Pour bien indenter, considérez les blocs et mettez au même niveau le début du bloc et la fin du bloc. Par exemple, un fin devrait se trouver au même niveau que son début : on devrait l'apercevoir immédiatement étant donné que tout ce qu'il y a entre les deux devrait se trouver un niveau d'indentation plus loin.

début
  ...
  début
    ...
  fin
  ...
fin

Procédez ainsi avec

• SI...FINSI
• TANTQUE...FTQ
• REPETER...JUSQU'A
• POUR...FP

De même : placez les alors et les sinon au même niveau.

Vous pouvez transformer ces règles, l'important étant de les fixer et de s'y tenir. Il existe plusieurs façons d'indenter et chaque auteur a ses préférences.

Utiliser des identifiants pertinents

Pour choisir un identifiant de variable ou de fonction, souvenez-vous qu'il doit remplir deux utilités principales

• décrire son rôle (sans toutefois remplacer le commentaire en déclaration)
• distinguer des autres (ne pas se retrouver avec deux fonctions calculer_nombre et calculer_nb, quotient et division...)

Évitez :

• de répéter le type de la variable dans son identifiant (entier_n, chaine_départ)
• les conventions utilisées en maths (n ou x ne suffisent pas pour décrire le rôle d'un entier/réel)

Pensez également aux conventions, notamment :

• i (j, k...) comme variable de boucle
• utiliser un préfixe pour signaler les variables entrées du programme qui seront données par l'utilisateur.

Commenter utile

Il ne faut pas décrire ce que vous faites mais pourquoi vous le faites

POUR i de 1 à 24 FAIRE
  instruction
FINPOUR

Pour cet algorithme le commentaire :

• (* il y a 24 heures dans une journée donc 24 instructions *) est pertinent. Plus particulièrement, le commentaire répond à la question "pourquoi 24 et pas 25 ?".
• (* i va de 1 à 24 *) n'est pas pertinent. Il ne répond pas à la question "pourquoi 24 et pas 23 ?".

Servez-vous également des commentaires pour indiquer ce que vous supposez : les conditions dans lesquelles votre algorithme fonctionne.

Travaux pratiques, tester un algorithme sur une machine

« Tester un programme peut montrer la présence de bugs, pas leur absence ».
(Edsger Dijkstra : Notes On Structured Programming, 1970)

Le langage de programmation le plus simple permettant d'implémenter directement un algorithme impératif par simple traduction de celui-ci est le langage Pascal, qui a été développé dans cette optique. Ainsi, un travail pratique qui peut accompagner l'apprentissage peut être simplement d'expérimenter des programmes en les recopiant et en visionnant le résultat en situation, sur une machine.

Prérequis

Prérequis cognitif

• l'algorithmique impérative, il est évidemment nécessaire d'avoir créé des algorithmes avant de vouloir les mettre sur une machine.
• Utilisation simple de l'ordinateur (édition de texte).

Prérequis logiciels

Un éditeur de texte : le plus simple suffit. Toutefois, il existe des éditeurs de texte qui facilitent l'édition d'un code source. On les appelle les éditeurs de code-source. En plus du simple éditeur de texte, ils proposent les fonctionnalités suivantes :

• Coloration syntaxique
• Complétion automatique des mots clés
• Numérotation des lignes (vous verrez que c'est indispensable : en effet, si le compilateur trouve une erreur dans votre code source, il vous indiquera le numéro de la ligne où elle se trouve)
• Aide à l'indentation

Quelques éditeurs de code source : Notepad++ (Windows), TextMate (Mac OS), SciTE (Windows et Linux) pour les plus abordables mais aussi emacs, vi (voir la catégorie éditeur de texte sur Wikipédia pour une liste exhaustive).

Un compilateur Pascal : Free Pascal est bon, libre, gratuit et fonctionne sûrement sur votre plateforme.

Un terminal, pour lancer et tester vos programmes. Vous pouvez utiliser un terminal classique sous Linux et Mac OS X. Sous Windows, cela s'appelle « Ligne de commande DOS ».

Il existe des logiciels qui réunissent toutes ces fonctionnalités : éditeur de code + compilateur + terminal. On les appelle les environnements de développement, certains sont complexes mais il en existe de très simples qui vous permettent de compiler le code et de lancer le programme simplement en appuyant sur un bouton. Geany (Linux) est parfait à notre niveau.

Note aux étudiants : votre salle de Travaux Pratiques sera sûrement équipée, votre enseignant vous indiquera comment accéder à tout ça.

Prérequis matériels

Un ordinateur, n'importe lequel et de n'importe quelle architecture (PC ou Mac), du moment que les prérequis logiciels sont respectés.

Les limites de l'ordinateur

Un ordinateur est une machine finie (par curiosité, vous pouvez voir la notion d'automate fini). De ce fait on ne peut pas tout calculer en un temps fini. Votre algorithme peut être bon mais ne pas fonctionner sur ordinateur. La finitude se voit aussi dans les grandeurs. Vous ne pouvez pas manipuler des nombres aussi grand que vous voulez. Les technologies ont leur limite. Cependant, les ordinateurs d'aujourd'hui sont assez développés pour que vous ayez une assez grande marge de manœuvre.

Problème de la valeur entière maximale

Petit TP : faites un algorithme qui prend une valeur entière, l'augmente et l'affiche sans cesse et observez à partir de quand le programme commence à donner des valeurs incohérentes.

En Pascal par exemple : l'entier maximal représentable est contenu dans la constante MAXINT (qui vaut 32 767). Cela a pour effet d'avoir 32 767 + 1 = -32 768.

Note hors-sujet : pour comprendre pourquoi ce problème se pose : voir la partie codage des entiers signés dans le cours d'architecture des ordinateurs.

Éviter ce problème

Si vous êtes confronté au problème : essayez de changer votre algorithme en privilégiant les calculs approchant les 0. Voici un exemple plus clair : a et b sont deux entiers entre 5 000 et 10 000 avec a > b

c:=30000+a 
c:=c-b

peut ne pas fonctionner car on a dépassé 32 767. Par contre,

c:=30000-b
c:=c+a

peut fonctionner car on n'a pas dépassé 32 767.

Comment programme-t-on ?

Vous avez donc votre algorithme, comme vous êtes doué(e) : vous êtes sûr(e) qu'il fonctionne, cependant vous voulez le vérifier in situ sur un ordinateur. Voici les étapes (toutes expliquées ci-après) à suivre pour obtenir votre programme informatique :

1. Traduire l'algorithme en Pascal : cette étape peut se faire sur papier, au brouillon. Comme c'est simple et rapide on peut traduire en même temps qu'on fait l'étape suivante.
2. Recopier la traduction (le code source) dans un éditeur de texte.
3. Compiler le code source pour le transformer en programme machine (ou binaire).

Le compilateur a engendré un programme, il ne vous reste qu'à l'exécuter pour vous en servir ou le tester.

Traduire l'algorithme en Pascal

Pascal ayant été prévu dans cette optique, il est très facile de convertir un algorithme (sur papier) en un programme exécutable (fichier texte sur un ordinateur). Voici un exemple de traduction afin de vous montrer que la ressemblance est réelle et que la traduction est facile. Cet exemple reprend l'algorithme donné dans le chapitre d'introduction.

Voici l'algorithme :

Algorithme cercle
Constantes
  pi = 3.1415
Lexique
  rayon     : réel (* le rayon donné par l'utilisateur *)
  périmètre : réel (* le périmètre du cercle *)
Début
  Afficher("Donner le rayon : ")
  Lire(rayon)
  périmètre←2*pi*rayon
  Afficher("Le périmètre est de : ", périmètre)
  Afficher("L'aire du cercle est de ", pi*rayon²)
  Afficher("Le volume de la sphère est de ",(4/3)*pi*rayon³)
Fin

et le code source en langage Pascal

program cercle;
const
  pi = 3.1415;
var
  rayon     : real; (* le rayon donné par l'utilisateur *)
  perimetre : real; (* le périmètre du cercle *)
begin
  writeln('Donner le rayon : ');
  readln(rayon);
  perimetre:=2*pi*rayon;
  writeln('Le périmètre est de : ', perimetre);
  writeln('L''aire du cercle est de ', pi*sqr(rayon));
  writeln('Le volume de la sphère est de ',(4/3)*pi*power(rayon,3))
end.

Pour traduire n'importe quel algorithme dans le langage Pascal, il suffit de respecter un certain nombre de règles de syntaxe simples. Tout ceci est développé dans le guide de traduction en Pascal.

Pour ce qui est de l'indentation : utiliser la caractère de tabulation prévu pour et surtout pas d'espaces. Il s'agit de la touche à gauche de la touche A (clavier AZERTY) ou de la touche Q (en clavier QWERTY). Il est possible que vous trouviez ce caractère trop large, un bon éditeur permet de régler cette largeur en donnant la taille souhaitée en largeurs de caractères, par exemple donner 4 comme valeur fera que les tabulations ont une largeur de 4 caractères si vous utiliser une police mono-espacée (ce qui doit être le cas dans un éditeur de code). Dans le cas contraire, c'est la taille du caractère d'espacement qui est considérée (dans notre exemple, la tabulation aura la même largeur que 4 espaces). Par défaut la taille des tabulations est de 8, nous vous recommandons 2,3 ou 4 à régler selon que me nombre des niveaux d'indentations est très élevé ou plus modéré. À noter qu'on peut essayer avec un réglage à 4 puis décrémenter a posteriori si besoin est.

Avant l'exécution, la compilation

Étape (que beaucoup trouvent la plus agréable, allez savoir pourquoi...) où il n'y a rien à faire puisque le compilateur se débrouille tout seul. Il vous suffit de lui demander de compiler votre code source. Nous n'allons pas décrire ici toutes les façons de faire car il y en a de multiples : cela dépend de vos choix logiciels. (si vous êtes étudiant, votre responsable de TP est censé vous expliquer tout ça).

Lancez la compilation, deux issues sont possibles :

Premier cas : la compilation échoue. Ne paniquez pas car rien n'est joué ! C'est très courant, même les informaticiens qui ont 20 ans de métier font encore parfois des erreurs. La plupart des compilateurs vous diront pourquoi ils refusent de compiler, ils vous indiqueront même où se situe l'erreur (ligne du code source) voire, dans certains cas, ils vous donnerons l'erreur et la correction à faire. Retournez éditer votre code source et corrigez l'erreur. Vous verrez que la plupart du temps il s'agit de fautes d'inattention (des '=' à la place des ':=', d'oublis de points-virgules en fin d'instructions, etc). Relancez la compilation. Parfois il faut recompiler vingt fois avant d'arriver à finir la compilation (c'est fou ce qu'il peut y avoir comme point-virgules...).

Second cas : la compilation fonctionne. Le compilateur vous indique qu'il a réussi. Vous devriez avoir maintenant à côté de votre fichier source un exécutable.

Exécuter le programme

Là encore, il existe tellement de possibilités de faire que nous ne les expliquerons pas ici. Assurez-vous de connaître un moyen d'arrêter un programme récalcitrant. (les étudiants se tourneront encore une fois vers leur enseignants de TP).

Pour tester votre programme, entrez des valeurs comme si vous l'utilisiez. Essayez de tester "toutes" les combinaisons en faisait des essais représentatifs. à expliciter...

Un problème ?

Voici les erreurs que vous pourriez constater en exécutant votre programme et des pistes pour les résoudre :

Erreur d'exécution	Où chercher l'erreur
Le programme boucle sans fin	Assurez-vous que le programme boucle sans fin en attendant un temps assez long pour en être sûr (certains calculs peuvent être très longs) ou que le programme indique qu'il s'est arrêté car il ne peut plus continuer à consommer autant. Si le programme boucle effectivement sans fin : vous avez dans votre code source une boucle répéter ou tant que dont la condition n'est jamais atteinte. Vérifiez que vous avez une instruction qui fait tendre la ou les variables d'arrêt vers le cas d'arrêt (par exemple, n'avez-vous pas oublié d'incrémenter le i ?).
Le programme ne donne pas les bons résultats (un « bogue »)	Vérifiez votre code source (oubli d'une instruction ?). Il est très peu probable que l'ordinateur fasse des erreurs de calculs donc si vous êtes sûr de votre code source : c'est peut-être votre algorithme qui est faux (retour à la case départ :(). Si votre algorithme est bon alors faites un déboguage.
Le programme donne des résultats complètement hors de propos (comme une opération sur deux chiffres donnant = 29876 ???)	Votre programme traite de trop grands nombres et vous avez dépassé les limites de Pascal.
erreur de segmentation (ou « segfault »)	arg :(
Vous n'avez touché à rien (promis) et pourtant ça fonctionnait tout-à-l'heure" (problème le plus courant : confirmé par nombre de professeurs...)	le problème ne vient pas de l'ordinateur qui, lui, n'est pas de mauvaise foi ;)

Le déboguage

Il existe des logiciels débogueurs dont c'est le rôle, cependant nous allons expliquer la démarche « manuelle » ici. Le déboguage manuel a pour but de déceler les bogues récalcitrants qu'on a cherchés pendant des heures en mettant à contribution les collègues. Il faut comprendre par là que ce doit être un (ultime) recours et non une pratique courante. Pédagogiquement, il est préférable, pour votre apprentissage, que vous trouviez l'erreur en raisonnant et en relisant attentivement votre code source ou en revérifiant votre algorithme.

Si vous décidez malgré tout de vous lancer dans ce processus fastidieux, pénible et coûteux en temps, si plus personne ne peut vous en dissuader, voici la situation et sa solution :

Vous avez donc relu votre code source 15 fois, revérifié votre algorithme 15 fois, demandé à vos collègues qui n'ont rien pu vous dire, même votre professeur a laissé tomber et pourtant il subsiste, le bogue. Introuvable, à la fois nulle part et partout. Si vous n'en dormez plus, voilà la solution.

Le déboguage (ou debugging) consiste à afficher ce que votre programme fait en arrière plan. Concrètement, cela revient à placer des « afficher » partout dans votre code. Chaque Affichage doit être unique, de sorte que dès que vous voyez une ligne en particulier vous devez pouvoir retrouver la ligne de code ayant produit cet affichage.

Exemple, considérons le programme suivant :

...
writeln('Donnez a');
readln(a);
writeln('Donnez b');
readln(b);
c:=a+b;
if c >= 100 then
  b:=4*c+15;
else
  b:=b*c+10;
c:=b-a;
writeln(c);
repeat
  readln(a);
  c:=c+a
until (a=0);
writeln(c);
...

Créons un autre fichier .pas contenant la version déboguage du code précédant :

...
writeln('Donnez a');
readln(a);
writeln('Donnez b');
readln(b);
writeln('on va faire c:=a+b avec a valant',a,' et b valant ', b);
c:=a+b;
writeln('on a maintenant c valant : ',c)
if c >= 100 then begin
  writeln('on est passé dans le cas c >= 100');
  b:=4*c+15;
  writeln('b vaut maintenant ',b);
  end;
else begin
  writeln('on est passé dans le cas c < 100');   
  b:=b*c+10;
  writeln('b vaut maintenant ',b);
end;
writeln('on est sorti du if c >= 100 ');
writeln('on a a,b,c qui valent ',a,b,c);
writeln('on fait c:=b-a');
c:=b-a;
writeln('c vaut maintenant ',c);
writeln('on l affiche ');
writeln(c);
writeln('on est avant le repeat');
repeat
  writeln('on est dans la boucle');
  readln(a);
  writeln('on fait c:=c+a avec a et c qui valent',a,c);
  c:=c+a
  writeln('c vaut maintenant ',c);
  writeln('fin de l interieur de boucle');
until (a=0);
writeln('on est sorti de la boucle');
writeln('on affiche c');
writeln(c);
...

L'idée étant que à chaque étape, vous pouvez vérifier que toutes les données sont valides. En suivant l'exécution avec ce qui s'affiche vous devriez voir à partir de quand l'erreur se produit.

Exemple complet

Dans cette partie, nous allons voir un cycle de programmation complet.

gedit

Comme environnement de travail, on a choisi de travailler sur le système d'exploitation Ubuntu pour PC. On utilisera gedit comme éditeur de texte et le compilateur Free Pascal car tous deux sont disponibles sur Ubuntu.

Nous allons implémenter l'algorithme suivant :

Algorithme inversion_calcul
Variables
  a : entier
  b : entier
Début
  Afficher("Donnez a")
  Lire(a)
  Afficher("Donnez b")
  Lire(b)
  a := a+b
  b := a-b
  a := a-b
  Afficher("a vaut ",a)
  Afficher("b vaut ",b)
Fin

Il s'agit de l'algorithme demandant deux nombres et les inversant avant de les afficher (inutile mais c'est un exemple). Traduisons-le :

program inversion_calcul;
Var
  a : integer;
  b : integer;
begin
  writeln('Donnez a');
  readln(a);
  writeln('Donnez b');
  readln(b);
  a := a+b;
  b := a-b;
  a := a-b;
  writeln('a vaut ',a);
  writeln('b vaut ',b);
end.

On recopie la traduction dans gedit, puis on enregistre dans un fichier inversion.pas :

notre code source dans gedit

Remarquez que gedit colorie le code de façon à le rendre plus lisible (on parle de coloration syntaxique).

Passons à la compilation : on a ouvert un terminal et taper la commande

fpc inversion.pas

capture d'écran d'un terminal dans lequel on a entré la commande fpc inversion.pas pour compiler notre code source inversion.pas

Le terminal affiche alors :

Free Pascal Compiler version 2.0.4 [2006/08/22] for i386
Copyright (c) 1993-2006 by Florian Klaempfl
Target OS: Linux for i386
Compiling inversion.pas
Linking inversion
15 Lines compiled, 0.0 sec

Les 15 lignes ont bien été compilées (ligne 6), le compilateur à créé un binaire inversion. Testons-le : dans le terminal, on donne la commande ./inversion pour lancer le programme.

Le programme se lance. Voici un test :

le programme nous demande, comme prévu, d'entrer a et b. Testons avec 21 et 39

On a entré nos deux nombres : notre programme va nous donner le résultat.

affichage du résultat : 39 et 21

Notre programme semble fonctionner. Les deux nombres ont bien été inversés. L'expérience est concluante, cependant, voyons ce qu'il se passe si on atteint les limites du codage des entiers.

Testons avec deux grands nombres :

le programme nous demande, comme prévu, d'entrer a et b. Testons avec 34567 et 5123

Le programme nous indique les résultats 5123 et -30969. Notre programme, comme tous les programmes a donc ses limites même si notre algorithme est bon.

Guide de traduction Pascal

Voici un guide de traduction d'un algorithme impératif en Pascal.

Le Squelette

Pour le squelette de l'algorithme :

Algorithme mon_algo

Constantes

Types

Variables

Début

Fin

On traduit ainsi :

program mon_programme;

Const

Type

Var

begin

end. (* notez ce point *)

Commentaires

Les commentaires notés

(* un commentaire *)

s'écrivent de la même façon

(* un commentaire *)

Types

Voici l'équivalence des types

type	Pascal
booléen	bool
entier	integer
réel	real
caractère	char
chaîne de caractères	string

• Les valeurs booléennes sont true et false.
• Les parties entière et décimale d'un réel sont séparées par un point et non une virgule.
• les chaînes sont déclarées entre deux apostrophes ' pour échapper un caractère on le double.

Exemple sur ce dernier point : pour inclure une apostrophe dans une chaîne,

writeln('l''apostrophe s''est échappée')

affiche

l'apostrophe s'est échappée

Constantes et variables

Les constantes et les variables ont des identifiants qui doivent respectées une syntaxe précise.

• l'identifiant ne peut comporter que des caractères alpha-numériques (de A à Z, de a à z et de 0 à 9) et des tirets-bas ou underscore : _.
• le premier caractère est une lettre.

les variables sont déclarées dans le Lexique du programme délimité par sa partie Var. Chaque déclaration est de la forme

identifiant : type;

Ainsi le lexique

Lexique
  un_reel : réel                     (* un réel quelconque *)
  une_chaine : chaîne de caractères  (* une chaîne quelconque *)

se traduit

Var
  un_reel : real;       (* un réel quelconque *)
  une_chaine : string;  (* une chaîne quelconque *)

Les accents ne sont généralement pas acceptés par les compilateurs Pascal.

Les identifiants des constantes respectent les mêmes règles. Par convention, on préférera les noter en majuscules. La déclaration d'une constante a pour syntaxe

 identifiant = valeur;

Ceci

Constantes
  PI = 3,14
  G = 9,81

s'écrit en pascal :

Const
  PI = 3.14;
  G = 9.81;

Instructions et blocs d'instructions

Pour exécuter une instruction (assignation, appel de fonction ou procédure) il suffit de l'écrire. Les paramètres sont précisés entre parenthèses et séparés par des virgules.

Les bloc d'instructions débutent par un begin et se terminent par un end. Les instructions du bloc sont séparées par des point-virgules. On gardera la convention algorithmique préférant une instruction par ligne.

Voici une ligne comportant une instruction unique :

une_instruction

Voici un bloc de k d'instructions :

begin
  instruction_1;
  instruction_2;
  (* ... *)
  instruction_k
end

Remarquez qu'aucun point-virgule ne ponctue la dernière instruction. En effet le ';' est un séparateur : il sépare les instructions entre elles. Il n'y a donc pas de point-virgule après la dernière instruction, pas plus qu'il n'y en a avant la première. Cela explique également pourquoi lorsqu'on écrit une seule instruction, elle n'est pas suivie d'un point-virgule.

Il est souvent affirmé à tort que « toutes les instructions se terminent par un point-virgule ». Ce n'est pas tout à fait vrai, comme nous venons de le voir. Cependant, cette croyance répandue a été prise en considération par les développeurs des compilateurs qui ignorent cette erreur.

Il convient de remarquer que le programme principal est un bloc d'instructions ponctué d'un point, ni plus ni moins.

Lecture et Écriture (affichage)

L'affichage s'effectue à l'aide de la procédure write. Elle peut prendre de un à plusieurs paramètres de n'importe quel type de base. Elle affiche tous les paramètres les uns après les autres (résultat identique à celui d'une concaténation).

Il existe une variante de write ayant la même spécification mais effectuant un retour à la ligne à la fin : il s'agit de la procédure writeln. On peut également appeler la procédure writln sans préciser de paramètres, cela effectue un retour à la ligne.

La lecture se fait à l'aide de la fonction read() qui prend en paramètre l'identifiant de la variable qui sera assignée.

readln est indentique à read() mais fait un retour à la ligne une fois la donnée lue.

Exemple

begin
  write('abc');
  write('def');
end

affiche

abcdef

alors que

begin
  writeln('abc');
  write('def');
end

affiche

abc
def

Assignation

L'assignation est une instruction et à ce titre elle doit respecter les règles sur les instructions (points-virgules...)

L'opérateur d'assignation est := (et non = qui est le test d'égalité)

La syntaxe de l'assignation est (espaces facultatifs) :

identifiant := expression

Il va sans dire que le type de l'expression doit être compatible avec celui de la variable assignée.

Exécution conditionnelle

On rappelle qu'une exécution conditionnelle est une instruction. Elle ne comporte pas de point-virgule sauf si elle est à l'intérieur d'un bloc. On suppose ici que l'instruction est au sein d'un bloc.

si condition alors instruction

donne

if condition then instruction;

S'il y a plusieurs instructions, on utilise un bloc :

if condition then begin
  instruction_1;
  instruction_2;
  instruction_k;
end;

Avec une instruction à exécuter quand la condition est fausse (sinon) :

si condition
  alors instruction_1
  sinon instruction_2

se traduit

if condtion
  then instruction_1
  else instruction_2;

De même on peut utiliser des blocs :

if condition then begin
  instruction_1;
  instruction_2;
  instruction_k;
end
else begin
  instruction_3;
  instruction_4;
  instruction_l;
end;

Structures itératives

Une boucle à compteur

POUR i de deb à fin faire instruction

donne

for i:=deb to fin do instruction;

On peut toujours utiliser un bloc comme instruction pour grouper plusieurs instructions à exécuter :

for i:=deb to fin do begin
  instruction_1;
  instruction_2;
  instruction_k;
end;

De même, une boucle répétée jusqu'à ce qu'une condition soit vraie (testée après chaque itération) :

repeat
  instruction
until condition;

et une boucle répétée tant qu'une condition est vraie (testée avant chaque itération) :

while condition do
  instruction
end;

Tableaux

lexique
  tab : tableau de deb à fin de T

donne :

var
  tab : array [deb..fin] of T;

Par exemple un tableau de 10 entiers, indicé de 1 à 10 :

var
  tab : array [1..10] of integer;

Le type enregistrement

type T = enregistrement
  champ : type_champ
fin

donne

type T = record
  champ : type;
end;

Exemple :

type WikilivreInfo = record
  titre : string;
  nombre_de_pages : integer;
  en_vitrine : boolean;
end;

Inverser deux variables

Problèmatique

Nous disposons de deux entiers a et b. Nous voulons intervertir ces deux nombres. À la fin du programme : la valeur de a sera égale à celle de b lors du lancement du programme et inversement : b sera égal au a initial.

Exemple : au début du programme nous posons a=2 et b=3. À la fin du programme nous aurons a=3 et b=2.

Solutions

Voici deux solutions acceptables :

Algorithme inversion_stockage
Variables
  a : entier
  b : entier
  temp : entier (* variable dans laquelle on stockera le contenu
                   d'une variable pour ne pas l'écraser au moment
                   de la première assignation *)
Début
  temp := a (* on sauvegarde a qui sera effacée à la ligne suivante
               pour pouvoir la placer dans b plus tard *)
  a := b
  b := temp
Fin

Algorithme inversion_calcul
Variables
  a : entier
  b : entier
Début
  a := a+b
  b := a-b
  a := a-b
Fin

Remarque

Ces deux solutions présentent en fait une notion clé de l'informatique : étudions nos deux solutions de plus près :

Simplifions le fonctionnement d'une machine au maximum : supposons

• Qu'il faut utiliser une unité de mémoire pour stoker une variable en mémoire
• Qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.

Temps de calcul requis par chaque algorithme :

• Pour inversion_stockage : 3 unités de temps (3 assignations)
• Pour inversion_calcul : 6 unités de temps (3 assignations + 1 somme + 2 différences)

Mémoire requise par chaque algorithme :

• Pour inversion_stockage : 3 unités de mémoire (a, b et temps)
• Pour inversion_calcul : 2 unités de mémoire (a et b)

On a donc que

• inversion_stockage prend plus de mémoire mais moins de temps de calcul que inversion_calcul
• inversion_calcul prend plus de temps de calcul mais moins de mémoire que inversion_stockage

Et c'est là un concept généralisable :

D'une façon générale, vous pouvez faire des algorithmes plus rapides en utilisant plus de mémoire et des algorithmes utilisant moins de ressources mémoire mais qui seront plus lents.

Attention cependant, cela ne veut surtout pas dire qu'aucun algorithme n'est améliorable sans perte de ressources en calcul ou en mémoire. Bien au contraire, vous devez toujours essayer d'être le plus efficace possible.

Ce constat ne permet pas de dire si un des algorithmes est plus efficace que l'autre : notre analyse a été trop simplifiée pour cela. En effet, nous n'avons pas considéré que :

• la mise en mémoire peut aussi prendre un temps non négligeable ;
• peut-être que les calculs de sommes et de différences sont très coûteux en temps ;
• peut-être que le processeur est assez avancé technologiquement pour effectuer un premier calcul et en commencer un deuxième avant d'avoir obtenu le premier résultat ;
• l'algorithme pourrait utiliser des réels, et, en général, les calculs sur les réels sont plus longs que sur les entiers.

Vous contesterez, avec raison, que sur cet exemple, aujourd'hui nos ordinateurs sont parfaitement capables d'exécuter ces deux programmes en un temps record et qu'on ne distinguera pas la différence suivant qu'on utilise l'un ou l'autre. C'est vrai, mais vous négligez que peut-être :

• ce programme sera exécuté sur une machine minuscule, une micro-puce de quelques millimètres dans laquelle on n'a pu mettre que très peu de mémoire et un minuscule processeur ;
• ce programme doit pouvoir être exécuté simultanément des milliers de fois sur la même machine ;
• ce programme ne sera pas exécuté plusieurs fois en même temps mais des milliers de fois, les unes après les autres, et que le programme ayant besoin d'inverser des milliers de valeurs à la suite doit pouvoir donner un résultat dans la seconde...

En réalité, n'importe quel compilateur décent, depuis les années 80, va optimiser bien au delà de ce que le programmeur moyen aura le courage de faire. Par exemple sur l'échange : utiliser deux registres au lieu d'une variable supplémentaire (R1 := A; R2 := B; A := R2; B:= R1) si les données tiennent dans un mot machine, ou utiliser les instructions spécialisées du processeur d'échange de deux zones en mémoire. En écrivant la forme la plus simple d'échange, le compilateur reconnaitra (parce qu'on lui a inculqué un certain nombre de recettes) de quoi il s'agit, et fabriquera le meilleur code possible. Le temps consacré à de la micro-optimisation est en général une perte sèche, il est de loin préférable de la consacrer à une bonne conception, et à l'utilisation d'algorithmes efficaces.

Un menu de sélection simple

Ce problème traite de la création d'une interface graphique rudimentaire dans un environnement textuel (un terminal).

Problématique

Nous supposons que nous avons déclaré 3 procédures dont les identifiants sont les suivants (peu nous importe ce qu'elles font : le sujet n'est pas ici)

• Procedure_A
• Procedure_B
• Procedure_C

Vous devez créer le programme principal permettant à l'utilisateur de choisir laquelle des trois il veut lancer. Le programme doit avoir les fonctionnalités suivantes :

• Une fois que la procédure choisie par l'utilisateur a été exécutée, le menu est de nouveau proposé.
• L'utilisateur doit pouvoir quitter le programme depuis le menu.
• Le programme doit expliquer à l'utilisateur comment utiliser le programme.
• (optionnel) on suppose que l'utilisateur est distrait et qu'il peut ne pas donner une bonne réponse. Gérez ce cas.

Première analyse

Voici quelques idées directrices formant une première analyse de la problématique. Chacun de ces points seront analysés dans la section suivante.

• ...permettant à l'utilisateur de choisir... : l'utilisateur doit intervenir. Il va falloir faire intervenir un Lire afin qu'il puisse nous donner son choix.
• ...laquelle des trois... :
• ...le menu est de nouveau proposé : il s'agit d'une répétition.
• ...quitter le programme depuis le menu : une autre possibilité. En fait, l'utilisateur aura le choix entre quatre possibilités : A, B, C ou quitter.
• ...expliquer à l'utilisateur comment utiliser le programme' : on affichera les instructions avec Afficher.

Analyse approfondie

Voici les réflexions qu'il faut mener sur les questions clés du problèmes.

Gérer le choix de l'utilisateur

Nous allons représenter le choix de l'utilisateur par un entier. Finalement, l'utilisateur à quatre possibilités pour le menu (entre parenthèse : l'entier que nous allons y associer) :

• Exécuter la procédure A (1)
• Exécuter la procédure B (2)
• Exécuter la procédure C (3)
• Quitter (0)

Nous allons donc lui poser la question "Que voulez vous faire ?", il répondra par un entier en fonction duquel on fera un SÉLECTIONNER.

(optionnel) l'utilisation d'une chaîne de caractères nous permettra de contrôler l'erreur si l'utilisateur entre autre chose que 1,2,3 ou 0. Si on utilise un entier et que l'utilisateur entre "truc" il va y avoir un problème (sur une machine, le programme se bloquera...).

L'utilisateur retrouve le menu

Pour que l'utilisateur retombe sur le menu, il va falloir utiliser une structure itérative, mais laquelle ? Petite réflexion :

1. À priori, on ne sait pas combien de fois l'utilisateur va exécuter une procédure. Cela exclut le POUR.
2. REPETER ou TANTQUE ? Le menu va s'afficher au moins une fois ce qui nous laisse penser qu'un REPETER est plus approprié. De plus la situation est bien décrite par la phrase "Afficher le menu jusqu'à ce qu'il choisisse de quitter", ce qui conforme notre choix. Nous utiliserons donc un REPETER.

Solution finale

Algorithme menu
(* on suppose que les procédures sont déclarées *)
Procedure_A ...
Procedure_B ...
Procedure_C ...
Variables
  reponse : chaîne de caractères (* entrée de l'utilisateur *)
Debut
  Répéter
    Afficher("Que voulez-vous faire ? Donnez l'entier correspondant")
    Afficher("1 : exécuter la procédure A")
    Afficher("2 : exécuter la procédure B")
    Afficher("3 : exécuter la procédure C")
    Afficher("0 : quitter")
    Lire(reponse)
    Sélectionner reponse parmi
      1 : Procedure_A()
      2 : Procedure_B()
      3 : Procedure_C()
      0 : (* on ne fait rien *)
      * : Afficher("Merci d'entrer un code valide")
  Jusqu'à (reponse='0')
Fin

Somme des n premiers entiers

Problématique

Écrire un algorithme sous forme d'une fonction qui calcule la somme des premiers entiers jusqu'à n inclus, n étant passé en paramètre.

Exemple : somme(5) calculera 1+2+3+4+5 et renverra donc 15

Solution

Voici une première réponse acceptable :

 Function somme(n : entier)
 Lexique
   somme : entier (* la somme qu'on complète au fur et à mesure et qu'on retournera à la fin *)
 Début
   somme:=0
   POUR i de 0 à n
     somme:=somme+i
   FP
   retourner somme
 Fin

Pourquoi partir de 0 et pas 1 ? Cela sert tout simplement à gérer le cas n=0. Cela ne change rien pour les autres cas puisque (en reprenant l'exemple de la problématique) somme(5) va calculer 0+1+2+3+4+5, c'est à dire 1+2+3+4+5 (=15).

Cependant, la boucle peut partir de 1 si elle ne s’exécute pas pour n=0. Dans ce cas, la somme sera 0 (valeur initiale de la variable somme).

Remarque

Essayons une analyse un peu plus mathématique du problème :

En fait notre fonction calcule pour n : $\sum _{i=0}^{n}i$. L'étude des séries nous apprend que

$\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$.

On peut en déduire que la fonction peut s'écrire

Function somme_directe(n : entier)
Début
  retourner (n*(n+1))/2
Fin

Ce qui d'une part est plus simple mais également, comme nous allons le voir, plus efficace.

Simplifions le fonctionnement d'une machine au maximum : supposons qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.

Supposons que nous voulions calculer somme(1000) : Avec somme() : nous allons effectuer :

• 1000 incrémentation de i
• 1000 sommes somme+i
• 1000 assignation

Soit au moins 3000 calculs.

Avec somme_directe() : nous allons effectuer

• une somme : n+1
• une multiplication n*(n+1)
• une division par 2

Soit 3 calculs.

Conclusion : 3000 calculs pour le premier algorithme, 3 calculs pour le second. La différence entre les deux : le mathématicien qui doit se retrouver en chaque algorithmicien.

Et dire que de nombreux étudiants en informatique sont souvent étonnés de la présence importante de mathématiques durant leur cursus...

(pour info : Wikilivres propose des cours de mathématiques...)

PGCD de deux nombres

Problématique

Écrire un algorithme donnant le Plus Grand Commun Diviseur (PGCD) de deux nombres donnés par l'utilisateur. On supposera que l'utilisateur ne donne que des entiers strictement supérieurs à zéro.

Il faudra écrire une fonction, prenant en entrée deux entiers strictement positifs et renvoyant leur PGCD. L'algorithme principal y fera appel.

Question subsidiaire : on considérera que l'utilisateur peut entrer n'importe quels entiers. Tenez-en compte pour que l'algorithme ne commette pas d'erreur et qu'il informe l'utilisateur.

Aide

Il faut avoir étudié ce problème d'algèbre pour avoir la solution. Elle consiste à appliquer l'algorithme d'Euclide.

Solution

Algorithme pgcd

Fonction euclide( u : entier
                   v : entier ) : entier
Variables
  r : entier (* le reste d'une division entière *)
Début
  Tant que v <> 0 faire
    r := u mod v
    u := v
    v := r
  FTQ
  retourner u
Fin

Variables
  u,v : entier (* les deux entiers donnés par l'utilisateur *)
Début
  Écrire("Donner les deux nombres : ")
  Lire(u,v)
  (* Début question subsidiaire *)
  si u=0 et v=0 alors Écrire("Le PGCD n'existe pas")
  sinon début
    si u < 0 alors u := -u
    si v < 0 alors v := -v
    (* Fin Question subsidiaire *)
    Écrire(euclide(u,v))
  fin
Fin

Pas vraiment de difficulté pour l'algorithme principal. La difficulté étant la fonction implémentant l'algorithme d'Euclide. Le jeu d'assignation à répéter jusqu'à obtenir un reste nul est difficile à visualiser.

Question subsidiaire : il y a trois événements à contrôler :

• Le cas où u=v=0 et où le PGCD n'existe pas et il faut arrêter le programme (ligne 22)
• Le cas où u ou v (ou les deux) est négatif est il faut prendre son opposé (lignes 24 et 25)

Pour la solution sans la question subsidiaire : ôter les lignes 21 à 26 et la 28 de la solution proposée.

Trier un tableau

Problématique

Voici un problème fondamental d'informatique.

Supposons qu'il soit déclaré tab, un tableau.

Pour écrire le programme on prendra la déclaration suivante

 var
   tab : tableau MIN à MAX de T

Pour simplifier le problème, vous pourrez considérer que T = entier.

Note : sachez toutefois que les opérateurs <, <=, >, >= sont génériques et permettent de comparer toutes données tant qu'elles font partie du même ensemble ordonné (Par exemple : l'alphabet).

Question subsidiaire : considérez le cas particulier où les éléments sont distincts. L'algorithme fonctionne-t-il ?

Solution

Il est tout d'abord important de savoir qu'il existe de nombreuses façon de procéder. Pour connaitre ces algorithmes de tri, élément important de la culture de tout algorithmicien, nous vous invitons à consulter l'article « Algorithme de tri » sur Wikipédia ainsi que les articles sur les différents algorithmes de tri existants.

Pour vous corriger : vérifiez que votre algorithme ne tombe pas sur une erreur courante en supposant que tous les entiers sont distincts. En effet, il est facile de faire un algorithme qui, voulant inverser deux éléments pour les remettre en ordre, boucle sans fin en voulant inverser sans fin : lorsqu'il tombe sur deux éléments égaux.

Une solution "simple"

Le tri par sélection est un des plus simples algorithmes de tri. Il consiste à rechercher le plus petit (ou le plus grand) élément du tableau et de le placer à sa place définitive : au début (ou à la fin du tableau). Une fois un tel élément placé à sa place définitive, on recommence avec le reste du tableau. Lorsqu'on place un élément, on n'écrase pas ce qui était là (on perdrait un élément du tableau) mais on le déplace à la position qu'on vient de libérer (ce qui revient à faire une permutation).

Une implémentation testable en Pascal

program tris;

const
	DEB = 0;
	FIN = 5;

type
	T_tabint = array [DEB..FIN] of integer;

procedure permuter(var i : integer; var j : integer);
(* à la fin, i vaut le j donné et j vaut le i donné *)
var
	tmp : integer; (* un tampon pour stocker l'élément que va remplacer l'élément minimum pendant l'inversion *)
begin
	tmp := i;
	i := j;
	j := tmp
end;

procedure afficher(var t : T_tabint);
(* procédure qui affiche le tableau passé en paramètre *)
(* sur une ligne et sous la forme [a|b|c|d...|l|m] *)

var
	i : integer; (* variable de boucle *)
begin
	write('[');
	for i := DEB to FIN-1 do write(t[i],'|');
	write (t[FIN],']');
end;

procedure remplir(var t : T_tabint);
(* procédure qui remplit le tableau passé en paramètre *)
(* avec des nombres aléatoires pris entre 0 et 99 *)

var
	i : integer; (* variable de boucle *)
begin
	for i := DEB to FIN do t[i] := random(99);
end;


procedure TriSelection(var t : T_tabint);
var
	i, j	: integer;	(* variables de boucle *)
	min		: integer;	(* indice du plus petit élément parmi ceux qui reste à trier *)
	
begin
   for i:=DEB to FIN-1 do begin
      min := i;
      for j:=i+1 to FIN do
         if (t[j] < t[min]) then min:=j;

      if (i <> min) then permuter(t[i],t[min]);
   end; 
end;

procedure TriBulle(var t: T_tabint);
var
	i, j	: integer;	(* variables de boucle *)
 
begin
  for i:=DEB to FIN-1 do begin
    j := i+1;
    for j := FIN-1 downto i do
    	if t[j+1]<t[j] then permuter(t[j],t[j+1]);
  end;
end;

var
	tab : T_tabint;

begin

	(* pour chaque tri on recrée un tableau aléatoire, on l'affiche *)
	(* puis on le trie et on l'affiche à nouveau *)

	(* Tri sélection *)
	writeln('TRI SELECTION');
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	TriSelection(tab);
	afficher(tab);
	writeln(' <- tableau trié');
		
	(* Tri bulle *)
	writeln('TRI BULLE');
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	TriBulle(tab);
	afficher(tab);
	writeln(' <- tableau trié');
	
end.

Voici un exemple d'exécution :

TRI SELECTION
[54|58|70|83|59|84] <- tableau donné
[54|58|59|70|83|84] <- tableau trié
TRI BULLE
[53|83|41|61|63|38] <- tableau donné
[38|41|53|61|63|83] <- tableau trié

Rechercher un élément dans un tableau

Problèmatique

Supposons que nous avons déclaré un tableau tab d'entiers comme suit :

Variables
  tab : tableau MIN à MAX de entiers

Supposons que ce tableau est rempli d'entiers inconnus mais triés dans l'ordre croissant.

Proposez un algorithme qui, étant donné un entier indiqué par l'utilisateur, trouve son indice dans le tableau. On supposera que l'entier indiqué par l'utilisateur est effectivement dans le tableau.

Aide

Vous remarquerez que ce problème s'apparente au problème de recherche d'un mot dans le dictionnaire. Pensez donc à la méthode que vous employez dans cette situation...

Solutions

Solutions moyennes

Voici une solution, qui n'est pas celle attendue. L'algorithme parcourt le tableau du début à la fin et compare l'élément à l'entier indiqué par l'utilisateur. Il s'arrête lorsqu'il est trouvé. Remarquez que la faiblesse de cette algorithme provient du fait qu'il fonctionne même quand le tableau n'est pas trié, il n'exploite donc pas cet avantage trop important pour être négligé.

Algorithme recherche
Variables
  q : entier (* l'entier recherché *)
  i : entier (* ce sera l'indice de parcours *)
Début
  Afficher("Donner l'entier à trouver")
  Lire(q)
  i ← MIN
  tantque tab[i] != q
    i ← i+1
  ftq
  Afficher("L'indice où se trouve ", q ," est ", i)
Fin

L'algorithme suivant fonctionne mais à le défaut de continuer à parcourir le tableau même quand l'élément a été trouvé.

Algorithme recherche_mauvais
Variables
  q : entier (* l'entier recherché *)
  i : entier (* ce sera l'indice de parcours pour la boucle *)
  résultat : entier (* l'indice résultat sera stocké ici *)
Début
  Afficher("Donner l'entier à trouver")
  Lire(q)
  i ← MIN
  pour i de MIN à MAX (* on parcourt tout le tableau *)
    si tab[i] = q alors résultat ← i (* si on a trouvé on mémorise l'indice *)
  ftq
  Afficher("L'indice où se trouve ", q ," est ", résultat)
Fin

Solution attendue

Voici enfin la solution attendue. Vous étiez peut-être arrivé à cette déduction seul ou en consultant l'aide mais vous avez compris que ce problème s'apparente à celui de la recherche dans un dictionnaire. En effet, on cherche un mot dans un ensemble de mots inconnus mais triés.

Si vous avez déjà cherché un mot dans le dictionnaire, vous avez certainement remarqué que lire le premier, regarder si c'est celui qu'on cherche, puis passer au suivant, et ainsi de suite n'est pas la solution la plus efficace...

La solution est donc l'algorithme de recherche dichotomique (du grec « dichotomie » : « couper en deux »). On ouvre le dictionnaire au milieu et un prend un mot au hasard, si le mot qu'on cherche est avant, recommence avec la première moitié du dictionnaire, s'il est après, avec la deuxième moitié. Dans la bonne moitié on prend un mot au milieu, etc...

Algorithme recherche_dichotomique
Variables
  q : entier         (* l'entier recherché *)
  i : entier         (* ce sera l'indice de parcours pour la boucle *)
  deb, fin : entiers (* deux entiers pour désigner le début et la fin de la zone dans laquelle on recherche *)
Début
  Afficher("Donner l'entier à trouver")
  Lire(q)
  (* on commence en recherchant dans tout le tableau *)
  deb ← MIN
  fin ← MAX
  répéter
    i = arrondir((fin+deb)/2) (* on prend i entre deb et fin *)
    si tab[i] > q
      alors fin ← i (* on est tombé trop haut : on ramène la borne supérieure *)
      sinon si tab[i] < q
              alors deb ← i (* on est tombé trop bas : on ramène la borne inférieure *)
  jusqu'à tab[i]=q
  Afficher("L'indice où se trouve ", q ," est ", i)
Fin

Traduction en Pascal

Voilà sa traduction en Pascal, le tableau étant rempli à la main :

program recherche_dichotomique;
Const
  MIN = 0;
  MAX = 10;
Var
  tab : array [MIN..MAX] of integer;
  q : integer;         (* l'entier recherché *)
  i : integer;         (* ce sera l'indice de parcours pour la boucle *)
  deb, fin : integer;  (* deux entiers pour désigner le début et la fin de la zone dans laquelle on recherche *)
Begin
  tab[0] := 1;
  tab[1] := 4;
  tab[2] := 9;
  tab[3] := 10;
  tab[4] := 24;
  tab[5] := 24;
  tab[6] := 74;
  tab[7] := 75;
  tab[8] := 76;
  tab[9] := 90;
  tab[10] := 99;
  Writeln('Donner l''entier à trouver : ');
  Readln(q);
  (* on commence en recherchant dans tout le tableau *)
  deb := MIN;
  fin := MAX;
  repeat
    i := round((fin+deb)/2); (* on prend i entre deb et fin *)
    if tab[i] > q
      then fin := i (* on est tombé trop haut : on ramène la borne supérieure *)
      else if tab[i] < q
              then deb := i; (* on est tombé trop bas : on ramène la borne inférieure *)
  until tab[i]=q;
  Writeln('L''indice où se trouve ', q ,' est ', i);
End.

Jeu du Tas de billes

Problématique

On cherche à implémenter un jeu dont voici les règles :

Règles du jeu :

• On commence avec un tas de billes, le jeu se joue à deux,
• Les joueurs jouent l'un après l'autre,
• Chaque joueur, à son tour, peut retirer une, deux, ou trois billes du tas,
• Le joueur qui prend la dernière bille a perdu.

En plus d'implémenter le mécanisme du jeu, on veillera à respecter les consignes suivantes :

• Au lancement, le programme rappelle les règles du jeu énoncées ci-dessus.
• Le contenu du tas de départ est demandé au lancement. Si le nombre donné est 0 ou moins, on prend un nombre aléatoire entre 10 et 30 et on l'annonce.
• Les deux joueurs entreront leurs noms en début de partie.
• À chaque tour, le programme rappelle à qui est le tour, en appelant les joueurs par leurs noms. Pour qu'on voie que le tour à passé, l'affichage est vidé des informations et saisies du tour précédent.
• À chaque tour, le programme rappelle combien il reste de billes dans le tas et donne une représentation graphique s'il reste moins de 30 billes (afficher sur une seule ligne un '.' par bille restante fera amplement l'affaire).
• Le programme gère les tentatives de triche et rappelle les règles si nécessaire.
• À la fin du jeu, le gagnant est désigné par son nom.

Solution

Trouver un algorithme pour ce jeu n'est pas aussi évident qu'il y parait.

Implémentation en Pascal

program billes;

var
	nb_billes :				integer;	(* le nombre de billes dans le tas *)
	coup :					integer;	(* nombre de billes à retirer lors d'un tour*)
	tour :					boolean;	(* vrai si c'est le tour du joueur 1 *)
	joueur1, joueur2 :		string;		(* noms des joueurs *)
	i :						integer;	(* variable de boucle *)

begin
	(* Affichage des règles *)
	writeln('Règles du jeu :');
	writeln('* On commence avec un tas de billes, le jeu se joue à deux.');
	writeln('* Les joueurs jouent l''un après l''autre.');
	writeln('* Chaque joueur, à son tour, peut retirer une, deux, ou trois billes du tas.');
	writeln('* Le joueur qui prend la dernière bille a perdu.');
	
	(* Recueil des informations nécessaires au jeu *)
	writeln('Donner le nom du joueur 1 : ');
	readln(joueur1);
	writeln('Donner le nom du joueur 2 : ');
	readln(joueur2);
	writeln('Donner le nombre de billes : ');
	readln(nb_billes);

	(* gestion du nombre de billes *)
	if (nb_billes <= 0) then begin
		nb_billes := 10+random(20);	(* random(n) renvoie un nombre entre 0 et n *)
		writeln('Un nombre aléatoire est pris : ',nb_billes);
	end;

	(* on démarre à false, ainsi c'est le joueur 1 qui jouera en premier *)
	tour := false;

	repeat
		(* nettoyer l'écran, un appel de clsrc() peut fonctionner également *)
		for i:=1 to 20 do writeln();

		(* on change le joueur à qui est le tour *)
		tour := not(tour);

		(* on indique à qui est le tour *)
		write('C''est au tour de ');
		if (tour) then writeln(joueur1) else writeln(joueur2);

		(* affichage (textuel et graphique) du nombre de billes restant *)
		writeln('Il reste ',nb_billes,' billes. ');
		if (nb_billes <= 30) then for i:= 1 to nb_billes do write('.');
		writeln();

		(* demande au joueur son coup , gestion de la triche *)
		writeln('Combien retirez-vous de billes ?');
		readln(coup);
		while ((coup < 1) or (coup > 3) or (coup > nb_billes)) do begin
			writeln('Tricheur !');
			writeln('* On ne peut retirer qu''entre une et trois billes.');
			writeln('* On ne peut plus de billes qu''il n''y en a.');
			writeln('Combien retirez-vous de billes ?');
			readln(coup)
		end;

		(* on a le coup voulu, on le joue *)
		nb_billes := nb_billes - coup

	until (nb_billes = 0);

	(* c'est le joueur qui a joué en dernier qui est perdant *)
	(* on inverse pour indiquer le gagnant *)
	if (not(tour)) then write(joueur1) else write(joueur2);
	writeln(' gagne !');

end.

Quiz

Problématique

On cherche à implémenter un programme qui, étant donnée une base de données de questions et de réponses correspondantes posent les questions et demande la réponse à un joueur. Le programme comptabilise les bonnes réponses et donne le score final. Le nombre de questions à poser est demandé au début de la partie, si le nombre donné est nul ou négatif, on choisit un nombre aléatoire entre un et le nombre de questions dans la base de données.

Les réponses seront soit

• vrai/faux
• une réponse en toutes lettres
• une réponse sous forme de nombre

Il est demandé d'implémenter seulement une de ces trois possibilités.

• À chaque question, le score actuel et le nombre de questions restantes est affiché
• On ne demande pas que le programme ne pose pas deux fois la même question au cours d'une même partie, réfléchir tout de même à un moyen de faire cela.

Données

questions : tableau de 0 à NBQ de chaine; (* bases de données des questions *)
réponses : tableau de 0 à NBQ de T (* bases de données des réponses *)

On suppose ces tableaux remplis, bien évidement la réponse à la question questions[i] est réponses[i]. T est booléen, integer, ou chaine : à vous de choisir et d'assumer ce choix dans l'algorithme.

Solution

Implémentation en Pascal

L'auteur vous demande de l'excuser pour la piètre qualité du contenu de la base de données...

program quiz;

const
	NBQ = 4; (* nombre de questions dans la base de données *)

var
	questions :       array [1..NBQ] of string; (* bases de données des questions *)
	reponses :        array [1..NBQ] of boolean; (* bases de données des réponses *)
	nb_questions :    integer; (* le nombre de questions à poser *)
	numero_question : integer; (* l'indice d'une question dans la BdD *)
	i :               integer; (* variable de boucle *)
	reponse :         char; (* entrée clavier *)
	r :               boolean; (* l'interprétation booléenne de l'entrée au clavier; *)
        rep_valide :      boolean; (* réponse entrée valide *)
	score :           integer; (* le score de joueur *)

begin

	(* remplissage de la base de données des questions *)
	questions[1] := 'La réponse est 42';
	questions[2] := 'faux et (vrai et (faux ou vrai))';
	questions[3] := 'L''algorithmique impérative c''est cool';
	questions[4] := 'si six scies scient six cyprès six-cent scies scient six-cent cyprès';

	(* remplissage de la base de données des réponses *)
	reponses[1] := true;
	reponses[2] := false;
	reponses[3] := true;
	reponses[4] := true;

	(* demande et gestion du nombre de questions *)
	Writeln('Donner le nombre de questions voulues pour ce quiz :');
	readln(nb_questions);
	if nb_questions <= 0 then nb_questions := random(NBQ)+1;

	(* initialisations *)
	score := 0;

	for i:=nb_questions downto 1 do begin

		(* Information du joueur : nombre de questions restantes et score *)
		Writeln('Il reste ',i, ' questions | SCORE : ', score);

		(* on choisit une question au hasard dans le BdD et on l'affiche *)
		numero_question := 1+random(NBQ);
		writeln(questions[numero_question]);

		(* on lit la réponse et on essaie de la comprendre *)
		(* si on ne la comprend pas, on passe à la question suivante. Tant pis pour le score *)
		readln(reponse);
		rep_valide := true;
		case reponse of
			'o' : r := true;
			'O' : r := true;
			'v' : r := true;
			'V' : r := true;
			'n' : r := false;
			'N' : r := false;
			'f' : r := false;
			'F' : r := false;
			else rep_valide := false;
		end;

		if rep_valide then begin
		(* on a la réponse du joueur, gestion du score et de l'affichage en fonction de la réponse BdD *)
			if r = reponses[numero_question] then begin 
				score := score+1;
				writeln('Bonne réponse \o/');
				end
			else begin
				writeln('Mauvaise réponse :(');
			end;
		else begin
			writeln('je n''ai pas compris la réponse : entrer o(ui), v(rai), f(aux) ou n(on)');
		end;
	end;

	(* informations finales *)
	Writeln('Score final : ', score)
end.

Solutions d'un polynômes

Problématique

On souhaite réaliser un programme qui donne les solutions d'un polynôme dont les coefficients sont donnés par l'utilisateur. On peut aborder le problème selon des difficultés croissantes :

1. Résoudre dans ℝ les polynômes du premier degré
2. Résoudre dans ℝ les polynômes du second degré
3. Résoudre dans ℂ les polynômes du second degré

Écarts entre les éléments d'un tableau

Problématique

Donner un algorithme qui, étant donné un tableau d'entiers, trouve le plus petit écart entre deux éléments.

Exemples :

• [1|10|4|6] : 6-4 = 2
• [1|10] : 10-1 = 9
• [5|5] : 5-5 = 0

Donner un algorithme qui, étant donné un tableau d'entiers, trouve le plus grand écart entre deux éléments.

Solution

Une implémentation testable en Pascal

program ecarts;

const
	DEB = 0;
	FIN = 10;

type
	T_tabint = array [DEB..FIN] of integer;

procedure afficher(var t : T_tabint);
(* procédure qui affiche le tableau passé en paramètre *)
(* sur une ligne et sous la forme [a|b|c|d...|l|m] *)

var
	i : integer; (* variable de boucle *)
begin
	write('[');
	for i := DEB to FIN-1 do write(t[i],'|');
	write (t[FIN],']');
end;

procedure remplir(var t : T_tabint);
(* procédure qui remplit le tableau passé en paramètre *)
(* avec des nombres aléatoires pris entre 0 et 99 *)

var
	i : integer; (* variable de boucle *)
begin
	for i := DEB to FIN do t[i] := random(99);
end;

procedure RechercheEcartMin(t : T_tabint);
var
	i,j : integer; (* variables de boucle *)
	ind1,ind2 : integer; (* indices *)
	ecart_min_trouve : integer;
	
begin
	ecart_min_trouve := MAXINT;
	for i := DEB to FIN-2 do begin
		for j:= i+1 to FIN do begin
			if (abs(t[i]-t[j]) <= ecart_min_trouve) then begin
				ecart_min_trouve := abs(t[i]-t[j]);
				ind1 := i;
				ind2 := j;
			end;			
		end;
	end;
	writeln('écart minimal trouvé : ',t[ind1],' - ',t[ind2],' = ',ecart_min_trouve)
end;

procedure RechercheEcartMax(t : T_tabint);
var
	i : integer; (* variable de boucle *)
	min,max : integer; (* indices du plus petit élément et du plus grand élément *)

begin
	min := DEB;
	max := DEB;
	for i:= DEB to FIN do begin
		if t[i] < t[min] then min := i;
		if t[i] > t[max] then max := i;
	end;
	writeln('écart maximal trouvé : ',t[max],' - ',t[min],' = ',t[max]-t[min])
end;

var
	tab : T_tabint;

begin
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	RechercheEcartMin(tab);
	RechercheEcartMax(tab);	
end.

Exemple de résultat produit par le programme :

[54|58|70|83|59|84] <- tableau donné
écart minimal trouvé : 83 - 84 = 1
écart maximal trouvé : 84 - 54 = 30

L'algorithmique impérative, et après ? perspective sur la suite des évènements...

Cette partie introduit un ensemble de sujets d'ouverture possibles pour la poursuite de l'apprentissage.

Algorithmique

Comme nous l'avons vu, notamment sur le problème du tri des tableaux, il existe de multiples algorithmes connus dont l'étude est intéressante pour la culture de l'algorithmicien.

C'est l'objet du wikilivre Programmation Algorithmique.

Calculabilité et complexité

Vous allez sûrement vous poser cette question un jour : Peut-on écrire un algorithme qui... ?. Grande question, nos ordinateurs d'aujourd'hui dérivent de la Machine de Turing. Toute une branche des mathématiques est dédiée au problème de la Calculabilité.

Au fil des remarques dans les problèmes posés,nous avons abordé la notion d'efficacité d'un algorithme. Notamment dans le problème sur la somme des n premiers entiers où nous avons clairement constaté qu'il existait deux façons d'obtenir un résultat : l'une prenant beaucoup plus de ressources (en temps et en mémoire) que l'autre. Eh bien ce concept est formalisé : il est possible d'évaluer grâce aux mathématiques si un algorithme est plus efficace qu'un autre. Il s'agit de la complexité

Finalement, il s'agit de répondre à deux questions : peut-on obtenir un résultat en un temps fini (calculabilité) ? et si oui, dans quel ordre de grandeur de temps (complexité) ?

Algorithmique fonctionnelle

Nous avons étudié l'algorithmique impérative : cette précision est effectivement nécessaire. Une autre algorithmique existe. Elle pose d'autres bases de départ, d'autres concepts. Elle est plus complexe à apprendre et à comprendre que l'algorithmique impérative mais la puissance de ses axiomes permet d'éviter de nombreux problèmes.

Cet exemple exploite le concept de la récursion, fondamental dans cette algorithmique.

Algorithme itératif (impératif)	Algorithme récursif (fonctionnel)
Fonction factorielle(n : entier) Lexique i  : entier (* variable de boucle *) résultat : entier (* le résultat final qu'on retournera *) Début si i=0 alors résultat←1 sinon début résultat←1 (* on initialise le résultat *) pour i de 2 à n résultat←résultat*i finpour fin finsi Fin	Fonction factorielle(n : entier) Début si n<=1 alors 1 sinon n*factorielle(n-1) Fin

C'est un bon complément et une bonne suite à l'apprentissage de l'algorithmique impérative.

Structures de données

Nous n'avons jusqu'ici utilisé qu'une structure de données, le tableau. Cette structure de données pose un problème : elle occupe la mémoire en fonction de sa déclaration. Ce qui signifie que si on ignore combien l'utilisateur va nécessiter d'indice, il va falloir réserver le tableau le plus grand possible afin d'être sûr qu'il puisse contenir autant d'éléments que l'utilisateur souhaitera. Il serait plus judicieux de réserver l'espace au fur et à mesure de la demande. C'est ce que l'on appelle le gestion dynamique de la mémoire (par opposition à statique).

Nous avons également vu qu'un tableau est générique : c'est-à-dire qu'au moment de sa déclaration, nous pouvons dire que tous ses éléments sont d'un type donné et choisir ce type.

Nous avons vu que les tableaux sont homogènes : c'est-à-dire qu'un tableau donné ne peut contenir qu'un seul type d'élément (celui précisé dans la déclaration du tableau). Nous pourrions avoir besoin d'un tableau dont certains éléments seraient des entiers, d'autres des chaînes, d'autres encore des booléens. Il s'agit là de la problématique de l'hétérogénéité.

Note : attention à ne pas confondre la notion de généricité avec celle d'hétérogénéité. La première désigne la capacité à contenir des éléments d'un même type que l'on peut choisir en le fixant au moment de la déclaration. La seconde désigne la capacité à contenir des éléments de types différents.

Supposons maintenant que nous devions utiliser des formes d'information qui ne font pas partie de type de bases : les listes, les matrices, les rationnels, les arbres, l'ADN, la couleur, etc. Comment créer les éléments nécessaires au stockage de telle information quand un simple tableau ou un simple enregistrement ne suffisent plus ?

Dynamicité, généricité, hétérogénéité et la création de nouveau types non-élémentaires sont autant de problèmes traités dans le wikilivre Structures de données.

Théorie des langages

La langage algorithmique est composé de règles de syntaxe bien précises dont la raison peut paraître obscure. Les langages de programmation ont également de nombreuses règles d'écriture. Qu'est ce qui détermine qu'un langage peut être compris par un ordinateur ? Pourquoi ne peut-on pas tout simplement écrire nos algorithmes en français littéral ?

C'est l'objet de la théorie des langages.

Architecture des ordinateurs

Nos algorithmes sont implémentés dans un langage informatique puis compilés pour être transformés en un fichier binaire exécutable. Pourquoi le binaire ? Comment l'ordinateur peut-il simplement avec l'électricité stocker des données et effectuer des opération sur celles-ci ? Que fait exactement le compilateur ? Pourquoi un binaire compilé pour Linux ne fonctionne pas sous Windows ?

Une infinité de questions peut se poser sur le fonctionnement de l'ordinateur au-delà de l'écran. Il s'agit de l'Architecture des ordinateurs

Correction des algorithmes

De la même façon que pour la calculabilité et la complexité, une branche des mathématiques permet de prouver qu'un algorithme fonctionne. Il s'agit de la logique de Hoare

Conclusion

Il existe une multitude de domaines d'extension et de connaissances qui touchent à l'informatique en plus de l'algorithmique impérative. La plupart sont liées aux mathématiques. Chacune de ces matières suscitera plus ou moins votre curiosité...

Ressources externes : bibliographie, liens...

Bibliographie

• (français) Daniel Canevet - L'algorithmique et le Pascal - Collection Informatique et communication, Éditions Paris : Delagrave - 1992 - 95 pages -  (ISBN 2-206-00698-7)
• (français) Claude Delannoy - Initiation à la programmation - Éditions Eyrolles - 1997 - 192 pages -  (ISBN 2-212-08983-X)

Wikilivres

• Programmation Pascal

Sur la Wikiversité

• Introduction générale à la programmation. Certaines notions exposées dans ce module dépassent le cadre du présent ouvrage.
• Algorithmique
• Langage Pascal

Sur Wikipédia

• le langage Pascal

Liens externes

• Le projet Euler propose une collection de problèmes mathématiques à résoudre à l'aide de l'informatique et notamment de l'algorithmique impérative. Attention, il s'agit là de problèmes bien plus difficiles que ceux qui ont été abordés ici. Le site étant de surcroît en anglais, il est donc à réserver aux courageux.
• Pascal sur developpez.com
• France-IOI : site francophone sur les Olympiades Internationales d'Informatique