EPREUVE ORALE D‘INFORMATIQUE

ENS :  LYON

Durée : 45 minutes. Coefficient :  6.

MEMBRE DU JURY : E. THIERRY

6 candidats ont passé l’oral d’informatique. Le sujet est préparé par les candidats pendant 45 minutes. L’oral devant le jury est également de 45 minutes : tout d’abord le candidat présente les résultats de ses 45 minutes de préparation, puis avance dans le sujet, cette réflexion étant guidée par l’examinateur.

Deux sujets ont été donnés : l'un sur le tri topologique des graphes et ses applications à l'ordonnancement, l'autre sur la structure d'arbre binaire de recherche et sur les questions de stockage de données. Ces thèmes sont par exemple présentés dans le livre « Introduction à l'algorithmique » de Cormen, Leiserson et Rivest. Il s’agissait de manipuler des structures de données de type tableau ou arbre, de s'interroger sur les complexités des algorithmes et éventuellement de faire une ou deux preuves mathématiques. Les énoncés étaient longs, les candidats n'ont en général préparé que les premières questions, mais les questions suivantes ont servi à guider le reste de l'épreuve orale.

Les attentes techniques portaient sur :
•	les structures de données : tableau bi-dimensionnel ou arbre,
•	les structures de contrôle : test bien sûr, itération et récursion,
•	la complexité : savoir établir la complexité de l’algorithme proposé.
•	les preuves de correction : savoir prouver que l'algorithme est juste, en particulier en sachant prouver des petits résultats sur les objets combinatoires manipulés, avec par exemple des preuves par récurrence.

Les sujets commençaient par une petite question nécessitant la rédaction d'un court programme, pour vérifier si les candidats pouvaient écrire un petit programme correct. C'était une condition nécessaire pour obtenir la moyenne. Le langage de programmation était laissé au libre choix du candidat, en particulier l'écriture d'algorithmes en pseudo-code était autorisée. On notera qu'il est préférable d'avoir un candidat écrivant en pseudo-code, plutôt qu'une tentative dans un langage dont le candidat connaît mal la syntaxe. 

On attendait ensuite des candidats qu'ils aient compris la problèmatique de l'énoncé et les structures manipulées, en particulier en pouvant répondre à la main aux questions sur de petits exemples.  Les questions principales consistaient ensuite à rédiger des algorithmes pour résoudre le problème général en suivant une méthode proposée par l'énoncé, à être capable d'évaluer leurs complexités et éventuellement à prouver leur justesse en démontrant de petits théorèmes. Tous ces points donnaient l'occasion de discuter avec l'examinateur sur ces différentes notions et éventuellement de s'interroger sur les possibilités d'amélioration. Concernant les petites preuves de théorèmes guidées par l'énoncé, on notera que la mise en place de raisonnements par récurrence (ou induction) n'a pas toujours été évidente pour les candidats. Les dernières questions de l'énoncé revenaient sur la problématique générale soit en proposant au candidat d'imaginer d'autres solutions au problème que celle présentée dans l'énoncé, soit en s'interrogeant sur des variantes du problème (à savoir est-ce qu'on peut adapter les solutions déjà présentée ou pas, etc.). C'était une occasion supplémentaire de mettre en valeur l'imagination ou les connaissances des candidats.