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.

Exercice : 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.

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
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

Exercice : 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.

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
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

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

Exercice

É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

Exercice : 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 = Oui alors
    Dire("Vous avez plus de 22 ans")
Sinon
    Dire("Vous avez 22 ans ou moins")

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 == Oui alors M = N
    Sinon m = N+1
    N = (m + M) / 2      # division entière
Tant que m différent de M

Dire("Votre nombre est", m)

END SOLUTION

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

BEGIN SOLUTION

m = 1890  # date assez ancienne pour une annee de naissance
M = 2022  # annee actuelle
N = (m + M) / 2
Faire
    Réponse = Demande("Votre année de naissance est-elle au plus ", N)
    Si Réponse == Oui alors M = N
    Sinon m = N + 1
    N = (m + M) / 2      # division entière
Tant que m différent de M

Réponse = Demande("Votre anniversaire a-t-il eu lieu cette année ?")
Si Réponse == oui Dire("Vous avez ", M - m, "ans")
Sinon Dire("Vous avez ", M - m - 1, "ans")

END SOLUTION

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

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

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
Que constatez-vous?

BEGIN SOLUTION

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

END SOLUTION
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
É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
Expliquez pourquoi cette opération permet de déterminer si deux mots booléens sont identiques.

Exercice : \(\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.

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
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

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