% category
% tags prologin, requin, algorithmique
% authors haveo
% date 1256487475.0
% title Réussir Prologin
% formatter mdown

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`

%endchapo
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](http://www.siteduzero.com/tutoriel-3-51767-la-notion-de-complexite.html)).

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](http://www.siteduzero.com/tutoriel-3-117382-arbres.html) 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 F_4 on calcule F_3 et F_2
puis pour calculer F_3 on calcule F_2 et F_1. On a calculé F_2 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 p_i 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 p_1 \+ p_2 =
p_3 \+ p_4 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( n^2 ), 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 10^6 instructions par seconde). Il
suffit donc de diviser le nombre d'instructions que vous avez à
calculer (n^2 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 : 

- ["L'algorithmique pour l'apprenti
  programmeur"](http://www.siteduzero.com/
  tutoriel-3-51781-algorithmique-pour-l-apprenti-programmeur.html),
  tutoriel traitant de manière pédagogique mais malheureusement
  incomplète des bases de l'algorithmique.
- "Introduction à l'algorithmique" de T.H. Cormen, ouvrage de
  référence sur le sujet mais peut-être un peu trop touffu pour un
  débutant.
- Prologin.org et France-IOI.org, deux sites proposant des exercices
  pour mettre ces notions en pratique.

= 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 !