.
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 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 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(2000)]
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()
import random as rd
import matplotlib.pyplot as plt
import math
ville1 = (3.002556, 45.846117)
ville2 = (-0.644905, 44.896839)
ville3 = (-1.380989, 43.470961)
ville4 = (1.376579, 43.662010)
ville5 = (5.337151, 43.327276)
ville6 = (7.265252, 43.745404)
ville7 = (-1.650154, 47.385427)
ville8 = (-1.430427, 48.197310)
ville9 = (2.414787, 48.953260)
ville10 = (3.090447, 50.612962)
ville11 = (5.013054, 47.370547)
ville12 = (4.793327, 44.990153)
ville13 = (2.447746, 44.966838)
ville14 = (1.750115, 47.980822)
ville15 = (4.134148, 49.323421)
ville16 = (7.506950, 48.580332)
ville17 = (1.233757, 45.865246)
ville18 = (4.047255,48.370925)
ville19 = (0.103163,49.532415)
ville20 = (-1.495348, 49.667704)
ville21 = (-4.494615, 48.447500)
ville22 =(-0.457140, 46.373545)
france = [ville1,ville2,ville3,ville4,ville5,ville6,ville7,ville8,ville9,ville10,ville11,ville12,ville13,ville14,ville15,ville16,ville17,ville18,ville19,ville20,ville21,ville22]
def dist(lon1,lat1,lon2,lat2):
radius = 6371 # km
dlat = math.radians(lat2 - lat1)
dlon = math.radians(lon2 - lon1)
a = (math.sin(dlat / 2) * math.sin(dlat / 2) +
math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) *
math.sin(dlon / 2) * math.sin(dlon / 2))
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
d = radius * c
return d
## Préliminaires
def cycleAlea(villes):
"""
Renvoie un parcours aléatoires des éléments de la liste villes
"""
v = villes[:]
cycle = []
while v != []:
i = rd.randint(0,len(v)-1)
ville = v.pop(i)
cycle.append(ville)
return cycle
def longueurCycle(c):
"""
Calcule la longueur du cycle hamiltonien cycle
"""
d = 0
for i in range(len(c)-1):
x,y = c[i]
z,t = c[i+1]
d = d + dist(x,y,z,t)
x,y = c[0]
z,t = c[-1]
d = d + dist(x,y,z,t)
return d
def dessineCycle(c):
"""
Affiche le cycle hamiltonien cycle sur un graphique
"""
n=len(c)
X = [c[i][0] for i in range(n)]
X.append(c[0][0])
Y = [c[i][1] for i in range(n)]
Y.append(c[0][1])
plt.plot(X,Y,marker='o',linestyle='-')
plt.show()
## Algorithme 2-opt
def renversement(c,i,j):
"""
Calcule le renversement du cycle c entre i et j.
Si c = [v0,v1,...,vn], alors renversement(c,i,j) = [v0,v1,..,v(i-1),vj,v(j-1),...,vi,v(j+1),...,vn]
"""
r = []
for k in range(i):
r.append(c[k])
for k in range(j,i-1,-1):
r.append(c[k])
for k in range(j+1,len(c)):
r.append(c[k])
return r
def DeuxOpt(c):
"""
Applique l'algorithme 2-opt a la liste de villes c
"""
cycle = cycleAlea(c)
# dessineCycle(cycle)
n = len(cycle)
echange = True
while echange:
echange = False
for j in range(n):
for i in range(j):
nouveau = renversement(cycle,i,j)
if longueurCycle(nouveau) < longueurCycle(cycle):
cycle = nouveau[:]
echange = True
# plt.clf()
# dessineCycle(cycle)
# plt.pause(.1)
return cycle,longueurCycle(cycle)
## Recuit simulé
def recuit(c,T0=10,Tmin=0.05,alpha=0.95,N=100):
cycle = cycleAlea(c)
T = T0
n = len(c)
while T>Tmin:
for _ in range(N):
i = rd.randint(0,n-2)
j = rd.randint(i+1,n-1)
nouveau = renversement(cycle,i,j)
if longueurCycle(nouveau) < longueurCycle(cycle):
cycle = nouveau[:]
else:
delta = longueurCycle(nouveau) - longueurCycle(cycle)
if rd.random() < math.exp(-delta/T):
cycle = nouveau[:]
T = alpha*T
return DeuxOpt(cycle)
## Algorithme génétique
def popInit(c,N):
"""
Crée une population de N cycles aléatoires
"""
pop = []
for _ in range(N):
pop.append(cycleAlea(c))
return pop
def bestFit(pop):
"""
Renvoie l'individu de pop avec la meilleure fitness
"""
min = longueurCycle(pop[0])
imin = 0
for i in range(1,len(pop)):
l = longueurCycle(pop[i])
if l < min:
min = l
imin = i
return pop[imin]
def tournoi(pop,K=5):
"""
Organise un tournoi de K personnes dans pop et renvoie le meilleur
"""
pool = [pop[rd.randint(0,len(pop)-1)] for _ in range(K)]
return bestFit(pool)
def selection(pop,K=5):
N = len(pop)
newpop = []
for _ in range(N):
sel = tournoi(pop,K)
newpop.append(sel)
return newpop
def disjointes(l1,l2):
"""
Teste si les listes l1 et l2 sont disjointes
"""
for elem in l1:
if elem in l2:
return False
return True
def repare(l,u,v):
"""
Renvoie une liste l modifiée pour que l et u soient disjoints
en remplaçant les doublons u[k] par v[k]
"""
k = len(l)
while not disjointes(l,u):
for i in range(k):
if l[i] in u:
l[i] = v[u.index(l[i])]
return l
def mate(p1,p2):
n = len(p1)
i = rd.randint(0,n-2)
j = rd.randint(i+1,n-1)
offspring1 = p2[:i+1]
offspring2 = p1[i+1:j]
offspring3 = p2[j:]
offspring1 = repare(offspring1,p1[i+1:j],p2[i+1:j])
offspring3 = repare(offspring3,p1[i+1:j],p2[i+1:j])
return offspring1+offspring2+offspring3
def reproduction(popu):
newpop = []
N = len(popu)
for _ in range(N//2):
i = rd.randint(0,len(popu)-1)
p1 = popu.pop(i)
j = rd.randint(0,len(popu)-1)
p2 = popu.pop(j)
newpop.append(mate(p1,p2))
newpop.append(mate(p2,p1))
return newpop
def mutation(ind,alpha=0.05):
n = len(ind)
if rd.random() < alpha:
i = rd.randint(0,n-2)
j = rd.randint(i,n-1)
ind[i],ind[j] = ind[j],ind[i]
return ind
def genetic(carte,N=100,alpha=.05,K=5,gen=100):
n = len(carte)
population = popInit(carte,N)
for k in range(gen):
population = selection(population,K)
population = reproduction(population)
population = [mutation(ind, alpha) for ind in population]
return bestFit(population), longueurCycle(bestFit(population))
Machine à inventer des mots Dictionnaire
import random as rd
## Mot complétement aléatoire
def motAlea():
s = ""
lettre = ""
while True:
lettre = rd.choice(alphabet)
if lettre == '>':
return s
if lettre != '<':
s = s+lettre
## Traitement dico
dico = [line.rstrip("\n") for line in open("dico.txt")]
alphabet = ['<','>']
for mot in dico:
for lettre in mot:
if lettre not in alphabet:
alphabet.append(lettre)
## Statistiques
def initProbaLettre1():
d = {}
for lettre1 in alphabet:
d[lettre1] = 0
return d
def initProba1():
"""
Cree un dictionnaire dont les clefs sont les lettres de l'alphabet
"""
d = {}
for lettre in alphabet:
d[lettre] = initProbaLettre1()
return d
def proba1():
"""
Met à jour le dictionnaire des probas de suites de 2 lettres suite à la lecture du mot, N étant le nombre de suites de deux lettres dans le dictionnaire
"""
d = initProba1()
N = 0
for mot in dico:
n = len(mot)
d['<'][mot[0]] += 1
N+=1
for i in range(n-1):
d[mot[i]][mot[i+1]] += 1
N+=1
d[mot[-1]]['>'] += 1
N+=1
for lettre1 in alphabet:
for lettre2 in alphabet:
d[lettre1][lettre2] /= N
return d
## Générateur de mots
def genMot1(d):
"""
Genere un mot en utilisant le dictionnaire de probabilites d
"""
s = ""
lettre = '<'
lettre = rd.choices(list(d[lettre].keys()), weights = d[lettre].values())[0]
# print(lettre)
s += lettre
while lettre != '>':
lettre = rd.choices(list(d[lettre].keys()), weights = d[lettre].values())[0]
s+= lettre
if len(s) > 15:
return genMot1(d)
return s[:-1]
## Test
d1=proba1()
#
for _ in range(10):
print(genMot1(d1))
#
## Mot le plus probable
d1=proba1()
def max_proba(d):
m = 0
l = ''
for k in d:
if d[k] > m:
m = d[k]
l = k
return l
mot = ""
lettre = '<'
while lettre != '>':
lettre = max_proba(d1[lettre])
mot = mot + lettre
if len(mot) > 20:
break
print(mot[:-1])
## En comptant les suites de 3 lettres
def initProbaLettre2():
print('foo')
d = {}
for lettre1 in alphabet:
d[lettre1] = 0
return d
def initProba2():
d = {}
for lettre1 in alphabet:
d[lettre1] = {}
for lettre2 in alphabet:
d[lettre1][lettre2] = {}
for lettre3 in alphabet:
d[lettre1][lettre2][lettre3] = 0
return d
def proba2():
d = initProba2()
N = 0
for mot in dico:
if len(mot)>1:
n = len(mot)
d['<'][mot[0]][mot[1]] += 1
N+=1
for i in range(n-2):
d[mot[i]][mot[i+1]][mot[i+2]] += 1
N+=1
d[mot[-2]][mot[-1]]['>'] += 1
N+=1
for lettre1 in alphabet:
for lettre2 in alphabet:
for lettre3 in alphabet:
d[lettre1][lettre2][lettre3] /= N
return d
def genMot2(d,lmax=15):
s = ""
lettre1 = '<'
lettre2 = rd.choice(alphabet)
while lettre2 == '<' or lettre2=='>' or lettre2=='-':
lettre2 = rd.choice(alphabet)
s=s+lettre1+lettre2
lettre = rd.choices(list(d[lettre1][lettre2].keys()), weights = d[lettre1][lettre2].values())[0]
lettre1,lettre2 = lettre2,lettre
s += lettre2
while lettre2 != '>':
if len(s)>lmax:
return genMot2(d)
lettre = rd.choices(list(d[lettre1][lettre2].keys()), weights = d[lettre1][lettre2].values())[0]
lettre1,lettre2 = lettre2,lettre
s+= lettre
return s[1:-1]
## Test2
d2 = proba2()
print()
for _ in range(10):
print(genMot2(d2))
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()
SELECT * FROM country
SELECT name, code FROM country
SELECT name FROM country
WHERE population < 1000
SELECT name FROM country
ORDER BY area DESC
SELECT * FROM
city JOIN country ON city.country = country.code
SELECT * FROM
country c JOIN spoken s ON c.code=s.country
WHERE c.code='F'
SELECT c.name FROM
encompasses e JOIN country c ON e.country=c.code
WHERE e.continent='Africa'
ORDER BY c.population
SELECT c.name FROM
encompasses e JOIN country c ON e.country=c.code
WHERE e.percentage < 100
SELECT language FROM spoken
GROUP BY language
HAVING COUNT(country)=1
SELECT s.language
FROM spoken s JOIN country c ON s.country = c.code
GROUP BY s.language
HAVING SUM ( c.population*s.percentage*0.01) < 5000
SELECT s.language, SUM(c.population*s.percentage*0.01) Nb FROM
spoken s
JOIN country c ON s.country=c.code
JOIN encompasses e ON e.country = c.code
WHERE e.continent='South America'
GROUP BY s.language
ORDER BY Nb DESC
Ces documents ne concernent pas mes étudiants actuels, mais peuvent continuer d'intéresser certaines personnes.