Асимптотические оценки высокой степени точности для сложности универсального многополюсника в модели клеточных схем

В общем случае клеточная схема из функциональных и коммутационных элементов представляет собой математическую модель интегральных схем, в первую очередь сверхбольших интегральных схем (СБИС), которая учитывает особенности их физического синтеза. Принципиальным отличием этой модели от хорошо изученных классов схем из функциональных элементов является наличие дополнительных требований на геометрию схемы, обеспечивающих учет необходимых трассировочных ресурсов при создании СБИС. Предметом изучения многих авторов стала сложность реализации универсального многополюсника порядка $ n, n=1, 2, \ldots, $ т.е. системы из всех функций алгебры логики от $n$ булевых переменных в различных классах схем. В работе на уровне асимптотических оценок высокой степени точности устанавливаются верхние и нижние оценки площади клеточных схем, его реализующих. При этом конструктивно построено семейство схемных универсальных многополюсников порядка $n$ с площадью, равной верхней оценке, и предложен метод получения соответствующей нижней оценки.