 | |
| MATH0252-1 | Mathématiques discrètes
 |
|
| Durée : | 30h Th, 30h Pr |
|
| Crédits/ECTS : |
|
|
| Titulaire(s) : | Michel Rigo |
|
| Langue : | Langue française |
|
| Aperçu général : | Dans ce cours de mathématiques discrètes, on aborde principalement les thèmes suivants : étude des suites linéaires récurrentes (sur un anneau quelconque), introduction à la cryptographie et aux codes correcteurs. Ces sujets trouvent de nombreuses applications : problèmes de dénombrement en combinatoire, sécurisation du commerce électronique, problème d'authentification, partage de secrets, .... Pour la partie cryptographique, on présente quelques cryptosystèmes classiques à clé privée ainsi que les cryptosystèmes à clé publique du type RSA ou basé sur le problème du logarithme discret. |
|
| Objectif du cours : | En se basant sur des connaissances classiques en algèbre acquises lors des deux premières années du cursus, on étudie les suites linéaires récurrentes (sur un anneau, sur un champ ou sur un champ fini). On donne quelques techniques de résolution des suites linéaires (par des méthodes exactes mais aussi par des méthodes approchées au moyen d'une analyse asymptotique élémentaire). Comme application, on passe en revue plusieurs problèmes de dénombrement comme le comptage du nombre de mots bien parenthésés. Ensuite, on présente certains aspects classiques de la cryptographie moderne : systèmes à clé privée, à clé publique, cryptosystème RSA, problème du logarithme discret, cryptanalyse, génération aléatoire de grands nombres premiers, algorithmes de factorisation, fonctions de hachage,... (Suivant le temps disponibles, on pourra aussi s'intéresser aux cryptosystèmes construits sur une courbe elliptique.) On s'intéresse en particulier aux algorithmes mis en oeuvre et à leur complexité. En guise d'illustration, des implémentations sont réalisées sous Mathematica. Enfin, on présente une introduction élémentaire aux codes correcteurs d'erreurs. Le cours s'intéresse principalement aux aspects théoriques, les nombreuses applications n'étant qu'esquissées. |
|
| Pré-requis : | De bonnes bases en algèbre générale (groupes, anneaux, espaces vectoriels) sont nécessaires pour aborder le cours (cours de 2e bachelier en mathématique ou équivalent). |
|
| Organisation : | Le cours est consacré principalement aux aspects théoriques. Les séances de répétition permettent de présenter la résolution d'exercices et l'illustration ou la concrétisation des concepts vus au cours. On pourra envisager d'implémenter certains algorithmes lors de ces séances d'exercices (par exemple, on pourra illustrer les concepts cryptographiques dans un logiciel du type Mathematica). L'horaire des cours et des séances d'exercices sera communiqué en début d'année. Il est à noter que ce cours n'est organisé que tous les deux ans. |
|
| Notes de cours : | Des notes reprenant l'ensemble de la matière enseignée au cours théorique seront distribuées aux étudiants en début d'année. Ces notes sont téléchargeables sur http://www.discmath.ulg.ac.be/ (http:///) |
|
| Evaluation : | L'examen en session comporte uniquement une partie orale. Cet examen porte sur la théorie et ses applications directes (on pourra par exemple demander de résoudre au tableau un petit exercice). La matière de l'examen et les modalités d'interrogation seront précisées par un affichage aux valves. |
|
| Contacts : | M. Rigo
Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
| Remarques : | Des compléments d'information sont disponibles sur
http://www.discmath.ulg.ac.be/ |
|
|
| |
