OK_metodichka_part_1 (1132796), страница 10
Текст из файла (страница 10)
Такимобразом, данное множество удовлетворяет условиям леммы8.2.Заметим, что сокращенная ДНФ любой ФАЛ из P2 (n)является неприводимой ДНФ, и поэтому соответствует ан(n)тицепи в ранжированном множестве (Γ , ⊆). Оценивая макn n−iсимальное значение величины i 2на отрезке i ∈ [0, n]так, как это делалось при доказательстве следствияиз лемnмы 8.2 для биномиальных коэффициентов,можнопо n−2i= bn/3c. Вказать, что оно достигается, когда i =3соответствии с формулой Стирлинга (1.3) отсюда следует,что мощность любой антицепи ранжированного множества64Глава 1. Дизъюнктивные нормальные формы(Γ(n) , ⊆), а значит и длина сокращенной ДНФ любой ФАЛ3nf из P2 (n), не больше, чем e2 √, где e2 — некоторая конnстанта.Лемма доказана.Литература[1] Алексеев В. Б.
Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей.
М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В. Яблонского иО. Б. Лупанова. Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем.
заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.6566Литература[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] Мурога С. Системы проектирования сверхбольшихинтегральных схем. М.: Мир, 1985.Литература67[18] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21.М.: Наука, 1969. С. 5–102.[19] Нигматуллин Р.
Г. Сложность булевых функций.М.: Наука, 1991.[20] Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. Т. 18. №2. С. 145–162.[21] Сапоженко А. А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.[22] Сапоженко А. А.
Некоторые вопросы сложности алгоритмов. Издательский отдел ф-та ВМиК МГУ, 2001.[23] Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т. 12. №1. С. 42–47.[24] Фихтенгольц Г. М. Основы математического анализа,том 1.
М.: Наука, 1968.[25] Фихтенгольц Г. М. Основы математического анализа,том 2. М.: Наука, 1964.[26] Чегис И. А., Яблонский С. В. Логические способыконтроля работы электрических схем // Труды МИАН СССР. Т. 51. М.: Изд-во АН СССР, 1958. С. 270–360.[27] Яблонский С. В. Введение в дискретную математику.2-е изд., перераб. и доп. М.: Наука, 1986.[28] Яблонский С. В. Надежность управляющих систем.М.: Изд-во МГУ, 1991.68Литература[29] Яблонский С. В.
Некоторые вопросы надежности иконтроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5–25.[30] Яблонский С. В. Эквивалентные преобразования управляющих систем. М.: Изд-во МГУ, 1986.[31] 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.[32] Shannon C. E. The syntesis of two-terminal switchingcircuits // Bell Syst. Techn. J. 1949. V. 28. №1.P. 59–98 (Русский перевод: Шеннон К. Работы потеории информации и кибернетике. М.: ИЛ, 1963.С.
59–101).[33] 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}
