Algorithmique — M1 — Université Paris Diderot Coorigé (béta 1.1) du partiel du

Algorithmique — M1 — Université Paris Diderot Coorigé (béta 1.1) du partiel du 28 novembre 2008 Exercice 1 : applications de cours 1.1. Récurrence Étant donné que T(n) = 9T(⌊n/3⌋) + n2 + 3 trouvez le comportement asymptotique de T(n). Justifiez votre réponse. Correction : On applique le Master Theorem. On trouve d’abord l’exposant k = log3 9 = 2. On remarque que la perturbation est n2 + 3 = Θ(n2) = Θ(nk) - c’est donc le cas de perturbation moyenne. D’où, par le Master Theorem, on obtient que T(n) = Θ(n2 log n). 1.2. Cinéma Les séances au cinéma “PRG-Algo” ont lieu aux horaires suivants : A :08h10-11h ; B :9h15-10h20 ; C :10h-13h ; D :11h-13h20 ; E :13h10-15h ; F :13h15-14h45 ; G :14h-17h ; H :14h50-18h ; L’étudiant a une journée libre et il veut voir le maximum de films pendant cette journée. 1. Quel algorithme de cours résout ce problème ? Décrivez l’algorithme en français ou en pseudo-code. Correction : C’est le même problème que l’affectation de salle (vue en cours). L algorithme glouton, vu en cours, est le suivant : Trier les requêtes (di, fi) en ordre ascendant de f T=0 pour i de 1 à n faire si di >= T aller au séance i T = fi 2. Appliquez l’algorithme pour choisir les films à voir. Correction : On trie les séances selon l’ heure de la fin : BACDFEGH On prend B, T=10 :20, on saute A et C, on prend D, T=13 :20, on saute F et E, on prend G, T=17, on saute H. On verra donc 3 films seulement : B,D,G. 1 Exercice 2 : Greedy - un algorithme facile à inventer Sur la rue Gloutonne il y a n maisons avec les coordonnées x1, x2, . . . , xn (données du problème). Une ligne de bus passe par cette rue. On cherche à placer les arrêts de bus de manière que pour chaque maison il y ait un arrêt à moins (ou=) de 100 m. Trouver le nombre minimal m et les coordonnées de tels arrêts a1, . . . , am. 1. Pour x1 = 180, x2 = 200, x3 = 370, x4 = 390, x5 = 590 faire un dessin et trouver une solution optimale. Correction : Deux arrêts suffisent : a1 = 280 desservira trois premières maisons, a2 = 490 les deux autres 2. Proposer un choix glouton pour le premier arrêt. Correction : On suppose que les maisons sont placé dans l’ordre croissant de numéros x1 < x2 < · · · < xn (si ce n’est pas le cas, il faut faire un tri en pré-traitement). Choix glouton : on met le premier arrêt à 100 mètres après la 1ère maisons (c.-à-d. a1 = x1 + 100). 3. Proposer un algorithme glouton qui résout le problème, Correction : On trie si nécessaire. On fait le choix glouton pour placer le premier arrêt. On saute toutes les maison desservis par cet arrêt, on refait la même procédure pour les maisons qui restent non desservis. Pseudo-code (variable Z désigne la fin de zone desservie, m=le nombre d’ arrêts déjà faits) Trier les maisons en ordre ascendant de xi Z = −∞ pour i de 1 à n faire si xi > Z //première maison pas encore desservie m++ ; //on ajoute un arrêt am = xi + 100 ; //100 mètres après la maison Z = am + 100 ; //et on déplace la frontière de la zone 4. Énoncer et démontrer le lemme du choix glouton. Correction : Lemme 1 Il existe une solution optimale où le premier arrêt (le plus à gauche) a la position a1 = x1 + 100 Démonstration : Soit A = a1, . . . , am une solution optimale quelconque (on suppose que les arrêts sont classés dans l’ ordre croissant des coordonnées. Forcément la maison la plus à gauche xi est desservie par un arrêt ai ( on a donc ai <= x1 + 100). Si on avance ce premier arrêt utile vers la droite à la nouvelle position x1 + 100, il desservira encore la maison x1 et toutes les autres maison qui étaient desservies par ai. Tous les arrêts plus à gauche : a1..ai−1 ne servent à rien, on peut les supprimer. Ainsi (en poussant le premier arrêt utile et en supprimant les inutiles) on obtient une nouvelle solution optimale A′ avec a′ 1 = x1 + 100. CQFD Remarque Pour démontrer la correction de l’algorithme il faut aussi établir la sous-structure- op- timale : après avoir placé le premier arrêt comme décrit à a1 = x1 + 100, il reste à resoudre le même problème, mais seulement pour toutes les maisons après la position a1 + 100. 2 5. Analyser la complexité de votre algorithme. Correction : La boucle principale fait O(n). Le tri fait O(n log n). D’où la réponse : si les maisons sont déjà classés (et le tri est inutile) la complexité de l’ algorithme est O(n). S’ils ne le sont pas la complexité est de O(n log n). Exercice 3 : Divide & Conquer - adaptation d’un algorithme de cours Tout le monde connaît la séquence de Fibonacci 1,1,2,3,5,8,13,21,. . . définie par la récurrence :    F(1) = 1 F(2) = 1 F(n) = F(n −2) + F(n −1) pour n > 2 Il est très facile de calculer F(n) en temps O(n). Dans cet exercice on trouve un algorithme beaucoup plus efficace. 1. Montrer que le calcul de la suite de Fibonacci se ramène à celui de la résolution d’une équation matricielle récurrente. On notera ⃗ V (n) =  F(n) F(n −1)  un vecteur colonne à deux éléments et F une matrice carrée (2 × 2). On cherche F telle que :  ⃗ V (2) = constante ⃗ V (n) = F · ⃗ V (n −1) Correction : On a ⃗ V (2) =  1 1  , ce qui est une constante. D’ autre part, pour n > 2 on a ⃗ V (n) =  F(n) F(n −1)  = F(n −1) + F(n −2) F(n −1)  =  1 1 1 0  · F(n −1) F(n −2)  = F · ⃗ V (n −1), avec F =  1 1 1 0  CQFD 2. Montrer que la solution de cette équation de récurrence s’écrit ⃗ V (n) = Fn−2 · ⃗ V (2). Correction : Preuve par récurrence. Base :⃗ V (2) = F0⃗ V (2) est trivial. Pas inductif : Supposons que c’est vrais pour n−1 : ⃗ V (n−1) = Fn−3 · ⃗ V (2). Alors ⃗ V (n) = F⃗ V (n−1) = F · Fn−3 · ⃗ V (2) = Fn−2 · ⃗ V (2) CQFD. 3. En déduire un algorithme (qui ressemble beaucoup à un algorithme de cours) de type « diviser pour régner » calculant F(n) pour tout n, et prouver que sa complexité est O(log(n)) en terme de nombre d’opérations arithmétiques. Correction : On a vu en cours un algorithme "diviser pour régner" de calcul de puissances. Il s’adapte parfaitement aux puissances de la matrice F. 3 int[.,.] fonction Puissance (F,n) si n=0 retourner I sinon si n=1 retourner F sinon si n est pair M= Puissance (F, n/2) retourner Mult(M,M) sinon // si n est impair M= Puissance (F, (n-1)/2) retourner Mult (Mult(M,M),F) En sachant que pour les matrices de taille fixe 2 × 2, l’opération de multiplication a un coût fixe O(1) (en nombre d’opérations arithmétiques), on obtient pour la complexité de cet algorithme la récurrence T(n) = T(⌊n/2⌋) + O(1), d’où, par Master Theorem T(n) = O(log n). Finalement, pour calculer le n-ème élément de la séquence de Fibonacci F(n) on applique la formule prouvée ⃗ V (n) = Fn−2 · ⃗ V (2). La complexité est O(log(n −2)) + O(1) ce qui se simplifie à O(log n). 4. Montrer par un cas particulier que cet algorithme d’élévation à la puissance n n’est pas optimal. Prendre par exemple : n = 15. Correction : L’algorithme "diviser pour régner” donne pour n = 15 le calcul suivant M 15 = M ∗(M 7)2 = M ∗(M ∗(M 3)2)2 = M ∗(M ∗(M ∗M 2)2)2. Ça fait 6 opération : 3 carrés et 3 multiplications avec M. Or, en réfléchissant on trouve un calcul avec 5 multiplications A = M ∗M ∗M; B = A ∗A; C = B ∗A; M 15 = B ∗C. Exercice 4 : Backtracking On considère le problème (NP-complet) classique de 3-matching. Il y a n garçons G = {g1, . . . , gn}, qui veulent épouser n filles F = {f1, . . . , fn} et s’installer dans n maisons M = {m1, . . . , mn}. Un ensemble S contient plusieurs triplets de la forme ijk qui représentent les souhaits. Ainsi un triplet ijk signifie que gi et fj sont d’accord de se marier uploads/s3/ corrige-partiel-2008.pdf

Tags
Administrationcorrection algorithme maison configuration complexité
Documents similaires
  • 34
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager