Commentaires sur le contenu de l'épreuve commune d'Informatique
du concours d'admission à l'Ecole polytechnique


L'épreuve consiste à vérifier la compréhension des notions fondamentales et élémentaires de l'algorithmique et de la programmation acquises dans le cadre du programme d'informatique commun aux classes préparatoires. On testera la précision de la pensée algorithmique et sa mise en oeuvre dans un noyau de langage isomorphe au noyau de tout langage de programmation moderne.

Le langage de programmation est laissé au choix parmi Maple, Mathematica ou l'un des langages suivants: Ada, Caml, C, C++, Java, Modula, Pascal, Ocaml. Si les détails de la syntaxe ne sont pas considérés comme importants, le langage support choisi sera précisé et on n'utilisera que les opérations de base, et non les fonctions puissantes de sa bibliothèque. Les seules fonctions graphiques autorisées permettront le tracé des segments entre deux points d'un repère cartésien du plan: MoveTo(x,y), LineTo(x,y), Line(dx,dy).

L'épreuve portera plus particulièrement sur les points suivants (présents dans la partie Algorithmes et Programmation des programmes actuels):

On se limitera a des raisonnements simples pour l'évalutation de la complexité des algorithmes: il s'agira d'être capable de compter le nombre d'opérations dans des boucles itératives. Il n'est pas question de faire des évaluations élaborées faisant intervenir la théorie de la complexité.

L'épreuve est principalement axée sur l'écriture de petits programmes (d'environ moins de 20 lignes) et l'apprentissage de la pensée algorithmique. On pourra faire référence aux algorithmes numériques utilisés dans les travaux pratiques ou les travaux dirigés de chimie, mathématiques, physique ou sciences industrielles, effectués dans les classes préparatoires. Le programme de l'épreuve ne contient aucune notion d'informatique théorique, comme la théorie des automates finis ou du calcul logique propositionnel. Les structures d'enregistrement (records) et les structures de données dynamiques (listes, arbres) ne sont pas au programme. De même, les algorithmes sur les graphes ne seront pas considérés. On veillera particulièrement à ne pas coder les structures de données dynamiques dans des tableaux, en remplaçant les références (ou pointeurs) par des indices dans ces tableaux.

Le programme de l'épreuve ne fait pas appel à des notions complexes d'algorithmique. Par exemple, la partie récursivité devra être bien différenciée de la méthode algorithmique ``Diviser pour Régner''. Il s'agit plus de montrer que les calculs par récurrence peuvent s'écrire avec des fonctions numériques récursives, ou que l'écriture récursive doit être utilisée quand elle est plus naturelle (par exemple dans la recherche dichotomique, ou dans la multiplication avec l'algorithme de Horner). Dans cette partie, aucune connaissance ne sera a priori exigée, mais les candidats devront être familiers avec l'existence de l'écriture récursive.

Comme point de repère, le programme de cette nouvelle épreuve correspond au cours de la semaine d'initiation à l'informatique, introduite à l'Ecole Polytechnique depuis 1999 (cf. http://www.enseignement.polytechnique.fr/informatique/Old/Init0/semaine0.html).

Les ouvrages suivants peuvent servir de base à la préparation d'un cours mais contiennenent pour la plupart infiniment plus que ce qui est demandé dans le cadre de cette épreuve.

[g]= culture générale; [d]= didactique; [r]= ouvrage de référence; [e]= exercices.

This document was translated from LATEX by HEVEA.