Algorithmique et Programmation TD n 1 : Introduction 1 Mode
Contents
1. de hauteur 1 des feuilles de hauteur 2 et ventuellement des feuilles de hauteur 1 Lorsqu on coupe une feuille de hauteur 2 le noeud interne qui est son p re est clon fois On s int resse au nombre maximal de feuilles qui descendent du m me noeud interne Nmax Il peut y avoir plusieurs noeuds internes disons k ayant pr cis ment ce nombre de feuilles Cependant couper une de ces feuilles fait baisser de un le nombre de noeuds interne ayant Nmax feuilles en change de la cr ation de 7 noeuds internes ayant Nmax 1 feuilles Cela prouve qu en k coupes on peut faire baisser de 1 le nombre maximal de feuilles descendant du m me noeud interne Clairement la taille de l arbre r sultant de ces k coupes m me si elle est plus grande est toujours finie on a rajout i i 1 i k noeuds internes Cela prouve qu en un nombre fini d tapes on peut se ramener la situation o tous les noeuds internes qui seront certes en tr s grand nombre n ont plus de feuilles On a donc fait baisser de 1 la hauteur de notre sous arbre Etant donn cette proc dure qui transforme un sous arbre de hauteur deux en un sous arbre de hauteur un on va maintenant conclure En fait si arbre de d part poss de m noeuds internes moins de m application de la proc dure sont n cessaire En effet si on rep re toutes les racines de sous arbre de hauteur deux il y en a n cessairement moins de m et qu on applique la proc dur2. Sa seule racine r elle est 1 839286755 ce qui donne la complexit du processus On part d une assignation des variables dans laquelle il existe un litt ral pur non vrai On le fait passer vrai et la formule reste satisfaite 1 function 3SAT 2 match y with OT aVyVz A EVuVv AW gt if 3SAT v zu then T else if 3SAT y r v then T else if 3SAT Ty then T 7 else 3SAT w Zyz 8 end function Le temps d ex cution ob it la r currence T n 2T n 2 2T n 3 C est une r currence lin aire dont le polyn me caract ristique est r3 2r 2 Sa seule racine r elle est 1 769292354 Cette technique est due Monien and Speckenmeyer et date de 1985 3 On applique en fait r cursivement la technique utilis e sur le litt ral x dans la solution pr c dente tous les litt raux substitu s cette am lioration est due aux m mes auteurs On suppose qu on donne toujours la fonction 3SAT une formule sans litt raux purs 1 function FIXLITERAL X 2 match y with 3 OT 4 _ if X contient un litt ral pur then 3SAT KILLPURE w X 5 else let u Vu Ay y X in 6 if FIXLITERAL Xu then T else FIXLITERAL XUv 7 end function 8 9 function 3SAT match y with 10 9 gt T 11 aVuVv Ay gt if FIXLITERAL Y x then T 12 else if FIXLITERAL 7 zy then T 13 else FIXLITERAL w ZYz 14 end function Notons T n le temps d ex cution de
3. 3SAT et T n celui de FIXLITTERAL On a clairement T n max T n 1 T n 1 T n 2 T n T n 1 T n 2 T n 3 D o on d duit en substituant la deuxi me quation dans la premiere T n T n 2 max T n 3 T n 4 T n 1 Comme T n est exponentiel en n on va supposer que T n O a Il r sulte de cette hypo th se qu l infini ou bien T n 3 T n 4 est syst matiquement plus grand que T n 1 ou bien c est l inverse En fait T n 3 T n 4 gt T n 1 implique que a lt 1 325 c est la racine d une b te quation cubique en a Cela signifie qu l infini T n T n 2 T n 3 T n 4 Or r soudre cette r currence lin aire nous donne a gt 1 456 Contradiction Il s ensuit qu linfini T n 1 est plus grand que T n 3 T n 4 et ainsi T n est asymptotiquement gouvern par la r currence T n T n 1 T n 2 dont la solution est T n 1 6180 Il s ensuit qu des facteurs polynomiaux pr s T n 1 6180 Solution de l exercice 9 Ce qu il ne faut pas faire c est si la salle est libre partir de l heure h accepter la premi re requ te qui se pr sente dont le d but est ult rieur h car cela conduit des solutions sous optimales Par exemple si les requ tes sont 1 10 2 4 et 6 8 cette m thode conduirait acce
4. disjointe et compl mentaire On va construire un algorithme polynomial qui r soud Max Clique sur les cographes a Montrez qu partir d un cographe on peut construire un arbre de d rivation qui d crit enti rement le cographe en temps polynomial xx b Montrez qu on peut remplacer compl mentaire par produit dans la d finition des co graphes xx c Donnez un algorithme qui r sout Max Clique en temps polynomial tant donn une repr sen tation arborescente du cographe pour la nouvelle d finition xxx 4 Donnez un algorithme lin aire en la taille du graphe Exercice 13 xxxx Hercule vs Hydre Hercule se bat contre Hydre qui est un monstre plusieurs t tes A chaque tour de jeu Hercule peut couper une des t tes mais alors Hydre a des t tes qui repoussent Plus pr cis ment l Hydre est commod ment repr sent e par un arbre dont les feuilles sont les t tes En coupant une t te Hercule d truit une feuille Il r ussit an antir le monstre s il parvient le r duire l arbre vide Les t tes repoussent de la fa on suivante si la feuille coup e a un grand p re dans l arbre alors une fois que la feuille est coup e son p re est clon fois o est le num ro du tour courant Par exemple si on coupe la feuille noire au troisi me tour rer PANNES pes og ee D montrez rigoureusement qu il est possible de tuer l Hydre Essayez bonne chance de donner une borne
5. gt SiU USy UT U UTy 10 On se convainc d abord que l application de ces r gles termine En effet elle font soit diminuer strictement le nombre de noeuds qui sont du m me type que leur parent soit elles poussent les n gation d un tage vers le bas ce qui ne peut pas se faire infiniment souvent m me si Vargument est informel soit elle font diminuer le nombre total de n gations Il est facile de v rifier que application de chacune des r gles s par ment ne modifie pas la valeur de p sur Varbre Enfin une fois qu on a fini de les appliquer il n y a plus de noeud compl mentaire dans l arbre c Une fois qu on a un coarbre union produit il n est pas dur de d terminer la taille de la plus grosse clique dans le cographe correspondant MAXCLIQUE 2 1 si x est une feuille MaAXCLIQUE T U U Th max MaxCrique T ae MAXCLIQUE T MAXCLIQUE T X X Tn D MAXOLIQUE T i 1 Le seul point non trivial est de v rifier la troisi me galit En fait comme l op ration pro duit est trivialement associative il suffit de d montrer que MAXCLIQUE U Ta MAXCLIQUE T MAXCLIQUE T2 pour conclure par r currence Pour cela on va construire explicitement une clique de la bonne taille sur le produit Notons G V Ei p T et Ci C V une clique de taille maximale dans G D apr s le r sultat qu on a montr sur le produit chaque sommet de C est reli tous le
6. question 2 Supposons qu un recouvrement optimal soit form de l assemblage de I k ensembles Notons u i le nombre de points non couverts apr s la i eme it ration de l algorithme en fixant uo n Puisqu on sait que ces u points sont totalement couverts par les k ensembles de la solution optimale il y a forc ment au moins un de ces ensembles qui couvre au moins u k points Le caract re glouton du choix effectu par l algorithme nous permet alors d affirmer que uj41 lt ui u k Il s ensuit en d roulant l expression que u lt n 1 1 k Ensuite en utilisant l in galit de convexit classique 1 x lt e valable si x est non nul autrement il y a galit on trouve u lt ne Lorsque i klnn on trouve w lt 1 et donc il n y a plus rien couvrir l algorithme a termin 3 On pose B 0 2 1 1 et on choisit des S disjoints tels que S 2 On consid re aussi deux ensembles suppl mentaires T et T qui contiennent chacun une moiti de tous les S L algorithme glouton choisi Sn S1 alors que To T est la solution optimale Solution de l exercice 4 1 NEAREST NEIGHBOUR on part d une ville au hasard et on va la ville non visit e la plus proche jusqu a ce qu on ait fait le tour On revient alors au point de d part 2 REPETITIVE NEAREST NEIGHBOUR on refait la m thode pr c dente mais en essayant depuis tous les points de d part p
7. sur le temps d ex cution de l Hydre no pun intended 5 Solutions Solution de l exercice 1 Il suffit de faire une recherche dichotomique On utilise les k 1 premi re boules pour faire une recherche dichotomique Ca isole un intervale de taille n 2 71 qu on recherche ensuite exhaustivement avec la derni re boule 3 On lache la premi re boule aux tages dont le num ro est i y n pour des valeurs de i croissantes On isole ainsi un intervale de taille y n contenant la bonne solution qu on parcourt exhaustivement avec la deuxi me boule 4 Pour am liorer la technique pr c dente il faut d terminer comment le pire cas est atteint Il est clair que le pire cas est atteint si le seuil est au niveau n Alors exactement 2 n lancers auront eu lieu Pour am liorer a il faut se dire qu il n est pas indispensable de faire au pire y n tests avec chacune des deux boules s par ment Si on fait 1 test avec la premi re boule on pourra en faire V2n 1 avec la seconde et c est bon Partant de cette observation l id e est qu avec la premi re boule on peut faire de plus grand pas au d but qu la fin En fait il suffit qu avec la premi re boule le i eme pas soit de longueur V2n i On est s rs d atteindre le sommet de l immeuble avec un peu moins de V2n lancers car van z 2n t n 4 a 3 i 0 Ensuite si la premi re boule se casse lors de son i me lancer alors on a un in
8. toutes les autres villes qui minimise le nombre de kilom tres parcourus Proposez 3 algorithmes gloutons qui donnent des solutions approximatives au probl me on ne de mande pas de prouver la qualit des solutions Il doit tre possible ce n est pas obligatoire d exhiber des exemples qui montrent que vos algorithmes ne sont pas des approximations si est une constante ind pendante de n Exercice 5 xx Algorithme de Kadane On se donne un tableau A de n l ments entiers Af1 Afn Le probl me est de d terminer deux indices 1 lt i j lt n tels que la somme A i Aly est maximale Notez que j lt i est une solution admissible et alors la somme vaut z ro Donnez un algorithme programmation dynamique qui n examine chaque case de qu une seule fois et qui termine donc en temps lin aire Exercice 6 xx Plus long facteur commun Le probl me est de d terminer quelle est la longueur du plus long facteur commun deux cha nes de caract res donn es Donnez un algorithme programmation dynamique et valuez sa complexit X Exercice 7 xx Massacre la tron onneuse Admettons qu on ait affaire un langage de programmation o la seule op ration possible sur les cha nes de caract re soit une fonction SPLIT qui prend en argument une cha ne de caract re w de taille n et un entier k et qui renvoie deux cha nes un pr fixe de taille k de w ainsi qu un suffixe de taille n k Ce
9. 0 L administration elle cherche rejeter le moins requ tes possible sachant que deux d partements ne peuvent pas faire cours en m me temps Donnez un algorithme glouton pour l administration prouvez son optimalit et tudiez sa complexit Attention il ne s agit pas de maximiser le nombre d heure d utilisation de la salle mais vous pouvez aussi essayer de r soudre ce probl me Exercice 10 xxx D m nagement Je vais bient t d m nager et je dois ranger mes affaires dans des cartons Plus pr cis ment j ai ma disposition un stock illimit de cartons d un m tre cube et je poss de n objets dont les volumes sont des rationnels a1 a compris entre 0 et 1 Le probl me est de trouver un rangement qui occupe le moins de cartons possible c est le probl me du Bin Packing 1 L algorithme NEXT FIT est le suivant prendre les objets dans un ordre quelconque placer l objet courant dans le dernier carton utilis s il tient sinon fermer le carton en cours et en cr er un nouveau Montrer que NEXT FIT est une 2 approximation et montrer que la borne est atteinte 2 L algorithme FIRST FIT DECREASING est le suivant Trier les a par ordre d croissant de volume Placer l objet courant dans le premier carton utilis o il tient sinon en cr er un nouveau Montrer que FIRST FIT DECREASING est au moins une 3 2 approximation Exercice 11 xxx Primaires Comme c est la mode le Part
10. ASS 2 c undef 3 n 0 4 while il reste des membres dans la queue do 5 faire entrer membre suivant 6 if n 0 then 7 c le candidat du membre pr sent 8 else 9 if c le candidat du membre pr sent then 0 nent l 11 else 12 nen l 13 end if 14 end if 15 end while 16 return c 17 end procedure Cette proc dure r v le le candidat co survivant la m l e Il suffit ensuite de refaire passer tout le monde en leur demandant si leur candidat est bien co et de compter le nombre de r ponse a tient dans l espace imparti pour conna tre le r sultat final Cet algorithme est d Boyer et Moore 1980 Solution de l exercice 12 1 M thode brutale On num re tous les sous ensemble de V il y en a 2 et on teste si chacun d entre eux est une clique ce qui prend un temps total n 2 2 Il suffit de montrer que l ensemble d ar tes est le bon pas de probl me pour les sommets Si x amp y est une ar te du produit alors ce n est par d finition pas une ar te de G1 U Go Trois cas sont possibles ou bien x y Vi et sous cette condition x y G1 U Go est quivalent x y G2 ou bien x y V2 et sous cette condition x y G1 U Go est quivalent x y Gy ou bien x V et y V on peut le supposer sans perte de g n ralit puisque le graphe est non orient Sous cette condition x y G1 U Go est toujours vrai 3 a Par d finit
11. Algorithmique et Programmation TD n 1 Introduction Ecole normale sup rieure D partement d informatique td algo di ens fr 2011 2012 1 Mode d emploi Les exercices 1 8 et 12 illustrent la technique du diviser pour r gner avec un niveau de sophistication croissant Les exercices 4 3 9 et 10 sont consacr s la m thode gloutonne et enfin les exercices 2 5 6 et 7 sont consacr s la m thode de la programmation dynamique L exercice 11 est inclassable et ne n cessite aucun pr requis L exercice 13 est consacr la preuve de terminaison d un algorithme en apparence simple Nous ne ferons pas de programmation ensemble mais l exercice 8 fournit des fonctions int ressantes dont la programmation n est pas enti rement triviale 2 Petits Rappels diviser pour r gner Cette strat gie r sout un probl me en le d coupant en sous probl mes du m me type en r solvant r cursivement les sous probl mes et en combinant les sous r sultats de fa on appropri e Cela aboutit typiquement un fonctionnement en arbre programmation dynamique C est une g n ralisation du diviser pour r gner Cette m thode a pris son nom dans les ann es 1950 quand le mot programmation signifiait tout autre chose qu au jourd hui On identifie galement une collection de sous probl mes et on les r soud un par un en commen ant par les plus petits en utilisant les solutions des petits sous probl m
12. cons cutifs le volume des objets pr sents est strictement sup rieur un car sinon l algorithme aurait rang tous les objets du deuxi me carton dans le premier Ainsi moins de la moiti de l espace est gaspill et le nombre de cartons utilis est par cons quent inf rieur 2V Le cas le pire ou en tout cas relativement mauvais est obtenu avec des 4n objets de tailles EA Ip A 1 1 2 2n 2 2n 2 In 2 Chaque carton ne contient que deux objets pour un volume de x Le nombre ce cartons utilis est donc 2n Par contre on peut mettre les 2n objets de taille 1 2 dans n cartons et les 2n objets de taille dans un seul carton 2 FIRST Fir DECREASING L id e consiste partitionner l ensemble de mes affaires en fonction de leur taille 2 1 2 A lt if B 4 lt 5 1 1 1 D asst C lt u lt On consid re ensuite deux cas mutuellement exclusifs Dans la solution DFF s il existe au moins un carton ne contenant que des l ments de D de petits trucs alors au plus un carton le dernier a un taux d occupation inf rieur ou gal 2 3 En effet si les l ments de D du dernier carton n ont pu tre mis dans les cartons pr c dents c est que ceux ci sont remplis au moins aux 2 3 d o la borne Sinon s il n y a pas de cartons remplis uniquement de bibelots de cat gorie D la solution de DFF est la m me que celle de l instance o on enl verait tous lesdits bib
13. e chacune d entre elles on fait baisser la hauteur totale de l arbre de un Ceci permet de conclure qu on peut d truire l arbre en un temps fini 11 R f rences 1 Nachum Dershowitz and Zohar Manna Proving termination with multiset orderings Commun ACM 22 465 476 August 1979 2 R W Floyd Assigning meanings to programs Mathematical aspects of computer science 19 19 32 1 1967 3 B Monien and E Speckenmeyer Solving satisfiability in less than 2n steps Discrete Appl Math 10 287 295 March 1985 12
14. e de w t j par les indices ax a On a i j k G t 1 min max F i as k 8 1 fus 5 1 0 Et on doit pouvoir conclure en temps n m Solution de l exercice 8 Supposons A x insatisfiable et prenons une assignation des variables arbitraire elle ne satisfait pas la formule Ou bien cette assignation rend x faux ou bien elle rend x vrai Dans ce deuxi me cas elle rend w faux Le r sultat de la question est la contrapos e de cette conclusion Consid rons une assignation A des variables qui satisfasse 7 Ou bien A rend x vrai ou bien A rend x faux De mani re quivalente ou bien satisfait Y A x ou bien elle satisfait Y A T L algorithme qu on en d duit est la recherche exhaustive 1 function 3SAT 4 2 match y with 3 gt T 4 gt if 3SAT x then T else 3SAT wz 5 end function La complexit dans le pire des cas est donn e par la formule T n 2T n 1 Poly n o n d signe le nombre de variables On aboutit trivialement au r sultat annonc La formule est obtenue en utilisant les lois de Boole 1 function 3SAT 4 2 match y with 3 9 gt T 4 aVyVz Ay gt if 3SSAT Y x then T 5 else if 3SAT Ty then T 6 else 3SAT w Zyz 7 end function Le temps d ex cution ob it la r currence T n T n 1 T n 2 T n 3 C est une r currence lin aire dont le polyn me caract ristique est r3 r r 1
15. elots de D puisque les l ments de D sont rang s apr s les autres On va maintenant montrer que si je n ai pas de bibelots de cat gorie D alors la solution de DFF est optimale S il n y a pas d objets de cat gorie D alors dans n importe quelle solution y compris l optimale on observe que les l ments de sont tout seuls il y a au maximum un seul l ment de B par carton il y a au plus deux l ments par carton La solution optimale est donc obtenue en rangeant d abord les l ments dans des cartons part puis en mettant les B dans un carton chacun et enfin en rangeant un C dans chaque carton B puis en faisant des cartons de 2 C Et c est pr cis ment ce que fait l algorithme DFF Solution de l exercice 11 Faisons une exp rience de pens e Supposons que les membre portent un dossard indiquant le nom de leur candidat Supposons qu une bagarre g n rale se d clenche et que les membres du parti des diff rentes tendances se cognent dessus les uns les autres Supposons aussi l action sym trique si un membre x cogne un membre y alors y cogne aussi sur x Supposons enfin que tout membre cogn se retrouve a terre inconscient Lorsque la situation s est calm e il est clair que des supporters d au plus une tendance restent debout sinon la m l e reprendrait Si une tendance avait la majorit absolue c est elle qui reste la fin Si aucune tendance n a la majorit ab
16. es pour r soudre les probl mes plus gros jusqu ce qu ils soient tous r solus La diff rence avec l approche divide and conquer de base est que le processus n est pas d crit par un arbre mais par un graphe orient acyclique la solution d un sous probl me peut re servir plus d une fois dans la suite algorithmes gloutons Ces m thodes construisent g n ralement une solution morceau par morceau et en choisissant le prochain morceau elles choisissent syst matiquement celui qui procure l avantage le plus vident et le plus imm diat Mots x et z sont respectivement un pr fixe et un suffixe d une cha ne de caract res w si on peut crire w x z De m me y est un facteur de w si on peut crire w x y z o x et z sont ventuellement vides Approximation Etant donn un probl me d optimisation une approximation est un algorithme po lynomial qui produit des solutions au pire fois plus grandes resp plus petites que la meilleure Graphes Un graphe non orient G V E est la donn e d un ensemble de sommets V pour verti ces pluriel irr gulier de vertex et d un ensemble d ar tes E C V reliant certains sommets En gros x y dans G ssi x y E Le graphe compl mentaire de G not G est obtenu en mettant des ar tes l o il n y en avait pas et r ciproquement L union de deux graphes dont les ensembles de sommets sont disjoints est bien d finie on met les de
17. hoisir de prendre la somme vide qui vaut z ro Ensuite ou bien f i 1 Ali gt 0 et alors on obtient la meilleure somme partielle terminant sur la 7 eme case en tendant la pr c dente d une case ou bien f i 1 Ali lt 0 et alors f z 0 L algorithme en d coule tout seul Solution de l exercice 6 Appelons a et B les deux cha nes de caract res L id e est de d finir f i j qui est la longueur du plus long suffire commun des pr fixes de tailles respectives i et j de a et 5 Une fois donn e cette information il est clair que max f i j est la solution compl te On peut donc d terminer la solution en temps et en espace a 6 Il existe cependant un algorithme plus sophistiqu dont la complexit est O lal 181 Solution de l exercice 7 1 D abord la version na ve en OCaml avec un param tre additionnel shift qui vaut 0 au d but 1 function MULTISPLIT w 1 shift 2 match 1 with 3 1 0 4 i 1 gt 5 let p s SPLIT w i shift in p MULTISPLIT s 1 shift i 7 end function Ce sont les appels SPLIT qui dominent le temps d ex cution Le premier co te n le second n ay le troisi me n a as etc Le coup total est donc n 5 n a n n 1 gt AR i 1 ai i 0 iei 2 Maintenant passons la version am lior e En fait c est tr s similaire aux boules en verre appelons f i j k 2 le co t d effectuer la d coup
18. i Pour l Algorithmique PPA organise ses primaires Les statuts du parti pr cisent que le candidat qui va tre d sign doit avoir obtenu la majorit absolue des voix des membres du parti Il y a k candidats et la totalit des n membres tiennent une r union dans une glise pour lire directement leur candidat main lev e par un vote majoritaire un seul tour Deux issues sont possibles ou bien un candidat r colte plus de 50 des voix et il est d sign ou bien le parti incapable de se mettre d accord se dissout dans la confusion Seulement voila tout le monde peur de se griller par le vote main lev e mais si je vote pour A et que B est lu B va m en vouloir mort il va me mettre au placard me coller le TD d algo etc Il n a malheureusement pas t pr vu de bulletins de vote pour organiser un vote secret Pour contourner le blocage qui s annonce le pr sident de s ance qui a de la ressource envisage de mettre les pr sents la queue leu leu puis de s installer dans le confessionnal et de les faire entrer tour a tour pour demander a chacun son candidat de mani re anonyme et confidentielle Malheureusement le pr sident de s ance qui est aussi le doyen du parti est si vieux que sa m moire flanche un peu Il ne dispose plus son ge canonique que de loga n log k bits de stockage Ses bits sont cependant tr s fiables Il r alise donc qu il lui est impossible d ex c
19. ion un cographe peut tre repr sent par un arbre de d rivation dont les feuilles sont tiquet es par des sommet tous diff rents et les noeuds sont soit tiquet s par union soit par compl mentaire La fonction suivante associe le cographe a l arbre de d rivation qu on appelle un coarbre p x x 0 si x est une feuille A T U U Th gt p T1 U U p Tn p T gt p T On montre qu on peut construire l arbre de d rivation en temps polynomial partir du graphe Soit on a affaire un sommet isol et c est assez facile Soit on a affaire un graphe non connexe testable en temps polynomial et on attaque chaque composante connexe s pa r ment tout en mettant un noeud union la racine de arbre Soit le graphe compl mentaire est non connexe et on se ram ne au cas pr c dent en mettant un noeud compl mentaire la racine de l arbre Enfin si le graphe compl mentaire est connexe c est que le graphe n est pas un cographe b On montre qu on peut se passer des noeuds compl mentaire condition de s autoriser des noeuds produit On tend la fonction p par p Ti M X Ta gt p T1 NX p Tn On peut alors r crire l arbre de mani re non d terministe parce que c est plus pratique en appliquant ad libitum les quatre r gles suivantes Ti U UT gt Ti X X Th T gt T T x si x est une feuille S U US UT2U UT
20. ment avant la requ te donc on peut remplacer par k dans A sans compromettre ce qui se passe ensuite I d coule de ceci que B A k U 1 est une solution non seulement valide mais aussi optimale puisqu elle a la m me taille que A Par hypoth se de r currence l appel r cursif GREEDY renvoie une solution optimale qu on va appeler S au probl me X i X si gt fk qui est lui m me n cessairement plus petit que X Il reste montrer que S S U k est bien une solution optimale au probl me de d part X En fait si on prend le probl me l envers on voit que B B k est une solution optimale au probl me X s il existait une solution de X strictement plus grande que B appelons la C alors C U k serait une solution valide au probl me de d part X qui serait strictement plus grande que la solution optimale B contradiction Il s ensuit que S et B ont la m me taille et donc que S U k a la m me taille que B qui est optimale L algorithme retourne donc bel et bien une solution optimale Solution de l exercice 10 1 NExT Fit Tout d abord si on note V gt gt a le volume total de mes affaires il para t clair qu il est impossible d utiliser moins de V cartons Examinons maintenant la solution produite par NEXT FIT Plus pr cis ment examinons deux cartons cons cutifs par exemple C1 et C2 ou bien C3 et C4 etc Dans deux cartons
21. nt des litt raux xx 3 D montrez que w est quivalente E Ap V y Ap V za D duisez en un algorithme r cursif de complexit 1 8392 indice il y a 3 appels r cursifs xx 4 Un litt ral x est dit pur si T n apparait pas dans w D montrez que si y est satisfiable alors il existe une assignation des variables dans laquelle tous les litt raux purs sont vrais Cela permet de se ramener au cas o aucun litt ral n est pur Cela signifie que si est non triviale on peut V crire w e VyVz A EVUVU AY o u et v sont des litt raux arbitraires qui peuvent tr s bien tre y 9 z et Z D duisez en un algorithme r cursif de complexit 1 7692 indice il y a 4 appels r cursifs xxx 5 Justifiez que dans chaque appel r cursif ou bien on a fait appara tre un litt ral pur qu on peut donc liminer ou bien on fait appara tre une clause deux litt raux D duisez en un algorithme de complexit 1 6180 c est le nombre d or xxx 6 Retrouver l algorithme d terministe dont le pire cas est le moins mauvais connu en 2011 1 33334 Exercice 9 xxx Planning de la salle La salle INFO 4 est tr s demand e Tous les d partements veulent y faire cours et tous envoient l administration des requ tes de la forme s t pour utiliser la salle entre l heure s et l heure t on peut supposer que les heures sont exprim es en secondes depuis le ler Janvier 197
22. orithme en log n sauts 2 Sik lt log n proposer un algorithme en k sauts x 3 Si k 2 proposer un algorithme en 2 n sauts xx 4 Dans ce dernier cas proposer aussi un algorithme en 2n sauts Exercice 2 xx Fragile le retour D crivez un algorithme qui tant donn n et k renvoie le nombre minimal de lancers effectuer pour tre s r de trouver la solution D terminer sa complexit Exercice 3 xx Set Cover On consid re un ensemble fini B n l ments et une famille finie S1 Sm de sous ensembles de B Le probl me Set Cover est de d terminer le plus petit au sens de la cardinalit ensemble J C 1 m tel que BcUS tet Donnez un algorithme glouton D montrez qu il n est pas optimal xx 2 D montrez ensuite que si B n alors il produit une solution qui est au pire Inn fois plus grande que l optimale Indice pour a on peut prouver quelque chose sur le nombre de points couverts par chaque choix glouton de l algorithme 3 D montrer que le pire cas est atteint asymptotiquement 4 Exercices faire chez vous Exercice 4 x Probl me du voyageur de commerce On consid re une carte g ographique sur laquelle figurent n villes et un voyageur de commerce qui doit visiter toutes ces villes une fois et une seule Le voyageur se d place en avion en ligne droite Le probl me consiste en partant d une des villes trouver un ordre dans lequel visiter
23. ossible et en gardant la meilleure solution bien s r 3 CHEAPEST LINK de fa on r p titive on trace un trait sur la carte entre les deux villes les plus proches condition que ce nouveau trait Ne soit pas le troisi me qui touche une ville N aboutisse pas la formation d une boucle dont au moins une ville ne ferait pas partie si la paire de ville consid r e ne convient pas on prend la suivante 4 GREEDY INSERTION on fabrique une boucle d abord r duite a une seule ville puis on ins re dans la boucle la ville qui minimise la taille de la boucle r sultante On peut d montrer que ces techniques offrent une approximation qui est au pire logn fois plus grandes que la solution optimale Il existe par ailleurs une 3 2 approximation qu on verra plus tard dans l ann e due Christofides en 1976 Enfin il existe depuis 2010 un sch ma d approximation polynomial d Arora et Mitchell qui ont gagn le prix Turing pour a pour tout gt 0 il existe un algorithme polynomial en le nombre de ville qui est une 1 approximation Solution de l exercice 5 L id e est de d finir f i qui est la meilleure somme partielle obtenue sur un intervalle de la forme x i Il est clair que max f z est la solution du probl me Il suffit de montrer qu on peut calculer f i partir de f i 1 et de Afi D j on observe que f z n est jamais n gatif car on pourrait toujours c
24. pter la premi re requ te et rejeter les deux autres tandis qu en rejetant la premi re on peut accepter les deux autres La bonne solution c est de trier les requ tes par date de fin croissante d en parcourir la liste dans cet ordre la et d ajouter la requ te courante si elle commence apr s que la salle soit lib r e par la requ te pr c dente a se fait donc en temps n logn et on va v rifier que le r sultat produit est optimal Pour a on suppose que n requ tes s1 t1 Sn tn ont t soumises et on les suppose tri es par heures de fin croissantes La proc dure d finie ci dessus correspond en fait la d finition GREEDY 0 GREEDY X let k min X in k U GREEDY i X s gt f D montrons que GREEDY fournit une solution de taille maximale par r currence sur la taille de son argument S il est vide o s il est de taille 1 il ny a rien faire Sinon supposons que X gt 2 et montrons que le choix glouton d inclure la requ te avec la plus petite heure de fin dans la solution est correct Pour cela on consid re une solution optimale du probl me c est dire un sous ensemble A de 1 n d signant les requ tes accept es Appelons galement k le plus petit l ment de X Si k A alors on va fabriquer une autre solution optimale B qui contient k Consid rons la requ te de A qui finit le plus t t min A Par d finition la requ te k finit n cessaire
25. s sommets de G2 donc en particulier tous ceux de C2 et vice versa Ceci prouve que C1 U C2 est une clique dans le produit Prouvons maintenant qu elle a la taille optimale et pour cela prenons une clique de taille maximale dans le produit On voit que C CN G sont deux cliques induites sur les sous graphes s par s et ces derni res sont forc ment plus petites que les cliques maximales sur les deux sous graphes On peut conclure partir de l Solution de l exercice 13 Plusieurs preuves sont possible La plus simple consiste observer que chaque fois qu Hercules coupe une t te cela fait d cro tre l ordre multi ensemble emboit sur Varbre cette relation d ordre a t introduite en 1979 par Dershowitz et Manna 1 Ensuite comme cet ordre est bien fond il ne peut pas y avoir de cha nes infinies d croissantes et la terminaison est tablie L id e d utiliser des relations bien fond e pour prouver la terminaison a t sugg r e par Floyd en 1967 2 Mais on va utiliser une approche plus directe qui fonctionne en deux temps On va d abord d mon trer qu il est possible ind pendemment de la valeur de i de transformer n importe quel sous arbre de hauteur 2 en un sous arbre de hauteur 1 sans modifier le reste de l arbre Ensuite on utilisera cette propri t pour conclure par induction Consid rons un sous arbre de hauteur 2 Il y a une racine des noeuds internes
26. solue la situation est moins claire mais en tout cas les d l gu s restants n appartiennent pas la majorit absolue vu qu il n y en a pas Pour distinguer ces deux situations le pr sident de s ance peut compter le nombre total de dossards de la tendance restante y compris ceux qui sont terre et v rifier s ils ont la majorit absolue Le probleme est donc de simuler la bagarre g n rale Dans un premier temps avant de la simuler nous allons organiser un peu ce pugilat chaotique Pour cela le pr sident de s ance choisit un premier membre au hasard et le prend avec lui Il va voir un autre membre au hasard et les pr sente S ils sont de la m me tendance il embarque les deux membres avec lui sinon ils s liminent mutuellement Ainsi le pr sident va promener avec lui un groupe de taille variable de membres qui sont tous d accord entre eux Si son groupe se vide le pr sident le r initialise avec un nouveau membre choisi au hasard L issue fatale est que plus personne n est debout sauf le groupe autour du pr sident qui subsiste donc la fin de la m l e Le pr sident peut simuler pacifiquement cette proc dure D abord observons qu avec log n bits il peut stocker la taille de son groupe et qu avec log k bits il peut stocker le candidat de son groupe Le pr sident met donc tous les membres la queue leu leu devant le confessionnal puis il ex cute la proc dure suivante 1 procedure FIRSTP
27. tervalle de taille V2n i contenant le seuil et si on l explore exhaustivement le nombre total de tests sera y 2n Solution de l exercice 2 En partant de notre immeuble on peut lancer la premi re boule dans l intervalle 1 n et on note f n k la solution optimale Quand on lance la premi re boule disons l tage i deux issues sont possibles ou bien la boule se casse et notre prochain lancer doit tre dans l intervalle 1 i 1 ou bien la boule ne se casse pas et notre prochain lancer doit tre dans l intervalle i 1 n Il faut donc dans le pire des cas tre capable de r soudre les deux sous probl mes l un avec une boule de moins l autre avec le m me nombre de boules Clairement fn k 1 min max f i 1 k 1 f n i k On peut donc tr s clairement calculer la solution optimale en temps n k et en espace O n k Note il faut bien s r stocker les valeurs d j calcul es de f n k sinon la complexit sera exponentielle Il est galement possible d am liorer les complexit s temporelles un des tudiants affirme n k et spatiales n semble facile mais je ne sais pas si on peut combiner avec l am lioration pr c dente Solution de l exercice 3 1 Il suffit de construire le recouvrement petit petit en ajoutant d abord l ensemble S qui recouvre le plus de points non couverts C est tr s facile de voir que ce n est pas optimal cf derni re
28. tte proc dure s ex cute in vitablement en temps n On ne peut pas lire les cases individuelles des cha nes Maintenant on veut fabriquer une fonction MULTISPLIT qui prend en argument une chaine de ca ract res w de taille n et une liste a1 am d entiers et qui renvoie les m 1 cha nes w 1 a1 w az da W m 1 Am w am n 1 Donnez une version r cursive naive de MULTISPLIT ainsi que son temps d ex cution 2 Donnez ensuite un algorithme qui d termine dans quel ordre effectuer les coupes pour minimiser le temps d ex cution programmation dynamique Est il plus rapide que la m thode na ve Exercice 8 xxx 3SAT On s int resse au probl me 3SAT qui consiste d terminer si une une formule logique en forme normale conjonctive avec au plus trois litt raux par clause est satisfiable On consid re une formule logique y au format 3SAT On va noter Y x la formule y dans laquelle on remplace le litt ral x par T 1 D montrer que si 7 Ax est insatisfiable alors toute assignation des variables satisfaisant Y contien drait 7 2 D montrez si x est un litt ral alors 4 et Y A x V Y AZ sont quivalentes c a d ont les m mes mod les D duisez en un algorithme r cursif pour 3SAT de complexit Poly n 2 On va maintenant chercher obtenir un algorithme asymptotiquement plus rapide Si d n est pas vide alors elle s crit Y x V y V z Av o x y et z so
29. uter son plan car il ne peut pas stocker les k loga n bits qui seraient n cessaire au d compte des scores individuels des candidats Il ne peut m me pas mesure les score de chaque candidats s par ment et garder le max car cela n cessiterait au moins 2 log n logs k bits de stockage Seulement comme ce n est pas le pr sident de s ance pour rien il con oit un algorithme qui va lui permettre de savoir malgr ses ressources limit es si un candidat a la majorit absolue et si oui lequel Comment peut il faire Exercice 12 xxx Max Clique Dans un graphe une clique est un ensemble de sommets tous mutuellement adjacents Yx y C x y x y dans G On ne conna t pas d algorithme polynomial pour le probl me Max Clique qui consiste d terminer la taille de la plus grande clique pr sente dans un graphe arbitraire donn en argument On peut d montrer vous allez le faire un jour que le probl me est NP complet c est dire qu il est de complexit comparable celle de 3SAT 1 Donnez un algorithme pour Max Clique D terminez sa complexit On va voir maintenant un cas particulier o un algorithme polynomial existe Si l union de deux graphes G et Go est bien d finie leur produit G1 M Gz G1 U Go l est galement 2 Montrez que G M Go Vi U V2 A UEBU r y reV ye VW 3 L ensemble des cographes est le plus petit ensemble de graphes contenant les sommets isol s et ferm par union
30. ux graphes c tes c te Un graphe est dit connexe si ce n est pas l union de deux graphes c est dire s il est d un seul tenant Logique Une variable bool enne prend comme valeur vrai T ou faux L L ensemble des formules bool ennes contient les variables L T et il est ferm pour la n gation 7 le ET 9 A 4 ainsi que le O V y Une formule est satisfiable s il existe une assignation des variables qui la rend vraie Sinon elle est insatisfiable Un litt ral est soit une variable soit la n gation d une variable Une formule bool enne est en forme normale conjonctive Si elle peut s crire AV i j o est un litt ral 3 Exercices pour le TD Exercice 1 x Fragile On dispose d un stock de boules en verre Le probl me est de d terminer partir de quel tage d un immeuble les boules en verre se cassent si on les jette par la fen tre Vous tes dans un immeuble n tages num rot s de 1 n et vous disposez de k boules Il n y a qu une seule op ration possible pour tester si la hauteur d un tage est fatale jeter une boule par la fen tre Si elle ne se casse pas vous pouvez la r utiliser ensuite sinon vous ne pouvez plus Vous devez proposer un algorithme pour trouver la hauteur partir de laquelle un saut est fatal renvoyer n 1 si on survit encore au n i me tage en faisant le minimum de sauts 1 Si k gt logo n proposer un alg
Download Pdf Manuals
Related Search