QCM : Fondamentaux de la vérification algorithmique — 10 questions

Question 1

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

Le code source traduit dans un langage de programmation

Une documentation technique détaillée du programme final

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

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

Explication

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.

Answer

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

Question 2

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

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

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

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

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

Explication

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.

Answer

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

Question 3

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

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

Assurer que l’algorithme termine dans un temps fini

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

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

Explication

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.

Answer

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

Question 4

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 ?

2020

2022

2025

2019

Explication

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é.

Answer

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.

Answer

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

Answer

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

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

Answer

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.

Question 5

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

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

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.

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

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

Explication

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.

Question 6

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

G. Dupont

A. Turing

E. Church

C. Gödel

Explication

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.

Question 7

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

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

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

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

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

Explication

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.

Question 8

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

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

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

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

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.

Explication

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.

Question 9

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

Le nom de la fonction et ses commentaires

La logique interne et les algorithmes utilisés

Les conditions de pré- et post-conditions

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

Explication

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.

Question 10

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

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.

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

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

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

Explication

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.

QCM : Fondamentaux de la vérification algorithmique — 10 questions

Questions et réponses du QCM

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

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

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

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 ?

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

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

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

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

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

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

Révisez avec les flashcards

Approfondir avec la fiche

Cours similaires

Introduction à l'Intelligence Artificielle Symbolique

Introduction aux documents et sécurité en construction

Introduction à l'Informatique et IA

Introduction aux marchés publics et réglementations du bâtiment

Gestion des imprimantes Windows et PDF

Introduction aux bases de données relationnelles

Crée tes propres QCM