Les tableaux présentent également un intérêt dans le traitement de problèmes décisionnels. Ils permettent de présenter de manière concise tout un ensemble de combinaisons de conditions qui, si elles sont satisfaites, impliquent qu'une combinaison d'actions définies est exécutée.
Lorsqu'un grand nombre de combinaisons de conditions peut se présenter
et qu'un vaste choix de combinaisons d'actions se présente, alors
les tables de décisions permettent de gérer efficacement cette
complexité. De plus, elles offrent le cadre nécessaire pour
vérifier les propriétés importantes des systèmes
décisionnels, à savoir :
Références :
K. LONDON,
"Decision tables : A Practical Approach for Data Processing"
Auerbach, Princeton, N.J, 1972.
(bonne monographie).
U.W. POOCH,
"Translation of Decision Tables"
Computing Surveys, vol. 6, No. 2, pp. 125-151, juin 1974.
Les tables de décision sont formées de trois composantes : les conditions, les règles et les actions. On peut les schématiser ainsi :
Fig. 15.1. Exemple de table de décision.
Cette table est divisée en quatre parties par les épaisses lignes verticales et horizontales. La partie en haut à gauche est appelée énoncé des conditions, la partie en bas à gauche est appelée énoncé des actions, la partie en haut à droite est appelée indicateurs de conditions (peuvent être "O" pour oui, "N" pour non et "-" pour peu importe) et la partie en bas à droite est appelée indicateurs d'actions (peuvent être soit blanc pour ne pas exécuter l'action ou X pour l'exécuter).
Fig. 15.2. Table étendue correspondant à la table de la figure 15.1.
Une table, dont certains indicateurs sont des "-" peut être trans formée en une table ne contenant pas d'indicateur "peu importe" (table étendue). Pour ce faire, il suffit de duplifier la colonne contenant un "-", de remplacer le "-" par un "O" dans une des deux copies et par un "N" dans l'autre. On réitère le processus jusqu'à ce qu'il n'y ait plus de "-" dans la table. Pour l'exemple de la figure 15.1, l'on obtient alors la table de la figure 15.2.
Plusieurs tables condensées différentes peuvent aboutir à la même table étendue. Ainsi, la table de la figure 15.1 n'est pas la seule table qui permette d'obtenir la figure 15.2, la figure suivante (figure 15.3) donne aussi le même résultat :
Fig. 15.3. Autre exemple de table condensée aboutissant aussi à la table étendue de la figure 15.2.
Cela vient du fait qu'un ensemble de règles ayant les mêmes actions peuvent être combinées de diverses manières pour obtenir des tables condensées. La méthode qui produit le plus de "-" produira la table la plus condensée.
Au vu des exemples précédents, il est facile de définir
les concepts de complétude, de cohérence et de redondance :
Une règle simple ne contient que des "O" et des "N". Une règle composite contient aussi des "-". Une règle composite R1 recouvre une règle R2 si l'extension de la règle R1 (suppression des "-") et l'extension de la règle R2 ont une ou plusieurs colonne(s) en commun.
Exemple
Fig. 15.4. Exemple de règles se recouvrant.
La règle 1 et la règle 2 se recouvrent car la règle 1 peut être étendue aux règles 1a et 1b, or la règle 1a est identique à la règle 2. Dans ce cas précis, le recouvrement est redondant car la règle 1a implique les mêmes actions que la règle 2. De même, la règle 2 et la règle 3 se recouvrent car une des extensions de la 2 (la 2a) a les mêmes indicateurs de conditions que l'une des extensions de la règle 3 (3b). Seulement là, les indicateurs d'actions diffèrent. Le recouvrement est donc incohérent.
Jusqu'à présent, les exemples que nous avons vus supposaient
que les conditions énumérées étaient toutes
indépendantes les unes des autres. Il se peut, cependant, que l'on
désire avoir des conditions qui soient liées. Par exemple,
on pourrait avoir C1 = "Age < 20",
C2 = "Age [15,30]",
C3 = "Age > 50". Dans ce cas, il y a risque
d'incohérence, y compris à l'intérieur d'une même
règle (par exemple si l'on a "O" pour C1 et C3
simultanément). Cela peut aussi aboutir à une table ambiguë,
si une même donnée peut satisfaire deux règles ayant
des indicateurs d'actions différents (par exemple, en reprenant les
mêmes conditions C1, C2 et C3 que
ci-dessus, si une règle avec des indicateurs de conditions valant
(O, O, N) avait des indicateurs d'actions différents d'une autre
règle ayant des indicateurs de conditions valant (N, O, N), les deux
règles seraient ambiguë pour toute personne d'un âge compris
entre 15 et 20 ans).
La structure de donnée à utiliser pour construire une table de décision peut se présenter sous diverses formes en fonction des caractéristiques de la table de décision. Ainsi, une table étendue (ne comportant pas d'indicateurs de conditions "-") permet l'utilisation d'une matrice de booléens pour stocker la valeur des indicateurs de condition, alors que dans l'exemple qui suit, il est fait usage d'un type énuméré pour représenter une condition :
const MaxNbCond = ...;
MaxNbRegles = ...;
MaxNbActions = ...;
type Condition =(Vrai, Faux, Indetermine);
ValeurCas = Vrai..Faux;
TableDecision = record
NbConditions: 1..MaxNbCond;
NbRegles: 1..MaxNbRegles;
ValCond: array[1..MaxNbRegles,
1..MaxNbCond]
of Condition;
NbActions: 1..MaxNbActions;
Agir: array[1..MaxNbRegles,
1..MaxNbActions]
of boolean;
TxtConditions:array[1..MaxNbCond]
of string[30];
TxtActions:array[1..MaxNbActions]
of string[30];
end; { TableDecision }
CasReel = array[1..MaxNbCond]
of ValeurCas;
procedure Traitement(Cas:CasReel;
Table:TableDecision);
{ cette procédure se charge de déterminer
quelles règles de la table de décisions
sont applicable au cas à traiter et
d'exécuter à chaque fois les actions
associées. }
var Regle, Action, Cond: integer;
Applicable: boolean;
begin { Traitement }
with Table do begin
for Regle := 1 to NbRegles do begin
Applicable := true;
for Cond := 1 to NbCond do
Applicable := Applicable and
((Cas[Cond]=ValCond[Regle,Cond]) or
(ValCond[Regle,Cond]=Indetermine));
if Applicable then
{ si la règle courante est applicable,
exécuter les actions corresp. }
for Action := 1 to NbActions do
if Agir[Regle,Action] then
case Action of
1: Action1;
...
end; { case }
end; { for Regle }
end; { with }
end; { Traitement }
Dans cet exemple, on a supposé que les différentes actions
associées aux règles étaient suffisamment complexes
pour nécessiter l'élaboration d'une procédure par action.
Dans un tel cas, Modula 2 offrirait plus de souplesse pour l'activation des
actions. On pourrait en effet remplacer l'instruction "case Action
of ..." par un appel d'une composante d'un tableau de procédures
:
InvoqueAction[Action];
si l'on suppose que InvoqueAction est un champ de l'enregistrement TableDecision déclaré comme array[1..MaxNbactions] of procedure.
On peut aussi supposer, comme alternative, que l'on dispose d'un interpréteur d'actions et que l'exécution d'une action revient à invoquer l'interpréteur en lui passant en paramètre le texte de l'action. L'instruction "case" serait alors remplacée par :
Interpret(TxtAction[Action]);
Les tables dont les indicateurs de conditions sont limités aux valeurs "O", "N" et "-" sont dites tables à indicateurs limités. On peut généraliser la notion de table de décision en étendant les indicateurs à des nombres entiers pour obtenir des tables généralisées. Une signification est alors associée à chaque valeur possible.
Un tel exemple de table généralisée est illustré dans la figure 15.5. Dans cette figure, la colonne "autre" correspond aux actions à exécuter si aucune des autres règles ne peut être activée.
Exemple
Fig. 15.5. Choix du pourboire dans un restaurant.
Une table généralisée peut être transformée en une table limitée. Il suffit pour cela de considérer comme des conditions booléennes sé parées l'égalité avec chaque valeur possible d'une condition pouvant avoir plusieurs valeurs. Pour l'exemple vu plus haut, cela donnerait :
C1 : qualité du service excellent
C2 : qualité du service bon
C3 : qualité du service passable
etc...
Une fois qu'une table de décision a été réalisée, il faut pouvoir programmer les règles qui la composent. Nous avons vu précédemment un exemple de structure de donnée ainsi qu'une procédure de traitement correspondante. Une autre technique possibles consiste à convertir ces règles en une cascade de tests utilisant les conditions énumérées dans la table. Cette technique est la suivante :
Soit C une matrice de n lignes représentant les indicateurs des n
conditions d'une table de décision (n>1). On répète
les actions suivantes :
in
Ce processus peut être illustré par la figure 15.6. Dans cette illustration, seuls les losanges contenant les conditions sont significatifs. Les matrices intermédiaires y ont été ajoutées uniquement pour améliorer la compréhension. De même, les règles indiquées dans les feuilles signifient que les actions correspondantes peuvent être invoquées.
Fig. 15.6. Exemple de conversion en cascade de tests.
Il est évident que si l'on traite les conditions dans un ordre différent, on obtiendra une cascade différente. La figure 15.7 illustre une autre possibilité obtenue à partir de la même table initiale.
Fig. 15.7. Cascade de tests équivalente à celle de la fig. 15.6.
Indépendamment de toute implantation sur ordinateur, ces conversions peuvent être effectuées à la main par un programmeur pour écrire la cascade de tests (if then else) correspondante et, ainsi, invoquer les actions correspondant à chaque chemin. On obtient alors une instruction composée du genre :
if C1 then
if C2 then
if C3 then
{ activer règle corresp. à (O,O,O) }
else
{ activer règle corresp. à (O,O,N) }
else if C3 then
{ activer règle corresp. à (O,N,O) }
else
{ activer règle corresp. à (O,N,N) }
else if C2 then
if C3 then
{ activer règle corresp. à (N,O,O) }
else
{ activer règle corresp. à (N,O,N) }
else if C3 then
{ activer règle corresp. à (N,N,O) }
else
{ activer règle corresp. à (N,N,N) }
Cela a l'inconvénient de figer la table dans le programme. Pour plus
de flexibilité, on peut envisager de construire un tableau d'entiers
à 2NbConditions entrées qui correspondront aux feuilles
de l'arborescence de conditions. La déclaration pourrait être
: array[ boolean, boolean, boolean] of 1..MaxNbRegles, pour
une table à trois conditions; Le i-ème indice correspondrait
à la i-ème condition. Ceci est toutefois difficilement envisageable
si l'on ne connaît pas à l'avance le nombre de conditions de
la table de décision à traiter. On a donc meilleur temps de
déclarer un indice entier et sélectionner, pour un cas donné,
la composante correspondant à la formule :
| NbConditions | = indice de la composante du tableau contenant le numéro de règle correspondant au cas donné | ||
| 2i-1*ord(Ci) | |||
| i=1 | |||
Cela donne les déclarations et la procédure de traitement suivants :
program TableDeDecision;
const MaxNbCond = 5;
MaxNbRegles = 32;
MaxNbActions = 5;
MaxCasDiff = 32; { 2**MaxNbCond }
type TableDecision = record
NbConditions: 1..MaxNbCond;
NbRegles: 1..MaxNbRegles;
Indicateurs: array[1..MaxCasDiff]
of 1..MaxNbRegles;
NbActions: 1..MaxNbActions;
Agir: array[1..MaxNbRegles,
1..MaxNbActions]
of boolean;
TxtConditions: array[1..MaxNbCond]
of string[30];
TxtActions: array[1..MaxNbActions]
of string[30];
end; { TableDecision }
StrConditions = string[MaxNbCond];
StrActions = string[MaxNbActions];
CasReel = StrConditions;
var Table: TableDecision;
Cas: CasReel;
F: text;
function Indice(S:StrConditions): integer;
{ permet de déterminer quelle règle cor-
respond aux indicateurs de condition
fournis en paramètre }
var I, Resultat: integer;
begin
Resultat := 0;
for I := 1 to length(S) do
Resultat:=Resultat*2 + ord(S[I]='O');
Indice := Resultat;
end; { Indice }
procedure Lecture(
var Table: TableDecision);
var R: 1..MaxNbRegles;
C: 1..MaxNbCond;
A: 1..MaxNbActions;
IndicCond: string[MaxNbCond];
IndicActions: string[MaxNbActions];
procedure EntreIndicateurs(
IndicCond:StrConditions;
Regle:integer);
var I: integer;
begin
I := pos('-', IndicCond);
if I = 0 then
Table.Indicateurs
[Indice(IndicCond)] := Regle
else begin
IndicCond[I] := 'O';
EntreIndicateurs(IndicCond,Regle);
IndicCond[I] := 'N';
EntreIndicateurs(IndicCond,Regle);
IndicCond[I] := '-';
end;
end; { EntreIndicateurs }
procedure EntreActions(
IndicActions:StrActions;
Regle: integer);
var I: integer;
begin
with Table do
for I:=1 to length(IndicActions) do
Agir[Regle,I]:=IndicActions[I]='X';
end; { EntreActions }
begin { Lecture }
assign(F,'NomDuFichierExterne');
reset(F);
with Table do begin
readln(F,NbConditions, NbRegles,
NbActions);
for C := 1 to NbConditions do
readln(F,TxtConditions[C]);
for A := 1 to NbActions do
readln(F,TxtActions[A]);
for R := 1 to NbRegles do begin
readln(F,IndicCond);
readln(F,IndicActions);
EntreIndicateurs(IndicCond,R);
EntreActions(IndicActions,R);
end; { for }
end; { whith }
end; { Lecture }
procedure Traitement(Cas: CasReel;
Table: TableDecision);
var Regle, Action: integer;
begin
with Table do begin
Regle := Indicateurs[Indice(Cas)];
write('il faut executer les actions');
for Action := 1 to NbActions do
if Agir[Regle,Action] then
writeln(TxtActions[Action]);
writeln;
end; { with }
end; { Traitement }
begin { programme principal }
Lecture(Table);
Cas := '';
for C:=1 to Table.NbConditions do begin
writeln(TxtConditions[C],'(O/N)');
insert(' ',Cas,C);
readln(Cas[C]);
end; { for }
Traitement(Cas,Table);
end. { TableDeDecision }
15.2. Arbres de
décision
Site Hosting: Bronco
Table des
matières.