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 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()

Graphes et algorithme de Dijkstra

Voyageur de commerce

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

Équations différentielles

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

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