ESSI1 2002-2003

Mathématiques Discrètes

 

Contrôle du Mercredi 22 Janvier

Durée : 3 heures

Documents autorisés : cours et TD

 

 

 

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

Les correcteurs se réservent le droit  d’enlever des points pour toute énormité donnée comme réponse.

 

 

Exercice 1

 

L’algorithme A1 a une complexité en Q(n), l’algorithme A2 a une complexité en Q(n²), l’algorithme A3 a une complexité en Q(n ln (n)), l’algorithme A4 a une complexité en Q(2ⁿ).

 

Question 1 : Si la taille de la donnée n est doublée, qu’arrive t-il au temps de calcul de A1, A2, A3 et A4 ?

 

Question 2 : Pour n=10, lequel de ces algorithmes est-il le plus rapide ?

 

Exercice 2

Question1 : Montrer par induction que la méthode sum suivante retourne .

Question 2 : Déterminer la complexité de cette méthode.

 

//On suppose que  0 £ min £ max < d  où d est la dimension du tableau A.

static int sum(int[] A, int min, int max){

            int mid;

            if(min == max) {

return A[min];

}

 

            else if (max-min == 1) {

return A[min] + A[max];

}

 

else {

mid = (min + max)/2;

                        return sum(A,min,mid) + sum(A,mid+1,max);

            }

}

 

 

 

 

Exercice 3

Résoudre l’équation de récurrence suivante

            u₀=1, u₁=1, u_n=2u_n-2+u_n-1+n²

 

Question 1 : En donnant le résultat sous une forme asymptotique

Question 2 : En donnant la forme exacte du résultat

 

Exercice 4

Les sommets du graphe orienté G_n sont les mots de longueur n sur l’alphabet {0,1,2}. Il y a un arc du sommet x=x₁x_2…x_n vers le sommet y=y₁y_2…y_n si et seulement si

 il existe j, 1£j£n tel que

            "i, i¹j, x_i=y_i

            y_j=x_j+1 modulo 3

 

Question 1 : Combien G_n a-t-il de sommets, d’arcs ?

Question 2 : Quelle est la distance maximum entre deux sommets de G_n ?

Question 3 : Le graphe non orienté obtenu en supprimant l’orientation de G_n est-il biparti ?

 

Exercice 5

Soit l’alphabet A = {0,1}. On appelle langage tout sous–ensemble de A* et on rappelle que le mot vide est noté  e. Si L et M sont deux langages de A*, on note

• LM = {u Î A*/ $ p Î L, $ q Î M : u = pq}.
• L^r  l’ensemble des mots miroirs des mots de L.
• L*  le langage défini  inductivement par le schéma  S_L :

Base : e Î L*

Règle : Si m Î L et  m’Î L*    alors mm’Î L*

 

Question 0 : Soient L₁ = {1,10}, L₂ = {e,0}, déterminer L₁.L₂, L₁^r et L₂*.

 

Question 1 : Donner un langage L pour lequel le schéma S_L est libre et un langage L pour lequel le schéma S_L  ne l’est pas.

 

Question 2 : Monter que L*L* = L*.

 

Question 3 : Que dire de (L*)* ?

 

 

On dit qu’un langage est régulier s’il appartient à l’ensemble de langages R  défini inductivement par

Base : {e}, {0}, {1}sont dans R

Règles :

R1 : Si L et M appartiennent à E, alors L È M appartient à R

R2 : Si L et M appartiennent à E, alors LM appartient à R

R3 : Si L appartient à E, alors L* appartient à R

 

Question 4 : le schéma précédant est-il libre ?

Question 5 : L₁ et L₂ appartiennent-ils à R  ?

Question 6 : Montrer par induction structurelle sur R  que si L est dans R  alors L^r l’est aussi