.
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]
Ces documents ne concernent pas mes étudiants actuels, mais peuvent continuer d'intéresser certaines personnes.