Algèbre et mathématiques discrètes
L’UE aura 12 semaines d’enseignement : 3h CM et 4h30 TD par semaine. Les horaires de CM et TD sont comme suit :
CM : 9h45-13h (lundi), Jiang Zeng;
TD A : 14h00h-19h00 (jeudi), Jean-Michel Brochet;
TD B : 8h-13h (mardi), Riccardo Biagioli.
MCC: 60% CC (moyenne de 3 CC de 1h30) et 40% CCF (3 heures)
Algèbre et mathématiques discrètes - MAT3137L
PROGRAMME DE L’UNITE D’ENSEIGNEMENT :
Analyse combinatoire élémentaire (1,5 semaine)
Principes combinatoires de base. Coefficients binomiaux. Dénombrement des injections et surjections entre deux ensembles finis. Nombres de Stirling de deuxième espèce. Permutations et partitions d'un ensemble fini. Principe d'inclusion-exclusion. Cardinaux des ensembles finis, ensembles dénombrables, exemples de Z, Q et R. Théorème de Cantor: il n'existe pas de bijection de A sur P(A), ensemble des parties de A.
Arithmétique de Z (2,5 semaines).
Anneau Z. Principes de récurrence, axiome de bon ordre de N. Sous-groupes de Z, divisibilité, division euclidienne, lemme de Gauss, pgcd, ppm, théorème de Bézout, algorithme d’Euclide, équation diophantienne ax+by=c, nombres premiers, congruences, l'anneau Z/nZ, caractérisations de éléments inversibles de Z/nZ, indicatrice d’Euler, petit théorème de Fermat, théorème d’Euler, théorème des restes chinois.
CC1 (1h30, mardi 16/10 à 8h)
Groupes (3 semaines)
Définition. Exemples. Produit fini de groupes, sous-groupe, sous-groupe engendré par une partie, sous-groupes de Z, exemples issus de l’algèbre linéaire et de la géométrie. Morphisme de groupes, image, noyau, isomorphisme de groupes. Groupes monogènes et cycliques, exemples de Z et Z/nZ. Ordre d’un élément et propriétés. Théorème de Lagrange. Application au Théorème d'Euler-Fermat. Groupe symétrique, cycles, théorème de factorisation en cycles, théorème de parité, groupe alterné.
CC2 (1h30, lundi 19/11 à 9h45)
Anneaux et corps (3 semaines)
Anneaux, sous-annaeaux, idéaux. Produit d'anneaux, morphismes d’anneaux, anneau intègre, anneau euclidien. Corps, sous-corps. Idéaux dans un anneau commutatif, interprétation de la divisibilité en termes d’idéaux, idéaux de Z. L’anneau Z/nZ : inversibles, théorème chinois, indicatrice d’Euler, théorème d’Euler.
Anneaux de polynômes à une indéterminée. Idéaux de K[X] où K est un sous-corps de C, pgcd, relation de Bézout, lemme de Gauss. Irréductibles de R[X] et C[X], décomposition en facteurs irréductibles. Critères d’irréductibilité dans Z[X] et Q[X] : polynômes primitifs dans Z[X], critère d’Eisenstein, réductions modulo p.
CC3 (1h30, mardi 10/12 à 11h30-13h00)
Graphes (2 semaine)
Sommets, sommets adjacents, arêtes, degré d’un sommet, ordre d’un graphe, chaîne, longueur d’une chaîne, graphe complet, graphe connexe, chaîne eulérienne, matrice adjacente associée à un graphe, recherche du plus court chemin sur un graphe pondéré connexe (algorithme de Dijkstra), coloriage de graphes, exemples d’application.
CCF (3h, janvier 2019).