of 8

Prologin. Concours national d'informatique. Épreuve écrite d'algorithmique

0 views
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Prologin Concours national d'informatique Épreuve écrite d'algorithmique A New Hop * 1 Préambule Bienvenue à Prologin. Ce sujet est l'épreuve écrite d'algorithmique et constitue la première des
Transcript
Prologin Concours national d'informatique Épreuve écrite d'algorithmique A New Hop * 1 Préambule Bienvenue à Prologin. Ce sujet est l'épreuve écrite d'algorithmique et constitue la première des trois parties de votre épreuve régionale. Sa durée est de 3 heures. Par la suite, vous passerez un entretien (20 minutes) et une épreuve de programmation sur machine (4 heures). Conseils Lisez bien tout le sujet avant de commencer. Soignez la présentation de votre copie. Les exercices ne sont pas en ordre croissant de diculté! Lisez vraiment bien tout le sujet. N'hésitez pas à poser des questions. Si vous avez ni en avance, relisez bien, ou préparez votre présentation pour l'entretien. N'oubliez pas de passer une bonne journée. Remarques Le barème est donné à titre indicatif uniquement. Indiquez lisiblement vos nom et prénom, la ville où vous passez l'épreuve et la date en haut de votre copie. Tous les langages sont autorisés, veuillez néanmoins préciser celui que vous utilisez. Ce sont des humains qui lisent vos copies : laissez une marge, aérez votre code, ajoutez des commentaires (seulement lorsqu'ils sont nécessaires) et évitez au maximum les fautes d'orthographe, sinon ça va barder. Le barème récompense les algorithmes les plus ecaces : écrivez des fonctions qui trouvent la solution le plus rapidement possible. Si vous trouvez le sujet trop simple, relisez-le, rééchissez bien, puis dites-le-nous, nous pouvons ajouter des questions plus diciles. Les questions bonus sont à traiter seulement une fois que le sujet entier a été essayé. * Une nouvelle cabriole 1 2 Speed-Dating 1 Au c ur de la Bretagne se trouve la forêt de Brocéliande 2. Au plus profond de cette forêt, une colline. Dans cette colline, un terrier gigantesque. Et dans ce terrier, le Grand Conseil des Lagomorphes 3 s'inquiète : les lapins sont entrain de dégénérer. Les humains, qui les trouvaient trop choupinouchous, les ont croisés et recroisés sur des générations pour obtenir les animaux les plus mignons possibles 4. Si cet élevage a des avantages esthétiques, les désavantages génétiques sont désastreux ; de plus en plus d'individus ont des structures osseuses dégénérées, leurs instincts se détériorent, les allèles délétères récessifs ne sont plus couplé à des allèles sains dominants 6. Après quelques jours de débat sur les dystopies dans lesquelles pourrait tomber une société eugéniste, un accord est convenu : il faut créer une nouvelle génération diverse, et le plus vite possible. Les lapins n'ayant pas de problème moral à se reproduire dès que possible 7, un grand événement sera organisé pour améliorer les chances de mixité. Durant le SD 8, chaque lapin rencontrera chacun des lapins avec qui il n'a pas de parent commun sur G générations dans un terrier. Malheureusement les terriers sont durs à trouver et à garder, il est donc vital de savoir : le nombre de terriers à trouver le temps que durera le SD, sachant qu'une rencontre dure une minute 3 Mix and Match 9 Chaque lapin du monde a un identiant 10, et a dressé une liste de ses ancêtres (plus lui-même) sur G générations. Par exemple si G = 2 (lui-même, ses parents et ses grands-parents) : Carotte, lapin Renard, ID 6 : {1, 2, 3, 4, 5, 6} Cupcake, lapin Hermine, ID 10 : {4, 2, 1, 7, 9, 10, 8} Civet, lapin Rex, ID 16 : {11, 10, 13, 12, 15, 16, 14} Choupy, lapin Minilop, ID 24 : {18, 19, 21, 6, 23, 24} Ciboulette, lapin de Bachman, ID 30 : {23, 5, 27, 29, 30} Carotte et Cupcake ne peuvent pas se rencontrer car ils ont des ancêtres en commun : 1, 2 et 4. Cupcake et Civet ne peuvent pas non plus se rencontrer car ils ont un ancêtre commun : 10 (Cupcake lui-même). Civet et Carotte peuvent se rencontrer. Pour Choupy et Ciboulette on ne vous spoil pas. Question 1 Écrivez une fonction qui, pour deux généalogies de lapins, renvoie vrai si les deux généalogies ne partagent pas d'ancêtre. On dénit A = 2 G+1 1 comme le nombre maximal d'ancêtres dans une généalogie (un ancêtre double ou plus n'est cité qu'une fois) Rencontre rapide 2. Assimilée à la forêt de Paimpont, mais ça fait beaucoup moins classe. 3. Du grec λαγός (lagós lièvre, oreilles pendantes ) et μόρφη (morphé forme ). En gros, les animaux ressemblant au lièvre. 4. Les autres sont passés à la casserole 5 5. Lapin Brocéliande : Mettre dans une casserole 1 4L de cidre sec et 1 bol de bouillon. Ajouter 1 bouquet garni. Saler, poivrer, amener à ébullition. Faire réduire (10min environ). En parallèle, faire revenir le lapin coupé en morceaux, amber. Lier avec de la farine, retourner les morceaux. Mouiller avec cidre et bouillon, ajouter 150g de lardons blanchis et dorés. Cuire doucement 3 4 d'heure. Ajouter 1kg de cèpes (ou de girolles) étuvés au beurre. Mijoter. Écraser le foie cuit avec une fourchette, ajouter un jaune d' uf et un peu de moutarde. Mouiller avec un peu de cidre. Ajouter à la sauce avant de servir. Simone Morand (éd.) (1996) Cuisine traditionnelle de Bretagne. Gisserot. 6. Faire des bébés avec son parent/frère/s ur : évitez. 7. Voir les expressions à ce sujet se terminant par comme un lapin 8. Speed-Dating 9. Mélanger et Assortir 10. Les lapins ont une machine qui s'incrémente à chaque naissance. TGCM. Et vu que les identiants sont non-genrés, impossible de savoir si les lapins qui se rencontrent seront de sexes diérents. Ils se feront des nouveaux amis et voilà. 11. Chaque individu a 2 parents. Si une k-ième génération d'ancêtres comprend u k individus, alors la génération précédentes aura u k+1 = 2 u k individus. C'est une suite géométrique de raison q = 2. Le nombre d'ancêtres sur G générations est donc A = G k=0 u k = u 0 qg+1 1 = 1 2G+1 1 = 2 q G+1 1 2 Question 2 Donnez la complexité (en fonction de A) de votre algorithme pour la Question 1, c'est-à-dire le nombre d'opérations eectuées par l'algorithme. Question 3 (3 points) On considère maintenant, et pour le reste du sujet, que les ancêtres sont triés par identiant par ordre décroissant 12. Réécrivez une version plus ecace de l'algorithme de la Question 1. Question 4 Donnez la complexité (en fonction de A) de votre algorithme pour la Question 3. Question 5 Listez tous les couples possibles avec les cinq lapins de l'exemple ci-dessus. 4 Ne pas se tirer dans les pattes Le Grand Conseil des Lagomorphes essaye d'organiser quand se rencontrera chaque couple. Après quelques discussions sur la forme la plus pratique pour visualiser tout ce bazar (un tableau à deux entrées avec des petites croix, un dictionnaire de listes de partenaires...) c'est un graphe qui a été choisi. Un graphe est une structure de données permettant de représenter des relations dans un ensemble d'éléments. Un graphe est composé de sommets, qui représentent les éléments, et d'arêtes, qui représentent les relations entre les diérents éléments. Dans cette partie on considère un graphe non orienté représentant les contraintes physiques des participants, où les sommets sont les couples d'id des lapins se retrouvant au SD. Les sommets de ce graphe sont reliés entre eux si et seulement s'ils ont un des deux lapins en communs 13. Chaque couple sera représenté par un couple d'id. Par exemple, voici le graphe correspondant aux couples (1,2), (1,3), (2,4), (2,5) : 1,3 2,5 1,2 2,4 Question 6 Dessinez le graphe correspondant à tous les couples de la Question 5. Question 7 Quelle structure de données peut-on utiliser pour représenter votre graphe (plusieurs réponses possibles)? Question 8 Écrivez une fonction qui, pour une liste de couples de lapins, renvoie le graphe correspondant. (4 points) On dénit C comme le nombre de couples se rencontrant au SD. 12. Le lapin en tête de liste est le dernier né, c'est-à-dire celui à qui appartient la liste. 13. Deux couples reliés ne peuvent donc pas se rencontrer en même temps. Nos lapins n'ont pas le don d'ubiquité. 3 Question 9 Donnez la complexité (en fonction de C) de votre algorithme pour la Question 8. Un graphe est dit planaire s'il peut être représenté sur un plan sans qu'aucune arête n'en croise une autre. Une face est une région du plan que l'on peut colorier sans toucher d'arêtes. Par exemple le graphe plus haut possède 2 faces. Les organisateurs, comme toute bonne administration, ont commencé à faire ce graphe avec un papier et un crayon 14. Évidemment c'est vite devenu un gros gribouillis. Ils se sont donc dit qu'un graphe planaire serait bien plus joli à utiliser. Question 10 (3 points) Montrer que cette égalité est vraie pour tout graphe planaire : dans un graphe planaire, le nombre de sommets plus le nombre de faces est égal au nombre d'arêtes plus deux 15. Question 11 Écrivez une fonction qui, pour un graphe donné, renvoie vrai s'il est planaire. (4 points) On dénit V comme le nombre de sommets et E comme le nombre d'arêtes. Question 12 Donnez la complexité (en fonction de V et de E) de votre algorithme pour la Question Le Lapin Blanc vous surveille 16 Le Conseil a réussi à établir un planning pour le SD, et veut tester s'il est valide. Un planning est un ordonnancement des couples de lapins où chaque couple se voit attribuer un créneau à la i ème minute. Un planning est dit valide si et seulement si, pour chaque créneau, aucun couples de ce créneau n'a de lapin en commun. Question 13 Comment pouvez-vous intégrer un planning à la structure de votre graphe (plusieurs réponses possibles)? Question 14 Écrivez une fonction qui, pour un graphe avec planning donné, renvoie vrai si le planning est valide. Question 15 Écrivez une fonction qui, pour un graphe avec planning donné, renvoie la durée minimale du SD. (4 points) Question 16 Donnez la complexité (en fonction de V et de E) de votre algorithme pour la Question 15. Question 17 (4 points) Écrivez une fonction qui, pour graphe planaire donné, renvoie un graphe avec un planning valide de 5 minutes ou moins. 14. Oui Monsieur ça peut écrire un lapin. Faut pas croire que vous savez tout hein. 15. Le graphe est connexe et non-nul. 16. En r'tard, en r'tard J'ai rendez-vous que'que part Je n'ai pas le temps de dire au revoir Je suis en r'tard, en r'tard 4 Question 18 Écrivez une fonction qui, pour un graphe avec un planning donné, renvoie le nombre minimal de terriers nécessaires pour réaliser le SD dans un temps minimum. 6 Des coussins pour les sans-coussinets 17 Le SD est maintenant prêt. Encore faut-il le superviser... Chaque membre du GCL 18 a donné ses disponibilités : une heure d'arrivée et une heure de départ. Ils seront tous ensemble dans un terrier dédié avec un panneau Informations planté au-dessus. Un graphe d'intervalles est graphe où chaque sommet représente un intervalle de temps. Si deux intervalles de temps se chevauchent, alors ils sont reliés par une arête. Un cycle dans un graphe est un chemin en suivant les arêtes où l'on revient à son sommet de départ, sans passer plusieurs fois par le même sommet. La longueur d'un cycle est le nombre de sommets parcourus en suivant ce cycle. Une corde est une arête entre deux sommets non-adjacent d'un cycle (vous pouvez le voir comme un raccourci). Question 19 Montrez qu'un graphe d'intervalles ne peut pas avoir de cycle de 4 arêtes sans corde. Question 20 Écrivez une fonction qui, pour une liste donnée d'intervalles, renvoie le graphe d'intervalles associé. Question 21 Écrivez une fonction qui, pour un graphe donné, renvoie vrai si le graphe est un graphe d'intervalles. Question 22 (6 points) (3 points) Pour éviter qu'ils soient trop inconfortables, on prévoit des coussins moelleux. Vu que ce n'est pas facile de trouver des coussins en forêt, on aimerait en rassembler un minimum, mais que chaque lapin présent dans le terrier puisse se poser sur un quand il est présent. Écrivez une fonction qui, pour un graphe d'intervalles donné, renvoie le nombre minimal de coussins. 7 Bonus 19 Question bonus 1 Si le graphe est planaire et qu'on a un nombre illimité de terriers, quel est le temps maximal du SD? Question bonus 2 À quelle classe de problèmes, la durée minimale du SD appartient-elle? Question bonus 3 Montrez qu'un graphe d'intervalles ne peut pas avoir de triangle inscrit dans un hexagone. 17. Le dessous des pattes du lapin, à la diérence des chiens et des chats, est dépourvue de coussinet. La peau est en contact direct avec le sol, sa seul protection étant les poils qui la recouvre. 18. Grand Conseil des Lagomorphes 19. Ça devrait être boni mais le français est cruel envers les latinistes. 5 Question bonus 4 Listez les départements bretons ainsi que leurs préfectures et sous-préfectures. Question bonus 5 Traduisez le mot lapin dans un maximum de langues diérentes ( lièvre sera accepté). La traduction en breton aura un bonus spécial. Le sujet comporte 6 pages (sans compter la page de garde), 22 questions, et 5 questions bonus. Les questions normales sont notées sur 49 points, et les questions bonus rapportent au total 8 points, plus 1 point de présentation. 6
Related Search
Advertisements
Related Docs
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks