 | | |
| MATH0064-1 | Mathématiques discrètes II
|
|
| Durée : | 30h Th, 30h Pr |
|
| Nombre de crédits : |
|
|
| Nom du professeur : | Michel Rigo |
|
Langue(s) du cours :
|
| Langue française |
|
Organisation et évaluation :
|
| Enseignement au deuxième quadrimestre |
|
Contenus du cours :
|
| Dans ce cours de mathématiques discrètes, on aborde principalement les thèmes suivants : théorie des graphes, étude des suites linéaires récurrentes (sur un anneau quelconque), introduction à la cryptographie et aux codes correcteurs. Ces sujets trouvent de nombreuses applications : tournées de distribution, flot et réseaux, coloriages, problèmes de dénombrement en combinatoire, sécurisation du commerce électronique, problème d'authentification, partage de secrets, ....
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. Pour une introduction à la théorie des graphes, plusieurs thèmes pourront être abordés : plus court chemin, connexité, tri topologique, théorie de Perron-Frobenius, Page Rank, arbres couvrants, planarité, coloriage, théorie de Ramsey. |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| Au terme de ce cours, l'étudiant maîtrisera des notions fondamentales issues de la théorie des graphes, de la cryptographie (RSA et sa mise en oeuvre, logarithme discret,...) et des suites linéaires récurrentes (séries formelles et génératrices, matrice compagnon, corps fini, nombres de Catalan,...) ainsi que les preuves et raisonnements sous-jacents. L'étudiant aura appréhendé la structure de graphe et intégré les concepts de cryptosystème à clé privée/publique et de chiffrement. Il/elle sera capable d'expliquer et d'appliquer les différents mécanismes pouvant apparaître lors de la recherche d'une formule clause pour une suite linéaire récurrente. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| De bonnes bases en algèbre générale (groupes, anneaux, espaces vectoriels et corps finis) sont nécessaires pour aborder le cours (cours de 2e bachelier en mathématique ou équivalent). |
|
Activités d'apprentissage prévues et méthodes d'enseignement :
|
| Cours théorique avec "tableau et craies" en interaction avec les étudiants. Dans les séances d'exercices, les étudiants sont face à des exercices qu'ils doivent résoudre ou à des situations qu'ils doivent implémenter sur machine. |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| 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. |
|
Lectures recommandées ou obligatoires et 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/
Quelques compléments :
- R. Diestel, Graph Theory, 3rd Edition, Graduate Text in Math. 173, Springer, (2005).
- C. Berge, Graphes et hypergraphes, Dunod, Paris, (1970).
- C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Text in Math. 207, Springer (2001).
- C. Meyer, A. Langville, Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, (2006).
- E. Seneta, Non-Negative Matrices, An Introduction to Theory and Applications,
George Allen and Unwin Ltd, London, (1973).
- J. Buchmann, Introduction to cryptography, Second edition, Undergraduate Texts in
Mathematics, Springer, (2002).
- R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics, A foundation for
computer science, Second edition, Addison Wesley, (1994).
- A. Salomaa, Public-Key Cryptography, Second edition, Texts in Theoretical Computer
Science, An EATCS Series, Springer, (1996).
- J. Talbot, D. Welsh, Complexity and Cryptography, An Introduction, Cambridge Univ.
Press (2006).
- H. Wilf, Generatingfunctionology, Academic Press (1994).
|
|
Modalités d'évaluation et critères :
|
| L'examen en session comporte une partie orale (énoncés et preuves de résultats, avec discussion) et une partie écrite. La partie écrite concerne uniquement la résolution d'exercices. La partie orale porte sur la théorie et ses applications directes. |
|
Stage(s) :
|
| |
|
Remarques organisationnelles :
|
| Des compléments d'information sont disponibles sur
http://www.discmath.ulg.ac.be/
On peut en particulier y consulter le journal de bord de l'année en cours et aussi celui des années précédentes. |
|
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 |
|
|
|
| Notes en ligne : |
|
|
| |
