Cours Master 1 Informatique Parcours MPRI: Combinatoire et Calcul algébrique

Bienvenue sur le site web du cours «Combinatoire et Calcul Algébrique» du Parcours MPRI du Master 1 Informatique de la faculté d’Orsay de l’Université Paris Saclay

Organisation

  • 6 séances de 3h30 + 1 séance d’oraux / soutenances de mini projet

  • Enseignants: Adeline Pierrot (AP), Florent Hivert (FH), ~~Viviane Pons (VP)~~, Nicolas Thiéry (NT); deux séances chacun

Programme

Ce cours est une introduction aux outils mathématiques pour le calcul symbolique et la combinatoire, avec des applications par exemple en cryptographie ou au test logiciel via le tirage aléatoire. Nous adopterons une approche effective en s’attachant tant aux algorithmes qu’aux implémentations dans les systèmes de calculs.

Pour les travaux pratiques, nous nous appuyerons sur Python3, muni de sa bibliothèque de calcul SageMath.

Prérequis

Cours d’algorithmiques de L3, algèbre linéaire de L2 et Maths pour l’informatique

Évaluation

ECTS : 2,5 Session 1 : CC * 60% + ET * 40% Session 2 : ET * 100% 1

Séances: les mercredis 14h-17h30, PUIO E107

Séance 1, 3 novembre: Rappels d’algèbre (NT)

Séance 2, 10 novembre: Codes correcteurs (NT)

Séance 3, 17 novembre: Combinatoire énumérative (AP)

Séance 4, 24 novembre: Séries génératrices (AP)

Séance 5, 1 décembre: Polynômes : représentations / interpolation (FH)

Séance 6, 8 décembre: Polynômes : Multiplication, Divisions et Applications (FH)

Examen, 15 décembre

L’examen aura lieu sous forme de présentation orale avec temps de préparation sur des exercices donnés. Présentez-vous dans la salle à l’heure indiquée. On vous donnera avec des exercices à préparer pendant 20 minutes. Ensuite, vous nous présenterez vos résultats pendant 20 minutes. Les exercices porteront sur les différentes thématiques du cours et pourront impliquer des calculs avec Sage (amenez votre ordinateur!). L’accès aux documents de cours est autorisé.

Les horaires de début de préparation vous ont été communiquées par mail. Veuillez vous présenter 5 minutes avant.