S15 – Mesurer et connaître les limites
| Élément | Détail |
|---|---|
| Niveau | BTS SIO option SISR, 2e année – complément : pour aller plus loin |
| Séance | S15 (séance 15 sur 19) – Phase 3 |
| Durée | 4 heures |
| Parcours | Complément – Mesures et limites : n'est le prérequis d'aucune séance ; seul le test de doublement est cité en S16 et S19. Voir le parcours cœur et complément. |
| Chapitre du programme | Analyse d'algorithme – mesures, limites |
| Prérequis | S13 ; S14 |
| Outils | Papier, calculatrice, éditeur Python intégré au site |
Note
Question qui guide la séance : « Que faire quand un algorithme devient trop long, même pour un ordinateur ? »
Objectifs
À la fin de la séance, l'étudiant est capable de :
- Mesurer un temps d'exécution
- Relier la mesure à la complexité
- Reconnaître une explosion exponentielle
- Estimer la durée d'une recherche exhaustive
- Proposer une amélioration
Contenu de la séance
| Document | Rôle |
|---|---|
| Cours | Cours |
| Exercices | Exercices |
| TP Python | TP (éditeur Python intégré) |
| Aide-mémoire | Aide-mémoire |
Déroulé conseillé (4 h)
| Durée | Activité | Format |
|---|---|---|
| 0 h 00 – 0 h 15 | Rappel : complexité asymptotique (S13), tris et recherches (S14) | Oral |
| 0 h 15 – 1 h 15 | Cours : mesure du temps, test de doublement, explosion exponentielle, améliorations | Cours et questions |
| 1 h 15 – 2 h 15 | Exercices | Individuel |
| 2 h 15 – 3 h 45 | TP Python | Individuel |
| 3 h 45 – 4 h 00 | Auto-évaluation | Individuel |
Durées indicatives : la séance dure 4 h ; l'enseignant ajuste selon le rythme du groupe.
Application en informatique
Évaluer pourquoi une recherche exhaustive de mot de passe ou de tournée est hors de portée, et comment gagner du temps.
Évaluation
- Feuille d'exercices et scripts du TP validés dans l'éditeur.
- Auto-évaluation « Je sais faire » en fin d'exercices.
Notes pour l'enseignant
- Exemples chiffrés recalculés par programme ; scripts du TP validés (solution réussie, squelette en échec).