Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Ecole normale superieure Departement d'informatique

3 pages
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


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin