[Examen Blanc] Tâche 2 : Algorithme alpha

שאלה 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(0)=b\)

\(T(1)=1\)

\(T(1)=b\)

\(T(0)=1\)

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

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

שאלה 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 + c_2 \times n + T(\frac{n}{2})\)

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

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

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

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

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

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

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

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

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

שאלה 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} = n\)

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

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

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

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

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

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

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

שאלה 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.

יוצרים	Pierre Dupont
מועד הגשה	01/09/2026 16:00:00
מגבלת הגשות	אין הגבלה

מידע