Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на синтез схем
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 3: | Строка 3: | ||
=== Простейшие методы === | === Простейшие методы === | ||
==== Промежуточные действия ==== | ==== Промежуточные действия ==== | ||
- | * Если ФАЛ представлена в виде таблицы, то построим по ней | + | * Если ФАЛ представлена в виде таблицы, то построим по ней сокращённую ДНФ (как объединение всех возможных случаев, когда она равна 1). |
- | * Если ФАЛ представлена в виде формулы, преобразуем ее, чтобы остались только функции базиса Б<sub>0</sub>. Кроме того, поднимаем все отрицания (они должны стоять только | + | * Если ФАЛ представлена в виде формулы, преобразуем ее, чтобы остались только функции базиса Б<sub>0</sub>. Кроме того, поднимаем все отрицания (они должны стоять над только переменными, но не над бо́льшими кусками выражения). |
- | + | ||
==== Получение СФЭ ==== | ==== Получение СФЭ ==== | ||
Строим как-нибудь подвыражения в соответствии с приоритетом операций. Поскольку оставлены только функции базиса Б<sub>0</sub>, то это не вызывает особых затруднений. Что вижу, то и рисую. | Строим как-нибудь подвыражения в соответствии с приоритетом операций. Поскольку оставлены только функции базиса Б<sub>0</sub>, то это не вызывает особых затруднений. Что вижу, то и рисую. | ||
Строка 18: | Строка 17: | ||
=== Метод каскадов === | === Метод каскадов === | ||
==== Промежуточные действия ==== | ==== Промежуточные действия ==== | ||
- | Пусть у нас имеются булевы функции F<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, | + | Пусть у нас имеются булевы функции F<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>),...,F<sub>k</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>), зависящие от n переменных. Обозначим следующее множество: |
- | M<sub>0</sub> = {F<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, | + | M<sub>0</sub> = {F<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>),...,F<sub>k</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>)}. |
В простейшем случае, в нем одна функция. Воспользуемся следующим приемом: | В простейшем случае, в нем одна функция. Воспользуемся следующим приемом: | ||
- | F(x<sub>1</sub>, x<sub>2</sub>, | + | F(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>)=x<sub>1</sub>*F(1,x<sub>2</sub>,...x<sub>n</sub>)V <span style="border-top:solid 1px">x<sub>1</sub></span>*F(0,x<sub>2</sub>,...x<sub>n</sub>) |
- | Тогда определим правило построения следующих множеств (M<sub>1</sub>, M<sub>2</sub>, | + | Тогда определим правило построения следующих множеств (M<sub>1</sub>,M<sub>2</sub>,...,M<sub>n</sub>): |
- | M<sub>i+1</sub> = {g(0,x<sub>i+1</sub>, | + | M<sub>i+1</sub> = {g(0,x<sub>i+1</sub>,...x<sub>n</sub>)|g∈M<sub>i</sub>} U {g(1,x<sub>i+1</sub>,...x<sub>n</sub>)|g∈M<sub>i</sub>}. |
Если функция представлена строкой значений, то формируем новое множество из левых и правых половин. | Если функция представлена строкой значений, то формируем новое множество из левых и правых половин. | ||
Если функция представлена формулой, то подставляем в нее x<sub>i</sub>=0 и x<sub>i</sub>=1 и упрощаем. | Если функция представлена формулой, то подставляем в нее x<sub>i</sub>=0 и x<sub>i</sub>=1 и упрощаем. | ||
Строка 30: | Строка 29: | ||
f<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 0010 1111 1000) | f<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 0010 1111 1000) | ||
f<sub>2</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 1111 0010 1000) | f<sub>2</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 1111 0010 1000) | ||
- | *M<sub>0</sub> = {(1000 0010 1111 1000),(1000 1111 0010 1000)} | + | *M<sub>0</sub>={(1000 0010 1111 1000),(1000 1111 0010 1000)} |
- | *M<sub>1</sub> = {(1000 0010),(1111 1000),(1000 1111),(0010 1000)} | + | *M<sub>1</sub>={(1000 0010),(1111 1000),(1000 1111),(0010 1000)} |
- | *M<sub>2</sub> = {(1000),(0010),(1111)} | + | *M<sub>2</sub>={(1000),(0010),<strike>(1111)</strike>} |
- | *M<sub>3</sub> = {(10),<strike>(00)</strike>,<strike>(11)</strike>} | + | *M<sub>3</sub>={(10),<strike>(00)</strike>,<strike>(11)</strike>} |
- | *M<sub>4</sub> = {0,1} | + | *M<sub>4</sub>={0,1} |
==== Получение СФЭ ==== | ==== Получение СФЭ ==== | ||
Строка 49: | Строка 48: | ||
==== Получение КС ==== | ==== Получение КС ==== | ||
Обозначаем все элементы всех множеств узлами КС. | Обозначаем все элементы всех множеств узлами КС. | ||
- | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(0,x<sub>i+1</sub>,...x<sub>n</sub>), то | + | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(0,x<sub>i+1</sub>,...x<sub>n</sub>), то соединаям g и h контактом с меткой <span style="border-top:solid 1px">x<sub>i</sub></span> |
- | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(1,x<sub>i+1</sub>,...x<sub>n</sub>), то | + | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(1,x<sub>i+1</sub>,...x<sub>n</sub>), то соединаям g и h контактом с меткой x<sub>i</sub> |
После этого удаляем вершину с меткой 0 и все ведущие в нее контакты. Вершину с меткой 1, а также F<sub>1</sub>,...,F<sub>k</sub> помечаем как входы КС. | После этого удаляем вершину с меткой 0 и все ведущие в нее контакты. Вершину с меткой 1, а также F<sub>1</sub>,...,F<sub>k</sub> помечаем как входы КС. | ||
Строка 73: | Строка 72: | ||
# Посчитать число функций в заданном классе ''Q''(''n''). | # Посчитать число функций в заданном классе ''Q''(''n''). | ||
# Сразу же из этого получить асимптотически нижнюю оценку функции Шеннона, связанной с классом ''Q''(''n''): | # Сразу же из этого получить асимптотически нижнюю оценку функции Шеннона, связанной с классом ''Q''(''n''): | ||
- | #* ''L''<sup>''K''</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / | + | #* ''L''<sup>''K''</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / ''n'' |
- | #* L<sup>C</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / | + | #* L<sup>C</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / ''n'' |
# Показать, как для любой функции из данного класса построить схему из класса U, реализующую данную функцию и имеющую сложность, асимптотически равную вычисленной нижней оценке. Из этого будет следовать, что полученная асимптотически нижняя оценка является и асимптотически верхней оценкой, а из этого, в свою очередь, будет следовать, что функция Шеннона для заданного класса ''U''(''n'') будет просто асимптотически равна полученной нижней оценке. | # Показать, как для любой функции из данного класса построить схему из класса U, реализующую данную функцию и имеющую сложность, асимптотически равную вычисленной нижней оценке. Из этого будет следовать, что полученная асимптотически нижняя оценка является и асимптотически верхней оценкой, а из этого, в свою очередь, будет следовать, что функция Шеннона для заданного класса ''U''(''n'') будет просто асимптотически равна полученной нижней оценке. | ||
#* В пункте 3 всегда пригождается следующее: для любой функции от ''n'' переменных можно построить, реализующую её СФЭ и КС со сложностью, асимптотически не превосходящей 2<sup>n</sup> / ''n'' | #* В пункте 3 всегда пригождается следующее: для любой функции от ''n'' переменных можно построить, реализующую её СФЭ и КС со сложностью, асимптотически не превосходящей 2<sup>n</sup> / ''n'' | ||
Строка 93: | Строка 92: | ||
'''Решение''' | '''Решение''' | ||
# Разлагаем ''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''. | ||
Строка 146: | Строка 145: | ||
==== Для исправления одного обрыва цепи ==== | ==== Для исправления одного обрыва цепи ==== | ||
- | *Выделяем звезду из одинаковых контактов, удаляем все | + | *Выделяем звезду из одинаковых контактов, удаляем все кантакты звезды и соединяем все контакты циклом. |
*Все контакты, не вошедшие ни в 1 звезду удваиваем параллельно. | *Все контакты, не вошедшие ни в 1 звезду удваиваем параллельно. | ||
*Данная конфигурация устойчива к одному обрыву, т.к. между любыми 2 узлами появляется не 1, а 2 пути. | *Данная конфигурация устойчива к одному обрыву, т.к. между любыми 2 узлами появляется не 1, а 2 пути. | ||
{{Курс Основы Кибернетики}} | {{Курс Основы Кибернетики}} |