NOM Date PRENOM Groupe

Description

Niveau: Supérieur
NOM : Date : . PRENOM : Groupe : . Mathematiques pour la Biologie (semestre 2) : Feuille-reponses du TD 4 Loi de conservation pour le modele de Lotka-Volterra Exercice 1. : 1. Soit H(x, y) = 3 ln y ? 0.2y + 4 lnx ? 0.1x. Calculer les deux derivees partielles de H puis ses 4 derivees partielles secondes. 2. Calculer la valeur de la fonction H puis la valeur de son vecteur gradient au point (x = 70, y = 20). 3. Trouver le gradient de la fonction f(x, y) = y lnx. Meme question pour la fonction g(x, y) = x+yx?y . 4. Calculer l'equation de la courbe de niveau k=2 de la fonction g puis tracer cette courbe. 1

• systeme dynamique de lotka-volterra


• champ de vecteur


• droite tangente


• vecteurs tangents


• vecteur sur la figure


• loi de conservation pour le modele de lotka-volterra


• graphes des solutions du systeme de lotka-voterra

Sujets

• Champ de vecteurs

Informations

• Publié par: chaeh
• Nombre de lectures: 23
• 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