Mathématiques pour l'informatique

Si vous avez manqué la première séance de cours et par conséquent la distribution du document intitulé Memento-I23, il faut le télécharger, le compléter, le signer puis le restituer au secrétariat pédagogique.

Chapitres du cours, planches de td et de tp

Les chapitres présentés ci-dessous sont censés être étudiés sur deux semestres entre la première et la deuxième année de la licence d'informatique, ils ne seront donc pas tous abordés, ou alors partiellement, dans l'enseignement de I23 de la première année (le chapitre sur les probabilités discrètes est en cours de rédaction).

NB. Les corrections des planches de travaux dirigés et des sujets de travaux pratiques ne seront disponibles qu'après les séances.

  1. Raisonnement, logique propositionnelle
  2. Ensembles, logique des prédicats
  3. Calcul booléen
  4. Relations, applications
  1. Combinatoire
  2. Probabilités discrètes (en travaux)
    • Planche de td 6 (correction)
    • Sujet de tp 6 (correction)
    • Test de connaissance
  3. Groupes
  4. Arithmétique
Les vidéos d'Eric Schrafstetter ci-dessous permettent également de mieux appréhender ces notions :
  1. Les relations.
  2. Relations d’équivalence.
  3. Lois et structures.
  4. Exemple de groupe (jeu Merlin).

Quelques démonstrations sont difficiles et demandent une certaine maturité pour être lues et comp­ri­ses. Elle ne sont évidemment pas exigées en première année mais permettent aux étudiants d'y re­ve­nir dans la suite de leur cursus.

Les exercices disséminés dans les chapitres ont été rassemblés dans les planches de travaux dirigés. La plupart des démonstrations demandées dans les exercices ne sont que des ap­pli­ca­tions directes des définitions des objets concernés. Les exercices marqués par le symbole † sont un peu plus difficiles et ceux marqués par le symbole ‡ sont plutôt des petits problèmes.

Les sujets de travaux pratiques sont présentés à la fin des chapitres. S'ils n'ont pas pu être traités intégralement durant les séances, ils sont censés être achevés chez soi. Certaines questions comp­lé­men­tai­res de pro­gram­ma­tion sont proposées pour les plus rapides et peuvent également être étudiées chez soi.

Prérequis

Le programme de mathématiques de la licence d'informatique peut difficilement être abordé par des étudiants qui ne sont pas titulaires d'un bac scientifique dans lequel ils ont choisi l'option mathématiques en première et en terminale (avec de bons résultats !) Il faut impérativement garder à l'esprit que l'enseignement de l'informatique dans une ufr de Sciences et Techniques n'est pas de nature technologique mais scientifique, même si certains aspects technologiques y sont abordés.

L'expérience montre que les étudiants qui n'ont pas d'appétence pour les mathématiques échouent, la lecture du premier chapitre de ce cours devrait lever certaines ambiguités et éviter quelques ma­len­ten­dus trop répandus, voire entretenus, concernant l'informatique.

Objectifs

Cet enseignement de première année couvre la partie algébrique du pro­gram­me de ma­thé­ma­ti­ques pour l'in­for­ma­ti­que, l'étude des éléments d'analyse est quant à elle, assurée dans un mo­du­le commun avec la li­cence de mathématiques au premier semestre. Ce cours aborde les notions basiques et fondamentales — mais pas pour autant triviales — de l'algèbre et in­tro­duit les principales structures qui ne sont qu'effleurées dans les en­sei­gne­ments gé­né­raux de ma­théma­tiques à l'Université. Ces éléments sont absolument in­con­tour­nab­les pour faire des études d'in­for­ma­ti­que, la très grande majorité des modèles et structures qui y sont utilisées sont de simples trans­po­si­tions 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é­cia­li­sés cor­res­pon­dants 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 toujours 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 et ainsi d'animer la structuration 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 puis­se 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 au lieu 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 les démonstrations que nous destinons aux êtres humains. Le volume horaire par étudiant que nous avons attribué aux tp représente le 1/3 des enseignements, 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 mises à 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*(*) Jacques Wolfmann, ma­thé­ma­ti­cien fran­çais spé­cia­lis­te de la théo­rie des co­des (1938-2018†)..

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 ou firefox, avec lesquels 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 et nouveaux termes sont récapitulés en tête de chapitre sous le sommaire et dirigent le lecteur à la position où ils/elles ont été introduit·e·s. Un terme ou un groupe de termes distingué de cette manière est un hyperlien vers sa définition.

Les chapitres contiennent des applications interactives 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

Modalités

Évaluation. L'évaluation des connaissances en première année se fait suivant le contrôle continu intégral. Les épreuves de contrôle continu sont obligatoires et sont constituées de :

  1. Un contrôle continu intermédiaire d'une durée de 1h20 en amphi contenant des qcm et des questions rédactionnelles.
  2. Un contrôle de travaux pratiques d'une durée de 2h15 en salle de tp.
  3. Un contrôle terminal sous la forme d'une épreuve écrite de 2h15 contenant des qcm, une ou plusieurs questions de programmation Python et un ou plusieurs exercices à rédiger.

Absence. Toute absence à une épreuve, de quelque nature que ce soit, doit être justifiée à l'administration dans un délai maximum de \(3\) jours après la fin de la période d'absence, faute de quoi la note de l'épreuve est \(0\).

En cas d'absence justifiée à une épreuve :
  1. Une épreuve de substitution vous est imposée.
  2. Sinon, vous pouvez en faire la demande officielle dans le même délai de 3 jours que votre justificatif d'absence. S'il ne s'agit pas du contrôle terminal, cette épreuve peut vous être refusée, mais dans ce cas le contrôle continu manqué est neutralisé.
L'absence à une épreuve de substitution est toujours sanctionnée par la note \(0\).

Notation. Si l'on désigne par \(\color{#88F}C\) la note du contrôle intermédiaire, \(\color{#F44}P\) la note de travaux pratiques et \(\color{#F44}T\) celle du con­trô­le terminal, alors la note finale \(F\) à cet ecue est calculée à partir de la formule suivante :

\begin{align} \label{eq:F} F&:=\max \{\frac{({\color{#88F}C}+ {\color{#F44}P}+{\color{#4F4}T})}{3},{\color{#4F4}T}\}. \end{align}

Annales des épreuves écrites

Les épreuves écrites et les épreuves de travaux pratiques de l'année scolaire 2019-2020 ont été annulées et remplacées par des épreuves en ligne à cause du confinement lors de l'épidémie de covid19 et l'évaluation est en contrôle continu intégral depuis l'année scolaire 2022-2023, il n'y a donc plus de session 2.

  1. Session 1 - Session 2 (2018-2019)
  2. Session 1 - Session 2 (2020-2021)
  3. Session 1 - Session 2 (2021-2022)
  4. Sujet (2022-2023)
  5. Sujet (2023-2024)
Vous avez eu les notes aux contrôle intermédiaire et au contrôle de travaux pratiques respectivement. Quelle note entière minimale \(T:=\,\) devriez-vous obtenir au contrôle écrit terminal pour valider votre ecue si l'on n'applique pas la règle du max, c'est-à-dire si \(F=\frac{1}{3}(C+P+T)\) ?

nb. Les notes des contrôles continu et du contrôle terminal sont entières.

Il suffit d'isoler \(T\) dans l'inégalité suivante : \[\frac{1}{3}(C+P+T)\geq 10 \quad\text{soit}\quad T\geq 30-(C+P).\] Autrement dit, puisque la note \(T\) est supposée entière : \[T:=\left\lceil 30-(C+P)\right\rceil\] où \(\lceil x\rceil\) désigne le plus petit entier supérieur ou égal au réel \(x\). Pour l'exemple proposé, \(T=\ \)?

Bibliographie

Ce cours est l'adaptation de notes personnelles, elles-mêmes inspirées de certains chapitres de nom­breux ou­vra­ges dont les plus remarquables sont :