L’UE MAT3137L aura 12 semaines d’enseignement: 3H CM (lundi 8h00-11h15) et TD (mardi 9h45-13h00 et vendredi 9h45-11h15).
Planning dans ADE: ici
CM : Jiang Zeng;
TD A : Alexis Tchoudjem (50%) et Gadi Perets (50%);
Il y a un CP (120 minutes) et un CT (120 minutes).
Note de CC : la moyenne pondérée du CP (50%) et du CT (50%).
0. Introduction. L'équipotence est une relation entre ensembles, selon laquelle deux ensembles sont équivalents lorsqu'il existe une bijection entre eux. I. Ensembles finis. Segments de N. Lemmes fondamentaux sur les injections/surjections entre deux segments. Notion d'ensemble fini. Ensembles infinis. II. Ensembles dénombrables. Théorème de Cantor. Lemme fondamental. Notion d'ensembles dénombrables. Produit d'ensembles dénombrables. Réunion d'ensembles dénombrables. Ensembles infinis non dénombrables. Exemple (Nombres transcendants). III. Compléments d'ordre culturel. Notion de cardinal. Le théorème de Cantor-Schröder-Bernstein. L'hypothèse du continu.
1. Quelques principes fondamentaux de dénombrement. Principe de somme, principe de produit, principe des bergers, principe des tiroirs, principe d'inclusion-exclusion. 2. Coefficients binomiaux et interprétations combinatoires: mots, sous-ensembles, chemins dans un réseau. Formule du binôme de Newton. Nombres de Stirling de 2e espèce, nombres de Bell et nombres de Catalan. Partitions d'entier. Douze facettes d'une application entre deux ensembles finis.
Arithmétique de Z. Sous-groupes de (Z, +). Divisibilité, division euclidienne, pgcd et ppcm, théorème de Bézout, congruences, nombres premiers. Lemme d'Euclide-Gauss. Théorème fondamental de l'arithmetique. Petit theoreme de Fermat. Theoreme de Wilson. Algorithme d'Euclide et algorithme de Bezout. Résolution d'équation diophantienne ax+by=c. Congruences dans Z (construction de Z/nZ). Equations linéaires modulo n. Algorithme d'inversion. Théorème des restes chinois. Application a la cryptographie a clefs publiques.
Groupes. 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, groupe symétrique. 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. Indicateur d' Euler. Theoreme d'Euler.
Anneaux unitaires. Produit fini d’anneaux, sous-anneau, morphisme et isomorphisme 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.
Graphes. 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 d'adjacence associée à un graphe, recherche du plus court chemin sur un graphe pondéré connexe (algorithme de Dijkstra), coloriage de graphes, exemples d’application.