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  (8 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 ?

 

 

1)      E est inclus dans LP, en effet on a vu en cours que les mots de LP formaient l’ensemble des mots vérifiant la propriété P :

P(m) :  d(m)=0 et d(p)³0 pour tout prefixe p de m, où la fonction d est la fonction qui compte le nombre de parenthèses ouvrantes moins le nombre de parenthèses fermantes.

On montre facilement par induction structurelle que tous les mots de E vérifient la propriété P :

Base : le mot vide vérifie P

Induction : Supposons que m et m’ vérifient P. Alors 

-         on a d ((m)(m’))=0.

-         Soit p un prefixe propre de (m)(m’). Considérons toutes les formes possibles pour p et montrons qu’à chaque fois, d(p) ³0

-                    p=(p_m où p_m est un prefixe de m, donc d(p) >0

-                    p=(m) , donc d(p) =0

-         p=(m)( p_m’ où p_m’ est un prefixe de m’, donc d(p) >0

 

2)      LP n’est pas inclus dans E, car () est dans LP mais pas dans E. 

 

3)      Le schéma définissant E est libre.

 

En effet, si un mot est dans la base, il ne peut pas être créé par la règle. Supposons qu’un mot m de E  puisse s’écrire à la fois sous la forme (m₁)(m₁') et (m₂)(m₂'), avec m₁,m₁',m₂,m₂' dans E. D'après la question  1 ,  m a un seul préfixe propre pour le quel le compteur d s’annule. Or d ((m₁))=d ((m₂))=0, on a donc (m₁)=(m₂) et par suite m₁=m₂ et donc aussi m_1’=m_2’.                                                                              

 

 

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.

 

Voir Exercice 3 de l’examen de Novembre 2001. Il n’y a que la base à changer.

 

Exercice 3 (7 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.

 

 

 

Pour les deux premières questions, on utilise la définition inductive libre de suites données dans l’énoncé.

            1)         maxDansS([])=0 ;

                   maxDansS(sÅn)=maxDansNxN(maxDansS(s),n)

 

      Ou si l’on préfere :

 

      Si s est vide maxDansS(s)=0,

      sinon maxDansS(s)= maxDansNxN(dernierElement(s), maxDansS(debut(s))

 

      2)         longueur([])=0

                  longueur(sÅn)= longueur(s)+1

 

Ou si l’on préfere :

 

      Si s est vide longueur(s)=0,

      sinon longueur(s)= 1+longueur (debut(s))

 

Pour les questions 3 et 4, on utilise la définition inductive libre des couples de suites CdS suivantes :

      Base ([],[]) est un CdS

            Règles

                        Si ([],s’) Î CdS et n’ ÎN, alors ([],s’Ån’) Î CdS

                        Si (s,[],) Î CdS et n ÎN, alors (sÅn,[]) Î CdS

                        Si (s,s’) Î CdS et n,n’ ÎN alors (sÅn, s’Ån’) Î CdS

 

      3)         egal([],[])=vrai

                  egal ([],s’Ån’)=faux

                  egal (sÅn,[]) = faux

                  egal (sÅn, s’Ån’)= (n=n’) et egal(s,s')

 

ou si l’on préfère

                  Si s=[], alors egal (s,s’)=(s’=[])

                             Sinon si (s’=[])  alors egal (s,s’)=faux

                                         Sinon egal(s,s’) =( (dernierElement(s)=dernierElement(s’)) et                                                                               (egal(debut(s), debut(s’)))

 

      4)         inclus([],s’)=vrai

                  inclus (sÅn,[])= faux

                  inclus (sÅn, s’Ån’)=((n=n’) et inclus (s,s')) ou (inclus (s, s’Ån’) )

 

ou si l’on préfère

                  Si s=[], alors inclus(s,s’)=vrai

                             Sinon si (s’=[]), inclus (s,s’)=faux

                                         Sinon inclus(s,s’)= (dernierElement(s)=dernierElement(s’) et                                                                    inclus (debut(s), debut(s’)))

                                                                            ou

                                                                            inclus (s, debut(s’)).