Algorithmique et Python · Première spécialité

Pourquoi programmer en maths ?

La machine fait le calcul, toi tu fais le raisonnement

Beaucoup de problèmes mathématiques demandent de répéter un calcul des centaines de fois, ou de tester une condition sur une longue liste de nombres. À la main, c'est interminable et source d'erreurs. La programmation confie cette exécution mécanique à la machine : tu décris une fois pour toutes la méthode (l'algorithme), et l'ordinateur l'applique sans fatigue ni erreur. Ton travail reste le plus important : penser la méthode.

Algorithme ou programme ?

Un algorithme est une suite finie d'instructions non ambiguës qui résout un problème. On peut l'écrire en langage naturel (en français, avec le symbole $\aff$ pour « prend la valeur ») ou dans un langage de programmation comme Python. Le programme, c'est la traduction de l'algorithme dans un langage que la machine comprend.

L'idée directrice

L'idée avant le code

Une variable, c'est une boîte avec une étiquette

Choisir, répéter : les deux gestes de base

Découper pour ne pas se noyer : les fonctions

Le cours complet

Variables, types et affectation

Propriété · Les principaux types

Type	Description	Exemple Python
`int`	nombre entier	$\texttt{n = 7}$
`float`	nombre décimal	$\texttt{x = 3.14}$
`str`	chaîne de caractères	$\texttt{nom = "Ada"}$
`bool`	booléen (vrai/faux)	$\texttt{test = True}$
`list`	liste de valeurs	$\texttt{L = [2, 4, 6]}$

Exemple · Échanger deux variables

Pour échanger les contenus de a et b, on passe par une variable temporaire (sinon on écrase une valeur) :

a = 3
b = 8
temp = a      # on met de cote l'ancien a
a = b         # a recoit b
b = temp       # b recoit l'ancien a
print(a, b)   # affiche 8 3

Instructions conditionnelles : choisir

Définition · Conditionnelle if / elif / else

Une instruction conditionnelle exécute un bloc si une condition est vraie, un autre sinon. En Python, l'indentation (le décalage) délimite les blocs.

if note >= 10:
    print("Admis")
elif note >= 8:
    print("Rattrapage")
else:
    print("Refuse")

Boucles bornées : répéter un nombre connu de fois

Définition · Boucle for

La boucle for répète un bloc pour chaque valeur d'une plage. range(a, b) parcourt les entiers de a à b-1 (la borne de droite est exclue).

somme = 0
for k in range(1, 101):   # k va de 1 a 100
    somme = somme + k
print(somme)              # 5050

Boucles non bornées : répéter jusqu'à une condition

Définition · Boucle while

La boucle while répète un bloc tant que sa condition reste vraie. On l'utilise quand on ne sait pas d'avance combien de répétitions seront nécessaires (recherche de seuil, par exemple).

capital = 1000
annees = 0
while capital < 2000:     # tant qu'on n'a pas double
    capital = capital * 1.05   # +5
    annees = annees + 1
print(annees)             # nombre d'annees pour doubler

Fonctions et programmation modulaire

Définition · Fonction

Une fonction regroupe un bloc d'instructions sous un nom. Elle reçoit des paramètres (entrées) et renvoie un résultat avec return.

def aire_disque(rayon):
    return 3.14159 * rayon**2

a = aire_disque(2)    # appel : rayon vaut 2
print(a)              # 12.56636

Les listes : la grande nouveauté

Définition · Liste

Une liste range plusieurs valeurs dans un ordre précis, sous un seul nom. Chaque élément a un indice (sa position), qui commence à 0.

L = [5, 12, 8, 20]   # liste en extension
print(L[0])          # 5   (premier element, indice 0)
print(L[3])          # 20  (quatrieme element, indice 3)
print(len(L))        # 4   (nombre d'elements)

Propriété · Trois façons de créer une liste

# 1. En extension : on ecrit les elements
carres = [0, 1, 4, 9, 16]

# 2. Par ajouts successifs : on part du vide et on remplit
carres = []
for k in range(5):
    carres.append(k**2)     # ajoute k^2 a la fin

# 3. En comprehension : une formule + une plage (+ une condition)
carres = [k**2 for k in range(5)]
pairs  = [k for k in range(20) if k

Méthode · Opérations courantes sur les listes

Opération	Code Python
Longueur	`len(L)`
Accéder à l'élément d'indice `i`	`L[i]`
Ajouter à la fin	`L.append(x)`
Supprimer l'élément d'indice `i`	`del L[i]`
Tester l'appartenance	`x in L`
Somme / maximum / minimum	`sum(L)`, `max(L)`, `min(L)`

Propriété · Deux façons de parcourir une liste

L = [5, 12, 8, 20]

# Parcourir par INDICES (utile si on a besoin de la position)
for i in range(len(L)):
    print(i, L[i])

# ITERER sur les ELEMENTS (plus simple si la position est inutile)
for valeur in L:
    print(valeur)

Exemple · Moyenne d'une liste de notes

def moyenne(notes):
    if len(notes) == 0:
        return None          # liste vide : pas de moyenne
    return sum(notes) / len(notes)

print(moyenne([12, 8, 15, 10]))   # 11.25

Un peu de logique et d'ensembles

Propriété · Négation des propositions quantifiées

Proposition	Sa négation
« Tous les $$x$$ vérifient $$P$$ »	« Il existe un $$x$$ qui ne vérifie pas $$P$$ »
« Il existe un $$x$$ tel que $$P$$ »	« Aucun $$x$$ ne vérifie $$P$$ »
« $$P$$ et $$Q$$ »	« (non $$P$$ ) ou (non $$Q$$ ) »
« $$P$$ ou $$Q$$ »	« (non $$P$$ ) et (non $$Q$$ ) »

Couples et produit cartésien

Exemple · Construire un produit cartésien

Si $A=\{1,2\}$ et $B=\{a,b,c\}$ , alors

\begin{aligned}&A\times B\\&= \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}.\end{aligned}

Il contient $2\times3=6$ couples. En Python :

A = [1, 2]
B = ["a", "b", "c"]
produit = [(x, y) for x in A for y in B]

Les deux boucles correspondent aux deux choix successifs : un élément de $$A$$ , puis un élément de $$B$$ .

Identité, équation et statut des lettres

Trois structures de raisonnement

Pour aller plus loin : prouver qu'un algorithme est correct

Démonstration · Pourquoi l'algorithme du maximum fonctionne

Considérons une liste non vide $$L$$ et le programme :

def maximum(L):
    m = L[0]
    for x in L[1:]:
        if x > m:
            m = x
    return m

L'invariant est : « après avoir lu les premiers éléments, $$m$$ est leur maximum ».

Initialisation : avant la boucle, seul $$L[0]$$ a été pris en compte ; son maximum est bien $$m=L[0]$$ .
Conservation : quand on lit $$x$$ , soit $x\leqslant m$ et le maximum reste $$m$$ , soit $$x>m$$ et on remplace $$m$$ par $$x$$ . Dans les deux cas, $$m$$ devient le maximum de tous les éléments déjà lus.
Sortie : tous les éléments ont été lus ; l'invariant affirme donc que $$m$$ est le maximum de toute la liste.

$\blacksquare$

Boîte à outils : réflexes pour le bac

Méthode · Mémo syntaxe Python

x = 5                  # affectation
if cond:               # condition (: puis indentation)
    ...
elif autre_cond:
    ...
else:
    ...
for k in range(a, b):  # boucle bornee (b exclu)
    ...
while cond:            # boucle non bornee
    ...
def f(parametres):     # fonction
    return resultat
L = [1, 2, 3]          # liste ; L[0] premier ; len(L) longueur
L.append(x)            # ajoute a la fin
[expr for k in range(n) if cond]   # liste en comprehension

Propriété · Quel outil pour quel besoin ?

Besoin	Outil
Choisir entre plusieurs cas	`if / elif / else`
Répéter un nombre connu de fois	`for ... in range(...)`
Répéter jusqu'à une condition	`while ...`
Réutiliser un calcul	`def ...: return ...`
Stocker plusieurs valeurs	une `list`
Construire une liste « en sélectionnant »	liste en compréhension avec `if`

Méthode · Trois algorithmes à savoir refaire par cœur

# 1. Somme / moyenne d'une liste
def moyenne(L):
    return sum(L) / len(L)

# 2. Recherche du maximum (sans max())
def maximum(L):
    m = L[0]
    for x in L:
        if x > m:
            m = x
    return m

# 3. Recherche de seuil (premier n tel que u_n depasse S)
def seuil(S):
    u = 1
    n = 0
    while u <= S:
        u = u * 2      # exemple : u_n = 2^n
        n = n + 1
    return n

Exercices

Exercice 1 ★☆☆ : Lire une affectation

On exécute : a = 4 ; b = 7 ; a = a + b ; b = a - b. Quelles sont les valeurs finales de a et b ?

Exercice 2 ★☆☆ : Trace d'une boucle

Que vaut s après ce code ? Détailler les valeurs successives.

s = 0
for k in range(1, 5):
    s = s + k

Exercice 3 ★☆☆ : Lire une liste

Soit L = [3, 9, 1, 7, 4]. Donner L[0], L[2], len(L), L[len(L)-1], et la valeur de sum(L).

Exercice 4 ★☆☆ : Pair ou impair

Écrire une fonction parite(n) qui renvoie la chaîne "pair" si n est pair, "impair" sinon. (Indice : n % 2 vaut $$0$$ si n est pair.)

Exercice 5 ★☆☆ : Compter

Écrire une fonction compte_pairs(L) qui renvoie le nombre d'éléments pairs d'une liste L.

Exercice 6 ★☆☆ : Liste en compréhension

Écrire, en une seule ligne (compréhension), la liste des cubes $$k^3$$ pour $$k$$ de $$1$$ à $$10$$ . Puis la liste des multiples de $$3$$ entre $$0$$ et $$30$$ inclus.

Exercice 7 ★★☆ : Somme conditionnelle

Écrire une fonction somme_positifs(L) qui renvoie la somme des éléments strictement positifs d'une liste L.

Exercice 8 ★★☆ : Table de multiplication

Écrire une fonction table(n) qui renvoie la liste [n, 2n, 3n, ..., 10n].

Exercice 9 ★★☆ : Maximum et sa position

Écrire une fonction indice_max(L) qui renvoie l'indice du plus grand élément de L (le premier en cas d'égalité).

Exercice 10 ★★☆ : Suite et seuil

On définit $$u_0=2$$ et $u_{n+1}=1{,}5\,u_n$ . Écrire une fonction seuil(S) qui renvoie le plus petit $$n$$ tel que $$u_n>S$$ .

Exercice 11 ★★☆ : Recherche dans une liste

Écrire une fonction est_present(x, L) qui renvoie True si x apparaît dans L, False sinon, sans utiliser le mot-clé in (avec une boucle).

Exercice 12 ★★★ : Logique et méthodes de preuve

1. Pour chaque implication, dire si elle est vraie, puis donner sa réciproque et dire si elle est vraie.

« $$n$$ multiple de $$4$$ $\Rightarrow$ $$n$$ pair » ;
« $x>3 \Rightarrow x>1$ » ;
« $x^2=9\Rightarrow x=3$ ».

2. Nier correctement : « tous les élèves ont réussi » ; « il existe un entier pair supérieur à $$100$$ » ; « $$x>0$$ et $$x<2$$ ».

3. Démontrer par disjonction des cas que $$n(n+1)$$ est pair pour tout entier $$n$$ .

4. Démontrer par contraposée : si $$n^2$$ est pair, alors $$n$$ est pair.

5. Démontrer par l'absurde qu'aucun entier ne peut être à la fois pair et impair.

Exercice 13 ★★★ : Crible des nombres premiers

Écrire une fonction est_premier(n) qui renvoie True si n est premier ( $n\geqslant 2$ ), puis une fonction premiers_jusqua(N) qui renvoie la liste des nombres premiers inférieurs ou égaux à N.

Exercice 14 ★★★ : Simulation et espérance

On lance deux dés et on s'intéresse à la somme $$S$$ . Écrire une fonction moyenne_somme(n) qui simule n lancers de deux dés et renvoie la moyenne des sommes obtenues. Vers quelle valeur doit-elle tendre ? (Lien fiche 10.)

Exercice 15 ★★★ : Inverser une liste

Écrire une fonction renverse(L) qui renvoie une nouvelle liste contenant les éléments de L dans l'ordre inverse, sans utiliser L.reverse() ni L[::-1].

Exercice 16 ★★★ : Ensembles et produit cartésien via les listes

1. Écrire une fonction intersection(A, B) qui renvoie la liste des éléments présents à la fois dans A et dans B (sans doublon). Relier au symbole mathématique correspondant.

2. Écrire une fonction produit_cartesien(A, B) qui renvoie la liste de tous les couples $$(x,y)$$ avec $x\in A$ et $y\in B$ . Combien de couples obtient-on si $$A$$ contient $$p$$ éléments et $$B$$ en contient $$q$$ ?

Problème type prépa

Partie A : les briques de base\\[2pt] On dispose d'une liste de notes, par exemple notes = [12, 8, 15, 10, 6, 18, 9].

Écrire moyenne(L) qui renvoie la moyenne d'une liste non vide.
Écrire maximum(L) et minimum(L) sans utiliser max ni min.
Écrire nb_admis(L) qui renvoie le nombre de notes supérieures ou égales à $$10$$ .

Partie B : compréhensions et sélection\\[2pt]

En une ligne (compréhension), construire la liste des notes >= 10.
Écrire ajuste(L) qui renvoie une nouvelle liste où chaque note est augmentée de $$1$$ point, sans dépasser $$20$$ .

Partie C : assemblage modulaire\\[2pt]

Écrire bilan(L) qui réutilise les fonctions précédentes et renvoie un texte du type : « Moyenne : 11.1 ; Min : 6 ; Max : 18 ; Admis : 4/7 ».
Expliquer en deux phrases pourquoi découper en petites fonctions (plutôt qu'un seul long bloc) rend le programme plus sûr et plus réutilisable.

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Démonstration

def parite(n):
    if n 
        return "pair"
    else:
        return "impair"

Le test n % 2 == 0 vérifie que le reste de la division par $$2$$ est nul. Noter le double égal == (test) et le : suivi de l'indentation.

Corrigé 5

Démonstration

On parcourt la liste et on compte :

def compte_pairs(L):
    c = 0
    for x in L:
        if x 
            c = c + 1
    return c

On itère directement sur les éléments (for x in L) car la position ne sert pas. c compte les nombres pairs rencontrés.

Corrigé 6

Démonstration

cubes = [k**3 for k in range(1, 11)]        # 1 a 10 inclus
mult3 = [k for k in range(0, 31) if k

Pour aller jusqu'à $$10$$ inclus, on écrit range(1, 11). La condition if k%3==0 ne garde que les multiples de $$3$$ . Résultats : [1, 8, 27, ..., 1000] et [0, 3, 6, ..., 30].

Corrigé 7

Démonstration

def somme_positifs(L):
    s = 0
    for x in L:
        if x > 0:
            s = s + x
    return s

On n'ajoute x à la somme que s'il est strictement positif. Par exemple sur [3, -2, 5, -7] on obtient $$3+5=8$$ .

Corrigé 8

Démonstration

def table(n):
    return [n * k for k in range(1, 11)]

La compréhension construit [n*1, n*2, ..., n*10]. On pouvait aussi partir d'une liste vide et faire append dans une boucle : les deux méthodes sont équivalentes.

Corrigé 9

Démonstration

On retient à la fois la valeur du maximum et son indice :

def indice_max(L):
    imax = 0
    for i in range(len(L)):
        if L[i] > L[imax]:
            imax = i
    return imax

On compare chaque élément L[i] au meilleur trouvé L[imax]. L'inégalité stricte > garantit qu'en cas d'égalité on garde le premier indice. Ici on parcourt par indices car c'est la position qu'on veut renvoyer.

Corrigé 10

Démonstration

def seuil(S):
    u = 2          # u_0
    n = 0
    while u <= S:
        u = 1.5 * u    # u_{n+1} = 1.5 u_n
        n = n + 1
    return n

La suite est géométrique de raison $$1{,}5>1$$ , donc elle croît sans limite : le while finit toujours par s'arrêter. On compte dans n le nombre d'étapes jusqu'à dépasser S. Par exemple seuil(10) renvoie $$4$$ (car $u_0=2,\,u_1=3,\,u_2=4{,}5,\,u_3=6{,}75,\,u_4=10{,}125>10$ ).

Corrigé 11

Démonstration

def est_present(x, L):
    for valeur in L:
        if valeur == x:
            return True   # trouve : on sort tout de suite
    return False          # parcours fini sans trouver

Dès qu'on trouve x, le return True arrête la fonction (inutile de continuer). Si la boucle se termine sans rien trouver, on renvoie False.

Corrigé 12

Démonstration

1(a). « $$n$$ multiple de $4\Rightarrow n$ pair » : vraie (tout multiple de $$4$$ est multiple de $$2$$ ). Réciproque : « $$n$$ pair $\Rightarrow n$ multiple de $$4$$ » : fausse ( $$n=2$$ est pair mais pas multiple de $$4$$ ).

1(b). « $x>3\Rightarrow x>1$ » : vraie. Réciproque : « $x>1\Rightarrow x>3$ » : fausse ( $$x=2$$ ).

1(c). « $x^2=9\Rightarrow x=3$ » : fausse (contre-exemple $$x=-3$$ ). Réciproque : « $x=3\Rightarrow x^2=9$ » : vraie.

2. Les négations sont :

« il existe au moins un élève qui n'a pas réussi » ;
« aucun entier pair n'est supérieur à $$100$$ » ;
« $x\leqslant0$ ou $x\geqslant2$ ».

3. Soit $$n$$ un entier. S'il est pair, alors $$n(n+1)$$ contient le facteur pair $$n$$ . S'il est impair, alors $$n+1$$ est pair et le produit contient le facteur pair $$n+1$$ . Les deux cas couvrent tous les entiers ; donc $$n(n+1)$$ est toujours pair.

4. Prouvons la contraposée. Si $$n$$ est impair, il existe $k\in\Z$ tel que $$n=2k+1$$ . Alors

\[n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1,\]

donc $$n^2$$ est impair. La contraposée est vraie ; ainsi $$n^2$$ pair implique $$n$$ pair.

5. Supposons qu'un entier $$n$$ soit pair et impair. Il existe alors $p,q\in\Z$ tels que $$n=2p$$ et $$n=2q+1$$ . Donc $$2p=2q+1$$ , soit $$2(p-q)=1$$ . Le membre de gauche est pair, celui de droite impair : contradiction. Un tel entier n'existe pas.

Leçon : une implication et sa réciproque sont indépendantes ; la contraposée est en revanche équivalente à l'implication initiale.

Corrigé 13

Démonstration

def est_premier(n):
    if n < 2:
        return False
    for d in range(2, n):       # diviseurs possibles
        if n 
            return False        # un diviseur trouve : pas premier
    return True

def premiers_jusqua(N):
    return [n for n in range(2, N + 1) if est_premier(n)]

est_premier cherche un diviseur entre $$2$$ et $$n-1$$ : s'il en trouve un, $$n$$ n'est pas premier. premiers_jusqua réutilise cette fonction dans une compréhension (programmation modulaire). Par exemple premiers_jusqua(20) renvoie [2, 3, 5, 7, 11, 13, 17, 19].

Corrigé 14

Démonstration

from random import randint

def moyenne_somme(n):
    total = 0
    for _ in range(n):
        total += randint(1, 6) + randint(1, 6)   # somme de 2 des
    return total / n

D'après la fiche 10, l'espérance de la somme de deux dés vaut $$7$$ . Par la loi des grands nombres, moyenne_somme(n) se rapproche de $\boxed{7}$ quand n devient grand.

Corrigé 15

Démonstration

On parcourt L de la fin vers le début en ajoutant dans une nouvelle liste :

def renverse(L):
    R = []
    for i in range(len(L) - 1, -1, -1):   # de len-1 jusqu'a 0
        R.append(L[i])
    return R

range(len(L)-1, -1, -1) compte à rebours : indice de départ len(L)-1, on s'arrête avant $$-1$$ (donc à $$0$$ ), pas de $$-1$$ . Par exemple renverse([1,2,3]) renvoie [3, 2, 1].

Corrigé 16

Démonstration

1.

def intersection(A, B):
    R = []
    for x in A:
        if x in B and x not in R:   # dans B, et pas deja pris
            R.append(x)
    return R

On garde un élément de A s'il est aussi dans B (condition x in B) et pas déjà ajouté (évite les doublons). Cela réalise l'intersection d'ensembles, notée $A\cap B$ en mathématiques. Par exemple intersection([1,2,3,2], [2,3,5]) renvoie [2, 3].

2.

def produit_cartesien(A, B):
    couples = []
    for x in A:
        for y in B:
            couples.append((x, y))
    return couples

Pour chacun des $$p$$ choix de $$x$$ , il existe $$q$$ choix possibles de $$y$$ . Le principe multiplicatif donne donc $p\times q$ couples. On peut aussi écrire en compréhension :

def produit_cartesien(A, B):
    return [(x, y) for x in A for y in B]

Corrigé du problème type prépa

Démonstration · Partie A : les briques de base

def moyenne(L):
    return sum(L) / len(L)

def maximum(L):
    m = L[0]
    for x in L:
        if x > m:
            m = x
    return m

def minimum(L):
    m = L[0]
    for x in L:
        if x < m:
            m = x
    return m

def nb_admis(L):
    c = 0
    for note in L:
        if note >= 10:
            c = c + 1
    return c

Chaque fonction fait une seule chose et la renvoie. On peut les tester isolément, par exemple maximum([12, 8, 15]) doit donner $$15$$ .

Démonstration · Partie B : compréhensions et sélection

# 4. notes >= 10 en une ligne
def admis(L):
    return [note for note in L if note >= 10]

# 5. +1 point, plafonne a 20
def ajuste(L):
    return [min(note + 1, 20) for note in L]

La compréhension de la question 4 se lit « les notes telles que note $\geqslant 10$ ». Pour la question 5, min(note + 1, 20) garantit qu'on ne dépasse jamais $$20$$ : un $$20$$ reste $$20$$ , un $$19$$ devient $$20$$ , un $$12$$ devient $$13$$ .

Démonstration · Partie C : assemblage modulaire

def bilan(L):
    moy = round(moyenne(L), 1)
    mini = minimum(L)
    maxi = maximum(L)
    adm = nb_admis(L)
    total = len(L)
    return ("Moyenne : " + str(moy) +
            " ; Min : " + str(mini) +
            " ; Max : " + str(maxi) +
            " ; Admis : " + str(adm) + "/" + str(total))

notes = [12, 8, 15, 10, 6, 18, 9]
print(bilan(notes))
# Moyenne : 11.1 ; Min : 6 ; Max : 18 ; Admis : 4/7

7. Pourquoi découper ? Chaque petite fonction peut être testée et corrigée séparément, ce qui rend les erreurs faciles à localiser ; et une fois sûre, chaque fonction se réutilise dans d'autres programmes sans tout réécrire. Un seul long bloc serait illisible et chaque modification risquerait de tout casser.

Fiche-mémoire

Méthode · Choisir et répéter

if condition:
    action
for k in range(n):
    action
while condition:
    mise_a_jour

Méthode · Fonction

def calcul(x):
    resultat = ...
    return resultat

Maîtrise du chapitre

Validation contrôlée

Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.

Proposition	Sa négation
« Tous les $\(x\)$ vérifient $\(P\)$ »	« Il existe un $\(x\)$ qui ne vérifie pas $\(P\)$ »
« Il existe un $\(x\)$ tel que $\(P\)$ »	« Aucun $\(x\)$ ne vérifie $\(P\)$ »
« $\(P\)$ et $\(Q\)$ »	« (non $\(P\)$ ) ou (non $\(Q\)$ ) »
« $\(P\)$ ou $\(Q\)$ »	« (non $\(P\)$ ) et (non $\(Q\)$ ) »