What is an algorithm?

Reading time5 min

En bref

Résumé de l’article

Dans cet article, nous vous présentons ce que sont les algorithmes, et comment ils peuvent être écrits et comparés. De plus, nous vous présentons le concept de pseudo-code, et montrons un premier exemple d’algorithme.

Points clés

Un algorithme est une solution à un problème spécifique qui prend un ensemble de valeurs en entrée et produit une valeur en résultat. Cette solution est réalisée par une séquence d’instructions algorithmiques appliquées aux données d’entrée pour produire la valeur finale du résultat.
Les algorithmes peuvent être comparés selon de nombreux critères.
Les algorithmes peuvent être écrits en pseudo-code, ou directement dans un langage de programmation.

Contenu de l’article

1 — Qu’est-ce qu’un algorithme ?

Voici une définition possible d’un algorithme :

Un algorithme est une solution à un problème spécifique qui prend un ensemble de valeurs en entrée et produit une valeur en résultat. Cette solution est réalisée par une séquence d’instructions algorithmiques appliquées aux données d’entrée pour produire la valeur finale du résultat.

Évidemment, il peut y avoir des variations de cette définition, au fur et à mesure que les technologies évoluent (par exemple, l’algorithmique quantique), mais la définition ci-dessus couvre la plupart des cas.

Les algorithmes existent depuis des siècles, et étaient utilisés bien avant l’ordinateur moderne pour décrire comment les problèmes devaient être résolus. Par exemple, suivre une recette pour faire un gâteau est exactement la même chose que suivre un algorithme. En d’autres termes, cela vous donne des instructions spécifiques qui, si vous les appliquez dans l’ordre, produisent la solution désirée.

Nous appelons spécification d’un algorithme le type et le nombre de valeurs prises en entrée, ainsi que les propriétés attendues de la valeur de sortie.

Algorithm

2 — Comparer les algorithmes

Pour un problème donné, plusieurs solutions algorithmiques peuvent généralement être envisagées. Ces solutions candidates qui produisent la même sortie pour le même ensemble de valeurs d’entrée peuvent alors être comparées selon :

La complexité (de leur compréhension).
Le temps qu’elles prennent pour produire la valeur de sortie.
L’espace mémoire qu’elles requièrent pendant le traitement.
La dépendance potentielle à des algorithmes externes.
Leur utilisation ou non de l’aléatoire.
De nombreux autres critères (par exemple, besoin de dispositifs particuliers).

Un exemple classique de problème pouvant être résolu automatiquement par des algorithmes est de prendre un ensemble de valeurs en entrée et de les réordonner selon une relation d’ordre. C’est un problème habituel dans un cours d’algorithmique car cette tâche se produit fréquemment dans de nombreux contextes applicatifs et parce que plusieurs stratégies algorithmiques peuvent être utilisées pour obtenir un même ensemble ordonné de valeurs. Dans ce cours, vous allez implémenter et concevoir des algorithmes pour différents problèmes, caractérisés par leurs propriétés, la stratégie utilisée ou le type des données sur lesquelles ils sont appliqués.

3 — Langages et algorithmes

Les concepts algorithmiques sont souvent illustrés et manipulés à l’aide d’un pseudo-code, une syntaxe restreinte aux instructions algorithmiques avec une forme moins rigoureuse que les langages de programmation formels. Typiquement, un pseudo-code pourrait ressembler à ceci :

total <- 0
for each element l_i in list L do
    total <- total + l_i
done

total := 0
for l_i in L do
    total := total + l_i
done

total <- sum_of_all_elements(L)

# L is supposed to be a list of integers, declared elsewhere
total = sum(L)

/**
 * 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) {
        // L is supposed to be a list of integers, declared elsewhere
        int total = 0;
        for (int l_i : L) {
            total += l_i;
        }
    }
}

/**
 * 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.
 */

import java.util.Arrays;
import java.util.Arrays;

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) {
        // L is supposed to be a list of integers, declared elsewhere
        int total = Arrays.stream(L).sum();
    }
}

Comme vous pouvez le voir, le but principal d’un pseudo-code est d’écrire rapidement un algorithme sans se concentrer sur les détails des langages de programmation (types de variables, contraintes syntaxiques, etc.). Un pseudo-code peut aussi être une formulation mathématique. Par exemple, ce qui suit est équivalent à tous les codes ci-dessus :

$$total := \sum_{i = 1}^{|L|} L_i$$

Pour éviter d’avoir à apprendre différents formalismes, nous avons choisi d’utiliser le langage de programmation Python dans ce cours d’algorithmique. Sa syntaxe raffinée le rend facile à comprendre, même pour les débutants. De plus, nous vous fournirons également, autant que possible, la version Java des algorithmes, pour vous familiariser avec un second langage.

Exemple

Pour illustrer ce concept d’algorithme, prenons le problème de déterminer si une valeur donnée est présente dans un ensemble. Le problème est spécifié par :

Valeurs d’entrée – Un ensemble $S$ et une valeur $v$ à rechercher dans $S$.
Valeur de sortie – true si $v \in S$, false sinon.

# Input values
S = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
v = 7

# Perform the check
found = False
for s in S:
    found = s == v
    if found:
        break

# Display the result
print(v, 'in', S, ':', found)

/**
 * 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.
 */

import java.util.Arrays;

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) {
        // Input values
        int[] S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        char v = 7;

        // Perform the check
        boolean found = false;
        for (int s : S) {
            found = (s == v);
            if (found) {
                break;
            }
        }

        // Display the result
        System.out.println(v + " in " + Arrays.toString(S) + " = " + found);
    }
}

Information

Notez que les programmes ci-dessus sont excessivement complexes et détaillés à titre d’exemple. Vérifier si un élément appartient à une liste est une opération très standard. Voici comment nous le faisons :

# Input values
S = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
v = 7

# Perform the check
found = v in S

# Display the result
print(v, 'in', S, ':', found)

/**
 * 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.
 */

import java.util.Arrays;

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) {
        // Input values
        int[] S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        char v = 7;

        // Perform the check
        boolean found = Arrays.stream(S).anyMatch(s -> s == v);

        // Display the result
        System.out.println(v + " in " + Arrays.toString(S) + " = " + found);
    }
}

Pour de tels algorithmes simples, vous devriez toujours utiliser les fonctions standard du langage de programmation, c’est-à-dire, ne pas réinventer la roue ! Il y a deux raisons principales à cela :

Cela vous fera gagner du temps.
Il y a de fortes chances que des centaines de programmeurs aient travaillé sur l’implémentation standard pour la rendre aussi optimisée que possible (par exemple, en exploitant des algorithmes complexes, votre matériel disponible, ou du code compilé en arrière-plan), donc ce sera très certainement plus efficace que votre solution rapide.

Pour aller plus loin

Il semble que cette section soit vide !

Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pouvons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !

Pour aller au-delà

Il semble que cette section soit vide !