>>> MATHEMATIQUES DISCRETES

MATHEMATIQUES - Semestre 2 (sous réserve du vote du CEVU)

Nombre de crédits

Semestre(s)

Volume Horaire

Précisions volumes horaires

Structure de rattachement

Autre(s) Structure(s) de rattachement

(Co)Responsable(s)

M. Ciligot-Travain

Campus d'enseignement

Contenu

I. Arithmétique

1. Divisibilité dans Z : Définition et propriétés ; Division euclidienne.

2. Arithmétique modulaire : Définition et premières propriétés de la congruence sur Z modulo N ; La congruence est une relation d'équivalence sur Z ; Compatibilité de la congruence avec l'addition et la multiplication.

3. PGCD : Définition du pgcd de deux entiers et premières propriétés ; Théorème de Bachet-Bézout ; Entiers premiers entre eux ; Théorème de Gauss ; Algorithme d'Euclide et algorithme d'Euclide étendu ; Résolution de l'équation diophantienne de degré 1 : ax+by=c ; PPCM.

4. Nombres premiers : Définition et premières propriétés ; Il existe une infinité de nombres premiers; Valuation p-adique, décomposition en facteurs premiers (Théorème fondamental de l'Arithmétique).

II. Théorie des graphes

Graphes orientés et non orientés : définition et exemples. Graphes eulériens et théorème d'Euler. Graphes hamiltoniens et théorème d'Ore. Matrice d'adjacence. Distance. Coloriage des sommets d'un graphe. Problème de plus court chemin.

Calendrier