1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
# Fast Power (Exponentiation rapide)
$a^n = a \times a \times a \times \dots \times a$
$a^9 = a \times a^8 = a \times (a^4 \times a^4)$
$\mathcal{O}(n) \rightarrow \mathcal{O}(\log n) \checkmark$
Généralisable sur des monoïdes
---
# Distances n sommets, n designations
## Notation
On note $D_{k}[X,Y]$ la distance minimale entre X et Y passant par au plus $k$ arcs
$$
D_{k}[X,Y] = \begin{cases}
M[X,Y] \; si \; k = 1 \\
min_{Z\in V}(D_{k-1}[X,Z] + M[Z,Y]) \; si \; k > 1
\end{cases}
$$
Avec $M$ la matrice pondérée, et en cherchant $2 \leq k \leq |V| - 1$
![[{337A76B1-DC9F-4A71-A261-156A3B3ABF66}.png]]
$\longrightarrow \mathcal{O}(|V|^4)$
# Semi-anneau
$(E,\oplus, \otimes, e,f)$ est un **semi-anneau** si :
1. $(E,\oplus,e)$ est un **monoïde commutatif**
2. $(E,\otimes,f)$ est un **monoïde**
3. $\otimes$ est **distributif** par rapport à $\oplus$
4. $e$ est **absorbant** pour $\otimes$ ($\forall x \in E, x \otimes e = e \otimes x = e$)
Si $(E,\oplus,\otimes,e,f)$ est un **semi-anneau** alors la structure $(\mathcal{M}_{n}(E),\boxplus,\boxtimes, \mathcal{O},\mathcal{I})$ où $\mathcal{I}$, $\mathcal{O}$, $S = A \boxplus B$, $P = A \boxtimes B$ sont définis par :
$$
\begin{align}
&\mathcal{I}_{i,j} = \begin{cases}
f \quad si \; i = j \\
e \quad sinon
\end{cases} \\
&\mathcal{O}_{i,j} = e \\
&S_{i,j} = A_{i,j} \oplus B_{i,j} \\
&P_{i,j} = A_{i,j} \otimes B_{i,j}
\end{align}
$$
est aussi un **semi-anneau**.
$\rightarrow$ Permet de réduire `SlowShortestPath` à $\mathcal{O}(|V|^3 \log |V|)$
## Exemples
$(\mathbb{R}, +, \times$
# Floyd Warshall
![[{2093C32E-4155-4837-8A07-EDB06608F3D6}.png]]
```
FloydWarshall(M)
n <- size(M)
D <- M
for X <- 1 to n
for Y <- 1 to n
P[X,Y] <- X
for K <- 1 to n
for X <- 1 to n
for Y <- 1 to n
if D[X,K] + D[K,Y] < D[X,Y]
D'[X,Y] <- D[X,K] + D[K,Y]
P[X,Y] <- P[K,Y]
else
D'[X,Y] <- D[X,Y]
D <- D'
return D,P
```
# Autres application
## THL
$\longrightarrow$ Automates
|
