Bases de Python et recherche séquentielle

Résumé en cinq points

1Objectifs 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.

2Traits généraux du langage Python

2.1Typage dynamique

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é.

2.2Principe 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.

2.3Porté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.

2.4Appel 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.

3Types de base

3.1Entiers et flottants

Sur les entiers, type int, les opérations exigibles sont :

• l'addition, la soustraction, la multiplication ;
• la division entière // ;
• l'exponentiation ** ;
• 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$.

3.2Booléens et comparaisons

Le type bool a deux valeurs, True et False, et trois opérations : not, and, or. Les comparaisons exigibles sont ==, !=, <, >, <=, >=.

Cela permet d'écrire i < len(t) and t[i] != x sans risque de sortir du tableau.

4Types structurés

4.1Chaînes et tuples, structures indicées immuables

Les chaînes de caractères et les tuples sont des structures indicées immuables. On peut :

• y accéder par indice positif valide, de $0$ à $\texttt{len(s)} - 1$ ;
• les concaténer avec + ;
• les répéter avec * ;
• en extraire 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.

4.2Listes

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 ;
• l'accès et la modification par indice positif valide ;
• la concaténation + ;
• l'extraction de tranche ;
• la copie ;
• pop en dernière position.

Le point délicat est la copie.

4.3Dictionnaires

Un dictionnaire associe des valeurs à des clés. Les opérations sont :

• 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. L'accès, l'insertion et le test de présence sont admis de coût constant en pratique, sans garantie dans le pire cas. Le principe du hachage, qui explique ce coût et les restrictions sur les clés, est vu en deuxième année.

5Structures de contrôle

5.1Affectation 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.

5.2Instruction conditionnelle

On utilise 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.

5.3Boucles 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 ou une liste ;
• 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.

5.4Dé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. Celui-ci s'utilise sans paramètre facultatif. Les commentaires commencent par #, et le programme demande qu'ils éclairent le code sans le paraphraser.

6Recherche séquentielle dans un tableau unidimensionnel

6.1Recherche 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

Variante utile : renvoyer l'indice de la première occurrence, ou $-1$ si x est absent, avec une boucle sur range(len(t)), qui va de $0$ à $n - 1$.

def indice_for(t, x):
    # renvoie le plus petit i tel que t[i] == x,
    # ou -1 si x n'est pas dans t
    for i in range(len(t)):
        if t[i] == x:
            return i
    return -1

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

La terminaison se justifie par un variant : $\texttt{len(t)} - i$ est un entier positif qui diminue de $1$ à chaque tour.

6.2Recherche 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

L'invariant est vrai avant la boucle avec $k = 1$, et chaque tour le conserve. Le premier tour retraite t[0] sans changer m. À la fin, $k = n$, donc m est le maximum de t.

Le parcours complet fait $n$ comparaisons, dont $n - 1$ sont utiles (on peut parcourir t[1:] pour n'en faire que $n - 1$). Le coût est linéaire.

6.3Comptage 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^2$ : un coût quadratique, étudié avec les boucles imbriquées dans le thème suivant. C'est le premier exemple où le choix de la structure de données change l'ordre de grandeur du coût.

6.4Coût constant et coût linéaire

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.

Méthodes

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 des algorithmes avec leur spécification et leur coût, et des faits de langage qu'il faut savoir expliquer. Le programme range la recherche d'un élément, le maximum, le second maximum et le comptage parmi les exemples d'activités. Il ne les exige pas comme connaissances, mais tout sujet suppose qu'on sache les réécrire en quelques minutes.

• Recherche d'un élément. Entrée : une liste t de longueur n et une valeur x. Sortie : True si x est égal à l'un des t[i], False sinon. Coût linéaire dans le pire cas, au plus n comparaisons. À savoir réécrire et justifier.
• Première occurrence. Même entrée, sortie : le plus petit i tel que t[i] == x, ou −1. Terminaison par le variant n − i. À savoir réécrire.
• Maximum. Hypothèse : liste non vide de valeurs comparables. Coût linéaire, correction par invariant. À savoir réécrire.
• Second maximum. Hypothèse : au moins deux éléments, convention sur les doublons fixée à l'avance. Un seul parcours, coût linéaire. À savoir réécrire.
• Comptage par dictionnaire. Coût linéaire, en admettant que le test de présence, l'accès et l'insertion dans un dictionnaire ont un coût constant en pratique. Ce coût est admis, sa justification par le hachage relève de la deuxième année.
• Coûts des opérations sur les listes : constants pour len, l'accès et la modification par indice, append et pop en fin. Linéaires pour in, la copie, la concaténation et la tranche. À connaître, sans démonstration.
• Terminaison par variant. Si une quantité entière positive décroît strictement à chaque tour, la boucle while s'arrête. Outil de validation exigible.
• Correction par invariant. Une propriété vraie avant la boucle et conservée par chaque tour est vraie à la sortie. Outil exigible.
• Faits de langage exigibles : and et or sont paresseux, une affectation ne copie pas une liste, une tranche fait une copie superficielle, une fonction qui modifie une case de la liste reçue modifie la liste de l'appelant, une variable affectée dans une fonction est locale.
• Hors programme ou sous condition : l'étude du coût moyen et du meilleur cas, la forme else d'une boucle, les indices négatifs. Les fonctions max, sorted, index et count ne sont utilisables que si le sujet les documente.

Clés de démonstration

Recherche booléenne avec une boucle for. Invariant : au début du tour qui examine t[i], x n'est aucun des éléments t[0], …, t[i − 1]. Si la fonction renvoie True, c'est qu'un test y == x a réussi, donc la réponse est juste. Si la boucle se termine, l'invariant avec i = n dit que x n'est nulle part. Astuce : l'invariant décrit la partie déjà parcourue, jamais la partie restante.

Recherche avec while. Le variant n − i est un entier positif qui diminue de 1 à chaque tour, d'où la terminaison. À la sortie, la condition est fausse. Par De Morgan, on a donc i ≥ n ou t[i] == x. Dans le premier cas, x est absent. Dans le second, l'invariant garantit que i est la première occurrence. Astuce : lire la sortie d'une boucle while comme la négation de sa condition.

Maximum. Invariant : m est le maximum des éléments déjà vus. Astuce : initialiser avec t[0], jamais avec 0, sinon l'invariant est faux dès le départ pour une liste de négatifs.

Second maximum. Invariant : m1 et m2 sont les deux premiers termes, dans l'ordre décroissant, des éléments vus. Pour la conservation, on distingue trois cas, x > m1, puis m2 < x ≤ m1, puis x ≤ m2. Astuce : dans le premier cas, l'ancien m1 descend en m2, c'est l'étape qu'on oublie.

Comptage. Invariant : après k tours, les clés de d sont exactement les valeurs présentes parmi les k premiers éléments, et chacune est associée à son nombre d'occurrences parmi eux. Astuce : l'invariant a deux moitiés, « les bonnes clés » et « les bons effectifs », et le test x in d sert la première.

Coût linéaire. La boucle fait n tours, et chaque tour coûte au plus une constante c. Le coût total est donc au plus c × n. Astuce : vérifier ligne par ligne que le corps ne contient aucune opération cachée de coût linéaire.

Exemples et contre-exemples à connaître

1. Un maximum initialisé à 0 renvoie 0 pour [−3, −1]. Le cas « tous négatifs » est le test qui démasque cette erreur.
2. Un return False placé dans la boucle, après le if, fait répondre False pour [1, 2] et x = 2. La première case différente de x suffit à conclure à tort.
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 décoratif.
4. Pour la liste [5, 5, 3], le second maximum vaut 5 avec doublons et 3 au sens strict. Sans convention annoncée, la question n'a pas de réponse.
5. maximum([]) provoque une erreur d'indice sur t[0]. La spécification doit exclure la liste vide ou la traiter.
6. Dans une fonction, t[0] = 0 modifie la liste de l'appelant, mais t = [0] ne la modifie pas. La première instruction agit sur la liste, la seconde change seulement ce que désigne le nom local.
7. Lire d[c] quand c n'est pas une clé provoque une erreur. C'est pour cela que le comptage teste c in d avant de lire d[c].
8. Une fonction qui contient n = n + 1 alors que n n'est défini que globalement provoque une erreur à l'exécution. L'affectation rend n local dans toute la fonction, et sa lecture précède alors toute affectation.
9. Une boucle qui contient t = t + [x] a un coût quadratique, alors que t.append(x) donne un coût linéaire. La concaténation recopie toute la liste à chaque tour.

Techniques du chapitre

Technique 1 : écrire la spécification avant le code. Mini-exercice : compter les occurrences de x dans t. On écrit la signature en commentaire, puis on vérifie le cas de la liste vide.

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

Pour la liste vide, la boucle ne tourne pas et la fonction renvoie 0. Le coût est linéaire.

Technique 2 : choisir entre for et while. On prend for quand on parcourt tout, while quand on s'arrête sur une condition. Mini-exercice : trouver le premier indice d'un nombre négatif. On écrit while i < len(t) and t[i] >= 0: suivi de i = i + 1, puis on renvoie i si i < len(t), et −1 sinon.

Technique 3 : vérifier un invariant en trois temps, initialisation, conservation, conclusion. Mini-exercice : la somme s des éléments. Invariant : après k tours, s = t[0] + … + t[k − 1]. Il est vrai pour k = 0 avec s = 0. Le tour suivant ajoute t[k]. À la fin, k = n.

Technique 4 : exhiber un variant pour une boucle while. Mini-exercice : compter les chiffres d'un entier n ≥ 1 avec while n > 0: suivi de n = n // 10. Le variant est n lui-même. C'est un entier positif, et n // 10 < n dès que n ≥ 1. La boucle termine donc.

Technique 5 : remplacer une recherche répétée par un dictionnaire. Mini-exercice : trouver le premier caractère d'une chaîne qui apparaît une deuxième fois. On parcourt la chaîne avec un dictionnaire vus. Dès que c in vus, on renvoie c. Sinon, on fait vus[c] = True. Le coût est linéaire au lieu de quadratique.

Technique 6 : lire le coût en repérant les boucles cachées. Mini-exercice : for i in range(len(t)): suivi de if t[i] in t[i + 1:]:. La tranche et le test in coûtent chacun de l'ordre de n − i. La somme donne un coût de l'ordre de n², donc quadratique.

Technique 7 : tester à la main sur trois cas. Mini-exercice : tester un maximum sur [3, 1, 2], sur [4] et sur [−5, −2]. Le troisième test révèle toute initialisation à 0.

Exercices classiques corrigés

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

def derniere(t, x):
    # t : list. Renvoie le plus grand i tel que t[i] == x, ou -1
    r = -1
    for i in range(len(t)):
        if t[i] == x:
            r = i
    return r

def f(u):
    u[0] = 7
    u = [0, 0]
    u[1] = 9

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

def indice_min(t):
    # t : liste non vide de nombres
    k = 0
    for i in range(1, len(t)):
        if t[i] < t[k]:
            k = i
    return k

def second_strict(t):
    m1 = t[0]
    m2 = t[0]         # sans signification tant que trouve est faux
    trouve = False
    for x in t:
        if x > m1:
            m2, m1 = m1, x
            trouve = True
        elif x < m1 and (not trouve or x > m2):
            m2 = x
            trouve = 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 c, v in d.items():
        if 2 * v > len(t):
            return c
    return None

def somme_deux(t, s):
    vus = {}
    for x in t:
        if s - x in vus:
            return True
        vus[x] = True
    return False

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

def renverse(t):
    r = []
    for x in t:
        r = [x] + r
    return r

def plus_long_plateau(t):
    courant = 1
    meilleur = 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 plus_petit_absent(t):
    n = len(t)
    present = [False] * (n + 1)
    for x in t:
        if x <= n:
            present[x] = True
    k = 0
    while present[k]:
        k = k + 1
    return k

Erreurs fréquentes