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

2004–2005

Contrôle de Mathématiques Discrètes du 4 Novembre 2004

Nom : Prénom : Groupe:

1

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

Il faut connaître un schéma inductif libre définissant 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.

– Suivant(0) = 1

– Suivant(1) = 2

– Pour m ≠ 0, Suivant(m0) = m1

– Pour m ≠ 0, Suivant(m1) = Suivant(m)0 Pour le code recursif voir EcritureBinaire.java

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.

– Sup(m,ϵ)= vrai

– Sup(ϵ,1m’)= faux

– Sup(ϵ,0m’)= faux

– Sup(0m,0m’)=Sup(m,m’)

– Sup(0m,1m’)= faux si longueur (m)≤ longueur (m’)

– Sup(0m,1m’)= Sup(m,1m) si longueur (m)> longueur (m’)

– Sup(1m,0m’)= vrai si longueur (m)≥longueur (m’)

– Sup(1m,0m’)= Sup(1m,m’) si longueur (m)<longueur (m’)

– Sup(1m,1m’)= faux si longueur (m)< longueur (m’)

– Sup(1m,1m’)= vrai si longueur (m)> longueur (m’)

– Sup(1m,1m’)= Sup(m,m’) si longueur (m)= longueur (m’)

Deuxième solution – Sup(m0,m’0)=Sup(m,m’)

– Sup(m1,m’1)=Sup(m,m’)

– Sup(m0,m’1)=Sup(m,suivant(m’))

– Sup(m1,m’0)=Sup(m,m’)

– Sup (m,ϵ)= vrai

– Sup(ϵ,m1)=faux

– Sup (ϵ,m0)=Sup(ϵ,m) Troisième solution valable sur l’ensemble EcrituresBin×EcrituresBin et non sur {0,1}^{∗}×{0,1}^{∗}.

– Sup(m,0)= vrai

– Sup(m,suivant(n))= faux si m = n

– Sup(m,suivant(n))= Sup(m,n) sinon

en utilisant le schéma suivant – Base = {(0,0)}

– (m,0) →(suivant(m),0)

– (m,n) →(m,suivant(n))

code laissé à l'imagination du lecteur....

NB. Il est clair que cette question n’était pas très facile et il en a été tenu compte lors de la correction.

4

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.

– Mul(m,0) = 0

– Mul(m,1) = m

– Pour m′ ≠ 0, Mul(m,m′0) = Mul(m,m′)0

– Pour m′ ≠ 0, Mul(m,m′1) = Σ(Mul(m,m′)0,m) Pour le code recursif voir EcritureBinaire.java

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.

– faireP alindrome(ϵ) = ϵ

– faireP alindrome(am) = amfaireP alindrome(m)a

public mot fairePalindrome (mot m){
if (m.vide()) {return m ;}
return m.pL().concat(fairePalindrome()).concat(m.pL()) ;
}

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.

– P refixe(ϵ,m′) = vrai

– Si m ≠ ϵ, P refixe(m,ϵ) = ϵ

– P refixe(am,bm′) = ((a = b) et P refixe(m,m′))

public boolean prefixe (mot m, mot m'){
if (m.vide()) {return true ;}
if (m'.vide()) {return false ;}
return (m.pL()==m'.pL())&& prefixe(m.fM(),m'fM());
}