Algorithmique On note ZN l'anneau quotient Z N ·Z Z N le groupe multiplicatif de cardinal N et len x la

Publié par

TD 7 Algorithmique On note ZN l'anneau quotient Z/N ·Z, Z?N le groupe multiplicatif de cardinal ?(N) et len(x) la longueur en bits d'un entier x. Exercice 1: Exponentiation 1. On suppose que l'on a ?1, . . . , ?k ? ZN , avec des entiers positifs e1, . . . , ek, ou len(ei) ≤ pour i = 1, . . . , k. Montrer comment calculer ? = ?e11 · · ·? ek k en utilisant + O(1) elevations au carre dans ZN et + 2k + O(1) multiplications dans ZN . 2. Montrer comment calculer ?e, ou ? ? ZN pour un exposant e de bits. Montrer que pour tout parametre entier positif k, on peut utiliser un precalcul qui utilise + O(1) elevations au carre dans ZN et 2k?1+O(1) multiplications dans ZN et ensuite on peut calculer ?e pour tout exposant e de bits en utilisant seulement +O(1) elevations au carre et 2k?1+/k+O(1) multiplications. 3. Que peut-on faire si ? est fixe ? Exercice 2: Tests de Primalite Un nombre de Carmichael est un nombre compose tel que pour tout a ? Z?n: a n?1 = 1 mod n.

  • groupe multiplicatif de cardinal ?

  • parametre entier positif

  • meme algorithme

  • demonstration du theoreme d'euler

  • ty mod

  • theoreme des restes

  • cardinal de z

  • symbole de legendre

  • entier

  • algorithme d'euclide etendu


Publié le : mardi 19 juin 2012
Lecture(s) : 77
Source : di.ens.fr
Nombre de pages : 4
Voir plus Voir moins
NOM : PRENOM :
Date : Groupe :
Mathe´matiquespourlaBiologie:Feuille-r´eponsesduTD7 Equationsdi´erentielles:m´ethodedEuleretcomple´ments
. .
Exercice 1.:nOel´evolmod`elispopataluoituledninledeesndiobaestnqitaale´nalcorlauepa dynamique suivante : y 0 y= 0,08y(1). 400000 1.Dequeltypedemod`elesagit-il?Querepr´esententlesconstantes0,08 et 400000?
2.Alissuedunelonguepe´riodedesurexploitation,onestimequeleectifdecettepopulationde baleineesttombe´a`70000.Ensupposantquoninterditalorssonexploitation,calculer,aumoyende lam´ethodedEuler,uneapproximationdesone´volutiony0,y1,y2, ....en prenant un pas de temps 0 hEederulurpo´eltauqnoi=1.Onrappleeluqlemae´htdoy=f(yti:e´sr)c tn=tn1+h (1) yn=yn1+hf(yn1). Indiquervotrere´ponsepuispre´sentersuccintementlescalculsquivousyontconduit: y0= 70000, y1=y.......... ,2=...............
3. Quepouvez-vous dire de limn→∞yn?
1
4.Onsupposequelonautoriseunquotadepe`chedehsteequminaqeeualyd-ta`d-ri000,ces=3 alors y 0 y= 0,08y(1)3000. 400000 Indiquerquelssontlese´quilibresdecettedynamiqueetpr´eciserleurstabilite´.
5.Quadvient-ila`lapopulationdebaleinesdanscecas(etseloncemode`le)sachantquey?(0) = 70000
6.Reprendreles3dernie`resquestionsensupposantcettefoisquaudeladuquotal´egallesactivite´s dep`echeillicitesportentlepre´le`vementsurlaressourcede3000`a5000.
Exercice 2.:ednoe´ltauqdnoi´eintrellieecllurenuaepporixmationdelasolutinOert´insca`asees dy(t) 2 = 18y(t) de condition initiale y(0)=-0,1. dt 1.V´erierparlecalculquey(t) =yrudeuastnalg,enutilibre)puisqe´(iliuulosnoites=0netu champdevecteurassocie´,expliquerpourquoiunesolutiondecette´equationdeconditioninitiale positive(resp.ne´gative)restepositive(resp.n´egative)pourtoutt >0. Indiquer sur la figure l’allure quedevraitavoira`votreavislasolutionconside´re´e.
Champ de vecteurs de y'=18y^2 1
y 0.5
0 ±1 12 3 4 x ±0.5
±1
02 Fig.hampsdev1Lecelitlereneonti´di´aluaeqcoss`e´ietceasruy= 18y.
2
2. Calculerles 4 premiers termes de l’approximation d’Euler de la solution de condition initialey(0) = 0,1 en prenant h=1.
3.Comparerlesre´sultatsdesdeuxquestionspr´ece´dentes.Quenpensez-vous?
Exercice 3.:deuiruqmAe´assedruegavaretcldersieumbanspiLachenilledel´pecie´eatsnunies nordquiest`aloriginederavagesimportantsparde´foliationlorsdesespullulations.Ladynamiquedela populationdeschenilles,propos´eeparLudwig,JonesetHollingen1978,estrepr´esente´eparle´quation die´rentiellesuivante:   2 dy(t)y(t) 4by(t) =ry(t) 1− −(2) 2 2 dt4a a+ 4y(t) o`uy(tes`anillstanlinlutapapoceehoidngnsiatelllaieledte´d)tu`oter,aetbrapaestds.Lreeetm`nos 2 by terme2lapupolaures´ercsellinehcednoitdemr´rpeutseetenuimod´eledationqssoienexsilepaer a2 +y 4 parunoiseauquiestsonprincipalpre´dateur(bptseoporiortelnnla`ailtaelecttpepolutaoindoiseaux). 1. Supposons queboC.0=atsenmmceleelppedomytepdena`dleaspasceculierticesencr(ab depr´edateurs)?Indiquercequerepre´sentelesconstantesretaet quel serait, dans ce cas, le comportement de la population de chenilles.
3
2 4b 2.De´signonsparf(y) la fonctionf(y) =ry(1)2 2rostLe.suivanteisguresneettnrspe´rse 4a a+4y les graphes deflorsquer= 0,1 etbetr`e2=op00rsdialeuoisvurtrramadspuneet´rea. Dans chacundescas,liresurcesgrapheslenombred´equilibresdeladynamique,enindiquantleurvaleurs approximatives,puis,toujourssanscalcul,pre´ciserleurstabilit´e.
40 f 20
0 1000 2000 3000 4000 5000 6000 y
-20
-40
a= 1700
40 f 20
0 2000 4000 6000 8000 y -20
-40
a= 2150
60
40 f 20
0 2000 4000 6000 800010000 y -20
a= 2500
3. Supposonsque la population initiale de chenilles soity(0) = 1000. Indiquer, dans chacun des trois caspr´ec´edentsquelcomportementlemod`elepr´evoitpourcettepopulation.Avotreavis,lundeux me´rite-t-illenomdepullulation?
4.Danscetypedemode`le,latailledelapopulationpourrait-elletendreverslinni(siparexemple sa valeur initialey(t)etnuoP?ouqr?itr`etaitortasimp)e´
4
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.