Théorie des langages : Exercices info3 a&g ds
Télécharger PDFInformations importantes pour les étudiants
N’oubliez pas d’indiquer votre numéro d’étudiant en grisant les cases du tableau.
Donnez aussi votre numéro d’étudiant au format standard.
Multiplication en binaire
1. Le décalage à droite est l’équivalent de la multiplication par 2 en binaire.
Questions sur la notation et les transitions
Question 1 : En notation little-endian, à quel entier correspond le tableau ci-après ?
0123456789
28 1×2 + 1×4 + 1×8 + 1×16
29 3
30 1×20 + 0×21 + 1×22 + 1×23 + 1×24
Aucune des réponses proposées n’est correcte.
Multiplication rapide
Exécution de l’algorithme avec des valeurs spécifiques
Question 12 : Exécutez l’algorithme avec A = 3.2 et B = 5. Que valent x, y, r et i en sortie ?
x = 3.2, y = 0, r = 16, i = 2
Rôle de la variable i
Question 13 : Que calcule la variable i ?
Le nombre de réductions par 2 du problème.
Complexité de l’algorithme
Question 14 : Avec B = 2i, l’algorithme fait environ (en ordre de grandeur) :
2 log2(B) additions.
États initiaux dans l’automate
Question 16 : En q0, que peut-on dire des variables ?
x = A, y = B, r = 0, i = 0.
Conditions d’utilisation pour la preuve de correction partielle
Question 24 : En faisant la preuve de correction partielle, quelles conditions d’utilisation obtient-on ?
B ≠ 0, A ≥ 0, B ∈ ℕ, A ∈ ℕ.
Exécution avec A = 0 ou B = 0
Question 25 : Que se passe-t-il si on exécute l’algorithme avec A = 0 ?
L’algorithme termine et le résultat est correct.
Question 26 : Que se passe-t-il si on exécute l’algorithme avec B = 0 ?
L’algorithme termine et le résultat est correct.
Preuve de correction partielle
Question 27 : À quoi sert l’étape de vérification ?
À garantir la terminaison de la boucle.
FAQ
Qu’est-ce qu’un invariant dans une preuve de correction partielle ?
Un invariant est une propriété qui reste vraie à chaque passage par un état donné du programme.
Pourquoi l’algorithme commence-t-il par vérifier que U[N] = 0 ?
Sinon l’indice i sortirait du tableau D pour vérifier les conditions d’utilisation.
Quelle est la différence entre une preuve de correction partielle et une preuve de correction totale ?
Une preuve de correction partielle ne prouve pas que le programme termine, tandis qu’une preuve de correction totale garantit à la fois la correction et la terminaison.