Les candidats devront indiquer clairement en tête de copie le langage de programmation choisi (Pascal ou Caml). Les fonctions et procédures demandées seront rédigées dans ce langage.

Un groupe de

chasseurs de fantômes combat un groupe de

fantômes. Chaque chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de rayon. Un rayon se propage en ligne droite et termine sa course en touchant le fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire d'éliminer tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre initial de

fantômes; il est très dangereux que deux rayons se croisent, cela ne doit donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse, dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont possibles que sur un rebord confondu avec la circonférence, mais les tirs se font entre deux points de la circonférence, selon des cordes du cercle.
I.A - Les

protagonistes sont représentés par des points distincts

répartis dans l'ordre des indices croissants sur la circonférence d'un cercle parcouru dans le sens trigonométrique;

sont des chasseurs,

des fantômes, mais, dans cette section I.A, on cherche les liens possibles entre les

sans s'occuper de qui est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par une corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il faut donc respecter les deux conditions :
i) chaque point est une extrémité d'une et une seule corde,
ii) les différentes cordes ne doivent pas se couper.

Dans toute la suite on fixe un entier

et on appelle stratégie de taille

un vecteur (

), tel que pour tout entier

vérifiant

on ait:

Cette notation exprime bien le lien entre les points

lorsque

En Pascal, on représente le vecteur par un tableau avec un type Vecteur défini par:
Const

; {de taille suffisante pour tout le problème}
Type Vecteur = array [1..Nmax] of integer;
En Caml, on représente le vecteur avec le type «vecteur» de Caml. On peut utiliser la fonction make_vect. Les éléments des vecteurs en Caml sont numérotés de 0 à

. On prendra des vecteurs de taille

, dont le premier élément ne sera pas utilisé, pour que les points soient bien aux indices 1 à

dans le vecteur Caml.
On considère des stratégies où les points d'une paire sont reliés par des segments de droites situés dans un même plan. Une stratégie est dite «admissible» si les segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend pas de la position des points sur la circonférence mais seulement de la stratégie.

Par exemple, pour les stratégies de taille

ci-contre:

La figure de gauche correspond à

qui est donc admissible, et celle de droite à

qui, elle, ne l'est pas.

1	2	3	4	5	6	7	8
2	1	6	5	4	3	8	7
2	1	7	5	4	8	3	6

I.A.1) Dans le cas

, donner le nombre de stratégies possibles, admissibles ou non.
I.A.2) Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les représenter sur une figure.
I.A.3) Déterminer le nombre de stratégies de taille

entier positif (qu'elles soient ou non admissibles).
I.B - Soit

quatre entiers distincts tels que :

.
I.B.1) Donner une condition nécessaire et suffisante, portant uniquement sur ces entiers, pour que les segments

se croisent.
I.B.2) Écrire une fonction «croise» prenant les quatre entiers pour paramètres et renvoyant un booléen dont le résultat est true si et seulement si les segments

se croisent. On suppose que les paramètres donnés à la fonction satisfont les conditions données en introduction du I.B.
I.B.3) En utilisant la fonction croise, écrire une fonction «estAdmissible» qui prend en paramètre le vecteur (et en Pascal, le nombre

de chasseurs) et renvoie un booléen dont le résultat est true si la stratégie est admissible.
I.B.4) Donner, en la justifiant, la complexité de cette méthode, en terme de temps de calcul (on se contentera d'une évaluation du type

, en précisant la valeur de

).
I.C - On souhaite tester la stratégie de façon plus efficace. Pour cela on utilise une fonction «evalue» qui prend deux entiers

comme paramètres (

étant compris entre 1 et

) et dont le résultat est true si et seulement si les deux propositions suivantes sont vraies :

les segments ayant leurs extrémités dans l'arc (fermé) ne se croisent pas. I.C.1) Donner la valeur de evalue(i, j) dans les trois cas particuliers et suivants :
а) ;
b) et ;
c) et .
I.C.2) Pour , montrer que evalue(i, j) se déduit de evalue(i +1 , et de evalue ( ).
I.C.3) Écrire une fonction testStrategie qui prend en paramètre un vecteur (et en Pascal le nombre de chasseurs) et renvoie un booléen dont la valeur est true si la stratégie est admissible. Cette fonction devra être de complexité .
I.C.4) Démontrer avec soin que la fonction testStrategie est bien de complexité .
I.D - La méthode précédente teste si une stratégie est admissible. On souhaite maintenant, le statut (chasseur ou fantôme) des points étant donné, déterminer directement une stratégie admissible, de façon également efficace.
I.D.1) Montrer que si est un chasseur ( ), alors il existe , avec tel que est un fantôme et tel que le nombre de chasseurs soit égal au nombre de fantômes de chaque côté de l'axe .
I.D.2) En déduire un algorithme simple pour construire une stratégie admissible.
I.D.3) On se propose d'évaluer la complexité de cette méthode.
a) Déterminer la complexité dans le pire des cas.
b) Évaluer, sans démonstration, la complexité moyenne.
I.D.4) Un vecteur contient la nature des points pour un chasseur, pour un fantôme . On a donc puisqu'il y a autant de fantômes que de chasseurs. Écrire une fonction cibles, qui prend en paramètre le vecteur (et en Pascal, le nombre de chasseurs) et qui renvoie la liste des indices des couples ( ) (où est un chasseur et un fantôme), composant une stratégie admissible du problème.

Partie II - Automates finis

On rappelle que les sections II.A, II.B, II.C sont indépendantes et peuvent être traitées dans un ordre quelconque.

Définitions et notations

Un automate (sous entendu fini) déterministe est un quintuplet

avec:

l'ensemble fini non vide des états;
A l'alphabet c'est-à-dire l'ensemble fini non vide des lettres;
l'état initial;
la fonction de transition (éventuellement partielle);
l'ensemble des états terminaux.

Lorsque

est défini sur l'ensemble

tout entier, on parle d'automate fini complet. Que l'automate soit complet, ou non, on peut choisir de représenter les transitions non par une fonction de transition

, mais par un ensemble de transitions

(le graphe de

), avec la condition de déterminisme :
(D)

, alors

Un automate (fini) non déterministe est un quintuplet

avec cette fois

l'ensemble des états initiaux et

la fonction de transition : si

désigne l'ensemble (éventuellement vide) des

tels qu'il existe une transition étiquetée par

vers

. Si on choisit de représenter les transitions par un ensemble inclus dans

, la condition

n'a plus à être vérifiée.
Pour présenter un automate, les candidats pourront, bien entendu, les représenter par un schéma. Ils veilleront alors à bien identifier l'état initial (ou les états initiaux) et les états terminaux par une notation adaptée.

On note

l'ensemble des mots écrits dans l'alphabet

(y compris le mot vide). Un langage sur l'alphabet

est un sous-ensemble de

. On note en particulier

le langage de

, c'est-à-dire l'ensemble des mots acceptés par

(permettant de passer d'un état initial à un état terminal).
Étant donné un mot

, on note

la longueur de

, c'est-à-dire le nombre de ses lettres.

II.A - Mots répétés

II.A.1) Soit

un alphabet. On s'intéresse au langage

constitué des mots

qui ne sont de la forme

(c'est-à-dire

) pour aucun

a) On suppose que

est réduit à une lettre.

Montrer alors que

est reconnaissable par automate fini et donner un automate reconnaissant effectivement

, ainsi qu'une expression rationnelle décrivant

.
b) On suppose maintenant que

n'est pas réduit à une lettre. Montrer que

n'est pas reconnaissable.
c) Soit

un entier strictement plus grand que 2 . Reprendre les deux questions précédentes en remplaçant

par

défini par:

II.B - Logique de Presburger

Soit

un entier strictement positif et

. On prend comme alphabet l'ensemble

. Un mot

représente le

-uplet d'entiers naturels (

) tel que

a) Donner une représentation des

-uplets suivants :
(4);
(2,3,0);

On appelle relation dans

tout sous-ensemble de

.
On dit qu'une relation

est rationnelle, lorsqu'il existe un automate fini

qui reconnaît exactement l'ensemble des mots de (

)* représentant les

-uplets de

Pour les deux questions b) et c) suivantes, on demande de donner, pour chacune des relations Eg, Inf et Add, un automate fini la reconnaissant effectivement.
b) Montrer que les relations :

sont rationnelles.
c) Montrer que la relation :

est rationnelle.
d) On suppose la relation

rationnelle et on définit les relations

par :

si, et seulement si, il existe

tel que

si, et seulement si, pour tout

.
Montrer que les relations

sont rationnelles.

II.C - Automate minimal

Soit

. Pour chaque entier

, on définit les langages

de la manière suivante :

.
.
II.C.1) Donner un automate déterministe complet, à états reconnaissant .
II.C.2) Donner un automate non-déterministe, à états reconnaissant .
II.C.3) Démontrer qu'il n'existe pas d'automate déterministe complet reconnaissant et possédant strictement moins de états.

On pourra raisonner par l'absurde et prouver que les états atteints en lisant depuis l'état initial sont distincts, pour certaines valeurs .

II.C.4) Déterminiser l'automate proposé dans la question C.2), lorsque

.
II.C.5) Démontrer qu'il n'existe pas d'automate déterministe complet reconnaissant

et possédant strictement moins de

états.
II.C.6) Démontrer qu'il n'existe pas d'automate fini (non-déterministe) reconnaissant

et possédant strictement moins de

états. Même question pour le langage