Ecole normale superieure Departement d'informatique

Description

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

Sujets

• Formule

Informations

• Publié par: pefav
• Nombre de lectures: 65
• Langue: Français

Extrait

´ Ecolenormalesup´erieure D´epartementd’informatique

Algorithmique et Programmation ◦ TD n1 : Introduction Avec Solutions

2010-2011

Exercicesthe ´ oriques Exercice 1. Le Grand saut.ateglee´eduqtrriubleimmed’uneme`dtsepeLlborerinpa`a´eedrmte sauterparlafeneˆtreestfatal.Vousˆetesdansunimmeublea`ne´egatun(sre´mot´esde1`an) et vous disposez dekseegtnu’date´´teluesenu’tare´poes.ntiaudquyan’Ilsrliseetetruhauaossiionpourtblep fatale:fairesauterun´etudiantparlafenˆetre.S’ilsurvit,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+ k−1 ) 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-esc’e,ivctonnjocelamronemrofnenuferoumel clausesquisontdesdisjonctions,comportantauplus3litte´rauxparclauses.Noussouhaitonsd´ecider siuneformuledonne´eφayantnt-`ac’esite,isfatsueelixsei’d-riesndioatgnsiasneviaarrteˆtaseselbtuep variables rendant vrai la formule. Nous supposons queφn’est pas la formule vide et que : 0 Φ = (x∨y∨z)∧Φ, 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´eifrsrefiiΦ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 Φ = (x∨y∨z)∧noitneptΦncevoriec,´soralnsttiledsaruplare´ 0 Φ = (x∨y∨z)∧(x¯∨u∨v)∧()∧Φ. 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 i 1 , . . . , i m telle que∀k,1≤i k ≤neti k < i k+1 . Une sous-suite est de pluscroissantesi∀k, A[i k ]≤ A[i k+1 ],rce´ssioetnadsi∀k, A[i k ]≥A[i k+1 ], etmonotonecritsostteanssoie´dtios,nassiorcte.seillee

1