ESSI 1 1998-1999

Mathématiques Discrètes

Examen du 29 Janvier 1999

 

 

 

Durée  3 heures

Tous documents autorisés

Le barème est donné à titre indicatif.

 

Donnez l’ensemble des solutions des équations de récurrences suivantes :

a)      

b)     

c)      

 

On se propose dans cet exercice de calculer la complexité de trois algorithmes dont le but est de fusionner les p listes triées de longueur n contenues dans un tableau de listes en une seule liste triée de longueur np.

On suppose qu’il existe une classe Liste contenant entre autre une méthode permettant de fusionner une liste l1 triée de longueur n₁ et un liste triée l2 de longueur n₂ en une seule liste triée de longueur n₁+n₂ et dont la signature est

public static Liste fusion (Liste l1, Liste l2)

et la complexité est en Q(n₁+n₂).

Question 1 (2 points)

Une première solution consiste en l’utilisation de la méthode suivante

 

public static Liste fusionMultiple(Liste[] mesListes) {

            Liste L=mesListes[1];

            for (int i=2; i < mesListes.length; i++){

                        L= Liste.fusion(L,mesListes[i]);

                        }

            return L;

}

 

Déterminer la complexité de cette méthode en fonction de n et de p.

 

Question 2 (2,5 points)

 

On suppose maintenant que p est une puissance de 2 et l’on  propose maintenant d’utiliser l’algorithme de multiFusion récursif suivant  :

           

        Pour multiFusionner p listes de taille n

            Si p=2 utiliser fusion

            Sinon    multiFusionner (récursivement) les p/2  première listes

                        multiFusionner (récursivement ) les p/2 dernières listes

                        Utiliser fusion pour fusionner le résultat des deux premières étapes.

 

Soit  c(n,p) = la complexité de la fusion de p listes de taille n par cette méthode.

 

a)       Déterminez la relation de récurrence suivie par cette suite, ainsi que c(n,2).

 

Posez d(n,p)=c(n,p)/n.

 

b)      Déterminez la relation de récurrence suivie par la suite d(n,p).

 

c)       Montrez qu’en fait d(n,p) ne dépend que de p.

On pourra par exemple montrer par induction sur p que

 

d)      Posez d(1,p)=f(p), et déterminez l’équation de récurrence suivie par f(p). Résoudre cette équation et en déduire c(n,p).

 

 

Question 3 (2,5 points)

On suppose toujours que p est une puissance de deux .

On se propose maintenant d’utiliser l’algorithme récursif suivant :

Pour multiFusionner p listes de taille n

            Si p=2 utiliser fusion

            Sinon    Utiliser fusion pour fusionner  deux à deux les listes initiales

                        multiFusionner (récursivement ) les p/2 listes de longueur 2n obtenues

                       

Soit c’(n,p) = la complexité de la fusion de p listes de taille n par cette méthode.

 

a)       Déterminer la relation de récurrence suivie par cette suite.

 

b)      Résoudre cette relation (vous pouvez procéder comme pour la question précédente).

 

 

 

 

Soit G un graphe non orienté. Soit V l’ensemble de ses sommets et E l’ensemble de ses arêtes. Un couplage de G est un sous-ensemble F de E tel que deux arêtes de F n’ont pas de sommets communs. Un couplage F de G est parfait si tout sommet de V est l’extrémité de l’une des arêtes de F.

Question 1(1point)

Montrer qu’un graphe admettant un nombre impair de sommets ne peut pas avoir de couplage parfait

Question 2 (1point)

Donner un couplage parfait du graphe ci-dessous

 

 

 

Question 3 (1 point)

Donner un exemple de graphe connexe ayant 4 sommets et n’admettant aucun couplage parfait.

 

Question 4 (2 points)

Dans toute la suite,  G est un  graphe biparti , c’est à dire dont les sommets sont répartis en deux sous-ensemble V₁ et V₂  tels que toute arête de G relie un sommet de V₁ à un sommet de V₂.

 

a) Montrer que si G admet un couplage parfait, alors  les cardinaux de V₁ et V₂  sont égaux.

 

Pour tout sous-ensemble U de V₁, on note G(U) le sous ensemble de V₂ constitué des sommets reliés à un sommet de U.

On dira qu’un graphe biparti admet la propriété P si et seulement si quel que soit U dans V₁, G(U) contient au moins autant de sommets que U.

 

b) Montrer que si G admet un couplage parfait, alors G admet la propriété P.

 

 

Question 5 (3 points)

On veut montrer par induction sur k que si G admet la propriété P, et que de plus les cardinaux de V₁ et V₂  sont tous les deux égaux à k alors G admet un couplage parfait.

 

a)       Prouvez le résultat si k=1 ou k=2

 

Supposez la propriété vraie pour tout k<n.

Soit G un graphe biparti admettant la propriété P et dont les cardinaux de V₁ et V₂  sont tous les deux égaux à n.

 

b)Placez vous dans le cas où pour  tout sous-ensemble U strictement inclus dans V₁ , le cardinal de G(U) est strictement supérieur à celui de U et montrez que G admet un couplage parfait.

 

c)Placez vous maintenant dans le cas où il existe un sous-ensemble U strictement inclus dans V₁ , tel que le cardinal de G(U) est égal à celui de U. Soit W le complémentaire de U dans V1. Soient les deux sous-graphes de G suivants :

·         G₁ dont les sommets sont ceux  de U et ceux de G(U) et les arêtes toutes celles de G reliant les sommets de U aux sommets de G(U)

·         G₂ dont les sommets sont ceux  de W et ceux de G(W) et les arêtes toutes celles de G reliant les sommets de W aux sommets de G(W)

 

Montrer qu’ils vérifient tous les deux la propriété P. En déduire que G admet un couplage parfait