Algorithmique et Programmation TD n Introduction

Publié par

Niveau: Supérieur
Algorithmique et Programmation TD n? 1 : Introduction Ecole normale superieure Departement d'informatique 2011-2012 1 Mode d'emploi Les exercices 1, 8 et 12 illustrent la technique du“diviser pour regner”avec un niveau de sophistication croissant. Les exercices 4, 3, 9 et 10 sont consacres a la methode gloutonne, et enfin les exercices 2, 5, 6 et 7 sont consacres a la methode de la “programmation dynamique”. L'exercice 11 est inclassable, et ne necessite aucun prerequis. L'exercice 13 est consacre a la preuve de terminaison d'un algorithme (en apparence) simple. Nous ne ferons pas de programmation ensemble, mais l'exercice 8 fournit des fonctions interessantes dont la programmation n'est pas entierement triviale. 2 Petits Rappels diviser pour regner Cette strategie resout un probleme en le decoupant en sous-problemes du meme type, en resolvant recursivement les sous-problemes, et en combinant les sous-resultats de fac¸on appropriee. Cela aboutit typiquement a un fonctionnement “en arbre”. programmation dynamique C'est une generalisation du “diviser pour regner”. Cette methode a pris son nom dans les annees 1950, quand le mot “programmation” signifiait tout autre chose qu'au- jourd'hui. On identifie egalement une collection de sous-problemes, et on les resoud un par un, en commenc¸ant par les plus petits, en utilisant les solutions des petits sous-problemes pour resoudre les problemes plus gros, jusqu'a ce qu'ils soient tous resolus.

  • represen- tation arborescente du cographe pour la nouvelle definition

  • solution de l'exercice

  • qualite des solutions

  • queue-leu-leu

  • borne sur le temps d'execution de l'hydre

  • cographe en temps polynomial

  • solution morceau par morceau


Publié le : mardi 29 mai 2012
Lecture(s) : 65
Source : di.ens.fr
Nombre de pages : 12
Voir plus Voir moins
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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi