Bases des algorithmes

Durée estimée: 45 minutes

Version textuelle

Introduction

Dans la leçon avec Blockly, nous avons introduit le terme d'algorithme et nous l'avons défini comme une séquence d' instructions précises qui réalisent des opérations ou des calculs.

Les algorithmes sont au coeur de la science informatique. Ce sont les algorithmes - sous forme de code informatique que l'ordinateur peut interpréter - qui rendent nos ordinateurs si puissants et versatiles.

Comme nous l'avons vu dans les problèmes de labyrinthe de la leçon 1.2, les algorithmes sont construits à partir de briques élémentaires appelées: structures de contrôle.
Il y a trois structures de base:

  • La Séquence – est une séquence d'instructions ou de déclarations.
  • La Sélection – est une instruction conditionnelle qui permet au programme de poursuivre sur une branche (séquence d'instructions) ou une autre parmi deux ou plus.
  • La Répétition (ou Itération) – est une structure qui permet de répéter une ou plusieurs instructions.

Les scientifiques ont démontré que TOUS les algorithmes peuvent être réalisés en utilisant uniquement ces trois structures !
En d'autres termes, quel que soit l'algorithme que vous avez conçu pour résoudre un problème, il sera possible de le construire à partir de séquences d'instructions, de sélections et de répétitions.

Problèmes de labyrinthes (Blockly)

Si vous n'avez pas effectué les jeux ou exercices du chapitre 1 sur les labyrinthes ou si vous voulez en faire d'autres avec les "séquences", "sélections" et "répétitions", vous pouvez essayer ce lien qui utilise les (instructions) du langage "Blockly".

Notions de base sur les algorithmes

Maintenant que vous avez réalisé des algorithmes pour sortir des labyrinthes avec des séquences, sélections et itérations voici un résumé des points clefs sur les algorithmes.

(La vidéo suivante est en anglais -en attente d'adaptation en français - mais les planches sont en français)



Activité par groupes ou pour la classe (15 minutes) - méthode POGIL

Constituez des équipes ("POGIL") de 4 et donnez à chacun un des rôles ci-dessous. Si vous êtes plus nombreux, notez tous les noms dans votre réponse.
Téléchargez cette FEUILLE qui est un fichier word, enregistrez en une copie, puis après avoir répondu en groupe, envoyez le résultat à votre enseignant, par mail ou via le portfolio, selon les indications qu'il vous donnera.
Role Responsabilité
Facilitateur Lit les questions à haute voix, Gère le temps et s'assure de la participation de chacun.
Porte-parole Echange avec l'enseignant ou l'animateur et avec les autres équipes.
Contrôleur qualité Prend note de toutes les réponses & et questions, et rend compte des analyses et réflexions de l'équipe à l'équipe et à l'enseignant.
Analyste process Examine comment l'équipe pourrait être plus efficace dans son travail.

Ecrire du Pseudocode: Questions d'analyse critique

Le Pseudocode d'un algorithme est une formulation intermédiaire entre le langage courant et un langage informatique compréhensible par l''ordinateur. Le Pseudocode est moins précis qu'un code informatique en Java, Python ou App Inventor, mais plus précis et moins verbeux que le langage courant.

Prenons l'exemple d'une liste de nombres [ 5, 10, -2, -3, 7, 8, 12 ] dont on veut la somme des nombres impairs.
Voici le pseudocode d'un algorithme de séquences, sélections et itérations (ou répétition) qui fait cette somme des nombres impairs et l'imprime. Notez que l'indentation est utilisée pour séparer les différentes parties de l'algorithme (et montrer en particulier ce qui doit être fait dans une répétition, ou la branche à exécuter après une sélection).
(*Note : nous avons conservé le pseudo code en anglais à titre d'illustration) 
  
  1. mettre le total à 0                      1. Set the running total to 0.
  2. pour chaque nombre de la liste :         2. For each number in the list:
  3.   si le nombre est pair :                3.   If the number is even
  4.     ajouter ce nombre au total actuel    4.      Add the number to the running total.
  5. imprimer la valeur du total              5. Print the running total.
Cet algorithme contient cinq lignes et des exemples des trois structures de contrôle : séquence, sélection et répétition. On a donné un numéro à chaque ligne pour faciliter et exercice.
  1. Quelle(s) ligne(s) de l'algorithme contient ou contiennent une structure de type "répétition" ? Rappelez vous qu'une structure de contrôle peut contenir plusieurs instructions.
  2. Quelle(s) ligne(s) de l'algorithme contient une structure de type "sélection" ?
  3. Quel est le résultat imprimé après exéccution cet algorithme ?
  4. (Portfolio : ) Prenons une liste d'entiers positifs commme 5, 10, 12, 13, 6, 7, 1, 3, 2, 1. Demandons cette fois-ci que pour chaque nombre de cette liste on l'ajoute si il est impair et on le soustrait si il est pair. Quel est le résultat pour ces nombres ?
  5. (Portfolio :) Ecrivez le pseudocode d'algorithme qui correspond à la manière dont vous avez procédé pour obtenir ce résultat.

Auto-contrôle

Le tableau suivant définit les termes techniques nouveaux de cette leçon.
Pour vérifier un terme, passez dessus avec la souris pour afficher sa définition.
algorithme
structure de contrôle
séquence
sélection
répétition 		itération
booléen
pseudocode
diagramme de flux
Not yet started
1 point
Algorithmes : laquelle de ces affirmations est fausse ?
Not yet started
1 point
Vrai or Faux: Le langage utilisé dans le jeu de labyrinthe Blockly est un exemple de pseudocode. pseudocode.
Not yet started
1 point
Le pseudocode ___________________.
Not yet started
1 point
Terminez la phrase suivante : le séquencement dasn un algorithme veut dire que chaque pas (ou instruction) est exécutée ____________.
Not yet started
1 point
Examinez le pseudocode suivant : 
mettre P à 1
mettre N à 4
Répéter tant que N > 0:
  mettre P égal au résultat de P fois N
  soustraire 1 à N
Imprimer P 
                                  
Set P to 1.
Set N to 4.
  Repeat while N > 0:
  Set P to result of multiplying P by N.
Subtract 1 from N.
Print P

quel résultat sera imprimé par cet algorithme ?

En savoir plus ?

La combinaison des trois stuctures de contrôle utilisées dans le jeu de labyrinthes Blockly est suffisante pour réaliser tout algorithme concevable ! Ca peut vous surprendre. Cette affirmation est un théorème qui a été démontré en 1966 par Corrado Boehm and Giuseppe Jacopini. Ce théomèrme s'appelle le théorème de la programmation structurée. Vous povez en savoir plus dans cet article Wikipedia.

Réflexions à conduire et inclure dans votre Portfolio

Dans la catégorie "réflexions" de votre portfolio, allez à la page 2.06 : Algos et pseudo code et répondez aux questions suivantes :

  1. (POGIL) Prenons une liste d'entiers positifs : 5, 10, 12, 13, 6, 7, 1, 3, 2, 1. En partant de 0, on ajoute chaque nombre de cette liste si il est impair et on le soustrait si il est pair.
    Quel est le résultat pour ces nombres ?
  2. (POGIL) Ecrivez sous forme "pseudocode" l'algorithme qui correspond à la manière dont vous avez calculé le résultat.
  3. Dans cette leçon, vous avez appris ce qu'est le pseudocode. Ecrivez un algorithme qui correspond au lavage de 5 tasses et 5 soucoupes en suivant une règle qui impose de laver les tasses dans l'eau chaude et les soucoupes dans l'eau froide.
    Utilisez l'indentation pour que votre algorithme soit facile à lire et identifiez dans cet algorithme des exemples de structures de type Séquence, Sélection, et Répétition.