Вопросы к Поиску с Алисой
В чём заключается алгоритм Куайна — Мак-Класки?
Метод Куайна—Мак-Класки — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. ru.ruwiki.ru ru.wikipedia.org
Алгоритм минимизации: ru.ruwiki.ru
- Термы, на которых определена функция алгебры логики (ФАЛ), записываются в виде их двоичных эквивалентов. ru.ruwiki.ru ru.wikipedia.org
- Эти эквиваленты разбиваются на группы, в каждую группу входят эквиваленты с равным количеством единиц (нулей). ru.ruwiki.ru ru.wikipedia.org
- Производится попарное сравнение эквивалентов (термов) в соседних группах, с целью формирования термов более низких рангов. ru.ruwiki.ru ru.wikipedia.org
- Составляется таблица, заголовком строк в которой являются исходные термы, а заголовком столбцов — термы низких рангов. ru.ruwiki.ru ru.wikipedia.org
- Расставляются метки, отражающие поглощение термов высших рангов (исходных термов), и далее минимизация производится по методу Куайна. ru.ruwiki.ru ru.wikipedia.org
Специфика метода заключается в сокращении количества попарных сравнений на предмет их склеивания. ru.ruwiki.ru ru.wikipedia.org Это достигается за счёт исходного разбиения термов на группы с равным количеством единиц (нулей). ru.ruwiki.ru ru.wikipedia.org
Метод имеет ограничения области применения, так как время работы метода растёт экспоненциально с увеличением входных данных. ru.ruwiki.ru
