Cтраница 2
Мы уже упоминали в конце § 6 о том, как изучение поведения функций, аналогичных функциям Шеннона, позволяет делать весьма важные для практики предсказания. [16]
Аналогично тому, как это делается для логических схем ( см., например, [ 21), введем функцию Шеннона / т / Л для сложности реализации текстом Г - сетямм. Пуст, L T ( t) - минимальная из сложностей Т - сетей, реализуюш. [17]
В данной работе предложен новый подход к получению оценок функций Шеннона для произвольных бесконечных базисов, позволяющий при довольно слабых ограничениях оценивать рост функций Шеннона с точностью до полиномиальной эквивалентности. [18]
Результаты, полученные при решении проблемы оптимального синтеза для базовых задач, характеризуются, во-первых, тем, что для всех задач из модельных классов, кроме так называемых задач включающего поиска из второго базового класса, получены точные и ( или) асимптотические результаты, для задач включающего поиска получена асимптотика функции Шеннона, а для некоторых базовых множеств - и асимптотика сложности для почти всех задач и для средней сложности по задачам. Во-вторых, полученные результаты можно условно разбить на 4 типа. [19]
В докладе были рассмотрены поляризованные полиномы функций многозначных логик. Доказаны некоторые оценки функций Шеннона их сложности. [20]
Первые результаты были получены К. В последующие годы были получены асимптотики функции Шеннона ( асимптотически совпадающие верхние и нижние оценки), ряд значений которых для случая схем из функциональных элементов и автоматных базисов будет приведен ниже. [21]
О поведении функций Шеннона для бесконечных базисов известно меньше. До недавнего времени порядки роста или асимптотики функций Шеннона были установлены лишь для некоторых конкретных базисов. Из этих результатов явствует, что поведение функций Шеннона для бесконечных базисов может быть довольно разнообразным. [22]
Поводом для этого послужил чисто формальный признак: функция Шеннона, связывающая информацию с числом N возможных событий в поведении системы, математически оказалась сходной с Н - функцией Больцмана. [23]
Кроме того, вместо синтеза схем для отдельных функций ( уравнений) рассматривается задача синтеза для класса Р ( п) всех функций от п переменных. При этом качество алгоритмов синтеза сравнивается путем сопоставления так называемых функций Шеннона. [24]
Полученная выше нижняя оценка для L ( га) показывает, что наилучшие из элементарных методов синтеза отличаются по порядку от нижней оценки в га раз. В действительности оказалось, что существует такой метод синтеза, который приводит к функции Шеннона по порядку совпадающей с нижней оценкой. Этот метод был создан К. [25]
Методы, использованные в этих работах, существенным образом опираются на оценки Э. И. Нечипорука ( см. [4]) мощности множества, содержащего доопределения всех частичных булевых функций определенного вида. Из опубликованных в этих работах результатов следует, в частности, асимптотически точная формула для функции Шеннона множества всех частичных булевых функций, вес которых незначительно отличается от размера области определения. [26]
Как мы уже отмечали, подход К - Шеннона - отказ от попытки синтеза минимальных по числу элементов схем для индивидуальных функций - методологически оказался очень ценным. Для различных классов управляющих систем ( схем в различных базисах из функциональных элементов, схем в пороговых базисах, релейно-контактных схем, формул) были построены асимптотически наилучшие алгоритмы синтеза и найдены асимптотики функции Шеннона. [27]
О поведении функций Шеннона для бесконечных базисов известно меньше. До недавнего времени порядки роста или асимптотики функций Шеннона были установлены лишь для некоторых конкретных базисов. Из этих результатов явствует, что поведение функций Шеннона для бесконечных базисов может быть довольно разнообразным. [28]
Методы, использованные в этих работах, существенным образом опираются на оценки Э. И. Нечипорука ( см. [4]) мощности множества, содержащего доопределения всех частичных булевых функций определенного вида. Из опубликованных в этих работах результатов следует, в частности, асимптотически точная формула для функции Шеннона множества всех частичных булевых функций, вес которых незначительно отличается от размера области определения. В 1999 г. П. Б. Милтерсе-ном в работе [13] было установлено) асимптотически точное поведение функции Шеннона частичных функций, вес которых бесконечно мал относительно размера области определения. [29]