Головна

метод синтезу

  1. Case-метод Баркера
  2. I. 2. 1. Марксистсько-ленінська філософія - методологічна основа наукової психології
  3. I. 2.4. Принципи та методи дослідження сучасної психології
  4. I. Методичні рекомендації
  5. I. Методичні рекомендації
  6. I. Методичні рекомендації
  7. I. Методичні рекомендації

Схема S для функції f (x1, ..., Xn), Заданої таблицею 1, будується на основі її уявлення (6) і складається з 6 блоків (рис. 6):

1) Блок А реалізує Q  (x  , ..., X  ), Причому L (A) ? (n-k) 2 .

2) Блок B реалізує Q  (x  , ..., X  ), Причому L (B) ? k 2 .

3) Блок C реалізує всі різні функції f  (s1, ..., S ,  ), Тоді L (С) ? p S 2 .

4) Блок D реалізує всі функції =  , Тоді L (D) ? p 2 .

5) Блок G здійснює множення  , Тому L (G) = 2

6) Нарешті, блок F реалізує функцію f (x1, ..., Xn) Як диз'юнкцію функцій, реалізованих блоком G. L (F) ? 2 .

 S:

Мал. 6

Отже, L (S) = L (A) + L (B) + L (C) + L (D) + L (G) + L (F) ? (n-k) * 2  + K * 2 +
 + P * S * 2  + P * 2  +2  = (N-k + 1) * 2  + K * 2  + P * S * 2  + P * 2 =

= (N-k + 1) * 2  + K * 2  + P * (2  + S * 2  ) ? (n-k + 1) * 2  + K * 2  + (  +1) * (2  + S * 2  ).

Поклавши k = [3 log n], s = [n-5 log n] отримаємо L (S) ?  (1 + O (  )) І L (n) ?  (1 + O (  )). Теорема повністю доведена.

~
теорема 4(Без доведення). L (n)> .

теорема 5 (Як наслідок теорем 3 і 4). L (n) ~ .

Зауваження. Описаний метод синтезу в теоремі 3 є асимптотично найкращим.

 



Попередня   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   Наступна

Лемма про несамодвойственной функції | Монотонні функції, їх властивості | Лемма про немонотонної функції | передповний клас функцій алгебри логіки | Подання про результати Посту | Завдання для самостійної роботи | Схеми з функціональних елементів | Визначення схем з функціональних елементів | Найпростіші методи синтезу | метод Шеннона |

© um.co.ua - учбові матеріали та реферати