ESSI1 1999-2000

Informatique Théorique

Mathématiques Discrètes

 

Examen du 31 Janvier 2000

 

 

Documents autorisés : cours

Durée : 3 heures

Déterminer si le  raisonnement  suivant est correct .

Si Superman était capable et désireux d’éliminer le mal, il le ferait. Si Superman n’est pas capable d’éliminer le mal, il est sans pouvoir. S’il n’est pas désireux d’éliminer le mal, il est maléfique. Superman  n’élimine pas le mal. Si Superman existe il n’est ni sans pouvoir ni maléfique.

Donc Superman n’existe pas.

Soit A ={0,1,2,3,4}. On considère le graphe G_k dont les sommets sont tous les mots de longueur k sur l’alphabet A. Deux sommets x₁ x₂ . x_k et y₁ y₂ . y_k sont reliés par une arête si et seulement il existe un unique j entre 1 et k tel que x_i= y_i pour tous les i différents de j et x_j= y_j +1 modulo 5 ou x_j = y_j -1 modulo 5.

a)       Dessiner G₁ et G₂.

b)       Combien G_k a-t-il de sommets ? Quel est le degré d’un sommet ? Combien y a-t -il d’arêtes ? Quelle est la distance maximum entre deux sommets ?

c)       Le graphe est-il biparti ?

 

1.        Soit A={0,1,2}. Donner un schéma inductif libre pour l’ensemble E des mots sur A ne commençant pas par un zéro et ne comportant pas deux zéros consécutifs.

2.        On interprète un mot de E comme la représentation d'un nombre entier en base 3. Par exemple 102 représente 11, et 22 représente 8.

Soit  L₀ (resp. L₁) l 'ensemble des mots de E qui représentent un entier pair (resp. impair) . On note p_n le nombre de mots de longueur n dans  L₀ et i_n le nombre de mots de longueur n dans  L₁. Déduire du schéma de la première question  des relations de récurrence liant les p_n et les i_n

3.        Résoudre 

 

On considère le programme java récursif suivant  où b est une constante entière

On suppose défini un objet table à partir d’une  classe Table dérivée de la classe Vector en y ajoutant la méthode table.echanger (int i, int j) qui échange  table.elementAt(i) et table.elementAt(j).

 

public void T(int debut, int fin){ // opère sur la Table  table dans la tranche table[debut..fin]

int n=fin-debut+1 ; //la dimension de la tranche

if (n>1)   { if (n=2) {// tri par ordre croissant des deux éléments de la tranche

if (table.elementAt(debut)>table.elementAt(fin)) {table.echanger(debut, fin) ;}}

               else {      T( debut, debut+n/b) ;

                               T( fin-n/b, fin) ;

                               T(debut, debut+n/b) ;

                       }

               }

}

 

a)       Etablir la relation de récurrence vérifiée par la complexité de cet algorithme

b)       Si b=3/2, (dans ce cas bien sûr l’algorithme utilise la partie entière de n/b) quelle en est la complexité ?

c)       Question bonus : démontrer que si b=3/2, T est un tri