C7 : Exercices

Assertions

C7.E1 : Vérification de préconditions

On s'intéresse à une fonction f(liste) qui prend une liste triée d'entiers en paramètre.

Écrire les assertions qui permettent, en début de fonction de vérifier les préconditions suivantes sur la liste passée en paramètre :

Validation d'une fonction

C7.E11 : Doctests

1) Écrire la fonction sans_doubon(liste:list) -> list qui prend une liste d'entiers positifs en paramètres et renvoie une liste contenant les mêmes valeurs sans doublons.

2) Proposer un jeu de tests pertinent pour cette fonction sous la forme de doctests.

C7.E12 : Tests avec des assertions

1) Écrire la fonction miroir(chaine:str) -> str qui prend une chaine de caractères en paramètres et renvoie une chaine avec les caractères dans l'ordre inverse.

2) Proposer un jeu de tests pertinent pour cette fonction en utilisant des assertions dans le programme principal.

C7.E13 : Invalider une fonction avec des tests

On considère la fonction suivante qui est censée tester l'appartenance d'une valeur à un tableau.

def appartient(val, tab):
    for i in range(len(t)):
        if t[i] == v:
            trouvee = True
        else:
            trouvee = False
    return trouvee

Proposer des tests pour cette fonction, et en particulier des tests montrant les différentes raisons pour lesquelles elle est incorrecte.

Complexité

C7.E21 (sans ordinateur)

Dans cet exercice on s'intéresse aux algorithmes qui permettent de transformer des listes d'effectifs en des liste d'effectifs cumulés.

Par exemple ces algorithme doivent transformer [2, 7, 8, 5, 6] en [2, 9, 17, 22, 28].

1) On s'intéresse à l'algorithme codé dans la fonction suivante : 

def eff_cumul_v1(l:list)->list:
    n = len(l)
    liste_cumul = []
    for i in range(n):
        cumul = 0
        for j in range(i+1):
            cumul = cumul + l[j]
        liste_cumul.append(cumul)
    return liste_cumul

# Programme principal
assert eff_cumul_v1([2]) == [2]
assert eff_cumul_v1([2, 10]) == [2, 12]
print("les tests sont ok")

1.a. Déterminer le nombre d'additions effectuées par la fonction avec une liste de longueur 1, puis 2, puis 3 et enfin 4.

1.b. Déterminer le nombre d'addition effectuées par la fonction avec une liste de longueur n.

2) Une version plus optimale

2.a. Proposer une version plus optimale de cette fonction de façon à ce que son coût soit linéaire.

2.b. Déterminer le nombre d'additions effectuées par votre fonction avec une liste de longueur 1, puis 2, puis 3 et enfin 4.

C7.E22 (sans ordinateur)

On s'intéresse à la fonction ci-dessous.

def search(x:int, l:list)->int:
    # x est la valeur à chercher
    # y est une liste de valeurs
    for i in range(len(y)):
        if x == y[i]:
            return i
    return None

1) Écrire la docstring de cette fonction.

2) Déterminer la coût de l'algorithme utilisé en fonction de la longueur de la liste passée en paramètre.

C7.E23 : Recherche dans une grille triée (sans ordinateur)

D'après e-nsi.gitlab.io/pratique/N3/540-grille_triee/sujet/

On considère une grille triée, c'est-à-dire une grille de \(n\) lignes et \(m\) colonnes, d'éléments distincts, dont chaque ligne et chaque colonne est triée dans l'ordre croissant.

Exemple de grille triée :

11 33 42 63
20 52 67 63
25 61 88 95

Les grilles seront implémentés par une classe Grille dont les seules méthodes sont :

Pour la suite de l'exercice, il n'est pas nécessaire de connaitre le détail du code de l'implémentation de la classe Grille.

Travail à faire :

On souhaite savoir si un élément est présent dans ce tableau.

Écrire une fonction recherche(elt, grille) qui renvoie None si elt est absent de grille, ou le tuple (i, j) correspondant à la position de elt si elt est présent dans grille.

On définit le cout de la recherche comme le nombre d'appels à la fonction donne_valeur. Le coût de la fonction proposée doit être optimal, ici un cout de \(n+m\) est possible.

Preuve d'un algorithme

C7.E31 : Multiplication avec des additions

1) Écrire une fonction qui prend deux nombres entiers positifs a et b comme paramètres et renvoie le produit a×b. La fonction ne devra pas utiliser l'opérateur *.

2) Faire la preuve de l'algorithme utilisé en trouvant :

3) Améliorer la fonction pour que les paramètres a et b puissent être positifs ou négatifs.