CM2

Exercice 1 :

F(n: entier)
	si n <= 1
		return 1
	pour j=n-1 à 1:
		S = F(j)

1. Donner l’arbre d’execution pour n=4 F(4) F(3) F(2) F(1) F(1) F(2) F(1) F(1)
2. Taille de l’arbre d’exécution Hauteur de l’arbre = n Degré (dans le pire des cas) = n-1 $O((n-1{)}^n)$ Espace requis = taille de la pile d’execution au max (n)
3. Complexité de F Nombre de nœuds = $(n-1{)}^n$ Coût d’un nœud $O(n)$ $⟹O(n(n-1{)}^n)$
4. Complexité de l’accélération de F $O(n)$

TD1

Exercice 1

Accélération : Si S est une variable globale, alors les paramètres sont (i, k) où i = index de l’element. Nombre différent couple possibles = $n\times k$ $⟹O(n\times k)$ Taille de l’entré = $n+\log k$ $T(n+\log k)=n+2^{\log k}$

Exercice 2

Décision : Paramètres : ($S$, $w_1$, $w_2$, $w_3$)

• Prendre l’objet dans le sac 1
• Prendre l’objet dans le sac 2
• Prendre l’objet dans le sac 3
• Ne pas prendre l’objet Complexité : Degré = 4 et S est de taille n donc la complexité est $O(4^n)$ et le coût d’un nœud est $O(1)$. La complexité totale est $O(4^n)$. Accélération : Les paramètres sont (i, $w_1$, $w_2$, $w_3$) Nombre des combinaisons de paramètres = $n\times W_1\times W_2\times W_3\times W_4$ Donc la complexité = $O(n\times W_1\times W_2\times W_3\times W_4)$

Exercice 3