Le cours
Le cours de mathématiques discrètes est présenté au travers de l'étude de problèmes concrets et ludiques, ou supposés comme tels pour un scientifique. L'objectif est de prendre conscience que les théories mathématiques ne sont pas détachées des aspects pratiques et qu'elles ont souvent été développées pour répondre à des questions concrètes. En résumé, la théorie c'est pratique.
Le premier problème abordé est celui du paradoxe des anniversaires: dans une classe, à partir de combien d'étudiants est-il plus probable que tous soient nés le même jour plutôt qu'un jour différent de l'année ? Nous abordons les ensembles, la cardinalité, les fonctions et la combinatoire pour y répondre. Nous revenons étudions sur ce faux paradoxe dans la partie cryptographie un peu plus tard.
Le deuxième problème est celui du taquin. Le taquin est constitué d'un plateau carré sur lequel coulissent horizontalement et verticalement 15 pièces numérotées de 1 à 15. La position initiale (et historique) des 15 pièces de ce casse-tête est la suivante:
Le problème consiste à ranger correctement les pièces 14 et 15 pour que toutes les pièces soient numérotées dans l'ordre de lecture, si cela est possible. Vous pouvez faire vos propres tentatives avec le jeu ci-dessus. Il suffit de cliquer sur une case sur la même ligne ou la même colonne que la case vierge pour déplacer toute la rangée. Nous étudions le groupe des permutations pour répondre à cette question.
Le troisième problème est de trouver comment envoyer des messages secrets sans que ceux-ci soient déchiffrable par le premier venu. C'est un prétexte pour aborder les bases de l'arithmétique et quelques algorithmes fondamentaux pour étudier quelques protocoles simples, comme le chiffrement affine. Nous introduisons également la notion de chiffrement à clef publique.
Le dernier problème est celui du loto-foot. Il s'agit de faire un pronostic sur n rencontres de foot, c'est-à-dire de choisir pour chacune des n rencontres entre la victoire de l'équipe à domicile (choix 1), de l'équipe visiteurs (choix 2) ou le match nul (choix N). On gagne si l'on trouve au moins n - e bons résultats (actuellement n = 15 et e = 3). Chaque bulletin joué couvre évidemment plusieurs résultats possibles puisqu'on gagne avec moins de e erreurs. La question est de savoir s'il est possible de bien choisir ses bulletins pour maximiser le nombre de résultats couverts par ces bulletins, ou réciproquement se fixer les résultats que l'on veut couvrir et déterminer les bulletins à jouer optimalement.
| # | DOMICILE | GRILLE | VISITEURS |
| 1 | AC AJACCIO | | BORDEAUX |
| 2 | NANCY | | REIMS |
| 3 | NICE | | LORIENT |
| 4 | TROYES | | SOCHAUX |
| 5 | VALENCIENNES | | BREST |
| 6 | VIT. ARNHEIM | | PSV EINDHOV. |
| 7 | LAZIO ROME | | NAPLES |
| 8 | EVIAN | | MARSEILLE |
| 9 | RENNES | | TOULOUSE |
| 10 | INTER MILAN | | CH. VERONE |
| 11 | MANCHESTER U | | EVERTON |
| 12 | CAGLIARI | | MILAN AC |
| 13 | FC BARCELONE | | GETAFE |
| 13 | LYON | | LILLE |
Deux sujets devraient être abordés pour compléter un cours de mathématiques pour l'informatique, mais le volume d'heure est insuffisant pour y parvenir : la logique et les probabilités discrètes.
Documents pédagogiques
Les mémos de cours
Les planches de td
Sujets d'examen