Quiz: Fondamentaux de la vérification algorithmique — 10 Fragen

1. Qu'est-ce qu'une spécification d'un algorithme ?

A. Le code source traduit dans un langage de programmation

B. Une documentation technique détaillée du programme final

C. Un ensemble de conditions décrivant précisément le cahier des charges, notamment les données d’entrée et de sortie

D. La démarche ou l’architecture des instructions permettant de réaliser une tâche

Answer: (C)

Erklärung

La spécification d'un algorithme est un ensemble de conditions qui décrivent précisément le cahier des charges, notamment les données d’entrée et de sortie attendues, servant de référence pour la conception et la vérification.

2. Selon G. Dupont en 2025, qu'est-ce qu'un algorithme qui termine ?

A. Un algorithme qui s’arrête après un nombre fini d’étapes

B. Un algorithme qui ne s’arrête jamais mais reste utile

C. Un algorithme qui s’arrête uniquement si l'utilisateur l'interrompt

D. Un algorithme qui tourne indéfiniment mais donne une réponse approximative

Answer: (A)

Erklärung

G. Dupont en 2025 définit qu’un algorithme qui termine est celui qui s’arrête après un nombre fini d’étapes, ce qui est la propriété fondamentale de la terminaison.

3. Quel est le rôle principal de la correction d’un algorithme ?

A. Garantir que l’algorithme utilise la moindre mémoire possible

B. Assurer que l’algorithme termine dans un temps fini

C. Vérifier que l’algorithme respecte la spécification en produisant le bon résultat s’il termine

D. Optimiser la vitesse d’exécution de l’algorithme

Answer: (C)

Erklärung

La correction d’un algorithme a pour rôle principal de garantir qu’il respecte la spécification en produisant le bon résultat lorsque l’algorithme termine. Les autres options concernent la terminaison, l’efficacité ou l’utilisation des ressources, mais ne décrivent pas la fonction principale de la correction.

4. En quelle année la propriété de terminaison d’un algorithme a-t-elle été formellement établie ou publiée selon le contexte ?

A. 2020

B. 2022

C. 2025

D. 2019

Answer: (C)

Erklärung

La propriété de terminaison a été formellement abordée ou publiée par G. Dupont en 2025, année où il a publié ses travaux sur la preuve de terminaison à l’aide de variants. Les autres années ne correspondent pas à cette étape spécifique dans le contexte donné.

5. En quoi la preuve par invariants diffère-t-elle de la preuve par variants dans la vérification d’un algorithme ?

A. La preuve par invariants concerne la terminaison en montrant une variable décroissante, alors que la preuve par variants conserve une propriété logique.

B. La preuve par invariants garantit la correction partielle en conservant une propriété, tandis que la preuve par variants garantit la terminaison en montrant une décroissance strictement positive.

C. La preuve par invariants ne concerne que les algorithmes récursifs, alors que la preuve par variants s’applique uniquement aux boucles.

D. Les invariants sont utilisés pour prouver la correction, alors que les variants sont utilisés pour prouver la correction et la terminaison.

Answer: (B)

Erklärung

La preuve par invariants sert à démontrer que la propriété logique reste vraie à chaque étape, assurant la correction partielle, tandis que la preuve par variants montre que l’algorithme termine en prouvant qu’une variable décroît strictement et atteint une limite, garantissant la terminaison.

6. Qui a formulé la méthode de preuve par variants pour démontrer la terminaison d’un algorithme ?

A. G. Dupont

B. A. Turing

C. E. Church

D. C. Gödel

Answer: (A)

Erklärung

G. Dupont est crédité d’avoir formalisé la méthode de preuve par variants pour assurer la terminaison d’un algorithme, notamment dans ses travaux de 2025-2026. Les autres noms sont liés à d’autres domaines de l’informatique ou de la logique, mais pas à cette méthode spécifique.

7. Quelle est la cause principale qui permet de garantir la terminaison des algorithmes simples ?

A. Ils sont écrits en langage de haut niveau comme Python ou Java

B. Ils ne comportent pas de boucle ou seulement des boucles for de longueur fixe

C. Ils utilisent des algorithmes récursifs pour réduire la complexité

D. Ils utilisent des structures de données avancées comme les arbres ou les graphes

Answer: (B)

Erklärung

Les algorithmes simples se caractérisent par l'absence ou la simplicité des boucles, ce qui facilite la preuve de leur terminaison. En ne comportant pas de boucle ou uniquement des boucles for de longueur fixe, ils évitent les risques de boucle infinie, ce qui garantit leur terminaison.

8. Comment appliquer concrètement la preuve de terminaison d’un algorithme récursif ?

A. En vérifiant que tous les paramètres d’entrée sont de types corrects, pour garantir la terminaison.

B. En utilisant uniquement des invariants de boucle pour garantir la correction, sans se soucier de la décroissance.

C. En prouvant que l’algorithme ne comporte pas de boucle infinie sans utiliser de variant.

D. En montrant que la valeur d’un paramètre décroît strictement à chaque appel récursif, assurant ainsi qu’il atteint une valeur limite finie.

Answer: (D)

Erklärung

La preuve de terminaison d’un algorithme récursif repose sur la définition d’un **variant** qui décroît strictement à chaque étape, garantissant que l’appel récursif progresse vers la condition d’arrêt. La réponse 0 décrit précisément cette démarche, en montrant que la valeur d’un paramètre ou d’une fonction associée diminue à chaque étape, ce qui assure la fin de la récursion.

9. Que caractérise principalement la signature d'une fonction ?

A. Le nom de la fonction et ses commentaires

B. La logique interne et les algorithmes utilisés

C. Les conditions de pré- et post-conditions

D. Les types des variables d’entrée et de sortie

Answer: (D)

Erklärung

La signature d'une fonction définit principalement les types des variables d’entrée et de sortie, ce qui constitue son contrat formel pour assurer la compatibilité et la compréhension du code.

10. Qu'est-ce que la vérification de la signature d'une fonction en programmation ?

A. C'est le processus de contrôle que les types des variables d'entrée et de sortie respectent la déclaration de la fonction.

B. C'est la vérification que la fonction produit le résultat attendu pour un cas donné.

C. C'est la validation que la fonction ne contient pas d'erreurs syntaxiques.

D. C'est la confirmation que la fonction s'exécute dans un temps raisonnable.

Answer: (A)

Erklärung

La vérification de la signature consiste à s'assurer que les types des paramètres d'entrée et de sortie correspondent à ceux déclarés dans la signature, garantissant ainsi la conformité du contrat de la fonction.