Mathématiques · Terminale · Calcul Intégral · 3e Trimestre

Complexité et optimisation algorithmique

Les élèves analysent l'efficacité des algorithmes mathématiques en termes de complexité et d'optimisation.

• Programmes Officiels
• EDNAT: MAT.TLE.87
• EDNAT: MAT.TLE.88

À propos de ce thème

L'analyse de la complexité algorithmique permet d'évaluer l'efficacité d'un programme indépendamment de la machine qui l'exécute. En Terminale, les élèves apprennent à compter le nombre d'opérations élémentaires (additions, comparaisons, affectations) en fonction de la taille de l'entrée n. La notation O(n), O(n²), O(log n) fournit un cadre pour comparer les algorithmes et justifier les choix d'implémentation. Ce chapitre fait le pont entre les mathématiques pures et l'informatique appliquée.

La comparaison entre algorithmes récursifs et itératifs est un thème central : un algorithme récursif peut être plus élégant mais plus coûteux en mémoire (pile d'appels) et en temps si des calculs sont répétés inutilement. La mémoïsation et la programmation dynamique offrent des solutions, mais elles sortent du cadre strict du programme. Les activités pratiques, où les élèves mesurent les temps d'exécution réels en Python et les comparent aux prédictions théoriques, ancrent la théorie dans l'expérience concrète.

Questions clés

1. Comment mesurer le temps d'exécution d'un script Python?
2. Pourquoi un algorithme récursif peut-il être plus lent qu'un itératif?
3. Comment réduire le nombre d'opérations dans un calcul de somme?

Objectifs d'apprentissage

• Calculer la complexité temporelle d'un algorithme simple en utilisant la notation asymptotique O(n).
• Comparer l'efficacité de deux algorithmes pour résoudre le même problème, en justifiant le choix basé sur leur complexité.
• Expliquer pourquoi un algorithme récursif peut présenter une complexité différente d'un algorithme itératif pour une tâche identique.
• Identifier les opérations coûteuses dans un algorithme et proposer des pistes d'optimisation pour réduire le nombre d'appels.
• Analyser l'impact de la taille de l'entrée sur le temps d'exécution d'un algorithme donné.

Avant de commencer

Structures de contrôle (boucles et conditions)

Pourquoi : Les élèves doivent maîtriser les boucles (for, while) et les structures conditionnelles (if, else) pour comprendre et écrire des algorithmes itératifs.

Introduction à la récursivité

Pourquoi : Une compréhension de base de la récursivité, y compris la notion de cas de base et d'appel récursif, est nécessaire pour analyser les algorithmes récursifs.

Bases de la programmation Python

Pourquoi : La capacité à lire, écrire et exécuter des scripts Python simples est fondamentale pour les activités pratiques d'analyse de complexité.

Vocabulaire clé

Complexité temporelle	Mesure du temps d'exécution d'un algorithme en fonction de la taille de l'entrée, souvent exprimée à l'aide de la notation O.
Notation O (grand O)	Notation mathématique utilisée pour décrire la borne supérieure de la croissance d'une fonction, indiquant la complexité d'un algorithme dans le pire des cas.
Algorithme récursif	Algorithme qui s'appelle lui-même pour résoudre des sous-problèmes plus petits, jusqu'à atteindre un cas de base.
Algorithme itératif	Algorithme qui utilise des boucles (comme 'for' ou 'while') pour répéter une séquence d'instructions jusqu'à ce qu'une condition soit remplie.
Opération élémentaire	Une opération de base effectuée par un algorithme, telle qu'une addition, une comparaison ou une affectation, dont on compte le nombre pour évaluer la complexité.

Attention à ces idées reçues

Idée reçue courante

Un algorithme récursif est toujours plus lent qu'un itératif.

Ce qu'il faut enseigner à la place

La récursivité n'est pas intrinsèquement plus lente. C'est la répétition de calculs identiques (comme dans Fibonacci naïf) qui cause le ralentissement. Avec mémoïsation, un algorithme récursif peut avoir la même complexité qu'un itératif. Les mesures de temps en groupe illustrent cette nuance.

Idée reçue courante

La complexité O(n²) signifie que l'algorithme fait exactement n² opérations.

Ce qu'il faut enseigner à la place

La notation O donne un ordre de grandeur asymptotique, pas un compte exact. O(n²) signifie que le nombre d'opérations croît proportionnellement à n² pour de grandes valeurs de n. Les constantes et termes de degré inférieur sont négligés. Les courbes tracées en groupe montrent cette convergence vers le comportement asymptotique.

Idée reçue courante

Mesurer le temps d'exécution suffit pour déterminer la complexité.

Ce qu'il faut enseigner à la place

Le temps d'exécution dépend de la machine, du système d'exploitation et des données. La complexité théorique est un modèle abstrait. Les activités comparatives montrent que les mesures suivent la tendance théorique mais avec des variations dues à l'environnement d'exécution.

Idées d'apprentissage actif

Cercle de recherche: Course d'algorithmes

Les groupes implémentent en Python deux algorithmes résolvant le même problème (par exemple tri par insertion vs tri par sélection). Ils mesurent les temps d'exécution pour des listes de taille croissante (100, 1000, 10000) et tracent les courbes. Comparaison collective des résultats avec les complexités théoriques.

45 min·Petits groupes

Penser-Partager-Présenter: Récursif vs itératif

Présentez le calcul de Fibonacci en version récursive et itérative. Chaque élève compte le nombre d'appels pour n=5 dans chaque version. En binôme, ils comparent et expliquent pourquoi la version récursive explose. Discussion collective sur la mémoïsation comme solution.

25 min·Binômes

Galerie marchande: Reconnaître la complexité

Six stations présentent des boucles Python (simple, imbriquée, logarithmique, etc.). Les groupes identifient la complexité de chaque code, justifient leur réponse et classent les algorithmes du plus rapide au plus lent. Tournée de validation entre groupes.

30 min·Petits groupes

Défi individuel : Optimiser une somme

Chaque élève reçoit un script Python calculant une somme avec une boucle imbriquée (O(n²)) et doit le réécrire en O(n) en utilisant une formule directe. Comparaison des temps d'exécution avant/après pour valider l'optimisation.

20 min·Individuel

Liens avec le monde réel

• Les développeurs de moteurs de recherche comme Google utilisent l'analyse de complexité pour optimiser les algorithmes de tri et de recherche, afin de fournir des résultats pertinents en quelques millisecondes, même avec des milliards de pages web.
• Dans le domaine de la finance, les traders algorithmiques emploient des algorithmes dont la rapidité d'exécution est cruciale. Une optimisation de quelques microsecondes peut faire la différence entre un profit et une perte sur des marchés très volatils.
• La conception de jeux vidéo repose sur des algorithmes d'intelligence artificielle et de rendu graphique. L'optimisation de ces algorithmes est essentielle pour assurer une fluidité d'image (framerate) élevée sur diverses plateformes matérielles.

Idées d'évaluation

Vérification rapide

Présentez aux élèves le code Python d'un algorithme simple (par exemple, recherche linéaire). Demandez-leur d'identifier les opérations élémentaires et de déterminer la complexité temporelle en notation O. Ils doivent justifier leur réponse en comptant le nombre d'opérations en fonction de la taille de l'entrée n.

Question de discussion

Posez la question suivante : 'Pourquoi un algorithme qui semble plus court ou plus élégant (par exemple, récursif) peut-il être moins performant qu'un algorithme plus long (par exemple, itératif) pour le même problème ?' Encouragez les élèves à utiliser les concepts de pile d'appels et de calculs répétés dans leurs réponses.

Billet de sortie

Donnez aux élèves un problème simple (par exemple, calculer la somme des n premiers entiers). Demandez-leur d'écrire deux algorithmes différents pour le résoudre : un itératif et un récursif. Ils doivent ensuite comparer leur complexité temporelle et indiquer lequel ils choisiraient pour une très grande valeur de n, en justifiant leur choix.

Questions fréquentes

Comment mesurer le temps d'exécution d'un script Python ?

Utilisez le module time : enregistrez time.time() avant et après l'exécution, puis calculez la différence. Pour des mesures plus précises, le module timeit exécute le code plusieurs fois et donne la moyenne. En Terminale, time.time() suffit pour observer les tendances de complexité.

Quelle est la différence entre O(n) et O(n²) en pratique ?

Pour n = 1000, un algorithme O(n) fait environ 1000 opérations contre 1 000 000 pour O(n²). Cette différence est déjà significative et devient critique pour n = 10 000 ou plus. C'est pourquoi l'optimisation algorithmique a un impact bien plus important que l'optimisation matérielle pour de grandes entrées.

Pourquoi la suite de Fibonacci récursive est-elle si lente ?

La version récursive naïve recalcule les mêmes valeurs de nombreuses fois : fib(5) appelle fib(4) et fib(3), mais fib(4) rappelle fib(3) à son tour. Le nombre d'appels croît exponentiellement (environ 2^n). La version itérative calcule chaque valeur une seule fois en O(n).

Comment enseigner la complexité algorithmique avec des méthodes actives ?

Les courses d'algorithmes en petits groupes sont très efficaces : les élèves implémentent, mesurent et comparent différentes solutions au même problème. La confrontation entre prédictions théoriques et mesures réelles développe l'intuition sur les ordres de grandeur et motive l'étude formelle de la notation O.