Support de cours les algorithmes de la brochure avec Excel et VBA, tutoriel & guide de travaux pratiques algorithmes en pdf.

Présentation d’un langage d’écriture des algorithmes

Certaines des instructions présentées ci-dessous utilisent la notion d’expres-sion booléenne : ces expressions ne peuvent avoir que deux valeurs possibles, vrai et faux.
On peut dire simplement qu’elles sont obtenues en comparant entre elles deux ex-pressions, dont la comparaison est possible, à l’aide des opérateurs classiques de comparaison : <; ; >; ; =; 6=.
Des expressions plus complexes pouvant être construites en utilisant les opéra-teurs logiques classiques : ou, et , non qui dénotent respectivement la disjonction, la conjonction et la négation.
1. informaticien célèbre pour ses travaux en algorithmique, créateur de TEX.

L’instruction d’affectation

La syntaxe de cette instruction varie suivant les langages utilisés. Elle a pour but d’affecter à une variable la valeur d’une expression. En général, dans les langages de programmation, sa forme est : « expression partie gauche » « symbole » « expression partie droite »
L’expression en partie gauche doit impérativement désigner une adresse et une valeur est associée à l’expression de la partie droite. Elle a pour but de ranger la valeur de l’expression à l’adresse indiquée par la partie gauche. Comme il a été dit le symbole varie suivant les langages de programmation.
– := en Algol, Pascal, Maple,. . .
– = en Basic , C, CAML,. . .
– en LSE
Signalons que sur certaines calculatrices de poche TI (Texas Instrument) le sym-bole utilisée pour l’affectation est !. Cela est très ennuyeux car les élèves qui ont l’habitude de manipuler ces matériels ont tendance à inverser le sens de l’af-fectation lorsqu’ils se mettent à programmer sur ordinateurs. . . Nous choisirons comme symbole car il est cohérent avec les notions de « partie gauche » et « par-tie droite » qui se retrouvent dans tous les langages utilisés par les ordinateurs et il ne comporte pas le symbole = qui perturbe les élèves, car il a pour eux une autre signification (l’égalité). En résumé notre instruction d’affectation sera : « expression partie gauche » « expression partie droite » et se lit L’expression partie gauche reçoit la valeur de l’expression partie droite
Exemples :
k 0, la variable k reçoit la valeur 0.
k k+1, la variable k reçoit la valeur de l’expression k+1.
k a*(10+b)/n, la variable k reçoit la valeur de l’expression a*(b+10)/n.

Les instructions conditionnelles

Ces instructions sont le si alors et le si alors sinon.
L’instruction si alors Elle s’écrit :
si « expression booléenne » alors « instruction ».
Si l’évaluation de l’expression donne la valeur vrai c’est l’instruction qui suit immédiatement le alors qui est exécutée, sinon c’est l’instruction suivante (celle qui suit le si alors ) qui est exécutée.
Dans le cas où l’on souhaiterait exécuter après le alors non pas une, mais plusieurs instructions, on écrira ces instructions sur plusieurs lignes (une instruction par ligne) précédées par un trait vertical qui englobe toutes ces instructions.
si « expression booléenne »
alors
instruction1
instruction2
…
instruction n
L’instruction si alors sinon
Elle s’écrit :
si « expression booléenne » alors « instruction 1 » sinon « instruction 2 ».
Si l’évaluation de l’expression donne la valeur vrai, c’est l’instruction 1 qui suit immédiatement le alors qui est exécutée, sinon c’est l’instruction 2 qui suit le sinon qui est exécutée.
Dans le cas où l’on souhaiterait exécuter non pas une, mais plusieurs instructions, on écrira ces instructions sur plusieurs lignes (une instruction par ligne) précédées par un trait vertical.
si « expression booléenne »
alors
instruction1
instruction2
…
instruction n
sinon
instruction1
instruction2
…
instruction p

Les instructions itératives

La boucle tant que Elle s’écrit :
tant que « expression booléenne  » faire  » instruction ».
Tant que l’expression booléenne est vraie on exécute l’instruction qui suit faire, dès qu’elle devient fausse, on passe à l’instruction suivante. Dans le cas où l’on souhaiterait exécuter non pas une, mais plusieurs instructions, on écrira ces ins-tructions sur plusieurs lignes (une instruction par ligne) précédées par un trait vertical.
tant que « expression booléenne « faire
instruction1
instruction2
…
instruction n
La boucle pour
Elle s’écrit :
pour « variable » variant de « expr. init » jusqu’à « expr. fin » faire « instruction ». ou encore
pour « variable  » variant de « expr. init » jusqu’à « expr. fin » avec un pas de « expr.
pas » faire « instruction ».
L’instruction qui suit faire est exécutée pour les différentes valeurs de la « va-riable ». La variable est appelée variable de contrôle de la boucle. Si l’expression pas n’est pas précisée, la variable de contrôle est incrémentée de 1 après chaque tour de boucle. Dans le cas où l’on souhaiterait exécuter non pas une, mais plu-sieurs instructions, on écrira ces instructions sur plusieurs lignes (une instruction par ligne) précédées par un trait vertical.
pour variable variant de « expr. init » jusqu’à « expr. fin » faire
instruction1
instruction2
…
instruction n
En général la variable de contrôle, l’expression initiale, l’expression finale et l’ex-pression pas (si elle est présente) ont des valeurs entières. Ce sera toujours le cas dans les algorithmes étudiés. Par ailleurs, on interdit de modifier la variable de contrôle à l’intérieur de la boucle.

Illustration des notions de preuve et de terminaison d’un algorithme

Ces notions sont illustrées à travers cinq exemples. On présente tout d’abord trois algorithmes qui permettent de calculer le produit a b de nombres entiers naturels a et b, puis le très connu algorithme d’Euclide pour calculer le PGCD de deux nombres entiers et enfin un algorithme un peu moins connu permettant de calculer le quotient et le reste de la division euclidienne de deux nombres entiers.
Algorithme de multiplication : Un premier algorithme
Algorithme 1. Ce premier algorithme calcule le produit de deux nombres entiers (a b) en n’effectuant que des additions.
x a
y b z 0
tant que y 6= 0 faire z z + x
y y 1 résultat z
Terminaison : y étant décrémenté de 1 à chaque itération, il deviendra néces-sairement nul au bout de b itérations.
Validité : Il suffit d’établir que z + x y reste en permanence égal à a b. On dit que cette quantité est invariante. C’est l’invariant qui caractérise la boucle. Cet invariant joint à la condition d’arrêt (y = 0) prouve que la variable z vaut a b à la sortie de la boucle.
– C’est trivialement vrai avant la boucle.
– Montrons que cette propriété reste vraie à la fin de chaque itération. Pour
cela nous noterons x0, y0 et z0 les valeurs respectives de x, y et z à la fin d’une itération. Bien évidemment, ces valeurs deviendront les nouvelles va-
leurs de x, y et z pour l’itération suivante. On a x0 = x, y0 = y 1 et z0 = z + x.
z0 + x0 y0 = z + x + x (y 1)
= z + x y
= a b par hypothèse de récurrence .
Algorithme de multiplication : Un deuxième algorithme
Algorithme 2. Ce second algorithme calcule le produit de deux nombres entiers en n’effectuant que des multiplications et divisions par 2.
x a
y b z 0
tant que y 6= 0 faire
si y impair alors z z + x
x 2 x
y y div 2
résultat z
Terminaison : y étant divisé par 2 à chaque itération, il deviendra nécessaire-ment nul après un nombre fini d’itérations.
Validité : Il suffit d’établir que z + x y reste en permanence égal à a b. Cet invariant joint à la condition d’arrêt (y = 0) prouve, ici encore, que la variable z vaut a b à la sortie de la boucle.
– C’est trivialement vrai avant la boucle.
– Montrons que cette propriété reste vraie à la fin de chaque itération. Pour cela nous noterons x0, y0 et z0 les valeurs respectives de x, y et z à la fin d’une itération. Bien évidemment, ces valeurs deviendront les nouvelles va-leurs de x, y et z pour l’itération suivante. Deux cas sont à envisager :
– y pair
On a x0 = 2 x , y0 = y=2 et z0 = z. z0 + x0 y0 = z + (2 x) (y=2)
= z + x y
= a b par hypothèse de récurrence .
– y impair
On a x0 = 2 x , y0 = (y 1)=2 et z0 = z + x. z0 + x0 y0 = z + x + (2 x) ((y 1)=2)
= z + x + x (y 1)
= z + x y
= a b par hypothèse de récurrence.
Cet algorithme est connu sous divers noms : multiplication russe, multiplication égyptienne,. . . Notons que son codage en informatique donne un algorithme très efficace car multiplications et divisions par 2 consistent en des décalages, et ces opérations élémentaires dans tout langage machine sont effectuées très rapide-ment. On peut donner une justification de sa validité autre que celle utilisant la notion d’invariant. Il suffit de considérer l’écriture binaire de y,
y = ki=0 y[i]2i où les coefficients y[i] valent 0 ou 1. Le produit x y est doncP
la P  égal à ik=0 y[ii] (x 2i). Tous les termes intervenant dans la somme sont de
forme x 2 et correspondent à des coefficients y[i] non nuls, i.e aux valeurs impaires que prend la variable y dans l’algorithme 2.
Dans la pratique on organise les calculs en faisant deux colonnes, une contenant respectivement les valeurs des quotients successifs de y par 2 et l’autre les valeurs de la forme x 2i. Il suffit alors de sommer les éléments de la deuxième colonne (en gras dans l’exemple ci-dessous) qui sont en face d’éléments impairs de la pre-mière colonne.
Exemple, soit à calculer le produit de x= 12 par y= 22.

1 Algorithmique 
1.1 Quelques idées en vrac
1.2 Présentation d’un langage d’écriture des algorithmes
1.3 Illustration des notions de preuve et de terminaison d’un algorithme
1.4 Un principe fondamental : la dichotomie
1.5 Quelques algorithmes élémentaires en arithmétique
1.6 Les algorithmes de la brochure avec Excel et VBA
2 Introduction à la logique mathématique 
2.1 Bref survol historique
2.2 Un langage mathématiquement défini
2.3 La formalisation des démonstrations
2.4 Illustration de quelques règles
2.5 La logique au quotidien en classe de mathématiques
2.6 Bibliographie

……….