Algorithmique et Programmation TD n Introduction

Description

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

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 66
• Langue: Français

Extrait

Algorithmique et Programmation TD n ◦ 1 : Introduction Ecolenormalesupe´rieure D´epartementd’informatique [e-mail] 2011-2012

1 Mode d’emploi Lesexercices1,8et12illustrentlatechniquedu“diviserpourr´egner”avecunniveaudesophistication croissant.Lesexercices4,3,9et10sontconsacr´es`alam´ethodegloutonne,etenfinlesexercices2,5, 6et7sontconsacre´s`alame´thodedela“programmationdynamique”.L’exercice11estinclassable,et nene´cessiteaucunpr´erequis.L’exercice13estconsacre´a`lapreuvedeterminaisond’unalgorithme(en apparence) simple. Nousneferonspasdeprogrammationensemble,maisl’exercice8fournitdesfonctionsint´eressantes dontlaprogrammationn’estpasentie`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`aunfonctionnement“enarbre”. programmation dynamique C’estunege´ne´ralisationdu“diviserpourre´gner”.Cetteme´thodeapris sonnomdanslesann´ees1950,quandlemot“programmation”signifiaittoutautrechosequ’au- jourd’hui.Onidentifiee´galementunecollectiondesous-proble`mes,etonlesr´esoudunparun,en commen¸cantparlespluspetits,enutilisantlessolutionsdespetitssous-problemespourr´esoudre ` lesprobl`emesplusgros,jusqu’a`cequ’ilssoienttousr´esolus.Ladiffe´renceavecl’approche“divide andconquer”debaseestqueleprocessusn’estpasdecritparunarbre,maisparungrapheoriente´ ´ acyclique(lasolutiond’unsous-proble`mepeutre-servirplusd’unefoisdanslasuite). algorithmes gloutons Cesme´thodesconstruisentg´en´eralementunesolutionmorceauparmorceau,et enchoisissantleprochainmorceau,elleschoisissentsyste´matiquementceluiquiprocurel’avantage lepluse´videntetleplusimme´diat. Mots x et z sont, respectivement, un pre´fixe et un suffixe d’unechaˆı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`emed’optimisation,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´eed’unensembledesommets V (pour “verti- ces”,plurielirre´gulierde“vertex”),etd’unensembled’areˆ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`iln’yenavaitpasetr´eciproquement.L’ union de deux graphes dont les ensembles desommetssontdisjointsestbiend´efinie(onmetlesdeuxgraphescoˆtes-a`-coˆte).Ungrapheest dit connexe sicen’estpasl’uniondedeuxgraphes(c’est-a`-dires’ilest“d’unseultenant”). 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´egationd’unevariable. Uneformuleboole´enneesten forme normale conjonctive Siellepeuts’´ecrire ψ = ^ _ ` ij i j

ou` ` ij estunlitt´eral.

1

3 Exercices pour le TD

Exercice 1 ( ? ) : Fragile .Ondisposed’unstockdeboulesenverre.Leprobl`emeestded´eterminera` partirdequel´etaged’unimmeublelesboulesenverresecassentsionlesjetteparlafenˆ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´rationpossiblepourtestersilahauteurd’une´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`aeffectuerpoureˆtresuˆrdetrouverlasolution.D´eterminersacomplexite´. Exercice 3 ( ?? ) : Set-Cover . On considere un ensemble fini B `a n e´le´ments,etunefamillefinie ` 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´emontrezqu’iln’estpasoptimal. ( ?? ) 2 D´montrez ensuite que si | B | = n , alors il produit une solution qui est au pire ln n fois plus grande . e quel’optimale.(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,enpartantd’unedes villes,`atrouverunordredanslequelvisitertouteslesautresvillesquiminimiselenombredekilome`tres parcourus. Proposez 3 algorithmes gloutons qui donnent des solutions approximatives auproble`me(onnede- mandepasdeprouverlaqualit´edessolutions).Ildoitˆetrepossible(cen’estpasobligatoire)d’exhiber 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 .Admettonsqu’onaitaffaire`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´fixedetaille k de ω ainsi qu’un suffixe de taille n − k .Cetteproc´edures’ex´ecutein´evitablementen temps n . On ne peut pas lire les “cases” individuelles des chaˆınes ( !).

2