Introduction

Qu'est-ce qu'un ordinateur et qu'est-ce qu'on y trouve ? Un clavier, un écran, une carte mère, un processeur, de la mémoire, un disque dur, des périphériques (lecteur de disquettes, CD, DVD, imprimantes, etc.). Bref, plein de choses mais les seules vraiment indispensables, sont le processeur (qui fait des opérations arithmétiques élémentaires), la mémoire (dans laquelle le processeur peut stocker des résultats intermédiaires) et le bout de fil qui est entre les deux (également appelé «bus») qui se trouve sur la carte mère.

Comment se fait-il que l'on arrive à faire des choses aussi complexes avec un processeur qui, en gros, ne sait faire que des opérations arithmétiques élémentaires ? À un niveau un peu supérieur, nous nous intéresserons dans ce cours à la conception d'algorithmes (c'est-à-dire de méthodes) exprimés dans un langage élémentaire et «compréhensible» par un ordinateur. Nous utiliserons donc un pseudo-langage de haut niveau, en français et relativement souple, pendant les cours de façon à s'abstraire des difficultés posées par un vrai langage. Une fois ce pseudo-langage maîtrisé, nous traduirons nos algorithmes en langage C. Ce langage date des années 70/80 est relativement bas niveau. Cela signifie que le C manipule les mêmes sortes d'objets que que la plupart des ordinateurs, à savoir des caractères, des nombres et des adresses. Ce langage est disponible sur toute les plates-formes existantes à ce jour et quand il ne l'est pas (sur une plate-forme embarquée comme un robot ou un agenda électronique), on effectue une compilation croisée.

Qu'est-ce qu'une compilation et comment se fait-il qu'un même langage puisse être utilisé sur autant de processeurs différents (i386, PowerPc, Atari, Sparc, Mips, etc.) ? Comme nous l'avons déja dit, chaque processeur n'est capable de faire que des choses élémentaires. Pour compliquer les choses, chaque processeur est utilisable à l'aide d'un langage machine il existe différents types de langages machine. Un compilateur permet de transformer un programme écrit en un langage comme le C en langage machine. Il existe donc autant de compilateur que de familles de processeurs, de langages et de système d'exploitation (enfin presque car certains langages n'ont jamais été porté sur certains systèmes). Nous utiliserons le C sous linux.

Mais avant de programmer, il faut définir un algorithme. Un algorithme est une procédure de calcul bien définie, qui prend en entrée une valeur (ou un ensemble de valeurs), et qui produit, en sortie, une valeur ou un ensemble de valeurs. Un algorithme est donc une suite d'étapes de calcul permettant de passer de la valeur d'entrée à la valeur de sortie. Un algorithme permet donc de résoudre un problème combinatoire. L'énoncé du problème spécifie en termes généraux la relation désirée entre l'entrée et la sortie. L'algorithme décrit une procédure de calcul permettant d'établir cette relation.