Bonjour,

J'ai établi une table de vérité et j'aimerais en déduire un code réduit
(factorisé) mais je ne me souviens plus comment procéder. Pouvez-vous
m'aider ?

J'ai relu un peu de théorie sur les diagrammes de Karnaugh et d'algèbre
de Bool mais je ne sais pas très bien concrètement comment les appliquer
dans ce cas lÃ***.

Il y a 4 entrées booléennes et 5 sorties possibles dont une non utilisée.

Je recherche le code le plus factorisé (sans redondances) qui serait comme :

Si condition1
alors sortie 1 (OK)
sinon si condition2
alors sortie 2 (EN)
sinon si condition3
alors sortie 3 (SU)
sinon sortie 4 (AN)
finsi
finsi
finsi

la sortie 5 (ND) n'étant pas utilisée

Voici la table de vérités :

Table de vérités :
+-----------------------+---------+
| Entrées | Sorties |
+-----+-----+-----+-----+---------+
| DFI | DFT | DDS | DFS | et |
+-----+-----+-----+-----+---------+
| NON | NON | NON | NON | EN |
+-----+-----+-----+-----+---------+
| NON | NON | NON | OUI | ND |
+-----+-----+-----+-----+---------+
| NON | NON | OUI | NON | SU |
+-----+-----+-----+-----+---------+
| NON | NON | OUI | OUI | EN |
+-----+-----+-----+-----+---------+
| NON | OUI | NON | NON | OK |
+-----+-----+-----+-----+---------+
| NON | OUI | NON | OUI | ND |
+-----+-----+-----+-----+---------+
| NON | OUI | OUI | NON | AN |
+-----+-----+-----+-----+---------+
| NON | OUI | OUI | OUI | OK |
+-----+-----+-----+-----+---------+
| OUI | NON | NON | NON | OK |
+-----+-----+-----+-----+---------+
| OUI | NON | NON | OUI | ND |
+-----+-----+-----+-----+---------+
| OUI | NON | OUI | NON | AN |
+-----+-----+-----+-----+---------+
| OUI | NON | OUI | OUI | OK |
+-----+-----+-----+-----+---------+
| OUI | OUI | NON | NON | OK |
+-----+-----+-----+-----+---------+
| OUI | OUI | NON | OUI | ND |
+-----+-----+-----+-----+---------+
| OUI | OUI | OUI | NON | AN |
+-----+-----+-----+-----+---------+
| OUI | OUI | OUI | OUI | OK |
+-----+-----+-----+-----+---------+

--
Léa Gris

On Tue, 15 Jan 2008 14:32:25 +0100, Lea GRIS :

>J'ai relu un peu de théorie sur les diagrammes de Karnaugh et d'algèbre
>de Bool mais je ne sais pas très bien concrètement comment les appliquer
>dans ce cas là.

Si tu fais le diagramme de Karnaugh de ta table, tu obtiens :

DDS DFS DFI DFT
00 01 11 10
00 EN OK OK OK
01 ND ND ND ND
11 EN OK OK OK
10 SU AN AN AN

Effectivement, en applicant directement la méthode usuelle, on
n'obtient à peu près rien.

Toutefois, sur cette table on lit directement l'algorithme suivant :

if (DDS == DFS)
{
if (DFI == 0 && DFT == 0)
{
return EN;
}
else
{
return OK;
}
}
else if (DDS == 0)
{
return ND;
}
else
{
if (DFI == 0 && DFT == 0)
{
return SU;
}
else
{
return AN;
}
}

Je ne sais pas trop si ça répond à ta question, mais je ne pense pas
qu'on puisse faire plus simple.

Fabien LE LEZ a écrit :
> On Tue, 15 Jan 2008 14:32:25 +0100, Lea GRIS :
>
>> J'ai relu un peu de théorie sur les diagrammes de Karnaugh et d'algèbre
>> de Bool mais je ne sais pas très bien concrètement comment les appliquer
>> dans ce cas là.
>
> Si tu fais le diagramme de Karnaugh de ta table, tu obtiens :
>
> DDS DFS DFI DFT
> 00 01 11 10
> 00 EN OK OK OK
> 01 ND ND ND ND
> 11 EN OK OK OK
> 10 SU AN AN AN
>
> Effectivement, en applicant directement la méthode usuelle, on
> n'obtient à peu près rien.

Merci à toi Fabien, c'était un peu mon impression aussi ou alors j'ai
trop perdu de mes cours d'informatique d'il y a 20 ans

En fait je cherchais une approche de factorisation purement algébrique
par-ce que les diagrammes de Karnaugh ne sont pas évident à interpréter.
Faire des groupes de 8, 4, 2 sorties dans le cas présent et trouver des
intersections de ces groupes... faut avoir l'oeil.

Autrement :
Quelqu'un m'a soumis une alternative intéressante en utilisant
directement une table.
Je la retranscris ici en C99 :

#include <stdbool.h>

/* représentations binaire des différentes valeurs d'entrée
* en vue de leur assemblage comme index entier
*/
#DEFINE DFI 0x01
#DEFINE DFT 0x02
#DEFINE DDS 0x04
#DEFINE DFS 0x08

/* les différentes valeurs de sorties,
* ce sont des chaînes de caractères mais il serait aussi
* possible d'y ranger des pointeurs vers la fonction
* à appeler conditionnellement à la valeur d'index
*/
static char * sorties[ ] = { "OK","EN","SU","AN","ND" };

/* Table de vérités */
static unsigned int * verites[ ] = {1,4,2,1,0,4,3,0,0,4,3,0,0,4,3,0};

char * gettest(bool dfi,dft,dds,dfs)
{
/* Assemble l'index entier avec les valeurs binaires conditionnelles
* et retourne la valeur de sortie trouvée dans la table de verites
*/
return(&sorties[(dfi ? DFI : 0)
& (dft ? DFT : 0)
& (dds ? DDS : 0)
& (dfs ? DFS : 0)]);
}

Cependant j'ignore si implémenter un index en assemblant des valeurs
binaires est plus ou moins coûteux en temps de réponse qu'implémenter
une suite de comparaisons algorithmiques.

De plus, l'indexation d'une table de vérité resterait-elle plus
avantageuse lorsque la complexité des conditions augmente en
considération d'un environnement moderne (cache L1-L2, pipelining,
prédictions des branchements, RAM significativement plus lente que le
CPU...).

L'approche tabulaire est séduisante de simplicité, mais as-t'elle un
sens ou est-ce une optimisation prématurée ?


>
> Toutefois, sur cette table on lit directement l'algorithme suivant :
>
> if (DDS == DFS)
> {
> if (DFI == 0 && DFT == 0)
> {
> return EN;
> }
> else
> {
> return OK;
> }
> }
> else if (DDS == 0)
> {
> return ND;
> }
> else
> {
> if (DFI == 0 && DFT == 0)
> {
> return SU;
> }
> else
> {
> return AN;
> }
> }
>
> Je ne sais pas trop si ça répond à ta question, mais je ne pense pas
> qu'on puisse faire plus simple.
>

On Tue, 15 Jan 2008 18:02:02 +0100, Lea GRIS :


>static char * sorties[ ] = { "OK","EN","SU","AN","ND" };

Je préférerais un
static char* sorties[2][2][2][2]= ...

>char * gettest(bool dfi,dft,dds,dfs)
>{
return sorties [dfi][dft][dds][dfs];

Mais bon, c'est un détail.

>De plus, l'indexation d'une table de vérité resterait-elle plus
>avantageuse lorsque la complexité des conditions augmente en
>considération d'un environnement moderne (cache L1-L2, pipelining,
>prédictions des branchements, RAM significativement plus lente que le
>CPU...).

Franchement, vu la complexité des architectures récentes, on ne peut
pas savoir. Faut implémenter les deux méthodes et faire des tests de
performances.
Et la plupart du temps, les tests indiquent que la différence réelle
est très faible en pratique, et qu'il vaut mieux pondre le code le
plus lisible.

Fabien LE LEZ a écrit :
> On Tue, 15 Jan 2008 18:02:02 +0100, Lea GRIS :
>
>
>> static char * sorties[ ] = { "OK","EN","SU","AN","ND" };
>
> Je préférerais un
> static char* sorties[2][2][2][2]= ...
>
>> char * gettest(bool dfi,dft,dds,dfs)
>> {
> return sorties [dfi][dft][dds][dfs];
>
> Mais bon, c'est un détail.
>
>> De plus, l'indexation d'une table de vérité resterait-elle plus
>> avantageuse lorsque la complexité des conditions augmente en
>> considération d'un environnement moderne (cache L1-L2, pipelining,
>> prédictions des branchements, RAM significativement plus lente que le
>> CPU...).
>
> Franchement, vu la complexité des architectures récentes, on ne peut
> pas savoir. Faut implémenter les deux méthodes et faire des tests de
> performances.
> Et la plupart du temps, les tests indiquent que la différence réelle
> est très faible en pratique, et qu'il vaut mieux pondre le code le
> plus lisible.

Comme le code que j'ai publié hier était cochon et erroné, je remet ici
un code propre et qui fonctionne. J'espère pouvoir bientôt comparer les
deux algorithmes. En attendant voici la version avec table :

#include <stdbool.h>
#include <string.h>
#include <stdio.h>

/* Représentations binaires des différentes valeurs d'entrées
* en vue de leur assemblage comme index entier.
*/
#define DFI 0x01
#define DFT 0x02
#define DDS 0x04
#define DFS 0x08

/* Les différentes valeurs de sorties sont des chaînes
* de caractères mais il serait aussi possible d'y ranger
* des pointeurs vers la fonction à appeler conditionnellement
* à la valeur d'index.
*/
static char *sorties[] = { "OK", "En cours", "Suspendu", "Annulé", "N-D" };

/* Table de vérités */
static unsigned int verites[] =
{ 1, 0, 0, 0, 2, 3, 3, 3, 4, 4, 4, 4, 2, 0, 0, 0 };

char *
dotest1 (bool dfi, bool dft, bool dds, bool dfs)
{
/* Assemble l'index entier avec les valeurs binaires conditionnelles
* et retourne la valeur de sortie trouvée dans la table de verites
*/
int i =
(dfi ? DFI : 0) | (dft ? DFT : 0) | (dds ? DDS : 0) | (dfs ? DFS : 0);

/* Le code suivant serait équivalent tant que l'implémentation
* du type bool vaut 0 pour faux et 1 pour vrai.
* En pratique je ne sais pas si c'est fiable et cela n'apporte
* aucune optimisation algorithmique.
* Je le laisse en exemple :
*
* i = dfi*DFI | dft*DFT | dds*DDS | dfs*DFS;
*/
int verite = verites[i];
return (sorties[verite]);
}

int
main (int argc, char *argv[])
{
int i;
bool dfi = false;
bool dft = false;
bool dds = false;
bool dfs = false;

for (i = 1; i < argc; i++)
{
if (strncasecmp ("DFI", argv[i], 3) == 0)
dfi = true;
if (strncasecmp ("DFT", argv[i], 3) == 0)
dft = true;
if (strncasecmp ("DDS", argv[i], 3) == 0)
dds = true;
if (strncasecmp ("DFS", argv[i], 3) == 0)
dfs = true;
};

printf ("DFI %s\n", (dfi ? "VRAI" : "FAUX"));
printf ("DFT %s\n", (dft ? "VRAI" : "FAUX"));
printf ("DDS %s\n", (dds ? "VRAI" : "FAUX"));
printf ("DFS %s\n", (dfs ? "VRAI" : "FAUX"));

printf ("Résultat : %s\n", dotest1 (dfi, dft, dds, dfs));
return (0);
}

--
Léa Gris

On Wed, 16 Jan 2008 00:06:15 +0100, Lea GRIS

> J'espère pouvoir bientôt comparer les deux algorithmes

Il faut bien sûr les comparer in situ, dans le programme final.
Par exemple, si la fonction renvoie une chaîne de caractères, et que
cette chaîne est analysée (ou, pire, envoyée à l'écran ou dans un
fichier), les performances de la fonction dotest1() auront bien peu
d'importance...

Lea GRIS wrote:

> Bonjour,
>
> J'ai établi une table de vérité et j'aimerais en déduire un code réduit
> (factorisé) mais je ne me souviens plus comment procéder. Pouvez-vous
> m'aider ?
>
> J'ai relu un peu de théorie sur les diagrammes de Karnaugh et d'algèbre
> de Bool mais je ne sais pas très bien concrètement comment les appliquer
> dans ce cas lÃ***.
>
> Il y a 4 entrées booléennes et 5 sorties possibles dont une non utilisée.
>
> Je recherche le code le plus factorisé (sans redondances) qui serait comme :
>
> Si condition1
> alors sortie 1 (OK)
> sinon si condition2
> alors sortie 2 (EN)
> sinon si condition3
> alors sortie 3 (SU)
> sinon sortie 4 (AN)
> finsi
> finsi
> finsi
>
> la sortie 5 (ND) n'étant pas utilisée
>
> Voici la table de vérités :
>
> Table de vérités :
> +-----------------------+---------+
> | Entrées | Sorties |
> +-----+-----+-----+-----+---------+
> | DFI | DFT | DDS | DFS | et |
> +-----+-----+-----+-----+---------+
> | NON | NON | NON | NON | EN |
> +-----+-----+-----+-----+---------+
> | NON | NON | NON | OUI | ND |
> +-----+-----+-----+-----+---------+
> | NON | NON | OUI | NON | SU |
> +-----+-----+-----+-----+---------+
> | NON | NON | OUI | OUI | EN |
> +-----+-----+-----+-----+---------+
> | NON | OUI | NON | NON | OK |
> +-----+-----+-----+-----+---------+
> | NON | OUI | NON | OUI | ND |
> +-----+-----+-----+-----+---------+
> | NON | OUI | OUI | NON | AN |
> +-----+-----+-----+-----+---------+
> | NON | OUI | OUI | OUI | OK |
> +-----+-----+-----+-----+---------+
> | OUI | NON | NON | NON | OK |
> +-----+-----+-----+-----+---------+
> | OUI | NON | NON | OUI | ND |
> +-----+-----+-----+-----+---------+
> | OUI | NON | OUI | NON | AN |
> +-----+-----+-----+-----+---------+
> | OUI | NON | OUI | OUI | OK |
> +-----+-----+-----+-----+---------+
> | OUI | OUI | NON | NON | OK |
> +-----+-----+-----+-----+---------+
> | OUI | OUI | NON | OUI | ND |
> +-----+-----+-----+-----+---------+
> | OUI | OUI | OUI | NON | AN |
> +-----+-----+-----+-----+---------+
> | OUI | OUI | OUI | OUI | OK |
> +-----+-----+-----+-----+---------+
>
Cherche l'algorithme de Quine Mac Cluskey.
Par exemple Ã*** partir de wikipedia (anglais...) :
http://en.wikipedia.org/wiki/Quine-McCluskey_algorithm