Les bases de l'algorithmique

Dans la première partie, j'introduis les définitions et les notions de base de l'algorithmique telles que les varaibles, l'affichage, la saisie.

Avant de rentrer dans vif du sujet, je vous propose de passer en revue quelques définitions.

Algorithme

Un algorithme est une suite ordonnée et finie d’instructions visant à résoudre un problème donné.

Pour tenir un discours mathématique, un algorithme est la description d’une méthode de calcul (l’algorithme d’Euclide par exemple).

Généralement un algorithme a des entrées et des sorties. Les instructions s'appliquent aux entrées afin de produire les sorties attendues. Pour les mêmes entrées, l’algorithme doit retourner les mêmes sorties ie que si l’on exécute plusieurs un algorithme avec les mêmes entrées alors on aura la même sortie.

Les recettes de cuisine sont de parfaits exemples d’algorithme. Les ingrédients sont les entrées et le plat final représente la sortie. Pour passer des ingrédients au plat final, le cuisinier doit suivre des instructions bien précises et ce dans un ordre.

Exemple: Algorithme S’habiller

1. Mettre le caleçon
2. Mettre le débardeur
3. Mettre le pantalon
4. Mettre la chemise
5. Mettre les chaussettes
6. Mettre les chaussures

Je vous propose de revenir sur quelques termes essentiels de la définition, ordonnée et finie.

L'importance de l'ordre

Ordonnée: En effet les instructions doivent être exécutées dans un ordre bien défini, une interversion (permutation) pourrait compromettre le bon fonctionnement de l’algorithme. Si vous suivez ces instructions dans l’ordre vous aurez le résultat attendu, celui d’être habillé. Par contre si l’on intervertit les instructions alors vous ne pouvez plus être certains d’obtenir le résultat. Si intervertir les instructions 1 et 2 ou encore les instructions 3 et 4 ne pose pas de problème, on a un vrai problème si on le fait avec les instructions 1 et 3 ou 2 et 4 ou encore 5 et 6.

Un temps d'exécution raisonnable

Finie: Cela me semble évident, il faut bien que l'exécution s’arrête à un moment donné. Je vous propose une nouvelle formulation de la définition: Un algorithme est une suite ordonnée et finie d’instructions visant à résoudre un problème donné dans un temps raisonnable. Imaginez que l’on souhaite additionner deux nombres et que les instructions tendent à être infinies, cela n’a aucun intérêt.

Principe de non-ambiguïté

Si l'on exécute un algorithme avec les mêmes entrées, il doit produire les mêmes résultats. C'est ça le principe de non-ambiguïté. Un algorithme qui additionne deux nombres entiers doit toujours produire le même résultats à chaque exécution si les entrées sont les mêmes à chaque fois.

Algorithmique

C’est la discipline qui étudie la conception et l’optimisation des algorithmes. D’aucuns diront qu’il s’agit d’une branche de l’informatique… C’est vrai, l’algorithmique a beaucoup évolué et se positionne aujourd’hui entre les mathématiques et l’informatique.

Algorithmicien

Le professionnel qui travaille sur les algorithmes. Il s’agit généralement d’informaticiens ou de mathématiciens.

---

Et c'est tout pour les définitions, rendez-vous dans la prochaîne section pour découvrir les notions de variables et de constantes.