Universite de Rouen Master MFA Analyse des EDP
3 pages
Français

Universite de Rouen Master MFA Analyse des EDP

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Niveau: Supérieur, Master, Bac+4
Universite de Rouen Master 1, MFA 2010–2011 Analyse des EDP Espaces de Sobolev Sauf mention contraire, les exposants p seront toujours dans [1,+∞]. D'autre part, on notera W 1,p l'ensemble W 1,p(Rn). 1 a) Montrer que si ? est borne et si p ≤ q alors W 1,q(?) ?W 1,p(?) et W 1,q0 (?) ?W 1,p 0 (?). b) Montrer que les resultats ci-dessus sont faux si ? est un ouvert quelconque. [On pourra construire un contre-exemple dans R de la forme (1 + x2) ? 2 avec ? ? R.] 2 Pour ? ?]1? n, 1[, on considere la fonction f(x) = |x|?. a) Montrer que les fonctions f et ?x|x|??2 sont localement integrables. b) Montrer que le gradient de f au sens des distributions est la fonction ?x|x|??2. [On ecrira la formule de Green sur B(0, )c et on fera tendre ? 0.] c) Montrer que f ?W 1,p(B) si et seulement si p < n1?? . d) Conclure que W 1,p(B) 6? C(B) si p < n.

  • sauf mention contraire

  • espaces de sobolev

  • g? ?

  • fk ?

  • universite de rouen master

  • support compact dans ?

  • deduire de l'exercice precedent

  • identite

  • deduire


Sujets

Informations

Publié par
Nombre de lectures 29
Langue Français
TD 4
Algorithmique
Exercice 1:Coupe minimale dans un graphe SoitGsegnuhparnecteconon-o´e,n´taeirneveneev´cmeleeltuieusplntteˆrasrulertnesensommets. UnecoupedansGestunensteˆruqselbmeadel`ene,evioisesnlGdevient non-connexe. Unecoupe minimaletedevuornureuocealimLee.obpreml`pemaximaleestdepuocenutseinemt´linadiarec NP-complet. Lide´edelalgorithmeestdechoisiruniform´ementuneareˆteetdefusionnerlesdeuxsommets enunseulsommetenmettantsurcesommetlesarˆetesquiarrivaientauxdeuxsommetsinitiauxet enenlevantlesboucles.Onappellecetteop´erationunecontractionilesemmˆephraegO.qteuvnio initialnavaitquuneseulearrˆeteentrechaquesommet,legrapheayantsubiunecontractionpeut encontenirauplusdeux.Ceprocessusdiminueduneunit´elenombredareˆte.Lalgorithmeeectue descontractionsjusqu`acequelenombredesommetssoite´gala`2etretournecommevaleurle nombredareˆtesentrecesdeuxpoints.
1.Montrerquunecontractiondarˆetenediminuepaslavaleurdunecoupeminimale. 2. Soitkla valeur d’une coupe minimale. Montrer queGa au moinskn/ra2teˆes. 3. SoitEirunearˆetaesdcehoisinedtnepee´´vnemelCa`ali-i`emeuo1re´atepp,in2. (a) Montrerque Pr[E1]12/n. i1 (b) Montrerque Pr[E2|E1]12/(nenemalern´´esglue)pt1[rPeuqtEi|∩ Ej]12/(ni+1). j=1 2 (c)Montrerquelaprobabilite´trouverunecoupeminimaleparceproce´d´eestaumoins. n(n1) 4.Montrercommentobtenirunalgorithmedontlaprobabilite´de´checsoit<1/eet donner sa complexit´e.
Exercice 2:nusnadevitisnartretuˆoClhegrap 3 1.RappelerlalgorithmedeFloyd-WarshallpourcalculerlaclˆoturetransitiveenΘ(n) en temps. 2.Montrerquesilexisteunalgorithmequicalculelacloˆturetransitivedunematricen×nenA(n) additions,multiplicationsde´l´ementsdunsemi-anneauetsiA(3n)cA(nnu´reel)opruc >0 et toutnentier positifs, alors il existe un algorithme de multiplication avecM(n) =O(A(n)) additions et multiplications. 3. Montrerque si le produit de deux matricesn×nutpentreˆeela´lceucM(n) additions et mul-tiplications et si 4M(n/2)M(n) etM(2n)cM(n) pour uncet toutncalstoˆl,rolaure transitive se calcule enA(n) =O(M(n)) additions et multiplications. 4.Montrerquelesemi-anneaubool´eenB= ({0,1},,,0,1) n’est pas un anneau. log 72 5. SoitAetBdeux matricesn×nptuestcelaucbeoloelr´eeennes.LeproduinO(n(logn=) ) 2.82 O(neualsnqiuterlcoˆsbintions,aiairepo)are´tisiantr.ve
Exercice 3:Chemins de longueur minimale Onutiliselesemi-anneaudesr´eelspourtraiterlescheminsdelongueurminimaldansungraphe. SoitAetBdeux matricesn×n[s0dsnaeitnœcc`a..M]∪ {∞}. On veut calculer la matriceCde cœfficients cik= min(aij+bjk). 1jn 3 1. Montrerque l’algorithme classique fonctionne enO(nlogM). 2.Onpeutame´liorerunpeucetalgorithmeenutilisantlefaitquepoura6=b, a bmin(a,b) lim (x+x)/x= 1 x0 a b et donc min(a, b) = log(x+x)/logxpourxpetit. P n b k (a) Soitb1, . . . , bn,nentiers positifs, et soitf(x) =xeta= min(b1, . . . , bn). Montrer k=1 m alors quea=d−(1/m) logf(2 )epour toutm >logn. (b)Soitunr´eel0< x <1 etzerideiobnabnmitneolezn´tearrr´eedseatrˆeeptoesdeelnx. Alors d−(1/m) logxe= 1 +bz/mc. (c) Donnerun algorithme qui calcule le (min,+)-produit de deux matricesAetBrate´sdecneevse log 7log 72 dans [0..M]∪ {∞}enO(niqetm´thleurssueare´po)irasnoitrse´leosuO(n(Mlogn) ) op´erationsbinaires. 3. Comparerles deux algorithmes et donner la valeur deMpour laquelle le premier algorithme est plus efficace. 4.Est-cequecetalgorithmeestplusrapidequandilsagitdematricesboole´ennes?
Exercice 4:2eS-`lmeobPrTA Soitx1, . . . , xnun ensemble denpsraelestneisriravelbaoobseel´esnndeineex´n.Unlitt´eral sur cet ensemble de variables est une variablexiintigaonsuo,e´na¬xi. Une 2-clause sur cet 0 ensembledevariableestunedisjonctiondedeuxlitt´eraux``. Une assignationτest une fonction de l’ensemblex1, . . . , xndans{0,1}itt´unleurdavalL.rela`ioatgnsiasneaut`menetavirlenτ, soit V(`, τatgsee´)a`elτ(xi) si`=xiea1t`τ(xi) si`=¬xi. La valeur d’une clauseca`tnemevrelati une assignationτ, soitV(c, τleuresvaesdesdestsel)e,umdmamixAS-2Tlboreme`uxraep.Lliux´ett s´enoncecommesuit: ´ Etantdonne´unentiernet une liste de 2-clauses sur l’ensemble de variablesx1, . . . , xne´ndtrerei,m s’il existe une assignationτennodiuqsetuota`uslascleliladeestslevalaue1rp(orbl`emeded´ecisio.)n Calculer une telle assignation si elle existe (calcul d’une solution).
1.Onassociea`unelistede2-clausessurlensembledevariablesx1, . . . , xnrieot´ennguphraeGdont 0 lessommetssontleslitte´rauxsurlensembledevariablesx1, . . . , xn. Pour chaque clause``, 0 0 onajoute`aGuarneteˆelaaltned¬`a``rˆeteallantdetenuae¬``a`eosnpuoo`(¬¬xi=xi). (a) Montrerque l’on peut calculerGen tempsO(n+m`u)onest le nombre de variables etm lenombredeclauses.Onexpliciteraunchoixdestructuresdedonn´eesetonproposeraune description de l’algorithme en terme de pseudo-code.
2