Université de Nice-Sophia Antipolis École Supérieure en Sciences Informatiques

2004–2005

Controle de Mathématiques Discrètes du 4 Novembre 2004

Aucun document autorisé

Note :

Nom : Prénom : Groupe:

Durée : 55 minutes

1 2 3 4 5 6

Les solutions de ces exercices seront publiées sur la page web du cours de Mathématiques Discrètes, à partir de demain matin.

On supposera que si m est un mot, on dispose de la méthode m.vide() qui retourne vrai si et seulement si le mot est vide, et que si m est un mot non vide , on dispose des méthodes m.premiereLettre(), m.derniereLettre(), m.debutMot(), m.finMot(), m.longueur() qui retournent respectivement la premiere lettre de m, la dernière lettre de m, le mot m privé de sa dernière lettre, le mot m privé de sa première lettre, la longueur de m . Si vous le souhaitez vous pouvez racourcir l’écriture des noms de ces méthodes en m.pL(), m.dL(), m.fM(), m.dM(), m.l().On dispose aussi de la méthode m.concat(m′) qui retourne le mot mm′.

On pourra utiliser la fonction Σ vue en cours, telle que si m et m’ sont deux ecritures binaires, Σ(m,m′) = m” si et seulement si m” est l’ecriture binaire de val(m) + val(m′)

1

On veut définir de façon inductive une fonction inductive de E dans F. Que doit on connaître sur E?

2

Soit EcrituresBin l’ensemble des ecritures en base 2 (sans zéro inutile en tête).

Définir inductivement la fonction (sans faire appel à la fonction val)

Suivant : EcrituresBin → EcrituresBin telle que Suivant(m) soit l’écriture binaire de val(m) + 1 Donner aussi un code récursif.

3

Définir inductivement la fonction (sans faire appel à la fonction val) Sup : {0,1}^{∗} x {0,1}^{∗} → {vrai,faux} telle que Sup(m,m′) est vraie si et seulement si val(m) ≥ val(m′) Donner aussi un code récursif.

Définir inductivement la fonction (sans faire appel à la fonction val) Mul : EcrituresBin x EcrituresBin → EcrituresBin telle que mul(m,m′) soit l’ecriture binaire de val(m) ∗ val(m′) Donner aussi un code récursif.

5

Soit A un alphabet, définir inductivement la fonction faireP alindrome : A^{∗} → A^{∗} telle que faireP alindrome(m) est le mot palindrome dont la moitié gauche est m. Par exemple,

faireP alindrome(abc) = abccba Donner aussi un code récursif.

Soit A un alphabet, définir inductivement la fonction P refixe : A^{∗}xA^{∗} → {faux,vrai} telle que P refixe(m,m′) est vraie si et seulement si m est un prefixe de m′. Donner aussi un code récursif.