Support du cours d’Algorithmique débutant

Support de cours pratique et détaillé avec exemples en PDF pour s’introduire à l’algorithmique, formation avancé pour tous les niveaux à télécharger.

 

1     Introduction

Ce cours présente des concepts communs aux divers langages de programmation utilisés en calcul scientifique et des conseils généraux de programmation.

Par ailleurs, le cours introduit l'écriture d'algorithmes pour préparer l'écriture d'un programme. L'algorithme est une suite finie, séquentielle, de règles que l'on applique à  un nombre fini de données, pour résoudre un problème.

L'algorithme se place à  un niveau logique, plus ou moins précis, repoussant les problèmes ou les détails techniques du langage de programmation. Voici un exemple : l'algorithme d'Euclide, qui permet de trouver le plus grand commun diviseur de deux nombres entiers.

Exemple : algorithme d'Euclide

L'algorithme peut être spécifié comme ci-dessus à  l'aide de symboles graphiques ou sous forme purement textuelle. Voici par exemple le même algorithme d'Euclide sous forme purement textuelle.

Ce cours : langage textuel de description d'algorithme (-œpseudocode-)

entrer (a, b)

{a et b 2 entiers naturels non nuls et a > b} r = reste de la division de a par b tant que r 6= 0 faire a = b b = r

r = reste de la division de a par b

fin tant que

écrire (b)

On trouve aussi l'appellation pseudo-code pour ce langage textuel de description d'algorithme.

Idéalement, on apprécierait que l'algorithme soit indépendant du langage de programmation visé : un même algorithme pourrait être -œtraduit- en divers langages de programmation. En pratique, en écrivant un algorithme, on a en ligne de mire un langage de programmation particulier. Notamment parce que l'on doit réfléchir pour l'algorithme aux structures de données qui vont être manipulées, et que les structures de données disponibles dépendent du langage de programmation.

2     Concepts de base des langages de programmation impératifs

Les langages de programmation classiquement utilisés en calcul scientifique (par exemple Fortran, C++, Python) sont dits -œimpératifs-. Dans un tel langage, un programme est une suite d'instructions, dans un ordre bien défini, qui modifient -œl'état de la mémoire-. La mémoire est essentiellement un ensemble de -œvariables-, qui contiennent des valeurs, en général des nombres ou du texte. On peut imaginer les variables comme des cases portant des noms. Le programme lit ou modifie les valeurs contenues dans ces cases. Lorsqu'un programme impératif est exécuté, la mémoire passe donc par une suite finie d'états. Cf. figures (1) et (2).

Figure 1 -“ à‰tat de la mémoire.

Définitions

-” Type d'une variable : type de la valeur qu'elle contient. Exemples : nombre entier, ou texte. Le type détermine les opérations possibles sur la variable. Exemple : + - à— / pour les entiers.

-” Constante littérale : une valeur, écrite littéralement. Exemple : 2,718282.

-” Constante symbolique : un nom donné à  une valeur littérale. Exemple : e pour la base des logarithmes népériens. Non modifiable par le programme.

-” Expression : combinaison d'opérations appliquées à  des variables ou des constantes.

-” Procédure : suite d'instructions à  laquelle on donne un nom.

Typage statique, déclarations. Dans certains langages de programmation, le type d'une variable donnée est fixé à  l'écriture du programme. On dit que le typage est statique dans ce langage de programmation. Par exemple, les langages Fortran, C et C++ sont à  typage statique. Le type d'une variable est alors fixé dans une ligne particulière du programme qu'on appelle une ligne de -œdéclaration-. En plus des déclarations de types des variables, on peut aussi trouver des déclarations qui définissent de nouveaux types (ne pas confondre la définition d'un nouveau type et la déclaration d'une nouvelle variable avec un type

exécution du programme

Figure 2 -“ Exécution d'un programme. La mémoire de la machine passe par une suite finie d'états.

pré-existant) et des déclarations de constantes symboliques. Les lignes de déclarations ne modifient pas l'état de la mémoire, elles définissent ou caractérisent des objets que le programme manipule.

Typage dynamique Dans d'autres langages de programmation, une variable de nom donné peut voir son type changer en cours d'exécution. Le type de la variable est déterminé par la valeur affectée à  cette variable. On dit que le typage est dynamique dans ce langage de programmation. Le langage Python par exemple est à  typage dynamique.

Types entier et réel. Les langages de programmation scientifique permettent d'utiliser des valeurs de type entier ou de type réel (entre autres types). La distinction entre entiers et réels n'est pas la même en informatique qu'en mathématiques. Mathématiquement, si un nombre est entier, il est aussi réel, tandis que, informatiquement, une valeur est ou bien entière ou bien réelle. Chaque langage offre donc une possibilité de distinguer une valeur entière d'une valeur réelle. Par exemple, dans les langages scientifiques classiques, les écritures 2 et 2. (avec un point) distinguent la valeur 2 considérée comme entière ou réelle. En outre, pour les langages à  typage statique, la déclaration d'une variable distingue le type entier et le type réel. Une valeur entière n'est pas traitée comme une valeur réelle. La différence est dans le -œcodage- de la valeur. Le codage est la représentation d'un nombre dans la mémoire de l'ordinateur. Les nombres sont représentés par leur développement en base 2. Le développement est exact pour les nombres entiers. Pour les nombres réels, le codage inclut une mantisse et un exposant, avec un nombre de chiffres binaires (des -œbits-) fixé, et le développement est approché. Par exemple, le développement binaire du nombre 0,1 est infini donc son codage informatique ne peut qu'en donner une approximation. De même, les opérations sur les entiers donnent des résultats exacts tandis que les opérations sur les réels donnent des résultats approchés. En conclusion, le choix entre l'utilisation d'une valeur informatique entière ou réelle n'est pas anodin. Préférez les valeurs informatiques entières si vous n'avez besoin mathématiquement que de valeurs entières.

Structures algorithmiques. Le programme enchaà®ne des opérations dans des structures. On distingue trois structures :

la séquence :

instruction 1 instruction 2 instruction 3

l'alternative :

si expression logique alors

...

sinon

... fin si

l'itération : répéter

(La signification de ces structures sera détaillée plus bas.) Ces trois structures sont suffisantes. C'est-à -dire que, théoriquement, tout algorithme peut être écrit avec seulement ces trois structures.

Mémoire vive versus espace disque. L'information nécessaire à  l'exécution d'un programme inclut la liste des instructions à  exécuter et l'ensemble des objets manipulés par le programme, variables, constantes, avec leurs valeurs. Cf. figure (2). Lors de l'exécution d'un programme, toute cette information est conservée dans une partie de l'ordinateur appelée -œmémoire vive-, ou encore -œmémoire centrale-. Cette information n'existe que le temps de l'exécution du programme. La mémoire vive, dédiée à  l'exécution des programmes, n'a donc en général rien à  voir avec l'espace disque sur lequel vous stockez vos fichiers.

L'affichage à  l'écran et la lecture sur le clavier sont analogues à  l'écriture et la lecture dans un fichier. On considère en général dans les langages de programmation l'écran et le clavier comme des fichiers particuliers. L'écran est un fichier sur lequel on ne peut qu'écrire et le clavier est un fichier sur lequel on ne peut que lire.

Les notions définies dans cette partie que vous devez avoir bien comprises : variable, type d'une variable, constante littérale, constante symbolique, expression, typage statique ou dynamique, déclaration, mémoire vive.

3     Langage de description d'algorithme

à€ partir de l'énoncé d'un problème de programmation, avant d'arriver au programme, nous pouvons d'abord décrire dans un langage naturel la méthode de résolution du problème. Nous pouvons passer ensuite à  la description dans un -œlangage de description d'algorithme-.

Intérêt d'un langage de description d'algorithme

méthode de algorithmes résolution du de plus en problème plus détaillés

(langage naturel)

problème

programme

                                                   (difficile)                            en langage de

description d'algorithmes informel

Langage de description d'algorithme

-” Pour n'importe quel problème (intégration numérique, échecs, paye, ...).

-” Caractéristiques principales d'un langage de programmation mais avec une syntaxe plus libre, et des parties informelles à  détailler plus tard.

-” Ce cours : un langage possible, proche du langage Fortran, pour préparer l'écriture d'un programme en Fortran. Ce qui importe : le niveau de formalisation du langage, intermédiaire entre un langage naturel et un langage de programmation.

3.1    Variables et types

On utilise des types de base :

Type entier : Ensemble de valeurs : Z, ensemble des entiers relatifs. Opérations arithmétiques usuelles.

Type réel : Ensemble de valeurs : R. Opérations arithmétiques usuelles.

Type texte : Ensemble des suites de caractères. Une suite de caractères est notée entre guillemets :

"Il␣fait␣beau."

Une opération de base sur les suites de caractères est la concaténation, notée // :

texte1 // texte2

Type logique : Seulement deux valeurs possibles : vrai, faux. Les opérations sur ce type sont : et logique, ou logique, négation, implication ...

On adopte pour écrire l'algorithme un typage statique, comme en Fortran.

On déclare donc le type des variables et on écrit par exemple :

entier i

ce qui signifie que i est une variable de type entier. On peut auss déclarer des constantes symboliques, par exemple : constante réelle pi = 3.141592654

Dans une expression, les constantes ou variables sont combinées avec des opérateurs. Les opérateurs utilisés doivent être cohérents avec le type des objets combinés. Une expression peut être plus ou moins compliquée. Elle peut se réduire simplement à  une valeur littérale, par exemple la valeur entière 3, ou la valeur chaà®ne de caractères -œbonjour-. Une expression peut aussi être simplement une variable, par exemple la variable réelle x. Une expression un cran plus compliquée, contenant une opération, est par exemple l'expression x + 3.

3.2    Les tableaux

Le tableau est une structure de données. Les éléments d'un tableau contiennent des valeurs d'un même type. Chaque élément du tableau a un indice, qui est une valeur entière. Les indices prennent toutes les valeurs comprises entre une borne inférieure et une borne supérieure. La plage d'indices peut éventuellement avoir une partie négative. Exemple de déclaration de tableau :

réel tab(1: 10)

qui signifie que tab est une variable tableau, qui contient des éléments de type réel, avec des indices entre 1 et 10 (tab contient donc 10 éléments). On peut généraliser à  plusieurs indices :

réel tab2(1: 10, -2: 3)

qui signifie que tab2 est un tableau de réels, avec un premier indice variant de 1 à  10 et un second indice variant de -2 à  3 (tab2 contient donc 60 éléments). On dira que tab2 a deux dimensions. La taille d'un tableau ne peut pas changer, ou en tout cas, il faut considérer que changer la taille d'un tableau est une opération coà»teuse.

Notation pour l'accès à  un élément du tableau, par exemple pour un tableau à  une dimension :

nom_tableau(expression entière)

L'expression entière donne une valeur d'indice et détermine donc l'élément de tableau référencé. Exemples :

tab(i * j - 3) tab(i) + tab2(j, - 2)

o๠i et j sont des variables entières.

Noter les différences principales entre la structure tableau décrite ci-dessus (qui est celle de Fortran) et la structure liste de Python : les éléments d'un tableau ont tous le même type; la taille d'un tableau ne change pas facilement. Le tableau Fortran est proche du tableau Numpy de Python plutà´t que de la liste de Python.

3.3    Les instructions simples

Les instructions simples sont les entrées-sorties et l'affectation.

Les entrées-sorties sont des échanges entre la mémoire centrale et l'extérieur : écran, clavier, mémoire de stockage. Pour les entrées, la syntaxe du langage de description d'algorithme est : entrer (ma_variable)

qui signifie : attendre une valeur de l'extérieur, l'affecter à  ma_variable. On pourra aussi écrire l'instruction avec plusieurs variables, par exemple :

entrer (x, y, z)

Pour les sorties, la syntaxe est :

écrire (expression)

qui signifie : calculer la valeur de l'expression et l'écrire. On pourra aussi écrire plusieurs expressions :

écrire (expression1, expression2, ...) La syntaxe pour l'affectation est :

ma_variable = expression

qui signifie : calculer la valeur de l'expression et l'affecter à  ma_variable. Bien distinguer l'affectation du test d'égalité de deux valeurs. On notera == le test d'égalité. Exemple :

x = y == z

o๠x est une variable de type logique. Dans cet exemple, y et z peuvent par exemple être des variables de type entier, et y == z est une expression de type logique.

3.4    Assertions

Les assertions sont des propositions vraies (au sens de la logique mathématique, on dit encore des prédicats) qui décrivent l'état de la mémoire, ou d'une partie de la mémoire. Comme déjà  indiqué dans le § 2, chaque instruction peut être interprétée comme une transformation de l'état de la mémoire. Les assertions permettent donc de caractériser formellement l'effet des instructions. Il est possible de pousser très loin cette idée de caractériser formellement des instructions, pour arriver à  prouver que des algorithmes ou des programmes sont corrects. Mais il est aussi utile d'insérer dans un algorithme des assertions comme de simples commentaires, qui permettent de se repérer dans le cours d'un algorithme.

On notera les assertions entre accolades. Par exemple :

{x + q * y == a et y > q} x = x - y

Nous avons une assertion avant l'instruction d'affectation. Quelle assertion pouvonsnous écrire après l'affectation? La valeur de x a été modifiée par l'affectation. Si nous notons x0 l'ancienne valeur, nous avons :

{x' + q * y == a et y > q et x == x' - y}

à‰liminons l'ancienne valeur pour obtenir une assertion entre les variables qui existent dans l'algorithme. Nous pouvons écrire après l'affectation :

{x + (q + 1) * y == a et y > q}

On parle aussi de -œschémas-, de la forme :

{P} I {Q}

o๠I est une instruction, l'assertion P s'appelle la pré-condition du schéma et l'assertion Q s'appelle la post-condition du schéma. Le schéma signifie que si on a P avant l'exécution de I alors on aura forcément Q après exécution de I. Par exemple, on a le schéma :

{x + q * y == a et y > q} x = x - y {x + (q + 1) * y == a et y > q}

3.5    Les instructions composées

Les instructions composées sont la séquence, l'alternative et l'itération.

3.5.1         La séquence

Syntaxe de la séquence : on écrira simplement une instruction par ligne.

instruction_1 instruction_2 instruction_3

qui signifie : exécuter instruction_1 puis, de l'état de la mémoire obtenu, exécuter instruction_2, etc.

Exemple d'assertions avec une séquence :

{x == a et y == b} x = x + y

{x == a + b et y == b} y = x - y

{x == a + b et y == a}

L'ordre d'écriture des instructions dans le langage de description d'algorithme (et dans les langages de programmation impératifs) est donc fondamental.

3.5.2         L'alternative

Syntaxe de l'alternative : si expression logique alors

instruction_1

sinon instruction_2

fin si

qui signifie : évaluer l'expression logique; si elle est vraie, exécuter instruction_1, sinon exécuter instruction_2.

On peut utiliser les variantes suivantes de l'alternative. Sans la partie -œsinon- :

si expression logique alors

instruction_1

fin si

Avec plusieurs parties -œsinon- : si expression logique 1 alors

instruction_1

sinon si expression logique 2 alors

instruction_2

sinon instruction_3

fin si

3.5.3         L'itération

Syntaxe de l'itération (qu'on appelle aussi -œboucle-) :

tant que condition faire instruction fin tant que

o๠la condition est une expression logique. Ce qui signifie : évaluer la condition; si elle est vraie, exécuter l'instruction puis revenir à  l'évaluation de la condition; si la condition est fausse, ne rien faire.

Attention : la condition ne reste pas forcément vraie lors de l'exécution de l'instruction intérieure, c'est ce qui permet de sortir de l'itération après un certain nombre de passages. La valeur de la condition : vraie ou fausse, n'est testée qu'à  chaque passage de la ligne -œtant que-.

Deux modes de raisonnement correspondent à  l'itération. Premier mode : répétition d'un même traitement sur des objets différents. Par exemple :

tant que lecture d'une ligne de mon fichier réussie faire

traitement à  partir de la ligne lue essai de lecture d'une nouvelle ligne de mon ficher

fin tant que

Deuxième mode de raisonnement : calcul du terme final d'une suite définie par récurrence. Dans ce cas, on utilise à  chaque passage le résultat du passage précédent. Cf. exemple de l'algorithme (1).

Algorithme 1 Exemple d'algorithme de calcul du terme final d'une suite définie par récurrence.

entrer (a, b)

i = 0 s = 0

tant que i < b faire

i = i + 1 s = s + a

fin tant que

écrire (s)

Nous pouvons caractériser formellement l'effet d'une itération à  l'aide des assertions. Notons C la condition de l'itération et I l'instruction à  l'intérieur de l'itération :

tant que C faire

I

fin tant que

P désignant une proposition, si on a le schéma :

{P et C} I {P}

alors on a aussi le schéma :

{P} tant que C faire

I

fin tant que

{P et non C}

P est appelé un invariant de la boucle.

Exhibons un invariant de boucle sur l'exemple trivial de l'algorithme (1) :

entrer (a, b) i = 0 s = 0 {s == a * i} tant que i 6= b faire i = i + 1 s = s + a

{s == a * i} fin tant que

{s == a * i et i == b} écrire (s)

L'utilisation des assertions a ainsi permis de prouver l'effet de l'algorithme : l'algorithme multiplie a par b.

Lorsque l'algorithme itératif ne semble pas évident à  écrire, l'utilisation des invariants de boucle permet de bien poser le problème et d'arriver à  une solution sà»re. La méthode conseillée pour écrire un algorithme itératif est donc :

1. Trouver une idée informelle de la boucle.
2. La traduire en invariant INV.
3. Trouver une condition de sortie CS telle que : (invariant et condition de sortie) â‡’ résultat final.
4. Initialiser avec une suite d'instructions INIT telle qu'on ait l'invariant après cette initialisation :

INIT {INV}

5. Trouver une instruction I qui permette de se rapprocher de CS en gardant INV vrai.
6. Il ne reste qu'à  assembler les éléments précédents. L'algorithme s'écrit :

INIT

tant que non CS faire

I

fin tant que

Nous avons vu l'itération avec la structure -œtant que-. Une variante de l'itération est la boucle -œpour- : pour i = V1 à  V2 faire bloc d'instructions

fin pour

o๠i est un nom de variable entière, V1, V2 sont des valeurs entières, et i ne doit pas être modifié par le bloc d'instructions intérieur. Cette syntaxe signifie exactement : i = V1 tant que i â‰¤ V2 faire bloc d'instructions i = i + 1

fin tant que

Noter que dans l'écriture avec -œpour-, le changement de valeur de i est implicite à  chaque passage à  la ligne -œpour-. L'écriture avec -œpour- est plus concise; on ne peut l'utiliser que si on connaà®t avant le début de la boucle le nombre d'itérations à  réaliser.

4     Conseils de présentation des algorithmes et programmes

Cette partie donne quelques conseils de présentation.

Choix des identificateurs. En écrivant un algorithme ou un programme (dans n'importe quel langage de programmation), faites l'effort de donner un nom significatif aux variables, aux fonctions etc.

Indentation. La clarté de l'algorithme ou du programme repose en partie sur l'indentation des instructions, même dans les langages (comme Fortran) ou l'indentation n'est pas imposée par le langage lui-même. Le principe de l'indentation est de faire commencer les instructions d'une séquence à  la même colonne, tandis que, dans les alternatives et les itérations, les -œblocs intérieurs- sont décalés. Par exemple :

1: X = 3

2: si C alors

3:          instruction

4:          instruction

5: sinon

6:          instruction

7: fin si

8: Y = 2

Ads