1NSI : Exercices sur Terminaison des algorithmes

Ex

On considère l'algorithme suivant :

i prend la valeur 1000
Tant que i > 0 :
    i prend la valeur i-1
afficher i

1. Déterminer un variant de boucle pour la boucle Tantque
2. En déduire que l'algorithme Termine

Ex

On considère l'algorithme suivant, qui détermine le premier entier \(n\) tel que \(3n+5>100\)

i prend la valeur 0
Tant que 3*i+5 ≤ 100 :
    i prend la valeur i+1
afficher(i)

1. Déterminer un variant de boucle pour la boucle Tantque
2. En déduire que l'algorithme Termine

Ex

i prend la valeur 100
m prend la valeur "bonjour"
Tant que i > 5 ET longueur(m) > 2 :
    i prend la valeur i-1
afficher(i)

1. Déterminer un variant de boucle pour la boucle Tantque
2. En déduire que l'algorithme Termine

Ex

On considère l'algorithme de multiplication d'une entier \(a\) par un entier \(b\) suivant :

def multiplie(a:int,b:int)->int:
    x = a
    y = b
    z = 0
    while y !=0:
        z = z + x
        y = y - 1
    return z

1. Déterminer un variant de boucle pour la boucle while
2. En déduire/Démontrer que l'algorithme Termine
3. Déterminer un invariant de boucle, pour la boucle while
4. En déduire/Démontrer que l'algorithme est Correct (càd que l'entier \(z\) renvoyé est bien le produit de \(a\) par \(b\))

Ex

On considère l'algorithme de Tri par Sélection suivant :

def tri_selection(A:list)->list:
n=len(A)
for i in range(n-1):
    mini = i
    for j in range(i+1,n):
        mini = j
    tmp = A[mini]
    A[mini] = A[i]
    A[i] = tmp
return A

1. Déterminer un variant de boucle pour la (première) boucle for
2. En déduire/Démontrer que l'algorithme Termine
3. Déterminer un invariant de boucle, pour la première boucle for
4. En déduire/Démontrer que l'algorithme est Correct (càd que la liste renvoyée est bien triée)