Licence de Sciences Economiques Annee Universite de Nice Sophia Antipolis Mathematiques L1

Sophia - Antipolis Mathematiques

Description

Niveau: Supérieur, Licence, Bac+1
Licence de Sciences Economiques Annee 2007-2008 Universite de Nice Sophia-Antipolis Mathematiques L1 FEUILLE DE TRAVAUX DIRIGES 4 Exercice 1 (Examen fevrier 2005). On considere la fonction{ f : R2 ? R (x1, x2) 7? x21 + x1x2 + x22 + x1 + 2x2 + 4. (1) Justifier en une phrase que f admet des derivees partielles d'ordre deux. (2) Soit (x1, x2) ? R2, determiner ∂f∂x1 (x1, x2) et ∂f ∂x2 (x1, x2). (3) Soit (x1, x2) ? R2, determiner ∂ 2f ∂x21 (x1, x2), ∂ 2f ∂x22 (x1, x2), ∂ 2f ∂x2∂x1 (x1, x2) et ∂2f ∂x1∂x2 (x1, x2). (4) Montrer que ∂f∂x1 (0, ? 1) = 0 et que ∂f ∂x2 (0, ? 1) = 0. Calculer f(0, ? 1). (5) Soit (x1, x2) ? R2, calculer ∂ 2f ∂x21 (x1, x2)? ∂ 2f ∂x22 (x1, x2)? ( ∂2f ∂x1∂x2 (x1, x2) )2 . (6) Montrer que f admet en (0, ? 1) un extremum local.

• triangle de sommets


• quantite ∂


• adoucissant p1


• quantite de lessive achetee


• prix de l'adoucissant p1


• minimum global


• licence de sciences economiques


• y2 ?


• derivees partielles d'ordre

Sujets

• Mathématiques
• Extremum

Informations

• Publié par: profil-ontoe-2012
• Nombre de lectures: 39
• 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