Cours L’algorithmique et mathématiques

Cours L’algorithmique et mathématiques             

La programmation

Un ordinateur est un outil permettant d'exécuter des programmes. Comme son nom l'indique, un ordinateur sert à mettre de l'ordre. Dans quoi? Dans des données de toutes sortes: des nombres bien sûr, mais aussi des textes, des images, etc. Un programme manipule des données, les crée, les transforme, les déplace.

Prenons l'exemple de quelques programmes courants. Le traitement de textes permet de créer des textes, de les modifier, de les imprimer. Le tableur est spécialisé dans le traitement des nombres, les calculs. Une base de données permet de ranger une grande masse de données et de les ressortir dans différents ordres, selon différents critères. Le navigateur permet de se connecteur à des serveurs web, d'en obtenir des documents et de les afficher de façon agréable (alors que le document transmis n'est qu'une suite de caractères plus ou moins bizarres).

Utiliser ces différents programmes (on parle aussi d'applications) n'est pas le travail de l'informaticien. De nos jours, on utilise des ordinateurs dans presque toutes les professions, et même hors du cadre professionnel, dans la vie courante. Le travail d'un informaticien est la conception et/ou la création de programmes. Il y a là la même différence qu'entre un chauffeur de taxi qui utilise une voiture et un employé de chez Renault qui conçoit ou fabrique des voitures. De même que cet employé a lui aussi une voiture, l'informaticien utilise des programmes qui l'aident dans son activité professionnelle et privée.

Un programme utilise des données et il leur applique un traitement. Cela donne un certain résultat. Créer un programme nécessite d'identifier les données nécessaires, de savoir le résultat qu'on désire atteindre et de connaître un moyen automatique, mécanique de passer des unes à l'autre. Ce moyen mécanique est ce qu'on appelle un algorithme. Un langage de programmation est un outil qui permet d'exprimer cet algorithme sous une forme qui est compréhensible à la fois pour l'informaticien et pour la machine. C'est un outil de communication entre l'homme et la machine.

L'ordinateur sait à la base utiliser quelques types de données (par exemple les nombres entiers, les caractères) et faire quelques opérations dessus (par exemple les additions). Un programme peut décrire des données plus complexes (par exemple, un fiche de paye) en combinant plusieurs de ces données élémentaires, ainsi que des traitements complexes en combinants plusieurs des opérations de base (par exemple, calculer toutes les retenues successives sur un salaire brut).

Nous commencerons dès le chapitre prochain à réaliser des programmes, ce qui permettra d'être plus concret.

Rappels de logique

Pour exprimer nos idées, nous énoncons des jugements, par exemple : ``une carré est constitué de quatres cotés égaux''. La logique vise à formaliser le concept de raisonnement (mathématique) et par là même celui d'énoncés, de jugements.

Le Calcul des propositions est une formalisation rudimentaire du raisonnement : Les énoncés comme celui de notre exemple sont considérés comme des entités indivisibles -des propositions- et l'unique propriété que nous retiendrons d'eux est celle d'être vraie ou fausse. A partir des propositions de base dites atomiques que nous noterons A,B,P,Q ...il sera possible de construire des propositions plus complexes. On pourra par exemple nier une proposition. A chaque proposition, P on associera une autre proposition, la négation de P que nous désignerons \non P. L'essentiel de cette opération est que \non P est fausse quand P est vraie et vraie quand P est fausse. Ceci peut se résumer par un tableau :

s              (non s)

v             f

f              v

Nous sommes bien en train de décrire un calcul puisque gràce au tableau précédent appelé table de vérité nous pouvons calculer la valeur de vérité de notre nouvelle proposition à partir des valeurs possibles de la proposition plus simple à partir de laquelle elle est formée. On appellera connexion toute opération qui permet de former une nouvelle proposition à partir de propositions données de telle sorte que la valeur de vérité du résultat ne dépende que des valeurs de vérité des propositions sur lesquelles on opère. Nous venons de décrire la connexion non. Voici les autres , qui portent sur deux propositions s et t.

s              t              (s et t)

v             v             v

v             f              f

f              v             f

f              f              f

s              t              (s ou t)

v             v             v

v             f              v

f              v             v

f              f              f

s              t              (s =>t)

v             v             v

v             f              f

f              v             v

f              f              v

et, ou et => correspondent respectivement aux expressions ``et'', ``ou'' et ``si ...alors'' de la langue naturelle. Leurs tables de vérité correspondent à leurs usages courant aux deux remarques suivantes près :

• La table de vérité du ou correspond a l'usage inclusif du mot ``ou''.
• La valeur de verité vrai attribuée au cas où la condition de l'implication est fausse est peu naturelle. Dans le langage courant, on ne s'intéresse à la vérité d'un tel énoncé que lorsque la condition est vraie : ``s'il fait beau je vais à la pêche '' n'a d'interêt pratique que s'il fait beau ...Ici, nous voulons définir un calcul et devons donc décider ce cas. Attribuer la valeur vrai dans ce cas est par ailleurs tout à fait raisonnable si l'on songe que le fait qu'il ne fasse pas beau ne démontre en rien la fausseté de notre première déclaration d'intention.

Nous allons maintenant définir plus formellement le Calcul des Propositions.

Le langage du Calcul des propositions

On se donne un ensemble de symboles de propositions de base : A,B,C,... Cet ensemble constitue l'ensemble des formules atomiques. On se donne un ensemble de symboles -les connecteurs- permettant de former les connexions : non, et, =>, ou Les formules sont construites à l'aide des règles suivantes :

1. Les formules atomiques sont des formules.
2. Si A et B sont des formules alors A ou B, A et B, A => B et non A sont des formules.

La notion de vérité

Soit F une formule et A_1,..., A_n les symboles de proposition qu'elles contient et les symboles vrai et faux. Etant donnée une valuation de {A1,..., An} dans {vrai, faux}, nous savons calculer, grace aux tables de vérité, la valeur de vérité de F.

F est une tautologie si et seulement si elle prend la valeur vrai pour chacune des valuations de {A1,..., An} dans {vrai, faux} (il y en a  ).

La notion de Déduction

Dans les paragraphes précédent, nous nous sommes intéréssés à la notion de vérité d'une proposition. Nous allons maintenant nous intérésser à la notion de raisonnement correct. En voici un exemple :

Le chat mange ou dort.

S'il dort il ronronne.

S'il ronronne il est content.

En ce moment, il ne mange pas.

Donc, en ce moment il est content.

Ce raisonnement est correct au sens où la conclusion de cet ensemble d'énoncé se déduit des quatre premières hypothèses.

Quand dirons nous qu'une proposition P se déduit des propositions P1,... Pn? On pourrait adopter la position suivante : supposant P1, ...Pn formalisées dans le calcul des propositions, P se déduit de P1,..., Pn si la proposition P1,..., Pn => P est une tautologie. Cette optique ne nous satisfait pas. Pour justifier une déduction, on en montre une Preuve, qui conduit des hypothèses à la conclusion par une suite d'étapes évidentes. Se dessine ici une autre approche de la logique: au lieu de s'interesser à ce qui est vrai on s'interesse à ce qui est démontrable. Ce que l'on va chercher à formaliser sera cette fois la notion de preuve.

Nous allons décomposer le raisonnement en étapes élémentaires qui correspondent au raisonnement sur chacun des connecteurs. A chaque connecteur c correspond deux types de raisonnement :

• Le premier qui permet de déduire une formule ayant c comme connecteur principal. Par exemple ``de A et B on déduit A et B'' En général, ce raisonnement s'utilise lorsque l'on veut démontrer une formule de la forme A et B. Il s'interprète donc de la façon suivante : pour démontrer A et B, il suffit de démontrer A et de démontrer B.
• Le second type de raisonnement permet d'utiliser des énoncés ayant c comme connecteur principal pour déduire d'autres formules. Par exemple `` de A et B on conclut A'' .

Voici les raisonnements élémentaires attachés à chacun des connecteurs :

conjonction

Pour démontrer A et B il suffit de démontrer A et de démontrer B.

De A et B on conclut A et on conclut B.

disjonction

Pour démontrer A ou B il suffit de démontrer A ou de démontrer B.

De A ou B on conclut C dès lors qu'on possède des démonstrations de C sous hypothèse A et de C sous hypothèse B. En d'autres termes on utilise un énoncé de la forme A ou B en raisonnant par cas : premier cas = A est vrai. deuxième cas = B est vrai.

implication

Pour démontrer A => B on démontre B en supposant A.

De A et de A => B on déduit B.

négation

pour démontrer non A on démontre une contradiction sous l'hypothèse A.

De A et de non A on déduit une contradiction.

Exemple

Les problèmes simples de logique propositionnelle peuvent se traiter au moyen de tables de vérité. Ces tables permettent de déterminer dans quel cas une formule logique est vraie ou fausse.

Prenons un exemple: on cherche à déterminer dans quels cas la formule A et (B ou (non A)) est vraie.

On va faire une table de vérité en envisageant tous les cas possibles de valeurs pour A et B. Puis on calculera successivement les valeurs de vérité de toutes les sous-formules de A et (B ou (non A)).

Toutes les combinaisons possibles pour A et B sont: A et B sont vrais, A est vrai et B faux, A est faux et B vrai, A et B sont faux. Il y a donc quatre cas possibles. On aura quatre lignes dans notre table de vérité.

Les sous-formules de A et (B ou (non A)) qu'on doit étudier sont: A, B, non A, B ou (non A) et A et (B ou (non A)). Cela nous donnera les 5 colonnes du tableau.

Dans la formule, on trouve trois opérateurs logiques: et, ou, non. Pour chacun, on a une table de vérité que l'on connait d'avance.

p             q             p et q

vrai        vrai        vrai

vrai        faux       faux

faux       vrai        faux

faux       faux       faux

p             q             p ou q

vrai        vrai        vrai

vrai        faux       vrai

faux       vrai        vrai

faux       faux       faux

p             non p

vrai        faux

faux       vrai

Pour notre formule, nous allons donc avoir une table de vérité à quatre lignes (plus les titres) et cinq colonnes.

1             2             3             4             5

A             B             non A    B ou (non A)      A et (B ou (non A))

On commence en remplissant les deux premières colonnes avec toutes les combinaisons possibles.

1             2             3             4             5

A             B             non A    B ou (non A)      A et (B ou (non A))

vrai        vrai                                        

vrai        faux                                       

faux       vrai                                        

faux       faux                                       

On va ensuite calculer la troisième colonne. Pour cela, on va appliquer l'opérateur non sur le contenu de la colonne 1. On va donc temporairement identifier le p de la table de vérité de non et le A de notre formule.

Pour la première ligne, dans la colonne 1, on a vrai. On va chercher dans la table de vérité quelle est la valeur de vérité de non p quand p vaut vrai. On trouve faux. Donc on met faux dans la case première ligne troisième colonne du tableau.

1             2             3             4             5

A             B             non A    B ou (non A)      A et (B ou (non A))

vrai        vrai        faux                       

vrai        faux                                       

faux       vrai                                        

faux       faux                                       

On agit de même pour toute la colonne.

1             2             3             4             5

A             B             non A    B ou (non A)      A et (B ou (non A))

vrai        vrai        faux                       

vrai        faux       faux                       

faux       vrai        vrai                        

faux       faux       vrai                        

On veut maintenant calculer la quatrième colonne du tableau. Il s'agit de faire un ou entre la deuxième et la troisième colonne. On va utiliser la table de vérité du ou en identifiant temporairement p à B et q à non A.

La première ligne consiste à calculer la valeur de vrai ou faux. On va chercher dans la table de vérité du ou ce que vaut p ou q quand p vaut vrai et q faux. Cela vaut vrai. On agit de même pour toute la colonne.

1             2             3             4             5

A             B             non A    B ou (non A)      A et (B ou (non A))

vrai        vrai        faux       vrai       

vrai        faux       faux       faux      

faux       vrai        vrai        vrai       

faux       faux       vrai        vrai       

Pour calculer la dernière colonne, on fait un et entre les colonnes 1 et 4. Cela donne:

1             2             3             4             5

A             B             non A    B ou (non A)      A et (B ou (non A))

vrai        vrai        faux       vrai        vrai

vrai        faux       faux       faux       faux

faux       vrai        vrai        vrai        faux

faux       faux       vrai        vrai        faux

On peut conclure de cette table que A et (B ou (non A)) est vraie seulement quand A et B sont vrais tous les deux.

On peut aussi montrer avec une table de vérité que A et (B ou (non A)) est équivalent à A et B. On calcule séparément la valeur de vérité de chacune des deux propositions et on constate qu'elles ont toujours la même valeur.

1             2             3             4             5             6

A             B             non A    B ou (non A)      A et (B ou (non A))         A et B

vrai        vrai        faux       vrai        vrai        vrai

vrai        faux       faux       faux       faux       faux

faux       vrai        vrai        vrai        faux       faux

faux       faux       vrai        vrai        faux       faux

La limite de la méthode des tables de vérité est la taille des tables. Quand on a deux propositions de base, A et B, il faut quatre lignes. Si on en a trois, A, B, C, il faut 8 lignes. Si on en a quatre, il faut 16 lines. Si on en a n, il faut 2 puissance n lignes. En pratique, il est difficile de dépasser 4.

Exercice 1.1

Question 1

Donnez les tables de vérité des propositions suivantes:

• (A et B) ou (non B)
• (non A) et (non B)
• (A et B) et (non A)
• non (A et (non B))

Question 2

Pour chacune de ces proposition, trouvez une autre proposition plus simple (c'est à dire avec moins d'opérateurs) équivalente. Rappel: deux propositions sont équivalente si elles ont la même valeur de vérité dans tous les cas possibles.

Exercice 1.2

Soient les propositions:

• (P) il pleut
• (S) la sortie est annulée
• (M) etre mouillé
• (R) rester à la maison

Question 1

Traduire les phrases suivantes en une proposition logique, en utilisant P, S, M et R.

• Si il pleut et si je reste à la maison, je ne serai pas mouillée.
• Si il pleut mais si je reste à la maison, je ne serai pas mouillée.
• Si il pleut et si la sortie n'est pas annulée ou si je ne reste pas à la maison, je serai mouillée.
• que la sortie soit annulée ou non, s'il pleut, je reste à la maison.

Question 2

Dans quels cas la proposition Si il pleut mais si je reste à la maison, je ne serai pas mouillée est vraie?

Pour répondre à cette question, on fera une table de vérité où on calculera la valeur de la proposition en fonction des valeurs de P, M et R.

Question 3

Si la proposition Si il pleut et si je reste à la maison, je ne serai pas mouillée est vraie et si il ne pleut pas, est-ce que je reste à la maison?

Il ne s'agit pas de faire un raisonnement de la vie courante, mais un raisonnement logique. Pour cela, on fera une table de vérité de la proposition correspondant à Si il pleut et si je reste à la maison, je ne serai pas mouillée (ce que vous avez répondu à la question 1.1) et on regardera les lignes telles que cette proposition est vraie et P est fausse. On regardera alors la valeur de R dans ces lignes.

Et on en tirera une conclusion.

Exercice 1.3

Soient a, b et c trois entiers positifs.

Question 1

Montrez que la proposition (a<b) => (a = b) a pour négation a<b.

Pour cela, vous pouvez donner un nom aux deux propositions élémentaires a<b et a=b (élémentaire d'un point de vue logique, car < et = ne sont pas des opérateurs logiques. Ce sont des opérateurs arithmétiques).

Ensuite, faites la table de vérité des deux propositions et utilisez vos connaissances sur l'arithmétique pour exclure certains cas qui ne sont pas compatibles avec l'arithmétique. Cela revient à éliminer des lignes de la table.

Tirez la conclusion.

Question 2

Montrez que la proposition (a<b) => a = a a pour négation fleche a  a.

chapitre 2:premiers programmes

Etapes de la production

Produire un programme se fait par étapes successives.

• spécification
• conception
• codage
• compilation
• test
• mise en service
• maintenance

La première étape, la spécification, consiste à décrire ce que l'on souhaite obtenir. A ce niveau, il ne s'agit pas de dire comment, mais juste de décrire le comportement attendu du programme, ce qui nécessite de détailler un peu ce qu'il faut lui apporter comme données (ce qui va rentrer dans le programme) et ce que sera le résultat (ce qui va sortir). Dans la plupart des exercices qui vous seront proposés au cours de l'année, la spécification sera l'énoncé de l'exercice.

La conception consiste à décrire le programme, c'est à dire les moyens à employer pour obtenir le résultat escompté. Dans le cas de problèmes complexes, il faut opérer par étapes successives. La conception doit déboucher sur un algorithme, c'est à dire un procédé mécanique permettant d'obtenir le résultat à partir des données.

Le codage, ou programmation au sens strict, consiste à exprimer l'algorithme dans un langage de programmation donné. Cela donne le code du programme. Ce code est une suite de caractères que l'on peut taper sur un clavier d'ordinateur. Dans la suite du cours, nous aurons tendance à faire en même temps la conception et le codage, ce qui n'est possible que pour de petits programmes simples. Cela a l'avantage de nous éviter d'utiliser un premier langage pour faire la conception et un second pour la programmation.

Sous sa forme de code Ada, le programme n'est encore pas compréhensible par l'ordinateur. Il faut une étape de traduction dans une forme directement compréhensible par le processeur. Cette traduction est effectuée par un programme qui s'appelle un compilateur. Ce compilateur prend comme donnée un programme Ada et donne comme résultat le même programme dans la langue maternelle du processeur (par exemple, un pentium). C'est ce qu'on appelle le code exécutable. La compilation est une opération automatique et suffisament simple pour qu'on ne la considère généralement pas comme une étape de travail à proprement parler.

Une fois compilé, le programme peut être exécuté. La première chose à faire est de le tester pour s'assurer qu'il fonctionne convenablement. Même à l'échelle de nos petits programmes de début d'année, cette étape est importante. Elle l'est encore bien plus dans un cadre industriel.

Une fois convenablement testé, le programme peut être donné aux utilisateurs et être exploité.

L'activité de maintenance consiste à maintenir le programme en état de marche, en corrigeant les erreurs au fil de leurs apparitions. Des erreurs (les fameux bugs), il y en a presque toujours dans des programmes un tant soit peu complexe. Par ailleurs, il arrive que le programme doive être adapté à un changement de son environnement (par exemple, un changement d'ordinateur).

La maintenance d'un programme est suffisament coûteuse et importante pour qu'il soit intéressant de la prendre en compte par avance. En effet, il faut toujours prendre soin de la lisibilité de son programme, c'est à dire de la facilité de lecture au moment où on voudra corriger une erreur ou réaliser une adaptation. Dans un cadre industriel, cela peut se produire des années plus tard, et les personnes amenées à réaliser la maintenance peuvent ne pas être celles qui ont réalisé le programme.

Dans notre contexte scolaire, nous n'avons pas les mêmes contraintes, mais nous auront quand même toujours la préoccupation de privilégier la lisibilité par rapport à d'autres qualités telles que la concision. Nous ne demanderons pas de documentation pour les programmes, bien que ce soit la base de la maintenance.

Concrètement

Nous allons reprendre les étapes de création d'un programme d'un point de vue très concret, pour une application immédiate.

La spécification sera donné par un cours énoncé en français, par exemple: écrire un programme qui affiche la somme de deux nombres tapés au clavier.

Il faut écrire un programme Ada. Dans un premier temps, on peut le griffoner approximativement sur un bout de papier. Il s'agit d'un brouillon. On peut tout aussi bien réaliser ce brouillon à l'écran. C'est une question de goût et d'habitude. Dans l'un et l'autre cas, il s'agit de jeter des idées un peu en vrac et de les organiser progressivement.

Il faut créer un fichier qui contienne le programme Ada. Pour cela on utilise un éditeur de texte. C'est une sorte de traitement de texte, mais dont le but n'est pas de mettre en page le texte en vue de l'imprimer, mais juste de créer un fichier. Dans un éditeur de texte, on ne modifie pas l'apparence des caractères (taille, souligné, italique, gras), on ne donne pas de structure (page, table des matières, titres). On se contente de taper les caractères les uns après les autres.

Sur votre PC, vous pouvez utiliser Edit dans une fenêtre ms-dos, ou alors l'éditeur fourni avec le compilateur Gnat, ce qui est plus pratique. Nous verrons cela dans les exercices 2.1 et 2.2.

Une fois le programme tapé, on le sauve sur disque, ce qui a pour effet de créer (ou éventuellement mettre à jour) le fichier correspondant. Ce fichier en langage Ada doit avoir l'extension .adb (attention aux éditeurs qui veulent vous imposer l'extension .txt!).

Ensuite la compilation se fait soit à l'aide d'une commande ms-dos (gnatmake), soit en cliquant sur une icône de Gnat. Souvent, la compilation se passe mal, parce qu'il y a des erreurs dans le programme. Ce n'est pas du bon Ada. Il faut le corriger dans l'éditeur de texte et recommencer la compilation.

Quand il n'y a plus d'erreur dans le programme, le compilateur crée un fichier exécutable ms-dos, un fichier ayant l'extension .exe.

C'est ce fichier qu'on utilise pour exécuter le programme et le tester. Quand on l'a testé suffisament pour être convaincu qu'il marche bien, on peut considérer le travail comme terminé.