Algorithmic statements

En bref

Résumé de l’article

Dans cet article, nous vous présentons les principaux constituants d’un algorithme : les instructions, les boucles et les instructions conditionnelles. Nous mentionnons également les risques liés aux boucles, et vous présentons brièvement une approche formelle pour s’assurer qu’il n’y a pas de boucles infinies.

Points clés

• Une instruction est un constituant atomique d’un algorithme.

• Les instructions peuvent être regroupées en blocs d’instructions (ou d’autres blocs).

• Une boucle (for ou while) permet d’exécuter un bloc d’instructions plusieurs fois, jusqu’à ce qu’une condition soit remplie.

• Une instruction conditionnelle (if) permet d’exécuter ou non un bloc d’instructions, en fonction d’une condition.

Contenu de l’article

1 — Instructions simples

Une instruction est une instruction algorithmique atomique. Les instructions formant un algorithme sont exécutées séquentiellement. Pensez à une recette de cuisine. Une instruction pourrait être par exemple “ajouter du sucre” ou “mettre au four”. Ou, plus proche de ce dont nous avons besoin, a = 2 * b ou print(x).

Plusieurs instructions (et blocs) peuvent être regroupés pour former un bloc d’instructions. Les blocs peuvent alors être exécutés ou non en fonction d’un test, ou être exécutés plusieurs fois. Voici les principales structures algorithmiques :

2 — Conditions

Les instructions conditionnelles (if) sont utilisées pour diviser l’exécution séquentielle de l’algorithme en fonction d’une condition booléenne. Si cette condition est évaluée à true, alors un bloc d’instructions est exécuté. Sinon, un autre bloc est exécuté, dans la partie else du test.

# Set some variables
balance = 453.5
request = 60

# Beginning of the conditional statement
if balance - request >= 0:

    # This block of code is executed if the test is True
    print("Withdrawal request accepted")
    balance -= request

else:

    # This block of code is executed if the test is False
    print("Withdraw request rejected: balance too low")

/**
 * 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) {
        // Set some variables
        double balance = 453.5;
        double request = 60;

        // Beginning of the conditional statement
        if (balance - request >= 0) {
            // This block of code is executed if the test is True
            System.out.println("Withdrawal request accepted");
            balance = balance - request;
        } else {
            // This block of code is executed if the test is False
            System.out.println("Withdraw request rejected: balance too low");
        }
    }
}

# Set some variables
balance = 453.5
request = 60

# Beginning of the conditional statement
if balance - request >= 0:

    # Nested conditional statement
    if balance - request == 0:

        # This block of code is executed if the first test is True and the nested test is True
        print("Withdrawal request accepted")
        print("Bank account is now empty")
        balance -= request
    
    else:

        # This block of code is executed if the first test is True and the nested test is False
        print("Withdrawal request accepted")
        balance -= request

else:

    # This block of code is executed if the first test is False
    print("Withdraw request rejected: balance too low")

/**
 * 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) {
        // Set some variables
        double balance = 453.5;
        double request = 60;
        // Beginning of the conditional statement
        if (balance - request > 0) {
            // Nested conditional statement
            if (balance - request == 0) {
                // This block of code is executed if the first test is True and the nested test is True
                System.out.println("Withdrawal request accepted")
                System.out.println("Bank account is now empty")
                balance = balance - request;
            } else {
                // This block of code is executed if the first test is True and the nested test is False
                System.out.println("Withdrawal request accepted");
                balance = balance - request;
            }
        } else {
            // This block of code is executed if the first test is False
            System.out.println("Withdraw request rejected: balance too low");
        }
    }

}

# Set some variables
balance = 453.5
request = 60

# Beginning of the conditional statement
if balance - request > 0:

    # This block of code is executed if the test is True
    print("Withdrawal request accepted")
    balance -= request

elif balance - request == 0:

    # This block of code is executed if the first test is False and the second test is True
    print("Withdrawal request accepted")
    print("Bank account is now empty")
    balance -= request

else:

    # This block of code is executed if both tests are False
    print("Withdraw request rejected: balance too low")

/**
 * 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) {
        // Set some variables
        double balance = 453.5;
        double request = 60;
        // Beginning of the conditional statement
        if (balance - request > 0) {
            // This block of code is executed if the test is True
            System.out.println("Withdrawal request accepted");
            balance = balance - request;
        } else if (balance - request == 0) {
            // This block of code is executed if the first test is False and the second test is True
            System.out.println("Withdrawal request accepted")
            System.out.println("Bank account is now empty")
            balance = balance - request;
        } else {
            // This block of code is executed if both tests are False
            System.out.println("Withdraw request rejected: balance too low");
        }
    }

}

3 — Boucles

De nombreuses solutions aux problèmes algorithmiques reposent sur la répétition d’un bloc d’instructions jusqu’à ce qu’un état attendu soit atteint. L’itération sur un bloc d’instructions se fait à l’aide de boucles qui permettent de définir des cycles dans le flux d’exécution d’un algorithme. Il existe deux types de boucles :

• Boucles bornées
• Boucles non bornées.

Les boucles bornées (ou boucles for) sont utilisées lorsque le nombre d’itérations à effectuer est connu a priori. Elles effectuent un nombre fixe d’itérations.

# Initialize a few variables
v = 1
n = 10
print("v =", v)

# A loop that will iterate 10 times
for i in range(n):
    v /= 2
    print("v =", v)

/**
 * 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) {
        // Initialize a few variables
        double v = 1;
        int n = 10;
        System.out.println("v = " + v);

        // A loop that will iterate 10 times
        for (int i = 0; i < n; i++) {
            v = v / 2;
            System.out.println("v = " + v);
        }
    }

}

Les boucles non bornées (ou boucles while) itèrent jusqu’à ce qu’une condition soit atteinte. Comme vous le verrez ci-dessous, il y a donc un risque de boucle infinie si vous n’êtes pas prudent. Voici un code similaire à celui ci-dessus qui utilise une boucle non bornée pour vérifier la valeur de v afin de s’arrêter :

# Initialize a few variables
v = 1
print("v =", v)

# A loop that will iterate until v is low enough
while v > 0.000001:
    v /= 2
    print("v =", v)

/**
 * 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) {
        // Initialize a few variables
        double v = 1;
        System.out.println("v = " + v);

        // A loop that will iterate until v is low enough
        while (v > 0.000001) {
            v = v / 2;
            System.out.println("v = " + v);
        }
    }

}

Les boucles non bornées sont universelles, ce qui signifie que tout problème itératif peut être résolu en utilisant des boucles non bornées, alors que les boucles bornées nécessitent que le nombre de boucles à effectuer soit connu à l’avance.

Pour aller plus loin

4 — Correction des boucles

Les boucles constituent souvent des éléments centraux des algorithmes. Tester les boucles ne suffit pas à garantir qu’elles produiront toujours les résultats attendus. Des langages et méthodes formels, comme la logique de Hoare, ont été conçus pour prouver la terminaison correcte des algorithmes. Il est proposé ci-après de se concentrer sur la preuve de la correction des boucles en utilisant l’induction mathématique.

La notion d’invariant est utilisée pour prouver par induction qu’une boucle atteint effectivement un état attendu à partir d’un état initial. Cet état attendu est défini par les valeurs prises par les différentes variables impliquées dans l’algorithme. Les invariants sont utilisés pour prouver la correction d’une boucle.

Un invariant est une condition booléenne qui est vraie dans l’état initial, c’est-à-dire avant la première itération de la boucle, et qui reste vraie à la fin de chaque itération.

Les boucles impliquent également une variante qui décrit évidemment le constituant de l’algorithme qui évolue pendant l’itération. La variante est souvent définie au moyen d’un entier naturel matérialisant la progression de l’itération vers le résultat attendu. Les variantes sont utilisées pour prouver la terminaison d’une boucle.

# A few variables
s = ['B', 'o', 'n', 'j', 'o', 'u', 'r', ' ', 'c', 'h', 'e', 'r', '.', 'e', '.', 's', ' ', 'é', 't', 'u', 'd', 'i', 'a', 'n', 't', '.', 'e', '.', 's']
v = 'e'
i = 0
nb_occ = 0

# Loop over the list
while i < len(s):
    if s[i] == v:
        nb_occ += 1
    i += 1

# Done
print("The number of occurrences of", v, "=", nb_occ)

/**
 * 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) {
        // A few variables
        char s[] = {'B', 'o', 'n', 'j', 'o', 'u', 'r', ' ', 'c', 'h', 'e', 'r', '.', 'e', '.', 's', ' ', 'é', 't', 'u', 'd', 'i', 'a', 'n', 't', '.', 'e', '.', 's'};
        char v = 'e';
        int i = 0;
        int nb_occ = 0;

        // Loop over the list
        while (i < s.length) {
            if (s[i] == v) {
                nb_occ += 1;
            }
            i += 1;
        }

        // Done
        System.out.println("The number of occurrences of " + v + " = " + nb_occ);
    }

}

Pour aller plus loin

• Program correctness using induction.

  Quelques exemples supplémentaires sur la manière de prouver la correction d’un programme par induction.