La lecture en ligne est gratuite
Télécharger
Algorithmique et Programmation TD n 1 : Introduction Ecolenormalesupe´rieure D´epartementdinformatique td-algo@di.ens.fr 2011-2012
1 Mode d’emploi Lesexercices1,8et12illustrentlatechniquedudiviserpourr´egneravecunniveaudesophistication croissant.Lesexercices4,3,9et10sontconsacr´es`alam´ethodegloutonne,etennlesexercices2,5, 6et7sontconsacre´s`alame´thodedelaprogrammationdynamique.Lexercice11estinclassable,et nene´cessiteaucunpr´erequis.Lexercice13estconsacre´a`lapreuvedeterminaisondunalgorithme(en apparence) simple. Nousneferonspasdeprogrammationensemble,maislexercice8fournitdesfonctionsint´eressantes dontlaprogrammationnestpasentie`rementtriviale. 2 Petits Rappels diviserpourre´gner Cettestrat´egier´esoutunprobl`emeenlede´coupantensous-proble`mesdumeˆme type,enre´solvantre´cursivementlessous-proble`mes,etencombinantlessous-r´esultatsdefa¸con appropri´ee.Celaaboutittypiquement`aunfonctionnementenarbre. programmation dynamique Cestunege´ne´ralisationdudiviserpourre´gner.Cetteme´thodeapris sonnomdanslesann´ees1950,quandlemotprogrammationsigniaittoutautrechosequau-jourdhui.Onidentiee´galementunecollectiondesous-proble`mes,etonlesr´esoudunparun,en commen¸cantparlespluspetits,enutilisantlessolutionsdespetitssous-problemespourr´esoudre ` lesprobl`emesplusgros,jusqua`cequilssoienttousr´esolus.Ladie´renceaveclapprochedivide andconquerdebaseestqueleprocessusnestpasdecritparunarbre,maisparungrapheoriente´ ´ acyclique(lasolutiondunsous-proble`mepeutre-servirplusdunefoisdanslasuite). algorithmes gloutons Cesme´thodesconstruisentg´en´eralementunesolutionmorceauparmorceau,et enchoisissantleprochainmorceau,elleschoisissentsyste´matiquementceluiquiprocurelavantage lepluse´videntetleplusimme´diat. Mots x et z sont, respectivement, un pre´xe et un suffixe dunechaˆınedecaracte`res ω sionpeut´ecrire ω = x.z .Demˆeme, y est un facteur de ω sionpeute´crire ω = x.y.z ,ou` x et z sont´eventuellement vides. Approximation Etantdonn´eunprobl`emedoptimisation,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´e) G = ( V, E )estladonn´eedunensembledesommets V (pour “verti-ces,plurielirre´gulierdevertex),etdunensembledareˆtes E V 2 reliant certains sommets. En gros, x y dans G ssi ( x, y ) E . Le graphe comple´mentaire de G ,not´e G est obtenu en mettant desarˆetesl`aou`ilnyenavaitpasetr´eciproquement.Lunion de deux graphes dont les ensembles desommetssontdisjointsestbiend´enie(onmetlesdeuxgraphescoˆtes-a`-coˆte).Ungrapheest dit connexe sicenestpasluniondedeuxgraphes(cest-a`-diresilestdunseultenant). Logique Une variablebool´eenne prend comme valeur “vrai” ( > ) ou “faux” ( ). L’ensemble des formules bool´eennescontientlesvariables, , > ,etilestferm´epourlane´gation( ψ ), le ET ( φ ψ ) ainsi que le OU ( φ ψ ). Une formule est satisfiable s’il existe une assignation des variables qui la rend vraie. Sinon, elle est insatisfiable . Un litt´eral estsoitunevariable,soitlan´egationdunevariable. Uneformuleboole´enneesten forme normale conjonctive Siellepeuts´ecrire ψ = ^ _ ` ij i j
ou` ` ij estunlitt´eral.
1
3 Exercices pour le TD
Exercice 1 ( ? ) : Fragile .Ondisposedunstockdeboulesenverre.Leprobl`emeestded´eterminera` partirdequel´etagedunimmeublelesboulesenverresecassentsionlesjetteparlafenˆetre.Vouseˆtes dansunimmeublea` n e´tages(num´erote´sde1a` n ) et vous disposez de k boules. Il n’y a qu’une seule ope´rationpossiblepourtestersilahauteurdune´tageestfatale:jeterunebouleparlafeneˆtre.Sielle nesecassepas,vouspouvezlare´utiliserensuite,sinonvousnepouvezplus. Vousdevezproposerunalgorithmepourtrouverlahauteur`apartirdelaquelleunsautestfatal (renvoyer n + 1 si on survit encore au n -i`eme´etage)enfaisantleminimumdesauts. 1. Si k ≥ d log 2 ( n ) e , proposer un algorithme en O (log 2 ( n )) sauts. 2. Si k < d log 2 ( n ) e , proposer un algorithme en O k + 2 k n 1 sauts. ( ? ) 3. Si k = 2, proposer un algorithme en 2 n sauts. ( ?? ) 4. Dans ce dernier cas, proposer aussi un algorithme en 2 n sauts. Exercice 2 ( ?? ) : Fragile, le retour .De´crivezunalgorithmequi´etantdonne´ n et k renvoie le nombre minimaldelancers`aeectuerpoureˆtresuˆrdetrouverlasolution.D´eterminersacomplexite´. Exercice 3 ( ?? ) : Set-Cover . On considere un ensemble fini B `a n e´le´ments,etunefamillenie ` S 1 , . . . , S m de sous-ensembles de B .Leproble`me Set-Cover estded´eterminerlepluspetit(ausensdela cardinalit´e)ensemble I 1 , . . . , m tel que : B [ S i i I 1.Donnezunalgorithmeglouton.D´emontrezquilnestpasoptimal. ( ?? ) 2 D´montrez ensuite que si | B | = n , alors il produit une solution qui est au pire ln n fois plus grande . e queloptimale.(Indice:pourc¸a,onpeutprouverquelquechosesurlenombredepointscouverts par chaque choix glouton de l’algorithme). 3.D´emontrerquelepirecasestatteint(asymptotiquement).
4Exercices`afairechezvous
Exercice 4 ( ? ):Proble`meduvoyageurdecommerce .Onconside`reunecartege´ographiquesur laquelle figurent n villes, et un voyageur de commerce qui doit visiter toutes ces villes une fois (et une seule).Levoyageursed´eplaceenavion,enlignedroite.Leprobl`emeconsiste,enpartantdunedes villes,`atrouverunordredanslequelvisitertouteslesautresvillesquiminimiselenombredekilome`tres parcourus. Proposez 3 algorithmes gloutons qui donnent des solutions approximatives auproble`me(onnede-mandepasdeprouverlaqualit´edessolutions).Ildoitˆetrepossible(cenestpasobligatoire)dexhiber des exemples qui montrent que vos algorithmes ne sont pas des λ -approximations si λ est une constante ind´pendante de n . e Exercice 5 ( ?? ) : Algorithme de Kadane . On se donne un tableau A de n ´el´ementsentiers A [1] , . . . , A [ n ].Leprobl`emeestdede´terminerdeuxindices1 i, j n tels que la somme A [ i ] + ∙ ∙ ∙ + A [ j ] est maximale. Notez que j < i est une solution admissible (et alors la somme va t ´ o). Donnez un u zer algorithme (programmation dynamique) qui n’examine chaque case de A qu’une seule fois (et qui termine doncentempsline´aire). Exercice 6 ( ?? ) : Plus long facteur commun .Leprobl`emeestdede´terminerquelleestlalongueurdu pluslongfacteurcommun`adeuxchaıˆnesdecaract`eresdonne´es.Donnezunalgorithme(programmation dynamique)et´evaluezsacomplexit´ e. Exercice 7 ( ?? ):Massacrea`latron¸conneuse .Admettonsquonaitaaire`aunlangagede programmationo`ulaseuleop´erationpossiblesurleschaıˆnesdecaracte`resoitunefonction Split , qui prendenargumentunechaˆınedecaract`ere ω de taille n et un entier k , et qui renvoie deux chaˆınes : un pre´xedetaille k de ω ainsi qu’un suffixe de taille n k .Cetteproc´eduresex´ecutein´evitablementen temps n . On ne peut pas lire les “cases” individuelles des chaˆınes ( !).
2