next up previous contents index
suivant: Choix du langage monter: Introduction précédent: Prérequis   Table des matières   Index


Objectifs

L'objectif de ce livre est de donner une image fidèle de ce que représentent les études supérieures en informatique puis le travail quotidien d'un informaticien.

Au centre du livre se trouve le graphe. Contrairement à d'autres objets mathématiques, comme les entiers, les sommes, etc., le graphe n'a pas une définition unique. L'informaticien se permet de la modifier en fonction des applications qu'il étudie. Dans ce livre, nous examinons un certain nombre de définitions raisonnables de graphes, et nous examinons les conséquences de celles-ci pour les problèmes traités.

La définition précise d'un objet n'est que le point de départ du travail. Il faut ensuite expliquer à un ordinateur comment le manipuler. Pour cela, chaque aspect de l'objet (graphe en ce qui nous concerne) doit être codé à l'intérieur de la mémoire de l'ordinateur. Il y a plusieurs façons d'obtenir un tel codage; on parle de représentation physique de l'objet.

Nous traitons assez peu la notion de représentation physique dans ce livre, car cela nécessiterait une connaissance de base sur l'architecture de l'ordinateur.

Par contre, nous utiliserons constamment la notion de représentation abstraite, centrale dans ce livre. Elle exprime les opérations utilisables par le programmeur pour manipuler l'objet. L'ensemble des opérations abstraites sur un objet est souvent déterminé par la représentation physique et contient en particulier des opérations efficaces (du point de vue du temps d'exécution). Il est essentiel pour le programmeur de bien examiner la manière dont son logiciel sera utilisé, afin de déterminer les opérations utilisées le plus fréquemment et choisir une représentation abstraite qui les optimise.

La représentation abstraite d'un graphe détermine donc ce que le programmeur a le droit de faire. Un programme qui manipule un graphe sera écrit en utilisant la représentation. Cependant, pour une représentation donnée, il y a le plus souvent plusieurs algorithmes possibles ayant le même effet souhaité sur l'objet. Un des objectifs de ce livre est d'examiner divers algorithmes sur les graphes et de déterminer leur efficacité (temps d'exécution) grâce à un outil mathématique appelé complexité asymptotique. Il s'agit essentiellement de déterminer, pour un algorithme donné, le nombre d'opérations élémentaires que doit effectuer l'unité centrale pour exécuter l'algorithme, et ceci indépendamment d'un type d'ordinateur particulier.

Après avoir choisi sa représentation et son algorithme, le programmeur doit encore le transcrire sous forme de programme en utilisant un langage de programmation. Là encore, plusieurs programmes sont possibles. Le dernier objectif de ce livre est de donner des conseils concernant l'organisation exacte du programme afin de favoriser sa modification ultérieure.


next up previous contents index
suivant: Choix du langage monter: Introduction précédent: Prérequis   Table des matières   Index