Tout sur les oraux en informatique aux concours des écoles d'ingénieurs

Voici quelques exemples de questions posées en orale d’informatique aux concours des écoles d’ingénieurs.

Exercice 1. Dans cet exercice, on autorise les doublons dans un arbre binaire de recherche et pour le cas d’égalité, on choisira le sous-arbre gauche. On ne cherchera pas à équilibrer les arbres.

1. Rappeler la définition d’un arbre binaire de recherche.
2. Insérer successivement et une à une dans un arbre binaire de recherche initialement vide toutes les lettres du mot bacddabdbae, en utilisant l’ordre alphabétique sur les lettres. Quelle est la hauteur de l’arbre ainsi obtenu ?
3. Montrer que le parcours en profondeur infixe d’un arbre binaire de recherche de lettres est un mot dont les lettres sont rangées dans l’ordre croissant. On pourra procéder par induction structurelle.
4. Proposer un algorithme qui permet de compter le nombre d’occurrences d’une lettre dans un arbre binaire de recherche de lettres. Quelle est sa complexité ?
5. On souhaite supprimer une occurrence d’une lettre donnée d’un arbre binaire de recherche de lettres. Expliquer le principe d’un algorithme permettant de résoudre ce problème et le mettre en œuvre sur l’arbre obtenu à la question 2 en supprimant successivement une occurrence des lettres e, b, b, c et d. Quelle en est la complexité ?

Lire aussi : Programme commun d’informatique en prépa scientifique.

Exercice 2. On considère le programme suivant, ici en OCaml, dans lequel n fils d’exécution incrémentent tous un même compteur partagé.

(* Nombre de fils d’exécution *)

let n = 100

(* Un même compteur partagé *)

let compteur = ref 0

(* Chaque fil d’exécution de numéro i va incrémenter le compteur *)

let f i = compteur := !compteur + 1

(* Création de n fils exécutant f associant à chaque fil son numéro *)

let threads = Array.init n (fun i => Thread.create f i)

(* Attente de la fin des n fils d’ex ́ecution *)

let () = Array.iter (fun t => Thread.joint) threads

On rappelle que l’on dispose en OCaml des trois fonctions Mutex.create : unit -> Mutex.t pour la création d’un verrou, Mutex.lock : Mutex.t -> unit pour le verrouillage et pour le déverrouillage, du module Mutex pour manipuler des verrous.

1. Quelles sont les valeurs possibles que peut prendre le compteur à la fin de ce programme ? 
2. Identifier la section critique et indiquer comment et à quel endroit ajouter des verrous pour garantir que la valeur du compteur à la fin du programme soit n de manière certaine.

Dans la suite de l’exercice, on suppose que l’on ne dispose pas d’une implémentation des verrous. On se limite au cas de deux fils d’exécution, numérotés 0 et 1. Nous cherchons à garantir deux propriétés :

• Exclusion mutuelle : un seul fil d’exécution à la fois ne peut se trouver dans la section critique
• Absence de famine : tout fil d’exécution qui cherche à rentrer dans la section critique pourra le faire à un moment.

On utilise pour cela un tableau veut_entrer qui indique pour chaque fil d’exécution s’il souhaite entrer en section critique ainsi qu’une variable tour qui indique quel fil d’exécution peut effectivement entrer dans la section critique. On propose ci-dessous deux versions modifiées f_a et f_b de la fonction f , l’objectif étant de pouvoir exécuter f_a 0 et de f_a 1 manière concurrente, et de même pour f_b .

let veut entrer = [| false ; false |]

let tour = ref 0

let f_a i=

let autre = 1 = i in

veut_entrer . ( i ) <= t r u e ;

while veut_entrer.(autre) do () done;

(* section critique *)

veut_entrer.(i) <= false

let f_b i =

let autre = 1 = i in

veut_entre . ( i ) <= t r u e ; tour := i ;

while veut_entrer.(autre) && !tour = autre do () done ;

(* section critique *)

veut_entrer.(i) <= false

3. Expliquer pourquoi aucune de ces deux versions ne convient, en indiquant la propriété qui est violée.

4. Proposer une version f_c qui permet de garantir les deux propriétés. Il s’agit de l’algorithme de Peterson.

5. Connaissez-vous un algorithme permettant de généraliser à n fils d’exécution ? Rappeler très succinctement son principe.

N’hésitez pas à consulter les annales des concours des écoles d’ingénieurs que vous visez pour une préparation plus adéquate à l’oral d’informatique.

Lire aussi : Attentes des jurys de concours en prépa scientifique en informatique.