Deuxièmes années Lycée Masséna

CCP 2015 MP SI : Corrigé de la partie info

Avertissement. On suppose les fonctions du module math importées : on utilisera cos, sin et sqrt.

Question 11. Yi+1 = Yi + hF (ti, Yi)

Question 12. En supposant que Yi est une liste à deux éléments, on a :

def fi(t,Y):return [Y[1],5/(7*m*(R-r))*(F0*sin(wbob*t)*cos(Y[0])-fv*(R-r)*Y[1]-m*g*sin(Y[0]))]

Question 13. La structure pour Yini est inutilement compliquée (liste de listes ?), mais jouons le jeu : on supposequ’il est donné comme une liste contenant deux listes à un seul élément. On se ramène à une structure de liste à deuxéléments permettant d’exploiter la fonction précédente.

def Euler(Yini,h,Tmaxi,F):n=int(Tmaxi/h)Y=[Yini[0][0],Yini[1][0]]SY=[[0]+Y]t=0for i in range(n):

FY=fi(t,Y)Y=[Y[0]+h*FY[0],Y[1]+h*FY[1]]t+=hSY.append([t]+Y)

return SY

Question 14. À Tmaxi fixé, on fait O(1/h) opérations : en effet chaque tour de boucle dans la fonction précédentes’effectue en temps constant, et on fait

⌊Tmaxi

h

⌋opérations. Ainsi si h est divisé par 10, le temps de calcul est multiplié

par 10.

Question 15. On fait parcourir à t, th et thp les valeurs de SY (la variable th est utilisée pour θ et thp pour.

θ) :on parcourt les éléments de SY, qui sont des listes à trois éléments, et on déconstruit directement chacune de ses listesà l’aide des trois variables. On utilise à nouveau la fonction fi pour calculer

..

θ qu’on stocke dans la variable thpp. Onpeut alors calculer les coefficients NI et TI . Si pour l’un des temps le rapport est strictement supérieur à f en valeurabsolue, on renvoie False. Sinon, on renvoie True en fin de fonction.

def VerifRSG(SY,f):for t,th,thp in SY:

thpp=fi(t,[th,thp])[1]NI=F0*sin(wbob*t)*sin(th)+m*g*cos(th)+m*(R-r)*thp**2TI=2/5*m*(r-R)*thppif abs(TI/NI)>f:

return Falsereturn True

Question 16. Je vous laisse répondre à cette question.

Question 17.

def Valeur_efficace(T,a,b):s=0for i in range(a,a+b):

s+=T[i]**2return sqrt(s/b)

La complexité est en O(b).

Question 18. • Comme N � Nmaxi, on peut considérer que l’on fait O(Nmaxi) itérations de la boucle dans le pirecas, sans surestimer la complexité. Le calcul de la valeur efficace a une complexité O(N). On a donc une complexitéO(N ×Nmaxi).

• Avec cette nouvelle écriture, le calcul de la valeur efficace se fait en temps O(1) (à part la première). On a doncune complexité O(Nmaxi) pour la boucle, et donc pour la fonction car N � Nmaxi. C’est mieux !

Svartz Page 1/2 2015/2016

Deuxièmes années Lycée Masséna

Question 19. Une structure de type pile ne permet d’accéder qu’à la mesure la plus récente. Ainsi pour pouvoirsupprimer la plus ancienne mesure (il y en a N), il faudrait dépiler entièrement la pile (dans une autre pile), supprimerla dernière mesure et rempiler les autres, ce qui aurait une complexité en O(N) : la structure de pile, bien qu’utilisable,n’est clairement pas adaptée ici.

Question 20.

def Init_Tampon(N,Te):T=creer_file()for i in range(N):

enfiler(T,Mesure(Te))return T

Question 21. En notation Python et pas en pseudo-code :

x=defiler(T)y=mesure(Te)enfiler(T,y)Xeff=sqrt(Xeff*Xeff+y*y-x*x)

Svartz Page 2/2 2015/2016