Mathématiques pour l'informatique [ue12, ue22]

Si vous avez manqué la première séance du cours et par conséquent la distribution du document intitulé Memento-U12-U22, il faut le télécharger et le lire.

Organisation des enseignements

Cet enseignement est constitué des 8 chapitres présentés ci-dessous, les 4 premiers sont étudiés au premier semestre (ue12), les 4 derniers au second semestre (ue22) de la première année de la licence d'informatique.

Chaque chapitre fait l'objet de

pour un total de 48he par ue. Les liens vers les corrections des planches de travaux dirigés et des travaux pratiques ne sont actifs qu'après la fin des séances correspondantes.

Partie I (UE-12 / Semestre 1) Partie II (UE-22 / Semestre 2)
  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 illustrent certaines notions étudiées dans ce cours :

  1. Les relations.
  2. Relations d’équivalence.
  3. Lois et structures.
  4. Exemple de groupe.

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 parfois qu'effleurées dans les en­sei­gne­ments gé­né­raux de ma­théma­tiques à l'Université. Ces éléments sont 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é, pourquoi on n'est pas nécessairement malade alors qu'un test fiable à 99% affirme qu'on l'est, 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 1h00 en amphi contenant des qcm et des questions rédactionnelles.
  2. Un contrôle de travaux pratiques d'une durée de 1h30 en salle de tp.
  3. Un contrôle terminal sous la forme d'une épreuve écrite de 1h45 contenant des qcm, une ou plusieurs questions de programmation Python et un ou plusieurs exercices à rédiger.

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&:=\frac{{\color{#88F}C}+ {\color{#F44}P}}{4}+\frac{{\color{#4F4}T}}{2}. \end{align}

Absence. L'absence à une épreuve est sanctionnée par la note \(0\). Cependant, une épreuve de substitution peut être organisée à l'appréciation de l'enseignant et au cas par cas si dans les 3 jours qui suivent la période d'absence :

  1. L'absence a été dûment justifiée à la scolarité.
  2. L'étudiant en a fait la demande.

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 lors du confinement pendant l'épidémie de covid19. L'évaluation s'est faite sous le régime du contrôle continu intégral les années scolaires 2022-2023 et 2023-2024, il n'y avait pas de seconde session.

  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 ?

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{C+P}{4}+\frac{T}{2}\geq 10 \quad\text{soit}\quad T\geq 20-\frac{C+P}{2}.\] Autrement dit, puisque la note \(T\) est supposée entière : \[T:=\left\lceil 20-\frac{C+P}{2}\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 largement inspirées de chapitres de nom­breux ou­vra­ges dont les plus remarquables sont :