Base d'épreuves orales scientifiques de concours aux grandes écoles

Énoncé(s) donné(s)

Exercice 1 :

1. Définir un arbre binaire de recherche.

2. Expliquer comment insérer un élément dans un arbre binaire de recherche.

3. Montrer que l'ensemble des arbre binaires de recherche à n éléments dont les étiquettes sont les entiers de 1 à n a un cardinal de $\frac{1}{n+1} \binom{2n}{n}$.

4. Etant donné un arbre binaire de recherche, proposer un algorithme qui renvoie les étiquettes ordonnées.

5. Quelle est la hauteur maximale et minimale d'un arbre binaire de recherche qui possède n éléments ?

6. Comment insérer une liste triée dans un arbre binaire de recherche initialement vide pour obtenir un arbre binaire de recherche équilibré ?

Exercice 2 :

On considère des graphes non orientés. A chaque sommet du graphe on associe une couleur, l'opération de recoloriage d'un sommet consiste à changer la couleur du sommet et celle de chaque sommet accessible depuis le sommet recolorié par des sommets de la même couleur (le sommet lui même doit être de la même couleur). Un graphe est alors dit inondé lorsque tout ses sommets sont de la même couleur.

1. (Un graphe exemple était proposé) Proposer une suite de recoloriages permettant d'inonder le graphe exemple.

2. Qu'est ce qu'on peut appeler un recoloriage inutile ? 

3. Réduire le problème d'inondation du graphe à un problème d'inondation d'un graphe avec moins de sommets que le graphe initial.

4. On se place dans un graphe possédant un cycle et où deux sommets adjacents ont une couleur différente. Majorer et minorer le nombre de recoloriage nécessaire pour inonder ce graphe.

5. Proposer un algorithme (glouton) pour inonder un graphe. Quelle est sa complexité temporelle ?

Il y'avait des questions 6 et 7 consistant à établir des résultats sur un algorithme d'approximation proposé pour ce problème.

Indication(s) fournie(s) par l'examinateur pendant l'épreuve

Commentaires divers