utilisation des tests

analyse d’algorithme
preuve de bon fonctionnement
refactoring
programmation par les tests

Analyse d’algorithme

L’algorithme fonctionne ainsi : à l’étape i l’algorithme place le ième plus petit élément en position i − 1 du tableau

Que devrions nous tester ? Cas général des tris :

tableau simple à un élément : normalmenet les algorithmes ne font rien
tableau déjà trié de petite taille : les algorithmes travaillent mais ne doivent rien faire
tableau trié à l’envers : parfois donne les cas limites
tableau non trié

A vous :

En utilisant le code de l’algorithme cid-dessous, créez les 4 tests proposés

vérifiez que vos tests sont bien ok en :

ajoutant un test qui plante

modifiant l’algorithme pour qu’il ne trie plus


def selection(tab):
    for i in range(len(tab) - 1):
        min_index = i
        for j in range(i + 1, len(tab)):
            if tab[j] < tab[min_index]:
                min_index = j

        tab[i], tab[min_index] = tab[min_index], tab[i]

Quelques règles :

un tri doit être reproductible. On n’utilise donc pas le hasard dans les tests (le tableau ne doit pas être mélangé par shuffle par exemple). Sinon un bug peut apparaitre de façon aléatoire.

pas trop de tests. Mais si on est pas sur, autant le rajouter. On pourra toujours l’enlever plus tard. Ici, est ce que tester des tableau avec des égalités à un sens ?

preuve du programme

Exemple pris d’un td sur le code de césar. Les tests permettent :

aux élèves de chercher à comprendre un bout de code : on donne le code d’une fonction et on demande aux élèves d’écrire les tests pour comprendre le fonctionnement.
aux enseignant de vérifier que le code produit par les élèves marche juste en exécutant les tests (code de césar)

La suite du td demande de lier les deux parties (plus le décodage) dans un programme principal de codage/décodage.

compréhension du code : exemple de la suppression d’accent

Il est parfois utile se supprimer tous les accent d’un texte pour avoir moins de lettres différentes.

On utilise pur cela un truc unicode, la normalisation ‘NFD’. En unicode, les caractères accentués peuvent s’écrire sous deux formes : soit la glyphe é soit une combinaison de glyphes : la glyphe e suivie de la glyphe d’accent '.

Dans un texte en français, la lettre de base est une lettre présente dans le code ascii, mais pas l’accent. En transformant alors un texte français normalisé en NFD en ascii on supprime les caractères qu’il ne connait pas, donc tous les accents.

Exemple de la transformation :

import unicodedata

s = "éçà ü ?"
print(s)
s2 = unicodedata.normalize('NFD', s)
print(s2)  # pas de différence, c'est toujours de l'utf-8 par encodé différemment
s3 = s2.encode('ascii', 'ignore')
print(s3)  # c'est du bytes maintenant
s_sans_accent = s3.decode('utf-8')
print(s_sans_accent)  # de l'utf-8 sans accent

A VOUS :

testez le bout de code ci-dessus

créez une fonction (dans transformations.py) que vous nommerez sans_accent qui prend un texte en paramètre et le rend sans accent

testez la fonction sans_accent en vérifiant qu’une chaine avec accent est bien transformée en une chaine sans accent.

créez une fonction (dans transformations.py) que vous nommerez majuscules_sans_accent qui prend un texte en paramètre et le rend sans accent et en majuscule (méthdoe upper des listes)

testez la fonction majuscules_sans_accent.

production de fonction testés : exemple du code de César

Cette façon de coder des messages très ancienne, César l’aurait utilisée, repose sur une substitution monoalphabétique particulière, c’est à dire remplacer une lettre de l’alphabet par une autre.

Le principe en est simple, chaque lettre de l’alphabet possède une valeur de 1 à 26 (A vaut 1, B vaut 2, …, Z vaut 26), que l’on code en lui rajoutant une constante modulo 26.

On a alors coutume de considérer que la clé permettant de coder le texte est la lettre correspondant au codage de ‘A’. Ainsi, l’ajout de la constante 4 correspond à la clé ‘E’, comme le montre la table suivante :

clé E
initiale :	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
codée :	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D

Le texte "LE VENDREDI C'EST ALGORITHMIE" devient alors "PI ZIRHVIHM G'IWX EPKSVMXLQMI" avec "E" comme clé (les caractères qui ne sont pas des majuscules sont ignorées dans le codage).

A VOUS :

Dans cesar.py, créez une fonction que vous appellerez code_cesar qui prend une lettre en majuscule en paramètre (le code) et rend un dictionnaire dont les clés sont les lettres en majuscules et la valeur l’encodage de cette lettre selon le code donné en paramètre.

testez votre méthode. Elle doit rendre {'A': 'E', 'B': 'F', 'C': 'G', 'D': 'H', 'E': 'I', 'F': 'J', 'G': 'K', 'H': 'L', 'I': 'M', 'J': 'N', 'K': 'O', 'L': 'P', 'M': 'Q', 'N': 'R', 'O': 'S', 'P': 'T', 'Q': 'U', 'R': 'V', 'S': 'W', 'T': 'X', 'U': 'Y', 'V': 'Z', 'W': 'A', 'X': 'B', 'Y': 'C', 'Z': 'D'} pour un paramètre valant 'E'.

refactoring

Une fois qu’une fonction est crée et testée, il est aisé de la modifier sans la casser. Ceci est particulièrement utile pour séparer un algorithme compliqué en plusieurs parties plus simple.

En cours, cela permet aux élèves d’avoir une compréhension plus fine de l’algorithme – souvent décrit en un seul tenant dans les livre et sur wikipédia – en le découpant en parties fonctionnelles.

Exemple du tri par sélection. Ce tri effectue 2 sous-tâches pour fonctionner : * recherche du minimum * échange de deux valeurs.

Nous allons extraire ces deux sous-fonctions. Comme notre méthode de tri est testé, on saura tout de suite si cela rate ou pas.

extraction de l’échange

A vous : Vérifiez régulièrement en exécutant vos tests que tout fonctionne encore.

Créez une méthode nommée échange qui à partir d’un tableau et de deux indices, les échange.

testez là

remplacez l’échange dans le tri par sélection par la nouvelle fonction

extraction du minimum.

A vous : Vérifiez régulièrement en exécutant vos tests que tout fonctionne encore.

Créez une méthode nommée min_indice_tableau qui à partir d’un tableau et d’un indice, rend l’indice du plus petti élément.

testez là

remplacez l’échange dans le tri par sélection par la nouvelle fonction

création par les tests

Partie la plus difficile mais également la plus utile et gratifiante une fois qu’on l’a comprise et qu’on l’utilise. On peut créer un algorithme ou un programme compliqué juste avec des tests. En ajoutant petit à petit de la complexité dans l’algorithme sans le casser (puisque les tests passent). L’exemple que l’on va utiliser est simple, mais cela fonctionne admirablement bine avec des problèmes bien plus compliqué dont, souvent, on a pas la bonne réponse immédiatement.

Exemple de la recherche dichotomique : un algorithme permettant de déterminer, par dichotomie, si un nombre est présent dans une liste d’entier trié :

il rend False si l’entier recherché n’est pas dans la liste
il rend True s’il est présent.

En cours : On pourra exécuter les différentes parties petit à petit et voir l’évolution

La boucle de production est la suivante :

vous écrivez un test que doit vérifier l’algorithme (un exemple)
on exécute les tests et on voit que le teste plante
on écrit le bout de code qui permet au test de fonctionner
on exécute les tests et on voit que le teste réussi !
retour en 1.

Comme on connait comment doit fonctionner la dichotomie, on va procéder en suivant ses étapes de fonctionnement

Programme final : dichotomie.py

départ : 0 et 1 élément

Vous pommencez par un algorithme vide. Il prend en entrée un element et une liste et rend None.


def dichotomie(element, tableau):
    return False

1er test : un element et tableau vide.

def dichotomie(element, tableau):
    return False
    
def test_vide():
    assert False == dichotomie(7, [])

Les tests passent.

2ème test : un élément et tableau de 1 élément ne le contient pas.

def dichotomie(element, tableau):
    return False
    
def test_vide():
    assert False == dichotomie(7, [])    

def test_un_element_pas_dedant():
    assert False == dichotomie(7, [1])

Les tests passent.

3ème test : un élément et tableau de 1 élément le contient.

def dichotomie(element, tableau):
    return False
    
def test_vide():
    assert False == dichotomie(7, [])    

def test_un_element_pas_dedant():
    assert False == dichotomie(7, [1])    

def test_un_element_dedant():
    assert True == dichotomie(7, [7])

Les tests ne passent plus.

On corrige le code pour que :

si le tableau est vide ça réponde False
si le tableau contient 1 élément ça répond True si l’élément est dans le tableau et False sinon

def dichotomie(element, tableau):
    if len(tableau) < 1:
        return False
    elif len(tableau) == 1:
        return element == tableau[0]
    return False

Les tests repassent.

plusieurs éléments

cas impair : le bon élément est au milieu

Les tests ajoutés :

def test_un_element_milieu():
    assert True == dichotomie(7, [2, 7, 12])

Les tests ne passent plus. On ajoute le cas impair.

def dichotomie(element, tableau):
    if len(tableau) < 1:
        return False
    elif len(tableau) == 1:
        return element == tableau[0]
    elif len(tableau) % 2 == 1:
        if element == tableau[len(tableau) // 2]:
            return True
    return False

Le cas 1 devient un cas particulier du cas impair. On refactorise :

def dichotomie(element, tableau):
    if len(tableau) < 1:
        return False
    elif len(tableau) % 2 == 1:
        if element == tableau[len(tableau) // 2]:
            return True
    return False

La refactorisation est aisée puisque l’on sait immédiatement si l’on s’est trompé (les tests plante) ou pas (les tests réussissent). On a plus peur de modifier son code !

cas impair : le bon élément n’est pas au milieu

On ajoute la récursion.

les tests ajoutés :

def test_element_pas_milieu_dessous_ok():
    assert True == dichotomie(2, [2, 7, 12])    
    
def test_element_pas_milieu_dessus_ok():
    assert True == dichotomie(12, [2, 7, 12])    

def test_element_pas_milieu_dessus_pas_ok():
    assert False == dichotomie(0, [2, 7, 12])

Le code :

def dichotomie(element, tableau):
    if len(tableau) < 1:
        return False
    elif len(tableau) % 2 == 1:
        if element == tableau[len(tableau) // 2]:
            return True
        elif element < tableau[len(tableau) // 2]:
            return dichotomie(element, tableau[:len(tableau) // 2])
        else:
            return dichotomie(element, tableau[len(tableau) // 2 + 1:])
    return False

On a accéléré le temps ici, puisque le code n’est pas arrivé de suite. Il y a eu plein d’erreurs avant de se rendre compte qu’il fallait ajouter le +1par exemple. Mais c’est allé vite car l’erreur ne pouvait venir que de ce qu’on a ajouté, c’est à dire 1 ligne.

cas pair

Les tests :

def test_element_pair_dessous_ok():
    assert True == dichotomie(2, [2, 12])    
    
def test_element_pas_milieu_dessus_ok():
    assert True == dichotomie(12, [2, 12])    

def test_element_pas_milieu_dessus_pas_ok():
    assert False == dichotomie(0, [2, 12])

Le code :

def dichotomie(element, tableau):
    if len(tableau) < 1:
        return False
    elif len(tableau) % 2 == 1:
        if element == tableau[len(tableau) // 2]:
            return True
        elif element < tableau[len(tableau) // 2]:
            return dichotomie(element, tableau[:len(tableau) // 2])
        else:
            return dichotomie(element, tableau[len(tableau) // 2 + 1:])
    else :
        if element == tableau[len(tableau) // 2]:
            return True
        elif element < tableau[len(tableau) // 2]:
            return dichotomie(element, tableau[:len(tableau) // 2])
        else:
            return dichotomie(element, tableau[len(tableau) // 2 + 1:])    
    return False

refactorisation finale

Le cas pair ressemble trop au cas impair. On unifie les 2.

def dichotomie(element, tableau):
    if len(tableau) < 1:
        return False

    if element == tableau[len(tableau) // 2]:
        return True
    elif element < tableau[len(tableau) // 2]:
        return dichotomie(element, tableau[:len(tableau) // 2])
    else:
        return dichotomie(element, tableau[len(tableau) // 2 + 1:])

On place un dernier test avec plus de 10 éléments, pour avoir bonne conscience :

def test_gros():
    assert True == dichotomie(18, list(range(20)))
    assert False == dichotomie(-3, list(range(20)))