Examen Partiel Algorithmique des Structure de Donnees

chaeh

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

14 pages

Français

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

Niveau: Supérieur
Examen Partiel : Algorithmique des Structure de Donnees Ecole normale superieure Departement d'informatique 5 Decembre 2011 Tous documents autorises. Ne paniquez pas. Il n'est pas indispensable d'ecrire du pseudo-code pour decrire un algorithme. L'important est de se faire comprendre. La rigueur des preuves sera evaluee. Il est possible d'admettre le resultat d'une question pour traiter les suivantes. Exercice 1 : Couverture Monotone minimale. On considere une grille n ? n dont les cases sont soit noires soit blanches. La grille est donnee par une matrice de booleens. Un chemin monotone dans la grille part d'une case noire, termine sur une case noire, et ne peut avancer que vers le bas ou vers la droite. Le but du probleme est de couvrir l'ensemble des cases marquees avec le moins possible de chemins monotones. La strategie generale est de ramener le probleme a une situation de flots maximaux. Comme c'est un peu complique, on va s'y prendre par etapes. D'abord, il est assez clair que la grille definit un reseau de transport de flot ou chaque case est reliee en a celle du bas et a celle de droite. (?) 1. Expliquez comment on peut forcer un flot a atteindre chacune des cases noires. Dessinez un flot maximal pour la grille d'exemple.

probleme de flot maximum de cout minimum

ordre de la partition

lexbfs

partition

temps linaire

flot

Sujets

Lexicographic breadth-first search

Partition

Informations

Publié par	chaeh
Publié le	01 décembre 2011
Nombre de lectures	120
Langue	Français

Extrait

ExamenPartiel:AlgorithmiquedesStructuredeDonn´ees Ecolenormalesup´erieure D´epartementd’informatique td-algo@di.ens.fr 5 Decembre 2011 ´

Tousdocumentsautoris´es.Nepaniquezpas. Iln’estpasindispensabled’´ecriredupseudo-code pourd´ecrireunalgorithme.L’importantestdesefairecomprendre.Larigueurdespreuvessera´evalu´ee. Ilestpossibled’admettrelere´sultatd’unequestionpourtraiterlessuivantes. Exercice 1 : Couverture Monotone minimale .Onconsid`ereunegrille n × n dont les cases sont soitnoiressoitblanches.Lagrilleestdonne´eparunematricedebool´eens.Un chemin monotone dans la grille part d’une case noire, termine sur une case noire, et ne peut avancer que vers le bas ou vers ladroite.Lebutduproble`meestdecouvrirl’ensembledescasesmarque´esaveclemoinspossiblede chemins monotones.

Lastrat´egiege´ne´raleestderamenerleproble`mea`unesituationdeﬂotsmaximaux.Commec’estun peucomplique,onvas’yprendrepare´tapes.D’abord,ilestassezclairquelagrillede´ﬁnitunr´eseaude ´ transportdeﬂoto`uchaquecaseestrelie´eena`celledubaset`acellededroite. ( ? )1.Expliquezcommentonpeutforcerunﬂot`aatteindrechacunedescasesnoires.Dessinezunﬂot maximalpourlagrilled’exemple.Onnecherchepas`aminimiserlenombredechemins. Undesproble`mesdeceﬂotestqu’ilpeut“brancher”:siplusieursunite´sdeﬂotentrentdansunecase, rien n’interdit qu’une partie aille dans la case du bas et que l’autre partie aille dans la case de droite. Cecinecorrespondpastr`esbien`anotrenotionintuitivedecequ’estun“chemin”.Unesolutiontentante a`cepbl`isteraita`imposerunecapacit´ede1surtouteslesareˆtes,maiscelaposedesdiﬃculte´s ro eme cons techniques.Ilfaudraitenparticuliers’assurerquec¸anechangepaslavaleurduﬂotmaximal. ( ?? )2.Montrezcomment,enremplac¸antchacundessommetsassocie´a`unecasenoireparun gadget compose´dedeuxsommets,onpeuttrouverunﬂotquitraversetouteslescasesnoire,enimposant quelacapacite´detouteslesarˆetessoit1.Onnecherchetoujourspas`aminimiserlenombrede chemins. Dessinez un ﬂot maximal possible pour la grille d’exemple. ( ? )3.Expliquezcommentonpeuttransformerlasolutionduproble`medeﬂot(aveccapacite´un)en solutionduproble`medecouverturemonotone,etvice-versa. Maintenant,lemomentquevousattendieztous,oncherche`aminimiserlenombredechemins.Pour cela,onvadirequelesareˆtesontnonseulementune capacite´ c ( u, v ),quilimitelaquantite´deﬂotqui peut passer, mais aussi un couˆt cost ( u, v ). Si f ( u, v )unit´esdeﬂotscirculentlelongd’uneareˆte,alorson “paye” f ( u, v ) ∙ cost ( u, v ),etdoncl’ensembleduﬂotcouˆte: Cost = X f ( u, v ) ∙ cost ( u, v ) ( u,v ) ∈ E Onad´eja`restreintlescapacit´es`aˆetreunitaires.Lescoˆuts,eux,peuventprendren’importequellevaleur dans Z .Ilspeuventenparticulierˆetren´egatifs,cequisigniﬁequepousserduﬂotdansl’areˆteenquestion rapporte un proﬁt .Onimposequelescoˆutssoientsymm´etriques: cost ( u, v ) = − cost ( v, u ). Sinon on pourraitr´ealiserunproﬁtinﬁni(ouuneperteinﬁnie...)enpoussatduﬂotlelongdel’arˆetedansunsens puisdansl’autredefac¸onre´p´etitive.