7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
´ 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