Теорема Шеннона — Лупанова (Mykjybg Oyuukug — Lrhgukfg)

Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

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

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

[править | править код]

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

Примечания

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

Литература

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