Слайды лекций (1132834), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

, yp ), получающаясяиз этой КНФ в результате раскрытия скобоки приведения подобных, соответствуеттупиковому тесту, связанному с множествомT = {t1, . . . , tr } и обратно.Утверждение 24.2 Длина любоготупикового диагностического теста дляотделимой по столбцам матрицы измножества B p,s заключена в пределах отdlog s e до (s − 1).Утверждение 24.3 Пусть ϕ(s ), t (s ) иp (s ) — целочисленные неотрицательныефункции натурального аргумента s , длякоторыхt (s ) = d2 log s e + ϕ(s ), p (s ) > t (s ),ϕ(s ) −−−→ ∞.s →∞Тогда у почти всех отделимых по столбцамматриц из B p(s ),s первые t (s ) строкобразуют диагностический тест.Следствие Для любой неотрицательной инеограниченно возрастающей функции ϕ(s )у почти всех отделимых по столбцам матрициз B p,s длина минимальногодиагностического теста не больше, чем2 log s + ϕ(s ).25.

Самокорректирующиесяконтактные схемы и методыих постороения.Асимптотически наилучшийметод синтеза контактныхсхем, корректирующих одинобрыв (одно замыкание)Утверждение 25.1 Для любых p > 0,q > 0 и любой КС Σ существуетэквивалентная ей КС Σ0, Σ0 ∈ UK(p,q ), длякоторойL(Σ0) 6 (p + 1)(q + 1)L(Σ)Утверждение 25.2 Для любой КС Σсуществуют эквивалентные ей (1, 0)- и(0, 1)-самокорректирующиесяКС Σ0 и Σ00 соответственно такие, чтоL(Σ0) 6 L(Σ) + ζ(Σ),L(Σ00) 6 L(Σ) + ζ(Σ)Утверждение 25.3 Для n = 1, 2, . . .имеют место следующие асимптотическиеравенства:LK(1,0)(n)∼LK(0,1)(n)2n∼nУтверждение 25.4 Для n = 1, 2, .

. .имеют место равенстваKKL(1,0) (`n ) = L(1,0) `n = 4n..

Характеристики

Список файлов лекций