X/ENS Informatique B MP-PC 2015

Thème de l'épreuve Enveloppes convexes dans le plan
Principaux outils utilisés tableaux et listes, boucles for et while, piles, complexité
Mots clefs enveloppe convexe, algorithme de balayage, algorithme du paquet cadeau, pile, nuage de points

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
                                            

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE ­ ECOLES NORMALES SUPERIEURES ECOLE SUPERIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES CONCOURS D'ADMISSION 2015 FILIERE MP HORS SPECIALITE INFO FILIERE PC COMPOSITION D'INFORMATIQUE ­ B ­ (XECLR) (Duree : 2 heures) L'utilisation des calculatrices n'est pas autorisee pour cette epreuve. Le langage de programmation choisi par le candidat doit etre specifie en tete de la copie. Enveloppes convexes dans le plan Ce sujet a pour objectif de calculer des enveloppes convexes de nuages de points dans le plan affine, un grand classique en geometrie algorithmique. On rappelle qu'un ensemble C R2 est convexe si et seulement si pour toute paire de points p, q C, le segment de droite [p, q] est inclus dans C. L'enveloppe convexe d'un ensemble P R2 , notee Conv(P ), est le plus petit convexe contenant P . Dans le cas ou P est un ensemble fini (appele nuage de points), le bord de Conv(P ) est un polygone convexe dont les sommets appartiennent a P , comme illustre dans la figure 1. 5 2 10 6 1 9 4 8 11 3 0 7 Figure 1 ­ Un nuage de points, numerotes de 0 a 11, et le bord de son enveloppe convexe. Le calcul de l'enveloppe convexe d'un nuage de points est un probleme fondamental en informatique, qui trouve des applications dans de nombreux domaines comme : ­ la robotique, par exemple pour l'acceleration de la detection de collisions dans le cadre de la planification de trajectoire, 1 ­ le traitement d'images et la vision, par exemple pour la detection d'objets convexes (comme des plaques mineralogiques de voiture) dans des scenes 2d, ­ l'informatique graphique, par exemple pour l'acceleration du rendu de scenes 3d par lancer de rayons, ­ la theorie des jeux, par exemple pour determiner l'existence d'equilibres de Nash, ­ la verification formelle, par exemple pour determiner si une variable risque de depasser sa capacite de stockage ou d'atteindre un ensemble de valeurs interdites lors de l'execution d'une boucle dans un programme, et bien d'autres encore. Dans ce sujet nous allons ecrire deux algorithmes de calcul du bord de l'enveloppe convexe d'un nuage de points P dans le plan affine. Le premier, dit algorithme du paquet cadeau, consiste a envelopper le nuage de points P progressivement en faisant pivoter une droite tout autour. Le deuxieme, dit de balayage, consiste a balayer le plan horizontalement avec une droite verticale, tout en maintenant au fur et a mesure l'enveloppe convexe de la partie du nuage situee a gauche de cette droite verticale. Les deux algorithmes sont illustres respectivement dans les figures 3 et 4. Le temps d'execution du premier algorithme est majore par une constante fois nm, celui du deuxieme par une constante fois n log n, ou n designe le nombre total de points de P et m le nombre de points de P appartenant au bord de Conv(P ). Rappelons que le temps d'execution d'un programme A (fonction ou procedure) est le nombre d'operations elementaires (comparaisons, additions, soustractions, multiplications, divisions, affectations, etc.) necessaires a l'execution de A. Sauf mention contraire dans l'enonce du sujet, le candidat n'aura pas a justifier des temps de calcul de ses programmes. Toutefois, il devra veiller a ce que ces derniers ne depassent pas les bornes prescrites. Dans toute la suite on supposera que le nuage de points P est de taille n 3 et en position generale, c'est-a-dire qu'il ne contient pas 3 points distincts alignes. Ces hypotheses vont permettre de simplifier les calculs en ignorant les cas pathologiques, comme par exemple la presence de 3 points alignes sur le bord de l'enveloppe convexe. Nos programmes prendront en entree un nuage de points P dont les coordonnees sont stockees dans un tableau tab a 2 dimensions, comme dans l'exemple ci-dessous qui contient les coordonnees du nuage de points de la figure 1 : i\j 0 1 0 0 0 1 1 4 2 1 8 3 4 1 4 4 4 5 5 9 6 5 6 7 7 -1 8 7 2 9 8 5 10 11 6 11 13 1 Precisons que les coordonnees, supposees entieres, sont donnees dans une base orthonormee du plan, orientee dans le sens direct. La premiere ligne du tableau contient les abscisses, tandis que la deuxieme contient les ordonnees. Ainsi, la colonne d'indice j contient les deux coordonnees du point d'indice j. Ce dernier sera nomme pj dans la suite. 2 Partie I. Preliminaires Question 1 Ecrire une fonction plusBas(tab, n) qui prend en parametre le tableau tab de taille 2 × n et qui renvoie l'indice j du point le plus bas (c'est-a-dire de plus petite ordonnee) parmi les points du nuage P . En cas d'egalite, votre fonction devra renvoyer l'indice du point de plus petite abscisse parmi les points les plus bas. Sur le tableau exemple precedent, le resultat de la fonction doit etre l'indice 7. Dans la suite nous aurons besoin d'effectuer un seul type de test geometrique : celui de l'orientation. Definition 1 Etant donnes trois points pi , pj , pk du nuage P , distincts ou non, le test d'orientation renvoie +1 si la sequence (pi , pj , pk ) est orientee positivement, -1 si elle est orientee negativement, et 0 si les trois points sont alignes (c'est-a-dire si deux au moins sont egaux, d'apres l'hypothese de position generale). Pour determiner l'orientation de (pi , pj , pk ), il suffit de calculer l'aire signee du triangle, comme illustre sur la figure 2. Cette aire est la moitie du determinant de la matrice 2 × 2 formee -- par les coordonnees des vecteurs - p- i pj et pi pk . pk pj pj + - pj pi p pk i pi = pk Figure 2 ­ Test d'orientation sur la sequence (pi , pj , pk ) : positif a gauche, nul au centre, negatif a droite. Question 2 Sur le tableau exemple precedent, donner le resultat du test d'orientation pour les choix d'indices suivants : ­ i = 0, j = 3, k = 4, ­ i = 8, j = 9, k = 10. Question 3 Ecrire une fonction orient(tab, i, j, k) qui prend en parametres le tableau tab et trois indices de colonnes, potentiellement egaux, et qui renvoie le resultat (-1, 0 ou +1) du test d'orientation sur la sequence (pi , pj , pk ) de points de P . Partie II. Algorithme du paquet cadeau Cet algorithme a ete propose par R. Jarvis en 1973. Il consiste a envelopper peu a peu le nuage de points P dans une sorte de paquet cadeau, qui a la fin du processus est exactement le bord de Conv(P ). On commence par inserer le point de plus petite ordonnee (celui d'indice 7 dans l'exemple de la figure 1) dans le paquet cadeau, puis a chaque etape de la procedure on selectionne le prochain point du nuage P a inserer. 3 La procedure de selection fonctionne comme suit. Soit pi le dernier point insere dans le paquet cadeau a cet instant. Par exemple, i = 10 dans l'exemple de la figure 3. Considerons la 5 2 10 6 1 9 4 8 11 3 0 7 Figure 3 ­ Mise a jour du paquet cadeau apres insertion du point p10 . relation binaire definie sur l'ensemble P \ {pi } par : p j pk orient(tab, i, j, k) 0. Question 4 Justifier brievement le fait que est une relation d'ordre total sur l'ensemble P \ {pi }, c'est-a-dire : - (reflexivite) pour tout j 6= i, pj pj , - (antisymetrie) pour tous j, k 6= i, pj pk et pk pj implique j = k, - (transitivite) pour tous j, k, l 6= i, pj pk et pk pl implique pj pl , - (totalite) pour tous j, k 6= i, pj pk ou pk pj . Ainsi, le prochain point a inserer (le point d'indice 5 dans la figure 3) est l'element maximum pour la relation d'ordre . Il peut se calculer en temps lineaire (c'est-a-dire majore par une constante fois n) par une simple iteration sur les points de P \ {pi }. Question 5 Decrire une realisation en Python de la procedure. Elle prendra la forme d'une fonction prochainPoint(tab, n, i), qui prend en parametre le tableau tab de taille 2 × n ainsi que l'indice i du point insere en dernier dans le paquet cadeau, et qui renvoie l'indice du prochain point a inserer. Le temps d'execution de votre fonction doit etre majore par une constante fois n, pour tous n et i. La constante doit etre independante de n et i, et on ne demande pas de la preciser. Question 6 Decrire a la main le deroulement de la procedure prochainPoint sur l'exemple de la figure 3. Plus precisement, indiquer la sequence des points de P \ {p10 } consideres et la valeur de l'indice du maximum a chaque iteration. On peut maintenant combiner la fonction prochainPoint avec la fonction plusBas de la question 1 pour calculer le bord de l'enveloppe convexe de P . On commence par inserer le point pi d'ordonnee la plus basse, puis on itere le processus de mise a jour du paquet cadeau jusqu'a ce que le prochain point a inserer soit de nouveau pi . A ce moment-la on renvoie le paquet cadeau comme resultat sans inserer pi une seconde fois. Un detail technique : comme la taille du paquet cadeau augmente peu a peu lors du processus, et qu'a la fin elle peut etre petite par rapport au nombre n de points de P , nous stockerons les 4 indices des points du paquet cadeau dans une liste. Par exemple, sur le nuage de la figure 1, le resultat sera la liste [7, 11, 10, 5, 2, 0]. Question 7 Ecrire une fonction convJarvis(tab, n) qui prend en parametre le tableau tab de taille 2 × n representant le nuage P , et qui renvoie une liste contenant les indices des sommets du bord de l'enveloppe convexe de P , sans doublon. Le temps d'execution de votre fonction doit etre majore par une constante fois nm, ou m est le nombre de points de P situes sur le bord de Conv(P ). Question 8 Justifier brievement le temps d'execution de l'algorithme du paquet cadeau. Intermede : piles d'entiers Dans la suite nous aurons besoin d'utiliser des piles d'entiers, dont on rappelle la definition ci-dessous : Definition 2 Une pile d'entiers est une structure de donnees permettant de stocker des entiers et d'effectuer les operations suivantes en temps constant (independant de la taille de la pile) : ­ creer une nouvelle pile vide, ­ determiner si la pile est vide, ­ inserer un entier au sommet de la pile, ­ determiner la valeur de l'entier au sommet de la pile, ­ retirer l'entier au sommet de la pile. Nous supposerons fournies les fonctions suivantes, qui realisent les operations ci-dessus et s'executent chacune en temps constant : ­ newStack(), qui ne prend pas d'argument et renvoie une pile vide, ­ isEmpty(s), qui prend une pile s en argument et renvoie True ou False suivant que s est vide ou non, ­ push(i, s), qui prend un entier i et une pile s en argument, insere i au sommet de s (c'esta-dire a la fin de la liste), et ne renvoie rien, ­ top(s), qui prend une pile s (supposee non vide) en argument et renvoie la valeur de l'entier au sommet de s (c'est-a-dire a la fin de la liste), ­ pop(s), qui prend une pile s (supposee non vide) en argument, supprime l'entier au sommet de s (c'est-a-dire a la fin de la liste) et renvoie sa valeur. Dans la suite il est demande aux candidats de manipuler les piles uniquement au travers de ces fonctions, sans aucune hypothese sur la representation effective des piles en memoire. Partie III. Algorithme de balayage Cet algorithme a ete propose par R. Graham en 1972. Nous allons ecrire la variante (plus simple) proposee par A. Andrew quelques annees plus tard. 5 La premiere etape consiste a trier les n points du nuage P par ordre croissant d'abscisse, en conservant tous les points de meme abscisse dans un ordre arbitraire. Question 9 Parmi les algorithmes de tri que vous connaissez, mentionnez-en un qui a un temps d'execution majore par une constante fois n log n sur les entrees de taille n. A partir de maintenant, on supposera que les points fournis en entree sont tries par abscisse croissante, comme c'est le cas dans l'exemple du tableau tab donne au debut du sujet. L'idee de l'algorithme est de balayer le nuage de points horizontalement de gauche a droite par une droite verticale, tout en mettant a jour l'enveloppe convexe des points de P situes a gauche de cette droite, comme illustre dans la figure 4. 5 5 5 2 2 10 6 1 2 4 10 6 9 1 4 11 0 4 8 11 3 0 7 1 9 8 8 3 10 6 9 11 3 0 7 7 Figure 4 ­ Diverses etapes dans la procedure de balayage. La droite de balayage est en tirets. Plus precisement, l'algorithme visite chaque point de P une fois, par ordre croissant d'abscisse (donc par ordre croissant d'indice de colonne dans le tableau tab car celui-ci est trie). A chaque nouveau point pi visite, il met a jour le bord de l'enveloppe convexe du sous-nuage {p0 , · · · , pi } situe a gauche de pi . On remarque que les points p0 et pi sont sur ce bord, et on appelle enveloppe superieure la partie du bord de Conv{p0 , · · · , pi } situee au-dessus de la droite passant par p0 et pi (p0 et pi compris), et enveloppe inferieure la partie du bord de Conv{p0 , · · · , pi } situee au-dessous (p0 et pi compris). Le bord de Conv{p0 , · · · , pi } est donc constitue de l'union de ces deux enveloppes, apres suppression des doublons de p0 et pi . Par exemple, dans le cas du nuage P de la figure 4 gauche, le sous-nuage {p0 , p1 , p2 , p3 , p4 } a pour enveloppe superieure la sequence (p0 , p2 , p4 ) et pour enveloppe inferieure la sequence (p0 , p3 , p4 ), le bord de son enveloppe convexe etant donne par la sequence (p0 , p3 , p4 , p2 ). Informatiquement, les indices des sommets des enveloppes inferieure et superieure seront stockes dans deux piles d'entiers separees, ei (pour enveloppe inferieure) et es (pour enveloppe superieure). La mise a jour de l'enveloppe superieure est illustree dans la figure 5 : tant que le point visite (p9 dans ce cas) et les deux points dont les indices sont situes au sommet de la pile es (dans l'ordre : p8 et p5 ) forme une sequence (p9 , p8 , p5 ) d'orientation negative (voir la definition 1 pour rappel de l'orientation), on depile l'indice situe au sommet de es (8 dans ce cas). On poursuit ce processus d'elimination jusqu'a ce que l'orientation devienne positive ou qu'il ne reste plus qu'un seul indice dans la pile. L'indice du point visite (p9 dans ce cas) est alors insere au sommet de es. La mise a jour de l'enveloppe inferieure s'opere de maniere symetrique. 6 5 5 2 2 1 4 + 10 6 5 2 10 6 - 9 1 4 11 0 4 8 11 3 0 7 1 9 8 8 3 10 6 9 11 3 0 7 7 Figure 5 ­ Mise a jour de l'enveloppe superieure lors de la visite du point p9 . Question 10 Ecrire une fonction majES(tab, es, i) qui prend en parametre le tableau tab ainsi que la pile es et l'indice i du point a visiter, et qui met a jour l'enveloppe superieure du sousnuage. Le temps d'execution de votre fonction doit etre majore par une constante fois i. Question 11 Ecrire une fonction majEI(tab, ei, i) qui effectue la mise a jour de l'enveloppe inferieure, avec le meme temps d'execution. Question 12 Ecrire maintenant une fonction convGraham(tab, n) qui prend en parametre le tableau tab de taille 2 × n representant le nuage P , et qui effectue le balayage des points de P comme decrit precedemment. On supposera les colonnes du tableau tab deja triees par ordre croissant d'abscisse. La fonction doit renvoyer une pile s contenant les indices des sommets du bord de Conv(P ) tries dans l'ordre positif d'orientation, a commencer par le point p0 . Par exemple, sur le nuage de la figure 1, le resultat de la fonction convGraham doit etre la pile s contenant la suite d'incides 0, 7, 11, 10, 5, 2 dans cet ordre, l'indice 0 se trouvant au fond de la pile s et l'indice 2 au sommet de s. Question 13 Analyser brievement le temps d'execution de l'algorithme de balayage decrit precedemment, en supposant une fois encore que les points du nuage fourni en entree sont deja tries par abscisse croissante. En deduire que le temps d'execution total de l'algorithme de Graham-Andrew est bien majore par une constante fois n log n. 7

Extrait du corrigé obtenu par reconnaissance optique des caractères


 X/ENS Informatique B (MP/PC) 2015 -- Corrigé Ce corrigé est proposé par Benjamin Monmege (Enseignant-chercheur à l'université) ; il a été relu par Céline Chevalier (Enseignant-chercheur à l'université) et Guillaume Batog (Professeur en CPGE). Ce sujet propose l'étude de deux algorithmes calculant l'enveloppe convexe d'un nuage de points en position générale dans le plan affine, c'est-à-dire qui ne contient pas trois points distincts alignés. Le calcul d'enveloppe convexe est utilisé dans de nombreux domaines : robotique, traitement d'image, théorie des jeux, vérification formelle... Les parties II et III sont indépendantes. · La première partie propose d'implémenter deux fonctions préliminaires permettant respectivement de trouver le point le plus bas du nuage et de tester l'orientation d'un triangle, opération cruciale dans la suite. · La deuxième partie étudie l'algorithme du paquet cadeau, qui consiste à envelopper petit à petit le nuage de points. Cette construction nécessite un temps d'exécution en O(nm), où n est le nombre de points et m celui de leur enveloppe convexe. · Enfin, la troisième partie étudie l'algorithme de balayage qui résout le même problème en temps O(n log n) grâce à la construction, à l'aide de piles, des enveloppes supérieure et inférieure des n points. Ce sujet est d'une longueur raisonnable pour une épreuve de deux heures. Il se concentre sur les parties d'algorithmique et de programmation du programme et ne présente aucune difficulté majeure sous réserve de maîtriser les rudiments du langage de programmation choisi. Indications Partie II 4 Dans la propriété d'antisymétrie, il s'agit en fait de montrer que si pj pk et pk pj alors pj = pk : la conclusion j = k vient alors du fait que le nuage P est un ensemble qui ne contient donc pas deux occurrences du même point. Pour prouver la propriété de transitivité, utiliser le fait que pi appartient à l'enveloppe convexe, de sorte que tous les autres points sont inclus dans un demi-plan contenant pi . 7 Utiliser les fonctions des questions 1 et 5. Pour ajouter un élément j à une liste liste, utiliser la commande liste.append(j). Partie III 10 Commencer par écrire une fonction auxiliaire renvoyant la paire (j, k) des dernier et avant-dernier éléments de la pile, en supprimant au passage le sommet de la pile. Utiliser alors une boucle while qui applique la fonction auxiliaire précédente et teste l'orientation du triangle (pi , pj , pk ), tant que celle-ci est négative. 11 Se convaincre que seul le test d'orientation doit être modifié par rapport à la question précédente. 12 Une fois obtenues les piles es et ei contenant les enveloppes supérieure et inférieure respectivement, il s'agit d'insérer à l'envers le contenu de es duquel on a retiré les premier et dernier éléments à la pile ei (pour éviter les doublons). 13 Borner le nombre de fois où chaque indice peut être inséré ou supprimé définitivement des deux piles es et ei, puis majorer le nombre total de tests d'orientation effectués le long de l'exécution de convGraham. I. Préliminaires 1 Initialisons un indice j à 0, ayant vertu à contenir l'indice du point de plus petite ordonnée. À l'aide d'une boucle for, testons chaque point afin de mettre à jour j si nécessaire, à savoir si le point courant a une ordonnée strictement inférieure, ou bien une même ordonnée mais une abscisse strictement inférieure. def plusBas(tab,n): j = 0 for i in range(1,n): if (tab[1][i] < tab[1][j] or (tab[1][i] == tab[1][j] and tab[0][i] < tab[0][j])): j = i return j 2 Pour i = 0, j = 3, k = 4, le tableau de l'énoncé apporte les coordonnées suivantes : le point p0 a pour coordonnées (0, 0), le point p3 a pour coordonnées (4, 1) -- et le point p4 a pour coordonnées (4, 4). Ainsi, les vecteurs - p- 0 p3 et p0 p4 ont pour coordonnées respectives (4, 1) et (4, 4). L'aire signée du triangle (p0 , p3 , p4 ) est donc 1 4 × 1 2 16 - 4 4 = =6>0 4 2 de sorte que le triangle (p0 , p3 , p4 ) est orienté positivement. Le résultat du test d'orientation sur (p0 , p3 , p4 ) est +1. De même, pour i = 8, j = 9, k = 10, le point p8 a pour coordonnées (7, 2), le point p9 a pour coordonnées (8, 5) et le point p10 a pour coordonnées (11, 6). --- Par conséquent, les vecteurs - p- 8 p9 et p8 p10 ont pour coordonnées respectives (1, 3) et (4, 4). L'aire signée du triangle (p8 , p9 , p10 ) est ainsi 1 4 - 12 1 4 × = = -4 < 0 3 4 2 2 ce qui implique que le triangle (p8 , p9 , p10 ) est orienté négativement. Le résultat du test d'orientation sur (p8 , p9 , p10 ) est -1. 3 La fonction orient calcule le déterminant utilisé dans l'aire signée du triangle (pi , pj , pk ) et teste son signe. En particulier, le déterminant est nul si et seulement si deux des trois points au moins sont confondus, auquel cas le résultat du test d'orientation est 0. def orient(tab,i,j,k): pi_pj = [tab[0][j]-tab[0][i], tab[1][j]-tab[1][i]] pi_pk = [tab[0][k]-tab[0][i], tab[1][k]-tab[1][i]] det = pi_pj[0] * pi_pk[1] - pi_pj[1] * pi_pk[0] if det > 0: return 1 elif det < 0: return -1 else: return 0 II. Algorithme du paquet cadeau 4 Pour la réflexivité, notons que pour tout j 6= i, orient(tab, i, j, j) = 0 puisque deux des points sont égaux, de sorte que pj pj . Pour l'antisymétrie, supposons fixés j et k tels que pj , pk P r {pi }, pj pk et pk pj . Par définition, det(- p- p ,- p- p ) 6 0 et det(- p- p ,- p- p )60 i j i k i k i j Puisque ces deux déterminants sont opposés l'un de l'autre, ils sont nuls, ce qui -- prouve que les vecteurs - p- i pj et pi pk sont colinéaires, c'est-à-dire que pi , pj et pk sont alignés. Grâce à l'hypothèse de position générale et le fait que pj et pk sont distincts de pi , cela montre que pj = pk . Une coquille s'est glissée dans l'énoncé : la propriété d'antisymétrie consiste à montrer a priori que pj pk et pk pj implique pj = pk , et non j = k. On peut cependant conclure que j = k puisque le nuage P est un ensemble qui ne contient donc pas deux occurrences du même point. Montrons la transitivité . Pour cela, fixons j, k, tels que pj , pk , p P r {pi }, pj pk et pk p . Supposons également que le point pi appartient à l'enveloppe convexe de P, de sorte que les points pj , pk et p sont tous dans un demi-plan dont la frontière D contient pi (et aucun des trois autres points grâce à l'hypothèse de position générale), comme représenté dans la figure de gauche ci-dessous. D p - pk p - e1 - e2 pi - pk pi + - - pj pj La figure de droite ci-dessus montre que la propriété de transitivité est fausse si pi n'est pas sur l'enveloppe convexe de P, puisque (pi , pj , pk ) et (pi , pk , p ) sont orientés négativement, mais que (pi , pj , p ) est orienté positivement. Munissons le plan affine d'un repère orthonormé direct (pi , - e1 , - e2 ) avec - e1 un vecteur - directeur de la droite D et e orienté vers le demi-plan contenant les points p , p j 2 k et p . Dans le plan complexe associé, les arguments principaux respectifs j , k et des points pj , pk et p appartiennent à [ 0 ; ]. L'interprétation géométrique du déterminant de deux vecteurs dans le plan euclidien assure que k- p- p k × k- p- p k × sin( - ) 6 0 et k- p- p k × k- p- p k × sin( - ) 6 0 i j i k k j i k i k Puisque k -j et -k appartiennent à [ - ; ], le fait que le sinus de ces angles soit négatif implique que k - j et - k appartiennent en fait à [ - ; 0 ]. Par somme, - j [ -2 ; 0 ]. Comme cet angle est par ailleurs inclus dans [ - ; ], on en déduit que - j [ - ; 0 ], de sorte que sin( - j ) 6 0. Finalement, det(- p- p ,- p- p ) = k- p- p k × k- p- p k × sin( - ) 6 0 i j i i j i j ce qui prouve que pj p . Voici une autre preuve utilisant la bilinéarité du déterminant. Les hypothèses d'orientation négative impliquent que