TD — Séance 0 — Qu’est-ce qu’un algorithme

Problème, instruction, exécution à la main

TD de la séance 0 d’Algorithmique : problème, instruction, exécution à la main.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Décrire un problème par ses données et son résultat ; dire si une suite d’étapes est un algorithme ; repérer et lever une ambiguïté, une étape qui peut ne pas finir, un ordre faux ; lire la structure d’un algorithme écrit en pseudo-code et en écrire la trace ; trouver et corriger une instruction mal écrite ; puis écrire ses propres algorithmes et les exécuter à la main sur un cas ordinaire et sur un cas limite. Une trace se remplit comme dans le CM : une ligne par pas, le numéro de la ligne exécutée, l’instruction, l’état des variables après le pas s’il y en a (en gras, la variable qui reçoit une valeur), et ce qu’écrit Écrire ; un arrêt s’écrit « arrêt » avec sa cause. Les prix, les quantités et les horaires des énoncés sont illustratifs.

Exercice 1 : problèmes et algorithmes

  1. Pour chaque problème, donner les données et le résultat.

    Problème Données Résultat
    convertir une somme en francs CFA en euros (1 € = 655,957 F CFA)
    calculer l’âge qu’aura une personne au 31 décembre d’une année donnée
    trouver le trajet le plus court de Ziguinchor à Kolda sur une carte routière
    dire si un candidat est admis, connaissant ses notes et la moyenne exigée

  2. Pour chacun des textes suivants, dire s’il est un algorithme, et justifier par l’exigence de la définition qu’il respecte ou non (finie, non ambiguë, dans l’ordre, qui se termine).

    • [T1] « Pour cuire le riz, le laisser sur le feu assez longtemps. »
    • [T2] « Compter à partir de 1, de un en un, et s’arrêter au dernier nombre entier. »
    • [T3] « Pour retrouver un ami au stade Léopold Sédar Senghor, faire le tour des tribunes jusqu’à le voir. »
    • [T4] « 1. Acheter une carte de recharge de 1000 F. 2. Gratter la zone grise pour faire apparaître le code secret. 3. Composer le numéro de recharge écrit au dos de la carte, suivi du code secret. 4. Lire le message qui donne le nouveau crédit. »
    Texte Algorithme ? Raison
    T1
    T2
    T3
    T4

  3. Pour le premier problème du tableau (a), proposer un cas ordinaire et un cas limite.

Exercice 2 : une recette ambiguë

Un cahier de recettes donne, pour le jus de bissap, les étapes suivantes.

  1. Rincer des fleurs de bissap.
  2. Les mettre dans de l’eau.
  3. Laisser reposer.
  4. Filtrer quand c’est prêt.
  5. Sucrer à son goût.
  6. Ajouter un peu de menthe.
  7. Mettre au frais et servir bien frais.

  1. Pour chaque étape, dire si elle est ambiguë et ce qui lui manque.

    Étape Ambiguë ? Ce qui manque
    1
    2
    3
    4
    5
    6
    7

  2. Quelle étape s’arrête à un moment que l’exécutant ne sait pas fixer ? Pourquoi est-ce un défaut de terminaison autant que d’ambiguïté ?

  3. On échange les étapes 3 et 4. Que se passe-t-il ? Que montre cet échange ?

  4. Réécrire la recette, sans ambiguïté, pour \(L\) litres de jus (\(L\geq1\)) : fixer soi-même des quantités vraisemblables, proportionnelles à \(L\) quand il le faut.

    Recette réécrite :

Exercice 3 : structure et trace

Avant une épreuve, un écran rappelle les consignes de la salle.

Algorithme Examen
Début
  Écrire "Ranger les sacs au fond de la salle"
  Écrire "Éteindre les téléphones"
  Écrire "Prendre une copie"
  Écrire "Inscrire son nom sur la copie"
Fin

  1. Nommer les parties de l’algorithme et donner leurs numéros de ligne. Pourquoi n’a-t-il pas de partie Variables ?

  2. Dérouler l’algorithme dans le tableau ci-dessous (toutes les lignes ne servent pas forcément).

    Pas Ligne Instruction Écrit

  3. Combien de pas compte la trace ? Combien en compterait-elle si l’on ajoutait deux instructions Écrire avant Fin ?

    Réponse :

  4. On échange les lignes 5 et 6. Qu’écrit l’algorithme ? L’exécution se passe-t-elle sans arrêt ? L’algorithme résout-il encore le problème ?

    Réponse :

  5. Pour chacun des en-têtes suivants, dire s’il respecte les conventions du cours, et pourquoi.

    En-tête Conforme ? Raison
    Algorithme Examen
    Algorithme Salle d’examen
    Algorithme Épreuve
    algorithme Examen
    Algorithme ConsignesExamen

Exercice 4 : trouver et corriger l’erreur

Partie A. Un ticket de ferry s’imprime ainsi.

Algorithme Ticket
Début
  Écrire "Ferry Dakar - Ziguinchor"
  Écrire "Cabine de 2 places"
  Écrire Embarquement
  Écrire "Bonne traversée"
Fin

  1. Dérouler l’algorithme dans le tableau ci-dessous, jusqu’à la fin de l’exécution.

    Pas Ligne Instruction Écrit

  2. Quelles lignes sont écrites ? Quelles lignes d’instruction ne sont pas exécutées ?

    Réponse :

  3. Corriger l’algorithme pour qu’il écrive le mot Embarquement ; donner ce qu’il écrit et le nombre de pas de sa trace.

    Réponse :

Partie B. Un étudiant propose une autre version du ticket.

Algorithme Ticket ferry
Début
  Écrire "Ferry Dakar - Ziguinchor"
  Écrire "Cabine de 2 places"
  Écrire "Embarquement"
Fin
Écrire "Bonne traversée"

  1. Relever les deux fautes d’écriture de cette version, en citant leurs lignes, et les corriger. Laquelle des deux empêche la ligne « Bonne traversée » de faire partie de l’algorithme ?

    Réponse :

Exercice 5 : conception

Partie A. Dans une gare, un distributeur automatique vend des tickets et rend la monnaie. Les données sont le prix \(p\) du ticket et la somme \(s\) introduite, avec \(s\geq p\) ; le résultat est un ticket et la monnaie.

  1. Écrire un algorithme de la vie courante, en étapes numérotées, non ambigu, pour acheter un ticket à ce distributeur.

    Algorithme :

  2. L’exécuter à la main pour \(p=1500\) F et \(s=2000\) F, puis pour le cas limite \(s=p=1500\) F. Que devient la dernière étape dans le cas limite ?

    Pas Étape Ce qui est fait Somme introduite Monnaie rendue
    Pas Étape Ce qui est fait Somme introduite Monnaie rendue

  3. Pourquoi \(s<p\) n’est-il pas une donnée permise ? Que devrait faire l’exécutant dans ce cas ?

Partie B. Une affiche annonce un tournoi de lutte.

  1. Écrire un algorithme sans variable, sous la forme complète, qui écrit, une par ligne : Tournoi de lutte de Kaolack, puis Samedi à 16 h, puis Entrée : 500 F. Numéroter les lignes.

    Algorithme :

  2. Dérouler l’algorithme dans une trace. Quel est le numéro de la ligne Fin ?

    Pas Ligne Instruction Écrit

Exercice 6 : une donnée lue, un résultat calculé

À une borne d’eau, on remplit des bidons de 20 litres. L’algorithme suivant utilise les deux instructions de l’aperçu du CM, Lire et l’affectation \(\leftarrow\).

Algorithme Bidons
Variables
  n, litres : entier
Début
  Lire n
  litres ← n × 20
  Écrire "litres :", litres
Fin

  1. Dérouler l’algorithme pour l’entrée 3.

    Pas Ligne Instruction n litres Écrit

  2. Le dérouler pour le cas limite 0. Le résultat a-t-il un sens ?

    Pas Ligne Instruction n litres Écrit

  3. Qu’écrit l’algorithme si l’on tape \(-2\) par erreur ? L’exécution s’arrête-t-elle ? Quelles sont les données permises de ce problème, et qui doit les fixer ?

  4. Combien de pas compte la trace, quel que soit l’entier tapé ? Expliquer pourquoi l’exécution se termine toujours.

  5. Comparer l’algorithme Bidons et l’algorithme Affiche de l’exercice 5 : lequel a des données ? Lequel écrit toujours la même chose ? Lequel résout un problème pour plusieurs cas ?

Pour cette séance

Le cours

Les slides

Retour au sommet