Exercice 3 Adso de Melk s’est intro duit de nuit sans autorisation dans la biblioth`que de l’abbaye. Celle-ci est organis´e comme un labyrinthe et au b out d’un certain temps Adsos’est rendu compte qu’il s’´tait p erdu. Il doit absolument sortir avant le premier office pourque p ersonne ne remarque son absence. Heureusement il disp ose d’une lamp e, de craie et a de quoi ´crire. Il sait aussi que les pi`ces de la biblioth`que ont entre une et quatre entr´es (toujours orient´es selon une des directions E,O,N,S) et que chaque pi`ce a un nom unique ecrit dans un cartouche au centre du plafond.
1. D´crire un algorithme qui permet a Adso de sortir de la biblioth`que. Votre descrip tion doit ˆtre pr´cise, non ambigue, et compr´hensible par un novice.
2. Peut-on se passer de l’hyp oth`se que le nom de chaque pi`ce est connu ?
3. Adso a p´n´tr´ a minuit dans la biblioth`que et il s’est rendu compte qu’il etait perdu une demi-heure plus tard. Il lui faut 2 minutes par pi`ce p our dechiffrer le nom de la pi`ce et examiner les entr´es. La biblioth`que comp orte 25 pi`ces et Adso met 10 minutes p our aller de la biblioth`que a sa cellule. Votre algorithme garantit-il qu’Adso sera de retour dans sa cellule avant le premier office qui a lieu a 4h30 du matin?