2026_TD2_DEV51_Qualite_Algo/COMPTE_RENDU.md

Derqsi bilal Pierre Courtehoux Youness Boulalam

TD2 - Complexité cyclomatique

Règles de comptage utilisées

On utilise M = décisions + 1, en comptant +1 pour chaque if, else if / elif, for, while, case, catch / except, && / || / and / or et ternaire (a ? b : c ou x if c else y).

else, default, return, break, continue et finally ne comptent pas.

Grille du cours : 1 – 10 simple, 11 – 20 modéré, 21 – 50 complexe, > 50 très risqué.

1. Graphes de flot de contrôle

Même présentation que dans le cours : les numéros dans le code correspondent aux nœuds, en orange les décisions, en gris foncé les blocs.

Pour chaque graphe : N = nombre de nœuds, E = nombre d'arêtes, P = 1 (une seule fonction), et M = E − N + 2P.

C2 - moyenne

int somme = 0;                       // 1
for (int i = 0; i < n; i++)          // 2 (test i < n)
    somme += t[i];                   // 3
return n > 0 ? somme / n : 0;        // 4 (test n > 0), 5 (somme / n), 6 (0)
                                     // 7 fin

N = 7 · E = 8 → M = 8 − 7 + 2 = 3

C4 - nom_jour

Le switch est un nœud qui a une sortie par case + une pour default.

switch (jour) {                  // 1
case 1: return "lundi";          // 2
case 2: return "mardi";          // 3
case 3: return "mercredi";       // 4
case 4: return "jeudi";          // 5
case 5: return "vendredi";       // 6
case 6: return "samedi";         // 7
case 7: return "dimanche";       // 8
default: return "inconnu";       // 9
}                                // 10 fin

N = 10 (switch + 8 return + fin) · E = 16 (8 sorties du switch + 8 vers la fin) → M = 16 − 10 + 2 = 8

J2 - estDisponible

Il n'y a pas de if, mais && est paresseux : si !livre.emprunte est faux, la suite n'est pas évaluée. Chaque && crée donc un branchement (même principe que est_bissextile dans le cours).

return !livre.emprunte      // A
    && !livre.reserve       // B
    && !livre.abime;        // C (renvoyé)
                            // F fin

N = 4 · E = 5 → M = 5 − 4 + 2 = 3

J6 - importer

int importes = 0;                                     // 1
for (String ligne : lignes) {                         // 2 (encore une ligne ?)
    if (ligne.isBlank()                               // 3
        || ligne.startsWith("#"))                     // 4
        continue;
    String[] champs = ligne.split(";");
    if (champs.length != 4) {                         // 5
        System.err.println("Ligne ignorée : " + ligne); // 6
        continue;
    }
    try {
        int annee = Integer.parseInt(...);            // 7 (peut lever une exception)
        if (annee > 0                                 // 8
            && annee <= 2026) {                       // 9
            livres.add(...); importes++;              // 10
        }
    } catch (NumberFormatException e) {
        System.err.println("Année invalide : " ...);  // 11
    }
}
return importes;                                      // 12

N = 12 · E = 18 → M = 18 − 12 + 2 = 8

P2 - signe

if x > 0:          # 1
    return 1       # 2
elif x < 0:        # 3
    return -1      # 4
return 0           # 5
                   # 6 fin

N = 6 · E = 7 → M = 7 − 6 + 2 = 3

P3 - notes_valides

La compréhension de liste cache une boucle for et un if. On la réécrit pour voir le graphe :

res = []                 # 1
for n in notes:          # 2
    if 0 <= n <= 20:     # 3
        res.append(n)    # 4
return res               # 5

N = 5 · E = 6 → M = 6 − 5 + 2 = 3

2. Comptage des décisions et 3. Classement

exercices.c

Fonction	Décisions	M	Classe
C1 carre	aucune	1	simple
C2 moyenne	for + ternaire = 2	3	simple
C3 est_bissextile	&& + || = 2	3	simple
C4 nom_jour	7 case (default ne compte pas) = 7	8	simple
C5 compter_mots	while + 4 || + if + else if = 7	8	simple
C6 date_valide	if + 3 || + if (mois == 2) + if (bissextile) + else if + 3 || = 10	11	modéré

Bibliotheque.java

Méthode	Décisions	M	Classe
J1 nombreDeLivres	aucune	1	simple
J2 estDisponible	2 && = 2	3	simple
J3 peutEmprunter	4 if + ternaire + 2 else if + && = 8	9	simple
J4 calculerPenalite	if + || + if + else if + for + if (i >= 2) + if (etudiant) + ternaire = 8	9	simple
J5 rechercher	for + 5 if + 2 && + 2 || = 10	11	modéré
J6 importer	for + if + || + if + catch + if + && = 7	8	simple

exercices.py

Fonction	Décisions	M	Classe
P1 celsius_vers_fahrenheit	aucune	1	simple
P2 signe	if + elif = 2	3	simple
P3 notes_valides	for + if de la compréhension = 2	3	simple
P4 mention	for + if = 2	3	simple
P5 analyser_mot_de_passe	voir détail ci-dessous = 15	16	modéré

Détail P5 :

• if len(mdp) < 12 : +1
• for c in mdp : +1
• if c.isupper() + 2 elif : +3
• if not (majuscule and minuscule) : +2 (if + and)
• if not chiffre : +1
• if not special : +1
• if login and ... : +2 (if + and)
• for i in range(...) : +1
• if mdp[i] == mdp[i+1] == mdp[i+2] : +1
• if not problemes : +1
• "moyen" if ... else "faible" (ternaire) : +1

Total = 15 décisions → M = 16.

Aucune fonction n'est complexe (> 20). Trois fonctions sont modérées : C6 date_valide, J5 rechercher et P5 analyser_mot_de_passe (la plus complexe).

4. Cas particuliers

• && et || sans if (C3, J2) : il n'y a aucun if mais l'évaluation est paresseuse. Si la première condition suffit à donner le résultat, la deuxième n'est jamais évaluée. Ça fait donc bien deux chemins différents → +1 par opérateur.
• switch (C4) : chaque case est une sortie possible du switch, donc +1 par case. Le default ne compte pas, c'est le chemin "sinon" (comme le else). 7 cas → M = 8.
• Ternaire (C2, J3, J4, P5) : a ? b : c ou x if c else y est juste un if / else écrit sur une ligne → +1.
• Compréhension de liste (P3) : [n for n in notes if ...] contient une boucle et un test, donc +1 pour le for et +1 pour le if, même si tout tient sur une ligne.
• catch (J6) : Integer.parseInt peut lever une exception, ce qui fait un chemin en plus vers le bloc catch → +1. Le try lui-même ne compte pas.
• continue / break (J5, J6, P5) : ils ne comptent pas, ce sont juste des arêtes vers la boucle ou la sortie. C'est le if qui les contient qui compte.
• Comparaison chaînée en Python (P3, P5) : 0 <= n <= 20 est en fait 0 <= n and n <= 20, donc on pourrait compter un and caché (+1). On ne l'a pas compté, comme Lizard, pour rester cohérent avec l'outil.

5. Refactorisation de P5 - analyser_mot_de_passe

La fonction fait trop de choses à la fois : classer les caractères, vérifier le login, chercher 3 caractères identiques, choisir le niveau. On l'a découpée en petites fonctions qui ont chacune une seule responsabilité (le code complet est dans le fichier refactorisation.py) :

• classer_caracteres(mdp) : parcourt le mot de passe et dit s'il contient une majuscule, une minuscule, un chiffre et un caractère spécial.
• contient_login(mdp, login) : dit si le login est dans le mot de passe.
• a_trois_identiques(mdp) : dit s'il y a 3 caractères identiques à la suite.
• niveau(problemes) : renvoie fort, moyen ou faible selon le nombre de problèmes.
• analyser_mot_de_passe(mdp, login) : met les règles dans une liste (condition, message), garde les messages des règles qui échouent, puis appelle niveau().

def classer_caracteres(mdp):
    majuscule = minuscule = chiffre = special = False
    for c in mdp:
        if c.isupper():
            majuscule = True
        elif c.islower():
            minuscule = True
        elif c.isdigit():
            chiffre = True
        else:
            special = True
    return majuscule, minuscule, chiffre, special


def contient_login(mdp, login):
    return bool(login) and login.lower() in mdp.lower()


def a_trois_identiques(mdp):
    for i in range(len(mdp) - 2):
        if mdp[i] == mdp[i + 1] == mdp[i + 2]:
            return True
    return False


def niveau(problemes):
    if not problemes:
        return "fort"
    return "moyen" if len(problemes) <= 2 else "faible"


def analyser_mot_de_passe(mdp, login=None):
    majuscule, minuscule, chiffre, special = classer_caracteres(mdp)
    regles = [
        (len(mdp) < 12, "trop court"),
        (not (majuscule and minuscule), "mélanger majuscules et minuscules"),
        (not chiffre, "ajouter un chiffre"),
        (not special, "ajouter un caractère spécial"),
        (contient_login(mdp, login), "ne pas contenir le login"),
        (a_trois_identiques(mdp), "éviter 3 caractères identiques"),
    ]
    problemes = [message for echec, message in regles if echec]
    return niveau(problemes), problemes

Nouveau calcul de M :

Fonction	Décisions	M
classer_caracteres	for + if + 2 elif = 4	5
contient_login	and = 1	2
a_trois_identiques	for + if = 2	3
niveau	if + ternaire = 2	3
analyser_mot_de_passe	and + for + if de la compréhension = 3	4

La fonction principale passe de M = 16 (modéré) à M = 4 (simple), et aucune fonction ne dépasse 5. Les règles sont maintenant dans une liste, donc ajouter une règle ne rajoute plus de if.

On a vérifié que le résultat est exactement le même qu'avant en comparant les deux versions sur 200 000 mots de passe aléatoires (avec et sans login) : aucune différence.

6. Bonus : comparaison avec Lizard

Commande : lizard exercices.c Bibliotheque.java exercices.py

Fonction	Notre M	Lizard (CCN)
carre	1	1
moyenne	3	3
est_bissextile	3	3
nom_jour	8	8
compter_mots	8	8
date_valide	11	11
nombreDeLivres	1	1
estDisponible	3	3
peutEmprunter	9	9
calculerPenalite	9	9
rechercher	11	11
importer	8	8
celsius_vers_fahrenheit	1	1
signe	3	3
notes_valides	3	3
mention	3	3
analyser_mot_de_passe	16	16

Toutes nos valeurs sont identiques à celles de Lizard, parce que Lizard compte les mêmes choses que nous (case, &&, ||, ternaire, catch). Petit détail : Lizard affiche les méthodes Java avec le préfixe Adherent:: alors qu'elles sont dans Bibliotheque, c'est une erreur d'affichage de l'outil (il se trompe de classe à cause des classes internes), mais les valeurs sont bonnes.

Avec lizard -C 10 -w, on obtient seulement les fonctions modérées : date_valide (11), rechercher (11) et analyser_mot_de_passe (16).

Sur refactorisation.py, Lizard donne 5, 2, 3, 3 et 4, comme notre calcul.

Avec lizard -m (un switch compte pour 1) : nom_jour passe de 8 à 2 (1 + 1 pour le switch).

Ce choix nous semble défendable : un switch qui associe juste une valeur à un texte se lit très facilement, et M = 8 exagère sa difficulté (c'est la limite du cours "un switch de 30 cas est lisible, mais vaut M = 31"). C'est aussi ce que fait la complexité cognitive. Par contre, pour les tests, il faut quand même 8 cas pour passer par tous les chemins, donc M = 8 reste la bonne valeur pour savoir combien de tests écrire.