Mardi 7 janvier 2014 12h—15h / Aucun document autorisé
Contents
1. e 1 sin l Si f n O nl 8 5 avec e gt 0 alors t n O nle amp Si f n O nl amp alors t n G n amp logn Si f n Q nl amp pour e gt 0 et si dc lt 1 tel que a f 2 lt c f n pour n assez grand alors t n O f n Soient a gt 1 b gt 1 f n une fonction positive et t n Exemples pour le probl me sur les r seaux de m tro Questions 1 amp 2 Les matrices Direct Directe Direct et Direct de l exemple sont 0 90 oo 180 oo oo 270 0 180 360 90 oo 270 90 0 90 oo 180 Loo oo oo oo oo oco oco co oo oo oo oo 1180 0 180 90 oo 90 oo Dee cS 180 90 0 90 Direct 5 360 180 0 270 90 oo loo oo oo oo oo 1 90 oo 90 270 0 oo 180 oo oo oo oo oo oo co coo oo oo oo oo coo oo oo oo 00 oo 270 oo 90 90 180 0 oo 270 180 90 O0 oo oo oo oo oo oo oo 0 E h Re M up 3 oo oo oo 0 90 180 180 90 270 270 lo 0 oo oo oo oo oo 90 0 oco 90 oco oo oco 180 co 0 90 oo 90 180 oo 0 90 90 90 90 Directa co oo 90 0 oo 180 oo Direct 180 90 90 0 270 180 90 90 rho oo 0 oco 90 oo 90 270 0 co 180 oo co oo 90 180 0 oo co oo 90 180 oo 0 o o oo co co oo oo 270 oo 90 90 180 oo 0 O0 co oo oo oo oo oo oo 0 270 180 oo 90 oco oo oo 0 Questions 3 amp 4 La matrice D et la matrice Viao de l exemple sont amp 3 e m c 0 92. 0 180 180 90 510 270 270 0 1 2 1 2 2 1 90 0 420 90 420 510 420 180 1 000100000 1 180 420 0 90 90 90 90 420 2 0 3 2 3 2 D 180 90 90 0 270 180 90 90 Vias de 1 1 3 0 2 3 2 1 90 420 90 270 0 420 180 600 2 2 2 0 2 510 510 90 180 420 0 420 510 o 3 3 0 co 270 420 90 90 180 420 0 420 2 2 2 2 oo 0 270 180 420 90 600 510 420 0 1 1 1 co oo 0 4 4 1 3 1 5 e IEn EC mT We ORIRE DRE a ET TA E R GE EE E E D D
3. Universit Paris Diderot M1 Informatique Ann e 2013 2014 Examen d algorithmique Mardi 7 janvier 2014 12h 15h Aucun document autoris Mode d emploi Le bar me est donn titre indicatif La qualit de la r daction des algorithmes et des preuves sera tr s fortement prise en compte pour la note On peut toujours supposer une question r solue et passer la suite Exercice 1 Diviser pour r gner 2 points Ecrire un algorithme Diviser pour r gner qui prend un tableau en param tre et qui renvoie une paire constitu e de la valeur minimale et de la valeur maximale du tableau Donner sa complexit Justifier l algorithme Exercice 2 Flots 2 points On consid re le r seau de transport de la figure ci dessous Appliquer l algorithme de Ford Fulkerson pour trouver un flot maximal On donnera tous les flots interm diaires et les graphes des augmentations obtenus par l algorithme En d duire une coupe de capacit minimale du r seau 5 Exercice 3 Calcul de notes 3 points On cherche calculer les notes de semestre d tudiants qui ont pass plusieurs unit s d enseignement chacune d elle re oit un coefficient repr sentant un nombre de cr dits Pour valider un semestre un tudiant doit valider 30 cr dits Il a pu suivre et valider un ensemble d UEs qui d passent les 30 cr dits et pour calculer sa note finale on cherche trouver les UE valid es qui lui permettent d obtenir so
4. conna tre les distances en temps s parant deux stations sur la ligne Pour cela on va construire une matrice Direct de taille n x ns telle que le coefficient Direct j k avec 1 lt j k lt ns repr sente le temps pour aller de la station j la station k par la ligne i et il vaudra oo si les deux stations ne sont pas reli es par la ligne 1 et il vaudra toujours 0 pour les coefficients de la diagonale Direct k k On donne en annexe les matrices Direct Direct et Directs de l exemple Donner un algorithme pour construire Direct partir de L Donner sa complexit 2 partir des n matrices Direct Direct donner un algorithme pour construire une matrice Direct de dimension n x n qui contient les temps minimaux pour aller d une station une autre par un trajet direct sans correspondance le coefficient Direct j k repr sente le temps minimal pour aller de j k par un trajet direct avec une des lignes du r seau et oo si il n y a pas de trajet direct entre elles et 0 pour les l ments de la diagonale Quelle est sa complexit on donne en annexe la matrice Direct de l exemple 3 On veut pr sent construire des matrices D de dimension n x n contenant les temps minimaux pour aller d une station une autre en au plus k changements de lignes correspondances Bien s r on a Do Direct Donner un algorithme pour calculer les matrices D D pour un k fix On pourra notamment cal
5. culer Di partir de D et Do en suivant les id es classiques de la programma tion dynamique Ici on supposera que tout changement de ligne toute correspondance prend A 240 secondes Quelle est la complexit de cet algorithme on donne en annexe la matrice D de l exemple 4 On souhaite pr sent trouver l itin raire correspondant aux temps minimaux ins crits dans Dg Par exemple pour D 6 1 qui vaut 510 le trajet est de la station 6 prendre la ligne 3 puis changer la station 3 et prendre la ligne 2 et descendre la station 1 Pour cela on va construire en m me temps que les matrices D des matrices Via de dimension n x n telles que le coefficient Via 5 est le num ro de ligne du dernier tron on sur le trajet allant de i j en temps Di j bien s r si k 0 ou si Dofi j D fi 5 il n y qu un tron on et Via i j sera le num ro de ligne pour aller directement de 4 j On utilisera oo lorsque la liaison n existe pas et 0 pour la diagonale Donner un algorithme pour calculer les matrice Viaz Donner sa complexit on donne en annexe la matrice Viag de l exemple 9 A partir des matrices Do D1 Dj et Viao Via Vias comment retrouver tout l itin raire ici on se contentera des num ros de ligne prendre pour aller de i j en temps D i 3 4 Universit Paris Diderot M1 Informatique Ann e 2013 2014 Annexe Master theorem a t g f n sin gt 1
6. n et 0 lt v lt V tel que T i v vaut VRAI si et seulement si il est possible de trouver un sous ensemble de a a de somme v Justifier l algorithme et donner sa complexit 2 Appliquer l algorithme sur l exemple 2 8 3 7 et V 15 3 Adapter le au cas o on cherche un multi ensemble o un m me l ment a peut apparaitre plusieurs fois Par exemple pour E 2 8 3 7 et V 14 c est possible en prenant 7 7 Probl me Itin raire de m tro 8 points On consid re un r seau avec n stations num rot es de 1 ns et n lignes de m tro num rot es de 1 n La ligne est d finie par un tableau L d entiers de taille t L 1 et L t sont les num ros des deux stations extr mit s de la ligne Sur cette ligne les m tros peuvent aller dans deux directions de L 1 Li t ou de L t L 1 Dans la premi re direction la station L j 4 1 suit L j pour j 1 t 1 et dans la seconde direction c est L qui suit L j 1 Dans les deux cas on supposera toujours que le temps n cessaire pour aller de l une l autre est 90 secondes Dans la figure ci dessous on repr sente un r seau de m tro de 8 stations n 8 et 3 lignes n 3 9 G ad E Li 1 2 4 8 et t 4 La eee La 1 5 3 7 4 et to 5 La 6 3 4 et ia 3 Universit Paris Diderot M1 Informatique Ann e 2013 2014 1 Pour chaque ligne on veut
7. n semestre 30 cr dits avec la meilleure moyenne pond r e possible Pour cela il est possible de diminuer le coefficient 1 par le poids en cr dits Universit Paris Diderot M1 Informatique Ann e 2013 2014 d une UE si c est n cessaire pour arriver exactement 30 cr dits mais bien s r il n est pas possible d augmenter le cr dit d une note Par exemple supposons que les notes sont les suivantes avec le nombre de cr dits entre parenth ses 12 6 17 8 11 3 15 3 14 4 8 5 13 6 18 5 Il est alors pr f rable pour l tudiant de prendre les notes 12 6 d grad en 4 17 8 15 3 14 4 13 6 18 5 Cela lui donne une moyenne de 15 1 ie 453 30 Proposer un algorithme glouton pour calculer la meilleure moyenne possible Donner sa complexit Justifier votre algorithme Exercice 4 Sous ensemble de somme exacte 5 points On cherche r soudre le probl me suivant tant donn s un ensemble de n valeurs enti res E a1 05 04 et une valeur cible V on veut savoir si il est possible de trouver un sous ensemble de E dont la somme des l ments vaut exactement V Par exemple pour 2 8 3 7 et V 12 c est possible avec le sous ensemble 2 3 77 mais si on prend V 14 ce n est pas possible 1 Proposer un algorithme de programmation dynamique pour r soudre ce probl me On cherchera construire un tableau Bool en deux dimensions Tfi v o 0 lt i lt
Download Pdf Manuals
Related Search