Aller au contenu
Ludicademy
Français
Thème Élan
ClairsSombres
S’inscrire

Fiche de révision : algorithmique, logique Tle

Les 3 leçons du chapitre, réduites à l’essentiel, avec un test à la fin. À imprimer ou à relire à l’écran.

Ludicademyludicademy.fr · apprendre en jouant, du CP à la Terminale
Fiche de révision · Logique · Tle

Algorithmique — l’essentiel du chapitre

3 leçons, ce qu’il faut en retenir, et un test pour vérifier.

1 La complexité : compter les opérations, pas les secondes

Mesurer un algorithme au chronomètre revient à mesurer une machine, un jour donné, sur un jeu d'essai donné. Changez de machine, la mesure change.

  • La complexité compte les opérations selon la taille n, pas les secondes sur une machine
  • On garde l'ordre de grandeur : le terme dominant, sans ses constantes
  • Deux boucles imbriquées sur les mêmes données donnent du n au carré
  • Une complexité exponentielle est condamnée dès quelques dizaines de données

2 La récursivité : un algorithme qui s'appelle lui-même

Un algorithme RÉCURSIF résout un problème en s'appelant lui-même sur un problème PLUS PETIT.

  • Un algorithme récursif s'appelle sur un problème strictement plus petit
  • Il lui faut un cas de base, sinon la descente ne s'arrête jamais
  • La descente empile les appels, la remontée calcule les résultats en sens inverse
  • La récursivité s'impose sur les structures récursives, pas partout : elle peut coûter très cher

3 Pourquoi une boucle s'arrête et pourquoi elle est juste

Essayer un programme sur quelques cas ne prouve rien : les essais montrent la présence de bogues, jamais leur absence.

  • Terminaison et correction sont deux questions distinctes, à prouver séparément
  • Le variant est un entier positif qui décroît strictement : il force l'arrêt
  • L'invariant est vrai avant la boucle et conservé par chaque tour, donc vrai à la sortie
  • Invariant plus condition de sortie donnent le résultat, pour toute donnée et sans essai

Je me teste

  1. Un algorithme en O(n²) traite 1 000 éléments en 1 seconde. Et 10 000 ? (La complexité : compter les opérations, pas les…)

    1. Environ 1 seconde
    2. Environ 100 secondes
    3. Environ 10 secondes
  2. Que manque-t-il à « factorielle(n) vaut n fois factorielle(n moins 1) » ? (La récursivité : un algorithme qui s'appelle lu…)

    1. Un compteur pour les tours de boucle
    2. Le cas de base pour arrêter la descente
    3. Une variable pour stocker le total
  3. Que doit être un variant de boucle ? (Pourquoi une boucle s'arrête et pourquoi elle e…)

    1. Une propriété vraie à chaque tour
    2. Un entier positif qui décroît strictement
    3. Une variable qui compte les tours

Réponses : 1. B · 2. B · 3. B

Chaque leçon, ses exercices et ses jeux : ludicademy.fr/fiches/revision/logique/tle/algorithmiquefiche de révision · usage libre en classe et à la maison

Les leçons du chapitre

Toutes les fiches de révision : par matière et par classe · les fiches d’exercices : la bibliothèque.