ИСТИНА

Данный доклад фокусируется на различных моделях схем, включая клеточные плоские и объёмные схемы, а также их обобщения - укладки схем из функциональных элементов на графы с заданными локальными ограничениями. Помимо функциональных элементов, укладки схем включают коммутационные элементы, которые реализуют тождественные функции и играют роль проводов для передачи сигнала от одного функционального элемента к другому. Рассматриваются несколько мер сложности. Обычная сложность схемы определяется как общее число элементов, содержащихся в ней. Глубина схемы определяется как максимальное количество функциональных элементов на пути от входа к выходу. Кроме того, изучаются меры мощности (активности) схемы. Мощность (активность) схемы на конкретном входном наборе определяется как количество элементов схемы, которые выдают на выходе значение 1 при подаче на вход схемы данного набора. Средняя мощность схемы определяется как среднее значение мощности по всем возможным входным наборам, а максимальная мощность -- как наибольшее значение мощности среди всех входных наборов. Кроме основных мер сложности можно ввести и другие, которые будут учитывать различные элементы с разным весом. Например, интересной характеристикой является глубина с учётом ветвлений. В ней учитывается не только функциональные элементы, но и коммутационные элементы, подключённые ко входам хотя бы двух других элементов (играют роль разветвлений проводов в схеме). В следующей части доклада будут представлены результаты, относящиеся к различным мерам сложности в описанных моделях. Первая группа результатов посвящена сложности укладок схем на графы, где каждое ребро графа может содержать не более k проводов схемы. Такие схемы называются многослойными схемами. Были получены асимптотические оценки функции Шеннона сложности многослойных схем на d-мерных целочисленных решётках. Также была получена универсальная нижняя оценка сложности многослойных схем на произвольном графе в терминах размеров сепараторов его подграфов. Следующая группа результатов посвящена порядкам функции Шеннона для активности клеточных схем для класса частичных операторов, замкнутых классов булевых функций и класса функций ограниченного веса. Заключительная группа результатов посвящена обобщению этих оценок на трёхмерный случай. Отдельное внимание уделяется влиянию зависимости активности схем от расположения выходов. В конце будет приведено сравнение полученных оценок мер сложности с известными оценками для аналогичных мер сложности в модели схем из функциональных элементов.