TD 1 : Notion d’algorithme

TD 1 : Notion d’algorithme#

Attention

Les exercices non marqués d’un \(\clubsuit\) sont considérés comme acquis d’une semaine sur l’autre.

Notes aux enseignants

Ne vous cassez pas la tête à introduire la notion d’algorithme. L’objectif est justement de les faire manipuler pour leur donner une idée informelle de ce que c’est.

De manière générale : sauf exception, vous n’avez pas à introduire de nouvelles notions en séance; l’amphi est fait pour cela; ou alors le TD est conçu pour leur faire découvrir par eux-mêmes.

Notes aux enseignants

Les deux exercices suivants sont l’occasion de faire découvrir intuitivement par la manipulation les notions suivantes :

  • Langage utilisé : quelles sont les instructions? quelle est leur sémantique?

  • Instructions, programme;

  • État du système;

  • Représentation (mentale) de cet état et de son évolution;

  • Vérification qu’un algorithme est correct par exécution pas-à-pas. Est-ce une preuve?

  • Étendre le langage en ajoutant de nouvelles instructions.

En général, beaucoup d’étudiants auront déjà fait ces exercices. L’intérêt de la séance est d’introduire et nommer explicitement les concepts sous-jacents.

À faire

  • [ ] Compléter les solutions avec l’état du système après chaque instructions

À faire

Remplacer décharge(objet) par décharge(): il y a au plus un objet dans le bateau. Ajuster le poly Semaine 2 et éventuellement ipywidets_games en conséquence.

Exercice 1 : Modélisation d’un problème et notion d’algorithme

Un passeur doit faire passer de l’autre côté d’une rivière un loup, une chèvre et un chou. Pour cela, il ne peut transporter qu’un seul d’entre eux à la fois dans sa barque. On ne sait pas trop ce qui arriverait si le loup venait à rester seul en présence de la chèvre, ou si la chèvre se retrouvait seule en présence du chou.

  1. Décrivez une suite d’instructions simples (un premier algorithme!) à effectuer scrupuleusement par le passeur garantissant que tout le monde traverse la rivière sain et sauf. Les instructions disponibles sont :

    • charge(objet) (exemple: charge(chèvre))

    • décharge(objet)

    • traverse()

    Indication : Ne cherchez pas à résoudre le problème de tête; au contraire, l’objectif est d’apprendre à raisonner sur papier pour aborder ensuite des problèmes plus complexes et pouvoir transmettre ce raisonnement. Cherchez une manière de représenter l’état du système, et décrivez sur votre feuille comment celui-ci évolue au fur et à mesure des instructions.

    BEGIN SOLUTION

    charge(chèvre)
traverse()
décharge(chèvre)
traverse()
charge(loup)
traverse()
décharge(loup)
charge(chèvre)
traverse()
décharge(chèvre)
charge(chou)
traverse()
décharge(chou)
traverse()
charge(chèvre)
traverse()
décharge(chèvre)

    Remarque : comme le loup et le chou ont des rôles symétriques, on peut trouver une autre solution en échangeant loup et chou ci-dessus.

    END SOLUTION

  2. Identifiez une séquence d’instructions qui se répète et proposer une nouvelle instruction les combinant – d’un niveau d’abstraction plus élevé – permettant de simplifier l’écriture de l’algorithme précédent.

    BEGIN SOLUTION

    La séquence charge(objet), traverse(), décharge(objet) est présente cinq fois dans la suite d’instructions donnée en solution à la questions précédente. En créant une nouvelle instruction transporte(objet) appliquant cette séquence, on peut écrire une nouvelle solution qui fait sept lignes au lieu de dix-sept et qui est beaucoup plus lisible et facile à exécuter pas-à-pas pour la vérifier :

    transporte(chèvre)
traverse()
transporte(loup)
transporte(chèvre)
transporte(chou)
traverse()
transporte(chèvre)

    END SOLUTION

Notes aux enseignants

Dans l’exercice suivant, représentez au tableau l’état du système après chaque instruction, par exemple comme dans la solution, et/ou demandez aux élèves de le faire sur leur feuille, afin de les familiariser avec la notion d’exécution pas-à-pas. Si vous avez du temps et un bon groupe, vous pouvez en profiter pour leur demander comment faire pour prouver que leur méthode est la plus efficace (par exemple prouver qu’on ne peut pas obtenir 4 litres en moins de 6 instructions). Cela peut se faire en dessinant le graphe (l’automate en fait) de toutes les possibilités en partant de l’état (0, 0) qui représente les deux cruches vides.

Exercice 2 : Modélisation d’un problème et notion d’algorithme

Soient deux cruches de capacités respectives 5 et 7 litres. Ces cruches ne sont pas graduées. Le but de ce problème est que l’une des deux cruches contienne 4 litres. Vous avez accès à un robinet et à une évacuation d’eau, mais vous ne disposez de rien d’autre que les deux cruches.

  1. Formalisez le problème en termes d’état du système et d’instructions, puis donnez une suite d’instructions permettant d’atteindre une solution.

    Indication : Comme dans l’exercice précédent, ne cherchez pas à résoudre le problème de tête.

    BEGIN SOLUTION

    Notons les deux cruches C5 et C7 respectivement, en fonction de leur capacité. L’état du système est décrit par le nombre de litres dans la première et la deuxième cruche respectivement. Appelons ces nombres L5 et L7. Alors, L5 est un entier entre \(0\) et \(5\) tandis que L7 est un entier entre \(0\) et \(7\).

    Instructions :

    • remplit(cruche): remplit au maximum la cruche (au robinet)

    • vide(cruche): vide entièrement la cruche (dans l’évacuation)

    • transvase(cruche1, cruche2): verse de l’eau de cruche1 dans cruche2 jusqu’à ce que cruche2 soit plein ou cruche1 soit vide.

    Le tableau suivant donne une suite d’instructions – avec l’évolution de l’état du système après chaque instruction – permettant d’obtenir 4 litres dans la cruche C7 :

    Instructions

    L5

    L7

    0

    0

    remplit(C7)

    0

    7

    transvase(C7,C5)

    5

    2

    vide(C5)

    0

    2

    transvase(C7,C5)

    2

    0

    remplit(C7)

    2

    7

    transvase(C7,C5)

    5

    4

    END SOLUTION

  2. Peut-on trouver une suite d’instructions de façon que l’une des deux cruches contienne 1 litre? 2 litres? 3 litres? 4 litres? 5 litres? 6 litres? 7 litres?

    BEGIN SOLUTION

    À faire

    • Donner le tableau avec la liste d’instructions et l’évolution de l’état

    Oui (se prouve en décrivant la suite d’instructions). Il est possible d’obtenir une cruche contenant :

    • 9 litres en 0 instructions

    • 1 litre en 8 instructions

    • 2 litres en 2 instructions

    • 3 litres en 4 instructions

    • 4 litres en 6 instructions

    • 5 litres en 1 instruction

    • 6 litres en 10 instructions

    • 7 litres en 10 instructions

    END SOLUTION

Notes aux enseignants

Pour l’exercice suivant, il y a toujours des élèves qui veulent utiliser racine(N). C’est naturel, mais cela ruine un peu l’exercice. Demandez-leur s’ils sont vraiment capables de calculer à la main la racine de n’importe quel entier (par exemple \(235\))? De tester si le résultat est exactement un entier?

Exercice 3

Écrivez un algorithme qui, étant donné un nombre entier \(N\), décide si \(N\) est ou non le carré d’un autre entier.

Par exemple, si l’entrée est \(16\), la réponse est oui. Si l’entrée est \(42\), la réponse est non.

Votre algorithme doit être assez simple pour que vous puissiez l’appliquer vous-même uniquement à l’aide d’un papier et d’un crayon pour poser les opérations (pas de calculatrice).

BEGIN SOLUTION

Algorithme :

Entrée: un entier $N$
Sortie: un booléen (vrai ou faux)

Pour $M$ nombre entier allant de $1$ à $N$ faire:
    Si $M*M$ est égal à $N$ alors répondre vrai (et s'arrêter).
Répondre faux (si on n'a pas déjà répondu).

Variante :

M $\leftarrow$ 1
Tant que M*M < N faire M $\leftarrow$ M + 1
Si M*M est égal à N répondre vrai, sinon répondre faux.

END SOLUTION

Notes aux enseignants

La rédaction de l’algorithme dans l’exercice suivant pose des questions de syntaxe (comment écrire la boucle, comment afficher les nombres, comment récupérer le nombre entré par l’utilisateur, comment réutiliser l’algorithme précédent). C’est intéressant de voir si les étudiants se posent ces questions et comment on peut y répondre. Comme pour l’instant on n’a pas donné de syntaxe, on peut choisir la variante qu’on veut, tant qu’elle est logique et expressive. En particulier on peut laisser les étudiants exprimer la boucle de la façon qui est naturelle pour eux, à condition que l’idée de boucle transparaisse bien dans leur solution.

Exercice 4 : Nombre mystère

On a fabriqué un robot «intelligent» capable de

  • poser des questions dont la réponse est « Oui » ou « Non »;

  • effectuer des opérations de base sur les nombres (addition, soustraction, multiplication, division).

Voici un exemple d’algorithme pour le robot :

Reponse = Demande("Êtes-vous né avant le 1er janvier 2000 ?")
Si Réponse est "Oui" alors
    Dire("Vous avez plus de 22 ans")
Sinon
    Dire("Vous avez 22 ans ou moins")

  1. Décrivez un algorithme qui permet au robot de deviner un nombre choisi entre 0 et 100 par l’utilisateur.

    BEGIN SOLUTION

    m = 0
M = 100
N = 50
Faire
    Réponse = Demande("Votre nombre est-il inférieur ou égal à ", N)
    Si Réponse est "Oui" alors M = N
    Sinon m = N+1
    N = (m + M) / 2      # division entière
Tant que m est différent de M

Dire("Votre nombre est", m)

    END SOLUTION

  2. Décrivez un algorithme qui permet au robot de donner l’âge exact de l’utilisateur.

    BEGIN SOLUTION

    # Invariant: l'âge de l'utilisateur est entre minimum inclus
# et maximum exclu
age_minimum = 0
age_maximum = 125  # hypothèse: personne n'a 125 ans ou plus
Tant que age_maximum > age_minimum + 1, faire:
	age = (age_minimum + age_maximum) / 2
    Réponse = Demande("Votre âge est-il au moins ", age)
    Si Réponse est "Oui" alors age_minimum = age
    Sinon age_maximum = age

# On a maintenant la garantie que:
# 1.  age_minimum ≤ age utilisateur < age_maximum
# 2.  age_maximum ≤ age_minimum + 1
# Donc l'âge de l'utilisateur est age_minimum

Dire("Vous avez ", age_minimum, "ans")

    END SOLUTION

  3. Quelles difficultés avez-vous rencontrées pour écrire les algorithmes?

    BEGIN SOLUTION

    Syntaxe : comment exprimer les boucles? Les variables? Comment afficher un nombre?

    Sémantique: quelles opérations s’autorise-t’on à utiliser dans le programme?

    Efficacité : tous les algorithmes sont-ils équivalents? On peut aborder ces différentes questions en fonction des réponses des étudiants.

    END SOLUTION

Notes aux enseignants

Les élèves n’ont pas du tout entendu parler de logique ou de booléens en amphi pour l’instant. L’exercice suivant est à introduire en douceur, ou à réserver à ceux qui ont déjà fait de l’informatique (pour les occuper utilement s’ils s’ennuient).

Exercice 5 : \(\clubsuit\) Un peu de logique et de booléens

  1. Construisez les tables de vérité correspondant aux opérations booléennes suivantes :

    • op1(a, b): (a ET (NON b)) OU ((NON a) ET b)

    • op2(a, b): (a OU b) ET ((NON a) OU (NON b)).

    BEGIN SOLUTION

    a

    b

    op(a, b)

    vrai

    vrai

    faux

    vrai

    faux

    vrai

    faux

    vrai

    vrai

    faux

    faux

    faux

    END SOLUTION

  2. Que constatez-vous?

    BEGIN SOLUTION

    Les deux opérations ont la même table de vérité

    END SOLUTION

  3. op1(a, b) est en fait une opération très courante en informatique; elle a même un nom. Savez-vous comment on l’appelle?

    BEGIN SOLUTION

    On l’appelle XOR ce qui est l’abréviation en anglais de OU exclusif (exclusive or).

    END SOLUTION

  4. Écrivez une opération op3(a, b) dont le résultat est vrai si et seulement si le résultat de op1(a, b) est faux. Utiliser au plus 5 mots OU, NON et ET dans l’écriture de op3(a, b).

    BEGIN SOLUTION

    S’il n’y avait pas la limitation sur le nombre de mots, on pourrait simplement mettre un NON en facteur de l’expression de op1 ou de op2, mais cela donne six mots. En cinq mots : op3(a, b): (a ET b) OU ((NON a) ET (NON b))

    END SOLUTION

  5. Expliquez pourquoi cette opération permet de déterminer si deux mots booléens sont identiques.

    À faire

    Solution

Exercice 6 : \(\clubsuit\) Notion de test de programme

Une collègue s’est occupée de coder un programme pointDeChute qui calcule l’abscisse à laquelle retombe un projectile lancé en \(x = 0\) avec une vitesse \(v\) suivant un angle \(\alpha\) (en degrés). Vous voulez tester si les résultats de ce programme sont cohérents.

  1. Spécifiez le programme sans écrire l’algorithme : que va-t-il prendre en entrée? renvoyer en sortie?

    BEGIN SOLUTION

    Deux entrées: vitesse et angle. 
Sortie: l'abscisse de retombée.

    END SOLUTION

  2. Donnez une série de tests dont vous connaissez le résultat sans calculs: situations extrêmes (par ex : tirer verticalement), symétries, …

    BEGIN SOLUTION

    • Pour toute vitesse \(v\), pointDeChute(v, 0) = 0 et pointDeChute(v, 90) = 0.

    • Pour tout angle \(\alpha\), pointDeChute(0, alpha) = 0

    • Pour toute vitesse \(v\) et tout angle \(\alpha\), pointDeChute(v, 180 - alpha) = -pointDeChute(v, alpha).

    END SOLUTION