Cuestionario: Introduction à la Complexité Algorithmique — 12 preguntas

1. Qu'est-ce que le modèle de calcul WORD-RAM dans l'analyse de la complexité algorithmique?

A. Un modèle basé sur la mémoire RAM réelle d'un ordinateur spécifique, avec des opérations dont le coût varie selon l'architecture matérielle.

B. Un modèle où la complexité est évaluée uniquement en termes d'espace mémoire utilisé, sans tenir compte du temps d'exécution.

C. Un modèle où chaque opération élémentaire est considérée comme prenant un temps constant, permettant de compter précisément le nombre d'opérations.

D. Un modèle où chaque opération élémentaire est considérée comme prenant un temps variable selon la taille de l'entrée.

Answer: (C)

Explicación

Le modèle WORD-RAM suppose que chaque opération élémentaire (affectation, opération arithmétique, test, etc.) prend un temps constant, ce qui permet de compter précisément le nombre d'opérations pour estimer la complexité en temps d’un algorithme.

2. Quel auteur ou référence précise est associé à la définition de la complexité en temps dans le modèle WORD-RAM mentionné dans le contenu ?

A. Landau (1894)

B. HAI403I (cours 1)

C. Perroux (1980)

D. Kuznets (date inconnue)

Answer: (B)

Explicación

La définition de la complexité en temps dans le modèle WORD-RAM, selon le contenu, est associée à HAI403I (cours 1), qui précise que chaque opération élémentaire prend un temps constant dans ce modèle.

3. Quel est le rôle principal d’un algorithme dans l’analyse d’un problème ?

A. Il sert à vérifier la correction de la solution proposée.

B. Il sert à décrire la structure de données utilisée.

C. Il permet de valider la complexité théorique du programme.

D. Il permet de résoudre efficacement un problème donné.

Answer: (D)

Explicación

L’algorithme a pour fonction principale de résoudre efficacement un problème donné, en suivant une procédure précise et finie.

4. Quelle est la date de publication ou d'introduction de la notation de Landau (O, Ω, Θ) utilisée pour l'analyse asymptotique en algorithmique ?

A. Dans les années 1950 par Donald Knuth

B. Au début du 20e siècle par David Hilbert

C. Au 21e siècle par Leslie Valiant

D. Vers 1894 par Edmund Landau

Answer: (D)

Explicación

La notation de Landau (O, Ω, Θ) a été introduite en 1894 par le mathématicien allemand Edmund Landau pour exprimer la croissance asymptotique des fonctions, notamment en analyse mathématique et en théorie des nombres, et est largement utilisée en analyse d'algorithmes depuis cette date.

5. En quoi la méthode naïve de calcul de xn diffère-t-elle de la méthode divide-and-conquer pour le calcul de la puissance?

A. La méthode naïve effectue des multiplications successives, tandis que divide-and-conquer divise le problème en sous-problèmes plus petits.

B. Les deux méthodes ont une complexité en temps en O(log n).

C. La méthode divide-and-conquer ne peut pas être utilisée pour calculer xn.

D. Les deux méthodes utilisent la même stratégie de division du problème.

Answer: (A)

Explicación

La méthode naïve calcule xn par des multiplications successives, ce qui est simple mais coûteux en temps. La méthode divide-and-conquer, en revanche, divise le problème en sous-problèmes plus petits (par exemple, en utilisant la propriété x^n = (x^{n/2})^2), ce qui permet de réduire la complexité à O(log n). Ainsi, leur objectif est le même, mais leur stratégie et leur efficacité diffèrent.

6. Qui est crédité d'avoir formulé ou publié une œuvre majeure sur les algorithmes récursifs en 1968 ?

A. Alan Turing, 1936

B. Edsger Dijkstra, 1968

C. Donald Knuth, 1968

D. John von Neumann, 1945

Answer: (C)

Explicación

Donald Knuth est crédité en 1968 pour ses travaux fondamentaux sur la conception et l'analyse d'algorithmes, y compris ceux utilisant la récursion, notamment dans ses œuvres majeures sur l'art de l'informatique. Les autres figures, bien que importantes, ne sont pas associées spécifiquement à cette contribution en 1968.

7. Quelle est la cause principale permettant de garantir la validité d’un algorithme itératif ?

A. L’analyse de la croissance asymptotique de la fonction

B. La preuve par récurrence appliquée à la fonction

C. La preuve d’invariant de boucle qui reste vrai avant et après chaque itération

D. L’évaluation de la complexité en espace de l’algorithme

Answer: (C)

Explicación

La preuve d’invariant de boucle est la méthode principale pour garantir la correction d’un algorithme itératif, en montrant qu’une propriété reste vraie à chaque étape, assurant ainsi la validité de l’algorithme.

8. Comment appliquer concrètement la preuve d’invariant de boucle ou la preuve par récurrence pour valider un algorithme ?

A. En simulant l’algorithme pour plusieurs cas d’entrée et en vérifiant que le résultat est correct.

B. En définissant une propriété Pi qui reste vraie avant et après chaque étape, puis en la prouvant par induction pour la boucle.

C. En écrivant un programme de test qui compare la sortie de l’algorithme à une solution connue.

D. En vérifiant que l’algorithme termine dans un nombre fini d’étapes, sans nécessairement prouver la correction.

Answer: (B)

Explicación

La preuve d’invariant de boucle consiste à définir une propriété Pi qui doit être vraie avant et après chaque itération de la boucle, puis à la prouver par induction. La preuve par récurrence consiste à montrer que la propriété est vraie pour le cas de base, puis qu’elle reste vraie lors de la transition d’un n à n+1. Ces méthodes sont appliquées concrètement en formalisant et en prouvant ces invariants ou propriétés pour garantir la correction de l’algorithme.

9. Quelle est la caractéristique principale de la notation de Landau O(g) en analyse asymptotique?

A. Elle indique que la fonction f ne dépasse pas la fonction g pour tout n, sans exception.

B. Elle stipule qu’il existe une constante c et un n₀ tels que, pour tout n ≥ n₀, f(n) ≤ c·g(n).

C. Elle affirme que f(n) est exactement égal à c·g(n) pour une valeur n donnée.

D. Elle indique simplement que f(n) croît plus vite que g(n) à l’infini.

Answer: (B)

Explicación

La notation O(g) signifie qu’il existe une constante c et un seuil n₀ tels que, pour tout n ≥ n₀, f(n) ≤ c·g(n). C’est une borne supérieure asymptotique, essentielle pour comparer la croissance des fonctions en analyse d’algorithmes.

10. Que signifie la croissance d'une fonction en analyse asymptotique ?

A. Elle indique la vitesse à laquelle la fonction tend vers zéro lorsque la variable tend vers l'infini.

B. Elle décrit la manière dont la valeur de la fonction évolue lorsque la variable tend vers l'infini, notamment sa limite ou son ordre de croissance.

C. Elle correspond à la valeur exacte de la fonction pour une valeur donnée de la variable.

D. Elle indique la variation de la fonction en un point précis, comme une dérivée ou une pente locale.

Answer: (B)

Explicación

La croissance d'une fonction en analyse asymptotique décrit comment la valeur de la fonction évolue lorsque la variable tend vers l'infini, notamment en utilisant des notations comme O(n), log n, ou 2^n pour classer cette croissance en ordre.

11. Selon la définition en analyse asymptotique, si la limite de f(x)/g(x) lorsque x tend vers l'infini est une constante finie non nulle, que peut-on déduire sur la comportement asymptotique de f par rapport à g ?

A. f tend vers zéro plus vite que g

B. f est en Ω(g) mais pas en O(g)

C. f est en O(g) mais pas en Ω(g)

D. f est en Θ(g)

Answer: (D)

Explicación

La limite finie et non nulle de f(x)/g(x) lorsque x tend vers l'infini implique que f et g ont la même croissance asymptotique, c'est-à-dire que f = Θ(g).

12. Quel est le rôle principal des complexités classiques en algorithmique ?

A. Évaluer et comparer l’efficacité des algorithmes

B. Définir la syntaxe d’un algorithme

C. Optimiser la syntaxe du code source

D. Mesurer la précision d’un résultat numérique

Answer: (A)

Explicación

Les complexités classiques (O, Ω, Θ) sont utilisées pour évaluer et comparer l’efficacité des algorithmes en fonction de leur consommation en ressources (temps et espace), ce qui permet de déterminer leur performance relative pour de grandes tailles d’entrée.