Module Math3-Alg3 : Combinatoires, arithmétiques et graphes

Table of Contents

1 Prérequis

Module Math1-Bases3 et Math3-Alg1

2 Objectif d'apprentissage

Le but du cours est de faire un tour d’horizon de différentes méthodes combinatoires autour de deux grands thèmes, la théorie des graphes et la théorie des nombres.

3 Descriptions des enseignements

3.1 Combinatoire

  • Principe de combinatoire: preuves par bijections, principes des bergers, double comptage (application aux égalités entre coeffcients binomiaux), principe des tiroirs, principe d’inclusion-exclusion (application au comptage de surjections)
  • Utilisation des séries génératrices pour déterminer un cardinal

3.2 Graphe:

  • Notions de base sur des graphes: graphe orienté, non orienté, isomorphisme, degré, lemme de la poignée de main, différents types de représentation.
  • Problèmes de chemins dans un graphe: longueur d’un chemin à partir de la matrice d’adjacence, connexité, k-connexité, chemin eulerien, chemin hamiltonien.
  • Arbres: différentes caractérisation des arbres, arbre orienté, notion de rang dans un graphe orienté sans circuit.
  • Coloration: coloration de sommet, nombre chromatique, notion de stable et de clique, polynôme chromatique, coloration d’arêtes, indice chromatique, Théorème de Vizing.
  • Planarité: graphe planaire, formule d’Euler et applications, coloration de graphe planaire, Théorème de Kuratowski (peut être admis).
  • Initiation à la méthode probabiliste à travers divers exemples.

3.3 Autres thèmes qui peuvent être abordés dans les graphes:

  • Initiation à la théorie de Ramsey.
  • Couplage : notion de couplage, couplage dans les graphe bipartis (théorème de Hall), couplage stable, Algorithme de Gale-Shapley, théorème de Tutte.
  • Problèmes d’optimisation pour les graphes valués: recherche d’arbre couvrant de pois maximal (algorithmes de Prim et Kruskal), recherche de plus court chemin (algorithmes de Bellman-Ford-Kalaba et Dijkstra-Moore), problème de flots dans les transports (algorithme de Ford-Fulkerson).

3.4 Théorie des nombres

  • Nombres premiers: arithmétique élémentaire, décomposition en nombres premiers, crible, quelques idées sur la distribution des nombres premiers (théorème d’Euclide, inégalités de Tchebychev, exemple de suite arithmétique contenant une infinité de nombre premier).
  • Equations diophantiennes: équation du type ax+by=c, triplets pythagoriciens, méthode de descente infini, entiers comme somme de quatre carrés.
  • Fonctions arithmétiques: fonctions arithmétiques élémentaires, convolution de Dirichlet et inversion de Moebius et applications au calcul de la fonction d’Euler.
  • Approximation diophantienne: théorème de Dirichlet, mesure d'irrationalité, théorème de Liouville, exemples de nombres transcendants
  • Fractions continues
  • Résidus quadratiques: Symbole de Legendre. Loi de réciprocité quadratique.

3.5 Autres thèmes qui peuvent être abordés en théorie des nombres:

  • Notion sur la théorie des partitions: fonctions génératrices, comportement asymptotique du nombre de partitions
  • Série de Dirichlet et applications aux développements asymptotiques élémentaires de fonctions arithmétiques
  • Formes quadratiques entières: Représentabilité d'un entier par une forme quadratique. Classes d'équivalence. Réduction.
  • Géométrie des nombres: convexes et réseaux, théorèmes de Minkowski.

4 Références

  • Éléments de théorie des graphes Alain Bretto, Alain Faisant, François Hennecart
  • Graph Theory and application Jean Claude Fournier
  • Théorie des Graphes J.A. Bondy et U.S.R. Murty
  • Théorie Des Nombres. Daniel Duverney
  • Introduction à la théorie des nombres Jean-Marie De Koninck Armel Mercier

Author: genzmer yohann

Created: 2021-11-19 ven. 14:37

Validate