Nous allons travailler dans un premier temps sur des tableaux de flottants. Nous utiliserons des tableaux dont le premier indice est 0 puisque c'est la seule possibilité en C, et la solution optimale dans les autres langages puisque nécessitant moins de calculs dans le code compilé. Si tous les tableaux utilisés ont la même dimension, on peut définir de manière globale :
#define composante float #define dim_tus 100 typedef composante type_tus[dim_tus];Ces déclarations sont nécessaires dans les langages effectuant un contrôle très strict des types de données (comme le Pascal) et refusant de combiner des tableaux de tailles différentes. En C, nous pouvons préparer des fonctions sur tous tableaux de réels, quelle que soit leur dimension :
#define composante float typedef composante type_tus[]; /* ou typedef composante *type_tus */C'est cette seconde déclaration que nous utiliserons dans les exemples suivants.
Remarque : dans notre cas il peut être intéressant de définir un tableau comme une structure regroupant le tableau, sa dimension et sa taille effective.
void init_tus(type_tus tab,int *taille,int dim)
{
int i;
for(i=0;i<dim;i++) tab[i]=0;
*taille=0;
}
L'initialisation à 0 n'est pas nécessaire dans la
plupart des cas. La taille est passée par adresse puisque
modifiée par la fonction init_tus.
int ajoute_val_tus(type_tus tab,int *taille,int dim,composante val)
/* retourne 0 si tout s'est bien passé, 1 si erreur */
{
if (*taille>=dim)
{
puts("dépassement de capacité du tableau");
return(1);
}
/* le else n'est pas nécessaire du fait du return précédent */
tab[(*taille)++]=val;
return(0);
}
void affiche_tus(type_tus tab,int taille)
{
int i;
for(i=0;i<taille;i++) printf("%dième valeur :
%f\n",i+1,tab[i]);
}
Les déclarations globales et fonctions ci-dessus étant
recopiées dans le fichier "base_tus", nous pouvons écrire le
programme suivant (ex_tus) :
#include <stdio.h>
#include "base_tus.inc"
#define dim 100
void main(void)
{
int nb;
composante v,t[dim];
init_tus(t,&nb,dim);
do
{
printf("entrez la %dième note (fin si <0 ou >20) :",nb+1);
scanf("%f",&v);
if(v<0||v>20) break; /* on aurait pu le mettre
dans la condition du while */
}
while (!ajoute_val_tus(t,&nb,dim,v));
affiche_tus(t,nb);
}
Exercice (tusexo_a) : modifier ce programme pour qu'il calcule
la moyenne et affiche, pour chaque note, l'écart avec la moyenne (ce qui
nécessite l'utilisation d'un tableau car il faut d'abord calculer la
moyenne puis utiliser les notes mémorisées auparavant).
void suppr_tus(type_tus tab,int *taille,int position)
{
int i;
if(position>=*taille||position<0)return;
(*taille)--;
for(i=position;i<*taille;i++)tab[i]=tab[i+1];
}
On peut remarquer que la suppression de la dernière composante
n'entraîne aucun décalage.
int insert_tus(type_tus tab,int *taille,int dim,int position,composante val)
/* retourne 0 si pas d'erreur */
{
int i;
if(position<0)return(1);
if(position>*taille)position=*taille;
if (*taille>=dim)
{
puts("dépassement de capacité du tableau");
return(2);
}
for(i=*taille;i>position;i--)tab[i]=tab[i-1];
tab[position]=val;
(*taille)++;
return(0);
}
Le décalage doit se faire par indice décroissant (par indice
croissant, on recopierait progressivement la composante à l'indice
position dans tout le reste du tableau).Les rotations sont également des manipulations fréquentes sur les tableaux :
void rot_gauche_tus(type_tus tab,int taille)
{
composante tampon;
int i;
tampon=tab[0];
for(i=1;i<taille;i++)tab[i-1]=tab[i];
tab[taille-1]=tampon;
}
void rot_droite_tus(type_tus tab,int taille)
{
composante tampon;
int i;
tampon=tab[taille-1];
for(i=taille-1;i>0;i--)tab[i]=tab[i-1];
tab[0]=tampon;
}
Exercice (tusexo_b) : faire un programme permettant de tester ces
fonctions, à l'aide d'un menu permettant d'essayer dans n'importe quel
ordre ces fonctions.
Les exemples qui suivent traitent des tableaux de flottants, les méthodes étant identiques pour tout type de composante à condition d'y définir une relation d'ordre (par exemple, pour des chaînes de caractères on utilisera strcmp au lieu de <, > et =). Mais il ne faut pas oublier que l'efficacité de l'algorithme dépend également des types de données traitées : une comparaison de chaînes de caractères étant relativement longue, les algorithmes effectuant beaucoup de tests seront moins efficaces qu'avec des flottants. De même, les tableaux trop gros pour entrer en mémoire devront être traités sur support externe, rendant l'accès aux données (plusieurs millisecondes) bien plus lent que les tests ou calculs (micro voire nanosecondes). Dans les cas plus complexes, comme par exemple les tableaux de structures, on appelle clef le champ servant pour le tri (par exemple le nom pour un tableau contenant nom, prénom, adresse,...). Dans ce cas, les calculs sur les clefs seront souvent plus rapides que les déplacements des structures entières. Les méthodes de tris présentées ici sont souvent utilisables également avec les autres types de données, mais les conclusions sur leur efficacité varieront. On qualifiera de stable un tri laissant dans le l'ordre initial les éléments de clef identique (par exemple, un stock saisi au fur et à mesure des arrivées de matériel, le classement par ordre alphabétique gardant les matériels de même nom dans leur ordre d'arrivée sera stable). Tous les algorithmes décrits ici sont stables, à condition d'y prendre garde (scruter le tableau du début vers la fin et non l'inverse par exemple). Dans ce chapitre, nous noterons N le nombre de composantes du tableau (appelé taille auparavant).
void tri_bulle_tus(type_tus tab, int N)
{
int ok,i;
composante tampon;
do
{
ok=1; /* vrai */
for(i=1;i<N;i++) if(tab[i-1]>tab[i])
{
ok=0;
tampon=tab[i-1];
tab[i-1]=tab[i];
tab[i]=tampon;
}
}
while(!ok);
}
Ce tri va nécessiter un grand nombre de déplacements
d'éléments, il est donc inutilisable dans les cas où ces
déplacements sont coûteux en temps. Il va nécessiter N-1
boucles principales dans le cas où le dernier élément doit
être placé en premier. Le nombre de boucles internes maximal est
donc de l'ordre de (N-1)2. Il peut par contre être
intéressant quand le tableau initial est déjà
pré-trié, les éléments n'étant pas
disposés trop loin de leur position finale (par exemple classement
alphabétique où les éléments sont
déjà triés par leur première lettre).Plutôt que de déplacer un élément dans une position meilleure que la précédente mais néanmoins mauvaise, les deux algorithmes qui suivent tentent de déplacer les éléments directement en bonne position.
void tri_insertion_tus(type_tus tab, int N)
{
int pt,ppg; /* position testée, premier plus grand */
composante tampon;
for(pt=1;pt<N;pt++)
{
ppg=0;
while(tab[ppg]<=tab[pt]&&ppg<pt)ppg++;
if(ppg<pt)
{
tampon=tab[pt];
suppr_tus(tab,&N,pt);
insert_tus(tab,&N,32767,ppg,tampon); /* je suis sur de ne pas
dépasser la dimension puisque je viens de supprimer un
élément */
}
}
}
Le nombre maximal de boucles internes est descendu à N(N-1)/2,
on a au maximum N-1 couples de suppression/insertion mais qui eux effectuent en
moyenne environ N/2 échanges d'éléments, ce qui
amène un maximum d'échanges de l'ordre de N2, ce qui
n'est pas satisfaisant. On peut néanmoins améliorer
l'implantation de cet algorithme en optimisant la recherche de la position d'un
élément dans la partie déjà triée, par
dichotomie par exemple (voir chapitre sur les recherches), ainsi qu'en
améliorant le couple suppression/insertion (ne décaler que les
éléments entre la position finale et la position initiale, par
une rotation à droite). On remplace la boucle principale par :
for(pt=1;pt<N;pt++)
{
dpg=pt-1;
tampon=tab[pt];
while(tab[dpg]>tampon&&dpg>=0)
{tab[dpg+1]=tab[dpg];dpg--;}
tab[dpg+1]=tampon;
}
Le tri par insertion peut être intéressant pour des
tableaux ayant déjà été triés, mais
où l'on a rajouté quelques nouveaux éléments en fin
de tableau (dans ce cas il faut améliorer l'implantation pour
découvrir rapidement le premier élément mal placé,
puis utiliser l'algorithme complet pour les éléments restants).
Dans les autres cas, il sera plutôt réservé aux types de
données permettant une insertion rapide (listes chaînées
par exemple).
void tri_selection_tus(type_tus tab, int N)
{
int pd,pp,i; /* place définitive, plus petit */
composante tampon;
for(pd=0;pd<N-1;pd++)
{
pp=pd;
for(i=pp+1;i<N;i++) if(tab[i]<tab[pp])pp=i;
tampon=tab[pp];
tab[pp]=tab[pd];
tab[pd]=tampon;
}
}
Chaque échange met un élément en position
définitive, l'autre par contre est mal placé. Mais aucun
échange n'est inutile. Un élément qui a été
bien placé ne sera plus testé par la suite. Le nombre de boucles
internes est environ N(N-1)/2, ce qui est meilleur que le tri bulle, mais
toujours de l'ordre de N2. Par contre le nombre de
déplacements d'éléments est au maximum de 2(N-1), la
moitié étant des déplacements nécessaires, ce qui
est faible pour un fichier en désordre total, mais n'est pas optimal
pour les fichiers dont la première partie est déjà
classée (et grande par rapport à la taille totale). Une
amélioration possible serait d'essayer de placer le second
élément de l'échange dans une position pas trop mauvaise,
à condition que cette recherche ne soit pas elle même plus
gourmande en temps.
void tri_shell_tus(type_tus tab, int N)
{
int pt,dpg,P; /* position testée,dernier plus grand */
composante tampon;
for(P=1;P<=N/9;P=3*P+1); /* calcul de P initial (<=N/9) */
for(;P>0;P/=3) /* inutile de soustraire 1 car division entière */
{
for(pt=P;pt<N;pt++)
{
dpg=pt-P;
tampon=tab[pt];
while(tab[dpg]>tampon&&dpg>=P-1)
{tab[dpg+P]=tab[dpg];dpg-=P;}
tab[dpg+P]=tampon;
}
}
}
L'intérêt de ce tri, bien qu'il ait une boucle autour du tri par
insertion, est qu'il crée rapidement un fichier presque trié, le
dernier tri par insertion sera donc beaucoup plus rapide. Il est en
général plus rapide que le tri par insertion pour les fichiers
complètement mélangés, mais pour certains tableaux et pour
certaines suites de P, il peut être bien plus mauvais que les autres tris.
void tri_rapide_tus(type_tus tab,int gauche,int droite)
{
int g,d;
composante tampon,val;
if(droite<=gauche)return; /* fin de récursivité
si tableau d'une seule case à trier */
/* choix du pivot : on prend par exemple la valeur de droite */
val=tab[droite];
g=gauche-1;
d=droite;
do
{
while(tab[++g]<val); /* g pointe le premier élément
(à gauche) plus grand (ou égal) que le pivot */
while(tab[--d]>val); /* d pointe le premier élément
(par la droite) plus petit (ou égal) que le pivot */
if(g<d) /* si g et d ne se sont pas rencontrés, on
échange les contenus de g et d et on recommence */
{tampon=tab[g];tab[g]=tab[d];tab[d]=tampon;}
}
while(g<d); /* on sort quand g a rencontré d, alors tous les
éléments à gauche de g sont <= au pivot, tous ceux
à droite de d sont >= */
/* on place le pivot en position g (d serait aussi possible), donc dans sa
bonne position (tous ceux à gauche sont <=, à droite sont >=) */
tampon=tab[g];tab[g]=tab[droite];tab[droite]=tampon;
/* il ne reste plus qu'à trier les deux parties, à droite
et à gauche du pivot */
tri_rapide_tus(tab,gauche,g-1);
tri_rapide_tus(tab,g+1,droite);
}
On appelle le tri d'un tableau complet par :
tri_rapide_tus(tableau, 0, N-1). On peut remarquer que cette
implantation du tri n'est pas stable, mais peut l'être en gérant
les égalités avec le pivot, mais en ralentissant le tri. On
effectue dans la boucle deux tests (g<d), on peut supprimer le second par
une boucle infinie et un break dans le if. Ce tri fait en moyenne 2Nlog(N)
boucles, sur des fichiers bien mélangés, mais N2 sur
un fichier déjà trié (et dans ce cas la profondeur de
récursivité est N, ce qui est prohibitif). Mais ces boucles sont
longues et gourmandes en mémoire du fait de la récursivité:
chaque appel de fonction est assez long, il faut mémoriser
l'état actuel. On peut optimiser le tri en remplaçant la
récursivité par des boucles (obligatoire si le langage
utilisé n'est pas récursif), ce qui évite d'empiler des
adresses, mais la gestion des variables locales doit être
remplacée par gestion par pile (voir plus loin) pour mémoriser
les sous-tris en attente, ce qui permettra d'accélérer le tri
mais nécessite une programmation complexe (rappel : la
récursivité sera automatiquement supprimée par le
compilateur, cette transformation par le programmateur peut être plus
efficace). Plutôt que d'arrêter la récursivité sur des sous-tableaux de taille 1, on peut s'arrêter avant (entre 5 et 25 en général) pour éviter une profondeur de récursivité trop importante. Le fichier est alors presque trié, on peut alors effectuer un tri par insertion qui dans ce cas sera très rapide. Une autre amélioration possible est de mieux choisir le pivot. la solution idéale est de trouver à chaque fois la valeur médiane du sous-tableau à trier, mais sa recherche précise rend le tri plus lent que sans elle. Une solution quelquefois utilisée est de prendre par exemple trois valeurs, pour en prendre la valeur médiane, par exemple tab[droite], tab[gauche] et tab[(droite+gauche)/2] (dans le cas d'un fichier parfaitement mélangé, le choix de trois positions n'a pas d'importance, mais dans des fichiers presque triés le choix ci-dessus est plus judicieux). La totalité de ces améliorations peut apporter un gain de l'ordre de 20% par rapport à la version de base.
int le_suivant(type_tus ti, int taille, int precedent)
{
int pos,i;
/* 1) recherche du premier égal au précédent */
pos=precedent+1;
while(pos<taille&&ti[pos]!=ti[precedent])pos++;
if(pos<taille)return(pos);
/* 2) sinon, recherche du suivant mais différent dans tout le tableau */
pos=0;
while(ti[pos]<=ti[precedent])pos++; /* le 1er > precedent */
for(i=pos+1;i<taille;i++) /*le plus petit dans la suite */
if(ti[i]>ti[precedent]&&ti[i]<ti[pos])pos=i;
return(pos);
}
void tri_creation_tus(type_tus ti, type_tus tf, int taille)
/* ti tableau initial, tf tableau final (trié) */
{
int i,imin=0;
for(i=1;i<taille;i++)if(ti[i]<ti[imin])imin=i;
tf[0]=ti[imin];
for(i=1;i<taille;i++)
{
imin=le_suivant(ti,taille,imin);
tf[i]=ti[imin];
}
}
On peut remarquer que ce tri minimise le nombre de copies des
éléments, mais nécessite beaucoup de comparaisons de clefs
(en particulier un élément déjà
sélectionné sera encore comparé par la suite). Ceci peut
être acceptable pour un fichier séquentiel à grands champs,
sur bande par exemple, mais dont les clefs peuvent être stockées
complètement en mémoire. On verra d'autres propositions dans le
cas des fichiers.
Dans la cas où les clefs sont bornées (c'est à dire comprises entre un minimum et un maximum connus à l'avance) et en nombre fini, on peut utiliser le tri basique : par exemple si toutes les clefs sont des entiers entre 000 et 999, on peut séparer le tableau en 10 parties en fonction des centaines, puis récursivement traiter les dizaines puis les unités (tri en base 10). Evidement, un tri en base 2 sera plus efficace sur ordinateur : on part à gauche ,on avance jusqu'à trouver un nombre commençant par 1, puis par la droite jusqu'à trouver un nombre commençant par 0, les échanger et continuer jusqu'à croisement des deux côtés. Puis on recommence (récursivement par exemple) sur le bit suivant, jusqu'à tri complet. Pour trier des clefs alphabétiques, on peut effectuer un tri en base 26, sur les N premiers caractères (N pouvant valoir 2 ou 3 par exemple), le fichier est alors presque trié. Il est alors plus efficace d'effectuer un tri par insertion (passe de finition) plutôt que de répéter le tri basique jusqu'à tri complet.
Le tri par fusion utilise un algorithme de fusion de deux tableaux triés en un seul plus grand, appelé récursivement sur les deux moitiés du tableau, jusqu'à une taille de tableau de 1 (ou plus, avec un tri spécifique pour petits tableaux, par exemple par échange sur des sous-tableaux de 3 éléments)
int rech_sequentielle_tus(type_tus tab, int N, composante val)
/* rend -1 si val non trouvée, première occurence trouvée sinon */
{
int i;
for(i=0;i<N;i++)if(tab[i]==val)return(i);
return(-1);
}
int rech_dichotomie_tus(type-tus tab, int N, composante val)
{
int g,m,d; /* gauche, milieu, droite */
g=0;d=N;
while (g<=d)
{
m=(g+d)/2; /* division entière */
if(val<tab[m])d=m-1;
else if(val>tab[m])g=m+1;
else return(m)
}
return(-1);
}
L'utilisation de la variable m permet d'éviter plusieurs
calculs de (g+d)/2. Dans certains cas il peut être intéressant de
prévoir également une mémorisation de tab[m], mais pas
pour les tableaux puisqu'ils permettent d'accès direct. L'ordre des
tests est important, l'égalité ayant statistiquement moins de
chances, elle doit être traitée en dernier (donc faire le maximum
de tests dans le cas le moins probable). Si on avait traité
l'égalité en premier, tous les autres cas auraient
nécessité deux tests, l'égalité puis la
sélection de la partie droite ou gauche. En cas de multiples
éléments correspondants à la valeur cherchée, on
retourne la position de l'un d'eux, mais pas nécessairement le premier
ou le dernier. Pour retourner le premier par exemple, il suffit de rajouter une
boucle testant l'égalité vers la gauche, à n'effectuer
qu'une seule fois bien évidement, lorsque une valeur adéquate a
été localisée. On peut améliorer l'algorithme en
comparant val à tab[g] et tab[d], pour estimer la position
recherchée plutôt que de la supposer au milieu, comme on effectue
une recherche dans un dictionnaire :
m=g+(int)((val-tab[g])*(d-g)/(tab[d]-tab[g])). Attention, ce calcul se
fait sur des composantes (par exemple des flottants), ce qui est toujours plus
long que de simples calculs sur des entiers.
Les tableaux unidimensionnels permettent de résoudre simplement divers problèmes mathématiques. Nous allons en traiter certains.
L'interpolation polynomiale correspond elle à la recherche d'une courbe polynomiale passant par N+1 points donnés : P(xi)=yi pour i entre 0 et N. La solution la plus simple consiste à choisir le polynôme de Lagrange (d'ordre N):
N
|
N
|
|||
| P(x)=
|
|
(
yj
|
|
(x-xi)/(xj-xi)
)
|
| j=0
|
i=0
i!=j
|
Outre les tableaux de chaînes de caractères, les tableaux multidimensionnels les plus utilisés sont les matrices Les algorithmes de base du calcul matriciel (base_mat) sont la mise à 0, la recopie, l'addition et le produit de matrices, qui sont simples à mettre en place (le produit entraîne néanmoins N3 multiplications, des algorithmes plus performants existent mais ne commencent à être rentables que pour N très grand, entre 10000 et un million !).
Par contre, le problème de l'inversion d'une matrice est plus complexe. Elle est utilisée principalement pour la résolution de N équations à N inconnues, représentées par une matrice NxN. La méthode de Gauss est certainement la plus simple à mettre en oeuvre, bien que pouvant poser problème dans certains cas particuliers. On utilise en fait la méthode de résolution d'un système d'équations A.X=B par substitution. Nous allons le préciser sur un exemple :
1
|
1
|
-2
|
x1
|
2
|
|||||||||
| 1
|
3
|
-4
|
*
|
x2
|
=
|
6
|
|||||||
| -1
|
-2
|
6
|
x3
|
-1
|
|||||||||
| A
|
X
|
B
|
1
|
1
|
-2
|
x1
|
2
|
|||||||||
| 0
|
2
|
-2
|
*
|
x2
|
=
|
4
|
|||||||
| -1
|
-2
|
6
|
x3
|
-1
|
1
|
1
|
-2
|
x1
|
2
|
|||||||||
| 0
|
2
|
-2
|
*
|
x2
|
=
|
4
|
|||||||
| 0
|
0
|
1
|
x3
|
1
|
void gauss_triangulation_simpliste(type_mat A,type_mat B, int N)
/* A de taille (N,N), B (N,1). On aurait pu gagner de la place en prenant B
tableau unidimensionnel, ou même le rajouter en colonne N de A */
{
int ce,l,c;
composante coef;
for(ce=0;ce<N-1;ce++) /* ce=col à effacer (dans les lignes SUIVANTES) */
for(l=ce+1;l<N;l++) /* pour chaque ligne au dessous */
{
coef=A[l][ce]/A[ce][ce];
A[l][ce]=0; /* normalement pas besoin de le calculer */
for(c=ce+1;c<N;c++) A[l][c]-=coef*A[ce][c];
B[l][0]-=coef*B[ce][0];
}
}
Si ces substitutions font apparaître une ligne de 0, soit le
système admet une infinité de solutions (0=0, une ligne est une
combinaison linéaire des autres), soit aucune (0=N). Mais cette
méthode n'est pas directement applicable pour des coefficients
réels (ou du moins flottants). En effet, si les substitutions
précédentes ont amené un coefficient nul, on obtient une
division par zéro. S'il est proche de 0, l'utilisation de ce coefficient
pour en annuler d'autres nécessitera un multiplicateur très
grand, ce qui entraînera une multiplication importante de l'erreur
inhérente à l'utilisation de réels et donc un
résultat faux (en fait on se trouvera en présence de coefficients
d'ordre de grandeur très différent, et donc les petits
deviendront négligeables devant l'erreur sur les très grands). La
solution est de ne pas traiter les lignes dans l'ordre mais pour une colonne
donnée, choisir pour celle qui aura son premier terme non nul celle dont
ce terme est le plus grand (on l'appelle le pivot).
Il suffit alors d'échanger la ligne que l'on veut traiter avec la ligne
contenant le pivot (échanger des lignes d'un système
d'équations ne modifie pas la solution) (gauss):
void gauss_triangulation(type_mat A,type_mat B, int N)
{
int ce,l,c,lpivot;
composante coef;
for(ce=0;ce<N-1;ce++) /* ce=colonne à effacer */
{
/*Recherche du pivot le + grand possible (dans les lignes qui restent)*/
lpivot=ce;
for(l=ce+1;l<N;l++)if(fabs(A[l][ce])>fabs(A[lpivot][ce]))lpivot=l;
/*Echange de la ligne du pivot et de la ligne ce (ne pas oublier B)*/
for(c=ce;c<N;c++) /*tous les termes devant ce sont nuls*/
{coef=A[ce][c];A[ce][c]=A[lpivot][c];A[lpivot][c]=coef;}
coef=B[ce][0];B[ce][0]=B[lpivot][0];B[lpivot][0]=coef;
/*Suite de l'algorithme, comme le cas simpliste */
for(l=ce+1;l<N;l++) /* pour chaque ligne au dessous */
{
coef=A[l][ce]/A[ce][ce];
A[l][ce]=0;
for(c=ce+1;c<N;c++)
A[l][c]-=coef*A[ce][c];
B[l][0]-=coef*B[ce][0];
}
}
}
Une fois la matrice A triangulée,
il ne reste plus qu'à déterminer la matrice colonne solution X:
void gauss_resolution(type_mat A,type_mat B,type_mat X,int N)
{
int l,c;
composante tampon;
for(l=N-1;l>=0;l--)
{
tampon=B[l][0];
for(c=l+1;c<N;c++)tampon-=A[l][c]*X[c][0];
X[l][0]=tampon/A[l][l];
}
}
Remarque : on pourrait retourner le résultat dans B (si
l'utilisateur désire le garder, il lui suffirait de le copier avant).
Ceci économise le tableau X et le tampon.D'autres algorithmes existent, mais ils ne sont plus efficaces que Gauss que pour de très grosses matrices. Mais souvent les grosses matrices possèdent des propriétés particulières nécessitant d'utiliser d'autres structures de données que les tableaux à 2 dimensions (en cas de matrices triangulaires, symétriques, bandes, en "ligne de ciel", creuses..., voir paragraphe 11.3.2), pour lesquelles Gauss n'est pas la meilleure solution, car la triangulation supprime ces propriétés.