Activités débranchées en classe

On place des élèves en ligne. Il peut y avoir plusieurs lignes s'il y a beaucoup d'élèves.

Chaque élève joue le rôle d'un appel de fonction.

Le professeur guide le déroulé, affiche les instructions au tableau et les explique.

Nombre de calculatrices

Objectif

Compter le nombre de calculatrices dans la classe.

Définition

On informe que pour cet exercice, comptent comme calculatrices :

• toutes les calculatrices classiques de poche,
• tous les téléphones portables,
• tous les ordinateurs portables.

Chaque élève détermine alors combien il possède à cet instant de calculatrices.

Combien de calculatrices y a-t-il avec toi et après toi ?

Algorithme

• S'il y n'a personne après,
  • on répond sa quantité personnelle.
• Sinon, dans l'ordre :
  1. on pose la même question au suivant,
  2. on attend sa réponse, ça peut prendre du temps,
  3. on ajoute à sa réponse sa quantité personnelle,
  4. puis on répond à qui avait posé la question.

Le professeur demande à l'élève en début de ligne « Combien de calculatrices y a-t-il avec toi et après toi ? ». On observe le déroulé.

On constate que la durée pour obtenir la réponse est toujours proportionnelle au nombre \(n\) d'élèves sur la ligne. On dira que le cout est linéaire en la taille des entrées.

Téléphones silencieux

Objectif

Savoir si tous les téléphones sont en mode silence.

Tous les téléphones sont-ils en mode silence ?

Algorithme

• On répond suivant le cas
  • Si son téléphone n'est pas en silencieux
    • on répond False pour « Oups, non »
  • Sinon,
    • S'il y n'a personne après,
      • on répond True pour « OK, c'est bon »
    • Sinon,
      • on pose la même question au suivant,
      • on répond la même chose que lui.

Le professeur demande à l'élève en début de ligne « Tous les téléphones sont-ils en mode silence ? ». On observe le déroulé.

On constate que la durée pour obtenir la réponse est, dans le pire des cas, proportionnelle au nombre \(n\) d'élèves sur la ligne. On dira que le cout est linéaire en la taille des entrées, dans le pire des cas. (Dans le meilleur des cas, pour le cout, la réponse est False dès le premier élève).

Maximum d'une liste

Le professeur distribue en début de rangée une feuille avec des nombres et affiche l'algorithme suivant au vidéo-projecteur :

Algorithme

• S'il ne reste qu'un nombre sur la feuille,
  • mémorisez-le,
  • barrez-le,
  • renvoyez ce nombre à celui qui vous a transmis la feuille.
• Sinon,
  • mémorisez un des nombres,
  • barrez-le,
  • transmettez la liste à votre voisin suivant,
  • attendez sa réponse,
  • quand sa réponse vous parvient
    • renvoyez le plus grand des deux nombres, entre réponse entendue et nombre mémorisé, à celui qui vous a transmis la feuille.

On observe le déroulé.

• On peut discuter de ce qui se passe si la liste contient plus de nombres que d'élèves sur la rangée.
• On peut évoquer le fait que la récursivité revient d'une certaine manière à déléguer le travail.