Читать онлайн «Асимптотические оценки сложности управляющих систем»

!Л0СЮВСЮ1/1 opjiKiiA alt^iuV, 01"ди1л : :::^i-Lc:;o,A ргболол;: И ОРДЕНА ТРУдО»30Г0 1?ЛСНОгО Лч\>. *Л. i ГО^УмЛРСТ^ПШ УНИВЕРСИТЕТ км. М. Ъ. Х. :1'Гл)?-А Меха пи tec -м* *: ема а я ч ос i *к л ь* t к;* _' - L. E. I/UaHOB АСИМПТОТИЧЕСКИЕ СЦЕНКИ СЛОЖНОСТИ УПРАВЛЯЩИХ СИСТЕМ Учебное пособие Издательство Московского университета 1Э84 УДК 519. 95 Лупанов О. Б. Асимптотические оценки сложности управляющих систем, - М. : Изд-во Моск. ун-та, 1984, 138 ©. Учебное пособие охватывает значительную часть курса "Элементы дискретной математики и математической кибернетики", читаемого на механико-математическом факультете МГУ, на протяжении 10 лет, а также часть материала, предусмотренного обязательной частью программы кандидатского экзамена по специальности 01. 01. 09 (Математическая кибернетика). В пособии рассматриваются основные классы "дискретных" управляющих систем (контактные схемы, формулы, схемы из функциональных элементов). Описываются простейшие методы синтеза, метод Шеннона, асимптотически наилучшие методы синтеза, метод каскадов. Приводятся примеры применения принципа локального кодирования. Для студентов и аспирантов. Рецензенты: проф. В. Б. Кудрявцев; докт. физ. -мат. наук Ю. И. Янов Олег Борисович Лупанов АСИШТОТИЧВСКИЕ ОЦЕНКИ СЛОЖНОСТИ УПРАВШШЦИХ СИСТЕМ Заведующий редакцией С. И. Зеленский Редактор Ф. И. Горобец Технический редактор Е. Д. Захарова Подписано к печати 11,10. 84» Формат 60х9Сг/16. Бумага офсетная * I* Офсетная печать* Услф печ. л. 8, 5. Уч. =изд. л. 5,23. Тираж 1000 экз. Заказ 20ВЧ Цена 15 коп. Заказное Ордена "Знак Почетап издательство Московского университета 103009, Москва, ул. Герцена, 5/7. Типография ордена "Знак Почета" изд=ва МГУ. Оглавление Введение ; 5 Глава I. Схемы из функциональных элементов § I. Определение схем из функциональных элементов 8 § 2. Некоторые свойства функции L(F} 13 § 3. Простейшие методы синтеза 15 § 4. Метод Шеннона 19 § 5. Метод каскадов 23 § 6. Асимптотически наилучший метод 26 Глава П. Контактные схемы § 7. Общие сведения 33 § 8. Метод Шеннона и метод каскадов 37 § 9. Разбиение множества наборов на сферы ... . 44 § 10. Реализация системы конъюнкций 49 § II. Асимптотически наилучший метод 54 § 12. Асимптотика функции L (п) 58 Глава Ш. Формулы в базисе { & , V,"" } и SC -схемы § 13, Связь мевду формулами в базисе { &, V, ~~} и 3? -схемами. Простейшие оценки сложности . . 62 § 14. Асимптотически наилучший метод 64 § 15. Асаштотика функции ЛЛ (Н) 71 "лава 1У. Схемы из функциональных элементов в произвольном базисе § 16. Обобщенное разложение 75 § 17. Асимптотически наилучший метод 77 § 18. Оценка числа схем данной сложности 84 § 19. Нижние оценки для функции L ( F^) ... . 92 § 20. Некоторые дальнейшие результаты о схемах из функциональных элементов и формулах в пг^ ""^вольном базисе 95 3 5 21. Схемы из функциональных элементов с задержками 97 Глава У. Схемы для функций из специальных классов § 22. Некоторые специальные вектор-функции 108 § 23.