Mathématiques Discrètes

ESSI 1

2001-2002

 

 

Examen du Vendredi  16 Novembre 2001

 

Durée : 2 heures

Les documents sont autorisés. Toutes vos réponses doivent être justifiées.

 

Exercice 1 [Ce type d’exercice a été vu plusieurs fois en TD et devoir, une rédaction particulièrement soignée est donc requise]

Soit Var et Op deux ensembles finis disjoints.

Soit E l'ensemble défini inductivement par

                Base : Var Ì E

Règle  E₁ , E₂ÎE, wÎOp Þ  E₁w ( E₂ ) ÎE

 

1) Montrer que tous les mots de E vérifient les deux propriétés suivantes

i)                     m contient autant de (  que  )

ii)                   tout préfixe propre de m contient au moins autant de (  que de )  

 

2) Montrer que le schéma définissant E est libre .

 

Exercice 2

1)Montrer que les polynômes P non nuls en x à coefficients dans R peuvent être définis inductivement par             

Base  c Î R -{0} Þ p(x)=c Î P

                Règle p(x) Î P, c ÎR Þ q(x)=xp(x)+c Î P

2) Montrer que le schéma définissant P est libre

3) Définir inductivement la fonction Degré :   P ® N , qui associe à tout polynôme son degré

4) Définir inductivement la fonction X2 : P ® P , telle que  X2(p(x)) = p(x²)

5) Définir inductivement la fonction  Calcul :  P x R ® R , qui calcule la valeur de p(x) pour un x dans R donné.

 

 

Exercice 3

Donnez et prouvez une définition inductive pour l'ensemble des mots binaires comportant un nombre pair de zéro. Votre schéma est -il libre ?