Mathématiques pour un cursus d'informatique
Propositions de John F. Sowa, et discussion

Laurent Bloch
 

   John Florian Sowa [1], après une carrière d'informaticien d'orientation plutôt théorique accomplie pour l'essentiel chez IBM, a écrit un livre intitulé Knowledge Representation [2] pour lequel il propose une annexe en ligne, Mathematical Background [3]. Quelles sont en effet les chapitres des mathématiques qui seront utiles, voire nécessaires, à qui veut apprendre l'informatique ?

Les 13 chapitres de John F. Sowa

Théorie des ensembles

   Les bases de la théorie des ensembles sont sûrement, des éléments des mathématiques, parmi les plus utiles à l'apprentissage et à la pratique de l'informatique. Que ce soit pour la programmation des ordinateurs, pour le paramétrage d'un système d'exploitation ou pour la configuration d'un réseau, il s'agit d'élaborer un automate qui sera appliqué à un ensemble de données, et la caractérisation précise de cet ensemble, par exemple un intervalle sur l'ensemble des entiers relatifs, sera une partie cruciale et délicate de cette élaboration. Être initié à la théorie des ensembles ne peut que contribuer à l'acquisition de la forme d'abstraction nécessaire à cet exercice. Si un seul chapitre doit être conservé, je pense que c'est celui-là.

   La notion de structure algébrique trouve à s'appliquer en maints endroits de la science informatique, notamment pour tout ce qui a trait aux types et aux sous-types de données. Avoir appris à raisonner rigoureusement dans ce cadre peut améliorer le travail du programmeur, c'est indispensable.

   Comme pour tous les apprentissages informatiques, il s'agit d'acquérir une forme de pensée abstraite. Et comme pour tout ce qui suit, les connaissances mathématiques utiles se réduisent, au moins dans un premier temps, à un niveau élémentaire, de terminale scientifique ou premières années de licence. Sachant que l'on peut néanmoins apprendre à programmer en ne connaissant que les nombres entiers, l'addition et la multiplication, mais l'effort à accomplir sera plus intense parce que la marche à gravir sera plus haute, les perspectives offertes seront plus étroites et le résultat sans doute moins bon.

   Bref, savoir plus de mathématiques ne peut pas nuire, mais ce n'est pas nécessaire, et surtout cela ne doit pas faire perdre de vue que l'informatique n'est pas un sous-produit des mathématiques, et que ses concepts sont différents. Ainsi, la notion de variable informatique diffère (subtilement) de la variable mathématique, et bien faire la différence entre les deux est indispensable. Essayer de ramener toute l'informatique à des formes mathématiques ne peut qu'empêcher d'y rien comprendre, et mener à l'échec.

Fonctions

   La plupart des programmes informatiques bien formés peuvent être vus comme des fonctions appliquées à des arguments pour donner des résultats. En tout état de cause, écrire ses programmes en les pensant selon ce modèle est une bonne discipline pour une programmation de bonne qualité, sûre. C'est pour cela qu'existe une style de programmation dit fonctionnel, et des langages fonctionnels (Lisp, Scheme, OCaml, Haskell), qui sont à mon avis les meilleurs. Alors avoir des idées assez précises sur la nature mathématique de ces objets me semble nécessaire.

   Là aussi, les bases sont suffisantes, ce qui n'interdit pas d'en savoir plus, bien sûr.

Λ-calcul

   Le λ-calcul, créé dans les années 1930 par Alonzo Church (le directeur de thèse d'Alan Turing), propose une abstraction de la notion de fonction, équivalente à la machine de Turing, propre à représenter toute fonction récursivement calculable. La valeur d'un programme informatique est une λ-expression [4]. Connaître les rudiments du λ-calcul ne peut pas nuire, cela procurera une meilleure vision de ce qu'est un programme, un niveau supérieur d'abstraction, et permettra donc d'écrire des programmes plus élégants et plus justes. Mais on peut s'en passer.

Théorie des graphes

   Beaucoup de problèmes informatiques peuvent être représentés sous formes de graphes : réseaux bien sûr, mais aussi systèmes de fichiers, algorithmes de tri, classifications et classements. Par exemple, les biologistes construisent des arbres phylogénétiques pour établir des proximités ou des distances entre des organismes, ou d'autres entités biologiques ; dès que le problème atteint une certaine taille il est insoluble sans l'informatique (et encore...) ; c'est l'analyse phylogénétique qui a permis de distinguer les procaryotes [5] des archées [6], deux des trois domaines du vivant [7] (le troisième, auquel appartiennent les lecteurs et l'auteur de cet article, est celui des eucaryotes [8], mais bien sûr ces classifications sont contestées). Ce sont Carl Woese [9] et George E. Fox [10] qui ont établi en 1977 la distinction entre les procaryotes (les bactéries, en gros) et les archées, par la construction d'un arbre phylogénétique [11] qui mettait en évidence leur séparation.

   Pour construire leur arbre phylogénétique, Carl Woese et George E. Fox ont utilisé des moyens informatiques [12] sans lesquels un calcul de cette complexité aurait été impossible. Ils sont ainsi des pionniers de la bio-informatique. Il leur a fallu des mois et des mois d'analyses de gels d'électrophorèse, ensuite saisies sur cartes perforées et comparées par programme.

   La théorie des graphes et la recherche opérationnelle ont ouvert un vaste champ à l'algorithmique, avec une préférence (non exclusive) pour les arbres : construction de graphes, parcours dans des graphes, calcul de distances, optimisation, etc. Les applications en sont multiples, de la bio-informatique à l'Internet, dont tout le fonctionnement repose sur de tels algorithmes.

   Un autre usage des graphes est la représentation des automates à états finis, que l'on retrouve dans tout ce qui concerne les analyses de textes les plus variés, que ce soit en linguistique de la programmation, en informatique linguistique, en génomique, etc.

Relations

   La théorie algébrique des relations, proche cousine de la théorie des ensembles, a de multiples applications en informatique, dont la plus importante est l'invention de l'algèbre relationnelle [13] en 1970 par Edgar Frank Codd, qui a donné naissance aux bases de données relationnelles [14]. Ces travaux ont donné une consistance scientifique formelle à la science des bases de données, sur laquelle reposent l'essentiel de l'informatique de gestion dans le monde, ainsi que la quasi-totalité des sites Web de par le monde. Il me semble inutile d'en dire plus.

Représentation des relations par des graphes

   Si on a des graphes et des relations, il est souvent commode de représenter celles-ci par ceux-là. Donc, oui, c'est utile.

Treillis

   Les treillis ont des applications informatiques, lire ce qu'en écrit J. Sowa. À mon avis on peut vivre sans.

Logique propositionnelle et logique des prédicats

   La logique symbolique joue un rôle central pour la programmation, et pas seulement, elle permet de mieux comprendre ce que l'on fait en programmant. Elle comporte deux branches principales, la logique propositionnelle, qui remonte à Aristote, formalisée par Leibniz et finalement par Boole, et la logique des prédicats. La seconde est plus puissante, parce qu'elle introduit des variables et des quantifieurs, mais moins simple ; elle permet de formuler les axiomes de l'arithmétique énoncés par Giuseppe Peano. Gottlob Frege et Peano sont les créateurs de la logique des prédicats, on lira obligatoirement les axiomes de Peano [15], et avec profit les textes de Gottlob Frege, concis, riches et accessibles.

   L'algèbre de Boole, qui formalise la logique propositionnelle, est à la base du fonctionnement des circuits logiques au cœur des ordinateurs.

Axiomes et démonstrations

   Une fois muni des bases de la logique symbolique, on peut aborder les démonstrations. Le texte de J. Sowa donne une vision d'ensemble résumée de ce vaste domaine. On prêtera une attention particulière à la distinction entre variables libres et variables liées. On retiendra que cette théorie de la démonstration peut mener, entre autres destinations passionnantes, aux fameux théorèmes de Gödel. Un informaticien ne saurait rester indifférent à ces choses qui ont tant d'implications pour son activité, d'autant plus que certains langages de programmation sont conçus explicitement en référence à ces fondations théoriques, et qu'ils en tirent de réels avantages.

Grammaires formelles

   Les grammaires formelles sont au &coelig;ur de la définition des langages de programmation. Elles permettent de décrire la syntaxe d'un langage par la spécification des chaînes de symboles acceptées par la grammaire, ou mots du langage. Comme l'ensemble de ces mots est infini, ils sont en général obtenus par dérivation d'une définition récursive. Avoir au moins survolé les rudiments des grammaires formelles devrait permettre d'écrire de meilleurs programmes.

Graphes de jeux

   Les graphes de jeux introduisent à toute une série de problèmes algorithmiques, notamment ceux mis en jeu par ce que l'on nomme (abusivement à mon avis) l'intelligence artificielle. Alors oui, c'est un bon terrain d'exercice, qui peut plaire aux étudiants.

Théorie des modèles

   « La théorie des modèles est une branche de la logique mathématique qui traite de la construction et de la classification des structures. Elle définit en particulier les modèles des théories axiomatiques, l'objectif étant d'interpréter les structures syntaxiques (termes, formules, démonstrations...) dans des structures mathématiques (ensemble des entiers naturels, groupes, univers...) de façon à leur associer des concepts de nature sémantique (comme le sens ou la vérité). » (Wikipédia). Je serais tenté de dire que dans un premier temps on peut vivre en s'en passant, mais il est certain que l'étudiant tenté par la théorie devra s'y intéresser.

Ce que Sowa omet et que j'ajoute

Théorie des nombres et systèmes de numération

   Quels que soient les algorithmes, quelles que soient les données auxquelles on les applique, celles-ci comme les textes des programmes sont irrévocablement codés sous forme numérique, les circuits logiques des ordinateurs ne traitent que des nombres. L'informaticien doit donc avoir des idées assez précises sur les nombres, sur les opérations qui s'appliquent à eux, sur la façon dont ils sont représentés dans la mémoire de l'ordinateur, sinon il sera exposé aux multiples erreurs disponibles dans ce domaine : arrondi abusif, débordement de capacité par excès ou par défaut, etc. La représentation des nombres fractionnaires (« avec des chiffres après la virgule », abusivement mais la plupart du temps qualifiés de « réels ») est un domaine de recherche et d'applications à part entière (si l'on peut dire) : en réalité, il ne s'agit que d'entiers bricolés (mais de façon compliquée), sur un intervalle borné.

Nombres premiers, classes d'équivalence modulo n

   La prolifération des cyberattaques et le développement en retour des travaux de cybersécurité, ainsi que les préoccupations croissantes dans le domaine cyberstratégique, ont accru l'intérêt pour la cryptographie et la recherche dans ce domaine.

   Pour des raisons mathématiques dont on trouvera quelques exemples ici [16], beaucoup d'algorithmes cryptographiques reposent sur la recherche de grands nombres premiers [17], sur l'arithmétique modulo n, sur le problème dit du logarithme discret et sur quelques problèmes de la même famille. La solution de ces problèmes a notamment permis l'échange confidentiel de clés de chiffrement sans circulation de clé en clair ni rencontre physique entre les parties (algorithme Diffie-Hellman), ainsi que le chiffrement asymétrique, à clé publique (algorithme Rivest-Shamir-Adleman, RSA). On ne peut comprendre ces découvertes capitales, utilisées universellement, sans en saisir les fondements mathématiques.

Algèbre linéaire

   L'informatique fait un usage intensif des vecteurs et des matrices, généralement pour des choses très simples, comme ranger des données. Pour un public motivé on pourra aller jusqu'à la méthode du pivot de Gauss, mais la plupart des étudiants n'auront besoin que des rudiments.

Pour conclure

   Ce bref survol, inspiré par le texte de John F. Sowa, auquel j'ai ajouté quelques sujets tout en mettant entre parenthèses certains de ceux qu'il proposait, n'a de prétention ni à l'exhaustivité ni à l'obligation. La plupart des informaticiens, à commencer par moi-même, n'ont de ces sujets qu'une connaissance imparfaite, voire inexistante. Je n'ai découvert la plupart d'entre eux qu'à l'issue de longues années de pratique empirique d'autodidacte.

   Il me semble utile que les cursus d'informatique comportent des éléments de mathématiques, et c'est parmi ces sujets qu'il faut les prendre, en les adaptant au niveau et à l'orientation des étudiants. Il est inutile, voire nuisible, de les assommer avec des questions qui n'ont rien à voir avec l'informatique, mais qui réussiront à les en détourner, comme les équations différentielles. Je vois combien il est important que je puisse dire à mes étudiants biologistes qu'ils n'auront jamais besoin d'autre chose que de l'addition et de la multiplication des nombres entiers, moyennant quoi on peut créer des algorithmes très savants avec un outillage si restreint.

Lectures recommandées

   Je ne saurais terminer sans signaler deux ouvrages recommandables, parce que chacun à sa façon ils respectent un équilibre raisonnable entre les mathématiques et l'informatique : Méthodes mathématiques pour l'informatique de Jacques Vélu, chez Dunod, plus particulièrement destiné à un premier cycle universitaire, et Mathématiques concrètes : Fondations pour l'informatique, de Donald Knuth, Robin-Lee Graham et Oren Patashnik, excellement traduit par Alain Denise chez Vuibert, un puits de science. Et j'aurais garde d'omettre le manuel d'Arithmétique de Pierre Wassef, chez Vuibert, plus spécialisé mais qui traite un grand nombre de sujets énumérés ci-dessus. Thérèse Hardin me signale également Éléments de Mathématiques discrètes, Cours, Exercices résolus, Implémentations avec les Langages Python et OCaml, de Mathieu Jaume, aux Éditions Ellipses ; les démonstrations mathématiques y sont faites avec tous les détails, même les plus petits ; de plus, tous les concepts sont implémentés en Ocaml et Python.

Laurent Bloch

Paru le 14 septembre 2018 sur le site de Laurent Bloch.
https://laurentbloch.net/MySpip3/Mathematiques-pour-un-cursus-d-informatique

Cet article est sous licence Creative Commons (selon la juridiction française = Paternité - Pas de Modification). http://creativecommons.org/licenses/by-nd/2.0/fr/

[1] https://en.wikipedia.org/wiki/John_F._Sowa

[2] http://www.jfsowa.com/krbook/krtoc.htm

[3] http://www.jfsowa.com/logic/math.htm

[4] En fait, pour être précis, c'est une fermeture, soit une λ-expression associée à un environnement. Un environnement est un ensemble de doublets variable-valeur.

[5] https://fr.wikipedia.org/wiki/Prokaryota

[6] https://fr.wikipedia.org/wiki/Archaea

[7] https://fr.wikipedia.org/wiki/Domaine_( biologie)

[8] https://fr.wikipedia.org/wiki/Eukaryota

[9] https://fr.wikipedia.org/wiki/Carl_Woese

[10] https://en.wikipedia.org/wiki/George_E._Fox

[11] https://en.wikipedia.org/wiki/File:PhylogeneticTree,_Woese_1990.PNG

[12] http://www.pbs.org/wgbh/nova/next/evolution/carl-woese/

[13] https://fr.wikipedia.org/wiki/Algébre_relationnelle

[14] https://fr.wikipedia.org/wiki/Base_de_données_relationnelle

[15] https://fr.wikipedia.org/wiki/Axiomes_de_Peano

[16] https://laurentbloch.net/MySpip3/Codes-secrets-et-arithmetique-modulo-n

[17] https://fr.wikipedia.org/wiki/Plus_grand_nombre_premier_connu