.
Contact :
Cours :
Pour s'entraîner aux questions de cours : Générateur de questions
Devoirs :
Cliquer sur le + pour afficher les fichiers et corrigés
## 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
## 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]
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()
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]
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()
Ces documents ne concernent pas mes étudiants actuels, mais peuvent continuer d'intéresser certaines personnes.