Algèbre et mathématiques discrètes

Organisation générale

L’UE aura 12 semaines d’enseignement : 3H CM et 4H30 TD par semaine. Les horaires de CM et TD sont variables.
CM : Lundi de 9h45 à 13h00, Riccardo Biagioli;
TD : Jusqu'au 04/11 : mardi de 14h00 à 17h15 et vendredi de 9h45 à 11h15, Riccardo Biagioli.
Apres le 04/11 : mardi de 14h00 à 17h15 et jeudi de 14h00 à 15h30, Gadi Peretz.


Règles d'évaluation

L'évaluation sera faite sur la base des notes obtenues lors de 4 contrôles continus (CC) et d'une épreuve commune anonyme terminale (ECA). La note finale sera calculée de la façon suivante : 60% de la moyenne des 3 meilleures notes parmi les 4 CC + 40% de la note de ECA. On vous rappelle que la note de deuxième session remplacé seulement la note de l'ECA. Les dates des CC sont reporté sur la section Contrôles ci-dessous.


Avancement du cours


Chapitre 1 : Combinatoire et théorie des ensembles

Méthodes combinatoires de base. Coefficients binomiaux. L'ensemble des parties. Principe d'inclusion-exclusion. Dénombrement des fonctions injectives et surjectives de [p] à [n]. Partitions d'ensembles et nombres de Stirling de deuxième espèce. Relations d'équivalence et d'ordre. Cardinaux des ensembles finis, infinis, dénombrables. Théorème de Cantor-Bernstein : s'il existe une injection f de l'ensemble non vide A à l'ensemble B, et une injection de B dans A, alors il existe une bijection de A sur B. Théorème de Cantor : il n'existe pas de surjection d'un ensemble E dans l'ensemble de ses sous parties P(E). Ensembles bien ordonnés. L'ensemble N est bien ordonné. Lemme de Zorn. Axiome du choix. Théorème de Zermelo : tout ensemble peut être muni d'une relation de bon ordre. LZ ⇒ AC. LZ ⇒ TZ. Comparaison des cardinaux. L'ordre sur les cardinaux est total.

Références : Notes Ch1. Preuve du Théorème de Cantor-Bernstein.

Chapitre 2 : Arithmétique

Nombre premiers, division euclidienne, gccd et ppcm. Lemme de Gauss et décomposition en facteurs premiers. Congruences. L'ensemble quotient Z/pZ. Petit théorème de Fermat. Théorème de Wilson.

Références : Note Ch2 (de M@ths en Ligne, Université de Grenoble).

Chapitre 3 : Groupes

Définition de monoïde et groupe. Exemples. Produit direct de groupes. Sous-groupes, le centre d'un groupe, les sous-groupes de Z. Classes modulo un sous-groupe. Théorème de Lagrange. Sous-groupes engendrés par une partie d'un groupe ; groupes monogènes, cycliques. Ordre d'un groupe et d'un élément. Groupe symétrique. Décomposition d'une permutation en cycles disjoints, comme produit de transpositions et transpositions simples. Signature et ordre d'une permutation. Morphismes de groupes, isomorphismes, noyau et image d'un morphisme. Théorème de Cayley. Sous-groupes normaux. Le noyau est un sous-groupe normal. Groupes quotients, projection canonique. Premier théorème d’isomorphisme de groupes. Caractérisation des groupes monogènes et cycliques.

Références : Premiers trois chapitres du livre Introduction à la théorie des groupes (de François Bergeron, Luc Bélair et Christophe Hohlweg).

Exercices supplémentaires sur le groupe des permutations.

Chapitre 4 : Anneaux et corps

Définition d'anneaux et sous-anneaux, exemples, premières propriétés. L'anneau Z/nZ et les entiers de Gauss Z[i]. Le groupe des unité U(A) d'un anneau A. Définition de corps et d'anneaux intègres. Tout corps est intègre. Un anneau intègre fini est un corps. La caractéristique d'un corps. Morphismes d'anneaux. L'anneau A[X] n'est jamais un corps. Notion d'idéal. Le noyau d'un morphisme est un idéal. Idéaux principaux. Quotient d'un anneau par un idéal. Idéaux premieres et maximaux et caractérisation des anneaux quotients correspondants. L'anneaux des polynômes A[X]. Division des polynômes, elements associés, PGCD, PPCM, identité de Bézout, algorithme d'Euclide. Polynômes irréductibles, décomposition en facteurs irréductibles dans K[X], K corps. Les cas K=C et K=R. Polynômes primitifs de Z[X], contenu, critère de Eisenstein.

Références : Notes sur l'anneau des polynômes et critères d'Eisenstein.

Chapitre 5 : Graphes

Définition de graphe et premiers exemples. Graphes isomorphes. Graphes simples. Matrices d'incidence et d'adjacence d'un graphe. Degré d'un sommet. Séquences de degrés : sequences réalisables ou non. Chemins dans les graphes : chemins simples , élémentaires, cycles. Nombres des chemins de longueur k dans un graphe. Graphes connexes. Théorèmes d'existence de cycles. Problème du plus cours chemin : algorithme de Dijkstra. Cycles eulériens, graphes eulériens, caractérisation.

Références : Graph Theory with Applications. Bondy and Murty.http://www.zib.de/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf


Fiches TD

Controles

Examen final

 
 
Valid XHTML 1.0 Valid CSS Driven by DokuWiki