Combinatoire et Algèbre 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 : 8h-9h30 (mardi) et 14h-17h15 (jeudi), Jérôme Germoni;

TD B : 8h-13h (mardi), Jean-Michel Brochet.

MCC: 50% CC (moyenne de 4 DS de 1h30) et 50% CT (3 heures).

Algèbre et mathématiques discrètes - MAT3137L

PROGRAMME DE L’UNITE D’ENSEIGNEMENT :

Combinatoire. Cardinaux des ensembles finis, dénombrabilité, exemples de Z, Q et R.

Arithmétique de Z. 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 (1h, mardi 17/10)

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. 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 (1h, jeudi 09/11)

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.

CC3-4 (1h30, lundi 11/12)

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 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.

 
 
Valid XHTML 1.0 Valid CSS Driven by DokuWiki