init: initial commit

1 files changed, 76 insertions, 0 deletions

diff --git a/THEG/PCC & Floyd Warshall.md b/THEG/PCC & Floyd Warshall.md
new file mode 100755
index 0000000..c04561c
--- /dev/null
+++ b/THEG/PCC & Floyd Warshall.md
@@ -0,0 +1,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
\ No newline at end of file