Correction CNC 2016

Télécharger Sujet:

cnc2016

Correction:

################

###PROBLEME 1###

################

#Q1

«  » »α=1;β=0″ » »

#Q2

def Heun(f,t0,y0,T,N):

    les_t=[t0]

    les_y=[y0]

    t=t0

    h=(T-t0)/N

    y=y0

    while t<T:

        y=y+h/2*(f(t,y)+f(t+h,y+h*f(t,y)))

        les_y+=[y]

        les_t+=[t+h]

        t=t+h

    return(les_t,les_y)

#Q3

def Euler(f,t0,T,y0,N):

    les_t=[t0]

    les_y=[y0]

    y=y0

    t=t0

    h=(T-t0)/N

    while t<T:

        y=y+h*f(t,y)

        les_y+=[y]

        les_t+=[t+h]

        t=t+h

    return(les_t,les_y)

#Q4

«  » »la taille du problème est N, posons T(N) le coût du programme Euler, nous avons:

    les_t=[t0] a un coût constant O(1) (coût d’une affectation)

    les_y=[y0] a un coût constant O(1) (coût d’une affectation)

    y=y0 a un coût constant O(1) (coût d’une affectation)

    t=t0 a un coût constant O(1) (coût d’une affectation)

    h=(T-t0)/N a un coût constant O(3) (coût d’une affectation+coût d’une soustraction+coût d’une division)

    la boucle while itère N fois pour calculer les N valeurs restantes de yi correspondantes aux temps ti avec i variant de 1 à N.

    y=y+h*f(t,y) a un coût constant O(4) (coût d’une affectation, coût d’une addition, coût d’une multiplication et coût de f qui est constant O(1))

    les_y=les_y+[y] coût constant O(2) (coût d’une affectation, coût d’une concaténation)

    les_t=les_t+[t+h] coût constant O(3) (coût d’une affectation, coût d’une concaténation, coût d’une addition)

    t=t+h coût constant O(2) (coût d’une affectation, coût d’une addition)

    return(les_t, les_y) coût nul (return n’est pas une opération élémentaire)

    donc T(N)=7+11*N=O(N)

la fonction Euler a une complexité linéaire.

«  » »

#Q5

«  » »le système de deux équations  différentielles du premier ordre est:

    nous avons U »l+U’l+Ul=-4π²cos(2πt)

    on pose y(t)=Ul(t) et z(t)=U’l(t)

    donc le système est:

        y'(t)=z(t)

        z'(t)=-4π²cos(2πt)-z(t)-y(t)

«  » »

#Q6

«  » »En posant Y(t)=[Ul(t),U’l(t)] donc y'(t)=[U’l(t),U »l(t)]=F(t,Y(t))

avec F:t,X—>F(t,X)=[X[1],-4π²cos(2πt)-X[1]-X[0]] » » »

#Q7

import matplotlib.pyplot as pp

import numpy as np

import scipy.integrate as si

F=lambda X,t:np.array([X[1],-4*(np.pi**2)*np.sin(2*np.pi*t)-X[1]-X[0]])

t=np.linspace(0,3,1001)

les_y=si.odeint(F,np.array([0,0]),t)

Y=les_y[:,0]

pp.plot(t,Y,’r’)

F1=lambda t,X:np.array([X[1],-4*(np.pi**2)*np.sin(2*np.pi*t)-X[1]-X[0]])

les_y=Heun(F1,0,np.array([0,0]),3,1000)[1]

Y1=np.array(les_y)[:,0]

pp.plot(t,Y1,’g’)

les_y=Euler(F1,0,3,np.array([0,0]),1000)[1]

Y2=np.array(les_y)[:,0]

pp.plot(t,Y2,’b’)

pp.xlabel(« temps(s) »)

pp.title(« circuit RLC, tension bobine »)

pp.ylabel(‘tension (mv)’)

pp.legend((‘Odeint’,’Heun’,’Euler’), »upper right »)

pp.show()

################

###PROBLEME 2###

################

#Q8

def enMajuscule(ch):

    ch1= » »

    for i in range(len(ch)):

        if ch[i]>=’a’ and ch[i]<=’z’:ch1+=chr(ord(ch[i])-32)

        elif ch[i]==’ç’or ch[i]==’Ç’:ch1+=’C’

        elif ch[i] in ‘âà’or ch[i] in ‘ÀÂ’:ch1+=’A’

        elif ch[i] in ‘éèêë’ or ch[i] in ‘ÈÉÊË’:ch1+=’E’

        elif ch[i] in ‘ïî’or ch[i] in « ÎÏ »:ch1+=’I’

        elif ch[i] in ‘ùûü’ or ch[i] in « ÙÛÜ »:ch1+=’U’

        elif ch[i]==’ô’ or ch[i]== »Ô »:ch1+=’O’

        elif ch[i]==’ÿ’ or ch[i]==’Ϋ’:ch1+=’Y’

        else:ch1+=ch[i]

    return(ch1)

#Q9

def majusculesSeules(texte):

    ch= » »

    alpha= »abcdefghijklmnopqrstuvwxyz »

    Alpha=enMajuscule(alpha)

    carspe= »âàéèêëïîùûüôÿç »

    carspeMaj= »ÀÂÈÉÊËÎÏÙÛÜÔΫÇ »

    for i in range(len(texte)):

        if texte[i] in alpha or texte[i] in Alpha or texte[i] in carspe or texte[i] in carspeMaj:

            ch+=enMajuscule(texte[i])

    return(ch)

#Q10

def vigenereEncode(ch,cl):

    texte=majusculesSeules(ch)

    ALPHA= »ABCDEFGHIJKLMNOPQRSTUVWXYZ »

    CH= » »

    for i in range(len(texte)):

        CH+=ALPHA[(ALPHA.index(texte[i])+ALPHA.index(cl[i%len(cl)]))%26]

    return(CH)

#Q11

«  » » la complexité de la fonction vigenereCode dans le pire des cas est:

    la taille du problème est la taille de CH égale à la taille de la variable texte qu’on pose N,

    l’instruction texte=majusculesSeules(CH) a un coût linéaire O(N+1) (coût d’une affectation et le coût de la fonction majusculesSeules qui est linéaire)

    l’instruction ALPHA= »ABCDEFGHIJKLMNOPQRSTUVWXYZ » a un coût constant O(1)

    ch= » » a un coût en O(1)

    la boucle fera dans le pire des cas N itérations

    l’instruction du corps de la boucle a un coût constant 0(5+2*26) (une affectation, une concaténation, une somme, deux calculs de reste et le coût de la fonction index O(26) appelée deux fois)

donc T(N)=N+1+1+1+N(5+2*26)=O(N) le coût est donc linéaire.

«  » »

#Q12

def vigenereEncodeRec(ch,cl,i,N):

    «  » » i est l’indice du caractère de la clé avec lequel la lettre d’indice 0 de ch sera codée

        N est la taille de la clé cl

        ch est la chaine à coder

        cl est la clé » » »

    ALPHA= »ABCDEFGHIJKLMNOPQRSTUVWXYZ »

    if len(ch)==1:

        return(ALPHA[(ALPHA.index(ch[0])+ALPHA.index(cl[i]))%26])

    else:

        return(vigenereEncodeRec(ch[0],cl,i)+vigenereEncodeRec(ch[1:],cl,(i+1)%N))

#Q13

«  » »posons N=len(ch)

pour une taille N de ch, nous avons:

    une affectation ALPHA= »ABCDEFGHIJKLMNOPQRSTUVWXYZ », un test if len(ch)==1, une concaténation, une somme et un calcul de reste donc un coût en O(5), s’ajoute le coût pour crypter ch[0] qui coûte 2+2*26 (une somme, un  calcul de reste et deux appels de la fonction index dont le coût est constant dans le problème O(26)) et on ajoute le coût pour crypter les n-1 caractères restants de ch.

    donc T(N)=c+T(N-1) et T(1)=c’ avec c=7+2*26 et c’=4+2*26

    T(N)=(N-1)c+c’=O(N)

la complexité de la fonction vigenereEncodeRec est linéaire » » »

#Q14

def vigenereDecode(ch,cl):

    ALPHA= »ABCDEFGHIJKLMNOPQRSTUVWXYZ »

    ch1= » »

    for i in range(len(ch)):

        ch1+=ALPHA[(ALPHA.index(ch[i])-ALPHA.index(cl[i%len(cl)]))%26]

    return(ch1)

#Q15

«  » »la clé doit être assez longue et variée » » »

#Q16

def sousChaines(CH,d,p):

    assert d<len(CH)

    ch= » »

    for i in range(d,len(CH),p):

        ch+=CH[i]

    return(ch)

#Q17

def listeDesSousChaines(CH,d):

    L=[]

    for i in range(d):

        L+=[sousChaines(CH,i,d)]

    return(L)

#Q18

def frequenceCaracteres(CH):

    L=[0]*26

    for i in range(len(CH)):

        L[ord(CH[i])-65]+=1

    return(L)

#Q19

def code(CH,p):

    L=listeDesSousChaines(CH,p)

    cle= » »

    for i in range(len(L)):

        L1=frequenceCaracteres(L[i])

        jmax=0

        for j in range(len(L1)):

            if L1[jmax]<L1[j]:jmax=j

        d=(jmax-4)%26

        cle+=chr(65+d)

    return(cle)

################################FIN D’EPREUVE################################