Introduction

Ce cours est une introduction à l'algorithmique pour les informaticiens. Il convient pour commencer de proposer une définition de ce qu'est un algorithme :

algorithme

méthode permettant de résoudre un problème de manière systématique

Cette définition montre bien que les algorithmes ne sont pas spécifiques à l'informatique ; on peut par exemple citer :

• la méthode consistant à poser une addition pour calculer la somme de deux nombres arbitrairement grands ;

• les instructions données par un GPS pour atteindre une destination ;

• une recette de cuisine pour réaliser une tarte aux pommes

comme des exemples d'algorithmes.

Ce qui distingue un algorithme d'une autre méthode de résolution de problèmes, c'est le caractère systématique de son exécution. En d'autres termes, un algorithme ne doit demander aucune initiative à celui ou celle qui l'exécute. Ceci explique l'importance de l'algorithmique en informatique : un ordinateur n'étant capable d'aucune initiative, il ne peut exécuter une tâche que si on lui fournit strictement un algorithme pour le faire. Tout programme informatique a donc, par définition, la structure d'un algorithme.

Afin de pouvoir être exécuté de manière systématique, un algorithme doit absolument éviter l'ambiguïté. Or les langues naturelles, comme le français, sont intrinsèquement ambiguës. Il est donc indispensable d'écrire les algorithmes dans un langage formel, dont la sémantique est précisément définie. Dans ce cours, nous utiliserons le langage Python 3. Tout en étant relativement lisible et facile à écrire, Python est un vrai langage de programmation ; tous les exemples du cours sont donc exécutables directement par un ordinateur (sous réserve que Python y soit installé, évidemment). Cependant, ce cours ne vise pas à être un cours de programmation en Python ; il n'aborde pas toutes les spécificités de ce langage, et les notions présentées restent valables dans la majorité des autres langages de programmation1.

Le caractère systématique ne signifie pas pour autant que l'exécutant de l'algorithme ne doit rien savoir faire a priori. Au contraire, tout algorithme présuppose un certain nombre de capacités. Dans les exemples ci-dessus :

• poser une addition suppose de connaître ses tables d'additions ;

• suivre un GPS suppose de savoir conduire, de connaître sa droite et sa gauche, ainsi que le code de la route ;

• suivre une recette de cuisine suppose de savoir peser, couper, verser... les ingrédients.

Les algorithmes pour l'informatique doivent donc s'appuyer sur ce que « sait faire » l'ordinateur. En pratique, ces capacités dépendent du langage et de l'environnement de programmation utilisés. Dans ce cours, c'est donc un sous-ensemble du langage Python qui déterminera les capacités initiales de l'ordinateur, au dessus desquelles nous construirons nos algorithmes (et qui seront décrites au chapitre Valeurs, expressions et variables).

Notes de bas de page

1

Dans certains cas, nous éviterons même d'utiliser certaines fonctionnalités de Python, afin de mieux mettre en avant certaines notions algorithmiques.