Теорема Шеннона — Лупанова

Теорема Шеннона — Лупанова определяет число элементов, необходимых для реализации автомата в заданном автоматном базисе[неизвестный термин].

Формулировка

править

1. Для любого базиса  :  , где   — константа, зависящая от базиса.

2. Для любого   доля функций  , для которых   стремится к нулю с ростом  .

Пояснения

править

Здесь  , где максимум берется по всем функциям от   переменных[прояснить]. Знак   обозначает асимптотическое равенство:  , если  . Смысл второго утверждения теоремы в том, что с ростом   почти все функции реализуются со сложностью, близкой к верхней границе  .

Доказательство

править

Доказательство есть в статье[1].

Примечания

править
  1. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, М., Физматгиз, 1963, вып. 10, c. 63-97.

Литература

править
  • Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. — 480 с. — ISBN 5-283-01563-7.