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

###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################################