Mathématiques en BCPST2

.

Python en BCPST2

Cliquer sur le + pour afficher les fichiers et corrigés

Tris de listes

Tris de listes

## 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 fusionRec(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 True:
        if l1 == []: return l+l2
        if l2 == []: return l+l1
        if l1[0] < l2[0]:
            l.append(l1[0])
            l1.pop(0)
        else:
            l.append(l2[0])
            l2.pop(0)
    return l

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()
Graphes et algorithme de Dijkstra

Graphes et algorithme de Dijkstra

## Exercice 1
import numpy as np

Exm1 = {
    0:[],
    1:[(2,0),(4,1),(5,3)],
    2:[(0,6),(1,2)],
    3:[],
    4:[(2,1)],
    5:[(3,2)]
    }

mat = np.array([[-1., -1., -1., -1., -1., -1.],
       [-1., -1.,  0., -1.,  1.,  3.],
       [ 6.,  2., -1., -1., -1., -1.],
       [-1., -1., -1., -1., -1., -1.],
       [-1., -1.,  1., -1., -1., -1.],
       [-1., -1., -1.,  2., -1., -1.]])

## Exercice 2

import numpy as np

def matriceVersListe(mat):
    n,_ = mat.shape
    d = dict()
    for i in range(n):
        l = []
        for j in range(n):
            if mat[i,j] != -1:
                l.append((j,mat[i,j]))
        d[i] = l
    return d

def listeVersMatrice(d):
    n = len(d)
    mat = -1*np.ones([n,n])
    for s in d:
        for (v,p) in d[s]:
            mat[s,v] = p
    return mat

## Exercice 3

def voisins(d,s):
    voisins = []
    for v,p in d[s]:
        voisins.append(v)
    return voisins

## Exercice 4

def cheminValide(d,chemin):
    n = len(chemin)
    for i in range(n-1):
        if chemin[i+1] not in voisins(d,chemin[i]):
            return False
    return True

## Exercice 5

def parcoursLargeur(d,s):
    visite = []
    file = [s]
    while file != []:
        print(file)
        sommet = file.pop(0)
        visite.append(sommet)
        for v in voisins(d,sommet):
            if v not in file and v not in visite:
                file.append(v)
    return visite

def parcoursProfondeur(d,s):
    visite = []
    file = [s]
    while file != []:
        print(file)
        sommet = file.pop()
        visite.append(sommet)
        for v in voisins(d,sommet):
            if v not in file and v not in visite:
                file.append(v)
    return visite

## Exercice 7

Exm = {
    0:[(1,7),(2,1)],
    1:[(3,4),(5,1)],
    2:[(1,5),(4,2),(5,7)],
    3:[],
    4:[(1,2),(3,5)],
    5:[(4,3)]
    }

def index_min_non_visite(l,v):
    """
    Donne l'index de l'element min dans une liste
    """
    k = -1
    min = float('inf')
    for i in range(len(l)):
        if l[i] < min and i not in v:
            k = i
            min = l[i]
    return k

def poids_arete(graphe,i,j):
    for elem in graphe[i]:
        if elem[0] == j:
            return elem[1]

def voisins(graphe,i):
    l = []
    for elem in graphe[i]:
        l.append(elem[0])
    return l

def Dijkstra_distances(graphe,sommet):
    sommets = list(range(len(graphe)))
    distances = [float('inf') for elem in graphe]
    distances[sommet] = 0
    for s,p in graphe[sommet]:
        distances[s] = p
    visites = [sommet]
    while len(sommets) > len(visites):
        k = index_min_non_visite(distances,visites)
        visites.append(k)
        for s in voisins(graphe,k):
            if s not in visites:
                if distances[s] > distances[k] + poids_arete(graphe,k,s):
                    distances[s] = distances[k] + poids_arete(graphe,k,s)
    return distances

## Exercice 9

def Dijkstra(graphe,sommet):
    sommets = list(range(len(graphe)))
    distances = [float('inf') for elem in graphe]
    origine = [None for elem in graphe]
    distances[sommet] = 0
    for s,p in graphe[sommet]:
        distances[s] = p
        origine[s] = sommet
    visites = [sommet]
    while len(sommets) > len(visites):
        print(distances)
        k = index_min_non_visite(distances,visites)
        visites.append(k)
        for s in voisins(graphe,k):
            if s not in visites:
                if distances[s] > distances[k] + poids_arete(graphe,k,s):
                    distances[s] = distances[k] + poids_arete(graphe,k,s)
                    origine[s] = k
    return distances,origine

## Exercice 10

def distance(graphe,i,j):
    tabDistances, tabOrigine = Dijkstra(graphe,i)
    k = j
    l = []
    while k!= i:
        l = [k] + l
        k = tabOrigine[k]
    l = [i] + l
    return l,tabDistances[j]
Méthode d'Euler

Méthode d'Euler

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: np.cos(t)-y,0,100,1,1000)
plt.plot(a,o)
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,y0,dy0,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,100,1000)
plt.plot(t,odeint(lambda y,t: np.cos(t)-y,1,t)); 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.gca(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()
Bases de données relationnelles
Machine à inventer des mots

Machine à inventer des mots

Dictionnaire

dico = [line.rstrip("\n") for line in open("dico.txt")]

alph = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','<','>']

## Analyse Fréquentielle

def ligne_dico():
    d = {}
    for l in alph:
        d[l] = 0
    return d

def matriceProba():
    d = {}
    for l in alph:
        d[l] = ligne_dico()
    return d

def probas():
    d = matriceProba()
    for mot in dico:
        d['<'][mot[0]] += 1
        n = len(mot)
        for i in range(n-1):
            d[mot[i]][mot[i+1]] += 1
        d[mot[n-1]]['>'] += 1
    for k in d:
        N = sum(d[k].values())
        for l in d[k]:
            if N != 0:
                d[k][l] /= N
    return d

## Creation de mots

import random as rd

# rd.choices(['A','B','C'], weights=[.1,.1,.1])[0]

def genMot(p):
    """
    p est le resultat de la fonction probas
    """
    s = ""
    l = rd.choices(alph,weights=p['<'].values())[0]
    s = s+l
    while l != '>':
        l = rd.choices(alph,weights=p[l].values())[0]
        s = s+l
    return s[:-1]

## Recommencons

def ligne_dico():
    d = {}
    for l in alph:
        d[l] = 0
    return d

def matriceProba_aux():
    d = {}
    for l in alph:
        d[l] = ligne_dico()
    return d

def matriceProba():
    d = {}
    for l in alph:
        d[l] = matriceProba_aux()
    return d

def probas():
    d = matriceProba()
    for mot in dico:
        n = len(mot)
        if n > 1:
            d['<'][mot[0]][mot[1]] += 1
            for i in range(n-2):
                d[mot[i]][mot[i+1]][mot[i+2]] += 1
            d[mot[n-2]][mot[n-1]]['>'] += 1
        else:
            d['<'][mot[0]]['>'] += 1
    for k1 in d:
        for k2 in d:
            N = sum(d[k1][k2].values())
            for l in d[k1][k2]:
                if N != 0:
                    d[k1][k2][l] /= N
    return d

def premiereLettre():
    d = ligne_dico()
    for mot in dico:
        d[mot[0]] += 1
    N = sum(d.values())
    for k in d:
        d[k] /= N
    return d

def genMot(p,p1):
    """
    p : probas (3d)
    p1 : probas de premiere lettre
    """
    s = ""
    l1 = '<'
    l2 = rd.choices(alph,weights=p1.values())[0]
    s += l2
    while l2 != '>':
        l1,l2 = l2, rd.choices(alph,weights=p[l1][l2].values())[0]
        s += l2
    return s[:-1]

## Mot le plus probable

def maxProba(d):
    lettre = 'a'
    p = 0
    for k in d:
        if d[k] > p:
            lettre = k
            p = d[k]
    return lettre

def motProbable(p,p1):
    s = ""
    l1 = '<'
    l2 = maxProba(p1)
    s += l2
    while l2 != '>':
        l1,l2 = l2, maxProba(p[l1][l2])
        s += l2
    return s[:-1]
Des probabilités

Probabilités

import random as rd

## Exercice 1

def uniformeD(a,b):
    """
    Renvoie un entier de [|a,b|] suivant la loi uniforme
    """
    return rd.randint(a,b)

def uniformeDListe(l):
    """
    Renvoie un élément aléatoirement choisi dans l
    """
    return rd.choice(l)

def bernoulli(p):
    if rd.random() < p:
        return 1
    else:
        return 0

def binomiale(n,p):
    b = 0
    for _ in range(n):
        b=b+bernoulli(p)
    return b

def geometrique(p):
    k = 0
    b = 0
    while b==0:
        k= k+1
        b = bernoulli(p)
    return k

## Exercice 2

import numpy as np

def factorial(k):
    if k==0: return 1
    else: return k*factorial(k-1)

def FPoisson(n,l):
    f = 0
    for k in range(n+1):
        f = f + np.exp(-l)*l**k/factorial(k)
    return f

def morue(l):
    u = rd.random()
    f = 0
    i = 0
    while u > f:
        i = i+1
        f = FPoisson(i,l)
    return i-1

def poisson(l):
    u = rd.random()
    i = 0
    L = np.exp(-l)
    S = 0
    while u > S:
        S = S+L
        i = i+1
        L = L*l/i
    return i-1

## Exercice 4
import matplotlib.pyplot as plt

def unif(a,b):
    u = rd.random()
    return (b-a)*u+a

def espUnif(a,b):
    e = 0
    for _ in range(10000):
        e = e + unif(a,b)/10000
    return e

def varUnif(a,b):
    m1 = 0
    m2 = 0
    for _ in range(10000):
        u = unif(a,b)
        m1 = m1 + u/10000
        m2 = m2 + u*u/10000
    return m2 - m1*m1

## Exercice 5
x = [unif(2,3) for _ in range(100000)]
y = [np.random.uniform(2,3) for _ in range(100000)]
plt.hist([x,y],density=True)
plt.show()

## Exercice 7

def expo(l):
    return (-1/l)*np.log(1-rd.random())

N = 100000
x = [expo(2) for _ in range(N)]
y = [np.random.exponential(1/2) for _ in range(N)]
plt.hist([x,y],density=True)
plt.show()

## Exercice 8

def N(n,l):
    b=0
    i=0
    while b==0:
        i=i+1
        b = rd.random() < l/n
    return i/n

def F(x,n,l):
    K=1000
    p = 0
    for _ in range(K):
        if N(n,l) <= x:
            p = p+1/K
    return p

abs = np.linspace(0,5,100)
ord = [F(x,10,2) for x in abs]

plt.plot(abs,ord)
plt.show()
Quelques sujets de TB

Archives

Ces documents ne concernent pas mes étudiants actuels, mais peuvent continuer d'intéresser certaines personnes.