Dans la mythologie Grecque, l'accès aux Enfers est gardé par le Cerbère, un terrible loup à trois têtes. Celui-ci se trouve devant trois couloirs qui, soit permettent de rejoindre le monde des vivants, soit conduisent directement aux Enfers.

Lorsque Cerbère accueille un nouvel arrivant, il est contraint de lui dire la vérité. Par la suite, il peut mentir ou dire la vérité à sa guise mais il respecte toujours les règles qu'il s'est fixées.

Après avoir bu la coupe de cigué, Socrate se retrouve face à Cerbère. Celui-ci, honoré de rencontrer le grand philosophe, veut lui offrir une chance d'éviter la damnation éternelle. Il lui dit alors : « Je vais t'indiquer un des couloirs qui mène au monde des vivants mais, pour mettre à l'épreuve ta grande sagesse, j'énoncerai trois indications logiques qui seront, soit toutes vraies, soit toutes fausses et tu en déduiras le couloir que tu devras suivre

Nous noterons

les propositions associées aux indications de la première, la deuxième et la troisième tête du Cerbère.

Question I. 1 Représenter l'énoncé de Cerbère sous la forme d'une formule du calcul des propositions dépendant de

La première tête dit ensuite : * Le premier couloir ainsi que le troisième mènent au monde des vivants ",

La deuxième tête dit : * Si le deuxième couloir mène au monde des vivants, alors le troisième n'y mène pas *,

La troisième tête conclut par : « Le premier couloir mène au monde des vivants par contre le deuxième n'y mène pas *.

Nous noterons

les variables propositionnelles correspondant au fait que le premier, le deuxième, le troisième couloir mènent au monde des vivants.

Question I.2 Exprimer

sous la forme de formules du calcul des propositions dépendant de

Question I. 3 En utilisant le calcul des propositions (résolution avec les tables de vérité), déterminer le couloir que Socrate doit suivre pour rejoindre le monde des vivants.

Question 1.4 En admettant que Cerbere ait menti en donnant les trois indications, Socrate pouvait-il suivre d'autres couloirs? Si oui, le ou lesquels?

Partie II : Algorithmique et programmation en CaML

Cette partie doit être traitée par les étudiants qui ont utilisé le langage CaML dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliares recursives Elles ne devront pas utiliser d'instructions itératives (for, while, ...) ni de références.
L'explication du comportement d'une fonction doit au moins expliciter :

L'objectif général.
Le rôle des paramètres de la fonction,
Le résultat renvoyé par la fonction,
Le rôle des variables locales à la fonction.
Le principe de l'algorithme,
La terminaison du calcul quels que soient les valeurs des paramètres.

Les approximations introduites lors de la conversion d'images analogiques continues en images numériques discontinues transforment souvent une partic continue de l'image en un nuage de points disjoints. Nous allons étudier dans cette partie une technique exploitée en traitement d'images numériques pour régénérer les parties continues : la construction de l'enveloppe convexc d'un ensemble de points.

1 Représentation du problème

1.1 Notations

Nous nous plaçons dans un espace euclidien orienté de dimension 2 muni d'un repère (

( ) représente la droite passant par les points et ,
représente le segment d'extrémités et et ,
r est l'angle orienté entre les vecteurs et , également noté .

1.2 Rappels

Déf. II. 1 (Enveloppe convexe) Soit

un ensemble de points; l'enveloppe convexe de

, notée

, est le plus petit des ensembles convexes contenant

. Dans le cas où

est un ensemble fini, ce que nous supposons dans la suite, nous admettrons que

est un polygone convexe caractérisé par ses sommets : une suite

composée de points de

. Les points de

sont alors des barycentres à coefficients positifs des points de

. c'est-à-dire:

Les points de la suite

sont orionnés de manière d ce que:

les segments sont les arêtes du polygone convexe (avec ), ils forment une ligne polygonale : le contour du polygone.

- le contour du polvgone est positif, c'est à-dire orienté dans le sens direct.

Exemple II.1 Le schéma suivant représente en hachuré l'enveloppe convexe

d'un ensemble de points

. Les sommets de

sont

1.3 Codage en CaML

Un point est représenté par un couple d'entiers :
type point == int * int;;
Un ensemble, une liste, une suite de points sont représentés par une liste de points :
type suite = point list;
Exemple II. 2 L'ensemble de points

de l'exemple II. 1 est représenté par la liste:

L'enveloppé convexe de

est représentée par la liste :

1.4 Produit croisé et fonctions trigonométriques

Les algorithmes que nous allons étudier reposent sur des propriétés trigonométriques. Le calcul informatique de fonctions trigonométriques est en général coûteux et source de nombreuses approximations. Pour éviter leur utilisation, nous allons exploiter le produit croisé qui permet la comparaison d'angles entre vecteurs sans calculer effectivement ces angles.

Déf. II. 2 (Produit croisé) Le produit croisé de trois points

est egal au produit mixte des vecteurs

, c'est-à-dire:

Question II. 1 Soient p, q et

trois points distincts; montrer que:

,
,
et sont alignés.

Question II. 2 Écrire en CaML une fonction cro i se de type point

point

int telle que l'appel (croise

) renvoie la valeur de

1.5 Séparation du plan par une droite

Déf. II. 3 Soient

, deux points distincts; l'ensemble des points à gauche de la droite (

) est

, l'ensemble des points à droite de la droite

est

Question II. 3 Écrine en CaML une fonction a_gauche de type point

point

suite

suitetelle que l'appel (a_gauche

e) renvoie une liste composée de tous les points de l'ensemble equi :

n'appartiennent pas à la droite ( ),
se trouvent à gauche de la droite ( ).

Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 4 Expliquer la fonction a.gauche proposée pour la question précédente.
Question II. 5 Calculer une estimation de la complexité de la fonction a_gauche en fonction de la taille de l'ensemble e. Cette estimation ne prendra en compte que le nombre d'appeis récursifs effectués.

Question II. 6 Modifier la fonction précédente pour définir en CaML une fonction separation de type point

point

suite

(suite * suite * suite) telle que l'appel (separation

e) renvoie un triplet de listes

, a) composées de tous les points de l'ensemble equi:

sont distincts de p et q,
se trouvent à gauche de la droite (p,q) pour la liste g.
se trouvent à droite de la droite ( ) pour la liste d.
appartiennent à la droite ( ) pour la liste a.

Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

2 Relation d'ordre polaire

La technique de construction d'enveloppes convexes étudiée dans les parties suivantes repose sur l'utilisation d'une relation d'ordre polaire pour trier les sommets de

Déf. II. 4 (Relation d'ordre polaire) Soit

un point; la relation

sur un ensemble

est définie par :

Question II. 7 Écrire en CaML une fonction ordre-polairede type point

point

bool telle que l'appel (ordrepolaire o

q) renvoie la valeur vraie si et seulement si

3 Décomposition en sous-problèmes disjoints

Pour simplifier la construction de relations d'ordre total à partir de relations d'ordre polaire, nous allons décomposer le problème en deux sous-problèmes disjoints séparés par la droite reliant le point le plus bas à gauche de

et le point le plus haut à droite de

Déf. II. 5 (Point en bas à gauche, en haut à droite) Soient p et

deux points;

est en bas à gauche de

(et

est alors en haut à droite de

) si et seulement si

. Cette notion est étendue à des ensembles de points en prenant le minimum et le maximum de l'ensemble selon la relation d'ordre précédente.

Question II. 8 Écrire en CaML une fonction ext reme de type
point

point

(point * point) relle que l'appel (extreme p1 p2) renvoie le couple (p1,p2) si p1 est en bas à gauche de p2 et le couple (p2, p1) si p2 est en bas à gauche de p1.

Question II. 9 Écrire en CaML une fonction extremes de type suite -> (point * point) telle que l'appel (ext remes e), sur un ensemble non vide de points e, renvoie un couple de points (

) de l'ensemble e. b et

doivent être les points en bas à gauche et en haut à droite par rapport aux points contenus dans e. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question II. 10 Expliquer la fonction ext remes proposée pour la question précédenze.
Question II.11 Soit

un ensemble de points, soit

le point en bas a gauche de

, soit

le point en haut à droite de

; montrer que

sont des sommets de l'enveloppe convexe

Théorème II.1 Soit

un ensemble de points; soient :

les points à droite de la droite n'appartenant pas à ,
les points à gauche de la droite n'appartenant pas à ,
les points de [.
alors forme une partition disjointe de et .

Exemple II. 3 L'ensemble de points

de l'exemple II. 1 est partitionné en :

Question II. 12 Montrer que la relation d'ordre polaire

est une relation d'ordre total sur

4 Algorithme de Jarvis : Génération des sommets

L'algorithmé étudié dans cette partic est dû̀ à Jarvis. Il est dérivé de la construction de l'ensemble des arêtes composant le contour de l'enveloppe convexe. Il repose sur le fait que les sommets d'un polygone convexe se trouvent soit tous à droite, soit tous ă gauche de chaque arête du polygone.

Théorème II. 2 Un polygone

de sommets

est convexe si et seulement si, pour toute arête

, les aurres sommets de

sont, soit tous à gauche (contour positif), soit tous à droite (contour négatif) par rapport da la droite (

L'algorithme initial proposé par Jarvis consiste à engendrer tous les segments possibles connectant deux points de l'ensemble, puis à éliminer les segments qui ne sont pas des arêtes. Cet algorithme est trop coûteux pour être utilisé pratiquement. Nous allons étudier une variante permettant d'éviter la construction de tous les segments potentiels.

Cette variante est basée sur la même propriété des arêtes. Elle consiste à choisír un premier sommet, puis à construire l'enveloppe en parcourant le contour positif.

Lensemble

est partitionné selon le théorème II.1.
Nous allons étudier le traitement de la partie droite

en partant du point en bas à gauche

. Le traitement de la partie gauche

sera symétrique en partant du point en haut à droite

Notons

les sommets de

. Nous avons montré dans la question II. 11 que

. Nous allons construire

selon la relation suivante

est le minimum de

selon

. Montrons dans une première étape la correction de cette technique :

Question II. 13 Soit

le minimum de

selon

; montrer que

est un sommet de

Question II.14 Soit

, soient

les i premiers sommets de

, soit

le minimum de

selon

montrer que

est un sommet de

Question II. 15 Déduire des questions précédentes que (

) est la suite des sommets de

Question II.16 Écrive en CaML une fonction minpolaire de type
point

suite

(point * suite) telle que l'appel (minpolaire o e), sur un ensemble non vide de points e, renvoie un couple (

) composé du point

, minimum dans l'ensemble e selon l'ordre

et du reste

de l'ensemble e privé de p. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question II.17 Expliquer la fonction min.polaire proposée pour la question précédente.
Question II. 18 Calculer uné estimation de la complexité de la fonction min.pola i re en fonction de la taille de la liste e. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.

Question II. 19 Écrire en CaML, une fonction demi _jarvis de type
point

point

suite

suitetelle que l'appel (demi_jarvis b

e) avec

un ensemble de points situés à droite de la droite (

), renvoie la suite (

) composée de points pris dans e

avec:

est le minimum de selon avec .

Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 20 Expliquer la fonction demi_jarvis proposée pour la question précédente.
Question II. 21 Calculer une estimation de la complexité de la fonction demi jarvis en fonction de la taille de l'ensemble e et du nombre de sommets de l'enveloppe convexe n. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.

Question II.22 Ecrire en CaML une fonction jarvis de type suite

suite telle que l'appel (jarvis e), sur un ensemble de points e contenant au moins trois points, renoie la suite des points composant l'enveloppe convexe des points contenus dans l'ensemble e. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question II.23 Expliquer la fonction jarvis proposée pour la question précédente.
Question II.24 Calculer une estimation de la complexité de la fonction jarvis en fonction de la taille de l'ensemble e. Cette estimation ne prendra en compte que le nombre d'appels récursifs effec. tués.

Partie II : Algorithmique et programmation en PASCAL

Cette partie doit être traitée par les étudiants qui ont utilisé le langage PASCAL dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (for, whi le, repeat,...).
L'explication du comportement d'une fonction doit au moins expliciter :

L'objectif général,
Le rôle des paramètres de la fonction.
Le résultat renvoyé par la fonction,
Le rôle des variables locales à la fonction,
Le principe de l'algorithme,
La terminaison du calcul quels que soient les valeurs des paramètres.

Les approximations introduites lors de la conversion d'images analogiques continues en images numeriques discontinues transforment souvent une partie continue de l'image en un nuage de points disjoints. Nous allons étudier dans cette partie une technique exploitée en traitement d'images numériques pour régénérer les parties continues : la construction de l'enveloppe convexe d'un ensemble de points.

1 Représentation du problème

1.1 Notations

Nous nous plaçons dans un espace euclidien orienté de dimension 2 muni d'un repère (

( ) représente la droite passant par les points et ,
représente le segment d'extrémités et et ,
est l'angle orienté entre les vecteurs et , également noté .

1.2 Rappels

Déf. II. 1 (Enveloppe convexe) Soit

un ensemble de points; l'enveloppe convexe de

, notée

, est le plus petit des ensemblex convexts contenant

. Dans le cas où

est un ensemble fini, ce que nous supposons dans la suite, nous admettrons que

est un polygone convexe caractérisé par ses sommets : une suite

composee de points de

. Les points de

sont ators des barycentres à coefficients positifs des points de

, c'est-à-dire:

Les points de la suite

sont ordonnés de manière à ce que :

Les segments sont les arêtes du polygone convexe (avec ), ils forment une ligne polygonale: le contaur du polygone,
le contour du polygone est positíf, c'est-à-dire orienté dans le sens direct.

Exemple II.1 Le schéma suivant représente en hachuré l'enveloppe convexe

d'un ensemble de points

. Les sommets de

sont

1.3 Codage en PASCAL

Un point est représenté par le type de base posnt.
Un ensemble, une liste, une suite de points sont représentés par le type de base SUITE.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement ètre utilisées dans les réponses aux questions:

FUNCTION P_Creer (a, 0: INTEGER) : POINT: renvoie un point dont l'abscisse est a et l'ordonnée o,
FUNCTION P_Abs ( : POINT) : INTEGER; renvoie l'abscisse de ,
FUNCTION P_Ord (p: POINT) : INTEGER; renvole l'ordonnée de p,
NIL représente la suite vide de points,
FUNCTION SAJouter ( : POINT; S: SUITE) : SUITE; renvoie une suite de points composée d'un premier point et du reste de la suite contenu dans .
FUNCTION S_Premier ( : SUITE) : POINT; renvoie le premier point de la suite ,
FUNCTION S_Reste ( S : SUITE) : SUITE; renvoie le reste de la suite s privée de son premier point,
FUNCTION S_Juxtaposer(s1,s2:SUITE):SUITE; renvoie la suite composée de la suite s1 suivie de la suite s 2 .

Exemple II. 2 L'ensemble de poins

de l'exemple II.I est représenté par la liste:
S_Ajouter ( P_Creer(0,3), S_Ajouter ( P_Creer(1,0),
S_Ajouter ( P_Creer(1, S), S_Ajouter ( P_Creer(2, 4),
S_Ajouter ( P_Greer(5,4), S_Ajouter( P_creer(3.2),
S_Ajouter ( P_Creer (3,6), S_Ajouter ( P_Creer(4,1),
S_Ajouter( P_Creer(6,5), S_Ajouter( P_Creer(5,3), NIL!))1)||)|) ]

L'enveloppé convexe de

est représentée par la listé:
S_Ajouter ( P_Creer(1,0), S_Ajouter ( P_Creer(4,1),
S_Ajouter

, S_Ajouter (

Creer 6 ),
S_Ajouter( P_Creer(1,5), S_Ajouter(

, NTL)))))

1.4 Produit croisé et fonctions trigonométriques

Déf. II. 2 (Produit croisé) Le produit croisé de trois points

, q et

est égal au produit mixte des vecteurs

, c'est-à-dire

Question II.I Soient p, q et r trois points distincts; montrer que:

,
,
et sont alignés.

Question II. 2 Écrire en PASCAL une fonction croise (p, q, x: POINT) : INTEGER; telle que l'appel croise (

) renvie la valeur de (

1.5 Séparation du plan par une droite

Déf. II. 3 Soient

, deux points distincts; l'ensemble des points à gauche de la droite (p,q) est

, l'ensemble des points à droite de la droite

est

Question II. 3 Ecrire en PASCAL une fonction a_gauche (p, q: POINT; e: SUITE) : SUITE telle que l'appel a_gauche (

) remoie une liste composée de tous les points de l'ensemble e qui:

n'appartiennent pas à la droite (p,q),
se trouvent à gauche de la draite ( ).

Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 4 Expliquer la fonction a_gauche proposée pour la question précédente.
Question II. 5 Calculer une estimation de la complexité de la fonction a_gauche en fonction de la taille de l'ensemble e. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.

Un triplet de suites de points est représenté par le type de base TRIPLET.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:

FUNCTION T_Creer ( : SUITE) : TRIPLET; renvoie un triplet dont les éléments sont s1, s2 et s3,
FUNCTION T_Un ( t : TRIPLET) : SUITE; renvoie le premier élément de t ,
FUNCTION T_Deux ( : TRIPLET) : SUITE; renvoie le deuxième élément de ,
FUNCTION T_Trois (L:TRIPLET) : SUITE; renvoie le troisième élément de .

Question II.6 Modifier la fonction précédente pour définir en PASCAL une fonction separation (

: POINT;

SUITE) : TRIPLET; telle que l'appel separation (

) renvoie un triplet T-Creer (

) de listes composées de tous les points de l'ensemble e qui :

sont distincts de p et q,
se trouvent à gauche de la droite (p.q) pour la liste g.
se trouvent à droite de la droite (p.q) pour la liste d,
appartiennent à la droite (p.q) pour la liste a.

Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

2 Relation d'ordre polaire

La technique de construction d'enveloppes convexes étudiée dans les parties suivantes repose sur l'utilisation d'une relation d'ordre polaíre pour trier les sommets de

Déf. II. 4 (Relation d'ordre polaire) Soit () un point; la relation

o sur un ensemble

est définie

Question II.7 Écrire en PASCAL une fonction ordre_polaire (o, p, q: POTNT) : BOOLEAN; telle que l'appel ordre-polaire (

) renvoie la valeur vraie si

3 Décomposition en sous-problèmes disjoints

et le point le plus haut à droite de

Déf. II. 5 (Point en bas à gauche, en haut à droite) Soient

deux points;

est en bas à gauche de

(et

est alors en haut à droite de

) si et seulement si

. Cette notion est étendue à des ensembles de points en prenant lé minimum et le maximum de l'ensemble selon la relation d'ordre précédente.

Un couple de points est représenté par le type de base COUPLE
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :

FUNCTION C_Creer (p1,p2: POINP) : COUPLE; renvoie un couple dont les éléments sont p1 et p2,
FUNCTION C_UN (C:COUPLE) : POINT; renvoie le premier élément de c.
FUNCTION C_Deux (C:COUPLE) : POINT; renvie le second élément de c.

Question II. 8 Écrire en PASCAL une fonction extreme (p1,p2 ; POINT) : COUPLE; elle que l'appel extreme (p1,p2) renvie le couple C Creer (p1,p2) si p1 est en bas à gauche de p2 et le couple C_Creer (p2, p1) sinon (dans ce cas, p2 est en bas à gauche de p1).

Question II. 9 Écrire en PASCAL une fonction ext remes ( e: SUTTE) : COUPLE; telle que V'appel ext remes (

), sur un ensemble non vide de points e, renvoie un couple de points

de l'ensemble e. bet h sout les point en bas à gauche et en haut à droite par rapport aux points contenus dans e. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question II. 10 Expliquer la fonction ext remes proposée pour la question précédente.
Question II. 11 Soit

un ensemble de points, soit

te point en bas à gauche de

, soit

le point en haut a droite de

montrer que

sont des sommets de

'enveloppe convexe'

Théorème II. 1 Soit

un ensemble de points; soient :

les points à droite de la droite ( ) 'appartenant pas à ( ),
les points à gauche de la droite n'appartenant pas à ,
les points de .
alors forme une partition disjointe de et .

Exemple II. 3 L'ensemble de points

de l'exemple II. I est partitionné en :

Question II.12 Montrer que la relation d'ordre polaire est une relation d'ordre total sur .

4 Algorithme de Jarvis : Génération des sommets

L'algorithme étudié dans cette partie est dû à Jarvis. Il est dérivé de la construction de l'ensemble des arêtes composant le contour de l'enveloppe convexe. Il repose sur le fait que les sommets dun polygone convexe se urouvent soit tous à droite, soit tous à gauche de chaque arête du polygone.

Théorème II. 2 Un polygone

de sommets

est convexe si et seulement si, pour toute arête

. les autres sommets de

sont, soit tous à gauche (contour positif). soit tous à droite (contour négatiff) par rapport à la droite (

L'algorithme initial proposé par Jarvis consiste à engendrer tous les segments possibles connectant deux points de l'ensemble, puis à climiner les segments qui ne sont pas des arètes. Cet algorithme est trop coûteux pour être utilisé pratiquement. Nous allons étudier une variante permettant d'éviter la construction de tous les segments potentiels.

Cette variante est basée sur la même propriété des arêtes. Elle consiste à choisir un premier sommet, puis à construire l'enveloppe en parcourant le contour positif.

L'ensemble

est partitionné selon le théorème II.1.
Nous allons étudier le traitement de la partie droite

en partant du point en bas à gauche

. Le traitement de la partic gauche

sera symétrique en partant du point en haut à droite

Notons

les sommets de

. Nous avons montré dans la question II. 11 que

. Nous allons construire

selon la relation suivante

est le minimum de

selon

. Montrons dans une première étape la correction de cette technique :

Question II.13 Soit

le minimum de

selon

; montrer que

est un sommet de

Question II.14 Soit

, soient

les i premiers sommets de

, soit

le minimum de

selon

; montrer que p est un sommet de

Question II.15 Déduire des questions précédentes que (

) est la suite des sommets de

Question II.16 Écrive en PASCAL une fonction min-polaire (o: POINT; e: SUTTE) : SUITE telle que l'appel min-polaire( 0, e), sur un ensemble non vide de points, renvoie une suite S_Ajouter (

) composée d'un premier point

, minimum dans l'ensemble e selon l'ordre

et du reste

composé des points de e privé de p. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question II.17 Expliquer la fonction min_pola ixe proposée pour la question précédente.
Question II. 18 Calculer une estimation de la complexité de la fonction min_polaire en fonction de la taille de la liste e. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.

Question II. 19 Ecrire en PASCAL une fonction demi_jarvis (b, h: POINT; e: SUITE) : SUITE; telle que l'appel demi_jarvis (

, e) avec e un ensemble de points situés à droite de la droite

, renvoie la suite

composée de points pris dans e

avec:

est le minimum de selon avec .

Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 20 Expliquer la fonction demi_jarvis proposée pour la question précédente.
Question II. 21 Calculer une estimation de la complexité de la fonction demi_jarvis en fonction de la taille de l'ensemble e et du nombre de sommets de l'enveloppe convexe n. Cette estimation ne. prendra en compte que le nombre d'appels récursifs effectués.

Question II. 22 Écrire en PASCAL une fonction jarvis (e:SUITE) : SUITE; telle que l'appel jarvis (e), sur un ensemble e contenant au moins trois points, renvoie la suite des points composant l'enveloppe convexe des points contenus dans l'ensemble e. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Question II.23 Expliquer la fonction jarvis proposée pour la question précédente.
Question II. 24 Calculer une estimation de la complexité de la fonction jarvis en fonction de la taille de l'ensemble e. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.

Partie III : Automates et langages

Le but de cet exercice est l'étude des propriétés de l'opération d'inversion d'un automate.
Pour simplifier l'exercice, nous considérerons uniquement des automates qui ne possèdent pas de transitions arbitraires e. Les résultats étudiés sont également valides dans ces cas-là, mais la formalisation et la construction des preuves sont plus complexes.

Soit l'alphabet

, un ensemble de symboles, soit

(parfois noté abusivement avec le même symbole que la transition arbitraire

) le symbole représentant le mot vide (

), soit

l'ensemble des mots composés de symboles de

; un automate fini sur

est un quintuplet

composé de :

Un ensemble d'états : ,
Un ensemble d'états initiaux : ,
Un ensemble d'états terminaux : ,
Une relation de transition : .

Remarquons que

est souvent notée sous la forme dune fonction totale de transition

dont les valeurs sont définies par :

La notation

, contrairement à

, est symétrique. Cette propriété simplifie la formalisation et la construction des preuves.

Les valeurs de la relation de transition

seront représentées par un graphe dont les neuds sont les états. Un état initial sera entouré d'un cercle

et un état final sera entouré d'un double cercle ( 0 ). Une arête étiquetée par le symbole

ira de l'état

à l'ćtat

si et seulement si

Soit

l'extension de

définie par :

Le langage sur

reconnu par un automate fini est :

Dér. III.I (État accessible) Soin l'autonale fini

est accessible si et seulement si

Déf. III. 2 (Ếtat co-accessible) Soit l'automate fun

est co-accessible si et seulement si

Nous considérerons uniquement dans cet exercice des automates dont tous les états sont accessibles et co accessibles.

1 Étude de l'exemple

Soit l'automate fini

dont la relation de transition est représentée par le graphe

Question III. 1 Donner sans la justifier une expression régulière ou ensembliste représentant le langage reconnu par

2 Opération d'inversion d'un automate:

Soit l'opération interne d'inversion d'un automate fini définie par :
Déf. III. 3 Soit

un automate fini, l'automate

, inverse de l'automate

, est défini par:

Question III. 2 Construire l'automate

.
Question III. 3 Justifier que l'automate

est non déterministe puis le déterminiser (seuls les états et les transitions utiles, c'est-à-dire accessibles depuis les etats initiaux et co-accessibles depuis les états terminaux, devront être construits). L'automate obtenu est notê

Question III. 4 Caractériser le langage reconnu par

par une expression régulière ou ensembliste. Comparer ce langage avec le langage reconnu par

Question III. 5 Construire l'automate

.
Question III. 6 Justifier que l'automate

est non déterministe puis le déterminiser (seuls les êtuts et les transitions utiles, c'est-à-dire accessibles depuis les états initiaux et co-accessibles depuis les états terminaux, devront être construits). L'automate obtenu est noté

Question III. 7 Caractériser le langage reconnu par

par une expression régulière ou ensembliste. Comparer ce langage avec le langage recomnu par

3 Étude de l'automate inverse

Question III. 8 Montrer que:

Déf. III. 4 L'opération d'inversion de mots sur

est définie par :

Question III. 9 Montrer que :

.
Question III. 10 Quelle relation liant les langages reconnus par

peut-on en deduire?