(Sujet1,Sujet2)

## Q 1.1

# Indices 2 et 7

## Q 1.2

def chaines_egales(chaine1,chaine2):
  n = len(chaine1)
  i = 0
  while i<n:
      if chaine1[i] != chaine2[i]:
          return False
      i += 1
  return True

## Q 1.3

def liste_occurences(texte,mot):
  res = []
  n = len(mot)
  for i in range(len(texte)-n+1):
      if chaines_egales(mot,texte[i:i+n]):
          res.append(i)
  return res

## Q 1.4

def premiere_occurence(texte,mot):
  l = liste_occurences(texte,mot)
  if l == []:
      return None
  else:
      return l[0]

## Q 2.1

# ATTAC

## Q 2.2

def longueur_bord(ch):
  n = len(ch)
  jmax = 0
  for j in range(1,n):
      if chaines_egales(ch[:j],ch[n-j:]):
          jmax = j
  return jmax

## Q 2.3

def longueur_bords_prefixes(ch):
  B = []
  for j in range(len(ch)):
      B.append(longueur_bord(ch[:i+1]))
  return B

## Q 2.

# [0,1,0,0,0,1,2,3]

## Q 5

def kmp(texte,mot):
  n = len(texte)
  p = len(mot)
  B = longueur_bords_prefixes(mot)
  i = 0
  j = 0
  while i <= n-p:
      while j<p and mot[j] == texte[i+j]:
          j += 1
      if j == p:
          return i
      if j == 0:
          i = i+1
      else:
          i = i+j - B[j-1]
          j = B[j-1]
  return None

##1,2,3,4
L = [[200, 100, 155], [0, 254, 255]]

print(L[1],L[1][1],len(L),len(L[1]))
##5
def mz(n,m):
  return [m * [0] for k in range (n)]

print(mz(2,3))

##6

def taille(L):
  return len(L)*len(L[1])

##7

def negatif(L):
  N = mz(len(L),len(L[0]))
  n = len(L)
  m = len(L[0])
  for i in range(n):
      for j in range(m):
          N[i][j] = 255 - L[i][j]
  return N

##8

def monochrome(L,s):
  M=mz(len(L),len(L[0]))
  n = len(L)
  m = len(L[0])
  for i in range(n):
      for j in range(m):
          if L[i][j]  >= s:
              M[i][j] = 255
  return M

##9

def reflexion(L):
  R = mz(len(L),len(L[0]))
  n = len(L)
  m = len(L[0])
  for i in range(n):
      for j in range(m):
          R[i][j] = L[i][m - j-1]
  return R

##10

def transpose(L):
  T=mz(len(L[0]),len(L))
  R = mz(len(L),len(L[0]))
  n = len(L)
  m = len(L[0])
  for i in range(n):
      for j in range(m):
          T[i][j] = L[j][i]
  return T

##11
def indmin(L):
  k = 0
  n=len(L)
  for i in range(n):
      if L[i]<L[k]:
          k = i
  return k

def selection(L):
  n= len(L)
  for i in range(n):
      k = i+indmin(L[i:])
      L[i],L[k] = L[k],L[i]
  return L

def selection_rec(L):
  n = len(L)
  if n==0 or n==1:
      return L
  else:
      k = indmin(L)
      L[0],L[k] = L[k],L[0]
      return [L[0]]+selection_rec(L[1:])

##12

def indminPhoto(L):
  k = 0
  n=len(L)
  for i in range(n):
      if L[i][1]<L[k][1]:
          k = i
  return k

def selectionPhoto(L):
  n= len(L)
  for i in range(n):
      k = i+indminPhoto(L[i:])
      L[i],L[k] = L[k],L[i]
  return L

##13
def dicho(x,T):
  a=0
  b=len(T)-1
  while a < b:
      m=(a+b)//2
      if x==T[m]:
          return True
      elif x<T[m]:
          b=m
      else:
          a=m
  return False

##14
def dichoPhoto(d,photos):
  a=0
  b=len(T)-1
  while a < b:
      m=(a+b)//2
      if x==T[m][1]:
          return True
      elif x<T[m][1]:
          b=m
      else:
          a=m
  return False

##15
def nomPatients(images):
  noms=[]
  for key in images:
      n = images[key][2]
      if n not in noms:
          noms.append(n)
  return noms

##16
def nombreDate(images,date):
  i = 0
  for key in images:
      if images[key][1]==date:
          i = i+1
  return i

##17
def fracture(images):
  lab = []
  for key in images:
      l = images[key][3]
      f = (images[key][4]=='FRACTURE')
      if f and l not in lab:
          lab.append(l)
  return lab

images ={
109:[2.9 ,20221223 , "DUKIC","OCEANA","",""],
203:[1.2 ,20221005 ,"MOING","RADIO1","FRACTURE", "TROUSSEAU"],
405:[6.9 ,20230178 ,"KARL","RADIO2","ARTHROSE", "JENNER"],
108:[4.1 ,20230206 ,"DUKIC","OCEANA","FRACTURE","PARE"],
406:[2.0 ,20230612 ,"KARL", "RADIO2", "TENDINITE", "JENNER"]}

(Sujet)

## Tri par Insertion

def triInsertion(l):
    ll = l[:]
    n = len(ll)
    for i in range(n):
        element = ll[i]
        j = i
        while (j>0 and ll[j-1] > element):
            ll[j] = ll[j-1]
            j = j-1
        ll[j] = element
    return ll

def triInsertionMieux(l):
    ll = l[:]
    n = len(ll)
    for i in range(n):
        element = ll[i]
        j = i
        while (j>0 and ll[j-1] > element):
            j = j-1
        ll.insert(j,element)
        del(ll[i+1])
    return ll

## Tri fusion

def divise(l):
    n=len(l)
    return l[:n//2],l[n//2:]

def fusion(l1,l2):
    if l1 == []: return l2
    if l2 == []: return l1
    if l1[0] <= l2[0]:
        return [l1[0]] + fusion(l1[1:],l2)
    else:
        return [l2[0]] + fusion(l1,l2[1:])

def fusion(l1,l2):
    l = []
    while (l1!=[] and l2!=[]):
        if l1[0] > l2[0]:
            l.append(l2[0])
            del(l2[0])
        else:
            l.append(l1[0])
            del(l1[0])
    if l1==[]:
        return l + l2
    else:
        return l+l1

def triFusion(l):
    n = len(l)
    if n<=1:
        return l
    else:
        lg,ld = divise(l)
        lg,ld = triFusion(lg),triFusion(ld)
        return fusion(lg,ld)

## Quicksort

def partition(l):
    lg = []
    ld = []
    pivot = l[0]
    for elem in l[1:]:
        if elem < pivot:
            lg.append(elem)
        else:
            ld.append(elem)
    return lg,ld,pivot

def quicksort(l):
    n = len(l)
    if n <= 1:
        return l
    else:
        lg,ld,pivot = partition(l)
        lg = quicksort(lg)
        ld = quicksort(ld)
        return lg+[pivot]+ld

## Quicksort + insertion

def sedgesort(l):
    n = len(l)
    if n<=15:
        return triInsertionMieux(l)
    else:
        lg,ld,pivot = partition(l)
        lg = sedgesort(lg)
        ld = sedgesort(ld)
        return(lg+[pivot]+ld)

## Mediane

def nth_least(l,n):
    lg,ld,pivot = partition(l)
    kg = len(lg)
    if n==kg:
        return pivot
    elif n<kg:
        return nth_least(lg,n)
    else:
        return nth_least(ld,n-(kg+1))

def mediane(l):
    n = len(l)
    return nth_least(l,n//2)

## Test
import random as rd
import time
l = [rd.randint(-499,499) for _ in range(20000)]

t = time.time()
l_insert = triInsertion(l)
print("Tri par insertion :",time.time() - t)
t = time.time()
l_insertmieux = triInsertionMieux(l)
print("Tri par insertion mieux :",time.time() - t)
t = time.time()
l_fusion = triFusion(l)
print("Tri fusion :",time.time() - t)
t = time.time()
l_qs = quicksort(l)
print("Tri rapide :",time.time() - t)
t = time.time()
l_sedge = sedgesort(l)
print("Tri Sedge :",time.time() - t)
t = time.time()
l_sort = sorted(l)
print("Tri Python :",time.time() - t)
t = time.time()

Sujet

import numpy as np
import matplotlib.pyplot as plt

## Euler

def Euler(F,t0,tf,y0,n):
    t=t0
    y=y0
    h=(tf-t0)/n
    abcisses=[t0]
    ordonnees=[y0]
    for i in range(n):
        y += h*F(t,y)
        t += h
        abcisses.append(t)
        ordonnees.append(y)
    return abcisses,ordonnees

a,o = Euler(lambda t,y: y,0,10,1,1000)
o2 = np.exp(a)
plt.plot(a,o)
plt.plot(a,o2)
plt.legend(["Euler","Exacte"])
plt.show()

## Euler systeme

def Euler_systeme(F,G,t0,tf,x0,y0,n):
    t=t0
    x=x0
    y=y0
    h=(tf-t0)/n
    temps=[t0]
    Lx=[x0]
    Ly=[y0]
    for i in range(n):
        x,y = x+h*F(t,x,y), y + h*G(t,x,y)
        t += h
        temps.append(t)
        Lx.append(x)
        Ly.append(y)
    return temps, Lx, Ly

# x et y en fonction du temps
t,x,y = Euler_systeme(lambda t,x,y:x*(3-2*y),lambda t,x,y: y*(-4+x),0,10,10,1,500000)
plt.plot(t,x); plt.plot(t,y)
plt.show()

## Euler EDO2

def Euler2(F,t0,tf,y0,dy0,n):
    f = lambda t,x,y: F(t,y,x)
    g = lambda t,x,y: x
    t,x,y = Euler_systeme(f,g,t0,tf,dy0,y0,n)
    return [t,y]

t,y = Euler2(lambda t,y,dy: -y,0,50,1,0,1000)
_,y2 = Euler2(lambda t,y,dy: -np.sin(y),0,50,1,0,1000)
plt.plot(t,y)
plt.plot(t,y2)
plt.show()

## RK4

def RK4(F,t0,tf,y0,n):
    t=t0
    y=y0
    h=(tf-t0)/n
    abcisses=[t0]
    ordonnees=[y0]
    for i in range(n):
        K1 = h*F(t,y)
        K2 = h * F(t+h/2,K1/2+y)
        K3 = h * F(t+h/2,K2/2+y)
        K4 = h * F(t+h,K3+y)
        y += (1/6)*(K1+2*K2+2*K3+K4)
        t += h
        abcisses.append(t)
        ordonnees.append(y)
    return abcisses,ordonnees

a,o = RK4(lambda t,y: np.cos(t)-y,0,100,1,1000)
plt.plot(a,o)
plt.show()

## odeint

from scipy.integrate import odeint

t = np.linspace(0,10,1000)
plt.plot(t,odeint(lambda y,t: np.cos(t)-y,1,t)); plt.show()
l = odeint(lambda y,t: np.array([y[0]*(3-2*y[1]), y[1]*(-4+y[0])]),np.array([10,1]),t)
plt.plot(l[:,0],l[:,1]); plt.show()
plt.plot(t,odeint(lambda y,t: np.array([-np.sin(y[1]),y[0]]),np.array([1,0]),t)[:,1]); 
plt.show()

## Lorenz
from mpl_toolkits.mplot3d import Axes3D
fig = plt.figure()
ax = fig.add_subplot(projection='3d')

def FLorenz(v,t,sigma=10,beta=2.66,rho=30):
    xp = sigma*(v[1]-v[0])
    yp = rho*v[0] - v[1] - v[0]*v[2]
    zp = v[0]*v[1] - beta*v[2]
    return [xp,yp,zp]

t = np.linspace(0,50,10000)
v = odeint(FLorenz, [20,0,0],t)
ax.plot(v[:,0],v[:,1],v[:,2],linewidth=.9)
v = odeint(FLorenz, [10,0,0],t)
ax.plot(v[:,0],v[:,1],v[:,2],linewidth=.9)
v = odeint(FLorenz, [0.1,0,0],t)
ax.plot(v[:,0],v[:,1],v[:,2],linewidth=.9)
plt.show()