Algorithmique et programmation Python – Cours 1re

Les listes en Python

Définition — Liste Python Une liste est une structure de données Python permettant de stocker une collection ordonnée d’éléments. Elle se note entre crochets, les éléments séparés par des virgules.

Créer une liste

# Création de listes
notes = [15, 12, 18, 9, 14]
prenoms = ["Alice", "Bob", "Clara"]
mixte = [1, "bonjour", 3.14, True]
vide = []

# Par compréhension
carrés = [x**2 for x in range(1, 6)] # [1, 4, 9, 16, 25]
pairs = [x for x in range(20) if x % 2 == 0]
  

Accéder aux éléments

notes = [15, 12, 18, 9, 14]

notes[0] # 15 (premier élément, indice 0)
notes[2] # 18 (troisième élément)
notes[-1] # 14 (dernier élément)
notes[-2] # 9 (avant-dernier)
notes[1:4] # [12, 18, 9] (tranche, indices 1 à 3)
  

Attention — Indices à partir de 0 En Python, les indices commencent à 0. Pour une liste de longueur $n$, les indices valides sont $0, 1, \ldots, n-1$. L’accès à un indice hors de cette plage provoque une erreur IndexError.

Modifier une liste

notes = [15, 12, 18]

notes.append(11) # Ajouter en fin : [15, 12, 18, 11]
notes.insert(1, 20) # Insérer à l’indice 1 : [15, 20, 12, 18, 11]
notes.remove(12) # Supprimer la valeur 12
notes.pop(0) # Supprimer et renvoyer l’élément d’indice 0
notes[0] = 16 # Modifier l’élément d’indice 0
  

Parcourir une liste

notes = [15, 12, 18, 9, 14]

# Parcours par valeur
for note in notes:
    print(note)

# Parcours par indice
for i in range(len(notes)):
    print(f"notes[{i}] = {notes[i]}")

# Parcours avec indice et valeur
for i, note in enumerate(notes):
    print(f"notes[{i}] = {note}")
  

Fonctions utiles

Fonction / Méthode	Description	Exemple
`len(liste)`	Longueur	`len([1,2,3]) → 3`
`sum(liste)`	Somme	`sum([1,2,3]) → 6`
`min(liste)`	Minimum	`min([3,1,2]) → 1`
`max(liste)`	Maximum	`max([3,1,2]) → 3`
`sorted(liste)`	Tri (nouvelle liste)	`sorted([3,1,2]) → [1,2,3]`
`liste.sort()`	Tri en place	Modifie la liste
`x in liste`	Appartenance	`2 in [1,2,3] → True`
`liste.count(x)`	Nombre d’occurrences	`[1,2,1].count(1) → 2`

▶ Visualiser pas à pas : recherche du maximum dans une liste

Fonctions Python

Définition — Fonction Python Une fonction est un bloc de code nommé qui prend des paramètres en entrée, exécute une suite d'instructions, et renvoie un résultat avec return. Elle se déclare avec le mot-clé def.

Syntaxe générale

def nom_fonction(paramètre1, paramètre2, ...):
    # Instructions (corps de la fonction)
    return résultat
  

Exemple — Fonction sans paramètre

def salutation():
    return "Bonjour !"

print(salutation()) # Bonjour !
  

Exemple — Fonction à un paramètre

def carré(x):
    return x ** 2

print(carré(5))  # 25
print(carré(7))  # 49
  

Exemple — Fonction à plusieurs paramètres

def moyenne(a, b):
    return (a + b) / 2

print(moyenne(10, 14))    # 12.0

def est_pair(n):
    return n % 2 == 0

print(est_pair(8))   # True
print(est_pair(7))   # False
  

Attention — Variables locales Les variables définies à l'intérieur d'une fonction (paramètres et variables internes) sont locales : elles ne sont accessibles qu'à l'intérieur de la fonction. À l'extérieur, elles n'existent pas.

Propriété — Pourquoi écrire des fonctions ?

Réutilisation : on définit le code une fois, on l'utilise plusieurs fois.
Lisibilité : un programme structuré est plus facile à lire et à corriger.
Tests : on peut tester chaque fonction séparément.
Décomposition : on découpe un problème complexe en sous-problèmes plus simples.

Exemple — Décomposition d'un problème

# Calculer l'IMC d'une personne (poids/taille²)
def imc(poids, taille):
    return poids / taille ** 2

def interprétation(valeur_imc):
    if valeur_imc < 18.5:
        return "insuffisance pondérale"
    elif valeur_imc < 25:
        return "corpulence normale"
    else:
        return "surpoids"

# Programme principal
v = imc(70, 1.75)
print(interprétation(v)) # corpulence normale
  

Tris : sélection et insertion

Un tri consiste à réorganiser les éléments d'une liste pour les ranger par ordre croissant (ou décroissant). Au programme de Première, deux algorithmes simples : le tri par sélection et le tri par insertion.

Tri par sélection

Principe À chaque étape, on cherche le plus petit élément parmi les non triés et on l'échange avec le premier non trié.

def tri_selection(L):
    n = len(L)
    for i in range(n):
        # Cherche l'indice du minimum dans L[i:n]
        i_min = i
        for j in range(i + 1, n):
            if L[j] < L[i_min]:
                i_min = j
        # Échange L[i] et L[i_min]
        L[i], L[i_min] = L[i_min], L[i]
    return L

print(tri_selection([5, 2, 8, 1, 9, 3])) # [1, 2, 3, 5, 8, 9]
  

Tri par insertion

Principe On parcourt la liste de gauche à droite. À chaque étape, on prend l'élément courant et on l'insère à la bonne place dans la partie déjà triée à sa gauche, en décalant les éléments plus grands.

def tri_insertion(L):
    n = len(L)
    for i in range(1, n):
        x = L[i]              # Élément à insérer
        j = i - 1
        while j >= 0 and L[j] > x:
            L[j + 1] = L[j]   # Décalage à droite
            j = j - 1
        L[j + 1] = x         # Insertion à la bonne place
    return L

print(tri_insertion([5, 2, 8, 1, 9, 3])) # [1, 2, 3, 5, 8, 9]
  

💡 Comparaison des deux tris

Les deux tris ont une complexité quadratique en $O(n^2)$ dans le pire cas : pour une liste de $n$ éléments, le nombre d'opérations croît comme $n^2$. Doubler la taille multiplie le temps par 4.
Le tri par insertion est plus rapide sur une liste presque triée (boucle while qui s'arrête vite).
En pratique, on utilise sorted(L) ou L.sort() qui implémentent un algorithme bien plus rapide (Timsort, en $O(n \log n)$).

Vocabulaire ensembliste

Définitions fondamentales

Ensemble : collection d’objets distincts appelés éléments. Notation : $\{1, 2, 3\}$, $\mathbb{R}$, $\mathbb{N}$.
Appartenance : $x \in A$ signifie « $x$ est un élément de $A$ ».
Inclusion : $A \subset B$ signifie « tout élément de $A$ est dans $B$ ».
Intersection : $A \cap B$ contient les éléments qui sont à la fois dans $A$ et dans $B$.
Réunion : $A \cup B$ contient les éléments qui sont dans $A$ ou dans $B$ (ou les deux).
Complémentaire : $\overline{A}$ contient les éléments qui ne sont pas dans $A$.

Exemple Soit $A = \{1, 2, 3, 4\}$ et $B = \{3, 4, 5, 6\}$.
$A \cap B = \{3, 4\}$, $A \cup B = \{1, 2, 3, 4, 5, 6\}$, $2 \in A$, $2 \notin B$, $A \not\subset B$.

Produit cartésien Le produit cartésien $A \times B$ est l’ensemble de tous les couples $(a, b)$ avec $a \in A$ et $b \in B$. $$A \times B = \{(a, b) \mid a \in A \text{ et } b \in B\}$$

Connecteurs logiques

Proposition Une proposition est un énoncé mathématique qui est soit vrai (V), soit faux (F). Une proposition ne peut pas être les deux à la fois.

Connecteur	Notation	Lecture	Vrai quand…
Négation	$\neg P$ ou NON $P$	« non P »	$P$ est fausse
Conjonction	$P \land Q$	« P et Q »	$P$ et $Q$ sont toutes deux vraies
Disjonction	$P \lor Q$	« P ou Q »	Au moins l’une des deux est vraie

Tables de vérité

$P$	$Q$	$\neg P$	$P \land Q$	$P \lor Q$
V	V	F	V	V
V	F	F	F	V
F	V	V	F	V
F	F	V	F	F

Quantificateurs

Quantificateurs

Quantificateur universel $\forall$ : « pour tout ». $\forall x \in E, P(x)$ signifie « pour tout $x$ de $E$, $P(x)$ est vraie ».
Quantificateur existentiel $\exists$ : « il existe ». $\exists x \in E, P(x)$ signifie « il existe au moins un $x$ de $E$ tel que $P(x)$ soit vraie ».

Négation des quantificateurs

La négation de « $\forall x \in E, P(x)$ » est « $\exists x \in E, \neg P(x)$ »
La négation de « $\exists x \in E, P(x)$ » est « $\forall x \in E, \neg P(x)$ »

Justification

Nions chaque proposition en utilisant les définitions des quantificateurs.

Si « pour tout $x \in E$, $P(x)$ » est fausse, cela signifie qu’il n’est pas vrai que tous les éléments vérifient $P$. Donc il existe au moins un élément qui ne la vérifie pas : $\exists x \in E, \neg P(x)$.

Réciproquement, si « il existe $x \in E$ tel que $P(x)$ » est fausse, c’est qu’aucun élément ne vérifie $P$, donc tous les éléments vérifient $\neg P$ : $\forall x \in E, \neg P(x)$. $\square$

Implication et équivalence

Définition — Implication L'implication $P \Rightarrow Q$ (« P implique Q », « si P alors Q ») est fausse uniquement quand $P$ est vraie et $Q$ est fausse.

$P$	$Q$	$P \Rightarrow Q$	$Q \Rightarrow P$ (réciproque)	$\neg Q \Rightarrow \neg P$ (contraposée)
V	V	V	V	V
V	F	F	V	F
F	V	V	F	V
F	F	V	V	V

À remarquer $P \Rightarrow Q$ et sa contraposée $\neg Q \Rightarrow \neg P$ ont exactement les mêmes valeurs de vérité : elles sont logiquement équivalentes. C’est le fondement du raisonnement par contraposée.

Condition nécessaire / suffisante Si $P \Rightarrow Q$ :

$P$ est une condition suffisante de $Q$ (P suffit pour avoir Q)
$Q$ est une condition nécessaire de $P$ (Q est obligatoire pour avoir P)

Exemple « Être divisible par 4 ⟹ être pair ».
Être divisible par 4 est une condition suffisante d’être pair.
Être pair est une condition nécessaire d’être divisible par 4.
La réciproque est fausse : être pair ne suffit pas pour être divisible par 4 (contre-exemple : 6).

Définition — Équivalence L'équivalence $P \Leftrightarrow Q$ (« P si et seulement si Q ») est vraie quand $P$ et $Q$ ont la même valeur de vérité. Elle signifie $(P \Rightarrow Q)$ et $(Q \Rightarrow P)$ simultanément. Quand $P \Leftrightarrow Q$, $P$ est une condition nécessaire et suffisante de $Q$.

Types de raisonnement

Raisonnement direct

Pour démontrer $P \Rightarrow Q$ : on suppose $P$ vraie et on en déduit $Q$ par une suite d’implications.

Raisonnement par contraposée

Pour démontrer $P \Rightarrow Q$ : on démontre la contraposée $\neg Q \Rightarrow \neg P$, qui lui est équivalente.

Exemple — Raisonnement par contraposée Montrer : « Si $n^2$ est pair, alors $n$ est pair. »

Contraposée : « Si $n$ est impair, alors $n^2$ est impair. »
Si $n$ est impair, il existe $k$ entier tel que $n = 2k+1$.
Alors $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$, qui est impair. ✓

Raisonnement par l’absurde

Pour démontrer $P$ : on suppose $\neg P$ et on aboutit à une contradiction.

Contre-exemple

Pour montrer qu’une proposition universelle est fausse, il suffit d’exhiber un contre-exemple (un seul cas où elle est fausse).

Exemple « Tout entier pair est divisible par 4. » → Faux : contre-exemple $n = 6$ (pair mais $6 \div 4 = 1{,}5$, non entier).

À retenir — L’essentiel du chapitre

Les listes Python s’indexent à partir de 0, on les parcourt avec for
$P \Rightarrow Q$ est équivalente à sa contraposée $\neg Q \Rightarrow \neg P$
P suffisante pour Q, Q nécessaire pour P : retenir dans le sens de l’implication
Un seul contre-exemple suffit à réfuter une proposition universelle

✏️ Exercices → 🎯 S’entraîner sur WIMS 📓 Notebook Python →

A voir aussi

Ch2 Second degre Ch3 Suites numériques Ch4 Dérivation

Solution du problème d’ouverture — Trier un million d’utilisateurs

Tri naïf (comparaison de toutes les paires) :

$\dfrac{n^2}{2} = \dfrac{(10^6)^2}{2} = \dfrac{10^{12}}{2} = 5 \times 10^{11}$ opérations

soit environ 500 milliards de comparaisons.

Tri fusion :

$n \log_2 n = 10^6 \times \log_2(10^6)$

Or $\log_2(10^6) = 6 \times \log_2(10) \approx 6 \times 3{,}322 \approx 19{,}93$.

Donc $n \log_2 n \approx 10^6 \times 19{,}93 \approx 2 \times 10^7$ opérations, soit environ 20 millions de comparaisons.

Gain :

$\dfrac{5 \times 10^{11}}{2 \times 10^7} = 25\,000$

Le tri fusion est environ 25 000 fois plus rapide que le tri naïf pour un million d’éléments. Le tri naïf a un coût quadratique (le nombre d’opérations croît comme $n^2$), tandis que le tri fusion a un coût bien moindre (proportionnel à $n \times \log_2 n$).

Solution de l’énigme — Test de primalité

Pour $n = 10\,000$, $\sqrt{n} = 100$ : on effectue au plus 99 divisions. Si $n$ avait un diviseur $d > \sqrt{n}$, alors $n/d < \sqrt{n}$ serait aussi un diviseur — déjà testé. On ne peut donc pas « manquer » un diviseur en s’arrêtant à $\sqrt{n}$.

Bilan — Formules essentielles

Notion	Définition / Formule	Piège à éviter
Listes Python	`[a, b, c]`, `len(L)`, `L.append(x)`, indexation `L[0]`	L’indexation commence à 0, pas à 1
Boucle `for`	`for i in range(n):` — parcourt $i = 0, 1, \ldots, n-1$	`range(n)` s’arrête à $n-1$, pas à $n$
Boucle `while`	`while condition:` — tant que la condition est vraie	Risque de boucle infinie si la condition ne devient jamais fausse
Ensembles de nombres	$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$	$\mathbb{Q}$ contient les fractions, pas seulement les entiers
Implication	$P \Rightarrow Q$ : si $P$ est vraie, alors $Q$ est vraie	La réciproque $Q \Rightarrow P$ n’est pas l’implication
Contraposée	$\text{non}(Q) \Rightarrow \text{non}(P)$ — équivalente à $P \Rightarrow Q$	Ne pas confondre contraposée et réciproque
Raisonnement par l’absurde	On suppose le contraire de ce qu’on veut prouver et on aboutit à une contradiction	Il faut nier correctement la proposition (attention aux quantificateurs)

Pièges et contre-exemples

Algorithmique et logique : teste d’abord ton intuition.

Score : 0 / 6 pièges identifiés

1 Terminer = correct ?

« Un algorithme qui termine donne toujours le bon résultat. »

Cette affirmation est-elle correcte ?

Explication

Faux. Terminer signifie que l’algorithme s’arrête en un nombre fini d’étapes, mais rien ne garantit que le résultat soit correct. Un algorithme peut boucler un nombre fini de fois et renvoyer n’importe quoi.

Terminer ≠ correct. Il faut aussi prouver la correction (le résultat est bien celui attendu).

Mini-test : un algorithme qui renvoie toujours 42 termine-t-il ?

2 Coût d’un algorithme en secondes ?

« Le coût d’un algorithme se mesure en secondes. »

Cette affirmation est-elle correcte ?

Explication

Faux. Le coût d’un algorithme se mesure en nombre d’opérations élémentaires en fonction de la taille $n$ de l’entrée, indépendamment de la machine utilisée.

Le coût est une mesure abstraite (nombre d’opérations), pas un temps concret. Un même algorithme tourne plus vite sur un ordinateur rapide, mais le nombre d’opérations reste le même.

Mini-test : dire qu’un algorithme a un « coût quadratique » signifie :

3 Deux boucles imbriquées = coût quadratique ?

« Deux boucles imbriquées donnent toujours un coût quadratique. »

Cette affirmation est-elle correcte ?

Explication

Faux. Cela dépend des bornes de chaque boucle. Si la boucle interne fait un nombre constant d’itérations (par exemple 3), le coût reste linéaire (proportionnel à $n$). Le coût n’est quadratique que si les deux boucles dépendent de $n$.

Toujours vérifier les bornes effectives de chaque boucle avant de conclure.

Mini-test : for i in range(n): for j in range(3): a un coût :

4 Tri par sélection toujours plus rapide que tri à bulles ?

« Un tri par sélection est toujours plus rapide qu’un tri à bulles. »

Cette affirmation est-elle correcte ?

Explication

Faux. Les deux ont le même coût quadratique en moyenne et dans le pire cas. Le tri à bulles peut même être plus rapide sur une liste déjà presque triée : il suffit d’un seul parcours (coût linéaire) pour vérifier que tout est en ordre.

Tri par sélection et tri à bulles : même coût quadratique en général. La vitesse dépend des données.

Mini-test : quel est le meilleur cas du tri à bulles optimisé ?

5 Recherche dichotomique sur toute liste ?

« La recherche dichotomique fonctionne sur toute liste. »

Cette affirmation est-elle correcte ?

Explication

Faux. La recherche dichotomique ne fonctionne que sur une liste triée. Sur une liste non triée, le principe de division par deux ne permet pas de savoir dans quelle moitié chercher.

Recherche dichotomique = liste triée obligatoire. Sinon, utiliser une recherche linéaire.

Mini-test : on cherche 5 dans [1, 7, 3, 9, 2]. Peut-on utiliser la dichotomie ?

6 Coût de la recherche dichotomique

« Pour chercher dans une liste triée de 1 million d’éléments, la recherche dichotomique a besoin d’au plus 20 étapes. »

Cette affirmation est-elle correcte ?

Explication

C’est vrai ! À chaque étape, on divise l’intervalle de recherche par 2. Après $k$ étapes, il reste $n/2^k$ éléments. On s’arrête quand il ne reste qu’un élément, soit $k = \log_2 n$. Pour $n = 10^6$, $\log_2(10^6) \approx 20$.

Diviser par 2 à chaque étape : le nombre d’étapes est $\log_2 n$. C’est spectaculairement efficace — 20 étapes suffisent pour un million d’éléments !

Mini-test : pour une liste de 1024 éléments, combien d’étapes au maximum ?

\(P\)	\(Q\)	\(\neg P\)	\(P \land Q\)	\(P \lor Q\)
V	V	F	V	V
V	F	F	F	V
F	V	V	F	V
F	F	V	F	F

\(P\)	\(Q\)	\(P \Rightarrow Q\)	\(Q \Rightarrow P\) (réciproque)	\(\neg Q \Rightarrow \neg P\) (contraposée)
V	V	V	V	V
V	F	F	V	F
F	V	V	F	V
F	F	V	V	V

Chapitre 1 — Algorithmique et logique

Algorithmique et raisonnement logique

Trier un million d’utilisateurs

D’Al-Khwarizmi à la cryptanalyse d’Al-Kindi

Test de primalité

Objectifs du chapitre

Sommaire

Les listes en Python

Créer une liste

Accéder aux éléments

Modifier une liste

Parcourir une liste

Fonctions utiles

Fonctions Python

Syntaxe générale

Exemple — Fonction sans paramètre

Exemple — Fonction à un paramètre

Exemple — Fonction à plusieurs paramètres

Exemple — Décomposition d'un problème

Tris : sélection et insertion

Tri par sélection

Tri par insertion

Vocabulaire ensembliste

Connecteurs logiques

Tables de vérité

Quantificateurs

Implication et équivalence

Types de raisonnement

Raisonnement direct

Raisonnement par contraposée

Raisonnement par l’absurde

Contre-exemple

A voir aussi

Bilan — Formules essentielles

Pièges et contre-exemples

Connecteur	Notation	Lecture	Vrai quand…
Négation	\(\neg P\) ou NON \(P\)	« non P »	\(P\) est fausse
Conjonction	\(P \land Q\)	« P et Q »	\(P\) et \(Q\) sont toutes deux vraies
Disjonction	\(P \lor Q\)	« P ou Q »	Au moins l’une des deux est vraie