---
# System prepended metadata

title: Theorie des graphs 5
tags: [' ING1', theorie des graphs, ' S6']

---

---
lang: fr
tags: theorie des graphs, S6, ING1
title: Theorie des graphs 5
date: 22/03/2019
---

# Theorie des graphs 5


Pour faire $x^{13}$ on peut fire $x * x * x ... x$ $\rightarrow$ 12 multiplication

Ou alors on peut faire:

$x^{13} = x * x^{12}$
$x^{12} = x^{6} * x^{6}$
$x^{6} = x^{3} * x^{3}$
$x^{3} = x * x^{2}$

$\rightarrow$ 5 multiplications

```python
Fastpow(x,n):
    if n = 0
        return 1
    if n is odd
        y <- Fastpow(x, (n-1)/2)
        return x*y*y
    y<- FastPow(x, n/2)
    return y*y
```

Ici on est en $\theta(log(n))$

:::info
Le truc cool, c'est que cela a n'importe (E, x, 1) (monoïde, cf. logique du 1er ordre).
Par exemple les matrices, les entiers, les réels etc.
:::


> Pourquoi tout ce blabla ? Car aujourd'hui on va voir 3 algos de > plus cours chemins avec n sources et nn destinations 
> (entrée: matrice d'adj pondérée, sortie; matrice des distances)


1. $\theta(|V|^4)$
2. $\theta(|V|^3log(|V|))$ On passe à cette complexité ave fastpow
3. $\theta(|V|^3)$

Ces 3 algos peuvent être résolu à l'aide de la programmation dynamique.

```python=
algonaze(Mg, n)
D <- Mg                        #Teta(n²)
for k <- 2 to n-1                # teta(n)
    for X<- 2 to n-1            #teta(n²)
        for Y <- 1 to n            # teta(n^3)
            D[x,y] <- min(D[X,Z] + Mg[Z,Y])     #teta(n^4)
    D <- D'                    #teta(n^4)
return 1                    #teta(n^4)
```

