Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

Algorithmique et programmation

Imprimer seulement Cinquième

Les leçons de ce thème vues en Cinquième, prêtes pour le papier.

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

1. Variables, types et affectation

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Écris 4(x−2)4(x - 2) sans parenthèses. Quel est le terme constant ?
  2. Réduis 9x+9−8x+39x + 9 - 8x + 3. Quel est le coefficient de xx ?
  3. Réduis 6x−(1x−6)6x - (1x - 6). Quel est le terme constant ?

Découvrir

On exécute x ← 3, puis x ← x + 2. Que vaut xx ?

  1. 55
  2. 33

L'idée clé

Une variable contient une valeur qui peut changer.

Types : entier, flottant, chaîne de caractères, booléen. L'affectation a ← b donne à aa la valeur de bb. Les instructions s'exécutent dans l'ordre.

Exemple corrigé

a ← 2, b ← a + 1, a ← b × 2.

b=3b = 3
a vaut 2.
a=6a = 6
On remplace a.

À toi, guidé

À toi : n ← 4, puis n ← n × n. Que vaut nn ?

1616
4 × 4.

Entraînement ★

  1. On exécute `x ← 3`, puis `x ← x + 1`, puis `x ← 2 × x`. Que vaut xx à la fin ?
  2. On exécute `x ← 97`, puis `x ← x + 95`, puis `x ← 2 × x`. Que vaut xx à la fin ?
  3. On exécute `x ← 4`, puis `x ← x + 1`, puis `x ← 2 × x`. Que vaut xx à la fin ?

Attention !

Entraînement ★★

  1. On exécute `a ← 3`, `b ← 4`, `c ← a`, `a ← b`. Que vaut aa à la fin ?
  2. On exécute `a ← 9`, `b ← 1`, `c ← a`, `a ← b`. Que vaut aa à la fin ?
  1. On exécute `x ← 3`, puis `x ← x + 1`, 2 fois de suite. Que vaut xx à la fin ?
  1. Que signifie `x ← x + 1` ?
    1. On remplace la valeur de `x` par sa valeur plus 1
    2. xx est égal à x+1x + 1
    3. Le programme s'arrête, car c'est impossible

Bilan

Trois questions pour vérifier que c'est acquis.

  1. On exécute `x ← 3`, puis `x ← x + 1`, puis `x ← 2 × x`. Que vaut xx à la fin ?
  2. On exécute `x ← 97`, puis `x ← x + 95`, puis `x ← 2 × x`. Que vaut xx à la fin ?
  3. On exécute `x ← 4`, puis `x ← x + 1`, puis `x ← 2 × x`. Que vaut xx à la fin ?

Fiche résumé

Affectation

  • a ← b : aa prend la valeur de bb.
  • Les instructions se font dans l'ordre.

Attention : ce n'est pas une égalité.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. On exécute `a ← 7`, `b ← 3`, puis `a ← a + b`, `b ← a − b`, `a ← a − b`. Que vaut aa à la fin ?

2. Conditions et boucles

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. On exécute `x ← 3`, puis `x ← x + 1`, puis `x ← 2 × x`. Que vaut xx à la fin ?
  2. On exécute `a ← 3`, `b ← 4`, `c ← a`, `a ← b`. Que vaut aa à la fin ?
  3. On exécute `x ← 3`, puis `x ← x + 1`, 2 fois de suite. Que vaut xx à la fin ?

Découvrir

Si x > 5 alors y ← 1 sinon y ← 0, avec x=3x = 3. Que vaut yy ?

  1. 00
  2. 11

L'idée clé

Conditions et boucles organisent le calcul.

Si … alors … sinon exécute une branche selon une condition. Pour ii allant de 1 à nn répète nn fois. Tant que répète tant que la condition est vraie.

Exemple corrigé

s ← 0, pour i de 1 à 3 : s ← s + i.

s=1+2+3s = 1 + 2 + 3
i = 1, 2, 3.
s=6s = 6
Résultat.

À toi, guidé

À toi : pour i de 1 à 4 : x ← x + 2, avec x=0x = 0 au départ. Que vaut xx ?

88
4 tours de +2.

Entraînement ★

  1. `s ← 0`, puis `pour i de 1 à 4 : s ← s + 2`. Que vaut ss ?
  2. `s ← 0`, puis `pour i de 1 à 12 : s ← s + 12`. Que vaut ss ?
  3. `s ← 0`, puis `pour i de 1 à 3 : s ← s + 2`. Que vaut ss ?

Attention !

Entraînement ★★

  1. `x ← 1`, puis `tant que x < 81 : x ← x × 3`. Que vaut xx à la fin ?
  2. `x ← 1`, puis `tant que x < 32 : x ← x × 2`. Que vaut xx à la fin ?
  1. `si 6 > 3 : x ← 1, sinon : x ← 0`. Que vaut `x` si 6>36 > 3 est vrai ?
  1. `pour i de 1 à 3` : combien de tours fait la boucle ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. `s ← 0`, puis `pour i de 1 à 4 : s ← s + 2`. Que vaut ss ?
  2. `s ← 0`, puis `pour i de 1 à 12 : s ← s + 12`. Que vaut ss ?
  3. `s ← 0`, puis `pour i de 1 à 3 : s ← s + 2`. Que vaut ss ?

Fiche résumé

Boucles

  • Pour : nombre de tours connu.
  • Tant que : on s'arrête quand la condition devient fausse.

Attention : compte bien les tours.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. `s ← 0`, puis `pour i de 1 à 4 : s ← s + i`. Que vaut ss à la fin ?

3. Fonctions en programmation et hasard

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. `s ← 0`, puis `pour i de 1 à 4 : s ← s + 2`. Que vaut ss ?
  2. `x ← 1`, puis `tant que x < 81 : x ← x × 3`. Que vaut xx à la fin ?
  3. `si 6 > 3 : x ← 1, sinon : x ← 0`. Que vaut `x` si 6>36 > 3 est vrai ?

Découvrir

def f(x): return x + 1. Que renvoie f(4) ?

  1. 55
  2. 44

L'idée clé

Une fonction regroupe un calcul réutilisable.

def f(x): définit une fonction ; return renvoie son résultat. random() renvoie un flottant de [0;1[[0 ; 1[ : on s'en sert pour simuler une expérience.

Exemple corrigé

def g(a, b): return a × b + 1. Calcule g(2, 3).

2×3+12 \times 3 + 1
On remplace.
77
Résultat.

À toi, guidé

À toi : def c(x): return x × x. Que renvoie c(3) ?

99
3 × 3.

Entraînement ★

  1. `def f(x): return 5 × x + 4`. Que renvoie `f(3)` ?
  2. `def f(x): return 25 × x + 41`. Que renvoie `f(3)` ?
  3. `def f(x): return 4 × x + 2`. Que renvoie `f(3)` ?

Attention !

Entraînement ★★

  1. `if random() < 0.4:` compte un succès. Quelle est la probabilité d'un succès ?
  2. `if random() < 0.3:` compte un succès. Quelle est la probabilité d'un succès ?
  1. `def f(x): return 3 × x`. Que renvoie `f(f(2))` ?
  1. À quoi sert `return` dans une fonction ?
    1. À renvoyer une valeur à qui l'a appelée
    2. À afficher une valeur à l'écran
    3. À redémarrer la fonction

Bilan

Trois questions pour vérifier que c'est acquis.

  1. `def f(x): return 5 × x + 4`. Que renvoie `f(3)` ?
  2. `def f(x): return 25 × x + 41`. Que renvoie `f(3)` ?
  3. `def f(x): return 4 × x + 2`. Que renvoie `f(3)` ?

Fiche résumé

Fonctions

  • def définit, return renvoie.
  • random() simule le hasard.

Attention : appelle la fonction avec le bon nombre d'arguments.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. `def f(x): return 2 × x + 1`. Que renvoie `f(f(f(4)))` ?

4. Compter les étapes d'un algorithme

Découvrir

On cherche un nombre entre 1 et 1 000 000 dans une liste triée. À chaque essai, on regarde le milieu et on garde la bonne moitié. Combien d'essais faut-il au plus ?

  1. Une vingtaine
  2. Environ 500 000

L'idée clé

Compter les étapes d'un algorithme.

  • Deux boucles imbriquées de nn et mm tours : n×mn \times m passages.
  • La dichotomie sur une liste de 2k2^k éléments : au plus kk étapes (environ k+1k + 1 comparaisons).

Compter les étapes permet de comparer deux algorithmes.

Exemple corrigé

Une boucle « pour i de 1 à 30 » contient une boucle « pour j de 1 à 40 ».

30×4030 \times 40
Chaque tour de i fait 40 tours de j.
12001200 passages
Total.

À toi, guidé

À toi : liste triée de 1024=2101024 = 2^{10} éléments : nombre de divisions par deux ?

1010
210=10242^{10} = 1024.

Entraînement ★

  1. Une boucle « pour i de 1 à 36 » contient une boucle « pour j de 1 à 37 ». Combien de fois l'instruction intérieure est-elle exécutée ?
  2. Une boucle « pour i de 1 à 44 » contient une boucle « pour j de 1 à 43 ». Combien de fois l'instruction intérieure est-elle exécutée ?
  3. Une boucle « pour i de 1 à 19 » contient une boucle « pour j de 1 à 21 ». Combien de fois l'instruction intérieure est-elle exécutée ?

Entraînement ★★

  1. Une liste triée contient 2102^{ 10 } éléments. Combien de divisions par deux faut-il pour arriver à un seul élément ?
  2. Une liste triée contient 2202^{ 20 } éléments. Combien de divisions par deux faut-il pour arriver à un seul élément ?

Bilan

Deux questions pour vérifier.

  1. Une boucle « pour i de 1 à 36 » contient une boucle « pour j de 1 à 37 ». Combien de fois l'instruction intérieure est-elle exécutée ?
  2. Une boucle « pour i de 1 à 44 » contient une boucle « pour j de 1 à 43 ». Combien de fois l'instruction intérieure est-elle exécutée ?

Fiche résumé

Coût d'un algorithme

  • Boucles imbriquées : on multiplie les nombres de tours.
  • Dichotomie : environ log⁡2n\log_2 n étapes.

Les moteurs de recherche choisissent des algorithmes dont le coût grandit lentement.

5. Histoire des algorithmes : al-Khwarizmi, Lovelace et Turing

Découvrir

Le mot « algorithme » vient du nom d'un savant de Bagdad, vers l'an 800. Lequel ?

  1. Al-Khwarizmi
  2. Alan Turing

L'idée clé

Des recettes de calcul aux ordinateurs.

80010001200140016001800vers 815al-Khwarizmivers 815al-Khwarizmi
  1. Étape 180010001200140016001800vers 815al-Khwarizmivers 815al-Khwarizmial-Khwarizmi vers 780 – vers 850Portrait imaginéZarateman (photograph), 2022. Zarateman. CC0 1.0Al-Khwarizmi (vers 780–850) : son nom donne le mot algorithme.
  2. Étape 280010001200140016001800vers 815al-Khwarizmi1843Lovelacevers 815al-Khwarizmi1843LovelaceAda Lovelace 1815–1852Margaret Sarah Carpenter, 1836. Domaine public1843 : Ada Lovelace décrit comment programmer la machine analytique.
  3. Étape 380010001200140016001800vers 815al-Khwarizmi1843Lovelace1936Turingvers 815al-Khwarizmi1843Lovelace1936TuringAlan Turing 1912–1954possibly Arthur Reginald Chaffin, 1928–1929. Domaine public1936 : Turing décrit sa machine abstraite.

Le mot algorithme vient du nom d'al-Khwarizmi (vers 780–850). En 1843, Ada Lovelace publie des notes sur la machine analytique de Babbage : elle y décrit comment la programmer, ce que beaucoup considèrent comme le premier programme. En 1936, Alan Turing décrit une machine abstraite qui passe d'un état à un autre selon une table de règles : la « machine de Turing ».

Source

La machine analytique tisse des motifs algébriques comme le métier Jacquard tisse des fleurs et des feuilles.

Ada Lovelace, note G sur la machine analytique de Babbage, 1843 (notre traduction de l'anglais)

Que compare Ada Lovelace ?

  1. Une machine à calculer programmable et un métier à tisser commandé par des cartes perforées
  2. Les mathématiques et l'art du tissage, sans parler de machine

Exemple corrigé

Un algorithme de la machine de Turing, en langage actuel : x←3x \leftarrow 3, puis trois fois x←2xx \leftarrow 2x.

3→6→12→243 \to 6 \to 12 \to 24
On exécute dans l'ordre.
x=24x = 24
Résultat.

Entraînement ★

  1. Que décrit Ada Lovelace dans ses notes de 1843 ?
    1. Comment programmer la machine analytique de Babbage
    2. La machine de Turing
    3. Le premier ordinateur électronique
  1. On exécute : x←5x \leftarrow 5, puis 4 fois x←2xx \leftarrow 2x. Quelle est la valeur finale de xx ?
  2. On exécute : x←7x \leftarrow 7, puis 5 fois x←2xx \leftarrow 2x. Quelle est la valeur finale de xx ?
  1. Une machine suit la règle : x←13x \leftarrow 13, puis 9 fois x←x+6x \leftarrow x + 6. Valeur finale de xx ?

Fiche résumé

Les algorithmes aujourd'hui

  • GPS : un algorithme cherche le plus court chemin.
  • Compression des photos et de la musique.
  • Recommandations de vidéos et moteurs de recherche.

Sources : biographies d'al-Khwarizmi, d'Ada Lovelace et d'Alan Turing sur MacTutor (voir « Sources et crédits »).