Ch. 00 · Leçon 1
Fiche récapitulative — Réflexes à avoir au bac
30 minanalyse · python
Affichage du code
Ce que vous saurez faire
- Retrouver en un coup d'œil les 6 traitements canoniques sur tableaux
- Mémoriser les 3 méthodes de tri du programme
- Choisir la bonne structure itérative selon le contexte
- Identifier les fonctions prédéfinies indispensables
Imprime-moi, plie-moi, glisse-moi dans ton classeur
Cette fiche est volontairement dense : tout l'essentiel du programme officiel sur une page. À utiliser comme antisèche autorisée pendant les révisions, jamais à l'examen évidemment.
1. Notation algorithmique tunisienne ↔ Python 3
| Élément | Algorithmique | Python 3 |
|---|---|---|
| Affectation | x ← 5 | x = 5 |
| Comparaison | x = 5 | x == 5 |
| Différent | x ≠ 5 | x != 5 |
| ET / OU / NON | ET, OU, NON | and, or, not |
| Division entière | a div b | a // b |
| Modulo | a mod b | a % b |
| Lecture | Lire(x) | x = int(input()) |
| Écriture | Écrire(x) | print(x) |
| Si | Si C Alors ... FinSi | if C: ... |
| Sinon | Sinon ... FinSi | else: ... |
| Pour | Pour i De a À b Faire ... FinPour | for i in range(a, b + 1): |
| Tant que | Tant que C Faire ... FinTantQue | while C: |
| Répéter | Répéter ... Jusqu'à C | while True: ... if C: break |
2. Choisir la bonne structure itérative
Connaît-on le nombre exact d'itérations à l'avance ?
- OUI →
Pour…Faire- NON → Le corps doit-il s'exécuter au moins une fois ?
- OUI →
Répéter…Jusqu'à- NON →
Tant que…Faire
3. Les 6 traitements canoniques sur tableaux
À connaître par cœur — toute épreuve bac en utilise au moins 2.
| # | Traitement | Initialisation | Corps de boucle |
|---|---|---|---|
| 1 | Somme | s ← 0 | s ← s + T[i] |
| 2 | Produit | p ← 1 | p ← p * T[i] |
| 3 | Maximum | m ← T[0] | Si T[i] > m Alors m ← T[i] |
| 4 | Minimum | m ← T[0] | Si T[i] < m Alors m ← T[i] |
| 5 | Recherche | trouve ← faux | Si T[i] = cible Alors trouve ← vrai |
| 6 | Comptage | nb ← 0 | Si condition(T[i]) Alors nb ← nb + 1 |
Bornes : Algo Pour i De 1 À N Faire, Python for i in range(N): ou for x in T:.
4. Les 3 méthodes de tri
| Méthode | Idée | Pire cas | Stabilité |
|---|---|---|---|
| Sélection | Cherche le min, le place en tête. Itère sur le sous-tableau restant. | O(n²) | Non |
| Bulles | Échange les voisins mal placés. Au moins une passe sans échange = trié. | O(n²) | Oui |
| Insertion | Pour chaque élément, l'insère à sa place dans la partie déjà triée. | O(n²) | Oui |
Optimisation bulles : sortir dès la 1ère passe sans échange. Permet O(n) sur tableau déjà trié.
5. Recherche : séquentielle vs dichotomique
| Séquentielle | Dichotomique | |
|---|---|---|
| Pré-requis | Aucun | Tableau trié |
| Complexité | O(n) | O(log n) |
| Pour n = 10⁶ | ~ 10⁶ comparaisons | ~ 20 comparaisons |
| Implémentation | Boucle Pour + test d'égalité | gauche, droite, milieu + division par 2 |
Mantra dichotomique :
g ← 0 ; d ← N - 1
Tant que g ≤ d Faire
m ← (g + d) div 2
Si T[m] = cible Alors Retourner(m)
Sinon Si T[m] < cible Alors g ← m + 1
Sinon d ← m - 1
FinSi
FinTantQue
Retourner(-1)
6. Échelle de complexité
Du plus rapide au plus lent :
| Complexité | Nom | Exemple |
|---|---|---|
| O(1) | Constante | Accès T[i] |
| O(log n) | Logarithmique | Dichotomie |
| O(n) | Linéaire | Somme, max, recherche séquentielle |
| O(n log n) | Linéarithmique | Tri fusion / rapide (hors programme) |
| O(n²) | Quadratique | Tris du programme (sélection, bulles, insertion) |
| O(2ⁿ) | Exponentielle | Combinatoire (hors programme) |
Limites pratiques :
- O(n²) inutilisable au-delà de n ≈ 10⁵ (sinon > 1 sec).
- O(n log n) tient jusqu'à n ≈ 10⁹.
7. Fonctions prédéfinies — top 20
Numériques
| Fonction | Effet |
|---|---|
abs(x) | Valeur absolue |
int(x) | Conversion en entier (tronque) |
float(x) | Conversion en réel |
round(x, n) | Arrondi à n décimales |
max(a, b, ...) | Maximum |
min(a, b, ...) | Minimum |
math.sqrt(x) | Racine carrée (requiert import math) |
math.floor(x) | Plus grand entier ≤ x |
math.ceil(x) | Plus petit entier ≥ x |
random.randint(a, b) | Entier aléatoire ∈ [a, b] inclus |
Chaînes
| Fonction | Effet |
|---|---|
len(ch) | Longueur |
ch.upper() / ch.lower() | Majuscules / minuscules |
ch.find(s) | Position de s (-1 si absent) |
ch.count(s) | Nombre d'occurrences |
ch.replace(a, b) | Remplace a par b |
ch.split(sep) | Découpe en liste |
ch.strip() | Enlève les espaces en bord |
c.isalpha() / c.isdigit() | Test lettre / chiffre |
chr(n) / ord(c) | Code ASCII ↔ caractère |
keyword.iskeyword(ch) | Test si ch est un mot-clé Python |
8. Sous-programmes : procédure vs fonction
| Procédure | Fonction | |
|---|---|---|
| Retourne une valeur ? | Non (ou via VAR) | Oui, via Retourner / return |
| Algo | Procédure nom(params) ... FinProcedure | Fonction nom(params) → type ... FinFonction |
| Python | def nom(params): ... (sans return) | def nom(params) -> type: return ... |
| Quand l'utiliser ? | Effet de bord (afficher, modifier) | Calcul renvoyant un résultat |
| Appel | nom(args) (instruction) | x ← nom(args) (expression) |
Paramètres en algorithmique :
- Par valeur (défaut) : le sous-programme reçoit une copie.
- Par variable (
VAR) : le sous-programme peut modifier l'original.
9. T.D.O — Format officiel
T.D.O
Objet | Type / Nature | Rôle
--------|----------------------|----------------------
age | Variable / entier | Âge saisi
PI | Constante / réel = 3.14 | Pi
notes | Tableau de N réels | Notes des élèves
N | Constante / entier = 25 | Taille du tableau
Toujours présent dans une copie d'examen. Perte de 2-3 points si oublié.
10. Réflexes anti-erreurs au bac
| Erreur fréquente | Solution |
|---|---|
= au lieu de == en Python | Toujours double-égal pour comparer |
| Indices 0 vs 1 (Python vs algo) | Préciser la convention dans la copie |
| Boucle infinie | Vérifier qu'au moins une variable de la condition est mise à jour |
range(1, N) au lieu de range(1, N+1) | Python exclut la borne supérieure |
| Max initialisé à 0 (négatifs ignorés) | Initialiser avec T[0] |
Cascade Si...Sinon mal ordonnée | Du plus restrictif au plus large (≥ 16 avant ≥ 14) |
| Dichotomie sur tableau non trié | Toujours vérifier le pré-requis |
| Modification de chaîne en Python | Reconstruire (chaînes immuables) |
| Pas de T.D.O dans la copie | -2 à -3 points automatiques |
| Pas de justification du choix de structure | Perte de points même si code correct |
En résumé visuel
4 CHAPITRES OFFICIELS
├── 1. Structures de contrôle I (12h) → conditionnelles + Pour
├── 2. Structures de contrôle II (12h) → Tant que + Répéter
├── 3. Sous-programmes (16h) → procédures + fonctions + tableaux + chaînes
└── 4. Traitements avancés (10h) → recherche + tri + complexité
5 PATTERNS À CONNAÎTRE PAR CŒUR
├── Accumulateur (somme, produit, max, min)
├── Recherche (séquentielle + dichotomique)
├── Tri (sélection, bulles, insertion)
├── Analyse modulaire (décomposer en sous-programmes)
└── Choix itératif (Pour / Tant que / Répéter selon contexte)
3 RÉFLEXES POUR GAGNER 5 POINTS
├── Écrire le T.D.O complet
├── Justifier le choix des structures
└── Tester les cas limites (tableau vide, 1 élément, négatifs)
Bonne préparation. Tu vas y arriver.