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

Énoncé(s) donné(s)

Type A

Un langage est dit décidable s'il existe un acepteur, c'est-à-dire une fonction qui prend un argument un mot et renvoie vrai si le mot appartient au langage et faux sinon.

1) Montrer qu'un langage fini est décidable.

2) Montrer qu'un langage régulier est décidable.

3) Montrer que le complémentaire d'un langage décidable est décidable, montrer que l'union, l'intersection et la concaténation de deux langages décidables est décidable.

On suppose qu'il existe une fonction arret qui résoud le problème de l'arrêt.

On considère les fonctions suivantes : 
auto_arret u = arret u u
paradoxe u = 
    if not auto_arret u then true
    else while true

4) Expliquer ce que font ces deux fonctions.

5) Montrer qu'une telle fonction arret n'existe pas.

6) Existe t-il une fonction eval_bis qui renvoie faux si le code ne termine pas et le résultat de l'éxécution sinon ?

7) Montrer qu'il existe des langages non décidables.

8) Une union dénombrable de langages décidables est-elle décidable ?

Type B

On s'intéresse au problème d'afficher un texte sur un un écran avec un nombre de caractère maximal par ligne sans couper de mot.

Un texte est un tableau de mot, un découpage est une liste de couples, le premier élement du premier couple d'un découpage est l'indice du premier mot sur la première ligne et le deuxième élément du premier couple est l'indice du dernier mot sur la première ligne etc.

On introduit le découpage trivial qui consiste à mettre un mot par ligne.

1)  On suppose que ce découpage existe, programmer une fonction qui étant donné un texte renvoie le découpage trivial.

2) Déterminer une condition pour l'existence de ce découpage.

3) Programmer une fonction qui pour un texte renvoie vrai si le découpage existe et faux sinon.

4) Ajouter des tests au jeu de test déjà présent et tester la fonction.

On donne une fonction mystère qui résoud le problème du découpage

5) Expliquer le fonctionnement de la fonction, quelle méthode algorithmique utilise t-elle ?

 

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

Type A) 8) : Penser au langage réduit à un seul mot. 

Commentaires divers

Type A : Les propriétes que doit avoir la fonction arrêt étaient explicitées. Les fonctions auto_arret et paradoxe étaient dans une syntaxe OCaml correcte.

Type B: Plusieurs exemples étaient données, de même qu'une fonction affiche qui étant donné un découpage, l'affiche. Il manque évidemment des questions, il y'avait ensuite une relation de récurrence qu'il fallait coder puis démontrer, on introduisait aussi une métrique déterminant si le découpage était "beau".