Cours — Algorithmique & programmation (Python)
Variables • affectation • entrées/sorties • tests • boucles • fonctions simples • simulation • probabilités/statistiques.
1) Objectifs et état d’esprit “maths + code”
Compétences attendues (2nde)
- Traduire un problème en algorithme (étapes logiques).
- Utiliser variables + affectation + calculs.
- Écrire des tests (conditions) et des boucles (répétitions).
- Lire/écrire des données (entrée/sortie), vérifier les types.
- Simuler une situation numérique/statistique (fréquences, estimations).
- Vérifier un programme : cas limites, invariants, tests.
Pièges fréquents (qui font perdre des points)
- Confondre = (affectation en Python) et == (test d’égalité).
- Oublier l’indentation (bloc if, for, while).
- Arrêter une boucle trop tôt (erreur off-by-one : 0..n-1 vs 1..n).
- Ne pas gérer les cas limites : \(n=0\), liste vide, division par 0, etc.
- Faire une simulation sans nombre d’essais suffisant (variabilité trop grande).
Règle d’or : en maths, on justifie; en code, on teste. Un programme “qui marche sur un exemple” n’est pas prouvé.
2) Qu’est-ce qu’un algorithme ?
Définition
Un algorithme est une suite finie d’instructions qui transforme des entrées en sorties.
En maths, on s’intéresse à :
- la correction (donne la bonne réponse),
- la terminaison (s’arrête),
- l’efficacité (nombre d’opérations).
Schéma “Entrée → Traitement → Sortie”
| Étape | Exemple concret |
|---|---|
| Entrées | Un entier \(n\), une liste de notes, un nombre réel \(x\). |
| Traitement | Calculer une somme, une moyenne, tester une condition, simuler une expérience. |
| Sorties | Un résultat (nombre), un message, une décision (Vrai/Faux). |
Exemple “maths” — Somme des \(n\) premiers entiers
Objectif : calculer \(S=1+2+\cdots+n\).
# Version algorithmique (boucle)
S = 0
for k in range(1, n+1):
S = S + k
Vérification rapide : si \(n=4\), alors \(S=10\). (On peut comparer avec la formule \(S=\dfrac{n(n+1)}{2}\).)
3) Variables, types et expressions
Variable = “boîte” qui contient une valeur
Une variable a :
- un nom (ex : n, x, somme)
- une valeur (ex : 12, 3.5, True)
- un type (entier, réel, booléen, chaîne, liste…)
Types usuels en Python (2nde)
| Type | Exemples |
|---|---|
| int | 0, 7, −12 |
| float | 3.14, −0.5 |
| bool | True, False |
| str | "bonjour", "2nde" |
| list | [12, 15, 9, 18] |
Très important : en Python, / fait une division “réelle”.
Pour la division entière et le reste : // et %.
Exemple — Division entière & reste (piège classique)
Pour \(a=17\) et \(b=5\) :
a = 17
b = 5
q = a // b # quotient entier
r = a % b # reste
# ici q = 3 et r = 2 car 17 = 5×3 + 2
L’écriture mathématique correspondante : \(\boxed{17 = 5\times 3 + 2}\).
4) Affectation : donner une valeur à une variable
Affectation en Python
En Python, = signifie “je stocke le résultat dans la variable”.
Exemple : x = 2*x + 1 veut dire : “nouveau \(x\) = \(2x+1\)”.
Différence avec un test
- x = 5 : affectation
- x == 5 : test (Vrai/Faux)
Erreur : écrire if x = 5: (interdit).
Exemple “suite” — Itération \(u_{n+1}=2u_n-3\)
On veut calculer \(u_0\), puis \(u_1,\dots,u_n\).
u = u0
for k in range(n):
u = 2*u - 3
# à la fin : u contient u_n
Piège : la boucle range(n) fait exactement \(n\) étapes : \(k=0,1,\dots,n-1\).
5) Entrées / sorties : lire, afficher, convertir
Afficher
print("Bonjour")
print("x =", x)
print("Somme =", S)
On peut aussi formater :
print(f"u_n = {u}")
Lire (et convertir !)
s = input("Entrer un entier n : ")
n = int(s) # conversion str → int
Piège : input() renvoie toujours une chaîne (str).
Donc "2" + "3" = "23" (concaténation), ce n’est pas 5.
Exemple piégé — Addition “fausse” si on oublie int()
a = input("a : ")
b = input("b : ")
print(a + b) # concatène deux textes
Correction :
a = int(input("a : "))
b = int(input("b : "))
print(a + b)
6) Tests (conditions) : if / elif / else
Comparaisons
| Opérateur | Signification |
|---|---|
| == | égalité |
| != | différent |
| <, <= | inférieur (strict / large) |
| >, >= | supérieur (strict / large) |
Connecteurs logiques
# and : ET (les deux vraies)
# or : OU (au moins une vraie)
# not : NON (inverse)
if (x >= 0) and (x <= 1):
print("x appartient à [0 ; 1]")
Notation FR : “\(x\in[0 ; 1]\)” correspond bien à 0 <= x <= 1.
Exemple “maths” — Parité + multiple (niveau piège)
Objectif : afficher un message selon \(n\) :
- “multiple de 6” si \(6\mid n\)
- sinon “pair” si \(2\mid n\)
- sinon “multiple de 3” si \(3\mid n\)
- sinon “aucun”
if n % 6 == 0:
print("multiple de 6")
elif n % 2 == 0:
print("pair")
elif n % 3 == 0:
print("multiple de 3")
else:
print("aucun")
Pourquoi cet ordre ? Parce que “multiple de 6” est plus précis (il implique pair et multiple de 3).
7) Boucles : répéter sans se tromper
Boucle for (nombre d’itérations connu)
# k prend 0,1,2,...,n-1
for k in range(n):
...
# k prend 1,2,...,n
for k in range(1, n+1):
...
Piège off-by-one : range(n) a n valeurs, mais la dernière est n−1.
Boucle while (arrêt conditionnel)
# tant que la condition est vraie, on répète
while condition:
...
Danger : si la condition ne devient jamais fausse → boucle infinie.
Il faut un “mécanisme” de sortie (compteur, mise à jour).
Exemple — Factorielle \(n!\) (avec contrôle des cas limites)
On veut calculer \(n!=1\times2\times\cdots\times n\), avec \(0!=1\).
# précondition : n est un entier >= 0
p = 1
for k in range(2, n+1):
p = p * k
# à la fin : p = n!
Vérification : \(0!\Rightarrow\) boucle vide ⇒ \(p=1\) (correct). \(5!\Rightarrow 120\).
Exemple “hard” — Plus petit \(k\) tel que \(1+\frac12+\cdots+\frac1k > 4\)
On cherche le plus petit entier \(k\) tel que \(H_k>4\) (où \(H_k\) est la somme harmonique).
k = 0
S = 0.0
while S <= 4:
k = k + 1
S = S + 1.0/k
print(k, S)
Idée maths : c’est une recherche par “seuil” : la boucle s’arrête au premier dépassement.
8) Fonctions (pour structurer et éviter les erreurs)
Pourquoi faire des fonctions ?
- Réutiliser du code sans copier-coller.
- Clarifier : chaque fonction fait une tâche.
- Tester plus facilement.
Syntaxe
def nom_fonction(param1, param2):
# calculs...
return resultat
Contrat : préciser ce que la fonction attend (entrées) et garantit (sortie).
Exemple — Fréquence d’un événement dans une liste (utile en proba)
On veut calculer la fréquence d’une valeur a dans une liste L.
def frequence(L, a):
# renvoie un nombre entre 0 et 1
if len(L) == 0:
return 0.0
c = 0
for x in L:
if x == a:
c = c + 1
return c / len(L)
Propriété : la valeur renvoyée appartient à \([0 ; 1]\).
9) Simulation numérique / statistique (Monte Carlo)
Principe
Une simulation répète une expérience aléatoire un grand nombre de fois.
La fréquence observée se stabilise vers la probabilité quand le nombre d’essais augmente.
Attention : une simulation n’est pas une preuve, mais un outil d’estimation / de vérification.
Aléatoire en Python
import random
# entier aléatoire uniforme dans {1,2,3,4,5,6}
d = random.randint(1, 6)
# nombre réel aléatoire uniforme dans [0 ; 1[
u = random.random()
Interprétation : random() renvoie \(u\in[0 ; 1[\).
Structure typique
N = 10000
c = 0
for i in range(N):
# 1) simuler
# 2) tester l'événement
# 3) compter
...
freq = c / N
Plus \(N\) est grand, plus l’estimation est stable (en général).
Exemple 1 — Estimer \(P(\text{obtenir un 6})\) au dé
import random
N = 20000
c = 0
for i in range(N):
d = random.randint(1, 6)
if d == 6:
c = c + 1
freq = c / N
print(freq)
Théorie : \(P(6)=\dfrac{1}{6}\approx 0{,}1667\). La fréquence doit être proche de 0.167.
Exemple 2 (hard) — Probabilité d’au moins un 6 en 4 lancers
Événement \(A\) : “au moins un 6 en 4 lancers”.
import random
N = 50000
c = 0
for i in range(N):
ok = False
for k in range(4):
d = random.randint(1, 6)
if d == 6:
ok = True
if ok:
c = c + 1
freq = c / N
print(freq)
Vérification théorique (proba contraire) :
“au moins un 6” = contraire de “aucun 6”.
\(P(\text{aucun 6})=\left(\dfrac{5}{6}\right)^4\). Donc
\[ P(A)=1-\left(\frac{5}{6}\right)^4. \]
“au moins un 6” = contraire de “aucun 6”.
\(P(\text{aucun 6})=\left(\dfrac{5}{6}\right)^4\). Donc
\[ P(A)=1-\left(\frac{5}{6}\right)^4. \]
Exemple 3 (très solide) — Estimer \(\pi\) (méthode du quart de disque)
On tire \((x,y)\) uniformément dans le carré \([0 ; 1]\times[0 ; 1]\).
On compte ceux qui vérifient \(x^2+y^2\le 1\) (quart de disque).
import random
N = 200000
c = 0
for i in range(N):
x = random.random()
y = random.random()
if x*x + y*y <= 1:
c = c + 1
pi_est = 4 * c / N
print(pi_est)
Lecture géométrique : \(\dfrac{c}{N}\approx\) aire(quart de disque) / aire(carré) \(=\dfrac{\pi/4}{1}\).
10) Debug : rendre un programme fiable
Méthode de base (très efficace)
- Cas simples : tester sur de petites valeurs (ex : \(n=0,1,2\)).
- Cas limites : liste vide, seuil exact, division, valeurs négatives.
- Traces : afficher des variables-clés à chaque étape.
- Invariants : une propriété vraie à chaque tour de boucle (ex : “S est la somme des k premiers”).
Erreurs typiques
- Indentation incorrecte : le bloc n’est pas celui qu’on croit.
- Condition inversée (<= au lieu de <).
- Variable non initialisée (ou initialisée au mauvais endroit).
- Compteur mal mis à jour (boucle infinie).
Exemple — Bug “off-by-one” sur une somme
Objectif : somme de 1 à \(n\).
Faux :
S = 0
for k in range(1, n): # s'arrête à n-1
S = S + k
Correct :
S = 0
for k in range(1, n+1):
S = S + k
11) Mini-formulaire Python (à connaître par cœur)
Tests
if condition:
...
elif autre_condition:
...
else:
...
# Comparaisons : == != < <= > >=
# Logique : and / or / not
Boucles
for k in range(n): # 0..n-1
...
for k in range(1, n+1): # 1..n
...
while condition:
...
Listes (très utile en stats)
L = [12, 15, 9]
len(L) # taille
L.append(18)
for x in L:
...
# somme (sans bibliothèque)
S = 0
for x in L:
S = S + x
moy = S / len(L) if len(L) > 0 else 0
Aléatoire (simulation)
import random
random.randint(a, b) # entier dans {a,...,b}
random.random() # réel dans [0 ; 1[
# schéma fréquence
N = 10000
c = 0
for i in range(N):
...
freq = c / N
Checklist “programme propre”
- Je précise les entrées (type attendu) et la sortie.
- J’initialise toutes les variables (compteurs, sommes) au bon endroit.
- Je traite les cas limites : \(n=0\), liste vide, seuil exact.
- Je vérifie les boucles : bornes (range) et mise à jour (while).
- Pour une simulation : je choisis un \(N\) assez grand et j’interprète la variabilité.
Notation FR rappel : intervalles \([a ; b]\) et \([a ; b[\) (pas de virgule).