S6 : Informatique au concours

Petit recueil de ce qui peut/est déjà tombé au concours.

Oraux Concours Commun INP

Pas forcément un concours que vous passez, mais peut valoir le coup de regarder puisqu'il y a aussi des corrigés :

https://www.concours-commun-inp.fr/fr/epreuves/les-epreuves-orales.html

QCM GEI

Remarques générales

Au fil des années, les QCM changent de format : moins de C et plus de python. Depuis 2024 il y a même du pseudo-code pour les questions algorithmiques.

Lisez attentivement chaque question. Il y a de temps en temps des typos, des indentations fantaisistes, des incohérences. Prenez ça comme une feature et non un bug : elles sont là pour voir votre intuition/compréhension informatique. Arriver à comprendre l'esprit de la question, prenez de la hauteur.

Méthode de résolution

Pour gérer un QCM il y a trois approches qui fonctionnent, par ordre de rapidité :

1. Connaissance. Vous reconnaissez l'algorithme, la notion : vous répondez directement la bonne réponse. Attention cependant à ne pas aller trop vite, il peut y avoir plusieurs réponses correctes et on est pas à l'abris d'un piège (il y en a...)
2. Élimination. On procède par élimination en supprimant itérativement les réponses incorrectes.
3. Bourrinage. Pour les questions algorithmiques, déroulez un exemple simple pour voir comment fonctionne l'algorithme et ce qu'il rend.

Programme

De la L1, L2 et L3 et un peu de hors programme.

Algorithmie

Tout le cours de L1 semble plus ou moins être au programme, ce qui correspond à la partie I du cours d'algorithmie :

En particulier :

• pseudocode
• tris
• complexité min, max et en moyenne ; différence entre complexité en temps et en espace
• pile/file

Il faut aussi connaître quelques algorithmes que GEI semble adorer :

• algorithme d'Euclide de calcul du PGCD.
• Bezout aussi appelé Euclide étendu (je crois). Nombre premiers.
• suite de Fibonacci
• la puissance $x^y$
• addition et soustraction binaire (c'est le même algorithme en complément à 2)
• suite de Syracuse
• méthode de chiffrement de César

Python

Questions souvent basique ou en lien avec un problème d'algorithmie. Relisez et comprenez la partie Base de la programmation du cours coder et développer :

Java

Le java n'est pas enseigné en MPCI, mais est présent au concours, en particulier pour le QCM de GIE.

Sarah a effectué un stage sous ma direction visant à apprendre le java et à donner des liens nécessaires aux MPCI pour qu'ils puissent eux aussi l'apprendre. Consultez son rapport pour vous permettre de bien vous préparer :

En particulier faite attention aux mots clés suivant qui peuvent induire des pièges un peu retors :

• extends
• public et static
• self

C

Il ne reste presque plus de C, remplacé par du python dans les derniers QCM.

Je ne sais pas si c'est utile de réviser pour le peu de questions qu'il y a, mais vous pouvez toujours jeter un œil à la partie C du cours système et réseau :

Graphes

Quelques notions sur les Graphes et les arbres. Relisez le début du cours de graphe :

En particulier :

• ordre et taille d'un graphe
• degré d'un sommet et d'un graphe
• graphes Eulérien et Hamiltonien
• graphe complet et connexe
• cycles et chemins
• arbre et forêt, ainsi que les définitions alternatives d'un arbre

Quelques algorithmes ont aussi à connaître :

• parcours en largeur/profondeur d'un graphe
• Dijkstra et son lien avec un parcours en largeur
• problème du voyageur de commerce
• coloration de graphe, en particulier l'algorithme glouton de Welsch et Powell (celui du cours)

X/ENS

Centrale

Le programme est gigantesque et regroupe tous les programmes de toutes les licences d'informatique (ainsi que de leurs options) de toute la France... Que vous n'ayez pas tout fait est normal !

Ne prenez pas peur : vous allez être interrogé sur une intersection entre votre programme MPCI et leur programme.

Donc :

1. lisez le programme en entier
2. faite l'intersection de ce que vous avez vu et le reste
3. révisez l'intersection commune
4. faire un check Wikipedia rapide sur les notions que vous n'avez pas vu, histoire de ne pas mourir idiot et de ne pas passer pour un inculte auprès de l'examinateur mais pas plus.

Oraux/écrit Algorithmie

Vous pouvez tomber sur le même exercices aux mines ou à l'X/ENS. Ce qui changera c'est les indications et le nombre de questions intermédiaires. Mais en gros tout peut tomber, c'est pourquoi faire les QCM GEI est un bon exercice pour bien asseoir les bases qui vous seront nécessaires pour résoudre les problèmes plus dur..

Préparez vous en reprenant les cours et en comprenant les démonstrations. Ce sont souvent les mêmes chemins qui sont pris. On ne peut pas vous demander de trouver des preuves digne du book ou la méga astuce algorithmique, mais vous devez montrer que vous connaissez votre sujet, connaissez les trucs de bases et que vous avez un peu d'intuition (ce qui se travaille en cherchant les ressemblances entre les différentes techniques de preuve).

TBD exercices oraux blanc

• enveloppe convexe
• variations et calcul sur 3-SUM
• sac à dos en programmation dynamique
• graphes bi-parti
• algorithme du lièvre et de la tortue pour :
  • détecter des cycles
  • trouver des doublons dans un tableau d'entiers ($n$ entiers dont les valeurs vont de $1$ à $n-1$) en $\mathcal{O}(n)$ opérations et $\mathcal{O}(1)$ en mémoire (cf. https://medium.com/@simrangarg0501/finding-the-duplicate-number-using-floyds-tortoise-and-hare-algorithm-618ced80e98e)