Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrige partiel 2008 Algorithmique ?? M ?? Université Paris Diderot Coorigé béta du partiel du novembre Exercice applications de cours Récurrence Étant donné que T n T n n trouvez le comportement asymptotique de T n Justi ?ez votre réponse Correction On a

Algorithmique ?? M ?? Université Paris Diderot Coorigé béta du partiel du novembre Exercice applications de cours Récurrence Étant donné que T n T n n trouvez le comportement asymptotique de T n Justi ?ez votre réponse Correction On applique le Master Theorem On trouve d ? abord l ? exposant k log On remarque que la perturbation est n n nk - c ? est donc le cas de perturbation moyenne D ? o? par le Master Theorem on obtient que T n n log n Cinéma Les séances au cinéma ??PRG-Algo ? ont lieu aux horaires suivants A h - h B h - h C h- h D h- h E h - h F h - h G h- h H h - h L ? étudiant a une journée libre et il veut voir le maximum de ?lms pendant cette journée 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 ? a ?ectation de salle vue en cours L algorithme glouton vu en cours est le suivant Trier les requêtes di ? en ordre ascendant de f T pour i de à n faire si di T aller au séance i T ? Appliquez l ? algorithme pour choisir les ?lms à voir Correction On trie les séances selon l ? heure de la ?n BACDFEGH On prend B T on saute A et C on prend D T on saute F et E on prend G T on saute H On verra donc ?lms seulement B D G CExercice Greedy - un algorithme facile à inventer Sur la rue Gloutonne il y a n maisons avec les coordonnées x x 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 m Trouver le nombre minimal m et les coordonnées de tels arrêts a am Pour x x x x x faire un dessin et trouver une solution optimale Correction Deux arrêts su ?sent a desservira trois premières maisons a les deux autres Proposer un choix glouton pour le premier arrêt Correction On suppose que les maisons sont placé dans l ? ordre croissant de numéros x x xn si ce n ? est pas le cas il faut faire un tri en pré- traitement Choix glouton on met le premier arrêt à mètres après la ère maisons c -à-d a x 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 ?n de zone desservie m le nombre d ? arrêts déjà faits Trier les maisons en ordre ascendant de xi Z ?? ?