1 Jak usprawnić obliczanie MKZ?Znamy metodę wg par sprzecznych oraz metodę bezpośrednią W celu sprawniejszego obliczania MKZ wprowadzimy skuteczniejszą metodę wg par zgodnych

2 Algorytm MKZ wg par zgodnychE – relacja zgodności (ei,ej)  E Rj = { ei | i < j oraz (ei,ej)  E} RKZk RKZk KZ  RKZk a) Rk+1 = , RKZk+1 jest powiększana o klasę KZ = {k+1} b) KZ  Rk+1 = , KZ bez zmian c) KZ  Rk+1  , KZ’ = KZ  Rk+1 {k+1}

3 Rj = { ei | i < j oraz (ei,ej)  E}Przykład Rj = { ei | i < j oraz (ei,ej)  E} E: 1,2 1,3 1,5 2,3 2,4 2,5 3,5 3,6 4,6 R1 =  R2 = 1 R3 = 1,2 R4 = 2 R5 = 1,2,3 R6 = 3,4

4 Przykład c.d. Rodzina MKZ R1 =  R2 = 1 R3 = 1,2 R4 = 2 R5 = 1,2,3a) Rk+1 = , RKZk+1 jest powiększana o klasę KZ = {k+1} b) KZ  Rk+1 = , KZ bez zmian c) KZ  Rk+1  , KZ’ = KZ  Rk+1 {k+1} R1 =  R2 = 1 R3 = 1,2 R4 = 2 R5 = 1,2,3 R6 = 3,4 {1} {1,2} {1,2,3} {2,4}, {1,2,3} {2,5}, {1,2,3,5}, {2,4} Rodzina MKZ {3,6}, {4,6}, {1,2,3,5}, {2,4}

5 Algorytm MKZ wg par sprzecznychZapisać pary sprzeczne w postaci koniunkcji dwuskładnikowych sum Koniunkcję dwuskładnikowych sum przekształcić do minimalnego wyrażenia boolowskiego typu suma iloczynów Wtedy MKZ są uzupełnieniami zbiorów reprezentowanych przez składniki iloczynowe tego wyrażenia

6 Ten sam przykład Pary zgodne Pary sprzeczne E: 1,2 1,3 1,5 2,3 2,4 2,53,5 3,6 4,6 1,4 1,6 2,6 3,4 4,5 5,6

7 Przykład... Pary sprzeczne:(k1, k4), (k1, k6), (k2, k6), (k3, k4), (k4, k5), (k5, k6) Obliczamy wyrażenie boolowskie typu „koniunkcja sum”: (k1 + k4) (k1 + k6 ) (k2 + k6) (k3 + k4) (k4 + k5) (k5 + k6) = Porządkujemy: (k4 + k1) (k4 + k3 ) (k4 + k5) (k6 + k1) (k6 + k2) (k6 + k5) = Przekształcamy wyrażenie do postaci „suma iloczynów”: = (k4 + k1k3k5) (k6 + k1k2k5) = k4k6 + k1k2k4k5 + k1k3k5k6 + k1k2k3k5

8 Przykład... Klasy zgodne uzyskamy odejmując od zbioru {k1,...,k6}, zbiory tych ki, które występują w jednym składniku wyrażenia typu „suma iloczynów” {k1,..., k6}  {k4, k6} = {k1, k2, k3, k5 } {k1,...,k6}  {k1, k2 , k4 , k5 } = {k3, k6} {k1,...,k6}  {k1, k3, k5 , k6} = {k2 , k4} {k1,...,k6}  {k1, k2, k3, k5 } = {k4, k6}

9 Warto umiejętnie dobierać metodę...Pary zgodne: (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,3), (2,5), (2,6), (2,7), (3,4), (3,5), (3,6), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), (5,8), (6,7), (6,8), (7,8), Pary sprzeczne: (1,8) (2,4) (2,8) (3,7) (4,5) Wybór metody jest oczywisty!

10 W poszukiwaniu innych metod…W obliczaniu kolumn, które można „skleić” znajdują zastosowanie algorytmy kolorowania grafu. Wierzchołki grafu reprezentują kolumny tablicy dekompozycji. Niezgodne pary kolumn łączy się krawędziami. Graf niezgodności: (ki, kj) (ki, ks) (kl, kr) Pary niezgodne: ks k2 ki kj kl k1 kr kp

11 Przykład… Pary zgodne: Pary sprzeczne:0,3 0,4 0,6 1,3 1,4 1,5 1,6 2,5 2,7 3,4 3,6 4,5 4,6 5,7 0,1 0,2 0,5 0,7 1,2 1,7 2,3 2,4 2,6 3,5 3,7 4,7 5,6 6,7

12 Graf niezgodności (0,1), (0,2), (0,5), (0,7), (1,2), (1,7), (2,3), (2,4), (2,6), (3,5), (3,7), (4,7), (5,6), (6,7) 1 2 3 4 5 6 7 i jego kolorowanie

13 Graf zgodności - przykład(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,3), (2,5), (2,6), (2,7), (3,4), (3,5), (3,6), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), (5,8),(6,7), (6,8), (7,8), S1 S2 S3 S4 S5 S6 S7 S8 MKZ1 = {S1, S2, S5, S6, S7} MKZ2 = {S1, S4, S6, S7} MKZ3 = {S5, S6, S7 ,S8} MKZ4 = {S4, S6, S7 ,S8} MKZ5 = {S3, S5, S6, S8} MKZ6 = {S3, S4, S6, S8} MKZ7 = {S1, S2, S3, S5, S6} MKZ8 = {S1, S3, S4, S6} Jak zauważyć rozwiązanie z grafu zgodności!

14 Graf niezgodności - przykładS1 S2 S3 S4 S5 S6 S7 S8 (S1, S8) (S2, S4) (S2 ,S8) (S3, S7) (S4, S5) Teraz łatwiej! MKZ1 = {S1, S2, S5, S6, S7} MKZ6 = {S3, S4, S6, S8}