Séquence de formation

Programme de $1^e$ NSI

Contenus	Capacités attendues	Commentaires
Tris par insertion, par sélection	Écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.	La terminaison de ces algorithmes est à justifier. On montre que leur coût est quadratique dans le pire cas.

Prérequis

Syntaxe python (boucle for, accès dans un tableau, procédures, branchement conditionnels)
Notion de variant de boucle, prouver la terminaison d'un algorithme
Notion d'invariant de boucle, prouver la correction d'un algorithme
Évaluer la complexité d'un algorithme

Soit la liste python:

liste = [2, 5, 1, 6, 7, 9, 0]

Le code python pour accéder à la valeur 5 est:
a. liste[5]
b. liste[2]
c. liste[1]

Soit le code python:

e = 1
f = 10
while f > 2:
    f = f-1
    e = e+e

Le variant de boucle dans ce code est:
a. La variable f
b. La différence entre la valeur de e à l'initialisation et à la fin de l'exécution
c. La différence entre la valeur de f et la valeur 2
d. La variable e
Cet algorithme se termine:
a. Vrai
b. Faux

Soit le code python:

def pow2(n):
    """ calcul de puissance de 2 """
    p = 1
    n = c
    while c > 0:
        p = p*2
        c = c-1
    return p

La complexité de cet algorithme vaut:
a. O( $2^n$ )
b. O(n)
b. O( $n^2$ )
Un invariant de boucle:
a. Permet de trouver le nombre d'itération d'une boucle
b. Est vrai avant, pendant et après l'exécution de l'algorithme
c. Est une variable qui ne change jamais
d. Permet de vérifier que l'algorithme est correct