Bases de Python et recherche séquentielle

Résumé en cinq points

Objectifs du premier semestre

Le programme fixe cinq objectifs aux travaux pratiques du premier semestre.

• Consolider la programmation en Python commencée au lycée.
• Mettre en place un environnement de travail, un éditeur, un interpréteur, l'exécution d'un fichier et l'usage de la console.
• Mettre en place une discipline de programmation, spécification précise des fonctions, annotations et commentaires, jeux de tests.
• Introduire les premiers éléments de complexité. On ne présente que l'estimation asymptotique du coût dans le cas le pire.
• Introduire des outils de validation, variants et invariants. L'ordre des thèmes du semestre n'est pas imposé, et aucune connaissance sur les modules rencontrés en travaux pratiques n'est exigible.

Traits généraux du langage Python

Typage dynamique

L'interpréteur détermine le type d'une valeur à la volée, au moment de l'exécution. On n'écrit donc pas de déclaration de type, et une même variable peut désigner successivement un entier puis une chaîne. La contrepartie est qu'une erreur de type n'apparaît qu'à l'exécution de la ligne fautive. D'où l'intérêt, demandé par le programme, de préciser la signature de chaque fonction en commentaire, types attendus en entrée et type renvoyé.

Principe d'indentation

En Python, les blocs d'instructions, corps d'une boucle, d'une fonction ou d'une conditionnelle, sont délimités par l'indentation, conventionnellement quatre espaces, après une ligne terminée par deux-points. Changer l'indentation change le sens du programme. Une instruction return décalée d'un cran vers la gauche sort de la boucle, et c'est une source d'erreurs fréquente dans les recherches séquentielles.

Portée lexicale

Quand une expression à l'intérieur d'une fonction fait référence à une variable, Python cherche d'abord la valeur définie à l'intérieur de la fonction, puis, à défaut, la valeur dans l'espace global du module. Une variable affectée dans une fonction est locale à cette fonction. Elle disparaît à la fin de l'appel et ne modifie pas une variable globale de même nom.

Appel de fonction par valeur

L'exécution de f(x) évalue d'abord l'argument x, puis exécute le corps de f avec la valeur calculée. Pour une liste, la valeur transmise désigne la liste elle-même et non une copie. Une fonction qui modifie une case de la liste reçue modifie donc la liste de l'appelant. Réaffecter le paramètre, en revanche, ne change rien pour l'appelant.

Types de base

Entiers et flottants

Sur les entiers, type int, les opérations exigibles sont l'addition, la soustraction, la multiplication, la division entière //, l'exponentiation ** et le reste %, avec des opérandes positifs. Par exemple 17 // 5 vaut 3 et 17 % 5 vaut 2. Les entiers de Python ne débordent pas, leur taille s'adapte.

Sur les flottants, type float, on dispose de +, −, *, / et **. La division / renvoie toujours un flottant, 6 / 3 vaut 2.0. Les flottants sont des approximations, 0.1 + 0.2 == 0.3 est faux. On y reviendra au chapitre sur la représentation des nombres, mais le réflexe est dès maintenant de ne jamais tester l'égalité de deux flottants.

Booléens et comparaisons

Le type bool a deux valeurs, True et False, et trois opérations, not, and, or. Les opérateurs and et or sont paresseux. Dans a and b, si a est faux, b n'est pas évalué. Cela permet d'écrire i < len(t) and t[i] != x sans risque de sortir du tableau. Les comparaisons exigibles sont ==, !=, <, >, <=, >=.

Types structurés

Chaînes et tuples, structures indicées immuables

Les chaînes de caractères et les tuples sont des structures indicées immuables. On y accède par indice positif valide, de 0 à len(s) − 1, on les concatène avec +, on les répète avec *, on en extrait une tranche avec s[i:j], qui contient les éléments d'indices i inclus à j exclu. Immuable signifie qu'on ne peut pas modifier une case. Pour « changer » une chaîne, on en construit une nouvelle.

Listes

Les listes sont des tableaux dynamiques mutables. Les constructions exigibles sont la compréhension [e for x in s], la répétition [e] * n et les append successifs. On dispose de len, de l'accès et de la modification par indice positif valide, de la concaténation +, de l'extraction de tranche, de la copie et de pop en dernière position.

Le point délicat est la copie. L'affectation m = t ne copie rien, m et t désignent la même liste, et modifier m[0] modifie t[0]. Une tranche t[:] fabrique une nouvelle liste, mais cette copie est superficielle. Pour une liste de listes, les sous-listes restent partagées. C'est aussi pourquoi [[0] * 3] * 2 est un piège, les deux lignes sont la même liste, alors que [[0] * 3 for i in range(2)] crée deux lignes distinctes.

Dictionnaires

Un dictionnaire associe des valeurs à des clés. Création {c1: v1, c2: v2}, accès d[c], insertion ou modification d[c] = v, test de présence c in d, nombre d'associations len(d), copie d.copy(). Au premier semestre, le programme demande de les utiliser en boîte noire, sans connaître leur fonctionnement interne, en retenant que l'accès, l'insertion et le test de présence ont un coût constant en pratique. Le principe du hachage, qui explique ce coût et les restrictions sur les clés, est vu en deuxième année.

Structures de contrôle

Affectation et dépaquetage de tuples

L'affectation se fait avec =. Le dépaquetage permet d'affecter plusieurs variables d'un coup, a, b = b, a échange deux valeurs, et c'est une façon sûre d'écrire une mise à jour simultanée.

Instruction conditionnelle

if, elif, else. Les branches sont testées dans l'ordre et une seule est exécutée. Un elif n'est examiné que si toutes les conditions précédentes étaient fausses.

Boucles while et for

La boucle while répète son corps tant que sa condition est vraie. Elle convient quand on ne connaît pas à l'avance le nombre de tours. La boucle for parcourt range(a, b), c'est-à-dire les entiers de a inclus à b exclu, une chaîne, un tuple, une liste, ou un dictionnaire à travers ses méthodes keys et items. Les instructions break et return dans le corps d'une boucle en sortent immédiatement. La forme else d'une boucle n'est pas au programme.

Définition d'une fonction

def f(p1, …, pn) introduit une fonction, return termine son exécution et renvoie une valeur. Une fonction sans return renvoie la valeur spéciale None. On sépare toujours le calcul, dans une fonction qui renvoie un résultat, de l'affichage avec print, qu'on utilise sans paramètre facultatif. Les commentaires commencent par #, et le programme demande qu'ils éclairent le code sans le paraphraser.

Recherche séquentielle dans un tableau unidimensionnel

Recherche d'un élément

Problème. Étant donné une liste t et une valeur x, dire si x apparaît dans t. L'algorithme séquentiel parcourt les cases dans l'ordre et s'arrête dès qu'il trouve x.

def appartient(t, x):
    # t : list, x : valeur quelconque. Renvoie True si x est un élément de t.
    for y in t:
        if y == x:
            return True
    return False

Le return False est après la boucle, au niveau de la définition. Placé dans la boucle, il ferait conclure dès la première case différente de x. Variante utile, renvoyer l'indice de la première occurrence, ou −1 si x est absent, avec une boucle sur range(len(t)).

Version avec une boucle while, qui renvoie l'indice. On avance tant qu'on n'a ni dépassé la fin ni trouvé x.

def indice(t, x):
    # renvoie le plus petit i tel que t[i] == x, ou -1 si x n'est pas dans t
    i = 0
    while i < len(t) and t[i] != x:
        i = i + 1
    if i < len(t):
        return i
    return -1

L'ordre des deux conditions compte. Grâce au caractère paresseux de and, t[i] n'est jamais lu quand i vaut len(t). Écrites dans l'autre ordre, elles provoqueraient une erreur d'indice quand x est absent. La terminaison se justifie par un variant, len(t) − i, entier positif qui diminue de 1 à chaque tour.

Coût. Dans le cas le pire, x absent ou en dernière position, on fait n comparaisons pour une liste de longueur n. Le coût est linéaire. Dans le meilleur cas, x en première position, il est constant, mais le programme ne s'intéresse qu'au pire cas.

Recherche du maximum et du second maximum

Maximum d'une liste non vide. On garde dans une variable m le plus grand élément vu jusqu'ici.

def maximum(t):
    # t : liste non vide de nombres. Renvoie le plus grand élément.
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

Invariant de boucle. Après le traitement des k premiers éléments, m est le maximum de ces k éléments. Il est vrai avant la boucle avec k = 1, et chaque tour le conserve. À la fin, k = n, donc m est le maximum de t. Le coût est linéaire, exactement n comparaisons.

Second maximum. Il faut d'abord fixer la convention. Ici, c'est la deuxième valeur de la liste triée par ordre décroissant, doublons compris, donc le second maximum de [5, 5, 3] est 5. On garde deux variables m1 ≥ m2, les deux plus grandes valeurs vues. Pour chaque nouvel élément x, si x > m1, l'ancien m1 devient m2 et x devient m1. Sinon, si x > m2, x devient m2. On initialise avec les deux premiers éléments rangés dans le bon ordre, ce qui suppose au moins deux éléments. Un seul parcours suffit, le coût reste linéaire. L'erreur classique est d'oublier de faire descendre l'ancien maximum en m2.

Comptage des éléments à l'aide d'un dictionnaire

Pour compter les occurrences de chaque valeur d'une liste, on parcourt la liste et on tient un dictionnaire dont les clés sont les valeurs rencontrées et les valeurs leurs effectifs.

def effectifs(t):
    d = {}
    for x in t:
        if x in d:
            d[x] = d[x] + 1
        else:
            d[x] = 1
    return d

Chaque tour de boucle fait un test de présence et une insertion, de coût constant en pratique. Le coût total est donc linéaire. Sans dictionnaire, compter les occurrences de chaque valeur en appelant une recherche séquentielle pour chacune coûterait de l'ordre de n², coût quadratique. C'est le premier exemple où le choix de la structure de données change l'ordre de grandeur du coût.

Coût constant et coût linéaire

Le coût d'un algorithme est le nombre d'opérations élémentaires qu'il effectue, exprimé en fonction de la taille n de l'entrée, dans le cas le pire et en ordre de grandeur. Un coût est constant s'il est borné indépendamment de n, et linéaire s'il est de l'ordre de n.

Coûts à connaître pour les listes de Python. Constant, len(t), l'accès et la modification t[i], append, pop en dernière position. Linéaire en la taille concernée, x in t, la copie, la concaténation, l'extraction d'une tranche. Pour les dictionnaires, accès, insertion et test de présence sont constants en pratique.

Exemple, détecter si une liste contient deux éléments égaux. Méthode naïve, comparer chaque élément à tous les suivants, soit de l'ordre de n²/2 comparaisons, coût quadratique. Méthode avec un dictionnaire, parcourir la liste une seule fois en enregistrant chaque valeur vue, et s'arrêter dès qu'une valeur est déjà présente, coût linéaire. Pour une liste d'un million d'éléments, la première méthode fait de l'ordre de cinq cents milliards de comparaisons, la seconde un million d'opérations.

Conséquence pratique, un x in t dans une boucle de n tours n'est pas une opération élémentaire. Il cache une boucle, et le coût total devient quadratique. Lire le coût d'un programme, c'est repérer ces boucles cachées.

Méthodes

• Écrire la signature et la spécification en commentaire avant le corps de la fonction, types d'entrée, type de sortie, cas particuliers comme la liste vide.
• Pour une recherche, se demander où placer le return du cas « non trouvé ». Presque toujours après la boucle.
• Pour un calcul de maximum ou de comptage, énoncer l'invariant en une phrase, « m est le maximum des éléments déjà vus ».
• Tester à la main sur trois cas, un cas général, un cas limite comme la liste à un élément, et un cas où la réponse est négative.
• Pour estimer un coût, compter les tours de boucle et repérer les opérations qui cachent une boucle, in sur une liste, copie, concaténation, tranche.
• N'utiliser que les éléments de l'annexe. Toute autre fonction, max, sorted, index, doit être accompagnée de sa documentation dans un sujet, et on ne peut pas s'en servir pour éviter d'écrire l'algorithme demandé.

Ce qu'il faut savoir refaire en khôlle

1. Écrire sans erreur une fonction de recherche d'un élément, en version booléenne puis en version qui renvoie un indice, et justifier la place de chaque return.
2. Écrire la recherche du maximum avec son invariant, puis celle du second maximum en un seul parcours, en précisant la convention sur les doublons.
3. Compter les occurrences des éléments d'une liste avec un dictionnaire, et comparer au coût d'une méthode sans dictionnaire.
4. Expliquer ce qu'affiche un programme qui fait m = t puis modifie m, puis le même avec m = t[:], et le cas d'une liste de listes.
5. Donner le coût dans le pire cas d'un petit programme en repérant les opérations de coût linéaire.
6. Expliquer la portée d'une variable affectée dans une fonction et l'effet d'une fonction qui modifie une liste reçue en paramètre.

Les résultats à connaître

En informatique, les « résultats » sont le comportement exact du langage, la correction des algorithmes et leur coût dans le pire cas.

• L'affectation m = t sur une liste ne copie rien, m et t désignent la même liste : exigible, à savoir illustrer.
• Une tranche t[:] est une copie superficielle, les sous-listes restent partagées : exigible, à savoir illustrer.
• Appel par valeur : une fonction qui modifie une case de la liste reçue modifie celle de l'appelant, une réaffectation du paramètre ne la modifie pas : exigible.
• Portée lexicale : une variable affectée dans une fonction est locale à cette fonction : exigible.
• and et or sont paresseux, le second opérande n'est évalué que si c'est nécessaire : exigible.
• La recherche séquentielle renvoie True si et seulement si x est un élément de t : exigible avec justification par invariant.
• La version while termine, avec le variant len(t) − i : exigible avec justification.
• La recherche séquentielle fait au plus n comparaisons, soit un coût linéaire dans le pire cas : exigible.
• Le calcul du maximum est correct, par l'invariant « m est le maximum des éléments déjà vus » : exigible avec justification.
• Le second maximum se calcule en un seul parcours, à convention fixée sur les doublons : exigible avec justification.
• Le comptage par dictionnaire est de coût linéaire : exigible, en admettant le coût constant des opérations de dictionnaire (boîte noire).
• Coûts des listes, constant pour len, t[i], append et pop en dernière position, linéaire pour in, la copie, la concaténation et la tranche : exigible sans démonstration.
• Hors programme signalé : indices négatifs, forme else d'une boucle, méthodes index, count et sort, fonctions max et sorted sans documentation, hachage (deuxième année), coût en moyenne ou dans le meilleur cas comme objet d'étude.

Clés de démonstration

Recherche booléenne. On montre qu'au début du tour qui examine la case d'indice i, x n'est dans aucune des cases 0 à i − 1. C'est vrai au départ, car on n'a encore rien examiné. Un tour qui ne sort pas conserve la propriété. Si la boucle s'achève, x n'est dans aucune case, donc False est juste. L'astuce est de relier chaque return à une phrase logique : « trouvé » pour le premier, « absent de toutes les cases » pour le second.

Recherche avec while. Invariant : x n'apparaît pas dans t[0:i]. Variant : len(t) − i, entier positif qui décroît de 1 à chaque tour. À la sortie, soit i = len(t) et x est absent, soit t[i] = x et i est le plus petit indice possible grâce à l'invariant. L'astuce est l'ordre des conditions, sans lequel l'invariant ne sert à rien puisque le programme plante.

Maximum. L'invariant porte sur les k premiers éléments. L'initialisation par t[0] rend l'invariant vrai dès le départ. L'astuce est de ne jamais initialiser par 0, qui n'est pas un élément de la liste.

Second maximum. L'invariant est « m1 et m2 sont les deux plus grandes valeurs, doublons compris, parmi les éléments vus, avec m1 ≥ m2 ». Quand x dépasse m1, l'ancien m1 devient le deuxième plus grand. Quand x est entre m2 et m1, seul m2 change. L'astuce est de traiter les trois cas x > m1, m2 < x ≤ m1 et x ≤ m2, et de vérifier que chacun conserve l'invariant.

Comptage. Invariant : les clés de d sont exactement les valeurs apparues dans les k premiers éléments, et d[v] est le nombre d'occurrences de v parmi eux. L'astuce est de séparer « v déjà vu » et « v nouveau », car d[v] n'existe pas encore dans le second cas.

Coût. On multiplie le nombre de tours par le coût du corps de boucle. L'astuce est de lire chaque instruction du corps et de se demander si elle cache une boucle.

Exemples et contre-exemples à connaître

1. [[0] * 3] * 2 crée deux références vers la même ligne. Modifier une case change les deux lignes. C'est le piège de toute matrice construite trop vite.
2. Un return False placé dans la boucle fait renvoyer False à appartient([1, 2], 2). La fonction ne regarde que la première case.
3. while t[i] != x and i < len(t) provoque une erreur d'indice quand x est absent. L'ordre des conditions n'est pas cosmétique.
4. Un maximum initialisé à 0 renvoie 0 pour [−3, −1]. La valeur renvoyée n'est même pas un élément de la liste.
5. Le second maximum de [5, 5, 3] vaut 5 ou 3 selon la convention. Un énoncé ambigu doit être tranché par écrit.
6. appartient([0.1 + 0.2], 0.3) renvoie False. La recherche d'un flottant par == est fragile.
7. t.append(x) dans une fonction modifie la liste de l'appelant, mais t = t + [x] ne la modifie pas. Mutation et réaffectation n'ont pas le même effet.
8. Une fonction qui affiche un résultat avec print sans le renvoyer donne None à l'appelant. print(f(t)) affiche alors None.
9. s[0] = "a" sur une chaîne provoque une erreur. Les chaînes sont immuables, on en fabrique une nouvelle.
10. if x in t dans une boucle sur t coûte de l'ordre de n². Une ligne d'apparence élémentaire peut rendre un programme quadratique.

Techniques du chapitre

Technique 1, spécifier avant d'écrire. Mini-exercice : spécifier une fonction qui compte les nombres strictement positifs d'une liste. Réponse : entrée, une liste de nombres éventuellement vide. Sortie, un entier. Liste vide, on renvoie 0. Le compteur s'initialise donc à 0 et le cas vide est traité sans test particulier.

Technique 2, sortir dès que la réponse est connue. Mini-exercice : tester si t est croissante. On parcourt i dans range(len(t) - 1) et on renvoie False dès que t[i] > t[i + 1], puis True après la boucle. La borne len(t) − 1 évite de lire t[len(t)], et la liste vide donne True.

Technique 3, l'accumulateur et sa valeur initiale. Mini-exercice : quelle initialisation pour une somme, un compteur, un produit, un maximum ? Réponse : 0, 0, 1 et t[0]. La valeur initiale doit rendre l'invariant vrai avant le premier tour.

Technique 4, choisir entre parcours par valeurs et par indices. Mini-exercice : on veut l'indice du premier nombre négatif. Un for y in t ne donne pas l'indice, on écrit donc for i in range(len(t)) et on teste t[i] < 0. On garde le parcours par valeurs quand seules les valeurs comptent, il est plus lisible.

Technique 5, un dictionnaire comme mémoire des valeurs déjà vues. Mini-exercice : savoir en un parcours si une chaîne contient deux fois la même lettre. On tient un dictionnaire vus, on renvoie True dès qu'une lettre y figure, sinon on l'ajoute. Coût linéaire en la longueur de la chaîne.

Technique 6, chiffrer un coût. Mini-exercice : coût de for x in t: r = r + [x] ? Au tour k la concaténation recopie environ k éléments. Le total est de l'ordre de n²/2, donc quadratique, alors que r.append(x) donne un coût linéaire.

Technique 7, tracer à la main. Mini-exercice : suivre maximum sur [2, 7, 7, 1]. On écrit un tableau dont chaque ligne donne x puis m après le tour : 2 puis 2, 7 puis 7, 7 puis 7, 1 puis 7. On vérifie ainsi l'invariant et les cas d'égalité.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

def occurrences(t, x):
    # t : list, x : valeur. Renvoie le nombre d'indices i tels que t[i] == x.
    c = 0
    for y in t:
        if y == x:
            c = c + 1
    return c

def derniere(t, x):
    # renvoie le plus grand i tel que t[i] == x, ou -1 si x est absent
    i = len(t) - 1
    while i >= 0 and t[i] != x:
        i = i - 1
    return i

def indice_min(t):
    # t : liste non vide. Plus petit indice où t atteint son minimum.
    k = 0
    for i in range(1, len(t)):
        if t[i] < t[k]:
            k = i
    return k

def f(u, v):
    u.append(0)
    v = v + [0]

t = [1, 2]
m = t
w = t[:]
f(m, w)
print(t, m, w)

def sans_doublons(t):
    r = []
    for x in t:
        if not (x in r):
            r = r + [x]
    return r

def sans_doublons2(t):
    vus = {}
    r = []
    for x in t:
        if not (x in vus):
            vus[x] = True
            r.append(x)
    return r

def second_strict(t):
    m1 = t[0]
    trouve = False
    m2 = 0
    for x in t:
        if x > m1:
            m2, m1, trouve = m1, x, True
        elif x < m1 and (not trouve or x > m2):
            m2, trouve = x, True
    if trouve:
        return m2
    return None

def majoritaire(t):
    d = {}
    for x in t:
        if x in d:
            d[x] = d[x] + 1
        else:
            d[x] = 1
    for v, c in d.items():
        if 2 * c > len(t):
            return v
    return None

def premier_doublon(t):
    vus = {}
    for y in t:
        if y in vus:
            return y
        vus[y] = True
    return None

def plus_long_plateau(t):
    meilleur = 1
    courant = 1
    for i in range(1, len(t)):
        if t[i] == t[i - 1]:
            courant = courant + 1
        else:
            courant = 1
        if courant > meilleur:
            meilleur = courant
    return meilleur

def somme_paire(t, s):
    pos = {}
    for j in range(len(t)):
        if s - t[j] in pos:
            return (pos[s - t[j]], j)
        pos[t[j]] = j
    return None

Erreurs fréquentes