Benjamin Monmege
Exemple de la factorielle: \[u_0 = 1 \qquad \text{ et }\qquad \forall n\geq 1 \quad u_n = n\times u_{n-1}\]
On définit \(u_n\) en fonction de \(u_{n-1}\)
def factorielle(n: int) -> int:
assert n >= 0
resultat = 1
for i in range(1, n+1):
resultat *= i
return resultatExemple de la factorielle: \[u_0 = 1 \qquad \text{ et }\qquad \forall n\geq 1 \quad u_n = n\times u_{n-1}\]
def factorielle(n: int) -> int:
assert n >= 0
if n == 0:
return 1
return n * factorielle(n - 1)
def multiply(x, y):
if x <= 0:
return 0
elif x % 2 == 0:
return multiply(x//2, y+y)
else:
return multiply(x//2, y+y) + y
>>> import sys
>>> sys.setrecursionlimit(100000)Résolution d’un problème en trois étapes :
e à celui x au milieu du tableau pour savoir s’il faut chercher à gauche ou à droitee=x, ou rechercher récursivement dans l’un des deux sous-tableaux
Si \(n\) est un paramètre de taille de l’entrée, la complexité d’un algorithme diviser pour régner est toujours de la forme
\[T(n) = \underbrace{T_d(n)}_{\text{division}} + \sum_{\text{sous-problèmes de taille } m<n} T(m) + \underbrace{T_c(n)}_{\text{combinaison}}\]
pour \(n\) suffisamment grand (sinon c’est le cas de base)
Recherche dichotomique : \(T(n) = \mathcal O(1) + T(\lceil n/2\rceil)\) + 0
Tri par fusion : \(T(n) = \mathcal O(n) + T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + \mathcal O(n)\)
Calculer \(T(n)\) par substitutions… ou utiliser le Master theorem
Soient \(a \geq 1\) et \(b > 1\), \(f\) une fonction et \(T\) définie par \[ T(n) = a \cdot T(n/b) + f(n) \]
Recherche dichotomique : \(a=1\), \(b=2\), \(f(n)=\Theta(1)\)
Tri par fusion : \(a=2\), \(b=2\), \(f(n)=\Theta(n)\)
Pour trier le tableau \(T[g,\ldots,d]\) :
Complexité : \(T(n) \leq \mathcal O(n) + \max_{0<k<n}T(k)+T(n-k-1) = \mathcal O(n) + T(n-1)\)
\(\Rightarrow \qquad T(n) = \mathcal O(n^2)\)
Complexité : \(T(n) \leq \mathcal O(n) + \max\limits_{n/4\leq k\leq 3n/4}[T(k)+T(n-k-1)]\)
Calcul par intuition/récurrence… \(T(n) = \mathcal O(n\log n)\)
Même analyse que le tri rapide :
Déplacer les disques un par un de la tour de gauche à celle de droite en ne plaçant jamais un disque sur un disque de diamètre inférieur
But : trouver une stratégie !
Divisons la stratégie pour \(n\) disques en trois partie :
Le problème a donc une solution récursive, si on s’autorise d’échanger
\[T(n) = \begin{cases} 1 & \text{si } n=1 \\ T(n-1) + 1 + T(n-1) = 1+2T(n-1) &\text{sinon}\end{cases}\]
\(\Rightarrow T(n) = 2^n-1\)
On peut démontrer que c’est le nombre minimal de mouvements nécessaires pour gagner… On a donc une stratégie optimale.
def hanoi(n, depart, intermediaire, arrivee):
assert n>0
if n == 1:
print(depart, " -> ", arrivee)
else:
hanoi(n-1, depart, arrivee, intermediaire)
print(depart, " -> ", arrivee)
hanoi(n-1, intermediaire, depart, arrivee)
Comment faire ce choix de pivot ?
###Théorème