NOM Date PRENOM Groupe

Description

Niveau: Supérieur
NOM : Date : . PRENOM : Groupe : . Mathematiques pour la Biologie (semestre 2) : Feuille-reponses du TD 5 La methode de Euler pour l'approximation d'une solution d'une equation differentielle Principe de la methode de Euler Etant donne une equation differentielle dx dt = f(t, x), (1) on veut approximer, pour une valeur initiale x0, une fonction x(t) qui verifie l'equation et pour laquelle on a x(0) = x0. Pour faire cela, on choisit quelques points ti pour lesquels on calcule des approximations xi correspondants. On espere que xi ≈ x(ti). A partir de la valeur x0 on peut calculer dxdt (0) = x?(0) a l'aide de l'equation (1) en calculant f(0, x0). Comme valeur approximative x1 au temps t1 = 0 + t1 on choisit de prendre x0 + dX = x0 + x?(0) · t1. (2) En general, la valeur xi+1 est determinee en ajoutant ∆xi = (ti+1 ? ti) · f(ti, xi) a son predecesseur, la valeur xi : xi+1 = xi +∆xi = xi + (ti+1 ? ti) · f(ti, xi). (3) Fig. 1 – Pour approximer la courbe, on suit la droite tangente a cette courbe.

• methode de euler pour l'approximation


• derivee x?


• x1 au temps t1


• developpement des populations


• feuille-reponses du td


• population initiale

Informations

• Publié par: chaeh
• Nombre de lectures: 9
• Langue: Français

Extrait

TD 5

Algorithmique Rappeldeprobabilit´e: Deux´eve´nementsE 1 etE 2 sont ditsind´sdantepenpaorsliil´tabibsdleueeqivrrxaeueˆmnetneem temps est Pr[E 1 ∩ E 2 ] = Pr[E 1 ]×Pr[E 2 ]. Danslecasleplusge´ne´ralo`uE 1 etE 2 rimeseas´nceptsaantspendnd´eenti:ano,nones

Pr[E 1 ∩ E 2 ] = Pr[E 1 |E 2 ]×Pr[E 2 ] = Pr[E 2 |E 1 ]×Pr[E 1 ],

ou`Pr[E 1 |E 2 r´esentelaper]litie´ocdntioinnleelprobabdeE 1 e´nndontta´eE 2 . Quand on a un ensemble d’e´v´enementsnonne´cessairementinde´pendants,ona:

k k−1 E] = P Pr[∩ i=1 i r[E 1 ]×Pr[E 2 |E 1 ]×Pr[E 3 |E 1 ∩ E 2 ]. . .Pr[E k E| ∩ i ]. i=1

Exercice 1:Coupe minimale dans un graphe SoitGntve´eecenemllueueisulpteteˆrasrapheungrect´conn-nro,eone´vaeitnsentrelesnsommets. UnecoupeCdansGtuesnsneblem’aedteˆruqseoisiselnve,ene`lGdevient non-connexe. Unecoupe minimaleutsenadiarecedupconeamepamixnureuoceesletmila.eeLil´tmeniedetrouvprobl`em NP-complet. L’id´eedel’algorithmeestdechoisiruniform´ementuneareˆteetdefusionnerlesdeuxsommets enunseulsommetenmettantsurcesommetlesarˆetesquiarrivaientauxdeuxsommetsinitiauxet enenlevantlesboucles.Onappellecetteope´rationunecontraction.Oegrapheˆmmeselivnioqteu initialn’avaitqu’uneseuleareˆteentrechaquesommet,legrapheayantsubiunecontractionpeut encontenirauplusdeux.Ceprocessusdiminued’uneunite´lenombredesommets.L’algorithme effectuedescontractionsjusqu’`acequelenombredesommetssoite´gal`a2etretournecommevaleur lenombred’arˆetesentrecesdeuxpoints.

1.Montrerqu’unecontractiond’areˆtenediminuepaslavaleurd’unecoupeminimalesionn’enl`eve pasd’areˆted’unecoupeminimale. 2. Soitkla valeur d’une coupe minimale. Montrer queGa au moinskn/.seteˆra2 3. SoitE i env´´el’entdenemdeˆetehciopesaenraisurC`alair1,pout-aip`eeme´e≤i≤n−2. (a) Montrerque Pr[E 1 ]≥1−2/n. i−1 (b) Montrerque Pr[E 2 |E 1 ]≥1−2/(n−[1)etqenPrue´nrelameptulgse´E i |∩ E j ]≥1−2/(n−i+1). j=1 2 (c)Montrerquelaprobabilit´etrouverunecoupeminimaleparceproc´ed´eestaumoins. n(n−1)