Quiz: Introduction aux fondamentaux de l'algorithmique — 5 domande

1. Quel mathématicien perse a contribué à la notion d’algorithme ?

A. Muhammad Ibn Mūsā al-Khuwārizmī

B. Alan Turing

C. Pierre-Simon Laplace

D. Ada Lovelace

Answer: (A)

Spiegazione

Muhammad Ibn Mūsā al-Khuwārizmī est mentionné dans le texte comme étant à l’origine de la notion d’algorithme, ce qui en fait le fait précis et vérifiable demandé dans cette question.

2. Comment appliquer le concept de variant de boucle dans la conception d'un algorithme pour assurer la terminaison d'une boucle ?

A. Utiliser un compteur qui s'incrémente à chaque étape sans vérifier sa valeur pour arrêter la boucle

B. S'assurer que la boucle ne contient pas d'opérations qui modifient l’état de la variable de contrôle

C. Choisir une condition d'arrêt basée uniquement sur une variable booléenne indépendante de la boucle

D. Définir une expression entière positive qui décroît strictement à chaque étape et vérifier qu’elle est mise à jour correctement à chaque itération

Answer: (D)

Spiegazione

La bonne pratique consiste à définir une expression entière positive qui décroît strictement à chaque étape, ce qui permet de garantir que la boucle finira par atteindre une condition d'arrêt. Les autres options ne garantissent pas nécessairement la terminaison ou ne suivent pas la méthode basée sur le concept de variant.

3. Qui est généralement crédité de l’approche utilisée pour prouver la correction d’un algorithme via un invariant de boucle ?

A. La méthode de preuve par invariant, souvent attribuée à la logique de la programmation structurée

B. Les travaux de Turing sur la machine universelle

C. Boudouni et ses travaux en algorithmique

D. Les principes de la programmation fonctionnelle de Lambda Calcul

Answer: (A)

Spiegazione

La méthode de preuve par invariant, qui consiste à vérifier l'initialisation, la conservation et la terminaison de l'invariant, est une approche classique en algorithmique pour démontrer la correction totale d’un algorithme. Elle est généralement associée à la logique de la programmation structurée, notamment à la démarche de C. A. R. Hoare.

4. Quelle est la conséquence de l’utilisation de la notation O dans l’étude de la complexité des algorithmes ?

A. Elle facilite la comparaison de l’efficacité des algorithmes pour de grandes tailles d’entrée

B. Elle permet d’évaluer précisément le nombre exact d’opérations pour une taille d’entrée donnée

C. Elle indique que tous les algorithmes ont une complexité identique dans le pire cas

D. Elle simplifie la mise en œuvre pratique de l’algorithme dans un programme

Answer: (A)

Spiegazione

L’utilisation de la notation O permet d’exprimer le comportement asymptotique des algorithmes, ce qui facilite leur comparaison en termes d’efficacité, surtout pour de grandes tailles d’entrée.

5. Quelle propriété garantit que l’algorithme de tri par sélection s’arrête après un nombre fini d’étapes ?

A. L’existence de conditions d’arrêt clairement définies

B. Le fait que la boucle est bornée par la taille du tableau

C. La présence d’un invariant de boucle

D. L’utilisation d’un variant de boucle

Answer: (B)

Spiegazione

Le texte indique que 'L’algorithme se termine lorsque la boucle parcourant la tableau est entièrement exécutée' et que cette terminaison est 'assurée par des boucles bornées, dont la limite est la taille du tableau'. La propriété qui garantit la terminaison est donc que la boucle est bornée par la taille du tableau, assurant un nombre fini d’étapes.