4 (1132840), страница 3
Текст из файла (страница 3)
Если Σ1 , ..Σζ - однородное разбиение КС Σ, а эквивалентная ей КС Σ0 (КСΣ00 ) получается из КС Σ в результате замены каждой подсхемы Σi эквивалентной ей КС Σ0i вида Cm (соответственно00KКС Σ00i вида Zm ), то Σ0 ∈ UK(1,0) (соответственно Σ ∈ U(0,1) ).Заметим, что при этомL(Σ0i ) 6 L(Σi ) + 1, L(Σ00i ) 6 L(Σi ) + 1и, следовательно,L(Σ0 ) 6 L(Σ) + ζ, L(Σ00 ) 6 L(Σ) + ζУказанный нетривиальный способ построения (0, 1)- или(1, 0)-самокорректирующихся КС, эквивалентных заданной,дает следующую оценку их сложности.Лемма 2.2.
Для любой КС Σ существуют эквивалентныеей (1, 0)- и (0, 1)-самокорректирующиеся КС Σ0 и Σ00 соответственно такие, чтоL(Σ0 ) 6 L(Σ) + ζ(Σ), L(Σ00 ) 6 L(Σ) + ζ(Σ).(2.1)Этот способ позволяет установить асимптотику функцииKШеннона для сложности КС из UK(0,1) и U(1,0) .Для ФАЛ f и p > 0, q > 0 определим ее (p, q)-самокорректирующуюся контактную сложность LK(p,q) (f ) как миниKмальную сложность КС Σ, Σ ∈ U(p,q) , реализующей f , азатем введем соответствующую функцию ШеннонаKLK(p,q) (n) = max L(p,q) (f ).f ∈P2 (n)16ВведениеОчевидно, чтоKKLK (f ) 6 LK(p,q) (f ) и L (n) 6 L(p,q) (n)(2.2)Kтак как UK(p,q) ⊆ U .Теорема 2.1. Для n = 1, 2, ...
имеет место следующиеасимптотические равенстваKLK(1,0) (n) ∼ L(0,1) (n) ∼2n.nДоказательство. Требуемые нижние оценки для функцийKШеннона LK(1,0) (n) и L(0,1) (n) вытекают из (2.2) и мощностных нижних оценок функции Шеннона LK (n) из теоремы2.1 главы 3.Для получения соответствующих верхних оценок возьмем произвольную ФАЛ f , f ∈ P2 (n), и построим для нееКС Σf по теореме 8.1 главы 3.
Из замечания к этой теоремевытекает, что при указанных там значениях параметров2nζ(Σf ) = o( √ )n nи поэтому, в соответствии с леммой 2.2 и (2.1), существуютK00КС Σ0f ∈ UK(1,0) и КС Σf ∈ U(0,1) , которые реализуют ФАЛf со сложностью, асимптотически не превосходящейТеорема доказана.2nn .Для построения нетривиальных КС, корректирующихболее одного обрыва или замыкания, можно использоватьследующую конструкцию. Пусть КС Σi , i = 1, . . . , r, реализует ФАЛ f и корректирует ti обрывов (замыканий), тогдаКС Σ, которая получается в результате параллельного (последовательного) соединения Σ1 , .
. . , Σr , реализует ФАЛ fс коррекцией t1 + . . . + tr + r − 1 обрывов (замыканий).Введение17Интересный пример нетривиальной самокоррекции КСдаёт контактная схема, реализующая ФАЛ `n и корректирующая один обрыв, которая получается из схемы Кардо добавлением 4 дополнительных контактов, проведенных следующим образом: для каждого σ, σ ∈ B, из входа (выхода)этой схемы, проведем контакт вида xσn (соответственно xσ1 )в вершину, соединенную контактом вида xσ̄n (соответственноxσ̄1 ) с ее выходом (соответственно входом). Указанная схемаявляется минимальной в силу леммы 2.1 главы 3 и, следовательно, справедливо утверждение.Лемма 2.3. Для n = 1, 2, .
. . имеют место равенстваKLK(0,1) (`n ) = L(0,1) `n = 4n.Литература[1] Алексеев В. Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики».
Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В. Яблонского иО. Б.
Лупанова. Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.18Введение19[9] Журавлев Ю. И. Локальные алгоритмы вычисленияинформации // Кибернетика. №1.
1965. С. 12–19.[10] Журавлев Ю. И. Теоретико-множественные методы валгебре логики // Проблемы кибернетики. Вып. 8.М.: Физматгиз, 1962. С. 5-44.[11] Кузьмин В. А. Оценки сложности реализации функций алгебры логики простейшими видами бинарныхпрограмм // Сб. «Методы дискретного анализа втеории кодов и схем». Новосибирск, 1976. Вып. 29.С. 11–39[12] Ложкин С.
А. Оценки высокой степени точности длясложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6.М.: Наука, 1996. С. 189–214.[13] Ложкин С. А. Структурное моделирование и декомпозиция для некоторых классов схем. М.: Издательский отдел ф-та ВМиК МГУ, 2001.[14] Лупанов О. Б. Асимптотические оценки сложностиуправляющих систем. М.: Изд-во МГУ, 1984.[15] Лупанов О. Б. О сложности реализации функцийалгебры логики релейно-контактными схемами //Проблемы кибернетики.
Вып. 11. М.: Наука, 1964.С. 25–48.[16] Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики.Вып. 3. М.: Физматгиз, 1960. С. 61–80.[17] Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования.20Введение// Проблемы кибернетики. Вып. 14. М.: Наука, 1965.С.
31–110.[18] Мурога С. Системы проектирования сверхбольшихинтегральных схем. М.: Мир, 1985.[19] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21.М.: Наука, 1969. С. 5–102.[20] Нигматуллин Р. Г. Сложность булевых функций.М.: Наука, 1991.[21] Поваров Г. Н.
Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. Т. 18. №2. С. 145–162.[22] Сапоженко А. А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.[23] Сапоженко А. А. Некоторые вопросы сложности алгоритмов. Издательский отдел ф-та ВМиК МГУ, 2001.[24] Сапоженко А. А., Ложкин С. А.
Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т. 12. №1. С. 42–47.[25] Фихтенгольц Г. М. Основы математического анализа,том 1. М.: Наука, 1968.[26] Фихтенгольц Г. М. Основы математического анализа,том 2. М.: Наука, 1964.[27] Чегис И. А., Яблонский С. В. Логические способыконтроля работы электрических схем // Труды МИАН СССР.
Т. 51. М.: Изд-во АН СССР, 1958. С. 270–360.Введение21[28] Яблонский С. В. Введение в дискретную математику.2-е изд., перераб. и доп. М.: Наука, 1986.[29] Яблонский С. В. Надежность управляющих систем.М.: Изд-во МГУ, 1991.[30] Яблонский С. В. Некоторые вопросы надежности иконтроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5–25.[31] Яблонский С. В.
Эквивалентные преобразования управляющих систем. М.: Изд-во МГУ, 1986.[32] Cardot C. Quelques resultats sur l’application de l’algèbrede Boole à la synthèse des circuits a relais //Ann. Telecommunications. 1952. V.7. №2. P. 75–84.[33] Shannon C. E. The syntesis of two-terminal switchingcircuits // Bell Syst. Techn. J.
1949. V. 28. №1.P. 59–98 (Русский перевод: Шеннон К. Работы потеории информации и кибернетике. М.: ИЛ, 1963.С. 59–101).[34] Wegener I. Branching programs and binary decisiondiagrams. SIAM Publishers, 2000..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
