Practical activity

Duration2h30

Présentation & objectifs

Voici quelques exercices pour vous faire manipuler des programmes simples et votre IDE.

Pendant cette activité, veuillez porter attention aux bonnes pratiques de programmation que vous avez étudiées précédemment. Ce sont de bons réflexes à acquérir rapidement.

Pour chaque exercice, nous vous demandons de montrer votre solution à un autre étudiant, afin qu’il puisse vous faire des remarques sur la lisibilité.

Important

Le but de cette séance est de vous aider à maîtriser des notions importantes en informatique. Un assistant de programmation intelligent tel que GitHub Copilot, que vous avez peut-être déjà installé, sera capable de vous fournir une solution à ces exercices basée uniquement sur un nom de fichier judicieusement choisi.

Pour l’entraînement, nous vous conseillons de désactiver d’abord ces outils.

À la fin de l’activité pratique, nous vous suggérons de retravailler l’exercice avec ces outils activés. Suivre ces deux étapes améliorera vos compétences à la fois de manière fondamentale et pratique.

De plus, nous vous fournissons les solutions aux exercices. Assurez-vous de ne les consulter qu’après avoir une solution aux exercices, à des fins de comparaison ! Même si vous êtes sûr que votre solution est correcte, veuillez les consulter, car elles fournissent parfois des éléments supplémentaires que vous auriez pu manquer.

Contenu de l’activité

1 — Correction de bugs syntaxiques

Le code suivant contient une erreur de syntaxe. Utilisez l’onglet Erreur de votre IDE pour trouver l’emplacement de l’erreur. Que dit-il ?

​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# Loop to append to a new string
result = ""
for i j in range(len(s)):
    result = s[i] + result

# Print the result
print("Reversed string:", result)
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // Loop to append to a new string
        String result = "";
        for (int i j = 0; i < s.length(); i++) {
            result = s.charAt(i) + result;
        }

        // Print the result
        System.out.println("Reversed string: " + result);
    }

}
Correction
Sortie
Expected "in" Pylance [Ln 7, Col 7]
Unexpected indentation Pylance [Ln 8, Col 1]
Unindent not expected Pylance [Ln 11, Col 1]
Main.java:25: error: ';' expected
        for (int i j = 0; i < s.length(); i++) {
                  ^

Comme vous pouvez le voir, l’onglet Problèmes ne vous dit pas directement qu’il y a un j en trop. Comme il essaie d’analyser le programme, il rencontre quelque chose d’inattendu, et vous l’indique. Dans ce cas, les erreurs affichées sont des conséquences indirectes de votre erreur de syntaxe.

Par conséquent, vous devrez parfois interpréter les messages pour relier les messages d’erreur aux erreurs réelles à corriger. Avec le temps et l’expérience, vous apprendrez à interpréter ces messages efficacement.

Vérifiez à nouveau votre code. Votre IDE devrait avoir souligné les lignes correspondant aux problèmes identifiés ci-dessus. Cela vous aidera à trouver les erreurs plus facilement.

Essayez de corriger l’erreur et exécutez à nouveau le code pour voir la différence !

Correction
​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# Loop to append to a new string
result = ""
for i in range(len(s)):
    result = s[i] + result

# Print the result
print("Reversed string:", result)
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // Loop to append to a new string
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            result = s.charAt(i) + result;
        }

        // Print the result
        System.out.println("Reversed string: " + result);
    }

}

2 — Correction de bugs sémantiques

Voici un code qui est syntaxiquement correct :

​
# Needed imports
import random

# Fill a list with 10 random numbers
numbers = []
for i in range(10):
    numbers.append(random.randint(-50, 50))

# Let's do the following operation 50 times
for i in range(50):

    # Divide each number by the subtraction of the two next numbers in the list
    for j in range(len(numbers) - 2):
        numbers[j] /= numbers[j + 1] - numbers[j + 2]

# Print the final list
print("Final list", numbers)
// Needed imports
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Use a random number generator
        Random random = new Random();

        // Fill a list with 10 random numbers
        List<Double> numbers = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            numbers.add((double) (random.nextInt(101) - 50));
        }

        // Let's do the following operation 50 times
        for (int k = 0; k < 50; k++) {
            // Divide each number by the subtraction of the two next numbers in the list
            for (int j = 0; j < numbers.size() - 2; j++) {
                numbers.set(j, numbers.get(j) / (numbers.get(j + 1) - numbers.get(j + 2)));
            }
        }

        // Print the final list
        System.out.println("Final list " + numbers);
    }

}

Cependant, lors de son exécution, on obtient la sortie suivante :

Sortie
Traceback (most recent call last):
  File "session_1.py", line 14, in <module>
    numbers[j] /= numbers[j + 1] - numbers[j + 2]
ZeroDivisionError: float division by zero
Final list [0.0, 0.0, -Infinity, 0.0, 0.0, Infinity, 5.139385345176833E-80, 2.240361480978435E-62, -41.0, -23.0]
# Here, no error is raised, but the values `Infinity` and `-Infinity` indicate that the division by zero was not handled correctly

Utilisez la commande print pour trouver la source de l’erreur. C’est-à-dire, ajoutez quelques print là où c’est pertinent pour comprendre ce qui mène à l’erreur. Puis exécutez le code et essayez d’analyser pourquoi cela arrive.

Correction

Avant toute chose, notez que le programme utilise des nombres aléatoires. Par conséquent, nous devrions fixer la graine à une valeur qui mène à l’erreur. Sur notre ordinateur, la graine 42 mène à une erreur. Cela peut être différent pour vous, essayez de trouver une telle valeur.

​
# Needed imports
import random

# Set the seed
random.seed(42)

# Fill a list with 10 random numbers
numbers = []
for i in range(10):
    numbers.append(random.randint(-50, 50))

# Let's do the following operation 50 times
for i in range(50):

    # Divide each number by the subtraction of the two next numbers in the list
    for j in range(len(numbers) - 2):
        numbers[j] /= numbers[j + 1] - numbers[j + 2]

# Print the final list
print("Final list", numbers)
// Needed imports
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Use a random number generator
        Random random = new Random();

        // Set the seed
        random.setSeed(42);

        // Fill a list with 10 random numbers
        List<Double> numbers = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            numbers.add((double) (random.nextInt(101) - 50));
        }

        // Let's do the following operation 50 times
        for (int k = 0; k < 50; k++) {
            // Divide each number by the subtraction of the two next numbers in the list
            for (int j = 0; j < numbers.size() - 2; j++) {
                numbers.set(j, numbers.get(j) / (numbers.get(j + 1) - numbers.get(j + 2)));
            }
        }

        // Print the final list
        System.out.println("Final list " + numbers);
    }

}

À ce stade, on obtient la sortie suivante lors de l’exécution du programme :

Sortie
Traceback (most recent call last):
  File "session_1.py", line 17, in <module>
    numbers[j] /= numbers[j + 1] - numbers[j + 2]
ZeroDivisionError: float division by zero
Final list [-0.0, -0.0, Infinity, 0.0, 0.0, -Infinity, -2.8530960909304215E-69, -5.679991152181034E-82, 25.0, -20.0]
# Here, no error is raised, but the values `Infinity` and `-Infinity` indicate that the division by zero was not handled correctly

Le message d’erreur nous indique que le crash se produit dans la dernière boucle. Cela semble lié à la soustraction de deux nombres qui vaut 0. Regardons la liste numbers avant cette boucle, et quelles parties posent problème.

​
# Needed imports
import random

# Set the seed
random.seed(42)

# Fill a list with 10 random numbers
numbers = []
for i in range(10):
    numbers.append(random.randint(-50, 50))

# Let's do the following operation 50 times
for i in range(50):

    # Debug
    print("Current list", numbers)

    # Divide each number by the subtraction of the two next numbers in the list
    for j in range(len(numbers) - 2):

        # Debug
        print("  numbers[j+1] =", numbers[j + 1], "/ numbers[j+2] =", numbers[j + 2], "/ difference =", numbers[j + 1] - numbers[j + 2])

        numbers[j] /= numbers[j + 1] - numbers[j + 2]

# Print the final list
print("Final list", numbers)
// Needed imports
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Use a random number generator
        Random random = new Random();

        // Set the seed
        random.setSeed(42);

        // Fill a list with 10 random numbers
        List<Double> numbers = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            numbers.add((double) (random.nextInt(101) - 50));
        }

        // Let's do the following operation 50 times
        for (int k = 0; k < 50; k++) {
            // Debug
            System.out.println(numbers);

            // Divide each number by the subtraction of the two next numbers in the list
            for (int j = 0; j < numbers.size() - 2; j++) {
                // Debug
                System.out.println("  numbers[j+1] = " + numbers.get(j + 1) + "/ numbers[j+2] = " + numbers.get(j + 2) + "/ division = " + (numbers.get(j + 1) / numbers.get(j + 2)));

                numbers.set(j, numbers.get(j) / (numbers.get(j + 1) - numbers.get(j + 2)));
            }
        }

        // Print the final list
        System.out.println("Final list " + numbers);
    }

}

Voici ce que nous obtenons :

Sortie
Current list [31, -36, -47, 44, -15, -19, -22, -33, 44, -37]
  numbers[j+1] = -36 / numbers[j+2] = -47 / difference = 11
  numbers[j+1] = -47 / numbers[j+2] = 44 / difference = -91
  numbers[j+1] = 44 / numbers[j+2] = -15 / difference = 59
  numbers[j+1] = -15 / numbers[j+2] = -19 / difference = 4
  numbers[j+1] = -19 / numbers[j+2] = -22 / difference = 3
  numbers[j+1] = -22 / numbers[j+2] = -33 / difference = 11
  numbers[j+1] = -33 / numbers[j+2] = 44 / difference = -77
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [2.8181818181818183, 0.3956043956043956, -0.7966101694915254, 11.0, -5.0, -1.7272727272727273, 0.2857142857142857, -0.4074074074074074, 44, -37]
  numbers[j+1] = 0.3956043956043956 / numbers[j+2] = -0.7966101694915254 / difference = 1.192214565095921
  numbers[j+1] = -0.7966101694915254 / numbers[j+2] = 11.0 / difference = -11.796610169491526
  numbers[j+1] = 11.0 / numbers[j+2] = -5.0 / difference = 16.0
  numbers[j+1] = -5.0 / numbers[j+2] = -1.7272727272727273 / difference = -3.2727272727272725
  numbers[j+1] = -1.7272727272727273 / numbers[j+2] = 0.2857142857142857 / difference = -2.012987012987013
  numbers[j+1] = 0.2857142857142857 / numbers[j+2] = -0.4074074074074074 / difference = 0.693121693121693
  numbers[j+1] = -0.4074074074074074 / numbers[j+2] = 44 / difference = -44.407407407407405
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [2.3638209938787975, -0.03353543008715422, -0.04978813559322034, -3.361111111111111, 2.4838709677419355, -2.492019430950729, -0.006433933039437627, -0.005029721079103795, 44, -37]
  numbers[j+1] = -0.03353543008715422 / numbers[j+2] = -0.04978813559322034 / difference = 0.01625270550606612
  numbers[j+1] = -0.04978813559322034 / numbers[j+2] = -3.361111111111111 / difference = 3.311322975517891
  numbers[j+1] = -3.361111111111111 / numbers[j+2] = 2.4838709677419355 / difference = -5.844982078853047
  numbers[j+1] = 2.4838709677419355 / numbers[j+2] = -2.492019430950729 / difference = 4.975890398692664
  numbers[j+1] = -2.492019430950729 / numbers[j+2] = -0.006433933039437627 / difference = -2.4855854979112912
  numbers[j+1] = -0.006433933039437627 / numbers[j+2] = -0.005029721079103795 / difference = -0.0014042119603338322
  numbers[j+1] = -0.005029721079103795 / numbers[j+2] = 44 / difference = -44.005029721079104
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [145.4416923383329, -0.010127502009044973, 0.008518098930252016, -0.6754793296882482, -0.9993102107447938, 1774.6746939531017, 0.0001462090374718159, -6.209532196424438e-05, 44, -37]
  numbers[j+1] = -0.010127502009044973 / numbers[j+2] = 0.008518098930252016 / difference = -0.01864560093929699
  numbers[j+1] = 0.008518098930252016 / numbers[j+2] = -0.6754793296882482 / difference = 0.6839974286185002
  numbers[j+1] = -0.6754793296882482 / numbers[j+2] = -0.9993102107447938 / difference = 0.32383088105654556
  numbers[j+1] = -0.9993102107447938 / numbers[j+2] = 1774.6746939531017 / difference = -1775.6740041638466
  numbers[j+1] = 1774.6746939531017 / numbers[j+2] = 0.0001462090374718159 / difference = 1774.6745477440643
  numbers[j+1] = 0.0001462090374718159 / numbers[j+2] = -6.209532196424438e-05 / difference = 0.00020830435943606026
  numbers[j+1] = -6.209532196424438e-05 / numbers[j+2] = 44 / difference = -44.000062095321965
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [-7800.32206051368, -0.014806345148840596, 0.026304158832723037, 0.0003804072865313625, -0.0005630949133829072, 8519623.395101551, -3.32292798030757e-06, -7.666089131388194e-07, 44, -37]
  numbers[j+1] = -0.014806345148840596 / numbers[j+2] = 0.026304158832723037 / difference = -0.041110503981563636
  numbers[j+1] = 0.026304158832723037 / numbers[j+2] = 0.0003804072865313625 / difference = 0.025923751546191674
  numbers[j+1] = 0.0003804072865313625 / numbers[j+2] = -0.0005630949133829072 / difference = 0.0009435021999142697
  numbers[j+1] = -0.0005630949133829072 / numbers[j+2] = 8519623.395101551 / difference = -8519623.395664645
  numbers[j+1] = 8519623.395101551 / numbers[j+2] = -3.32292798030757e-06 / difference = 8519623.395104874
  numbers[j+1] = -3.32292798030757e-06 / numbers[j+2] = -7.666089131388194e-07 / difference = -2.5563190671687508e-06
  numbers[j+1] = -7.666089131388194e-07 / numbers[j+2] = 44 / difference = -44.00000076660891
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [189740.36572287712, -0.5711497860353364, 27.879276630317488, -4.465071621885766e-11, -6.609387378630434e-11, -3332769959947.7046, 7.552108914573704e-08, -9.464307569615054e-09, 44, -37]
  numbers[j+1] = -0.5711497860353364 / numbers[j+2] = 27.879276630317488 / difference = -28.450426416352823
  numbers[j+1] = 27.879276630317488 / numbers[j+2] = -4.465071621885766e-11 / difference = 27.87927663036214
  numbers[j+1] = -4.465071621885766e-11 / numbers[j+2] = -6.609387378630434e-11 / difference = 2.144315756744668e-11
  numbers[j+1] = -6.609387378630434e-11 / numbers[j+2] = -3332769959947.7046 / difference = 3332769959947.7046
  numbers[j+1] = -3332769959947.7046 / numbers[j+2] = 7.552108914573704e-08 / difference = -3332769959947.7046
  numbers[j+1] = 7.552108914573704e-08 / numbers[j+2] = -9.464307569615054e-09 / difference = 8.49853967153521e-08
  numbers[j+1] = -9.464307569615054e-09 / numbers[j+2] = 44 / difference = -44.00000000946431
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [-6669.1571840138595, -0.020486535343364014, 1300147916305.0884, -1.3397479200622142e-23, 1.9831513900029704e-23, -3.9215795757362864e+19, -1.7163883893066504e-09, -1.168433033285809e-10, 44, -37]
  numbers[j+1] = -0.020486535343364014 / numbers[j+2] = 1300147916305.0884 / difference = -1300147916305.109
  numbers[j+1] = 1300147916305.0884 / numbers[j+2] = -1.3397479200622142e-23 / difference = 1300147916305.0884
  numbers[j+1] = -1.3397479200622142e-23 / numbers[j+2] = 1.9831513900029704e-23 / difference = -3.3228993100651846e-23
  numbers[j+1] = 1.9831513900029704e-23 / numbers[j+2] = -3.9215795757362864e+19 / difference = 3.9215795757362864e+19
  numbers[j+1] = -3.9215795757362864e+19 / numbers[j+2] = -1.7163883893066504e-09 / difference = -3.9215795757362864e+19
  numbers[j+1] = -1.7163883893066504e-09 / numbers[j+2] = -1.168433033285809e-10 / difference = -1.5995450859780694e-09
  numbers[j+1] = -1.168433033285809e-10 / numbers[j+2] = 44 / difference = -44.00000000011684
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [5.129537262934622e-09, -1.5757080472493495e-14, -3.9126912824800088e+34, -3.416347658355685e-43, -5.057021926249269e-43, 2.451684300813796e+28, 3.900882702959301e-11, -1.4425099176368013e-12, 44, -37]
  numbers[j+1] = -1.5757080472493495e-14 / numbers[j+2] = -3.9126912824800088e+34 / difference = 3.9126912824800088e+34
  numbers[j+1] = -3.9126912824800088e+34 / numbers[j+2] = -3.416347658355685e-43 / difference = -3.9126912824800088e+34
  numbers[j+1] = -3.416347658355685e-43 / numbers[j+2] = -5.057021926249269e-43 / difference = 1.640674267893584e-43
  numbers[j+1] = -5.057021926249269e-43 / numbers[j+2] = 2.451684300813796e+28 / difference = -2.451684300813796e+28
  numbers[j+1] = 2.451684300813796e+28 / numbers[j+2] = 3.900882702959301e-11 / difference = 2.451684300813796e+28
  numbers[j+1] = 3.900882702959301e-11 / numbers[j+2] = -1.4425099176368013e-12 / difference = 4.0451336947229815e-11
  numbers[j+1] = -1.4425099176368013e-12 / numbers[j+2] = 44 / difference = -44.00000000000144
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [1.3109997422754321e-43, 4.027171922060274e-49, -2.3848068803464593e+77, 1.3934696474671249e-71, -2.0626725572173683e-71, 6.060823908025844e+38, -8.865642506725394e-13, -1.780876441526915e-14, 44, -37]
  numbers[j+1] = 4.027171922060274e-49 / numbers[j+2] = -2.3848068803464593e+77 / difference = 2.3848068803464593e+77
  numbers[j+1] = -2.3848068803464593e+77 / numbers[j+2] = 1.3934696474671249e-71 / difference = -2.3848068803464593e+77
  numbers[j+1] = 1.3934696474671249e-71 / numbers[j+2] = -2.0626725572173683e-71 / difference = 3.456142204684493e-71
  numbers[j+1] = -2.0626725572173683e-71 / numbers[j+2] = 6.060823908025844e+38 / difference = -6.060823908025844e+38
  numbers[j+1] = 6.060823908025844e+38 / numbers[j+2] = -8.865642506725394e-13 / difference = 6.060823908025844e+38
  numbers[j+1] = -8.865642506725394e-13 / numbers[j+2] = -1.780876441526915e-14 / difference = -8.687554862572702e-13
  numbers[j+1] = -1.780876441526915e-14 / numbers[j+2] = 25.0 / difference = -44.00000000000144
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [7.96687086516761e-269, 2.4472894707970443e-274, -6.249358773299426e+257, -3.295579109903561e-161, 4.8782552260775314e-161, -3.42502193481704e+64, -4.579360798928404e-16, -2.7143369021900854e-18, 44, -37]
  numbers[j+1] = 2.4472894707970443e-274 / numbers[j+2] = -6.249358773299426e+257 / difference = 6.249358773299426e+257
  numbers[j+1] = -6.249358773299426e+257 / numbers[j+2] = -3.295579109903561e-161 / difference = -6.249358773299426e+257
  numbers[j+1] = -3.295579109903561e-161 / numbers[j+2] = 4.8782552260775314e-161 / difference = -8.173834335981092e-161
  numbers[j+1] = 4.8782552260775314e-161 / numbers[j+2] = -3.42502193481704e+64 / difference = 3.42502193481704e+64
  numbers[j+1] = -3.42502193481704e+64 / numbers[j+2] = -4.579360798928404e-16 / difference = -3.42502193481704e+64
  numbers[j+1] = -4.579360798928404e-16 / numbers[j+2] = -2.7143369021900854e-18 / difference = -4.552217429906503e-16
  numbers[j+1] = -2.7143369021900854e-18 / numbers[j+2] = 25.0 / difference = -44.0
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [0.0, -0.0, inf, -9.622067165183299e-226, -1.424298973529967e-225, 7.523854006436124e+79, 1.0407638179382736e-17, -3.351033212580352e-20, 44, -37]
  numbers[j+1] = -0.0 / numbers[j+2] = inf / difference = -inf
  numbers[j+1] = inf / numbers[j+2] = -9.622067165183299e-226 / difference = inf
  numbers[j+1] = -9.622067165183299e-226 / numbers[j+2] = -1.424298973529967e-225 / difference = 4.620922570116372e-226
  numbers[j+1] = -1.424298973529967e-225 / numbers[j+2] = 7.523854006436124e+79 / difference = -7.523854006436124e+79
  numbers[j+1] = 7.523854006436124e+79 / numbers[j+2] = 1.0407638179382736e-17 / difference = 7.523854006436124e+79
  numbers[j+1] = 1.0407638179382736e-17 / numbers[j+2] = -3.351033212580352e-20 / difference = 1.044114851150854e-17
  numbers[j+1] = -3.351033212580352e-20 / numbers[j+2] = 44 / difference = -44.0
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Current list [1.3109997422754321e-43, 4.027171922060274e-49, -2.3848068803464593e+77, 1.3934696474671249e-71, -2.0626725572173683e-71, 6.060823908025844e+38, -8.865642506725394e-13, -1.780876441526915e-14, 44, -37]
  numbers[j+1] = 4.027171922060274e-49 / numbers[j+2] = -2.3848068803464593e+77 / difference = 2.3848068803464593e+77
  numbers[j+1] = -2.3848068803464593e+77 / numbers[j+2] = 1.3934696474671249e-71 / difference = -2.3848068803464593e+77
  numbers[j+1] = 1.3934696474671249e-71 / numbers[j+2] = -2.0626725572173683e-71 / difference = 3.456142204684493e-71
  numbers[j+1] = -2.0626725572173683e-71 / numbers[j+2] = 6.060823908025844e+38 / difference = -6.060823908025844e+38
  numbers[j+1] = 6.060823908025844e+38 / numbers[j+2] = -8.865642506725394e-13 / difference = 6.060823908025844e+38
  numbers[j+1] = -8.865642506725394e-13 / numbers[j+2] = -1.780876441526915e-14 / difference = -8.687554862572702e-13
  numbers[j+1] = -1.780876441526915e-14 / numbers[j+2] = 25.0 / difference = -44.00000000000144
  numbers[j+1] = 44 / numbers[j+2] = -37 / difference = 81
Final list [-0.0, -0.0, Infinity, 0.0, 0.0, -Infinity, -2.8530960909304215E-69, -5.679991152181034E-82, 25.0, -37.0]
[-35.0, 9.0, -46.0, 39.0, -39.0, 6.0, -47.0, -26.0, 25.0, -20.0]
  numbers[j+1] = 9.0/ numbers[j+2] = -46.0/ division = -0.1956521739130435
  numbers[j+1] = -46.0/ numbers[j+2] = 39.0/ division = -1.1794871794871795
  numbers[j+1] = 39.0/ numbers[j+2] = -39.0/ division = -1.0
  numbers[j+1] = -39.0/ numbers[j+2] = 6.0/ division = -6.5
  numbers[j+1] = 6.0/ numbers[j+2] = -47.0/ division = -0.1276595744680851
  numbers[j+1] = -47.0/ numbers[j+2] = -26.0/ division = 1.8076923076923077
  numbers[j+1] = -26.0/ numbers[j+2] = 25.0/ division = -1.04
  numbers[j+1] = 25.0/ numbers[j+2] = -20.0/ division = -1.25
[-0.6363636363636364, -0.10588235294117647, -0.5897435897435898, -0.8666666666666667, -0.7358490566037735, -0.2857142857142857, 0.9215686274509803, -0.5777777777777777, 25.0, -20.0]
  numbers[j+1] = -0.10588235294117647/ numbers[j+2] = -0.5897435897435898/ division = 0.179539641943734
  numbers[j+1] = -0.5897435897435898/ numbers[j+2] = -0.8666666666666667/ division = 0.6804733727810651
  numbers[j+1] = -0.8666666666666667/ numbers[j+2] = -0.7358490566037735/ division = 1.1777777777777778
  numbers[j+1] = -0.7358490566037735/ numbers[j+2] = -0.2857142857142857/ division = 2.5754716981132075
  numbers[j+1] = -0.2857142857142857/ numbers[j+2] = 0.9215686274509803/ division = -0.3100303951367781
  numbers[j+1] = 0.9215686274509803/ numbers[j+2] = -0.5777777777777777/ division = -1.5950226244343892
  numbers[j+1] = -0.5777777777777777/ numbers[j+2] = 25.0/ division = -0.02311111111111111
  numbers[j+1] = 25.0/ numbers[j+2] = -20.0/ division = -1.25
[-1.315177964180458, -0.38235294117647056, 4.508136094674554, 1.9253493013972058, 0.6095083833121744, -0.19055922281728732, -0.036030050595390196, -0.012839506172839505, 25.0, -20.0]
  numbers[j+1] = -0.38235294117647056/ numbers[j+2] = 4.508136094674554/ division = -0.08481397481059696
  numbers[j+1] = 4.508136094674554/ numbers[j+2] = 1.9253493013972058/ division = 2.341464009363416
  numbers[j+1] = 1.9253493013972058/ numbers[j+2] = 0.6095083833121744/ division = 3.1588561439213083
  numbers[j+1] = 0.6095083833121744/ numbers[j+2] = -0.19055922281728732/ division = -3.1985247121656526
  numbers[j+1] = -0.19055922281728732/ numbers[j+2] = -0.036030050595390196/ division = 5.288896897682073
  numbers[j+1] = -0.036030050595390196/ numbers[j+2] = -0.012839506172839505/ division = 2.8061866329101983
  numbers[j+1] = -0.012839506172839505/ numbers[j+2] = 25.0/ division = -5.135802469135802E-4
  numbers[j+1] = 25.0/ numbers[j+2] = -20.0/ division = -1.25
[0.26892565437509375, -0.1480389098208511, 3.4260494811449784, 2.4064832604729385, -3.9442933301742342, 8.217108634672064, 0.0014404622308674094, -2.853223593964335E-4, 25.0, -20.0]
  numbers[j+1] = -0.1480389098208511/ numbers[j+2] = 3.4260494811449784/ division = -0.04320979910989984
  numbers[j+1] = 3.4260494811449784/ numbers[j+2] = 2.4064832604729385/ division = 1.4236747611831166
  numbers[j+1] = 2.4064832604729385/ numbers[j+2] = -3.9442933301742342/ division = -0.6101177217381637
  numbers[j+1] = -3.9442933301742342/ numbers[j+2] = 8.217108634672064/ division = -0.48000988006064577
  numbers[j+1] = 8.217108634672064/ numbers[j+2] = 0.0014404622308674094/ division = 5704.494334241538
  numbers[j+1] = 0.0014404622308674094/ numbers[j+2] = -2.853223593964335E-4/ division = -5.0485431072227955
  numbers[j+1] = -2.853223593964335E-4/ numbers[j+2] = 25.0/ division = -1.1412894375857339E-5
  numbers[j+1] = 25.0/ numbers[j+2] = -20.0/ division = -1.25
Final list [-0.0, -0.0, Infinity, 0.0, 0.0, -Infinity, -2.8530960909304215E-69, -5.679991152181034E-82, 25.0, -20.0]
Remarques

Cette sortie nous montre clairement deux choses :

  • L’erreur vient d’une soustraction -0.0 - (-0.0) = 0.0, qui met le dénominateur de la division à 0.
  • L’apparition de ces 0 est causée par une très rapide diminution de toutes les valeurs dans la liste (sauf les deux dernières).

Cette sortie nous montre deux choses :

  • L’erreur vient d’une division 3.5381129532088862E277 / 2.392123271624348E-165 = Infinity, qui met le dénominateur de la division à Infinity, ce qui introduit à son tour des 0.
  • L’apparition de ces valeurs est causée par une très rapide diminution de toutes les valeurs dans la liste (sauf les deux dernières).

Nous avons trouvé la source de notre problème ! La correction dépend évidemment de ce que l’algorithme était censé faire, car c’est un exemple didactique.

Notez toutefois que l’erreur n’est pas causée par la présence de deux nombres aléatoires consécutifs dans la liste initiale, ce qui aurait pu être la solution la plus simple à laquelle vous auriez pensé ! Comme les erreurs ne sont pas toujours évidentes, exécutez toujours fréquemment vos programmes et utilisez des outils de débogage !

Maintenant, utilisez le débogueur pas à pas de VSCode pour déboguer le même programme. Comment faire ?

Correction

Comme l’erreur se produit à la ligne 14, mettons un point d’arrêt à cette ligne. Puis, en exécutant le débogueur pas à pas, observons le contenu des variables à chaque fois que ce point d’arrêt est atteint :

i
j
numbers
0 0 [44, -38, 27, -10, -17, -28, -17, 19, -19, 45]
0 1 [-0.676923076923077, -38, 27, -10, -17, -28, -17, 19, -19, 45]
0 2 [-0.676923076923077, -1.027027027027027, 27, -10, -17, -28, -17, 19, -19, 45]
… … …
14 2 [-0.0, -0.0, -inf, -0.0, 0.0, -3.238439139240665e+104,
-1.080447209418469e-17, 9.822769774067204e-25, -19, 45]

3 — Programmation pas à pas

Vous allez implémenter une stratégie de Monte Carlo pour estimer la valeur de $\pi$. Le principe illustré dans la figure ci-dessous est de générer pseudo-aléatoirement les coordonnées cartésiennes de points situés dans le sous-espace unité, le carré cyan foncé. Considérant $n$ points pseudo-aléatoires générés, le rapport entre le nombre de points situés dans le quart supérieur droit du disque et le nombre total de points générés est une estimation de $\frac{\pi}{4}$.

Pour déterminer si un point est dans le quart supérieur droit du disque, il suffit de calculer sa distance euclidienne à l’origine. Si cette distance est inférieure à 1, il est dans le disque. Pour rappel, pour un point dont les coordonnées sont $(x,y)$, la distance à l’origine se calcule comme suit : $\sqrt{x^2 + y^2}$.

3.1 — Récupérez vos outils

Pour estimer $\pi$, vous avez besoin de quelques outils de programmation :

  • Un générateur de nombres aléatoires, et une méthode de ce générateur pour obtenir un nombre dans l’intervalle $[0, 1]$. Trouvez la méthode correcte dans la documentation du module random.

  • Une méthode pour calculer la racine carrée d’une valeur. Trouvez la méthode correcte dans la documentation du module math.

Vous demanderez via une invite le nombre de points à générer (la valeur à affecter à $n$). Pour ce faire, utilisez la fonction intégrée input.

Suivons quelques étapes pour obtenir un programme fonctionnel.

3.2 — Découpez votre algorithme en morceaux

Un code source complet est toujours écrit pas à pas, et chaque étape testée. C’est clairement la meilleure et la seule façon d’atteindre efficacement l’objectif. Alors, selon vous, que devons-nous faire ?

--- secondary_color: lightgray --- # Quiz Mettez les étapes proposées dans l'ordre ! 1. Demander la valeur de $n$. 2. Définir une boucle qui fera $n$ tours. 3. Générer des points aléatoires dans le sous-espace unité. 4. Calculer la distance entre un point pseudo-aléatoire et l'origine. 5. Estimer la valeur de $\pi$.

Implémentez cet algorithme étape par étape, et utilisez l’instruction print pour vérifier que chaque étape semble correcte.

Correction

Écrivons le programme étape par étape. D’abord, demandons une valeur de $n$ et vérifions que l’entrée fonctionne comme prévu. Nous ajoutons aussi directement les imports et la graine aléatoire. Le print nous aide à vérifier que l’entrée fonctionne bien, et que notre conversion de type est correcte.

​
# Number of points to generate
n = int(input("Enter the number of points to generate: "))
print(n, type(n))
// Needed imports
import java.util.Scanner;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Create a scanner object for user input
        Scanner scanner = new Scanner(System.in);

        // Number of points to generate
        System.out.print("Enter the number of points to generate: ");
        int n = scanner.nextInt();

        // Print the value of n and its type
        System.out.println(n + " " + ((Object)n).getClass().getSimpleName());
    }

}

Maintenant, générons $n$ points. Ici, nous choisissons de fixer la graine aléatoire pour faciliter le débogage au cas où nous en aurions besoin.

​
# Needed imports
import random

# Set the seed
random.seed(42)

# Number of points to generate
n = int(input("Enter the number of points to generate: "))

# Generate the points
for i in range(n):
    x = random.random()
    y = random.random()
    print("(%f, %f)" % (x, y))
// Needed imports
import java.util.Scanner;
import java.util.Random;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Create a scanner object for user input
        Scanner scanner = new Scanner(System.in);

        // Set the seed
        Random random = new Random();
        random.setSeed(42);

        // Number of points to generate
        System.out.print("Enter the number of points to generate: ");
        int n = scanner.nextInt();

        // Generate the points
        for (int i = 0; i < n; i++) {
            double x = random.nextDouble();
            double y = random.nextDouble();
            System.out.printf("(%.6f, %.6f)\n", x, y);
        }
    }

}

Tout semble correct, continuons. Pour estimer $\pi$, déterminez le nombre de points qui tombent dans le cercle unité (calcul de la norme de l’origine au point).

​
# Needed imports
import random
from math import sqrt

# Set the seed
random.seed(42)

# Number of points to generate
n = int(input("Enter the number of points to generate: "))

# Number of points inside the circle (initially 0)
nb_pt_inside = 0
for i in range(n):

    # Generate the point
    x = random.random()
    y = random.random()
    
    # Check if the point is inside the circle
    if sqrt(x**2 + y**2) <= 1:
        nb_pt_inside += 1

# Estimate pi
estimate_pi = 4 * nb_pt_inside / n
print("Estimate of pi: ", estimate_pi)
// Needed imports
import java.util.Scanner;
import java.util.Random;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {
  
    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Create a scanner object for user input
        Scanner scanner = new Scanner(System.in);

        // Set the seed
        Random random = new Random();
        random.setSeed(42);

        // Number of points to generate
        System.out.print("Enter the number of points to generate: ");
        int n = scanner.nextInt();

        // Number of points inside the circle (initially 0)
        int nbPtInside = 0;
        for (int i = 0; i < n; i++) {

            // Generate the point
            double x = random.nextDouble();
            double y = random.nextDouble();

            // Check if the point is inside the circle
            if (Math.sqrt(x * x + y * y) <= 1) {
                nbPtInside++;
            }
        }

        // Estimate pi
        double estimatePi = 4.0 * nbPtInside / n;
        System.out.println("Estimate of pi: " + estimatePi);
    }

}

En faisant varier la valeur de $n$, observez la précision de l’estimation de $\pi$ obtenue.

Correction

Voici quelques résultats possibles que nous avons observés. Notez que, comme nous utilisons des nombres aléatoires, vous pouvez obtenir des résultats différents.

N
Estimation de pi
10 3.6
100 3.12
1 000 3.128
10 000 3.126
100 000 3.13728
1 000 000 3.140592
10 000 000 3.1423096
100 000 000 3.14147488

4 — Un problème classique de tri

Trier un tableau (ou une liste) de valeurs selon une relation d’ordre est un problème algorithmique très classique. Il est souvent utilisé pour découvrir empiriquement des concepts théoriques tels que la terminaison, la complexité, etc.

4.1 — Deux variantes de la stratégie de tri par sélection

L’algorithme de tri par sélection est très facile à comprendre (voici une explication avec musique et gestes). Considérez que vous avez un jeu de cartes non triées dans votre main droite et que vous construisez progressivement une permutation triée de ces cartes dans votre main gauche. La stratégie du tri par sélection consiste d’abord à sélectionner la carte ayant la plus petite valeur dans votre main droite et à la placer en première position dans votre main gauche. Vous faites ensuite de même avec la carte ayant la deuxième plus petite valeur, et ainsi de suite.

Identifiez les différentes étapes pour finalement avoir un programme qui génère un tableau de taille N (une constante choisie) composé de valeurs générées aléatoirement, puis trie ce tableau par sélection et vérifie que le tableau est bien trié. Puis écrivez un programme qui effectue ce tri.

Une fois le programme prêt, écrivez une étape supplémentaire pour vérifier que le tableau est bien trié. Testez sa correction en essayant différentes valeurs pour N (impaires et paires). De plus, assurez-vous que le programme gère plusieurs occurrences des mêmes valeurs dans le tableau.

Correction
​
# Needed imports
import random
import time

# Constants
N = 10

# Set the seed
random.seed(42)

# Generate a random list of N numbers
list_to_sort = [random.randint(0, 100) for i in range(N)]
print("Unsorted list:", list_to_sort)

# Get the current time
# We are going to measure execution time for info
# Here, we measure the process time rather than the elapsed time
start = time.process_time()

# Iterate over each cell of the list
for i in range(N-1):

    # Find the smallest value in the remaining part of the list (i.e., from i to N-1)
    # Below, we provide an implementation based on loops
    # It is equivalent to the following code:
    # index_min = numpy.argmin(list_to_sort[:i])
    index_min = i
    for j in range(i+1, N):
        if list_to_sort[j] < list_to_sort[index_min]:
            index_min = j

    # Exchange value at position i with the smallest value found
    list_to_sort[i], list_to_sort[index_min] = list_to_sort[index_min], list_to_sort[i]

# Get the current time after sorting
# The difference will give us the execution time
stop = time.process_time()
print("Sorted list in %f seconds" % (stop - start))

# Check that the list is indeed sorted
i = 1
while i < N and list_to_sort[i] >= list_to_sort[i-1]:
    i += 1
print("Is the list sorted?", i == N)
print("Sorted list:", list_to_sort)
// Needed imports
import java.util.Random;
import java.util.Arrays;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    // Constants
    public static final int N = 10;

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Create a random object
        Random random = new Random();
        random.setSeed(42);

        // Generate a random list of N numbers
        int[] listToSort = new int[N];
        for (int i = 0; i < N; i++) {
            listToSort[i] = random.nextInt(101);
        }
        System.out.println("Unsorted list: " + Arrays.toString(listToSort));

        // Get the current process time (in nanoseconds)
        long start = System.nanoTime();

        // Selection sort implementation
        for (int i = 0; i < N - 1; i++) {
            // Find the smallest value in the remaining part of the list (i.e., from i to N-1)
            int indexMin = i;
            for (int j = i + 1; j < N; j++) {
                if (listToSort[j] < listToSort[indexMin]) {
                    indexMin = j;
                }
            }

            // Swap value at position i with the smallest value found
            int temp = listToSort[i];
            listToSort[i] = listToSort[indexMin];
            listToSort[indexMin] = temp;
        }

        // Get the current time after sorting (in nanoseconds)
        long stop = System.nanoTime();
        System.out.printf("Sorted list in %.6f seconds%n", (stop - start) / 1e9);

        // Check if the list is sorted
        boolean isSorted = true;
        for (int i = 1; i < N; i++) {
            if (listToSort[i] < listToSort[i - 1]) {
                isSorted = false;
                break;
            }
        }
        System.out.println("Is the list sorted? " + isSorted);
        System.out.println("Sorted list: " + Arrays.toString(listToSort));
    }

}

Une légère variation de l’algorithme consiste à positionner la plus petite et la plus grande valeur en même temps, la deuxième plus petite et la deuxième plus grande, etc. Implémentez cette stratégie dans un nouveau script.

Correction
​
# Needed imports
import random
import time

# Constants
N = 10

# Set the seed
random.seed(42)

# Generate a random list of N numbers
list_to_sort = [random.randint(0, 100) for i in range(N)]
print("Unsorted list:", list_to_sort)

# Get the current time
# We are going to measure execution time for info
# Here, we measure the process time rather than the elapsed time
start = time.process_time()

# Iterate over each cell of the list
for i in range((N-1) // 2 + 1):
    
    # Find the smallest and the highest value in the remaining part of the list (i.e., from i to N-1)
    # Below, we provide an implementation based on loops
    # It is equivalent to the following code:
    # index_min = numpy.argmin(list_to_sort[:i])
    # index_max = numpy.argmax(list_to_sort[:i])
    index_min = i
    index_max = i
    for j in range(i+1, N-i):
        if list_to_sort[j] < list_to_sort[index_min]:
            index_min = j
        if list_to_sort[j] > list_to_sort[index_max]:
            index_max = j

    # Exchange value at position i with the smallest value found
    list_to_sort[i], list_to_sort[index_min] = list_to_sort[index_min], list_to_sort[i]

    # In case the highest value is located at position i and would be erased by the lowest value found
    if index_max == i:
        index_max = index_min

    # Exchange value at position N-i-1 with the highest value found
    list_to_sort[N-i-1], list_to_sort[index_max] = list_to_sort[index_max], list_to_sort[N-i-1]

# Get the current time after sorting
# The difference will give us the execution time
stop = time.process_time()
print("Sorted list in %f seconds" % (stop - start))

# Check that the list is indeed sorted
i = 1
while i < N and list_to_sort[i] >= list_to_sort[i-1]:
    i += 1
print("Is the list sorted?", i == N)
print("Sorted list:", list_to_sort)
// Needed imports
import java.util.Random;
import java.util.Arrays;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    // Constants
    public static final int N = 10;

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Create a random object
        Random random = new Random();
        random.setSeed(42);

        // Generate a random list of N numbers
        int[] listToSort = new int[N];
        for (int i = 0; i < N; i++) {
            listToSort[i] = random.nextInt(101);
        }
        System.out.println("Unsorted list: " + Arrays.toString(listToSort));

        // Get the current process time (in nanoseconds)
        long start = System.nanoTime();

        // Iterate over each cell of the list
        for (int i = 0; i <= (N - 1) / 2; i++) {
            // Find the smallest and the largest value in the remaining part of the list (i.e., from i to N-1)
            int indexMin = i;
            int indexMax = i;
            for (int j = i + 1; j < N - i; j++) {
                if (listToSort[j] < listToSort[indexMin]) {
                    indexMin = j;
                }
                if (listToSort[j] > listToSort[indexMax]) {
                    indexMax = j;
                }
            }

            // Swap value at position i with the smallest value found
            int temp = listToSort[i];
            listToSort[i] = listToSort[indexMin];
            listToSort[indexMin] = temp;

            // If the highest value is located at position i and would be erased by the smallest value found
            if (indexMax == i) {
                indexMax = indexMin;
            }

            // Swap value at position N-i-1 with the largest value found
            temp = listToSort[N - i - 1];
            listToSort[N - i - 1] = listToSort[indexMax];
            listToSort[indexMax] = temp;
        }

        // Get the current time after sorting (in nanoseconds)
        long stop = System.nanoTime();
        System.out.printf("Sorted list in %.6f seconds%n", (stop - start) / 1e9);

        // Check if the list is sorted
        boolean isSorted = true;
        for (int i = 1; i < N; i++) {
            if (listToSort[i] < listToSort[i - 1]) {
                isSorted = false;
                break;
            }
        }
        System.out.println("Is the list sorted? " + isSorted);
        System.out.println("Sorted list: " + Arrays.toString(listToSort));
    }

}

4.2 — Comparaison empirique de leur efficacité

Pour chacune des stratégies de tri que vous avez développées dans la section précédente, assurez-vous de créer un script dédié. Dans la suite, nous supposons que le premier s’appelle selection_sort_min.py, et le second selection_sort_min_max.py.

Puis, adaptez les deux scripts comme suit :

  • Le seul print qu’ils doivent faire est le temps écoulé pour trier la liste, c’est-à-dire print(stop - start) dans les corrections ci-dessus (sans aucun autre texte). Supprimez tous les autres prints, ainsi que le test final pour vérifier si la liste est triée.

  • Adaptez votre script pour récupérer la valeur de N depuis le premier argument en ligne de commande, c’est-à-dire en utilisant sys.argv[1]. N’oubliez pas de la convertir en entier.

  • Adaptez votre script pour récupérer la valeur de la graine aléatoire depuis le second argument en ligne de commande, c’est-à-dire en utilisant sys.argv[2]. N’oubliez pas de la convertir en entier.

Correction
​
# Needed imports
import random
import time
import sys

# Constants
N = int(sys.argv[1])

# Set the seed
random.seed(int(sys.argv[2]))

# Generate a random list of N numbers
list_to_sort = [random.randint(0, 100) for i in range(N)]

# Get the current time
# We are going to measure execution time for info
# Here, we measure the process time rather than the elapsed time
start = time.process_time()

# Iterate over each cell of the list
for i in range(N-1):

    # Find the smallest value in the remaining part of the list (i.e., from i to N-1)
    # Below, we provide an implementation based on loops
    # It is equivalent to the following code:
    # index_min = numpy.argmin(list_to_sort[:i])
    index_min = i
    for j in range(i+1, N):
        if list_to_sort[j] < list_to_sort[index_min]:
            index_min = j

    # Exchange value at position i with the smallest value found
    list_to_sort[i], list_to_sort[index_min] = list_to_sort[index_min], list_to_sort[i]

# Get the current time after sorting
# The difference will give us the execution time
stop = time.process_time()
print(stop - start)
// Needed imports
import java.util.Random;

/**
 * To run this code, you need to have Java installed on your computer, then:
  * - Create a file named `Main.java` in a directory of your choice.
  * - Copy this code in the file.
  * - Open a terminal in the directory where the file is located.
  * - Run the command `javac Main.java` to compile the code.
  * - Run the command `java -ea Main` to execute the compiled code.
  * Note: '-ea' is an option to enable assertions in Java.
  */
public class Main {

    /**
     * This is the entry point of your program.
      * It contains the first codes that are going to be executed.
      *
      * @param args Command line arguments received.
      */
    public static void main(String[] args) {
        // Constants: Read N and seed from command line arguments
        int N = Integer.parseInt(args[0]);
        long seed = Long.parseLong(args[1]);

        // Create a random object and set the seed
        Random random = new Random(seed);

        // Generate a random list of N numbers
        int[] listToSort = new int[N];
        for (int i = 0; i < N; i++) {
            listToSort[i] = random.nextInt(101);  // Generate random integers between 0 and 100
        }

        // Get the current process time (in nanoseconds)
        long start = System.nanoTime();

        // Selection sort algorithm
        for (int i = 0; i < N - 1; i++) {
            // Find the smallest value in the remaining part of the list (i.e., from i to N-1)
            int indexMin = i;
            for (int j = i + 1; j < N; j++) {
                if (listToSort[j] < listToSort[indexMin]) {
                    indexMin = j;
                }
            }

            // Swap value at position i with the smallest value found
            int temp = listToSort[i];
            listToSort[i] = listToSort[indexMin];
            listToSort[indexMin] = temp;
        }

        // Get the current time after sorting (in nanoseconds)
        long stop = System.nanoTime();
        
        // Print the execution time in seconds
        System.out.println((stop - start) / 1e9);
    }

}
​
# Needed imports
import random
import time
import sys

# Constants
N = int(sys.argv[1])

# Set the seed
random.seed(int(sys.argv[2]))

# Generate a random list of N numbers
list_to_sort = [random.randint(0, 100) for i in range(N)]

# Get the current time
# We are going to measure execution time for info
# Here, we measure the process time rather than the elapsed time
start = time.process_time()

# Iterate over each cell of the list
for i in range((N-1) // 2 + 1):
    
    # Find the smallest and the highest value in the remaining part of the list (i.e., from i to N-1)
    # Below, we provide an implementation based on loops
    # It is equivalent to the following code:
    # index_min = numpy.argmin(list_to_sort[:i])
    # index_max = numpy.argmax(list_to_sort[:i])
    index_min = i
    index_max = i
    for j in range(i+1, N-i):
        if list_to_sort[j] < list_to_sort[index_min]:
            index_min = j
        if list_to_sort[j] > list_to_sort[index_max]:
            index_max = j

    # Exchange value at position i with the smallest value found
    list_to_sort[i], list_to_sort[index_min] = list_to_sort[index_min], list_to_sort[i]

    # In case the highest value is located at position i and would be erased by the lowest value found
    if index_max == i:
        index_max = index_min

    # Exchange value at position N-i-1 with the highest value found
    list_to_sort[N-i-1], list_to_sort[index_max] = list_to_sort[index_max], list_to_sort[N-i-1]

# Get the current time after sorting
# The difference will give us the execution time
stop = time.process_time()
print(stop - start)
// Needed imports
import java.util.Random;

/**
 * To run this code, you need to have Java installed on your computer, then:
  * - Create a file named `Main.java` in a directory of your choice.
  * - Copy this code in the file.
  * - Open a terminal in the directory where the file is located.
  * - Run the command `javac Main.java` to compile the code.
  * - Run the command `java -ea Main` to execute the compiled code.
  * Note: '-ea' is an option to enable assertions in Java.
  */
public class Main {

    /**
     * This is the entry point of your program.
      * It contains the first codes that are going to be executed.
      *
      * @param args Command line arguments received.
      */
    public static void main(String[] args) {
        // Constants: Read N and seed from command line arguments
        int N = Integer.parseInt(args[0]);
        long seed = Long.parseLong(args[1]);

        // Create a random object and set the seed
        Random random = new Random(seed);

        // Generate a random list of N numbers
        int[] listToSort = new int[N];
        for (int i = 0; i < N; i++) {
            listToSort[i] = random.nextInt(101);  // Generate random integers between 0 and 100
        }

        // Get the current process time (in nanoseconds)
        long start = System.nanoTime();

        // Iterate over each cell of the list
        for (int i = 0; i <= (N - 1) / 2; i++) {
            // Find the smallest and the largest value in the remaining part of the list (i.e., from i to N-1)
            int indexMin = i;
            int indexMax = i;
            for (int j = i + 1; j < N - i; j++) {
                if (listToSort[j] < listToSort[indexMin]) {
                    indexMin = j;
                }
                if (listToSort[j] > listToSort[indexMax]) {
                    indexMax = j;
                }
            }

            // Swap value at position i with the smallest value found
            int temp = listToSort[i];
            listToSort[i] = listToSort[indexMin];
            listToSort[indexMin] = temp;

            // If the highest value is located at position i and would be erased by the smallest value found
            if (indexMax == i) {
                indexMax = indexMin;
            }

            // Swap value at position N-i-1 with the largest value found
            temp = listToSort[N - i - 1];
            listToSort[N - i - 1] = listToSort[indexMax];
            listToSort[indexMax] = temp;
        }

        // Get the current time after sorting (in nanoseconds)
        long stop = System.nanoTime();

        // Print the execution time in seconds
        System.out.println((stop - start) / 1e9);
    }

}

Maintenant, créez un nouveau script Python qui utilise la fonction intégrée sorted de Python. Ci-dessous, nous supposons que ce script s’appelle built_in_sorted.py. Il doit respecter les mêmes adaptations que les deux autres scripts ci-dessus, c’est-à-dire,

  • Être exécutable depuis la ligne de commande avec la commande suivante :

    ​
    python <script_name> <N> <seed>
    python <script_name> <N> <seed>
    python3 <script_name> <N> <seed>
    python3 <script_name> <N> <seed>

  • Afficher le temps total écoulé en résultat.

Correction
​
# Needed imports
import random
import time
import sys

# Constants
N = int(sys.argv[1])

# Set the seed
random.seed(int(sys.argv[2]))

# Generate a random list of N numbers
list_to_sort = [random.randint(0, 100) for i in range(N)]

# Get the current time
# We are going to measure execution time for info
# Here, we measure the process time rather than the elapsed time
start = time.process_time()

# Sort the list
list_to_sort = sorted(list_to_sort)

# Get the current time after sorting
# The difference will give us the execution time
stop = time.process_time()
print(stop - start)
// Needed imports
import java.util.Random;
import java.util.Arrays;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Constants: Read N and seed from command line arguments
        int N = Integer.parseInt(args[0]);
        long seed = Long.parseLong(args[1]);

        // Create a random object and set the seed
        Random random = new Random(seed);

        // Generate a random list of N numbers
        int[] listToSort = new int[N];
        for (int i = 0; i < N; i++) {
            listToSort[i] = random.nextInt(101);  // Generate random integers between 0 and 100
        }

        // Get the current process time (in nanoseconds)
        long start = System.nanoTime();

        // Sort the list using Java's built-in sorting method
        Arrays.sort(listToSort);

        // Get the current time after sorting
        long stop = System.nanoTime();

        // Print the execution time in seconds
        System.out.println((stop - start) / 1e9);
    }

}

Cette fonction utilise un algorithme plus avancé appelé Powersort. De plus, lors de l’appel à sorted, l’interpréteur appelle une version compilée de la fonction de tri en arrière-plan. Elle peut donc être directement interprétée en code binaire par votre ordinateur, et est donc beaucoup plus rapide.

Important

La plupart des fonctions intégrées de Python (et celles des bibliothèques) utilisent la même astuce, il est donc toujours préférable de les utiliser plutôt que de réinventer la roue. Moins vous écrivez de boucles, plus votre code Python sera rapide !

Maintenant, placez le script suivant dans le même répertoire que les fichiers que vous venez de créer. N’oubliez pas d’adapter les noms de fichiers. Ce script exécutera tous les autres scripts pour différentes tailles d’entrée, et créera un fichier .csv avec les temps moyens. Il utilisera également la graine aléatoire pour s’assurer que tous les scripts sont comparés dans les mêmes conditions.

​
# Needed imports
import subprocess
import os

# Constants
SCRIPTS = ['selection_sort_min.py', 'selection_sort_min_max.py', 'built_in_sorted.py']
NB_TESTS_FOR_AVERAGE = 10
VALUES_OF_N = [10, 100, 1000, 10000]
OUTPUT_FILE_NAME = 'average_execution_times.csv'
PYTHON_EXECUTABLE = "python"

# We will write the average execution time for each script in a file
current_dir = os.path.dirname(__file__)
output_file = open(os.path.join(current_dir, OUTPUT_FILE_NAME), 'w', buffering=1)

# Loop over each script
for script in SCRIPTS:

    # Loop over each value of N
    results_for_n = []
    for n in VALUES_OF_N:

        # Loop over each test
        execution_times = []
        for seed in range(NB_TESTS_FOR_AVERAGE):

            # Run the script
            command = [PYTHON_EXECUTABLE, os.path.join(current_dir, script), str(n), str(seed)]
            output = subprocess.run(command, capture_output=True, text=True)
            result = float(output.stdout)
            execution_times.append(result)

        # Compute the average execution time
        average_execution_time = sum(execution_times) / NB_TESTS_FOR_AVERAGE
        results_for_n.append(average_execution_time)

    # Write the results for the current script
    output_file.write(script + ';')
    output_file.write(';'.join([str(result) for result in results_for_n]))
    output_file.write('\n')

# Close the file
output_file.close()

Puis, utilisez soit LibreOffice, Microsoft Office, ou tout logiciel équivalent, pour tracer, pour chaque script, le temps moyen en fonction de la taille de la liste. Alternativement, vous pouvez aussi installer le paquet Python matplotlib pour créer cette courbe. Voici un script pour le faire.

​
# Needed imports
import os
import matplotlib.pyplot as plt

# Constants
VALUES_OF_N = [10, 100, 1000, 10000]
CSV_FILE_NAME = 'average_execution_times.csv'

# Read the results from the file
current_dir = os.path.dirname(__file__)
results = {}
with open(os.path.join(current_dir, CSV_FILE_NAME), 'r') as file:
    for line in file:
        split_line = line.strip().split(';')
        script = split_line[0]
        times = [float(time) for time in split_line[1:]]
        results[script] = times

# Plot the results
fig, ax = plt.subplots()
for script, times in results.items():
    ax.plot(VALUES_OF_N, times, label=script)
ax.set_xscale("log")
ax.set_yscale("log")
ax.set_xlabel("N")
ax.set_ylabel("Average execution time (s)")
ax.set_title("Comparison of sorting algorithms")
ax.legend()
plt.show()
Correction

5 — Optimisez vos solutions

Ce que vous pouvez faire maintenant est d’utiliser des outils d’IA tels que GitHub Copilot ou ChatGPT, soit pour générer la solution, soit pour améliorer la première solution que vous avez proposée ! Essayez de faire cela pour tous les exercices ci-dessus, pour voir les différences avec vos solutions.

Pour aller plus loin

6 — Un problème classique de tri (encore)

Concevez un algorithme basé sur des comparaisons de tri qui satisfait l’invariant suivant :

Après i itérations de la boucle interne, les i plus grandes valeurs de la liste l de taille N sont triées dans un ordre croissant dans la partie droite de l.

À chaque itération, la première valeur du tableau (indice 0) est déplacée par échange avec ses voisins vers la droite jusqu’à ce qu’une valeur plus grande soit trouvée. Dans ce cas, c’est cette valeur la plus grande qui est déplacée vers la partie droite du tableau. Une boucle interne est utilisée pour appliquer ce processus jusqu’à ce qu’aucun échange ne puisse plus être effectué.

Écrivez votre script dans un nouveau fichier appelé bubble_sort.py. Assurez-vous que votre algorithme fonctionne correctement, comme vous l’avez fait dans un exercice précédent.

Correction

La correction, avec musique et images !

​
# Needed imports
import random
import time

# Constants
N = 10

# Set the seed
random.seed(42)

# Generate a random list of N numbers
list_to_sort = [random.randint(0, 100) for i in range(N)]
print("Unsorted list:", list_to_sort)

# Get the current time
# We are going to measure execution time for info
# Here, we measure the process time rather than the elapsed time
start = time.process_time()

# Loop through the list to sort it
for i in range(len(list_to_sort)):

    # Loop through the list to compare elements
    for j in range(len(list_to_sort) - 1):

        # Swap elements if they are not in the right order
        if list_to_sort[j] > list_to_sort[j + 1]:
            list_to_sort[j], list_to_sort[j + 1] = list_to_sort[j + 1], list_to_sort[j]

# Get the current time after sorting
# The difference will give us the execution time
stop = time.process_time()
print("Sorted list in %f seconds" % (stop - start))

# Check that the list is indeed sorted
i = 1
while i < N and list_to_sort[i] >= list_to_sort[i-1]:
    i += 1
print("Is the list sorted?", i == N)
print("Sorted list:", list_to_sort)  
// Needed imports
import java.util.Random;
import java.util.Arrays;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    // Constants
    public static final int N = 10;

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Set the seed
        Random random = new Random(42);

        // Generate a random list of N numbers
        int[] listToSort = new int[N];
        for (int i = 0; i < N; i++) {
            listToSort[i] = random.nextInt(101);  // Generate random integers between 0 and 100
        }
        System.out.println("Unsorted list: " + Arrays.toString(listToSort));

        // Get the current process time (in nanoseconds)
        long start = System.nanoTime();

        // Bubble sort implementation
        for (int i = 0; i < listToSort.length; i++) {
            for (int j = 0; j < listToSort.length - 1; j++) {
                if (listToSort[j] > listToSort[j + 1]) {
                    // Swap elements
                    int temp = listToSort[j];
                    listToSort[j] = listToSort[j + 1];
                    listToSort[j + 1] = temp;
                }
            }
        }

        // Get the current time after sorting (in nanoseconds)
        long stop = System.nanoTime();

        // Print the execution time in seconds
        System.out.printf("Sorted list in %.6f seconds%n", (stop - start) / 1e9);

        // Check if the list is sorted
        boolean isSorted = true;
        for (int i = 1; i < N; i++) {
            if (listToSort[i] < listToSort[i - 1]) {
                isSorted = false;
                break;
            }
        }
        System.out.println("Is the list sorted? " + isSorted);
        System.out.println("Sorted list: " + Arrays.toString(listToSort));
    }
    
}

Une légère amélioration peut certainement être appliquée à votre algorithme pour réduire le nombre d’échanges. Essayez de trouver ce qui peut être amélioré et comparez les deux versions selon le temps qu’elles mettent à trier le même tableau. Écrivez votre solution dans un nouveau fichier appelé bubble_sort_2.py.

Correction

Voici un code possible qui implémente deux optimisations :

  • Introduire un drapeau pour détecter si la liste est déjà triée – Cela permet à l’algorithme de s’arrêter tôt si aucun échange n’est effectué pendant un passage, ce qui signifie que la liste est déjà triée.

  • Réduire la plage de la boucle interne – À chaque passage, le plus grand élément est placé à la bonne position, donc la plage de la boucle interne peut être réduite à chaque itération.

​
# Needed imports
import random
import time

# Constants
N = 10

# Set the seed
random.seed(42)

# Generate a random list of N numbers
list_to_sort = [random.randint(0, 100) for i in range(N)]
print("Unsorted list:", list_to_sort)

# Get the current time
# We are going to measure execution time for info
# Here, we measure the process time rather than the elapsed time
start = time.process_time()

# Loop through the list to sort it
i = 0
swapped = True
while i < len(list_to_sort) and swapped:
    
    # Initialize flag to detect if any swap was made during this pass
    swapped = False  

    # Loop through the list to compare elements
    for j in range(0, N - i - 1):

        # Swap elements if they are not in the right order
        if list_to_sort[j] > list_to_sort[j + 1]:
            list_to_sort[j], list_to_sort[j + 1] = list_to_sort[j + 1], list_to_sort[j]
            swapped = True

    # Next index
    i += 1

# Get the current time after sorting
# The difference will give us the execution time
stop = time.process_time()
print("Sorted list in %f seconds" % (stop - start))

# Check that the list is indeed sorted
i = 1
while i < N and list_to_sort[i] >= list_to_sort[i-1]:
    i += 1
print("Is the list sorted?", i == N)
print("Sorted list:", list_to_sort)
// Needed imports
import java.util.Random;
import java.util.Arrays;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    // Constants
    public static final int N = 10;

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Set the seed
        Random random = new Random(42);

        // Generate a random list of N numbers
        int[] listToSort = new int[N];
        for (int i = 0; i < N; i++) {
            listToSort[i] = random.nextInt(101);  // Generate random integers between 0 and 100
        }
        System.out.println("Unsorted list: " + Arrays.toString(listToSort));

        // Get the current process time (in nanoseconds)
        long start = System.nanoTime();

        // Bubble sort implementation with early exit when no swaps occur
        int i = 0;
        boolean swapped = true;

        while (i < listToSort.length && swapped) {
            swapped = false;  // Reset the flag

            // Loop through the list to compare elements
            for (int j = 0; j < N - i - 1; j++) {
                if (listToSort[j] > listToSort[j + 1]) {
                    // Swap elements if they are not in the right order
                    int temp = listToSort[j];
                    listToSort[j] = listToSort[j + 1];
                    listToSort[j + 1] = temp;
                    swapped = true;  // Set the flag if a swap is made
                }
            }

            // Next index
            i++;
        }

        // Get the current time after sorting (in nanoseconds)
        long stop = System.nanoTime();

        // Print the execution time in seconds
        System.out.printf("Sorted list in %.6f seconds%n", (stop - start) / 1e9);

        // Check if the list is sorted
        boolean isSorted = true;
        for (int k = 1; k < N; k++) {
            if (listToSort[k] < listToSort[k - 1]) {
                isSorted = false;
                break;
            }
        }
        System.out.println("Is the list sorted? " + isSorted);
        System.out.println("Sorted list: " + Arrays.toString(listToSort));
    }

}

Comment pouvez-vous visualiser l’invariant ci-dessus en utilisant un débogueur pas à pas ?

Correction

Ajoutez un point d’arrêt à la fin de la boucle. Cela vous permettra de visualiser la liste triée à chaque itération, et de vérifier que l’invariant est respecté.

Voici un exemple de visualisation :

Itération (i + 1)
list_to_sort
1 [14, 3, 81, 35, 31, 28, 17, 94, 13, 94]
2 [3, 14, 35, 31, 28, 17, 81, 13, 94, 94]
3 [3, 14, 31, 28, 17, 35, 13, 81, 94, 94]
4 [3, 14, 28, 17, 31, 13, 35, 81, 94, 94]
5 [3, 14, 17, 28, 13, 31, 35, 81, 94, 94]
6 [3, 14, 17, 13, 28, 31, 35, 81, 94, 94]
7 [3, 14, 13,17, 28, 31, 35, 81, 94, 94]
8 [3, 13, 14, 17, 28, 31, 35, 81, 94, 94]
9 [3, 3, 14, 17, 28, 31, 35, 81, 94, 94]

Notez que la dernière itération n’est pas effectuée car la liste est déjà triée, ce qui rend l’invariant vrai pour le dernier indice également.

Pour aller plus loin

7 — Comprendre le script qui exécute les tris

Dans l’exercice 4, nous vous avons fourni un script pour comparer les temps d’exécution des algorithmes de tri. Comprenez ce script, et adaptez vos algorithmes de tri à bulles ci-dessus pour les intégrer dans le script. Puis comparez leurs temps d’exécution avec les autres algorithmes de tri que vous avez vus précédemment.

8 — Comparer les algorithmes de tri

Il existe beaucoup d’autres algorithmes de tri. Vous pouvez par exemple consulter ce lien. Essayez d’en coder quelques-uns et comparez leurs performances sur différentes tailles de listes.