Partiel du 16 novembre 2010

Description

Partiel du 16 novembre 2010

Sujets

• Arts

Informations

• Publié par: okemepar
• Nombre de lectures: 75
• Langue: Français

Extrait

Algorithmique — M1

Partiel du 16 novembre 2010 Corrig

On applique les cours

Exercice 1(1 point) –RÉcurrence Ètant donn que 3 T(n) =27T(bn/3c) +3n+logn trouvez le comportement asymptotique deT(n). Justifiez votre rponse. 3 Correction.On applique le Master theorem aveca=27, b=3, f(n) =3n+logn. L’exposant estk=loga= b k log 3 27=3, et puisquef(n) =Θ(n)on a la perturbation moyenne. On conclut par Master theorem que : k 3 T(n) =Θ(nlogn) =Θ(nlogn). Exercice 2(2 points) –La science Un chercheur souhaite assister À un nombre maximum de confrences durant le mois de d- cembre. Les dates prvues sont : Le colloque des savants1-12 dcembre. Le colloque des ignorants8-10 dcembre. La petite confÉrence sur les grands graphes14-15 dcembre. La grande confÉrence sur les petits graphes3-19 dcembre. La semaine des automates18-25 dcembre. La journÉe des grammaires11 dcembre. Le workshop de Nol :24-31 dcembre. 1.?C’est une instance d’un problme vu en cours. Lequel Correction.Ordonnancement des sances de cinma dans une salle. 2.Expliquez l’algorithme de cours pour ce problme. (inutile de prouver sa correction) Correction. Trier les confrences selon la date de fin. Plan= vide ; fin=0 ; pour i de 1 À n : Si d[i] >fin Plan = Plan U {i} ; fin = f[i] ; retourner Plan 3.Appliquez cet algorithme et trouvez la solution du problme. Correction.On classe les confrences selon la fin : 8-10; 11-11; 1-12; 14-15; 3-19; 18-25; 24-31. On prend 8-10, puis 11-11, on laisse 1-12 (en conflit), on prend 14-15, on laisse 3-19, on prend 18-25, on laisse la dernire. Conclusion :on peut assister À 4 confrences maximum : 8-10, 11-11, 14-15 et 18-25

1