Для функций Шеннона самокорректирующихся контактных схем коррекция одного отказа не меняет главный асимптотический член сложности. В курсе доказана теорема
\(L^K_{(1,0)}(n)\sim L^K_{(0,1)}(n)\sim 2^n/n\).
Первый класс исправляет один обрыв, второй — одно замыкание. Нижняя оценка наследуется от обычных контактных схем, а верхняя достигается специальной конструкцией, у которой дополнительная цена самокоррекции имеет меньший порядок по сравнению с
Что важно запомнить
- Самокорректирующийся класс не может быть проще обычных контактных схем.
- Для коррекции одного обрыва и одного замыкания по отдельности главный асимптотический член остаётся
- Простейшее поконтактное резервирование даёт постоянный множитель, но не является асимптотически оптимальным.
- Оптимальная конструкция использует однородные фрагменты и добавляет лишь нижнепорядковую избыточность.
- Символ \(\sim\) означает отношение, стремящееся к 1 при \(n\to\infty\), а не точное равенство для каждого \(n\).
Функции Шеннона надёжных КС
Обозначим через \(L^K_{(p,q)}(n)\) максимальную по всем \(n\)-местным ФАЛ минимальную сложность контактной схемы, которая реализует функцию и корректирует до \(p\) обрывов и \(q\) замыканий. При \((p,q)=(0,0)\) получается обычная функция Шеннона контактных схем.
Теорема для одного отказа
Теорема главы о надёжности утверждает
\(L^K_{(1,0)}(n)\sim L^K_{(0,1)}(n)\sim 2^n/n\).
Нижняя граница получается сразу: допустимые самокорректирующиеся реализации образуют подкласс обычных КС, поэтому \(L^K_{(1,0)}(n)\ge L^K(n)\) и \(L^K_{(0,1)}(n)\ge L^K(n)\). Для обычных контактных схем \(L^K(n)\sim2^n/n\), откуда следует нужная нижняя асимптотика.
Почему избыточность не меняет главный член
Верхняя граница использует более экономную конструкцию. Для любой КС \(\Sigma\) лемма даёт эквивалентную \((1,0)\)- или \((0,1)\)-самокорректирующуюся схему \(\Sigma'\) с \(L(\Sigma')\le L(\Sigma)+\zeta(\Sigma)\). В асимптотически оптимальной исходной конструкции число однородных частей выбирается так, что \(\zeta(\Sigma)=o(2^n/n)\). Поэтому из \(L(\Sigma)=(1+o(1))2^n/n\) получается
Поэтому требование исправлять один отказ существенно для конкретной структуры, но в функции Шеннона не меняет ведущую асимптотику.
Пример простыми словами
Наивное удвоение всех контактов для защиты от одного обрыва могло бы дать оценку примерно вдвое больше обычной. Теорема показывает, что это не предел: при правильной группировке и совместном резервировании относительная дополнительная цена стремится к нулю.
Частые ошибки
- Считать \(2^n/n\) точной сложностью каждой функции или каждой надёжной схемы. Это асимптотика функции Шеннона.
- Доказывать оптимальность только простой двухкратной избыточностью. Она даёт верхнюю оценку, но проигрывает по ведущей константе.
- Смешивать случаи \((1,0)\) и \((0,1)\) с одновременной коррекцией одного обрыва и одного замыкания \((1,1)\).
