Avant-propos
|
Dans la littérature de cet hémisphère (...) abondent les
objets idéaux, convoqués et dissous en un moment, suivant les
besoins poétiques. Ils sont quelquefois déterminés par la pure
simultanéité. Il y a des objets composés de deux termes, l'un de
caractère visuel et l'autre auditif : la couleur de l'aurore et le
cri lontain d'un oiseau. Il y en a composé de nombreux termes : le
soleil et l'eau contre la poitrine du nageur, le rose vague et
frémissant que l'on voit les yeux fermés, la sensation de quelqu'un
se laissant emporter par un fleuve et aussi par le rêve. Ces objets
au second degré peuvent se combiner à d'autres ; le processus, au
moyen de certaines abréviations, est pratiquement infini. Il y a des
poèmes fameux composés d'un seul mot énorme. Ce mot intègre un
objet poétique créé par l'auteur.
Jorge Luis
Borges
|
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 4#4, et de toute la technologie qui l'entoure, s'inscrivent exactement dans cette évolution. Car Java ne peut pas simplement être vu comme un nouveau langage, mais plutôt comme le c3#3ur 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.
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 de la première partie du cours 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, ce qui est le but de la seconde partie du cours. 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, optimisation, etc) pour leur élaboration et à des ouvrages de mathématiques discrètes pour l'étude de certains objets mathématiques, comme les graphes, introduits ici pour leurs capacités de modélisation.
À l'exception de quelques résultats élémentaires, les algorithmes ne feront ici l'objet d'aucune étude mathématique (preuve de propriétés, analyse de complexité). Bien qu'intitulée Algorithmes, cette partie n'aborde donc pas réellement l'algorithmique ; elle 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.
Mes remerciements à Gilbert Caplain, Jean-Philippe Chancelier, Olivier Carton, Étienne Duris, Hervé Grall, Mathieu Jaume, 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, Thierry Salset et Jean-Philippe Chancelier.