# 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