Avant-propos
La définition rigoureuse de ce qu'est un algorithme est du ressort de l'informatique théorique, laquelle fait appel à des notions de logique mathématique ; ce n'est pas l'objet de ce cours. N'importe quel dictionnaire en donne une définition intuitive, et nous en verrons suffisamment d'exemples pour affiner cette intuition. Disons simplement que l'algorithme est la forme que revêtent les solutions que l'informatique sait donner aux problèmes qui lui sont posés. Certains algorithmes sont implémentés directement par des circuits électroniques numériques : c'est le cas de ceux qui réalisent les opérations arithmétiques, et d'algorithmes beaucoup plus élaborés comme la transformée de Fourier rapide. C'est aussi le rôle de certains circuits que l'on trouve sur des objets courants (carte à puce, appareil photo, téléphone portable) dont l'usage est bien délimité et non modifiable.
Un ordinateur ne diffère guère de ces objets courants, puisqu'il contient des circuits implémentant un (unique) algorithme dont l'usage est tout aussi délimité et non modifiable : << exécuter des programmes >>. La description de cet algorithme étant le sujet d'un cours d'architecture des machines, et non de ce cours, nous ne pouvons ici qu'énoncer son caractère universel : l'algorithme implémenté par les circuits d'un ordinateur est capable de simuler n'importe quel autre algorithme. Les instructions nécessaires à cette simulation forment un programme, qu'il suffit d'exécuter.
Du modèle d'architecture conçu, dans les années 44-46, par von Neumann, Wilkes, Goldstine et Burks, retenons qu'instructions et données sont représentées d'une même façon, par une suite d'éléments binaires. Les premiers ordinateurs construits suivant ce modèle furent programmés directement en binaire. On utilisa peu après des langages d'assemblage, qui forment une notation textuelle des instructions. Depuis la fin des années 50, on utilise des langages de programmation. Au moyen de ces langages, un programme est écrit sous la forme d'un texte, c'est-à-dire d'une suite de caractères, humainement lisible, appelé programme-source, qui n'est pas directement exécutable. Une des techniques employées pour faire exécuter ce programme est de le traduire en instructions de la machine, au moyen d'un compilateur ; on obtient ainsi le programme-objet. Celui-ci peut alors être soumis à la machine pour exécution.
De nombreux langages de programmation ont été utilisés ; parmi les plus connus figurent Fortran, Lisp, Prolog, Smalltalk, Cobol, Pascal, C, C++, Java, Caml. Le langage C a été conçu et implémenté par Dennis M. Ritchie. Le Turing Award 1983 lui fut décerné, conjointement avec Ken L. Thomson pour le développement et l'implémentation du système d'exploitation Unix. Sa définition, désormais qualifiée << Kernighan-Ritchie >>, a été clarifiée et modernisée au cours de sa normalisation ANSI, publiée en 1988, et qui a adopté certaines évolutions consacrées par l'usage. Certaines de ces évolutions sont apparues à l'occasion du développement du langage C++, dû à Bjarne Stroustrup, et conçu comme une extension de C, par l'addition des classes. Il s'agissait, dans les années 1983-85, de donner au programmeur la possibilité d'écrire en C des programmes dans le style << orienté objets >>, imaginé dès la fin des années 70, à la fois pour développer des applications de simulation (le langage Simula) et les premières interfaces graphiques (Smalltalk, puis Objective C). C++ s'est depuis considérablement enrichi et stabilisé sous la forme d'une norme ISO, adoptée en 1997 et ratifiée en août 1998, pour devenir l'un des langages majeurs de l'informatique contemporaine.
Mais les enjeux s'étaient déplacés entre-temps. Avec l'émergence des micro-ordinateurs, les années 80 ont consacré la fin des ordinateurs centraux, les << mainframes >> ; avec l'émergence de l'Internet, les années 90 ont consacré la fin de l'ordinateur personnel ; avec l'émergence des systèmes embarqués, les années à venir consacreront la fin de l'ordinateur. Il faut comprendre que toujours plus d'ordinateurs centraux seront utilisés, plus de micro-ordinateurs, plus d'ordinateurs en général, mais que l'informatique aura cessé de s'identifier à l'ordinateur. Cette évolution se caractérise par la présence de techniques informatiques dans des champs d'activité de plus en plus larges, non comme outils, mais comme composants de systèmes et souvent comme composants critiques. Cette présence apparaît aussi bien dans les grands systèmes (industrie, transport, commerce, etc) que dans les objets de la vie courante (téléphone, montre, automobile, électroménager, etc). Les critères de sécurité passent au premier plan des préoccupations, le bug de l'an 2000 en étant une simple illustration.
L'informatique (ou science de l'ordinateur, computer science, ou science du calcul, computation science) s'est alors transformée en <<sciences et techniques de l'information et de la communication>>, dont les mots-clés sont :
Le développement du langage Java
,
et de toute la
technologie qui l'entoure, s'inscrit exactement dans cette évolution.
Car Java ne peut pas simplement être vu comme un nouveau langage, mais
plutôt comme le c
ur d'une nouvelle technologie, qui répond à de
nouveaux enjeux et qui se déploie dans de nombreuses applications. Java
y intervient à la fois de façon matérielle (cartes à puce, systèmes
embarqués) et de façon logicielle sous forme d'API spécialisées
(Application Programming Interface), par exemple pour l'accès aux
bases de données, la programmation réseau ou pour le graphique.
L'utilisation de ces API fait que de nombreuses applications
traditionnellement difficiles à programmer deviennent plus abordables.
La mise en uvre des algorithmes et des structures de données,
ainsi que la construction de composants logiciels supposent des
techniques de modularité et de réutilisation qui conduisent à
privilégier la programmation à objets, l'un des trois principaux styles
de programmation, avec le style impératif et le style applicatif. Tout
programme Java est une mixture de traits applicatifs, impératifs et
objets. Les programmes sont organisés dans le style objet, lequel
recourt à des expressions (style applicatif) et à des structures de
contrôle (style impératif).
Le style applicatif est entièrement fondé sur l'évaluation d'expressions satisfaisant la propriété : la valeur d'une expression ne dépend que des valeurs des sous-expressions et de l'opération qui les combine. Ce style conduit souvent à des programmes concis et faciles à comprendre, et que certains langages, comme Caml, savent exécuter efficacement. Pour écrire des algorithmes quelconques dans le style applicatif, il faut recourir à la récursivité, c'est-à-dire à la capacité d'une fonction de s'appeler elle-même. Les définitions récursives sont souvent très naturelles et résultent de techniques générales de résolution de problèmes. Par contre, les programmes ainsi construits ne peuvent pas toujours être utilisés si l'on doit respecter des exigences d'efficacité.
Le style impératif représente un algorithme à l'aide de deux types de structures : les structures de contrôle (appel de fonction, branchements, itérations) et les structures de données, le contrôle permettant d'assembler des instructions qui opèrent sur des données, en transformant l'état de la mémoire. L'instruction typique de ce style est l'affectation , et les structures de contrôle typiques sont des itérations (les << boucles >> for et while). Désormais, la valeur d'une expression dépend non seulement de l'opération et des valeurs des sous-expressions, mais aussi de l'état courant de la mémoire. La notion de valeur cède le pas à celle d'objet, la notion d'expression à celle d'instruction. Des objets sont construits, des objets sont modifiés, des objets sont détruits. C'est dans ce style qu'on écrira les programmes les plus efficaces, que les compilateurs sauront le mieux optimiser. Ses structures, qui sont souvent plus difficiles à maîtriser que celles du style applicatif, conduisent à des programmes plus difficiles à prouver, mais qui forment la majeure partie de ce que produisent les programmeurs. Fortran, Pascal, et C ont été conçus pour la programmation impérative.
L'approche orientée objet de la programmation tente de représenter un algorithme comme une communauté d'organismes vivants, chacun étant créé, disposant de ses propres ressources, ayant éventuellement son propre comportement et interagissant avec les autres membres de la communauté. Ceci reste de l'ordre de la métaphore, mais conduit en pratique à incorporer les instructions dans la définition même des objets, de sorte que contrôle et données cessent d'être découplés comme c'était le cas de l'approche classique. Comme en programmation impérative, des objets sont créés, modifiés, détruits ; mais ce sont maintenant les interactions entre objets qui constituent la trame des programmes écrits dans ce style. C++ et, plus récemment, Java et Objective CAML, sont des langages représentatifs de ce style de programmation.
Le style objet s'est développé avec le triple objectif
d'améliorer la capacité des programmes à modéliser les objets physiques,
à organiser le logiciel et à gérer les ressources mises en uvre. En
premier lieu, le génie logiciel, pareil à toute autre activité
d'ingénierie, a conduit à la notion de << composant >> logiciel, forme
de module. Une fois produit, un module peut être réutilisé : il
offre un certain nombre de services, et en utilise d'autres, ce qui
constitue l'interface du module. D'autre part, la programmation
a pour objectif de construire des modèles de processus calculatoires,
les algorithmes, laissant à d'autres disciplines le soin de construire
des modèles des processus du monde physique. Le développement de la
programmation objet est dû au souhait que la programmation elle-même
puisse contribuer à cette modélisation. Enfin, la mise en uvre
d'un algorithme sur une machine suppose que certaines ressources
matérielles sont disponibles : comment ces ressources sont acquises,
désignées, utilisées et rendues. La plus importante de ces ressources
est la mémoire. La gestion de ces ressources est partagée entre le
programmeur et le système. Les langages à objets cherchent à rendre la
gestion des ressources la plus uniforme possible, à travers la notion
d'objet.
Certaines caractéristiques sémantiques des langages à objets (comme la modularité, l'encapsulation, l'héritage, le sous-typage, la liaison tardive) sont liées à ce style de programmation. L'utilisation judicieuse de ces techniques, requise pour le développement de systèmes logiciels complexes, reste cependant assez difficile - et une affaire de goût.
Ce document constitue le support des deux cours Objets et patterns (chapitres 1 et 3) et Algorithmes (chapitre 2). Le premier cours est consacré à la programmation à objets en Java. Les informaticiens, quand ils se font linguistes, distinguent la syntaxe, la sémantique, et la pragmatique d'un langage de programmation.
La syntaxe regroupe les règles lexicales et grammaticales de formation des programmes, qui permettent de décider si un texte est un << programme syntaxiquement correct >>, ou plus simplement, est un << programme >>, ou bien s'il comporte des << erreurs de syntaxe >>. Tout débutant doit se sentir rebuté par cette forme d'écriture et sa rigidité qui ne pardonne pas la moindre faute de frappe ; la connaissance des règles syntaxiques facilitera surtout le travail du compilateur. L'idéal serait d'appliquer ces règles sans jamais devoir les apprendre, en utilisant un éditeur de texte bien configuré (Emacs, ou celui d'un environnement de programmation) en lisant beaucoup de programmes bien écrits et en procédant par imitation. Disons le clairement : la syntaxe de Java n'est pas un objectif de ce cours. On trouvera cependant en annexe la grammaire complète de Java, à titre de référence.
La sémantique explicite la signification des programmes : quelle est la valeur d'une expression, quel est l'effet d'une instruction. C'est ici que résident les concepts réellement importants de la programmation, qui s'appliquent également à d'autres langages : évaluation, portée des déclarations, appel de fonction, modes d'allocation, etc. Les objectifs de sûreté et d'efficacité des programmes nécessitent une connaissance précise de la sémantique : celle-ci sera donc traitée dans ce cours, de façon très informelle mais assez complète, et constitue l'essentiel de la partie Objets.
Formes (syntaxiques) et concepts (sémantiques) ne suffisent pas pour apprendre à programmer. La pragmatique désigne la mise en pratique de ces formes et concepts : quelle construction utiliser dans tel contexte, comment l'utiliser, etc. La pragmatique est aux langages de programmation ce que la rhétorique fut au langage parlé pendant des siècles : un ensemble de règles de l'art, de recettes, d'exemples et d'usages que reconnaissent les programmeurs. L'ambition du cours Objets et patterns est de faire partager des éléments, nécessairement disparates, de cette pragmatique de Java, en recourant à la notion de pattern.
Il faut encore avoir quelque chose à dire, pour écrire des programmes qui ont du sens. Les programmes de ce cours satisfont un unique objectif, qui est de résoudre des problèmes, au moyen d'algorithmes. Ceux-ci sont conçus, parfois par des informaticiens, et souvent par des spécialistes de la discipline dont émane le problème posé, qui maîtrisent des techniques de résolution spécifiques (par exemple en mathématiques appliquées). Le lecteur est renvoyé à d'autres cours (probabilités, calcul scientifique, recherche opérationnelle, etc) pour leur élaboration. À l'exception de quelques résultats élémentaires, les algorithmes ne feront l'objet d'aucune étude (preuve de propriétés, analyse de complexité) : le troisième chapitre, Algorithmes, n'aborde donc pas réellement l'algorithmique. Il présente plutôt quelques structures de données utiles, les principales formes d'algorithmes ainsi que quelques algorithmes résolvant des problèmes classiques. Les chapitres 2 et 3 sont très interdépendants, comme le lecteur le constatera en suivant les nombreux renvois mutuels.
Mes remerciements à Gilbert Caplain, Jean-Philippe Chancelier, Olivier Carton, Étienne Duris, Hervé Grall, Mathieu Jaume, Renaud Keriven, Bernard Lapeyre et Thierry Salset pour leur relecture de ce texte et leurs nombreuses corrections et suggestions. L'installation des logiciels et de l'environnement de travail a été effectuée par Tu Dien Au, Jean-Louis Boudoulec, Jean Couedic et Thierry Salset. La traduction de ce texte, de LATEX en HTML, et son installation sur le Web ont été réalisées par Jean-Philippe Chancelier.