[Examen Blanc] Tâche 2 : Algorithme alpha

Question 1: Définition du cas de base de la récurrence

Considérez l'algorithme alpha décrit ci-dessus.
Sélectionnez, parmi les réponses proposées, celle qui définit le cas de base de la récurrence de l'algorithme alpha.

\(T(1)=b\)

\(T(1)=1\)

\(T(n-1)=b\)

\(T(0)=1\)

\(T(0)=b\)

\(T(n-1)=1\)

Question 2: Définition de la récurrence dans le cas général

Considérez l'algorithme alpha décrit ci-dessus.
Sélectionnez, parmi les réponses proposées, celle qui définit le cas général de la récurrence de l'algorithme alpha.

\(T(n)=c_1 + 2 \times T(n-1)\)

\(T(n)= c_1 \times n + T(n-1)\)

\(T(n-1)=c_1 + T(n-1)\)

\(T(n)=c_1 + T(\frac{n}{2})\)

\(T(n)=c_1 + c_2 \times n + T(\frac{n}{2})\)

\(T(n)=c_1 + T(n-1)\)

\(T(n)= c_1 \times n + T(\frac{n}{2})\)

\(T(n)=c_1 + c_2 \times n + T(n-1)\)

\(T(n-1)= c_1 \times n + T(n-1)\)

\(T(n)=c_1 + c_2 \times n + 2 \times T(n-1)\)

Question 3: Profondeur maximale

Pour un problème de taille n, quelle sera la profondeur de récursion maximale, désignée généralement par \(i_{max}\), atteinte par l'algorithme alpha décrit ci-dessus.

Note : cette sous-question ne peut rapporter des points que si vous avez correctement répondu aux 2 sous-questions précédentes.

\(i_\text{max} = 2 \times n\)

\(i_\text{max} = n+1\)

\(i_\text{max} = \frac{n}{2}\)

\(i_\text{max} = n-1\)

\(i_\text{max} = n\)

\(i_\text{max} = n*(n+1)/2\)

\(i_\text{max} = n*(n-1)/2\)

\(i_\text{max} = n^2\)

Question 4: Complexité temporelle de l'algorithme

Quelle est la complexité temporelle de la méthode alpha obtenue en résolvant les équations de récurrence de cette méthode ?

Identifiez la complexité temporelle et la notation la plus appropriée pour décrire cette complexité.

Indiquez d'abord la notation (Omega, Theta ou O) suivi de la complexité indiquée entre parenthèse.

par exemple, indiquez Omega(log(n)) pour une complexité qui serait \(\Omega(\log(n))\)
par exemple, indiquez O(n*log(n)) pour une complexité qui serait \(O(n\log(n))\)
par exemple, indiquez Theta(2^n) pour une complexité qui serait \(\Theta(2^n)\)

Note : cette sous-question ne peut rapporter des points que si vous avez correctement répondu aux 3 sous-questions précédentes.

Auteur(s)	Pierre Dupont
Date limite	01/09/2026 16:00:00
Limite de soumission	Pas de limite

Informations