Réussir Prologin

Par haveo, le dimanche 25 octobre 2009, à 17:17 | Catégorie : | Mots-clés : prologin, requin et algorithmique | Source

Vous êtes un jeune, intéressé par l’informatique et vous venez de découvrir l’existence d’un concours portant sur votre activité préférée, Prologin. Plutôt sûr de vous-même vous décidez de tenter votre chance. Mais bientôt, vous commencez à douter ; mais sur quoi peut bien porter ce concours ? Vous parcourez le site officiel à la recherche de renseignements, mais vous n’êtes pas satisfait. À force d’acharnement, de contacts un peu louches et de recherches Google douteuses vous arrivez sur un billet apparemment peu digne de confiance qui prétend exposer les connaissances requises pour Prologin.

* <----- vous êtes ici

Comme vous le savez sûrement, le concours Prologin se déroule en trois temps : qualification, demi-finale et finale. Il se trouve que la qualification est tellement facile qu’elle est à la portée de tout un chacun. La finale quand à elle est tellement spéciale que la seule préparation efficace à une finale est … une autre finale. Lors de votre première vous ferez probablement n’importe quoi, de préférence en vous amusant et vous vous en contenterez.

Gardez à l’esprit que ce billet n’est qu’un modeste résumé des compétences que prologin requiert et en aucun cas une référence exhaustive sur le sujet.

Rédaction

Premièrement, apprenez à présenter. Plus votre copie sera agréable à lire moins le correcteur prendra de temps pour la lire. Le correcteur est un bénévole, il corrige les copies parce que c’est un mal nécessaire et probablement pas pour le plaisir. Moins il passera de temps à tenter de déchiffrer ce que vous avez écrit plus il sera content. Un code indenté, aéré, coloré et une écriture lisible seront toujours récompensés.

Deuxièmement, accompagnez votre code d’explications claires et concises. Le correcteur n’est pas là pour le plaisir de déchiffrer des codes obscurs. Vous ne risquez donc pas de lui gacher le plaisir en lui expliquant comment votre algorithme fonctionne, au contraire.

Un dicton de programmeur dit : Keep It Simple, Stupid (KISS). Dans la mesure du possible, vous devriez chercher la solution la plus simple. C’est celle qui a le plus de chance d’être juste et en plus les correcteurs la comprendront aisément. Si toutefois vous séchez n’hésitez pas à écrire ce à quoi vous avez pensé. Même si votre algorithme est un peu alambiqué, qu’il ne marche pas tout le temps ou qu’il ne vous satisfait pas en matière d’efficacité n’hésitez pas à montrer au correcteur que vous avez fait l’effort de chercher. Qui sait, peut-être que vous n’étiez pas si loin de la solution ?

Algorithmique

Lorsqu’on conçoit des algorithmes, on est tout particulièrement intéressé par leur efficacité (à plusieurs points de vue) algorithmes, par exemple le temps qu’ils mettent à s’executer.

Ce qu’on nomme complexité d’un algorithme est la quantité de ressources (temps ou mémoire principalement) consommée en fonction de la taille de l’entrée. On utilise généralement des notations appelées de Landau pour obtenir un aperçu du comportement pour de grandes entrées (on parlera de comportement asymptotique) de cette consommation. Ces notions sont abordées et expliquées en détail dans le tutoriel "L’algorithmique pour l’apprenti programmeur" (suivez le lien).

Une structure prépondérante en informatique est celle de graphe. On peut se représenter un graphe par un ensemble de points (qu’on appelle en fait noeuds) reliés par des traits (qu’on appelle en fait arrêtes). Tous les problèmes où vous aurez affaire à un ensemble d’éléments reliés les uns aux autres parlent en fait de graphes. On a fréquemment besoin de chercher un élément dans un graphe. On utilise pour cela des algorithmes de parcours de graphe comme BFS ou DFS. Le tutoriel précédemment cité traite aussi de manière assez intéressante ce sujet, ici par exemple.

Mais puisque toutes les questions ne portent pas sur les graphes (heureusement) introduisons maintenant une autre technique, plus universelle : la programmation dynamique. L’idée est très simple, on conçoit un algorithme qui appelle une fonction récursive, pour optimiser cet algorithme on enregistre les résultats des appels dans une structure de données à temps d’accès constant de sorte que si l’algorithme en vient à appeler deux fois la fonction avec les mêmes valeurs il ne recalcule rien.

Une application basique de ceci est le calcul des nombres de Fibonacci. On définit ,F_0 = 0 et F_1 = 1 et F_(n+2) = F_(n+1) + F_n. Si on utilise un algorithme récursif classique on peut montrer que le calcul a une complexité exponentielle, c’est pas terrible. En fait cela est du au fait que certains nombres de Fibonacci sont calculés plusieurs fois. Par exemple, pour calculer F4 on calcule F3 et F2 puis pour calculer F3 on calcule F2 et F1. On a calculé F2 au moins deux fois. En utilisant la programmation dynamique on garantit que chaque nombre n’est calculé qu’une fois et on peut donc montrer que l’algorithme a une complexité linéaire. Un programme qui était trop lent est devenu assez rapide.

Une remarque assez importante, puisqu’on utilise une matrice pour accéder aux résultats (ou à l’absence de résultats) de l’appel de la fonction avec des paramètres donnés, ces paramètres doivent être entiers pour pouvoir garantir un accès en temps constant et une occupation mémoire décente. Si vous voulez utiliser la programmation dynamique avec des chaines de caractère, des listes ou je ne sais quoi de différent d’un entier (ou pire, si vous voulez les convertir en entier), vous vous trompez. Toute la difficulté d’un certain nombre de problèmes est justement de se ramener à des paramètres entiers biens trouvés pour réduire le nombre de situations différentes.

Exemple : Le problème du sac à dos, version facile. Soit n objets différents disponibles à volonté de poids pi entier. On a un sac à dos qui peut contenir un poids P, quel est le poids maximum qu’on peut y mettre à l’aide de nos n objets.

Solution : Ici, on remarque que le problème peut se ramener à résoudre le problème dans le cas où on commence par mettre l’objet 1, puis dans celui où on commence par mettre l’objet 2, etc. Il suffira de prendre le maximum de ces sous-cas qui couvrent bien tout l’éventail des possibilités. L’astuce consiste à voir que deux sous-problèmes ont la même réponse si le poids des objets qu’on considère comme étant de toute façon dans le sac est le même dans les deux cas. Ainsi si on considère le sous-problème où on commence par rentrer 1 puis 2 et celui où on commence par rentrer 3 puis 4, il suffit que p1 + p2 = p3 + p4 pour que ces deux problèmes aient la même réponse. Le paramètre de notre fonction récursive sera donc la poids cumulé des objets imposés a priori. On commencera par appeler la fonction avec ce paramètre valant zéro. L’algorithme en lui-même est laissé en exercice au lecteur.

Ce sujet n’est malheureusement pas traité par "L’algorithmique pour l’apprenti programmeur" (peut-être cela viendra un jour) ainsi je vous recommande de vous tourner vers des ouvrages certes un peu moins abordables mais bien plus complets comme l’excellente "Introduction à l’algorithmique".

Bien qu’il soit primordial de posséder un certain nombre de bases, il est tout aussi important de savoir ce que vous ne devez pas savoir. Les algorithmes avancés de pathfinding dont vous pourriez avoir entendu parler (Djikstra, A*) ne vous seront d’aucune utilité de par la complexité de leur implémentation (qui utilise par exemple des files de priorité dont l’implémentation optimale est tout sauf triviale). Ne pensez même pas à les utiliser, rabattez-vous sur DFS et BFS.

Je tiens également à vous prévenir de quelques questions classiques des sujets d’écrit. La première question qui vous sera posée est presque toujours la même, "Quelle structure de donnée allez-vous utiliser pour stocker blah ?". Généralement les structures qu’on vous demande sont simples. C’est la première question on n’allait pas vous demander des structures exotiques. Une autre question "piège" c’est l’évaluation du temps d’execution de votre algorithme. Vous venez de calculer la complexité de votre algorithme (O( n2 ), par exemple) et on vous donne les paramètres (donc n) et les spécifications d’une machine notamment (ce qui est le plus important) sa fréquence d’horloge, par exemple 500 MHz (c’est-à-dire 500 x 106 instructions par seconde). Il suffit donc de diviser le nombre d’instructions que vous avez à calculer (n2 dans ce cas là, il y a des constantes cachées mais on ne vous demande qu’une estimation) par le nombre d’instructions executées par secondes.

Un petit résumé des ressources qui vous permettront d’approfondir le sujet :

Programmation

Il vous faudra aussi être au point niveau programmation et connaissance de votre langage.

On va vous fournir des codes pour gérer les entrées-sorties. Parfois ils marcheront. Parfois non. Vous feriez donc mieux de connaitre les primitives d’entrée-sortie de votre langage, au cas où.

De manière plus générale, il est indispensable de s’exercer à la pratique de son langage pour pouvoir d’une part éviter de faire trop d’erreurs (qui peuvent faire perdre un peu de temps si ce sont des erreurs de syntaxe voire beaucoup si elles sont plus subtiles) et d’autre part les corriger pus rapidement. N’hésitez pas à demander de l’aide (à des amis, sur des forums ou bien encore sur IRC) si vous ne comprenez pas une erreur, vous aurez bien moins d’aide à disposition le jour J !

Là encore je vous conseille de traiter les exercices de Prologin.org et France-IOI.org.

Bonne chance !