PROFDINFO.COM

Votre enseignant d'informatique en ligne

Travail 1 - Les oracles

Consignes

Le problème

OracleIl y a très, très longtemps, dans le royaume de Télanor, vivait une princesse nommée Sorga. Soupçonnée d'entretenir une relation amoureuse avec un simple paysan, Sorga fut un jour enfermée au donjon par son père, le terrible Mazillion. Ne pouvant survivre à l'idée de plus revoir Sorga, le paysan, nommé Beraki, se décida un jour à affronter Mazillion pour lui demander de rendre la liberté à sa fille. Impressionné, semble-t-il, par la détermination du jeune homme, le roi lui donna une chance: "Si tu trouves en moins de trois jours le nombre de cavaliers tués au cours de la fameuse bataille de la Vallée des Zugles, ma fille sera libérée. Sinon, tu seras chassé à jamais de mon royaume." Beraki n'avait d'autre choix que d'accepter l'offre du père de Sorga. Il quitta le château, la mort dans l'âme, ne sachant comment trouver réponse à la question de Mazillion. La bataille de la Vallée des Zugles s'était déroulée il y a des siècles et peu d'écrits subsistaient à ce jour sur le déroulement de ce tragique événement. Et de plus, ni lui, ni aucun de ses proches ne savaient lire. C'est alors qu'il se rappela une histoire que lui racontait parfois sa mère alors qu'il était enfant. Dans la Forêt bleue, au-delà du fleuve Tangrin, vivraient des oracles. Sous la forme d'étranges vieillards à l'âge indéterminé, ces oracles seraient détenteur de toute la connaissance du monde, et répondraient avec bienveillance à tous les êtres au cœur pur qui leur poseraient des questions. Mais ce qu'ignorait alors Beraki, c'est que le sombre Zoumtor, le plus grand sorcier des royaumes du Nord et une vieille connaissance de Mazillion, a jeté un sort aux oracles. Ne pouvant complètement les anéantir, le sorcier a quand même réussi à faire en sorte qu'après chaque réponse donnée à un voyageur dans la Forêt bleue, tout oracle s'endort pour une période indéterminée. Beraki arrivera-il à temps dans la forêt? Réussira-t-il à obtenir le nombre magique de la bouche des oracles? La princesse Sorga retrouvera-t-elle la liberté? C'est ce que nous saurons dans le prochain épisode.

Après cette courte introduction, vous savez à quel point il est important de découvrir le nombre magique si on veut que Sorga et Beraki se marient, soient heureux et aient beaucoup de petits bâtards. Dans ce projet, nous tenterons de réaliser cet exploit en faisant appel à la recherche dichotomique et à nos propres oracles (processus).

Les processus oracles

Un oracle est un processus enfant qui connaît la valeur du nombre magique, puisque ce dernier lui est passé lors de la création du processus ainsi que des informations sur la communication.

Maintenant, comment interroge-t-on un oracle? En utilisant le mécanisme de communication par message de Neutrino (voir les notes de cours). L'oracle agit en tant que serveur, constamment à l'écoute, il attend qu'on lui envoie un nombre entier. Après réception du nombre, il retourne une réponse déterminée en fonction de la valeur du nombre magique par rapport au nombre transmis. La convention utilisée pourrait être la suivante:

 

Valeur retournée Signification
-1
Le nombre magique est inférieur à celui transmis à l'oracle.
0
Le nombre magique est celui transmis à l'oracle.
1
Le nombre magique est supérieur à celui transmis à l'oracle.

Vous pouvez utiliser une autre convention. Vous ne pouvez toutefois pas retourner au client davantage d'informations (aucun autre indice).

L'oracle est construit à l'aide d'une boucle sans fin: il attend un message, répond au message et s'endort pour une période spécifiée sur la ligne de commande. À son réveil, il retourne attendre un message et le cycle se poursuit. Il devrait être possible de mettre fin proprement à l'exécution d'un oracle, par exemple, en lui transmettant une valeur négative. Rappelons que la création d'un processus peut se faire à l'aide des fonctions fork() et exec*() ou spawn().

Le processus principal

Le processus principal commencera par créer le nombre d'oracles spécifié sur la ligne de commande, puis, procédera à la recherche dichotomique (voir plus loin) jusqu'à la découverte du nombre magique. Le nombre magique, le nombre d'oracles utilisés et la durée de sommeil des oracles sont passés en parramètres lors du lancement du programme.

Le nombre magique est un entier dans l'intervalle 0 à 32767. Le nombre d'oracles peut varier de 1 à un maximum que vous êtes libre de déterminer. Ce maximum ne doit toutefois pas être inférieur à 10. Quant à la durée du sommeil des oracles, il s'agit d'un nombre entier dans l'intervalle 0 à 1000 (les unités sont des ms).

La recherche dichotomique

Nous avons écrit plus haut que la quête du nombre magique devait utiliser la recherche dichotomique. Vous n'êtes pas obligé. Libre à vous d'utiliser un autre algorithme ou même le pur hasard. Vous serez dans ce cas gravement pénalisé au niveau de la performance.

Mais qu'est-ce que la recherche dichotomique (ou recherche binaire)? Eh bien c'est tout simplement celle que vous utilisez pour chercher un numéro dans le bottin téléphonique ou un mot dans le dictionnaire. Vous ouvrez le bottin au milieu, déterminez si le nom se trouve dans la partie gauche ou droite, ouvrez la partie pertinente (celle où devrait se trouver le nom) en son milieu et ainsi de suite jusqu'à la découverte de l'information. Dans ce programme, vous lancerez une recherche dichotomique sur chacun des oracles disponibles, la recherche N étant basée sur le résultat de la recherche N-1.

Les résultats

À la fin de l'exécution de votre programme, vous devez afficher les informations suivantes:

• nombre magique;
• nombre d'oracles utilisés;
• durée du sommeil des oracles;
• nombre de recherches (questions aux oracles).

Lors de la correction, nous pourrons comparer les différents programmes pour voir ceux qui obtiennent la meilleure performance avec un nombre donné d'oracles!

Les oracles - Grille de correction

 

Nom:
 
Nom:
 

 

Critères
Pointage
Fonctionnalités (60%)
 
Gestion des paramètres de la ligne de commande
/5
 
Lancement et arrêt des oracles
/20
 
Recherche dichotomique du nombre magique
/20
 
Respect des délais des oracles
/5
 
Affichage des résultats
/10
Qualité de la programmation (40%)
  Auto-documentation
/10
 
Présentation du code source
/10
 
Modularité de l'application
/15
 
Gestion des erreurs potentielles
/5
  TOTAL
/100