Licence de Sciences Economiques Annee Universite de Nice Sophia Antipolis Mathematiques L1
3 pages
Français

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

-

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

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

Informations

Publié par
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ˆ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
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents