Informatique · du code qu’un correcteur peut lire

1. Trouve une quantité entière, positive ou nulle à chaque tour, qui décroît strictement à chaque itération.
2. Justifie ces deux propriétés à partir du corps de la boucle.
3. Conclus : une suite d’entiers naturels strictement décroissante est finie, donc la boucle s’arrête.

Exemple résolu. Algorithme d’Euclide sur deux entiers naturels (tant que b ≠ 0 : a, b = b, a % b). b est un entier naturel, et le nouveau b, reste de la division par l’ancien b, lui est strictement inférieur. La boucle termine.

Le piège. Proposer une quantité qui décroît mais peut devenir négative, ou qui n’est pas entière : ce n’est pas un variant.

1. Énonce une propriété vraie avant la boucle et conservée par chaque tour.
2. Montre l’initialisation, puis la conservation : si elle est vraie au début d’un tour, elle l’est à la fin.
3. À la sortie, combine l’invariant et la condition d’arrêt pour obtenir le résultat voulu.

Exemple résolu. Recherche dichotomique de x dans une liste triée t, avec g = 0 et d = len(t) − 1 au départ : invariant « si x est dans t, il est dans t[g..d] ». Chaque tour le conserve parce que t est triée ; à la sortie (g > d), la tranche est vide, donc x n’est pas dans t.

Le piège. Choisir un invariant qui ne dit rien à la sortie : avec la condition d’arrêt, il doit donner exactement le résultat.

1. Écris la relation de récurrence du coût : nombre d’appels, taille des sous-problèmes, coût du travail hors appels.
2. Cas à connaître : C(n) = C(n/2) + O(1) donne O(log n) ; C(n) = 2C(n/2) + O(n) donne O(n log n) ; C(n) = C(n − 1) + O(n) donne O(n²) ; C(n) = 2C(n − 1) + O(1) donne O(2ⁿ).
3. Compte le coût caché des opérations Python : une tranche t[a:b] copie b − a éléments.

Exemple résolu. Le tri fusion coupe la liste en deux, trie chaque moitié et fusionne en temps linéaire : C(n) = 2C(n/2) + O(n), soit O(n log n). Une recherche dichotomique qui passe t[:m] à l’appel suivant coûte O(n) et non O(log n), à cause des copies.

Le piège. Ignorer le coût des copies ou des concaténations dans les appels récursifs.

1. Définis précisément le sous-problème et ses paramètres, par exemple L[i][j] = longueur de la plus longue sous-suite commune à u[:i] et v[:j].
2. Écris la relation de récurrence et les cas de base.
3. Remplis le tableau dans un ordre où chaque case ne dépend que de cases déjà calculées ; la complexité vaut le nombre de cases multiplié par le coût d’une case.

Exemple résolu. Plus longue sous-suite commune : L[i][j] = L[i−1][j−1] + 1 si u[i−1] = v[j−1], sinon max(L[i−1][j], L[i][j−1]), avec L[0][j] = L[i][0] = 0. Pour des mots de longueurs n et m : O(nm) en temps et en mémoire.

Le piège. Écrire la récurrence sans définir exactement ce que contient une case : c’est là que naissent les décalages d’indice.

1. Parcours en largeur (file) : distances en nombre d’arêtes dans un graphe non pondéré, en O(n + m).
2. Parcours en profondeur (pile ou récursion) : composantes connexes, détection de cycle, tri topologique.
3. Algorithme de Dijkstra (file de priorité) : plus courts chemins pour des poids positifs ou nuls, en O((n + m) log n) avec un tas.

Exemple résolu. Nombre minimal de coups d’un cavalier entre deux cases d’un échiquier : le graphe (cases, coups possibles) n’est pas pondéré, donc un parcours en largeur depuis la case de départ donne la réponse.

Le piège. Utiliser Dijkstra avec des poids négatifs, ou un parcours en profondeur pour chercher des plus courts chemins.

1. L’affectation b = a ne copie pas une liste : a et b désignent le même objet.
2. [[0] * m] * n crée n références vers la même ligne ; écris [[0] * m for _ in range(n)].
3. Une fonction qui modifie une liste reçue en argument la modifie aussi pour l’appelant : copie-la d’abord si ce n’est pas voulu.

Exemple résolu. t = [[0] * 3] * 2 puis t[0][0] = 1 donne [[1, 0, 0], [1, 0, 0]] : les deux lignes sont le même objet.

Le piège. Croire que t.copy() copie aussi les sous-listes : c’est une copie superficielle.

1. FROM et JOIN … ON construisent la table de travail, avec la condition de jointure.
2. WHERE filtre les lignes avant le regroupement ; GROUP BY forme les groupes ; HAVING filtre les groupes selon un agrégat.
3. SELECT ne contient que les colonnes du GROUP BY et des agrégats : COUNT, SUM, AVG, MIN, MAX.

Exemple résolu. Élèves ayant au moins trois notes strictement supérieures à 15 : SELECT id_eleve, COUNT(*) FROM notes WHERE note > 15 GROUP BY id_eleve HAVING COUNT(*) >= 3.

Le piège. Mettre une condition sur un agrégat dans WHERE : WHERE COUNT(*) >= 3 est refusé, c’est le rôle de HAVING.