Historiquement, les ordinateurs sont avant tout des machines à
calculer : c'est d'ailleurs là l'unique utilisation qui a été faite du
premier d'entre eux, l'ENIAC. Il semble donc naturel de démarrer un
cours d'initiation à l'informatique par une étude de la représentation
des nombres (entiers ou pas), ainsi que des algorithmes fondamentaux
de manipulation que sont l'addition et la multiplication.
L'objectif de ce cours est double :
-
connaître (et comprendre) divers systèmes de représentation des
nombres, ainsi que les traductions d'un système à l'autre. Ceci
inclut non seulement les représentations <<abstraites>>, ou de haut
niveau, comme par exemple la représentation Fibonacci,
qui ne sont pas naturellement celles choisies pour représenter les
nombres en machine, mais aussi les représentations <<concrètes>>,
c'est-à-dire celles qu'une machine peut utiliser avec plus ou moins
de profit (et on verra notamment certains des problèmes posés par la
représentation des réels en virgule flottante).
- introduire des rudiments d'algorithmique, par le biais des
opérations de base sur les nombres (addition et multiplication
principalement, mais d'autres aussi, cf les divers
exercices). Ceci inclut les notions de preuve (de correction
ou d'arrêt) d'algorithme, ainsi que des notions de complexité, par
l'estimation, la plus précise possible, du nombre
d'opérations élémentaires effectuées par un algorithme en fonction
de la taille de ses données d'entrée.
Autant que faire se peut, j'ai essayé de rédiger le plus clairement
possible les preuves des
affirmations contenues dans le texte (théorèmes et autres). La lecture
de ces preuves n'est pas nécessaire à la compréhension des notions
exposées, mais elle est évidemment fortement encouragée (ne serait-ce
que par l'utilisation qui est faite de techniques de preuve auxquelles
vous n'êtes pas accoutumés).
Concernant les exercices, la plupart sont originaux; d'autres font
partie du folklore (par exemple les jeux d'allumettes). Ils sont, dans
leur grande majorité, relativement faciles : il s'agit de simples
applications du
cours, et sinon quelques minutes de réflexion devraient
suffire. Quelques-uns sont par contre beaucoup plus retors, et ils
sont alors indiqués par une ou deux étoiles, selon leur degré de
difficulté.
Les principales sources que j'ai utilisées sont les suivantes :
-
David GOLDBERG, What Every Computer Scientist Should Know
About Floating-Point Arithmetic, ACM Computing Surveys, Vol. 23,
No 1, March 1991, pp 5--48;
- Ronald GRAHAM, Donald KNUTH, Oren PATASHNIK, Concrete
Mathematics : A Foundation for Computer Science, Addison-Wesley;
- Donald KNUTH, The Art of Computer Programming, volume 2,
<<Seminumerical Algorithms>>, Addison-Wesley;
- Jean-Marie MULLER, Arithmétique des ordinateurs, Masson.