TD 01 - Analyse et Test d’Algorithmes (Pseudo-code)

1 Partie 1 : Écriture d’algorithmes en pseudo-code

1.1 Exercice 1

  1. Écrire un algorithme qui calcule la somme des entiers de 1 à \(n\).
  2. Tester votre algorithme pour \(n=0\) puis 5 et -3.

1.2 Exercice 2 : Loups, moutons et serpents

Des loups, des moutons et des serpents sont sur une île.

  • Le matin, chaque loup tue un mouton.
  • Le midi chaque mouton tue un serpent.
  • Le soir chaque serpent tue un loup.

Écrire pour chacun des cas, un algorithme permettant de répondre à ces questions :

  1. Combien d’animaux reste-t-il au bout de cinq jours ?
  2. 🏠 À faire à la maison : À partir de combien de jours reste-t-il moins de 200 moutons ou 0 loup ?
  3. 🏠 À faire à la maison : En 7 jours, il ne reste qu’un loup, 2 moutons et 3 serpents. Combien y avait-il d’animaux au départ ?

2 Partie 2 : Tester un algorithme avec une valeur et vérification du résultat

2.1 Exercice 3 : Contre-exemples

Donner un contre exemple pour chacune des affirmations suivantes :

  1. \(a + b \geq \max(a,b)\).
  2. 🏠 À faire à la maison : \(a\times b \geq \min(a,b)\).
  3. Si la somme des chiffres d’un entier \(n\) est multiple de 6 alors \(n\) est multiple de 6.
  4. 🏠 À faire à la maison : Si \(p\) est impair et \(p\) est premier alors \(p+2\) ou \(p+4\) est premier.
  5. \(n^2-n+41\) est premier pour tout \(n\geq 0\).
  6. 🏠 À faire à la maison : L’équation \(ax^2+bx+c=0\) a toujours 2 solutions (dans \(\mathbb{R}\) ou \(\mathbb{C}\)).
  7. 🏠 À faire à la maison : L’équation \(ax^2+bx+c=0\) a au moins une solution (dans \(\mathbb{R}\) ou \(\mathbb{C}\)).

2.2 Exercice 4 : Analyse de conditions

Pour chaque algorithme, si le dernier BLOC est exécuté, que peut-on dire des valeurs des variables ?

ALGO 1
SI x > 0 ALORS
  BLOC 1
SINON SI x < -1 ALORS
  BLOC 2
SINON
  BLOC 3
FSI

Question : Que peut-on dire de \(x\) si BLOC 3 est exécuté ?

ALGO 2
SI x > 0 OU y > 0 ALORS
  BLOC 1
SINON SI x < -1 ALORS
  BLOC 2
SINON
  BLOC 3
FSI

Question : Que peut-on dire de \(x\) et \(y\) si BLOC 3 est exécuté ?

ALGO 3
SI x*y ≠ 0 ALORS
  BLOC 1
SINON SI x = 0 ALORS
  BLOC 2
SINON
  BLOC 3
FSI

Question : Que peut-on dire de \(x\) et \(y\) si BLOC 3 est exécuté ?

ALGO 4
SI x > 0 ET y = 0 ALORS
  BLOC 1
SINON SI x = 0 ET y > 0 ALORS
  BLOC 2
SINON SI x = 0 ALORS
  BLOC 3
SINON
  BLOC 4
FSI

Question : Que peut-on dire de \(x\) et \(y\) si BLOC 4 est exécuté ?

ALGO 5
SI x > 0 ET y > 0 ALORS
  BLOC 1
SINON SI |x-y| < 1 ALORS
  BLOC 2
SINON SI xy ≥ 0 ALORS
  BLOC 3
SINON
  BLOC 4
FSI

Question : Que peut-on dire de \(x\) et \(y\) si BLOC 4 est exécuté ?

ALGO 6
SI x > 10 ALORS
  BLOC 1
SINON SI y < 5 ALORS
  BLOC 2
SINON
  BLOC 3
FSI

Question : Que peut-on dire de \(x\) et \(y\) si BLOC 3 est exécuté ?

3 Partie 3 : Chercher les erreurs

3.1 Exercice 5 : Factorielle

Voici un algorithme :

ALGORITHME exo(n):
DONNEES:
  n : entier positif
VARIABLES :
  f, i : entiers
DEBUT :
  f ← 1
  i ← 1
  TQ i < n FAIRE
    f ← f * i
    i ← i + 1
  FTQ
  AFFICHER f
FIN
  1. Que semble faire cet algorithme ?
  2. Tester-le pour les nombres 0 ; 1 ; 2 et 5. Que constatez-vous ?
  3. Modifier cet algorithme pour corriger l’erreur.

Pensez à tracer l’exécution pas à pas pour \(n=2\) et \(n=5\) pour identifier où se situe le problème.

3.2 Exercice 6 : Test de primalité 🏠

  1. Trouver et expliquer l’erreur dans l’algorithme suivant qui annonce si un nombre entier est premier ou non.
ALGORITHME EstPremier(n)
DONNEES :
  n : entier
VARIABLES :
  Diviseur : entier
  Premier : booléen
DEBUT
  Diviseur ← 1
  Premier ← Vrai
  TQ Diviseur < n FAIRE
    SI n mod Diviseur = 0 ALORS
      Premier ← Faux
    FSI
    Diviseur ← Diviseur + 1
  FTQ
  SI Premier = Vrai ALORS
    AFFICHER "Nombre premier"
  SINON
    AFFICHER "Non premier"
  FSI
FIN

  1. On peut améliorer un peu cet algorithme en s’arrêtant dès qu’on sait que le nombre n’est pas premier. Modifier la condition de la boucle en utilisant un ET.

  2. Essayer de modifier la condition dans le cas où le nombre est premier afin de faire moins d’itérations dans la boucle.

Tester l’algorithme avec \(n=1\). Que se passe-t-il ?

Jusqu’à quelle valeur faut-il tester les diviseurs pour être sûr qu’un nombre est premier ?

3.3 Exercice 7 : Invalidation d’un algorithme

  1. Proposer une instance qui invalide l’algorithme sensé le résoudre.
NoteSpécification du problème
Problème Somme des diviseurs propres
Entrée Un entier \(n > 0\)
Sortie La somme des diviseurs propres de \(n\)

Définition : Un diviseur propre de \(n\) est un diviseur de \(n\) qui est différent de 1 et de \(n\).

ALGORITHME SomDivPropre(n): entier
DEBUT
  d ← 2
  s ← 1
  TQ d < n FAIRE
    SI n mod d = 0 ALORS
      s ← s + d
    FSI
    d ← d + 1
  FTQ
  RENVOYER s
FIN
  1. Proposer une correction de cet algorithme.

Quelle est la différence entre “diviseur de \(n\)” et “diviseur propre de \(n\)” ? Vérifier la définition donnée dans l’énoncé.

4 Conseils généraux

ImportantMéthodologie pour tester un algorithme
  1. Cas normaux : Tester avec des valeurs typiques
  2. Cas limites : Tester avec 0, 1, -1, valeurs minimales/maximales
  3. Cas particuliers : Tester avec des valeurs qui pourraient poser problème
  4. Traçage : Suivre l’exécution pas à pas pour comprendre le comportement

Pour invalider une affirmation, un seul contre-exemple suffit !

NoteRappels sur les nombres premiers
  • 1 n’est pas considéré comme un nombre premier
  • Les deux seuls nombres premiers pairs sont 2
  • Pour tester si \(n\) est premier, il suffit de vérifier les diviseurs jusqu’à \(\sqrt{n}\)