Ecole normale superieure Departement d'informatique

Publié par

Ecole normale superieure 2010-2011 Departement d'informatique Algorithmique et Programmation TD n? 1 : Introduction Avec Solutions Exercices theoriques Exercice 1. Le Grand saut. Le probleme est de determiner a partir de quel etage d'un immeuble sauter par la fenetre est fatal. Vous etes dans un immeuble a n etages (numerotes de 1 a n) et vous disposez de k etudiants. Il n'y a qu'une seule operation possible pour tester si la hauteur d'un etage est fatale : faire sauter un etudiant par la fenetre. S'il survit, vous pouvez le reutiliser ensuite, sinon vous ne pouvez plus. Vous devez proposer un algorithme pour trouver la hauteur a partir de laquelle un saut est fatal (renvoyer n+ 1 si on survit encore au n-ieme etage) en faisant le minimum de sauts. 1. Si k ≥ dlog2(n)e, proposer un algorithme en O(log2(n)) sauts. 2. Si k < dlog2(n)e, proposer un algorithme en O(k + n 2k?1 ) sauts. 3. Si k = 2, proposer un algorithme en 2 √ n sauts. 4. Dans ce dernier cas, proposer aussi un algorithme en √ 2n sauts. Solution : Exercice 2. 3SAT. Soit ? une formule en forme normale conjonctive, c'est-a-dire une conjonction de clauses qui sont des disjonctions, comportant au plus 3 litteraux par clauses.

  • programmation td

  • taux d'occupation inferieur

  • nouvelle montrer

  • formule

  • ordre quelconque

  • kdff ≤

  • litteral pur


Publié le : mardi 19 juin 2012
Lecture(s) : 50
Tags :
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
´ Ecolenormalesup´erieure D´epartementdinformatique
Algorithmique et Programmation TD n1 : Introduction Avec Solutions
2010-2011
Exercicesthe´oriques Exercice 1. Le Grand saut.ateglee´eduqtrriubleimmeduneme`dtsepeLlborerinpa`a´eedrmte sauterparlafeneˆtreestfatal.Vousˆetesdansunimmeublea`ne´egatun(sre´mot´esde1`an) et vous disposez dekseegtnudate´´teluesenutare´poes.ntiaudquyanIlsrliseetetruhauaossiionpourtblep fatale:fairesauterun´etudiantparlafenˆetre.Silsurvit,vouspouvezler´eutiliserensuite,sinonvousne pouvez plus. Vousdevezproposerunalgorithmepourtrouverlahauteura`partirdelaquelleunsautestfatal(renvoyer n+ 1si on survit encore aun`e-i´emeegatfne)asiaeltnst.seuaumdmimin
1. Sik≥ dlog (n)e, proposer un algorithme enO(log (n)) sauts. 2 2 n 2. Sik <dlog (n)e, proposer un algorithme enO(k+k1) sauts. 2 2 3. Sik= 2, proposer un algorithme en 2nsauts. 4. Dansce dernier cas, proposer aussi un algorithme en2nsauts.
Solution : Exercice 2. 3SAT.Soitφndectiojnnoenocriuea`d-t-esce,ivctonnjocelamronemrofnenuferoumel clausesquisontdesdisjonctions,comportantauplus3litte´rauxparclauses.Noussouhaitonsd´ecider siuneformuledonne´eφayantnt-`acesite,isfatsueelixseid-riesndioatgnsiasneviaarrteˆtaseselbtuep variables rendant vrai la formule. Nous supposons queφn’est pas la formule vide et que : 0 Φ = (xyz)Φ, 0 pourdeslitt´erauxx, y, zune formule 3CNF.et Φ
1.Donnerunalgorithmeparrechercheexhaustiver´esolvantceprobl`emeestdonnersacomplexite´. 0 0 00 0 2. Montrerque Φ = (xΦ|x)(yΦ|y)(zΦ|z) avec Φ|xan¸cttboeuneernealpmluΦeofmral x.´eitsresylanxelpmocapararvEni.thmer´ecursifeta´ddeiuernulaogir 0 3.Ame´liorercetalgorithmeenremarquantquedanslepremierappelre´cursifsilaformuleΦ|xne 0 peutpaseˆtresatisfaiteavecxou,nouspcu´eifrsreiΦsnovre´v,alorsdavraidnpaeprlsnelesoc|¯xy aulieude.Quelleestlanouvellecomplexit´edevotrealgorithme? 4.Unlitt´eralestpurrofaelumiamΦsapsn´saategn¯ioisilapparaˆıtdanslx. Montrer que si Φ peut eˆtresatisfaite,ilexistealorsuneassignationquisatisfaitΦavectousleslitte´rauxpurs`avrai.Si 0 Φ = (xyz)noitneptΦncevoriec,´soralnsttiledsaruplare´ 0 Φ = (xyz)(x¯uv)()Φ. Simplifiez la formule Φ pourxr´ecursif.Analyseornsvaucloeml-aogirhtemvr`aetainndouner plexit´e. ´ Exercice 3.Etude des sous-suites monotones de taille maximale d’un tableau.On se donne un tableauAdenitnestnesreeml´´eA[1], . . . , A[n]. On appellesous-suite de longueurmune suite d’indices i1, . . . , imtelle quek,1iknetik< ik+1. Une sous-suite est de pluscroissantesik, A[ik]A[ik+1],rce´ssioetnadsik, A[ik]A[ik+1], etmonotonecritsostteanssoie´dtios,nassiorcte.seillee
1
1.ekez)serTh´e(soSrE¨demedroe`On noteψ: [1. . . n][1. . . n]×[1. . . nnqui`al]fanotcoikassocie deuxentiers:lalongueurmaximaledessous-suitescroissantes(respectivementd´ecroissantes)de Aecidnitdesntme´eelr´ieednrtnelodk. Montrez queψzee-qneuD.e´udsinjectivesiestin2 (Nofete´crlisrsixe+1)lo,a1eotonemonailledetnuseemtnustiuo-sN. 0 0 2. Exprimezψ(k) en fonction de tous lesψ(k) pourk <kalmioglahtiropemonyl.D´eduisez-enun quid´etermine,parprogrammation dynamique, la longueur maximale des sous-suites monotones de Aiquesoncode,ainstptoqieuˆotusamyou.Vonsduespc-oderennoszespmetneome´mnetene,ir fonction den. 3.Modiezlalgorithmedelaquestionpre´ce´dentepourquilache,enplusdelalongueurmaximale des sous-suites monotones deA, une sous-suite monotone de longueur maximale. Exercice4.Proble`medOptimisation:BinPacking.Soitnobjets de volume des rationnels a1, . . . , anou`0< ai1. Peut-on les partitionner enksetıˆobB1, . . . , Bkt´eapacidecaeleuq1st,puul P 1. jBk Oncherche`aminimiserlavaleurk. Uneλ-approximation est un algorithme polynomial tel que, pour toute instanceId,mee`lborpuSolalgo(I)λOpt(I).
1. L’algorithmeNext Fit est le suivant : – prendreles objets dans un ordre quelconque placerlobjetcourantdansladernie`reboıˆteutilise´esiltient,sinonencr´eerunenouvelle Montrer que Next Fit est une 2-approximation. Montrer que la borne est fine. 2. L’algorithmeDec First Fit est le suivant : – Trierlesaisantroisroparerdecd´ Placerlobjetcourantdanslapremi`ereboˆıteutilise´eou`iltient,sinonencr´eerunenouvelle Montrer que Dec First Fit est une 3/2-approximation.
Solution :
3 KDF FKOpt+ 1 2
2 2 1 1 11 A={ai>}, B={ ≥ai>}, C={ ≥ai>}etD={ ≥ai} 3 3 2 2 33
DanslasolutionDFF,silexisteaumoinsuneboˆıtenecontenantquedes´ele´mentsdeD, alors au plus 2 uneboˆıte(ladernie`re)auntauxdoccupationinfe´rieuroue´gal`a.Eneet,silese´l´ementsdeDde la 3 2 dernie`reboıˆtenontpueˆtremisdanslesboıˆtespr´ec´edentes,cestquecelles-cisontrempliesaumoins 3 (dou`laborne).
Sinon,lasolutiondeDFFestlamˆemequecelledelinstanceo`uonenl`evelese´le´mentsdeD. La solution deDFFpourlese´l´ementsA,BetCest optimale. Dans toute solution, lese´l´ementsdeAsont tout seuls, lese´le´mentsdeBetContauplustnedme´eeln´suluupaanotesetıˆobrap2sBet.obıˆpra OrDFFfaitlameilleurer´epartitiondesCen les appariant au plus grandBouCcompatible.
11 Remarque : on peut montrerKDF FKOpt+ 4 ? 9 Exercice 5.Mariage.orcgspnaemsntUaspstmroeahiiebsxensedeu´esdtitustniojsidselbmeHetF etnadarˆetequentreunsommetdeHet un sommet deFantnayseegenutmnU.airarˆaesetemnsedbl deuxa`deuxaucunsommetcommun.SiMest un mariage, on noteM(h),hH,lunique´el´emnetfde Feletelqurˆaeetsielixts{h, f}soit dansM. On poseM(h) =sifn´end.OasepstxientiM(f), fFe.logueanai`ermenad,
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.