Complexité et optimisation algorithmique

Les élèves comprennent mieux la complexité algorithmique quand ils expérimentent concrètement les différences de performance. Cette approche active permet de transformer une notion abstraite en expérience tangible, où chaque opération élémentaire devient visible. Travailler en groupe révèle aussi des perspectives variées sur les choix d'implémentation.

• Terminale
• Mathématiques : Vers l\\
• 4 activités
• 20 min–45 min

Objectifs d’apprentissage

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

Cercle de recherche

⏱ 45 min·Petits groupes

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.

Préparation et détails

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

Conseil de facilitation: Pendant la Course d'algorithmes, demandez aux groupes de chronométrer chaque version de l'algorithme sur des entrées de tailles différentes pour visualiser la croissance temporelle.

Setup: Groupes en îlots avec accès aux ressources documentaires

Materials: Corpus de documents sources, Fiche de suivi du cycle de recherche, Protocole de formulation de questions, Canevas de présentation des résultats

• Analyser
• Évaluer
• Créer
• Autogestion
• Conscience de soi

Penser-Partager-Présenter

⏱ 25 min·Binômes

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.

Préparation et détails

Pourquoi un algorithme récursif peut-il être plus lent qu'un itératif?

Setup: Disposition de classe standard ; les élèves se tournent vers leur voisin

Materials: Consigne de discussion (projetée ou distribuée), Optionnel : fiche de prise de notes pour les binômes

• Comprendre
• Appliquer
• Analyser
• Conscience de soi
• Compétences relationnelles

Galerie marchande

⏱ 30 min·Petits groupes

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.

Préparation et détails

Comment réduire le nombre d'opérations dans un calcul de somme?

Setup: Espace mural dégagé ou tables disposées en périphérie de la salle

Materials: Papier grand format ou panneaux d'affichage, Feutres et marqueurs, Post-it pour les retours critiques

• Comprendre
• Appliquer
• Analyser
• Créer
• Compétences relationnelles
• Conscience sociale

Débat formel

⏱ 20 min·Individuel

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.

Préparation et détails

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

Setup: Deux équipes face à face, le reste de la classe en position d'auditoire

Materials: Fiche de sujet de débat, Dossier documentaire pour chaque camp, Grille d'évaluation pour le public, Chronomètre

• Analyser
• Évaluer
• Créer
• Autogestion
• Prise de décision

Enseigner ce sujet

Commencez par des exemples concrets où les élèves comparent des algorithmes simples avant d'aborder la théorie. Insistez sur le fait que la complexité est une question d'échelle, pas de performance absolue. Évitez de se perdre dans les détails mathématiques : privilégiez l'intuition visuelle avec des courbes et des exemples numériques.

À quoi s’attendre

Les élèves savent expliquer pourquoi un algorithme est plus efficace qu'un autre en utilisant la notation O et en identifiant les opérations élémentaires. Ils justifient leurs choix d'implémentation en comparant des approches récursives et itératives. La collaboration montre une compréhension nuancée des compromis entre lisibilité et performance.

Attention à ces idées reçues

Idée reçue courante

During Penser-Partager-Présenter : Récursif vs itératif, un élève affirme : 'Un algorithme récursif est toujours plus lent qu'un itératif.'

Ce qu'il faut enseigner à la place

Pendant cette activité, demandez aux élèves de comparer les temps d'exécution du calcul de Fibonacci avec et sans mémoïsation. Ils observeront que la récursivité naïve est lente, mais que la version optimisée atteint la même complexité qu'un itératif. Utilisez les données collectées pour corriger cette idée reçue.

Idée reçue courante

During Galerie marchande : Reconnaître la complexité, un élève déclare : 'La complexité O(n²) signifie que l'algorithme fait exactement n² opérations.'

Ce qu'il faut enseigner à la place

Pendant le parcours, montrez les courbes de croissance de différents algorithmes (linéaire, quadratique, logarithmique). Demandez aux élèves de tracer manuellement les points pour n=10, 100 et 1000, et observez que le comportement asymptotique ne correspond pas à une valeur exacte. La correction émerge de la visualisation des écarts.

Idée reçue courante

During Défi individuel : Optimiser une somme, un élève pense : 'Mesurer le temps d'exécution suffit pour déterminer la complexité.'

Ce qu'il faut enseigner à la place

Pendant ce défi, faites varier l'environnement d'exécution (machine, langue de programmation) et demandez aux élèves de comparer les résultats. Ils constateront que le temps varie, mais que la tendance théorique (O(n) vs O(1)) reste stable. Cette activité montre pourquoi la complexité est un modèle abstrait.

Idées d'évaluation

Vérification rapide

Après Course d'algorithmes, présentez le code Python de la recherche linéaire. Demandez aux élèves d'identifier les opérations élémentaires (comparaisons, affectations) et de déterminer la complexité temporelle O(n). Collectez leurs justifications écrites pour évaluer leur capacité à compter les opérations en fonction de n.

Question de discussion

Pendant Penser-Partager-Présenter : Récursif vs itératif, posez la question : 'Pourquoi un algorithme plus court (récursif Fibonacci) peut-il être moins performant qu'un itératif ?' Écoutez les échanges pour vérifier que les élèves mentionnent la pile d'appels et les calculs répétés. Utilisez leurs réponses pour évaluer leur compréhension des compromis.

Billet de sortie

Après Défi individuel : Optimiser une somme, demandez aux élèves d'écrire les deux algorithmes (itératif et récursif) pour calculer la somme des n premiers entiers. Ils doivent comparer leur complexité temporelle et justifier leur choix pour une grande valeur de n. Ramassez les tickets pour évaluer leur capacité à appliquer la notation O et à argumenter leur décision.

Extensions et étayage

• Challenge : Proposez un algorithme de tri peu efficace (par exemple, tri à bulles) et demandez aux élèves de le comparer à un tri plus optimisé (tri fusion) en mesurant le temps d'exécution pour n supérieur à 10 000.
• Scaffolding : Pour les élèves en difficulté, fournissez des exemples de code avec les opérations élémentaires déjà comptées pour la recherche linéaire.
• Deeper : Explorez les limites de la notation O en demandant aux élèves de proposer des algorithmes où la complexité pratique diffère de la complexité théorique (par exemple, algorithmes avec optimisations cachées).

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é.