import pylab as pl
import time
def RPN(l):
pile=[]
for el in l:
if el not in ('x','+'):
pile.append(el)
elif el=='+':
pile.append(pile.pop()+pile.pop())
else:
pile.append(pile.pop()*pile.pop())
print(pile)
RPN([2,3,4,'x','+'])
[2] [2, 3] [2, 3, 4] [2, 12] [14]
hash(12345), hash("12345"), hash((1,2,3,4,5))
(12345, 1533824495253068585, -5659871693760987716)
Mais pas les listes
hash([1,2,3,4,5])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
Cell In[13], line 2 Traceback (most recent call last): ^ SyntaxError: invalid syntax. Perhaps you forgot a comma?
La fonction de hachage est localement injective, c'est-à-dire qu'elle est très sensible aux petites variations des clefs.
hash("Dupont"),hash("Dupond"),hash("Dupont")-hash("Dupond")
(-546747165689147820, -5722525303616470491, 5175778137927322671)
def mesure_duree(f,arg):
"""
retourne le résultat d'exécution de la fonction f avec arg passé en argument
"""
t1=time.perf_counter()
res=f(*arg)
t2=time.perf_counter()
print("C{}={} effectué en {:.1e}s".format(arg,res,t2-t1))
def binom(n, p):
if p == 0 or n == p:
return 1
return binom(n-1, p-1) + binom(n-1, p)
mesure_duree(binom,(8,2))
C(8, 2)=28 effectué en 1.9e-05s
mesure_duree(binom,(8,4))
C(8, 4)=70 effectué en 0.00s
mesure_duree(binom,(30,15))
C(30, 15)=155117520 effectué en 22.8s
Version itérative du calcul des coefficients binomiaux¶
def binom_it(n, p):
t = pl.zeros((n + 1, p + 1))
for i in range(0, n + 1):
t[i, 0] = 1
for i in range(1, p + 1):
t[i, i] = 1
for i in range(2, n + 1):
for j in range(1, min(p, i) + 1):
t[i, j] = t[i - 1, j - 1] + t[i - 1, j]
return t[n, p]
mesure_duree(binom_it,(30,15))
C(30, 15)=155117520.0 effectué en 8.2e-04s
Version récursive avec memoisation¶
binom_dict = {}
def binom_mem(n, p):
if (n, p) not in binom_dict:
if p == 0 or n == p:
binom_dict[(n, p)] = 1
else:
binom_dict[(n, p)] = binom_mem(n - 1, p - 1) + binom_mem(n - 1, p)
return binom_dict[(n, p)]
mesure_duree(binom_mem,(30,15))
C(30, 15)=155117520 effectué en 3.9e-04s
Remarque culturelle¶
Le code suivant permet d'associer automatiquement un dictionnaire à la fonction récursive utilisée.
from functools import lru_cache
@lru_cache
def binom(n, p):
if p == 0 or n == p:
return 1
return binom(n-1, p-1) + binom(n-1, p)
mesure_duree(binom,(30,15))
C(30, 15)=155117520 effectué en 1.7e-04s
4.2. Algorithme de Floyd-Warshall¶
def floydwarshall(M):
n = M.shape[0]
N = M.copy()
for k in range(n):
for i in range(n):
for j in range(n):
N[i, j] = min(N[i, j], N[i, k] + N[k, j])
return N
M=pl.array([
[0,float('inf') , float('inf') , float('inf') , -1 , float('inf')],
[1,0,float('inf'),2,float('inf'),float('inf')],
[float('inf'),2,0,float('inf'),float('inf'),6],
[-3,float('inf'),float('inf'),0,float('inf'),float('inf')],
[float('inf'),7,float('inf'),4,0,float('inf')],
[float('inf'),5,-4,float('inf'),float('inf'),0]
])
M
array([[ 0., inf, inf, inf, -1., inf], [ 1., 0., inf, 2., inf, inf], [inf, 2., 0., inf, inf, 6.], [-3., inf, inf, 0., inf, inf], [inf, 7., inf, 4., 0., inf], [inf, 5., -4., inf, inf, 0.]])
floydwarshall(M)
array([[ 0., 6., inf, 3., -1., inf], [-1., 0., inf, 2., -2., inf], [ 1., 2., 0., 4., 0., 6.], [-3., 3., inf, 0., -4., inf], [ 1., 7., inf, 4., 0., inf], [-3., -2., -4., 0., -4., 0.]])
Complément : fermeture transitive d'un graphe¶
Considérons de nouveau un graphe non pondéré, orienté ou non. Le problème de la fermeture transitive consiste à déterminer si deux sommets $a$ et $b$ peuvent être reliés par un chemin allant de $a$ à $b$. Pour le résoudre, nous allons utiliser la matrice d'adjacence associée à ce graphe, mais cette fois en utilisant les valeurs booléennes True
pour dénoter l'existence d'une arête et False
pour en marquer l'absence. Remplaçons maintenant dans l'algorithme de Floyd-Warshall la relation de récurrence sur les coefficients des matrices $M^{(k)} \mathrm{par}^{\text {: }}$
$$
m_{i j}^{(k+1)}=m_{i j}^{(k)} \text { ou }\left(m_{i, k+1}^{(k)} \text { et } m_{k+1, j}^{(k)}\right)
$$
On peut prouver de façon similaire à ce que nous avons fait que le booléen $m_{i j}^{(k)}$ dénote l'existence d'un chemin reliant les sommets $v_{i}$ et $v_{j}$ en ne passant que par les sommets $v_{1}, v_{2}, \ldots, v_{k}$. a matrice $M^{(n)}$ résout le problème de la fermeture transitive.
L'algorithme ainsi modifié est connu sous le nom d'algorithme de Warshall :
def warshall(M):
n = M.shape[0]
N = M.copy()
for k in range(n):
for i in range(n):
for j in range(n):
N[i, j] = N[i, j] or N[i, k] and N[k, j]
return N
N=M.copy()
n = M.shape[0]
for i in range(n):
for j in range(n):
if N[i,j]==float('inf'):
N[i,j]=False
else:
N[i,j]=True
warshall(N)
array([[1., 1., 0., 1., 1., 0.], [1., 1., 0., 1., 1., 0.], [1., 1., 1., 1., 1., 1.], [1., 1., 0., 1., 1., 0.], [1., 1., 0., 1., 1., 0.], [1., 1., 1., 1., 1., 1.]])