262080481

1.5.2. Wyznaczenie tablicy minimalnych pokryć M

Tablicę pokryć minimalnych M (tab. 9) wyznacza się w następujący sposób: w macierzy porównań M wyszukujemy wszystkie możliwe kombinacje kolumn, gdzie w każdym wierszu wystąpi co najmniej jedna jedynka, przy czym powinna to być jak najmniejsza liczba kolumn, która spełnia ten warunek. W poniższym przykładzie mamy dwie możliwe kombinacje: kolumny a, b oraz b, d.

Tabela 9 Minimalne liczby kolumn pokrywających macierz M (a,b oraz b,d) [5]

a b h 0 1 0 1	c d a Ol 1 0 0 0 0 1 o	b 0 1 1	c d 0 1 0 0 0 1
i i i i	0 1 1 ii i	1 1	0 1 1 1

Następnie każdą kombinację kolumn zapisujemy w tablicy w taki sposób, że każdej wybranej kolumnie przypisujemy wartość 1. Poszczególne kombinacje kolumn tworzą kolejne wiersze tablicy minimalnych pokryć M. Jeżeli jakaś kolumna występuje we wszystkich wierszach tablicy wtedy jej atrybut jest atrybutem niezbędnym (nieusuwalnym) - co oznacza, że atrybut ten występuje w każdym wyniku algorytmu - nie może powstać rozwiązanie bez tego atrybutu. W literaturze [8] atrybut niezbędny definiowany jest w następujący sposób:

Definicja

Atrybut p e P jest nieusuwalny (niezbędny) z P jeżeli P — {p} ^ P; w przeciwnym wypadku atrybut p jest zbędny w P.

W poniższym przykładzie jest to kolumna b.

Tabela 10 Tablica minimalnych pokryć M [5]

a    b    c    d

1    1    -

1    -    1

15