1NSI : Exercices sur Correction des algorithmes

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 invariant de boucle, pour la boucle while
2. 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
    A[i], A[mini] = A[mini], A[i]
return A

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