Algorithmique impérative/Version imprimable
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
Avant-propos
modifierIntroduction
modifier« Les ordinateurs sont inutiles, ils ne savent que donner des réponses. » (Pablo Picasso).
À qui s'adresse ce livre ?
modifierCe 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
modifierSelon 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
modifierL'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 :
- Une partie théorique qui présente les divers aspects de l'algorithmique impérative et la façon de les exploiter.
- Une partie sur les outils de travail de l'algorithmicien.
- Des problématiques concrètes, une analyse simple puis approfondie du problème et de ses solutions.
Petit historique
modifierComme 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
modifierPremière approche
modifierOn 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
modifierTout 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
modifier
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
modifierUn 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
modifierChaque 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
modifierVoici 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
modifierUn 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
modifierEn 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
modifierEn 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.
- L'information cardinal de E est une information qui peut être représentée par un entier (ici 4).
- L'information b appartient à E est une information qui peut être représentée par un booléen (ici VRAI).
- L'information e appartient à E est une information qui peut être représentée par un booléen (ici FAUX).
- 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.
- L'information nombre de personnes dans l'ascenseur peut être représentée par un entier.
- L'information il y a au moins une personne dans l'ascenseur peut être représentée par un booléen.
- L'information l'ascenseur est au premier étage peut être représentée par un booléen.
- 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
modifierAu 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() 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.
|
|
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
|
|
Vous en serez déjà arrivé à ces conclusions : si b est un booléen,
b et FAUX
vautFAUX
quel que soitb
b ou VRAI
vautVRAI
quel que soitb
Ces opérateurs peuvent bien sûr former des expressions. Quelques exemples :
non(non(FAUX))
vaut FAUX((VRAI et FAUX) ou VRAI)
vautVRAI
La négation est prioritaire sur la conjonction. La conjonction est prioritaire sur la disjonction.
Tableau récapitulatif
modifierType | 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
modifierCe 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
modifier
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
modifierToutes 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
modifierVariables 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
modifierDe 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
modifierÀ 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
modifier
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
modifierVoici expliquées deux instructions que l'on retrouvera très fréquemment dans des algorithmes. Il s'agit des instructions Afficher
et Lire
.
Afficher
modifierAfficher
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
modifierLa 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
modifierSouvent, 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
modifier
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
modifierAu 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é :
par soustraction de x dans les deux membres :
donc
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
modifier
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...
modifierL'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
. Sicondition
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
modifierSI 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
modifierIl 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
modifierSI condition ALORS Afficher("La condition vaut VRAI") SINON Afficher("La condition vaut FAUX") FINSI
Une équivalence utile
modifierRemarquez 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
modifier
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
modifierLa 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 :
i
est affecté à la valeur dedeb
(i←deb
)- si
i
est différent defin
alors on exécuteinstruction
- incrémenter
i
(i←i+1
) - revenir au point 2
Il est évident que pour que le programme fonctionne deb
<fin
.
Exemples
modifierDix itérations
modifierLexique 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
modifierTANTQUE condition instruction FINTANTQUE
condition
est une expression booléenne, comme dans la structure SI condition ALORS...
Cette structure est exécutée comme suit :
- si
condition
est vraie : exécuterinstruction
sinon, continuer aprèsFINTANTQUE
- reprendre au point 1
La boucle infinie
modifierIl est possible grâce à cette structure de créer une boucle infinie :
TANTQUE VRAI instruction FTQ
Une boucle POUR
modifierIl est possible de simuler une boucle POUR
à l'aide d'un TANTQUE
i←deb TANTQUE i <= fin instruction i←i+1 FTQ
Exemples
modifierStructure REPETER
modifierREPETER instruction JUSQU'A condition
condition
est une expression booléenne.
Cette structure s'exécute comme suit :
- exécuter
instruction
- si
condition
est vrai : continuer au point 3 sinon, reprendre au point 1 - exécuter ce qui suit le
JUSQU'A
La boucle infinie
modifierIl est possible grâce à cette structure de créer une boucle infinie :
REPETER instruction JUSQU'A FAUX
Une boucle POUR
modifierIl est possible de simuler une boucle POUR
à l'aide d'un REPETER
i←deb REPETER instuction i←i+1 JUSQU'A i=fin
Exemples
modifierComment déterminer la structure à utiliser ?
modifierLe 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
modifierPremière approche
modifierLe 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
modifierLes 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
modifierLa 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
modifierPremière approche
modifierLes 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 ?
modifierUne 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
modifierPremière approche
modifierL'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
modifierOn 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
modifierSupposons 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
modifierCela 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
modifierPour 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
modifierAu final, l'algorithme se compose de la façon suivante :
Algorithme
suivi du nom de l'algorithme- De la déclaration des procédures et des fonctions
- De la déclaration des constantes de l'algorithme principal
- De la déclaration des variables de l'algorithme principal
- 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
modifierTypes, expressions et opérateurs
modifierQuestions théoriques
modifier- Citez des exemples de types
- Donnez un opérateur polymorphe
- Écrire un programme qui saisit trois nombres dans un ordre donné et les fait sortir dans l'ordre inverse d'entrée.
Solutions :
- booléen, entier, réel, caractère, chaîne de caractères
- + (polymorphe car fonctionne avec des entiers et des réels)
Types et valeurs
modifierDonner le type des expressions suivantes et leur valeur
- 0
- 1+2
- 0.0+1.0
- "a"
- "a"."b"="b"
- "a"."b"
Donner le type de a et de l'expression :
- a+1
- a."b"
- a=1.0
Solutions
modifier- entier : 0
- entier : 3
- réel : 1.0
- caractère : "a"
- booléen : FAUX
- chaîne de caractères : "ab"
Questions avec la variable a :
- entier ; a entier
- chaîne de caractères : a caractère ou chaîne de caractères
- booléen : a réel
Calcul booléen
modifierQuelle est la valeur de ces expressions booléennes ?
- non(VRAI)
- VRAI et FAUX
- FAUX ou FAUX
- VRAI et VRAI
- non(FAUX ou VRAI)
- FAUX et ((VRAI et VRAI) ou (VRAI et (FAUX ou (VRAI et FAUX)))))
- VRAI ou (VRAI et (FAUX ou ((FAUX et VRAI) ou VRAI)))
a
et b
sont des booléens, simplifier les expressions :
- non(non(a))
- non(non(non(b)))
- faux ou a
- faux et a
- vrai et a
- vrai ou a
- a et non(a)
- a ou non(a)
- non(a=b) et (a=b)
Solutions
modifier- FAUX
- FAUX
- FAUX
- VRAI
- FAUX
- 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. - 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 - ...
Simplifications :
- a
- non(b)
- a
- faux
- a
- vrai
- faux
- vrai
- faux
Condition
modifierDonner un extrait d'algorithme équivalent à celui-ci sans utiliser de sinon
:
si condition alors instruction1 sinon instruction2
Solution
modifiersi condition alors instruction1 finsi si non(condition) alors instruction2 finsi
Boucles
modifier13 à 47
modifierDonner une boucle qui affiche les entiers de 13 à 47
Solution:
Pour i de 13 à 37 Afficher(i) FP
de 5 en 5
modifierDonner 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
modifierSelon la déclaration suivante
tab : tableau 0 à 10 de T
Le tableau contient 11 éléments.
Procédures et fonctions
modifierÉcrire des fonctions en procédures, des procédures en fonctions.
La rédaction d'un algorithme
modifierLorsqu'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
modifierL'indentation d'une ligne est l'espace qui la sépare de la marge gauche.
Problème
modifierConsidé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
modifierPour 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
modifierPour 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
etcalculer_nb
,quotient
etdivision
...)
É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
oux
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
modifierIl 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
modifier« 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
modifierPrérequis cognitif
modifier- 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
modifierUn é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
modifierUn 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
modifierUn 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
modifierPetit 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
modifierSi 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 ?
modifierVous 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 :
- 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.
- Recopier la traduction (le code source) dans un éditeur de texte.
- 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
modifierPascal 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
modifierÉ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
modifierLà 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 ?
modifierVoici 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
modifierIl 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
modifierDans cette partie, nous allons voir un cycle de programmation complet.
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
:
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
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 :
On a entré nos deux nombres : notre programme va nous donner le résultat.
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 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
modifierVoici un guide de traduction d'un algorithme impératif en Pascal.
Le Squelette
modifierPour 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
modifierLes commentaires notés
(* un commentaire *)
s'écrivent de la même façon
(* un commentaire *)
Types
modifierVoici 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
etfalse
. - 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
modifierLes 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
modifierPour 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)
modifierL'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
modifierL'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
modifierOn 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
modifierUne 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
modifierlexique 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;
Procédures et fonctions
modifierLe type enregistrement
modifiertype 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
modifierProblèmatique
modifierNous 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
modifierVoici 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
modifierCes 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 queinversion_calcul
inversion_calcul
prend plus de temps de calcul mais moins de mémoire queinversion_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
modifierCe problème traite de la création d'une interface graphique rudimentaire dans un environnement textuel (un terminal).
Problématique
modifierNous 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
modifierVoici 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
ouquitter
. - ...expliquer à l'utilisateur comment utiliser le programme' : on affichera les instructions avec
Afficher
.
Analyse approfondie
modifierVoici les réflexions qu'il faut mener sur les questions clés du problèmes.
Gérer le choix de l'utilisateur
modifierNous 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
modifierPour que l'utilisateur retombe sur le menu, il va falloir utiliser une structure itérative, mais laquelle ? Petite réflexion :
- À priori, on ne sait pas combien de fois l'utilisateur va exécuter une procédure. Cela exclut le POUR.
- 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
modifierAlgorithme 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
modifierProblématique
modifierÉ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
modifierVoici 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
modifierEssayons une analyse un peu plus mathématique du problème :
En fait notre fonction calcule pour n : . L'étude des séries nous apprend que
.
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
modifierProblématique
modifierÉ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
modifierIl faut avoir étudié ce problème d'algèbre pour avoir la solution. Elle consiste à appliquer l'algorithme d'Euclide.
Solution
modifierAlgorithme 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
modifierProblématique
modifierVoici 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
modifierIl 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"
modifierLe 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
modifierprogram 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
modifierProblèmatique
modifierSupposons 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
modifierVous 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
modifierSolutions moyennes
modifierVoici 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
modifierVoici 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
modifierVoilà 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
modifierProblématique
modifierOn 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.
Première analyse
modifierAnalyse approfondie
modifierSolution
modifierTrouver un algorithme pour ce jeu n'est pas aussi évident qu'il y parait.
Implémentation en Pascal
modifierprogram 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
modifierProblématique
modifierOn 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
modifierquestions : 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
modifierImplémentation en Pascal
modifierL'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
modifierProblématique
modifierOn 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 :
- Résoudre dans ℝ les polynômes du premier degré
- Résoudre dans ℝ les polynômes du second degré
- Résoudre dans ℂ les polynômes du second degré
Écarts entre les éléments d'un tableau
modifierProblématique
modifierDonner 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
modifierUne implémentation testable en Pascal
modifierprogram 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...
modifierCette partie introduit un ensemble de sujets d'ouverture possibles pour la poursuite de l'apprentissage.
Algorithmique
modifierComme 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é
modifierVous 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
modifierNous 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
modifierNous 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
modifierLa 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
modifierNos 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
modifierDe 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
modifierIl 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...
modifierBibliographie
modifier- (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
modifierSur la Wikiversité
modifier- 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
modifierLiens externes
modifier- 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