ESSI1 2002-2003

Mathématiques Discrètes

 

Contrôle du Vendredi  15 Novembre

Durée : 2 heures

Documents autorisés : cours et TD

 

 

 

 

 

 

 

 

Toutes vos réponses doivent être accompagnées d’une preuve ou d’un contre-exemple.

Le barème est donné à titre indicatif, et les correcteurs se réservent le droit  d’enlever des points pour toute énormité donnée comme réponse.

 

 

 

 

 

Exercice 1  (7 points)

On rappelle que l’on a définit en cours l’ensemble LP des mots bien parenthésés comme étant l’ensemble défini inductivement par

Base : eÎLP

Règle : m et m’ Î LP   Þ(m)m’ Î LP  

 

Soit E l’ensemble défini inductivement par

Base : eÎE

Règle : m et m’ Î E   Þ(m)(m’) Î E 

 

1)      A-t-on E inclus dans LP ?

2)      A-t-on  LP inclus dans E ?

3)      Le schéma définissant E est-il libre ?

 

 

 

 

 

 

Exercice 2 (5 points)

Soit l’alphabet A={1,0}, définir inductivement le sous ensemble de A*, formé de mots ayant un nombre impair de 0.

Votre schéma est-il libre ?

 

 

 

Exercice 3 (8 points)

On définit inductivement l’ensemble S des suites d’entiers naturels par le schéma libre suivant

Base : e est dans S

Règle : Si s Î S et n ÎN, alors s’=sÅn Î S

 

L’opérateur Å ajoute l’entier n en fin de suite.

On pourra si on le souhaite utiliser les opérateurs dernierElement (de S dans N) et debut ( de S dans S)  qui sont définis sur les suites non vide par :

            dernierElement(sÅn)=n

            debut(sÅn)=s

 

1)      On suppose que l’on a une fonction maxDansNxN de NxN dans N, définir inductivement la fonction maxDansS de S dans N, qui retourne le plus grand élément de la suite (on pourra si on le souhaite donner une valeur à maxDansS([])

2)      Définir inductivement la fonction longueur de S dans N, qui compte le nombre d’éléments de S (distincts ou non)

3)      Définir inductivement, la fonction egal de SxS dans {vrai, faux} qui teste l’égalité de deux suites (deux suites sont  égales si elles ont la même longueur et contiennent les mêmes entiers dans le même ordre)

4)      Définir inductivement la fonction inclus de SxS dans {vrai,faux}. La suite s est incluse dans la suite s’, si on peut l’obtenir à partir de s’ en « rayant » des éléments de s’ , sans modifier l’ordre.