CORRECTION DE L'EVALUATION EN ALGORITHMIQUE TEST 20 / XX

Examen Corriges en Algorithme

Exercice 1 : Generalites — 6.25 pts

1. Definir : Algorithmique, constante, instruction. (0,75 pt)
   • Algorithmique : discipline qui etudie la conception et l’ecriture d’algorithmes (suite finie d’etapes) permettant de resoudre un probleme.
   • Constante : donnee (valeur) fixee a l’avance qui ne change pas pendant l’execution de l’algorithme. Exemple : PI = 3.1415.
   • Instruction : action elementaire executée par l’algorithme (affectation, lecture, ecriture, test, boucle...). Exemple : s <- s + i.
2. Donner la difference fondamentale entre la boucle REPETER et la structure SI. (0,5 pt)
   • SI est une structure de decision : elle choisit d’executer un bloc ou un autre selon une condition, et s’execute une seule fois.
   • REPETER...JUSQU’A est une structure de repetition : elle repete un bloc plusieurs fois jusqu’a ce que la condition devienne vraie (le bloc s’execute au moins une fois).
3. Qu’est-ce qu’une boucle infinie ? Donner un exemple. (0,5 pt)
   • Boucle infinie : boucle qui ne se termine jamais parce que la condition d’arret n’est jamais satisfaite (ou parce que les variables ne progressent pas vers l’arret).
   • Exemple :

     Tantque (VRAI) faire
       Ecrire("Je ne m'arrete jamais");
     FinTantque
             

   • Autre exemple (erreur logique) :

     i <- 1;
     Tantque (i <= 10) faire
       Ecrire(i);
       i <- i - 1;   // i s'eloigne de 10, donc boucle infinie
     FinTantque
             

4. Les affirmations suivantes sont-elles correctes ? (0,5*3 = 1,5 pts)
   1. "Dans une boucle POUR le test s’effectue toujours."
      • Vrai : la boucle POUR controle toujours une condition de poursuite (bornes). Le test d’entree (ou de poursuite) est fait automatiquement par la structure a chaque iteration.
      • Precision : ce test n’est pas ecrit explicitement comme dans TANTQUE, mais il existe (controle des bornes).
   2. "Les actions internes d’une boucle REPETER peuvent ne pas etre executees."
      • Faux : dans REPETER...JUSQU’A, le corps s’execute toujours au moins une fois (test en fin de boucle).
   3. "Les actions d’une boucle POUR sont toujours executees."
      • Faux : si l’intervalle d’iteration est vide (ex : pour i de 5 a 1), alors le corps peut ne jamais s’executer.

5) Donner la signification de : mod, div, abs( ), puis donner un exemple d’algorithme ou on les utilise. (1,25 pts)

• mod : retourne le reste de la division entiere. Exemple : 17 mod 5 = 2.
• div : division entiere (quotient sans la partie decimale). Exemple : 17 div 5 = 3.
• abs(x) : valeur absolue de x. Exemple : abs(-7) = 7.

Exemple d’algorithme utilisant mod, div, abs :

Algorithme Exemple_Mod_Div_Abs;
Var n, q, r : entier;
Debut
  Lire(n);
  n <- abs(n);         // on rend n positif
  q <- n div 10;        // quotient par 10
  r <- n mod 10;        // dernier chiffre
  Ecrire("Quotient=", q, " Reste=", r);
Fin.

6) Soit l’algorithme suivant : (0,5 + 1,25 = 1,75 pt)

Algorithme InvariantGenius;
Var s, i, n : entier;
Debut
  Lire(n);
  s <- 0;
  Pour i de 1 a n faire
    s <- s + i;
  FinPour
  Ecrire(s);
Fin.

• (a) C’est quoi un invariant de boucle ? (0,5 pt)

  Un invariant de boucle est une propriete logique qui reste vraie : avant la premiere iteration, avant et apres chaque iteration (maintenance), et qui permet, a la fin de la boucle, de conclure sur le resultat de l’algorithme.

• (b) Verifier l’invariant propose : S = somme de k=0 a i-1 de k. Pourquoi ? (1,25 pt)

  L’invariant correct (au debut de chaque iteration i) est : s = 1 + 2 + ... + (i-1). Ce qui est equivalent a s = somme(k=1 a i-1) k.

  L’ecriture donnee somme(k=0 a i-1) k est aussi correcte car ajouter 0 ne change rien.

  Preuve rapide par les 3 points :

  • Initialisation : avant la boucle, i=1 et s=0. Or somme(k=1 a 0) k = 0 (somme vide) donc l’invariant est vrai.
  • Maintenance : si avant une iteration on a s = 1+...+(i-1), alors apres s <- s + i, on obtient s = 1+...+(i-1)+i = 1+...+i. A l’iteration suivante, l’invariant devient vrai pour i+1 (car i devient l’ancien i+1).
  • Terminaison : a la fin, i a depasse n, donc l’invariant donne s = 1 + 2 + ... + n, ce qui correspond bien au resultat affiche.

Exercice 2 : Ecriture des Algorithmes

Ecrire un algorithme qui demande successivement 20 nombres a Bob, puis affiche le plus grand parmi ces 20 nombres.

Correction :

Algorithme Max20;
Var i : entier;
Var x, maxi : entier;
Debut
  Lire(x);
  maxi <- x;
  Pour i de 2 a 20 faire
    Lire(x);
    Si (x > maxi) Alors
      maxi <- x;
    FinSi
  FinPour
  Ecrire("Le plus grand est : ", maxi);
Fin.

Exercice 3 : Execution Manuelle d’un Algorithme — 5 pts

ALGORITHME 01 (Genius1)

(a) Potentielles erreurs + algorithme soft (1 pt)

• Variable n est lue mais n’est pas declaree correctement dans l’extrait (il manque le type).
• Variables i et sum sont utilisees sans declaration claire.
• Probleme de syntaxe : "Pour i = 1 de 1 a n" est incorrect ; on doit ecrire "Pour i de 1 a n".
• Confusion sum / Sum (majuscule-minuscule) : incoherent.
• Le symbole de fleche est mal encode dans l’extrait : on doit utiliser "<-".

Version soft (corrigee) :

Algorithme Genius1_Soft;
Var n, i : entier;
Var sum : entier;
Debut
  Ecrire("Entrer un nombre :");
  Lire(n);
  sum <- 0;
  Pour i de 1 a n faire
    sum <- sum + i * i;
  FinPour
  Ecrire("Resultat: ", sum);
Fin.

(b) Pour n = 4 : que fait l’algorithme + trace (1,5 pt)

L’algorithme calcule la somme des carres des entiers de 1 a n : sum = 1^2 + 2^2 + ... + n^2. Pour n = 4 : sum = 1 + 4 + 9 + 16 = 30.

Tableau de trace (n=4) :

ALGORITHME 02 (Genius2)

(a) Potentielles erreurs + algorithme soft (1 pt)

• Les variables a, b, Y, R, Q ne sont pas declarees explicitement.
• La chaine d’affichage "Entrer deux nombres" est mal fermee dans l’extrait.
• Manque de gestion du cas b = 0 (division par 0 impossible).
• Si b est negatif, la condition "R >= Y" doit etre adaptee (ou utiliser abs(b)).

Interprétation : cet algorithme realise la division entiere de a par b par soustractions successives, et retourne le reste et le quotient.

Version soft (corrigee) :

Algorithme Genius2_Soft;
Var a, b : entier;
Var Y, R, Q : entier;
Debut
  Ecrire("Entrer deux nombres :");
  Lire(a, b);

  Si (b = 0) Alors
    Ecrire("Erreur : division par 0 impossible");
  Sinon
    Y <- abs(b);
    R <- abs(a);
    Q <- 0;

    Tantque (R >= Y) faire
      R <- R - Y;
      Q <- Q + 1;
    FinTantque

    Ecrire("Reste=", R, " Quotient=", Q);
  FinSi
Fin.

(b) Pour a = 5 et b = 2 : que fait l’algorithme + trace (1,5 pt)

Il calcule le quotient et le reste de la division entiere : 5 = 2*2 + 1 donc quotient = 2, reste = 1.

Tableau de trace (a=5, b=2) :

PROBLEME : Algorithme d’Euclide pour le PGCD et le PPCM — 5,5 pts

Question : Concevez un algorithme qui calcule le PGCD(a,b) par Euclide puis le PPCM(a,b).

Correction (avec conditions de validite) :

Algorithme PGCD_PPCM_Euclide;
Var a, b : entier;
Var A0, B0 : entier;
Var r, pgcd, ppcm : entier;
Debut
  Lire(a, b);

  a <- abs(a);
  b <- abs(b);

  Si (a = 0 et b = 0) Alors
    Ecrire("PGCD indefini (0,0)");
  Sinon
    A0 <- a;
    B0 <- b;

    Tantque (b <> 0) faire
      r <- a mod b;
      a <- b;
      b <- r;
    FinTantque

    pgcd <- a;

    Si (pgcd = 0) Alors
      ppcm <- 0;
    Sinon
      ppcm <- (A0 * B0) div pgcd;
    FinSi

    Ecrire("PGCD=", pgcd);
    Ecrire("PPCM=", ppcm);
  FinSi
Fin.

• La boucle d’Euclide applique : PGCD(a,b) = PGCD(b, a mod b) jusqu’a obtenir b=0.
• Ensuite : PPCM(a,b) = (a*b)/PGCD(a,b). Ici on utilise div car on travaille en entiers.