1 Espresso . . . mankamenty

2 Czy można przewidzieć od jakich argumentów funkcja istotnie zależy ???Funkcja 7 argumentów x2 x4 x6 x7 f 1 2 3 4 5 6 7 8 9 x1 x2 x3 x4 x5 x6 x7 f 1 2 3 4 5 6 7 8 9 Pamiętamy z ekspansji Czy można przewidzieć od jakich argumentów funkcja istotnie zależy ???

3 Przykład z Synteza układów logicznych str 65.type fr .i 10 .o 1 .p 25 .e Funkcja 10 argumentów .i 10 .o 1 .p 6 .e Espresso Brak x3 - 9 argumentów

4 Można wykazać, że funkcja ta jest zależna od…Zagadka... .type fr .i 10 .o 1 .p 25 .e Od ilu argumentów zależy ta funkcja Można wykazać, że funkcja ta jest zależna od… …zaledwie 7 argumentów!

5 Espresso redukuje składniki iloczynoweWniosek Espresso redukuje składniki iloczynowe Nie redukuje argumentów!!!

6 Nowy sposób opisu funkcji: rachunek podziałówPROBLEM: Obliczania minimalnej liczby argumentów od których funkcja istotnie zależy ...jest bardzo istotny w redukowaniu złożoności obliczeniowej procedur minimalizacji funkcji boolowskich, a w konsekwencji może się przyczynić do uzyskiwania lepszych rezultatów. Nowy sposób opisu funkcji: rachunek podziałów

7 Elementy rachunku podziałówPodziałem na zbiorze S jest system zbiorów P = {Bi }, którego bloki są rozłączne, czyli Bi  Bj =, jeśli tylko i  j. Dla S = {1,2,3,4,5,6}, P = {{1,2}, {3,5}, {4,6} } jest podziałem na S. Podzbiory nazywamy blokami  = Podstawowe pojęcia: Iloczyn podziałów oraz relacja .

8 Elementy rachunku podziałów…Powiemy, że podział Pa jest nie większy od Pb (co oznaczamy: Pa   Pb ), jeśli każdy blok z Pa jest zawarty w pewnym bloku z Pb. a = b = c = c ≤ a Tak c  b NIE! (0) – podział najmniejszy (1) – podział największy

9 Elementy rachunku podziałów…Iloczynem podziałów a • b nazywamy największy (względem relacji ) podział, który jest nie większy od a oraz b. a = b = a • b =

10 Nowy sposób opisu funkcji - podziałyFunkcja f x1 x2 x3 x4 x5 x6 x7 f 1 2 3 4 5 6 7 8 9 P1 = P2 = P3 = P4 = P5 = P6 = P7 = Pf =

11 Pojęcie zmiennej niezbędnejJeżeli wektory Xa oraz Xb: f (Xa)  f (Xb), różnią się dokładnie dla jednej zmiennej to zmienną taką nazywamy niezbędną Wyjaśnienie i interpretacja w książce: Warto przeczytać rozdział 3.4

12 Redukcja argumentów – przykładFunkcja f x4 x6 – zmienne niezbędne różnią się na pozycji ponieważ wiersze 2 i 8 x1 x2 x3 x4 x5 x6 x7 f 1 2 3 4 5 6 7 8 9 x4 x6 na pozycji a wiersze 4 i 9 P4 =  P6 =  Dalej liczymy iloczyn P4 P6  P4•P6 = Pf =

13 Redukcja argumentów – przykładIloczyn podziałów wyznaczonych przez zmienne niezbędne ma bardzo ważną interpretację P4•P6 = Pf =

14 Redukcja argumentów – przykład c.d.x1 x2 x3 x4 x5 x6 x7 f 1 2 3 4 5 6 7 8 9 1, 5, 7, 9 4, 6, 8 1, 5 1, 7 1, 9 4, 6 4, 8 x1 x2 x3 x5 x7 x2 x3 x1 x2 x3 x5 x7 x2 x3 x2 x7 Tu obliczamy minimalne pokrycie kolumnowe x2 x3 x7 x2 x7 ...ale teraz systematycznie...

15 Redukcja argumentów – przykład c.d.x1 x2 x3 x5 x7 x2 x3 x2 x7 (x1 + x2) (x3 + x5 + x7) (x2 + x3) (x2 + x7) = = (x2 +x1)(x2 + x3)(x2 + x7)(x3 + x5 + x7) = =(x2 +x1x3x7) (x3 + x5 + x7) = Tylko to było znalezione przez Espresso = x2x3 + x2x5 +x2x7 + x1x3x  {x4,x6} {x2,x3,x4,x6} {x2,x4,x5,x6} {x2,x4,x6,x7}

16 ...ale gdybyśmy wiedzieli o tym wcześniej, żefunkcja ta zależy tylko od {x2,x4,x6,x7} x1 x2 x3 x4 x5 x6 x7 f 1 2 3 4 5 6 7 8 9 x2 x4 x6 x7 f 1 2 3 4 5 6 7 8 9 A taką funkcję można łatwo zminimalizować nawet na tablicy Karnaugha

17 Redukcja argumentów EspressoWprowadzenie redukcji argumentów do procedury ekspansji daje – w rozsądnym czasie – wyniki lepsze niż słynne Espresso

18 Przykład z Synteza układów logicznych str 65.type fr .i 10 .o 1 .p 25 .e Funkcja TL27 10 argumentów .i 10 .o 1 .p 6 .e Espresso 9 argumentów 6 termów

19 Funkcja TL27 Funkcja TL27 przed redukcją PandorRealizacja funkcji f1 Ilość zmiennych = 7 Ilość wektorów = 25 R3 = {1,2,4,6,7,9,10} .type fr .i 10 .o 1 .p 25 .e Pandor Jedno z 10 rozwiązań po redukcji argumentów

20 Przykład TL27 Funkcja 10 argumentów, 25 wektorów w TPWynik Espresso – 9 argumentów, 6 termów Wynik Pandora po RedArg – 7 argumentów, 5 termów

21 Jedno z wielu rozwiązań po redukcji argumentówFunkcja KAZ Przed redukcją Jedno z wielu rozwiązań po redukcji argumentów .type fr .i 21 .o 1 .p 31 .end Pandor Ile jest takich rozwiązań

22 Przykład KAZ Silnie nieokreślona funkcja 21 argumentów, 31 wektorów w TP Wynik Espresso – 9 argumentów, 3 termy Wynik Pandora – 5 argumentów, 3 termy