L’algorithmique

Qu’est-ce qu’un algorithme ?

Selon le dictionnaire Larousse, l’algorithmique est un :

Ensemble de règles opératoires dont l’application permet de résoudre un problème énoncé au moyen d’un nombre fini d’opérations. Un algorithme peut être traduit, grâce à un langage de programmation, en un programme exécutable par un ordinateur.

Les algorithmes dans la vie quotidienne

Les algorithmes sont omniprésent dans nos vies et nous les utilisons quotidiennement même sans faire usage d’un appareil numérique. Le simple fait, par exemple, de suivre une recette de cuisine est un algorithme puisqu’il s’agit d’une suite logique et finie d’opération menant à un résultat attendu (selon nos capacité culinaire bien sur 😉).

Autre exemple: rechercher un mot dans le dictionnaire. Ce problème demande une suite logique d’opération que l’on pourraient détailler comme suit :

1. Ouvrir à la première lettre du mot rechercher.
2. Lire le premier mot de la page.
3. Vérifier si le mot lu est avant notre mot selon l’ordre alphabétique.
4. Si celui-ci se situe avant le mot recherché, lire le mot suivant et recommencer l’étape 3.
5. sinon, le mot est trouvé et on arrète la recherche.

L’algorithme du dictionnaire met d’ailleurs en lumière des concepts algorithmiques qui sont la base de tous les langages informatique : les structures de contrôle et structures de données.

Structures de contrôle et structures de données

Les algorithmes permmettent donc la manipulation des données. Mais celle-ci n’est pas suffisante. Si la donnée n’est pas enregistrée quelque part, elle ne peut pas être exploitée. Il y a donc lieu de les stocker de façon temporaire (la mémoire vive) ou permanent (une base de donnée).

Pour reprendre l’exemple du dictionnaire, l’efficacité d’un algorithme de recherche de mot dépend de l’organisation du stockage. On imagine parfaitement la complexité d’un tel algorithme dans le cas ou les mots seraient placés de façon désordonnée: impossible de savoir ou l’on en est dans notre recherche.

Structures de données

Les structures de données permettent d’organiser les données en vue de les traiter plus aisément. Elles correspondent à un espace mémoire alloué par l’algorithme pour stocker les données manipulées par un algorithme.

Reprenons l’exemple du dictionnaire. Il repose sur la manipulation de deux structures de données :

• les variables
  1. le mot en cours de lecture.
  2. le mot que l’on recherche.
• les tableaux
  1. les mots et leur définitions.

Plus généralement, on distingue les structures suivantes :

Les constantes

une structure de données dont la valeur ne change pas au fil de l’algorithme.

Les variables

une structure de données qui peuvent évoluer au fil de l’algorithme.

Les tableaux

une structure de données représentant une séquence d’élément auquel on peut accéder par leur position/leur indice.

Structures de contrôle

Les structures de contrôle permettent de manipuler les données en vue de faire effectuer à l’algorithme une opération particulière.

Reprenons l’exemple du dictionnaire. Il repose sur deux structures de contrôle :

• Les conditions
  1. Vérifier si le mot lu est avant notre mot selon l’ordre alphabétique
  2. Si celui-ci se situe avant le mot recherché, lire le mot suivant
• les boucles
  1. Lire les mots jusqu’à ce que le mot lu corresponde au mot recherché

Plus généralement, on distingue les structures suivantes :

Les séquences

une structure de contrôle permettant d’effectuer une action.

Les conditions

une structure de contrôle permettant de vérifier la valeur d’une variable par rapport à un autre donnée.

une structure de contrôle permettant d’effectuer une action selon son résultat.

Les boucles

un structure de contrôle permettant d’effectuer un nombre de fois défini une action.

Pourquoi les algorithmes sont essentiel en informatique ?

Un ordinateur est un outil permettant l’exécution de taches répétitive et de calculs rapides.

L’algorithmique est une discipline importante en informatique car elle permet de décomposer un problème/un objectif/un résultat en un ensemble d’opérations/de tâches qui seront demandées à la machine via un langage de programmation.

En informatique, il est possible de déployer de nombreux algorithmes : recherche, analyse, comparaison d’éléments, classement d’informations, extraction de données, etc.

En somme, un algorithme permet la manipulation de données à des fins de traitements spécifique.

Structure et nomenclature des algorithmes

Un algorithme répond à une nomenclature permettant aux développaires de comprendre celui-ci indépendament du langage de programmation utilisé par la suite.

Structure générale d’un algorithme

Un algorithme se compose de plusieurs blocs :

1. L’entête, qui définie le type d’algorithme et son nom
2. La partie déclarative qui définie les structures de données constantes et variables
3. Le corps de l’algorithme qui indique les instructions de l’algorithme son début et sa fin.

        Algorithme nom_algorithme
        Constantes
            nom_constante = valeur
        Variables
            nom_variable : type
        Début
           instructions
           ...
        Fin
        

Cas particuliers : les sous-algorithmes. Fonctions et procédures

Les fonctions et procédures effectuent un certains nombres d’instructions, peuvant être utilisés autant de fois que necessaire, et dans autant d’algorithmes que necessaires.

Les avantages des sous-algorithmes sont :

• l’amélioration de la lisibilité de l’algorithme principal,
• la décomposition de problèmes complexes en sous-problèmes plus simple à résoudre,
• la facilitation de la correction des algorithmes en cas d’erreur.

Dans un algorithme, lorsque l’on utilise une fonctions ou une procédure, un nouveau bloc s’ajoute :

        Algorithme nom_algorithme
        Constantes
            nom_constante = valeur
        Variables
            nom_variable : type
        Fonctions
            liste des fonctions
        Procédures
            liste des procédures
        Début
           instructions
           ...
        Fin
        

Structure générale d’une fonction

Une fonction est un sous-algorithme qui permet d’exécuter des instructions en fonction d’un certain nombres de paramètre et re revoyer un résultat à l’algorithme qui y fait appel.

        Fonction nom_fonction (parametre_1 : type, parametre_2 : type, ...) : type_donnée_retournée
        Constantes
            nom_constante = valeur
        Variables
            nom_variable : type
        Début
           instructions
           ...
           Retourner valeur
        Fin
        

Appeler une fonction

Dans l’algorithme qui appelle la fonction, l’appel s’écrit :

1. nom de la variable,
2. flèche vers la gauche,
3. nom de la fonction
4. entre parenthèses, valeurs des paramètres

        ma_variable ← nom_fonction(valeur_parametre_1, valeur_parametre_2)
        

Les constantes

Les constantes sont des structures de données dont la valeur ne change pas au cours d’un algorithme.

La déclaration d’une variable s’écrit dans la partie déclarative comme suit :

1. nom de la constante
2. égal
3. valeur de la constante

Exemples de déclaration d’une constante :

        CONSTANTE 
            pi = 3,14159265...
        

Les variables

Les variables sont des structures de données permettant le stockage temporaire d’une indormation, d’un résultat, etc.

La déclaration d’une variable s’écrit dans la partie déclarative comme suit :

1. nom de la variable
2. deux points
3. type de la variable

Exemples de déclaration de variables :

        Variables 
            une_chaine : Chaine
            un_compteur : Entier
            un_reel : Réel
            un_booleen : Booleen
        

Au cours de l’algorithme, la valeur des variables peut-être modifiée à n’importe quel moment dans le corps de l’algorithme.

L’assignation s’écrit :

1. nom de la variable,
2. flèche vers la gauche,
3. valeur assignée

Exemple de variable assignées :

        Début
            une_chaine ← “lorem ipsum”
            un_compteur ← 2
            un_reel ← 2.7
            un_booleen  ← vrai
        Fin
        

Cas particulier : les variables de type tableaux

Les tableaux sont un type de variables permettant de stocker plusieurs données auquelles ont accède par leur position/leur index dans celui-ci.

Comme un tableau sur papier, ceux-ci peuvent avoir un nombre de colonnes plus ou moins conséquentes. On distingue deux familles de tableau : unidimentionnels (une colonne, plusieurs lignes) et multidimentionnels (plusieurs colonnes, plusieurs lignes)

La déclaration d’une variable tableau s’écrit dans la partie déclarative comme suit :

1. nom et dimensions du tableau
2. deux points
3. type du tableau

Exemples de déclaration de variables tableau :

        Variables
            tableau_unidimentionnels[1,10] : tableau de Entier
            tableau_multidimentionnels[1,10][1,10] : tableau de Entier
        

Dans l’exemple ci-dessus :

• la variable tableau_unidimentionnels[1,10] est un tableau d’une colonne et 10 lignes.
• la variable tableau_multidimentionnels[1,10][1,10] est un tableau de 10 colonnes et 10 lignes.

Le corps de l’algorithme

En algorithmique, on dispose d’un certain nombre d’instructions et d’opérateurs permettant d’indique l’action à réaliser.

Les structures de contrôle conditionnelles

Si, alors

Si la condition est vrai, alors on effetue l’instruction 1. Puis, on effectue l’instruction 2.

        Si condition = vrai Alors
            instruction_1
        Fin si

        instruction_2
        

Si, alors, sinon

Si la condition est vrai, alors on effetue l’instruction 1, sinon, on effectue l’instruction 2. Puis, on effectue l’instruction 3.

        Si condition = vrai Alors
            instruction_1
        Sinon
            instruction_2
        Fin si

        instruction_3
        

Si, alors, sinon, si, alors sinon

Si la condition est vrai, alors on effetue l’instruction 1, sinon, si le test 2 est vrai, alors on effectue l’instruction 2, sinon, on effectue l’instruction 3. Puis, on effectue l’instruction 4.

        Si condition = vrai Alors
            instruction_1
        Sinon si condition = vrai Alors
            instruction_2
        Sinon
            instruction_3
        Fin si

        instruction_4
        

Selon

        Selon variable_1 
            Cas valeur_1 :
                instruction_1
            Cas valeur_2 :
                instruction_2
            Cas autre :
                instruction_3
        Fin selon

        instruction_4
        

Les structures de contrôle itératives

Tant que

Tant que la condition du test est respectée, on effectue l’instruction 1. Puis, on effectue l’instruction 2.

        Tant que condition = vrai
            instruction_1
        Fin tant que

        instruction_2
        

Jusqu’à

jusqu’à ce que la condition soit respectée, on effectue l’instruction 1. Puis, on effectue l’instruction 2

        Répète
            instruction_1
        Jusqu'à condition = vrai

        instruction_2
        

Exemples d’algorithme du quotidien

Calculer le TTC d’un montant

L’algorithme ci-dessous permet de saisir un montant hors taxes et d’afficher le montant TTC pour une TVA de 20%.

        Algorithme TTC
        Constantes
            TVA = 0.2
        Variables
            montantHT : Réel
            montantTTC : Réel
        Début
            Afficher "Saisir le montant HT"
            Saisir montantHT
            montantTTC ← montantHT * ( 1 + TVA )
            Afficher montantTTC
        Fin