programmation (suite)

Plus schématiquement, effectuer l’analyse de faisabilité d’un problème revient à vérifier qu’il est possible de ramener celui-ci, du point de vue de la logique, à
— un ensemble fini de symboles ;
— un ensemble fini de relations formelles entre symboles ;
— une liste séquentielle de règles globales de manipulation des relations et symboles précédents (automates finis) permettant formellement d’aboutir au résultat désiré.

La construction des algorithmes logiques

On appelle algorithme tout processus qui :
— décompose une tâche globale en un nombre fini de travaux élémentaires, c’est-à-dire susceptibles d’être effectués par l’entité à laquelle en sera confiée la réalisation ;
— décrit explicitement l’ordonnancement temporel desdits travaux élémentaires.

Ayant terminé l’analyse de faisabilité, l’informaticien sait donc si, formellement, le problème qu’il étudie peut être traité ou non par un ordinateur. Cependant, à ce stade et même si la réponse à la précédente question est oui, il ne sait pas encore nécessairement comment effectuer logiquement ledit traitement dans le détail, car, pour savoir si quelque chose est réalisable, il n’est pas obligatoire d’être capable d’en effectuer la construction : il suffit, par exemple, de savoir que cela a déjà été fait.

Par suite, une fois prise la décision de continuer l’analyse du problème en vue de son traitement par un ordinateur et compte tenu des capacités limitées de ce dernier, l’informaticien va devoir compléter et entièrement expliciter (du point de vue de la logique) la formulation des diverses étapes du traitement formel. Il devra donc décrire complètement tous les algorithmes de traitement formel de l’information que la résolution de ce problème nécessite. Or, ces traitements formels sont rarement spécifiques du problème envisagé, et, par suite, en vue d’une économie d’efforts, l’informaticien a intérêt à se constituer, au fur et à mesure des besoins, une bibliothèque d’algorithmes ; cette tâche est hautement facilitée par les nombreuses publications relatives à ce sujet faites dans les revues d’informatique. De plus, à un traitement formel donné correspondent en général plusieurs algorithmes ; par exemple, il existe au moins une dizaine de méthodes permettant de calculer de façon approchée les racines d’une équation algébrique. À ce niveau de l’étude, rien ne permet de faire un choix entre ces diverses possibilités de traitement, et celles-ci doivent donc, pour l’instant, être considérées comme équivalentes.

La notion d’algorithme

Si un écolier sait seulement lire, écrire sur du papier ligné, reconnaître la droite de la gauche, effectuer des soustractions de nombres entiers, de deux nombres entiers a et b reconnaître si a est supérieur, égal ou inférieur à b, être en mesure intellectuellement d’exécuter les instructions qu’on lui donne, on peut le mettre en mesure de calculer le plus grand diviseur commun (p. g. d. c.) de deux nombres entiers a et b en lui fournissant l’ensemble de « règles du jeu » suivant.
— Règle 0 : commencer le travail par la lecture de la règle 1.
— Règle 1 : écrire sur une même ligne les deux entiers a et b, a étant posé à gauche de b ; passer à la règle 2.
— Règle 2 : comparer les nombres posés ; passer à la règle 3.
— Règle 3 : si les nombres sont égaux, leur valeur commune est la réponse désirée ; fournir cette réponse et arrêter le travail ; sinon passer à la règle 4.
— Règle 4 : si le nombre posé à gauche est plus petit que celui qui est posé à droite, recopier ces nombres sur la ligne en dessous de celle sur laquelle il a été écrit précédemment, en posant à gauche le plus grand des deux nombres et à droite le plus petit ; sinon ne rien faire ; passer à la règle 5.
— Règle 5 : soustraire le nombre posé à droite de celui qui est posé à gauche ; écrire le résultat sur la même ligne que les précédents à leur droite ; passer à la règle 6.
— Règle 6 : recopier sur la ligne en dessous de celle sur laquelle on vient d’écrire les deux derniers nombres de droite de cette ligne ; passer à la règle 2.

Si on lui demande de calculer le plus grand diviseur commun de 35 et 56, sa page de calcul sera :

L’ensemble des règles précédentes constitue pour cet écolier (ou pour toute entité ayant les mêmes capacités) « un algorithme de calcul du plus grand diviseur commun de deux nombres entiers », c’est-à-dire un processus fournissant le résultat désiré, processus qu’il est en mesure d’appliquer de façon entièrement automatique chaque fois qu’on lui fournit deux nombres entiers et qu’on lui en demande de calculer le plus grand diviseur commun, et ce, d’ailleurs, sans qu’il ait à savoir ce qu’est un plus grand diviseur commun.

La définition externe des fichiers

Heuristiquement, un fichier associé à un problème est un ensemble de quantités d’information utilisées dans ce problème et ayant toutes une nature et, au moins, une utilisation (au cours de certaines phases) communes ; cet ensemble de données est supposé muni d’une structure, c’est-à-dire d’un procédé d’identification par ordonnancement de ses éléments (ou articles). Si, par exemple, le problème envisagé a pour ensemble d’informations tout ce qui est relatif aux opérations comptables concernant le personnel d’une entreprise, on définira comme fichiers :
— l’ensemble des « caractéristiques individuelles des employés », chaque article de ce fichier étant constitué de la réunion des informations (nom, prénom, numéro de sécurité sociale, classification, taux de rémunération, etc.), cet ensemble, qui concerne chaque membre du personnel de l’entreprise considérée, est muni, par exemple, de la structure : ordre alphabétique sur la partie « nom, prénom » de chaque article ;
— l’ensemble des « absences du personnel », un article de ce fichier étant, par exemple, constitué de la réunion des informations : nom, prénom, numéro de la semaine, nombre d’heures d’absence pendant cette semaine, etc. ;
— l’ensemble des « congés du personnel » ;
— l’ensemble des « heures supplémentaires », etc.

Un fichier est sélectif si l’on peut avoir accès à un de ses articles sans nécessairement pour cela devoir prendre connaissance des autres articles : un dictionnaire anglais-français est par construction un fichier du type sélectif.

Un fichier est séquentiel s’il ne doit jamais être envisagé comme sélectif, autrement dit si toutes les utilisations que l’on peut en avoir en vue impliquent la nécessité de prendre connaissance de l’ensemble de ses articles pour obtenir l’information désirée : par exemple, la liste des candidats reçus à un concours est un fichier de type séquentiel.

On appelle méthode d’accès toute technique permettant d’obtenir un article précis dans un fichier donné à partir de la connaissance de la structure de ce fichier.