03

Algorithmes d’exploration d’un arbre d’énumération

Exercice 1

Q 1.1

Soit le nombre de noeuds dans l’arbre des appels récursifs de donc si

Polynome caractéristique de A:
,

d’où l’arbre des appels comporte noeuds. De plus chaque appel est en est de complexité

De même pour : Chaque appel est en l’arbre d’appel comporte

d’où

:

D’où

: Suite arithmétique de raison 1:

Opérations en , noeuds, d’où

Exercice 2

Exercice 3

Q 3.1

Or pas d’expression claire pour , donc
d’où (??????????) (se retrouve avec PC, autre méthode et aucune explication donnée par la prof)

Parcours en

D’où

Q 3.2

Même complexité dans le pire des cas mais meilleure complexité dans le meilleur des cas.

Pour :

• degré 0: A(n-1) appels
• degré >= 1: donc au plus appels

D’où

d’où P.C:
, comlexité en

Q 3.3

Même raisonnement qu’à la question précédente, on majore

À RÉSOUNDRE LOL REVOIT LES NOTIONS DE MATHS DE BASE

Page incomplète ou erronée? Contribuez sur le repo