Bases de Python et boucles simples

Résumé en cinq points

Objectifs du semestre 1 et discipline de programmation

Le programme fixe trois objectifs aux séances du premier semestre.

• Consolider l'apprentissage de Python commencé au lycée.
• Mettre en place un environnement de travail, éditeur, console, exécution d'un fichier.
• Mettre en place une discipline de programmation, spécification précise des fonctions et des programmes, annotations et commentaires, jeux de tests. La consolidation porte sur six points, que la suite de la fiche reprend dans l'ordre, les variables, les expressions et instructions, les instructions conditionnelles, les fonctions, les instructions itératives et la manipulation de quelques structures de données. Aucune connaissance sur les modules rencontrés en séance n'est exigible.

Variables, expressions et instructions

Variables et affectation

Une variable est un nom qui désigne une valeur. L'affectation, écrite avec le signe =, évalue d'abord l'expression de droite puis associe sa valeur au nom de gauche. Ainsi n = n + 1 n'est pas une équation mais une mise à jour, la nouvelle valeur de n est l'ancienne plus un. Le principe d'indentation délimite les blocs, et la portée lexicale fixe où une variable est visible. Dans une fonction, Python cherche d'abord la valeur définie dans la fonction, puis, à défaut, dans l'espace global du module.

Expressions et types de base

Une expression se calcule et produit une valeur, une instruction s'exécute et modifie l'état du programme, par exemple une affectation. Les opérations exigibles de l'annexe sont les suivantes.

• Entiers, type int, avec +, −, * et **, sur des opérandes positifs. La division entière et le reste ne figurent pas dans l'annexe de BCPST, ils peuvent être utilisés en séance avec un rappel.
• Flottants, type float, avec +, −, *, / et **. La division / donne toujours un flottant, et les flottants sont des valeurs approchées. On ne teste jamais l'égalité de deux flottants avec ==. Par exemple, 0.1 + 0.2 == 0.3 vaut False, car aucun de ces trois nombres n'est représenté exactement en machine. On teste plutôt que la valeur absolue de la différence est inférieure à une petite tolérance.
• Booléens, type bool, valeurs True et False, avec not, or et and.
• Comparaisons ==, !=, <, >, <=, >=.

Instructions conditionnelles

if, elif et else exécutent un bloc selon la valeur d'une condition. Les conditions sont testées dans l'ordre et une seule branche est exécutée. Exemple, classer un pH en acide, neutre ou basique, avec trois branches sur pH < 7, pH == 7 et le reste, en gardant à l'esprit qu'avec des flottants le cas neutre exact est rare et qu'une tolérance est plus réaliste.

Fonctions

Une fonction se définit par def f(p1, …, pn), et return renvoie sa valeur. On distingue soigneusement renvoyer et afficher. Une fonction qui calcule doit renvoyer son résultat avec return, pour qu'on puisse le réutiliser dans un autre calcul. L'affichage avec print, utilisé sans paramètre facultatif, sert seulement à observer. Les commentaires, introduits par #, donnent la spécification de la fonction, ce qu'elle attend et ce qu'elle renvoie.

def somme_carres(n):
    # n : entier positif. Renvoie 1² + 2² + ... + n².
    s = 0
    for k in range(1, n + 1):
        s = s + k ** 2
    return s

Vérification sur un petit cas, somme_carres(3) vaut 1 + 4 + 9 = 14, ce que confirme la formule n(n + 1)(2n + 1)/6.

Instructions itératives

Boucle for

La boucle for répète un bloc pour chaque valeur d'une séquence, range(a, b) pour les entiers de a inclus à b exclu, une chaîne de caractères, une liste, ou un dictionnaire à travers ses méthodes keys et items. range(n) va de 0 à n − 1, soit n valeurs. C'est la boucle à utiliser quand le nombre de tours est connu à l'avance.

Boucle while

La boucle while répète un bloc tant qu'une condition est vraie. Elle convient quand on ne sait pas à l'avance combien de tours seront nécessaires, par exemple pour trouver le premier entier n tel que la somme des 1/k pour k de 1 à n dépasse 3. Deux vérifications s'imposent. La condition doit finir par devenir fausse, sinon la boucle ne s'arrête pas. Et les variables doivent être initialisées avant la boucle.

def premier_rang(seuil):
    # renvoie le plus petit n tel que 1 + 1/2 + ... + 1/n > seuil
    n = 0
    s = 0
    while s <= seuil:
        n = n + 1
        s = s + 1 / n
    return n

premier_rang(3) renvoie 11, car la somme vaut environ 2,929 pour n = 10 et 3,020 pour n = 11. La boucle s'arrête parce que cette somme tend vers l'infini, résultat démontré en mathématiques. Pour une suite convergente, une boucle while avec un seuil supérieur à la limite ne s'arrêterait jamais, d'où l'importance de savoir avant d'écrire la boucle que la condition finira par devenir fausse. Un return dans le corps d'une boucle en fait sortir immédiatement. La forme else d'une boucle n'est pas au programme.

Quelques structures de données

Chaînes de caractères

Une chaîne est une suite immuable de caractères. On connaît sa longueur avec len, on accède au caractère d'indice i avec s[i] pour i de 0 à len(s) − 1, on concatène avec +, on répète avec *, on extrait une tranche avec s[i:j], de l'indice i inclus à j exclu. Immuable signifie qu'on ne modifie pas une chaîne, on en construit une nouvelle.

Listes

Une liste est une suite modifiable. On la crée par compréhension, [e for x in s], ou par append successifs à partir de la liste vide. On dispose de len, de l'accès et de la modification par indice, de la concaténation +, de la répétition *, des tranches, de la copie et de pop en dernière position. L'affectation m = t ne copie pas la liste, m et t désignent la même, et modifier l'une modifie l'autre. Ce phénomène, appelé aliasing, est étudié au second semestre.

Dictionnaires

Un dictionnaire associe des valeurs à des clés. On le crée, on lit et on insère une valeur par sa clé, on connaît sa taille avec len et on le copie avec copy. Il est approfondi au second semestre.

Algorithmes élémentaires opérant par boucles simples

Calculs de sommes et de produits

Le schéma est toujours le même. Un accumulateur est initialisé à l'élément neutre, 0 pour une somme, 1 pour un produit, puis mis à jour à chaque tour. Après le tour d'indice k, il contient la somme ou le produit des termes jusqu'à k. Cette phrase est l'invariant de la boucle, et elle permet de vérifier le programme.

Exemple de produit, la factorielle, n! = 1 × 2 × … × n, avec un accumulateur initialisé à 1. Initialiser à 0 donne toujours 0, c'est l'erreur la plus fréquente.

Exemple de somme de flottants, la somme des 1/k² pour k de 1 à n, qui tend vers π²/6, environ 1,645. On l'écrit avec 1 / k ** 2, et la division / renvoie un flottant.

Calcul des termes d'une suite récurrente d'ordre 1

Une suite définie par u₀ et u_n+1 = f(u_n) se calcule avec une seule variable mise à jour n fois.

def terme_logistique(r, u0, n):
    # modèle logistique discret u(k+1) = r u(k) (1 - u(k)). Renvoie u(n).
    u = u0
    for k in range(n):
        u = r * u * (1 - u)
    return u

Le modèle logistique, où u est une population rapportée à sa valeur maximale, converge vers 1 − 1/r pour 1 < r < 3, oscille ensuite entre plusieurs valeurs, et devient chaotique pour r proche de 4. Le nombre de tours est range(n), n tours, car on part de u₀ et on calcule u₁, …, u_n. Se tromper d'un tour est l'erreur classique, qu'on détecte en testant n = 0 et n = 1 à la main.

Autre exemple, une population de poissons qui perd 10 % de ses effectifs chaque année et reçoit 10 000 alevins par alevinage, modélisée par u_n+1 = 0,9 u_n + 10 000. Cette suite arithmético-géométrique converge vers le point fixe ℓ tel que ℓ = 0,9 ℓ + 10 000, soit ℓ = 100 000, quelle que soit la population initiale. Le programme est le même que pour toute suite d'ordre 1, seule la fonction de mise à jour change, et comparer les termes calculés à la limite théorique est un bon test.

Suites récurrentes d'ordre supérieur

Pour une suite d'ordre 2, u_n+2 = a u_n+1 + b u_n, il faut garder les deux derniers termes. À chaque tour, on calcule le nouveau terme à partir des deux précédents, puis on décale.

def fibonacci(n):
    # F(0) = 0, F(1) = 1, F(k+2) = F(k+1) + F(k). Renvoie F(n).
    a = 0
    b = 1
    for k in range(n):
        c = a + b
        a = b
        b = c
    return a

L'ordre des affectations compte. Écrire a = b puis b = a + b ferait perdre l'ancienne valeur de a. La variable auxiliaire c conserve le nouveau terme pendant le décalage. Invariant, après k tours, a vaut F(k) et b vaut F(k + 1). Pour une suite d'ordre 3 ou plus, on garde autant de variables que l'ordre, ou une liste des derniers termes.

Liste des termes d'une suite

Pour tracer une suite ou l'étudier, on veut souvent tous ses termes et pas seulement le dernier. On part d'une liste contenant u₀ et on ajoute chaque nouveau terme avec append. Le dernier terme de la liste t s'écrit t[len(t) − 1], l'indice positif valide exigé par le programme. La liste obtenue a n + 1 éléments, u₀ à u_n.

def termes_logistique(r, u0, n):
    t = [u0]
    for k in range(n):
        u = t[len(t) - 1]
        t.append(r * u * (1 - u))
    return t

Pour visualiser la suite, on trace les points d'abscisse k et d'ordonnée u_k avec un module graphique, par exemple import matplotlib.pyplot as plt, puis plt.plot(range(n + 1), t) et plt.show(). Aucune connaissance de ce module n'est exigible, sa documentation est fournie quand il sert. Tracer la liste des termes pour r = 2,8, r = 3,2 et r = 3,9 montre d'un coup d'œil la convergence, l'oscillation entre deux valeurs et le comportement chaotique du modèle logistique.

Boucles simples sur les chaînes de caractères

Une boucle for parcourt une chaîne caractère par caractère. Exemples en lien avec la biologie, sur une séquence d'ADN écrite avec les lettres A, C, G, T.

• Compter les bases G et C et calculer le taux de GC, nombre de G et de C divisé par la longueur.

def taux_gc(seq):
    # seq : chaîne non vide sur l'alphabet A, C, G, T
    n = 0
    for base in seq:
        if base == 'G' or base == 'C':
            n = n + 1
    return n / len(seq)

• Construire le brin complémentaire, en remplaçant A par T, T par A, C par G et G par C, et en concaténant les caractères obtenus dans une nouvelle chaîne, puisque la chaîne d'origine est immuable.
• Inverser une chaîne, en ajoutant chaque caractère devant le résultat partiel, ou en parcourant les indices de la fin vers le début. Le coût de ces traitements est proportionnel à la longueur de la chaîne, un seul parcours suffit.

Méthodes

• Avant d'écrire la boucle, écrire l'invariant en une phrase, « s contient la somme des termes déjà traités ». L'initialisation et la mise à jour en découlent.
• Initialiser un accumulateur de somme à 0 et de produit à 1.
• Compter les tours. range(n) fait n tours, range(1, n + 1) parcourt 1 à n.
• Pour une suite d'ordre 2, utiliser une variable auxiliaire lors du décalage, ou vérifier l'ordre des affectations.
• Tester sur n = 0, n = 1 et un petit cas calculé à la main.
• Renvoyer le résultat avec return, et réserver print à l'observation.
• N'utiliser que les éléments du langage de l'annexe. Une fonction toute faite, comme sum ou max, ne remplace pas l'algorithme demandé.

Ce qu'il faut savoir refaire en khôlle

1. Écrire une fonction qui calcule une somme ou un produit défini par une formule, avec son invariant, et la vérifier sur un petit cas.
2. Calculer le n-ième terme d'une suite récurrente d'ordre 1, puis la liste de ses n + 1 premiers termes.
3. Calculer le n-ième terme d'une suite d'ordre 2 en gérant correctement le décalage des variables.
4. Trouver avec une boucle while le premier rang où une suite dépasse un seuil, en justifiant l'arrêt de la boucle.
5. Parcourir une séquence d'ADN pour compter des bases, calculer un taux de GC ou construire le brin complémentaire.
6. Expliquer la différence entre renvoyer et afficher, et entre m = t et une copie de liste.

Les résultats à connaître

En informatique, les « résultats » sont le comportement exact du langage, la correction des algorithmes et leur nombre d'opérations dans le pire cas.

• L'affectation évalue entièrement l'expression de droite, puis donne sa valeur au nom de gauche : exigible.
• range(a, b) produit b − a entiers si a < b, et aucun sinon. range(n) fait donc n tours, et zéro si n ≤ 0 : exigible.
• / renvoie toujours un flottant, même entre entiers. ** entre entiers positifs renvoie un entier exact : exigible.
• Les flottants sont approchés, deux calculs mathématiquement égaux peuvent différer. On compare avec une tolérance : exigible, à savoir illustrer.
• and et or n'évaluent leur second opérande que si c'est nécessaire : exigible.
• return termine la fonction immédiatement, même au milieu d'une boucle. Une fonction qui n'exécute aucun return renvoie None : exigible.
• Une chaîne est immuable, une liste est modifiable, et m = t ne copie pas une liste : exigible.
• Accumulateur de somme ou de produit : après le tour d'indice k, il contient la somme ou le produit des termes d'indice au plus k : exigible avec justification par invariant.
• Suite d'ordre 1 : après k tours, la variable contient u_k. Le calcul de u_n demande n tours : exigible avec justification.
• Suite d'ordre 2 : après k tours, le couple de variables vaut (u_k, u_k+1) : exigible avec justification.
• Boucle while de seuil : elle termine si et seulement si la condition finit par devenir fausse. Il faut un argument mathématique ou un garde-fou : exigible avec justification.
• Parcours d'une chaîne de longueur n : n tours de boucle, soit un nombre d'opérations proportionnel à n : exigible.
• Hors programme signalé : division entière // et reste % (utilisables en séance avec un rappel), indices négatifs, forme else d'une boucle, fonctions sum, max et reversed, méthodes de chaîne comme count ou replace, notion formelle de complexité (vue plus tard).

Clés de démonstration

Accumulateur. On énonce l'invariant « après le tour d'indice k, s vaut la somme des termes d'indice au plus k ». L'initialisation à l'élément neutre le rend vrai avant le premier tour, car une somme vide vaut 0 et un produit vide vaut 1. L'astuce est d'écrire l'invariant avant le code : la valeur initiale et la ligne de mise à jour s'en déduisent.

Suite d'ordre 1. On raisonne par récurrence sur le nombre de tours. Avant tout tour, u vaut u₀. Si u vaut u_k avant un tour, l'instruction u = f(u) lui donne la valeur u_k+1. L'astuce est de compter les tours et non les indices : n tours mènent de u₀ à u_n.

Suite d'ordre 2. Invariant : après k tours, x vaut u_k et y vaut u_k+1. Le tour calcule z = a y + b x, qui vaut u_k+2, puis décale. L'astuce est la variable auxiliaire, qui mémorise le nouveau terme avant d'écraser x.

Terminaison d'un while. On exhibe une quantité entière positive qui décroît strictement à chaque tour, par exemple nmax − n, ou bien on prouve mathématiquement que la suite finit par franchir le seuil. L'astuce est d'utiliser une formule explicite quand elle existe, comme pour une suite arithmético-géométrique.

Parcours de chaîne. Invariant : après avoir lu les k premiers caractères, le résultat partiel est celui qu'on aurait obtenu sur la tranche seq[0:k]. L'astuce, pour une chaîne résultat, est de décider si le nouveau caractère se place devant ou derrière le résultat partiel.

Exemples et contre-exemples à connaître

1. Ajouter dix fois 0.1 à 0 donne 0.9999999999999999 et non 1.0. Une somme de flottants accumule les erreurs d'arrondi.
2. range(6 / 2) provoque une erreur, car 6 / 2 vaut 3.0, un flottant. Un nombre de tours doit être un entier.
3. Une factorielle dont l'accumulateur est initialisé à 0 renvoie 0 pour tout n. C'est le cas d'école de la mauvaise initialisation.
4. for k in range(1, n) oublie le terme d'indice n. On le repère en testant n = 1, qui donne une somme vide.
5. Dans Fibonacci, écrire a = b puis b = a + b fait doubler b à chaque tour. On obtient 0, 1, 2, 4, 8 au lieu de 0, 1, 1, 2, 3.
6. Chercher le premier n tel que la somme des 1/k² dépasse 2 ne termine jamais, car cette somme reste inférieure à π²/6 ≈ 1,645.
7. Une fonction qui affiche son résultat avec print sans le renvoyer donne None. f(3) + 1 provoque alors une erreur.
8. Un return s indenté dans la boucle renvoie le premier terme seulement. La somme de 1 à 5 donne alors 1.
9. seq[0] = 'T' sur une chaîne provoque une erreur. Pour transformer une séquence, on construit une nouvelle chaîne.
10. Pour u_n+1 = 0,9 u_n + 10 000, un while qui attend u ≥ 100 000 en partant de 20 000 ne termine pas mathématiquement. La limite n'est jamais atteinte.

Techniques du chapitre

Technique 1, l'invariant d'abord. Mini-exercice : calculer le produit 1 × 3 × 5 × … × (2n − 1). Invariant : après le tour k, p est le produit des 2j + 1 pour j de 0 à k. Donc p = 1 au départ, for k in range(n) et p = p * (2 * k + 1). Tests : n = 0 donne 1, n = 2 donne 3.

Technique 2, compter les tours. Mini-exercice : for k in range(2, n) fait combien de tours ? Réponse : n − 2 si n ≥ 2, et zéro sinon. On vérifie toujours le dernier tour et le cas où la boucle ne s'exécute pas.

Technique 3, mettre à jour un terme au lieu de le recalculer. Mini-exercice : sommer q^k pour k de 0 à n sans **. On garde une variable terme, initialisée à 1, et on fait s = s + terme puis terme = terme * q. Chaque tour coûte deux opérations.

Technique 4, un while avec justification. Mini-exercice : plus petit n tel que 2ⁿ > 10⁶. On part de n = 0 et p = 1, et tant que p ≤ 10⁶ on double p et on incrémente n. La suite 2ⁿ tend vers l'infini, donc la boucle termine. Réponse : 20, car 2²⁰ = 1 048 576.

Technique 5, comparer des flottants avec une tolérance. Mini-exercice : tester que x et y sont égaux à 10⁻⁹ près sans fonction de bibliothèque. On écrit x - y < 1e-9 and y - x < 1e-9, ce qui équivaut à |x − y| < 10⁻⁹.

Technique 6, construire une chaîne résultat. Mini-exercice : transcrire un brin codant d'ADN en ARN, en remplaçant T par U. On part de r = '' et, pour chaque caractère c, on ajoute 'U' si c vaut 'T', sinon c lui-même, avec r = r + .... 'GAT' donne 'GAU'.

Technique 7, tracer à la main. Mini-exercice : suivre fibonacci(4) de la fiche. On écrit a et b après chaque tour : (1, 1), (1, 2), (2, 3), (3, 5). La fonction renvoie a = 3, qui est bien F(4).

Exercices classiques corrigés

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

def verifie(n):
    # n : entier >= 1. True si la somme calculée vaut 1 - 1/(n+1) à 1e-9 près.
    s = 0
    for k in range(1, n + 1):
        s = s + 1 / (k * (k + 1))
    e = s - (1 - 1 / (n + 1))
    return e < 1e-9 and -e < 1e-9

def approx_exp(x, n):
    # n : entier >= 0. Renvoie la somme des x**k / k! pour k de 0 à n.
    terme = 1
    s = 1
    for k in range(1, n + 1):
        terme = terme * x / k
        s = s + terme
    return s

def somme_termes(u0, n):
    # renvoie u(0) + ... + u(n) pour u(k+1) = 0.5 u(k) + 3
    u = u0
    s = u0
    for k in range(n):
        u = 0.5 * u + 3
        s = s + u
    return s

def terme_ordre2(a, b, u0, u1, n):
    # renvoie u(n), n entier >= 0
    x = u0
    y = u1
    for k in range(n):
        z = a * y + b * x
        x = y
        y = z
    return x

def liste_ordre3(n):
    # n : entier >= 0. Renvoie [u(0), ..., u(n)].
    t = [0, 0, 1]
    for k in range(n - 2):
        m = len(t)
        t.append(t[m - 1] + t[m - 2] + t[m - 3])
    return t[0:n + 1]

def annee_seuil(u0, seuil):
    # plus petit n tel que u(n) >= seuil. Hypothèse : seuil < 100000.
    n = 0
    u = u0
    while u < seuil:
        u = 0.9 * u + 10000
        n = n + 1
    return n

def complement_inverse(seq):
    # seq : chaîne sur A, C, G, T
    r = ''
    for base in seq:
        if base == 'A':
            c = 'T'
        elif base == 'T':
            c = 'A'
        elif base == 'C':
            c = 'G'
        else:
            c = 'C'
        r = c + r
    return r

def occurrences_motif(seq, m):
    # m non vide. Nombre de i tels que seq[i:i+len(m)] == m.
    p = len(m)
    c = 0
    for i in range(len(seq) - p + 1):
        if seq[i:i + p] == m:
            c = c + 1
    return c

def heron(a, eps):
    # a > 0, eps > 0 pas trop petit, 1e-12 par exemple
    u = a
    v = (u + a / u) / 2
    while u - v > eps or v - u > eps:
        u = v
        v = (u + a / u) / 2
    return v

def annee_doublement(j0, a0, nmax):
    j = j0
    a = a0
    n = 0
    while j + a < 2 * (j0 + a0) and n < nmax:
        nouveau_j = 1.2 * a
        a = 0.5 * j + 0.6 * a
        j = nouveau_j
        n = n + 1
    if j + a >= 2 * (j0 + a0):
        return n
    return -1

Erreurs fréquentes