QCM : Informatique et calculabilité (11 questions)

Questions et réponses du QCM

1. Quelle caractéristique définit un algorithme destiné à un lecteur humain ?

C’est une description ouverte d’un problème, sans ordre défini ni limite dans le nombre d’instructions.
C’est une suite d’instructions traduites en langage machine et dépourvues de toute ambiguïté.
C’est une suite d’opérations arithmétiques conçue pour être exécutée par une machine particulière.
C’est une suite finie d’instructions qui résout un problème et peut rester vague dans sa précision.

C’est une suite finie d’instructions qui résout un problème et peut rester vague dans sa précision.

Explication

Un algorithme est une suite finie d’instructions destinée à résoudre un problème pour un lecteur humain, et sa précision peut rester vague. À la différence d’un programme, il n’a pas besoin d’être formulé sans ambiguïté pour une machine.

2. Lorsqu’un algorithme est écrit pour être compris et exécuté par une machine, quelle exigence caractérise le programme obtenu ?

Il doit être correct et formulé sans ambiguïté pour la machine.
Il doit être traduit en instructions destinées exclusivement à un lecteur humain.
Il doit résoudre le problème sans préciser l’ordre des opérations.
Il peut rester vague dès lors qu’un lecteur humain en comprend l’intention.

Il doit être correct et formulé sans ambiguïté pour la machine.

Explication

Un programme est un algorithme écrit dans un langage compris par une machine ; il doit donc être correct et non ambigu. La possibilité de rester vague concerne l’algorithme destiné à un lecteur humain, pas le programme.

3. Quelles opérations la Pascaline de Blaise Pascal, créée en 1642, effectuait-elle ?

Le calcul de polynômes par différences successives.
Des additions et des soustractions.
Le comptage électrique de données de recensement.
Des multiplications et des divisions.

Des additions et des soustractions.

Explication

Créée par Blaise Pascal en 1642, la Pascaline effectuait des additions et des soustractions. Le calcul de polynômes correspond à la machine à différences de Babbage, et non à la Pascaline.

4. Quelle fonction la tabulatrice de Herman Hollerith remplissait-elle lors du recensement américain de 1890 ?

Elle exécutait les quatre opérations arithmétiques au moyen d’un mécanisme manuel.
Elle produisait des tables de polynômes par calcul mécanique des différences.
Elle réalisait du comptage à l’aide d’une machine électrique, à 150 additions par seconde.
Elle enregistrait les données du recensement sans effectuer de calculs.

Elle réalisait du comptage à l’aide d’une machine électrique, à 150 additions par seconde.

Explication

Utilisée pour le recensement américain de 1890, la tabulatrice de Hollerith réalisait du comptage grâce à une machine électrique, à raison de 150 additions par seconde. Le calcul de polynômes était l’objectif de la machine à différences de Babbage.

5. Dans la récursion de Peano, que désigne l’opération ++E++E appliquée à un entier naturel EE ?

La somme de EE et d’un entier fourni en entrée.
Le prédécesseur de EE, défini lorsque E>0E>0.
Le résultat de EE divisé par deux avec une division entière.
Le successeur de EE, soit E+1E+1.

Le successeur de $$E$$, soit $$E+1$$.

Explication

L’opération ++E++E désigne le successeur de EE, obtenu en lui ajoutant un. L’opération de prédécesseur est notée −−E--E et devient indéterminée lorsque EE vaut zéro.

6. Dans la machine de Peano 3.0, quelle valeur renvoie `vide(L)` lorsque `L` est la liste vide ?

La valeur 1
Le reste de la liste
La valeur 0
La tête de la liste

La valeur 1

Explication

La fonction `vide(L)` renvoie 1 si la liste est vide et 0 dans le cas contraire. La valeur 0 correspond donc à une liste non vide, et non à la liste vide.

7. Dans la multiplication russe binaire, quel est le rôle de l’accumulateur ZZ au fil des itérations ?

Doubler la valeur de YY avant chaque division entière
Remplacer XX par son reste après chaque multiplication
Mémoriser le quotient obtenu après chaque division par 2
Conserver progressivement les contributions qui composent le produit final

Conserver progressivement les contributions qui composent le produit final

Explication

À chaque étape où YY est impair, XX est ajouté à ZZ, qui finit par contenir le produit. La valeur de YY, elle, est divisée par 2 à chaque itération plutôt que doublée.

8. À quelle date la thèse de Church-Turing situe-t-elle l’établissement de l’idée que tout algorithme intuitivement calculable peut être implémenté par un programme de Peano ?

Elle la situe en 1930, avec les travaux sur les machines de calcul.
Elle ne lui associe aucune date précise dans les éléments présentés.
Elle la situe en 1890, lors du recensement américain.
Elle la situe en 1946, lors des travaux d’Emil Post.

Elle ne lui associe aucune date précise dans les éléments présentés.

Explication

La thèse de Church-Turing est énoncée sans date précise dans les éléments présentés. L’année 1946 est associée à la démonstration de l’indécidabilité du problème PCP par Emil Post, et non à l’établissement de cette thèse.

9. En quoi le problème PCP diffère-t-il d’un problème de décision pour lequel un algorithme général existe ?

La décision dépend de la longueur maximale imposée à la séquence.
La question porte sur l’égalité de chaque domino pris séparément.
Un algorithme peut répondre si l’on interdit les répétitions de dominos.
Aucun algorithme général ne peut toujours déterminer si une séquence de dominos convient.

Aucun algorithme général ne peut toujours déterminer si une séquence de dominos convient.

Explication

Le PCP est indécidable : aucun algorithme général ne garantit une réponse oui ou non pour toute instance. L’interdiction des répétitions ne caractérise pas cette différence, car le PCP autorise les répétitions.

10. Quelle méthode de chiffrement utilise une clé aléatoire aussi longue que le message et ne la réutilise jamais, ce qui la rend incassable ?

Le masque jetable, qui emploie une clé aléatoire de la longueur du message
Le chiffrement symétrique, qui réutilise une clé secrète pour les deux opérations
Le code de César, qui décale chaque lettre d’un nombre fixe de positions
Le chiffre de Vigenère, qui répète une clé fournissant des décalages successifs

Le masque jetable, qui emploie une clé aléatoire de la longueur du message

Explication

Le masque jetable exige une clé aléatoire aussi longue que le message et jamais réutilisée ; il est présenté comme incassable. Vigenère utilise plutôt une clé qui fournit des décalages successifs, sans cette exigence de longueur et de non-réutilisation.

11. Pour qu’Alice transmette un message confidentiel à Bob avec la cryptographie à clés publiques, quelle conséquence découle du choix de la clé de chiffrement ?

Bob peut le déchiffrer avec sa clé privée correspondante.
Alice peut le déchiffrer avec sa propre clé privée.
Alice permet à Bob de le vérifier avec sa clé publique.
Bob doit le déchiffrer avec sa clé publique.

Bob peut le déchiffrer avec sa clé privée correspondante.

Explication

Le chiffrement avec la clé publique de Bob permet au détenteur de la clé privée correspondante, Bob, de déchiffrer le message. Chiffrer avec la clé privée d’Alice relève du mécanisme de signature et ne garantit pas la confidentialité envers Bob.

Révisez avec les flashcards

Mémorisez les réponses avec 10 flashcards sur Informatique et calculabilité.

Qu’est-ce qu’un algorithme ?

Une suite finie d’instructions permettant de résoudre un problème, destinée à un lecteur humain et pouvant rester vague.

Quels traducteurs les langages évolués nécessitent-ils ?

Des assembleurs, des interpréteurs ou des compilateurs.

Quelle opération la Pascaline de Blaise Pascal effectue-t-elle ?

Des additions et des soustractions.

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Informatique et calculabilité.

Voir la fiche →

Cours similaires

Réseaux et protocoles Internet

Assistant vocal et démarche de projet

IA générative et culture des données

Listes d’entiers en machine de Peano

Programmation

Bases de données et archivage

Programmation de la carte micro:bit

Programmation

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM