Mathématiques Discrètes

ESSI 1

Examen du premier février 2001

 

 

 

Toutes les réponses doivent être justifiées par un contre-exemple ou une preuve dont la rédaction doit être soignée.

Les documents sont autorisés mais pas les calculettes.

 

Exercice 1 (5pt)

On considère l’ensemble  B* des mots sur l’alphabet B={0,1}.

Soit M  le sous ensemble de B* constitué des mots ayant autant de 0 que de 1.

Soit E l’ensemble défini de manière inductive par

Base  eÎE

Règles    m ÎE  Þ 0m1 ÎE

 m ÎE  Þ 1m0 ÎE

 

a)       Le schéma définissant E est –il libre ?

b)       A-t-on M Ì E ?

c)       A-t-on E Ì M?

 

 

Exercice 2 (5 pt)

On considère l’ensemble  B* des mots sur l’alphabet B={0,1}.

Soit M  le sous ensemble de B* constitué des mots ayant autant de 0 que de 1.

Soit F l’ensemble défini de manière inductive par

Base  eÎF

Règles    m ÎF  Þ 0m1 ÎF

 m ÎF Þ 1m0 ÎF

 m,m’ ÎF Þ mm’ ÎF

 

 

b) Le schéma définissant F est –il libre ?

c) A-t-on M Ì F ?

d) A-t-on F Ì M?

 

 

Exercice 3 (5 pt)

Donner la forme générale des solutions de l’équation

 

Exercice 4 (5 pt)

Soient k et n deux entiers tels que k est compris entre 2 et n/2.

 On considère le graphe ayant n sommets numérotés de 0 à n-1, et tel qu’il y a une arête entre les sommets numérotés i et j si et seulement si |i-j| égal 1 ou k modulo n .

a)       Combien ce graphe a-t-il d’arêtes ?

b)       Quel est le diamètre de ce graphe ? Comment choisir k pour minimiser ce diamètre ?

c)       Ce graphe est-il biparti ?