Algèbre et mathématiques discrètes

Organisation générale

L’UE aura 12 semaines d’enseignement (Seq. 3+1M ={lundi matin, mardi matin, jeudi après-midi}): 3H CM et 4H30 TD par semaine en moyenne. Les horaires de CM et TD sont variables.

CM : Jiang Zeng;
TD A : Jiang Zeng (50%) et Alexis Tchoudjem (50%).
TD B: Gadi Perets

Modalité d'évaluation

Il y a trois CC's (pas de rattrapage) et un CT (+un rattrapage pour CT).

Note de CC : la moyenne des deux meilleures notes parmi trois notes de CC.

Note de l'UE: 60 % CC + 40% CT.

PROGRAMME DE L’UNITE D’ENSEIGNEMENT

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

Chapitre 2. Arithmétique de Z. Divisibilité, division euclidienne, pgcd, théorème de Bézout, congruences, nombres premiers. Résolution de ax+by=c.

Chapitre 3. Congruences. Théorème d'Euler. Petit théorème de Fermat. L’anneau Z/nZ : inversibles, indicatrice d’Euler, théorème d’Euler. Théorème chinois.

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

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

Notes de cours.

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

Notes sur polynômes .

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

Diapo du cours.

Algorithme de Dijkstra.

Références: Graph Theory with Applications (Chapitre 1). Bondy and Murty ici

Dates, sujets et corrigés de CC

CC1: vendredi 09/10 8h30–9h30 sujet - Corrigé.

CC1bis: amphi Jordan, jeudi 22/10 17h30–18h30 sujet - Corrigé.

CC2: amphi Jussieu, jeudi 18/11 14h00–15h30sujet - Corrigé.

CC3: amphi Jordan, jeudi 10/12 10h30–12h00 (en prévision)

Fiches TD

 
 
Valid XHTML 1.0 Valid CSS Driven by DokuWiki