Universite de Rouen Master MFA Analyse des EDP

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

• Identité
• Déduction

Informations

• Publié par: larec
• Nombre de lectures: 29
• Langue: Français

Extrait

TD 4

Algorithmique

Exercice 1:Coupe minimale dans un graphe SoitGsegnuhparnecteconon-o´e,n´taeirneveneev´cmeleeltuieusplntteˆrasrulertnesensommets. UnecoupedansGestunensteˆruqselbmea’del`ene,evioisesnlGdevient non-connexe. Unecoupe minimaletedevuornureuocealimLee.obpreml`pemaximaleestdepuocenutseinemt´linadiarec NP-complet. L’ide´edel’algorithmeestdechoisiruniform´ementuneareˆteetdefusionnerlesdeuxsommets enunseulsommetenmettantsurcesommetlesarˆetesquiarrivaientauxdeuxsommetsinitiauxet enenlevantlesboucles.Onappellecetteop´erationunecontractionilesemmˆephraegO.qteuvnio initialn’avaitqu’uneseulearrˆeteentrechaquesommet,legrapheayantsubiunecontractionpeut encontenirauplusdeux.Ceprocessusdiminued’uneunit´elenombred’areˆte.L’algorithmeeffectue descontractionsjusqu’`acequelenombredesommetssoite´gala`2etretournecommevaleurle nombred’areˆtesentrecesdeuxpoints.

1.Montrerqu’unecontractiond’arˆetenediminuepaslavaleurd’unecoupeminimale. 2. Soitkla valeur d’une coupe minimale. Montrer queGa au moinskn/ra2teˆes. 3. SoitE i runearˆetaesdcehoisinedtnepee´´vnemel’Ca`ali-i`emeuo1re´atepp,≤i≤n−2. (a) Montrerque Pr[E 1 ]≥1−2/n. i−1 (b) Montrerque Pr[E 2 |E 1 ]≥1−2/(n−enemalern´´esglue)pt1[rPeuqtE i |∩ E j ]≥1−2/(n−i+1). j=1 2 (c)Montrerquelaprobabilite´trouverunecoupeminimaleparceproce´d´eestaumoins. n(n−1) 4.Montrercommentobtenirunalgorithmedontlaprobabilite´d’e´checsoit<1/eet donner sa complexit´e.

Exercice 2:nusnadevitisnartretuˆoClhegrap 3 1.Rappelerl’algorithmedeFloyd-WarshallpourcalculerlaclˆoturetransitiveenΘ(n) en temps. 2.Montrerques’ilexisteunalgorithmequicalculelacloˆturetransitived’unematricen×nenA(n) additions,multiplicationsd’e´l´ementsd’unsemi-anneauetsiA(3n)≤c∙A(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 4∙M(n/2)≤M(n) etM(2n)≤c∙M(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œccffi`a..M]∪ {∞}. On veut calculer la matriceCde cœfficients c ik = min(a ij +b jk ). 1≤j≤n 3 1. Montrerque l’algorithme classique fonctionne enO(nlogM). 2.Onpeutame´liorerunpeucetalgorithmeenutilisantlefaitquepoura6=b, a bmin(a,b) lim (x+x)/x= 1 x→0 a b et donc min(a, b) = log(x+x)/logxpourxpetit. P n b k (a) Soitb 1 , . . . , b n ,nentiers positifs, et soitf(x) =xeta= min(b 1 , . . . , b n ). 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-cequecetalgorithmeestplusrapidequandils’agitdematricesboole´ennes?

Exercice 4:2eS-`lmeobPrTA Soitx 1 , . . . , x n un ensemble denpsraelestneisriravelbaoobseel´esnndeineex´≤n.Unlitt´eral sur cet ensemble de variables est une variablex i i≤ntigaonsuo,e´na¬x i . Une 2-clause sur cet 0 ensembledevariableestunedisjonctiondedeuxlitt´eraux`∨`. Une assignationτest une fonction de l’ensemblex 1 , . . . , x n dans{0,1}itt´’unleurdavalL.rela`ioatgnsiasneaut`menetavirlenτ, soit V(`, τatgsee´)a`elτ(x i ) si`=x i ea1t`−τ(x i ) si`=¬x i . 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 variablesx 1 , . . . , x n e´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-clausessurl’ensembledevariablesx 1 , . . . , x n rieot´ennguphraeGdont 0 lessommetssontleslitte´rauxsurl’ensembledevariablesx 1 , . . . , x n . Pour chaque clause`∨`, 0 0 onajoute`aGuarneteˆelaaltned¬`a``rˆeteallantdetenuae¬``a`eosnpuoo`(¬¬x i =x i ). (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