Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на синтез схем
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 93: | Строка 93: | ||
'''Решение''' | '''Решение''' | ||
# Разлагаем ''f'' по первым трём переменным: | # Разлагаем ''f'' по первым трём переменным: | ||
- | #* ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = <span style="border-top:solid 1px">''x''</span><sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(0, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & ''x''<sub>3</sub> & ''f''(0, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(0, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>2</sub> & ''x''<sub>3</sub> & ''f''(0, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(1, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & ''x''<sub>3</sub> & ''f''(1, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(1, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''x''<sub>2</sub> & ''x''<sub>3</sub> & ''f''(1, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = (<span style="border-top:solid 1px">''x''</span><sub>1</sub>''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ ''x''<sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>) & ''f''<sub>a</sub> ∨ (<span style="border-top:solid 1px">(<span style="border-top:double 3px">''x''</span><sub>1</sub>''x''<sub>2</sub><span style="border-top:double 3px">''x''</span><sub>3</sub> ∨ ''x''<sub>1</sub><span style="border-top:double 3px">''x''</span><sub>2</sub>''x''<sub>3</sub>)</span>) & ''f''<sub>b</sub> (*), | + | #* ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = <span style="border-top:solid 1px">''x''</span><sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(0, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & ''x''<sub>3</sub> & ''f''(0, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(0, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>2</sub> & ''x''<sub>3</sub> & ''f''(0, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(1, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & ''x''<sub>3</sub> & ''f''(1, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(1, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''x''<sub>2</sub> & ''x''<sub>3</sub> & ''f''(1, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = (<span style="border-top:solid 1px">''x''</span><sub>1</sub>''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ ''x''<sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>) & ''f''<sub>a</sub> ∨ (<span style="border-top:solid 1px">(<span style="border-top:double 3px">''x''</span><sub>1</sub>''x''<sub>2</sub><span style="border-top:double 3px">''x''</span><sub>3</sub> ∨ ''x''<sub>1</sub><span style="border-top:double 3px">''x''</span><sub>2</sub>''x''<sub>3</sub>)</span>) & ''f''<sub>b</sub> (*), где ''f''<sub>a</sub> = ''f''(0, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(1, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(1, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = f(1, 1,1,x4,...,xn) = ''f''(0, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(0, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>); ''f''<sub>b</sub> = ''f''(0, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(1, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>). Теперь видно, что функция из данного класса однозначно определяется парой (''f''<sub>a</sub>, ''f''<sub>b</sub>), где ''f''<sub>a</sub>, ''f''<sub>b</sub> — функции от ''n'' − 3 переменных. Таким образом, число функций из заданного класса равно числу таких пар, т. е. 2<sup>2<sup>''n'' − 3</sup></sup> × 2<sup>2<sup>''n'' − 3</sup></sup> = 2<sup>2<sup>''n'' − 2</sup></sup> |
# Из (1) следует, что ''L''<sup>C</sup>(''Q''(''n'')) ≳ 2<sup>''n'' − 2</sup> / ''n'' | # Из (1) следует, что ''L''<sup>C</sup>(''Q''(''n'')) ≳ 2<sup>''n'' − 2</sup> / ''n'' | ||
# Опять же, из (*) ясно, как строить схему для произвольной функции из заданного класса. Строим СФЭ для функций ''f''<sub>a</sub>, ''f''<sub>b</sub> (сложность каждой ≤ (2<sup>''n'' − 3</sup> / (''n'' − 3)). И, кроме того, нам потребуется дополнительная константа С «∨», «&» и «¬» для реализации (*). Складывая (2<sup>''n'' − 3</sup> / (''n'' − 3)) + (2<sup>''n'' − 3</sup> / (''n'' − 3)) + С, получим как раз, что это ≲ 2<sup>''n'' − 2</sup> / ''n''. | # Опять же, из (*) ясно, как строить схему для произвольной функции из заданного класса. Строим СФЭ для функций ''f''<sub>a</sub>, ''f''<sub>b</sub> (сложность каждой ≤ (2<sup>''n'' − 3</sup> / (''n'' − 3)). И, кроме того, нам потребуется дополнительная константа С «∨», «&» и «¬» для реализации (*). Складывая (2<sup>''n'' − 3</sup> / (''n'' − 3)) + (2<sup>''n'' − 3</sup> / (''n'' − 3)) + С, получим как раз, что это ≲ 2<sup>''n'' − 2</sup> / ''n''. |