Mathématiques pour l'informatique

Objectifs

Cet enseignement de première année couvre la partie algébrique du pro­gram­me de mathématiques pour l'in­for­ma­ti­que. L'étude des éléments d'analyse est assurée dans un mo­du­le commun avec la li­cence de mathématiques. Ce cours aborde les notions basiques et fondamentales de l'algèbre et introduit les principales structures qui ne sont qu'effleurées dans les enseignements généraux de mathématiques à l'Université. Ces éléments sont absolument incontournables pour faire des études d'informatique, la très grande majorité des modèles et structures qui y sont utilisées sont de simples transpositions de leurs homologues mathématiques. Les différents chapitres servent d'amorces à l'étude plus poussée des concepts introduits. Ils doivent permettre à l'étudiant d'aborder les en­sei­gne­ments spécialisés correspondants et d'autres domaines qui s'appuient sur ces mêmes fon­de­ments.

Cet enseignement tente, dans la mesure du possible, d'aborder chaque nou­vel­le notion à travers l'étu­de d'un ou plusieurs problèmes concrets et en liaison avec l'informatique. Il s'agit de justifier la pa­no­plie d'outils né­ces­sai­res à la résolution de ces problèmes plutôt que d'une présentation laconique des notions étudiées. Nous verrons, entre autres, comment déterminer que des robots sont dé­fec­tueux, comment fiabiliser l'information fournie par une boussole, comment s'assurer qu'un contrat ne puisse pas être fal­si­fié, comment ranger les pièces d'un casse-tête et comment communiquer de ma­nière secrète.

L'apprentissage du langage mathématique pour des études d'in­for­ma­ti­que s'ap­pa­ren­te à l'apprentissage du solfège pour pratiquer le jazz, c'est un passage obligé. Pour pousser la métaphore musicale, l'étude de problèmes concrets consiste à jouer de la musique plutôt que de se contenter d'en étudier les codes.

Ce cours ayant une vocation pédagogique, certains sacrifices à la rigueur nous ont parus inévitables et sont parfaitement assumés. La tentation était grande de ne pas laisser dans l'ombre certains points délicats. Dans ces moments, nous avons réfréné nos pulsions d'investigation autant que pos­si­ble en nous contentant souvent de quelques remarques pour attirer l'attention du lecteur. Les exercices ainsi que les sujets de travaux pratiques sont des jalons dans le cours plutôt que rassemblés en fin de chapitre. Il s'agit de s'assurer que l'on a bien saisi les notions et que l'on est capable de manipuler les objets et outils nouvellement introduits.

Un autre point distingue cet enseignement de ceux qui sont généralement pratiqués en ma­thé­ma­ti­que, les travaux pratiques. La grande majorité des preuves abordées au collège, au lycée et en premier cycle à l'université sont constructives, quand il ne s'agit pas purement et simplement d'al­go­ri­thmes (multiplier des nombres, calculer les zéros d'un polynôme, dériver une fonction, calculer l'in­ter­sec­tion de deux droites, etc.). Les comprendre est une chose, mais les programmer demande une assimilation bien plus profonde des concepts étudiés. Il s'agit en substance de concevoir des ex­pli­ca­tions destinées à des ordinateurs, assez peu réputés pour leur ouverture d'esprit et leur ca­pa­ci­té à combler eux-mêmes les innombrables trous que nous laissons dans celles que nous destinons aux êtres humains. Le volume horaire par étudiant que nous avons attribué aux tp représente les 3/7 de l'enseignement, cela donne une idée de l'importance que nous ac­cor­dons à la pratique.

Sans ouvrir un débat sur la nécessité des incessantes réformes de l'Université et leurs conséquences, il y a consensus pour affirmer que les volumes horaires sont aujourd'hui très insuffisants pour former correctement un étudiant à la science. Néanmoins, les centaines d'heures qui ont été dégagées*(*) au sens propre com­me au figuré peu­vent être mise à profit par l'étudiant pour lire et étudier en dehors du cadre universitaire. C'était déjà une condition nécessaire quand les volumes horaires étaient bien plus substantiels. C'est pré­ci­sé­ment l'objectif visé par ce cours en ligne. Nous invitons avec insistance l'étudiant à lire et étudier chaque chapitre avant d'assister au cours. Ce travail préalable permet de laisser une grande place à l'interaction entre les étudiants et l'enseignant pour apporter des réponses aux points qui sont restés obscurs.

Nous espérons également qu'à travers ce cours, l'étudiant entreverra les aspects ludiques des ma­thé­ma­ti­ques. Toutes ces notions théoriques ne sont pas une fin en soi, elles fournissent les moyens de résoudre des problèmes de manière effective. En résumé, la théorie c'est pratique.

Ce cours a été rédigé et développé pour un navigateur supportant les principales normes en vigueur. Le lecteur est invité à télécharger un navigateur libre comme chromium avec lequel ces pages ont été testées et validées.

Les nouveaux termes définis sont distingués des autres de cette manière. Toutes les définitions sont récapitulées en tête de chapitre sous le sommaire et dirigent le lecteur à la position où elles ont été introduites. Un terme ou un groupe de termes distingué de cette manière est un hyperlien vers sa définition.

Chaque chapitre contient des applications interactives qui sont censées aider le lecteur à comprendre un résultat en effectuant ses propres expérimentations. Pour cela, des permettent de modifier certains paramètres et sont ma­té­ria­li­sés par un cadre en trai­til­lés jaunes.

Les scripts javascript présents dans ces pages ne servent qu'à la mise en page des mathématiques avec le processeur MathJax et à l'exécution des dif­fé­rents pro­gram­mes qui illustrent le cours. Pour faciliter la lecture, les preuves et les solutions des exercices sont repliées et se déplient en cliquant dessus.

Contrôle des connaissances

Le contrôle des connaissances sera constitué de :

  1. Six qcm de contrôle continu d'une durée de 30 minutes, un par chapitre ;
  2. Une épreuve écrite de 2 heures ;
  3. Une épreuve pratique de 2 heures.

Les chapitres du cours

Les chapitres présentés ici (dont certains ne sont pas encore rédigés) sont destinés à couvrir les deux semestres de la première année de licence, ils ne seront donc pas tous abor­dés ou alors partiellement en I23.

  1. ✍ Logique et ensembles
  2. ✍ Calcul booléen
  3. ✍ Relations, applications
  4. ✍ Combinatoire
  5. ✍ Groupes
  6. ✍ Arithmétique
  7. ✍ Codage
  8. ✍ Automates

Annales des contrôles terminaux

Bibliographie

Ce cours est l'adaptation de notes personnelles elles-mêmes largement inspirées des ouvrages sui­vants, entre autres :