sujet Test 3 : preuve

1. Suppression de valeur

Donnez la complexité et prouvez que l'algorithme-1 suivant rend une liste L2, restriction de L aux valeurs différentes de val.

Nom : Algorithme-1
Entrées : 
    val : une valeur
    L : une liste de n valeurs
Programme :
    création d’une liste L2 vide
    pour chaque élément x de L :
        si x ≠ val : 
            ajoute x à la fin de L2
    Retour L2

2. Suppression de doublon

Donnez la complexité et prouvez que l'algorithme-2 suivant retourne une liste L2 ne contenant qu’une seule occurrence de chaque valeur de L, en conservant le même ordre.

Nom : Algorithme-2
Entrées : 
    L : une liste de n valeurs
Programme :
    création d’une liste L2 vide
    tant que L est non vide:
        x = L[0]
        ajoute x à la fin de L2
        L = algorithme-1(L, x)    
    Retour L2