Метод Лупанова улучшает метод Шеннона за счёт ДУМ. После разбиения переменных на группы кофакторы не берутся как самостоятельные выходы огромного универсального блока. Каждый кофактор представляется дизъюнкцией функций из компактного ДУМ, а функции ДУМ реализуются в СФЭ один раз и многократно
Теорема 6.1 курса даёт для любой \(f\in P_2(n)\) СФЭ со сложностью \(L(\Sigma_f)\le (2^n/n)\cdot (1+(5 \log n+O(1))/n)\). В сочетании с мощностной нижней оценкой это даёт точную асимптотику \(L^C(n)\sim 2^n/n\). Для почти всех ФАЛ сложность имеет ту же асимптотику, то есть в классе СФЭ имеет место эффект
Что важно запомнить
- Метод сохраняет разложение функции на кофакторы, как в методе Шеннона.
- Каждый кофактор дополнительно раскладывается через функции специального
- Функции ДУМ реализуются один раз и используются многими кофакторами, что снижает стоимость общего блока.
- Теорема 6.1 даёт
- Следствие: \(L^C(n)\sim 2^n/n\).
- Почти все n-местные ФАЛ имеют сложность, асимптотически равную \(L^C(n)\). Это эффект Шеннона для
От метода Шеннона к методу Лупанова
В методе Шеннона после фиксации части переменных требуется уметь выбирать произвольные кофакторы от q переменных. Лупанов сохраняет это разложение, но отказывается от прямой реализации всего множества P₂(q). Вместо этого выбирается стандартное ДУМ G, а каждый кофактор представляется дизъюнкцией p функций из
Совместная реализация ДУМ
СФЭ реализует систему функций G единожды. Затем для каждого кофактора нужные выходы G соединяются дизъюнктивной частью, а адресные переменные выбирают соответствующий кофактор. Ключевое преимущество СФЭ здесь состоит в свободном разветвлении результатов: один выход, реализующий функцию из G, может участвовать сразу в большом числе
Асимптотическая оптимальность
Параметры разбиения и высоты ДУМ выбираются так, чтобы стоимость реализации G, дизъюнктивных сборок и селекторной части была сбалансирована. Теорема 6.1 даёт для любой f
\(L(\Sigma_f)\le (2^n/n)\cdot (1+(5 \log n+O(1))/n)\).
Поскольку мощностный метод уже даёт \(L^C(n)\ge (1-o(1))2^n/n\), верхняя и нижняя оценки совпадают в главном члене. Поэтому \(L^C(n)\sim 2^n/n\). Более того, почти все функции имеют ту же асимптотическую сложность, что и самая сложная
Пример простыми словами
В методе Шеннона можно представить ситуацию так: для каждого нужного кофактора требуется готовый отдельный выход универсального устройства. В методе Лупанова кофакторы собираются из общего набора деталей G. Если одна функция из G нужна сотням кофакторов, она всё равно реализуется в СФЭ только один раз.
Частые ошибки
- Считать ДУМ набором отдельных независимых реализаций для каждого кофактора. Выигрыш возникает из совместного использования функций G.
- Заменять асимптотику утверждением \(L^C(f)=2^n/n\) для каждой функции. Теорема даёт универсальную верхнюю оценку, а точная асимптотика относится к функции Шеннона.
- Переносить результат \(2^n/n\) на формулы. Для формул порядок сложности другой.
- Называть коэффициенты метода Шеннона 8 и метода Лупанова 1 точными конечными значениями. Сравнение является асимптотическим.
