Вопросы к экзамену (1156406)
Текст из файла
Вопросы к экзамену по курсу«Дополнительные главы кибернетики и теории управляющих систем»(осенний семестр 2013/2014 уч. года, лектор – профессор С.А. Ложкин).I. Асимптотически оптимальные методы синтеза схем и оценки высокойстепени точности для ряда функций Шеннона. Синтез схем для функций изспециальных классов.1. Некоторые модификации контактных схем (КС), итеративные КС (ИКС).Верхние оценки числа схем контактного типа, нижние мощностныеоценки функций Шеннона ([2:гл.2§7; гл.4 §4]).2. Формулы и схемы из функциональных элементов (СФЭ) в произвольномбазисе, усилительные СФЭ. Верхние оценки числа формул и СФЭ,нижние мощностные оценки функций Шеннона ([2:гл.2§4; гл.4 §4]).3. Универсальные системы функций алгебры логики (ФАЛ) и ихпостроение на основе селекторных разбиений переменных ([2:гл.4§8],[10]).4.
Асимптотические оценки высокой степени точности (АОВСТ) для ИКСи КС из ориентированных контактов ([10]).5. Асимптотически наилучший метод синтеза СФЭ в произвольном базисе,АОВСТ для сложности усилительных СФЭ в некоторых базисах([2:гл.4§8], [10]).6. Асимптотически наилучший метод синтеза формул в произвольномбазисе, АОВСТ для сложности формул в некоторых базисах ([2:гл.4§8],[10]).7.
Мультиплексорные ФАЛ и обобщенное разложение ([3:§16], [11]).Построение СФЭ асимптотически оптимальных как по сложности, так ипо задержке ([11], [3:§21]).8. Задача синтеза схем для функций из специальных классов, мощностныенижние оценки и примеры её решения. Инвариантные классыС.В. Яблонского, их структурные и метрические свойства ([5], [3:§25]).9.
Принцип локального кодирования О.Б. Лупанова и примеры егоприменения. ([4: гл. 6, §§4-5], [3:§§23-25], [13]).10. Синтез схем для не всюду определенных ФАЛ ([7], [14]).II. Синтез схем для индивидуальных функций и оценки их сложности.11. Асимптотика сложности контактного универсального многополюсника([12]).12. Забивание переменных константами. Сложность линейной функции вклассе СФЭ ([4:гл.8,§2]).13.
Незабиваемые множества переменных ФАЛ. Асимптотика сложностимультиплексора в классе СФЭ и некоторых классах КС ([1: §§5,7]).14. Сферические функции. Сложность линейной, а также ряда других ФАЛ вклассе КС и классе самокорректирующихся КС ([9], [4:гл.8,§1]).15. Теорема В.М. Храпченко. Сложность линейной ФАЛ в классе π-схем([4:гл.2,§3; гл.8§5]).16.
Получение высоких нижних оценок индивидуальной сложности. МетодЭ.И. Нечипорука ([4:гл.8,§6]).1Основные типы задач к экзамену.1. Задачи на АОВСТ (оценка числа схем и нижние мощностные оценки,селекторные разбиения БП и универсальные множества ФАЛ,обобщенное разложение ФАЛ, верхние АОВСТ).2. Задачи на синтез схем для ФАЛ из специальных классов (нижниемощностные оценки, принцип локального кодирования О.Б. Лупанова,не всюду определенные ФАЛ).3.
Задачи на индивидуальную сложность ФАЛ (сложность «больших»систем ФАЛ, забивание БП константами, контактная сложностьсферических ФАЛ, теорема Храпченко).Литература.Основная:1. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. М.:МГУ, 2000.2. Ложкин С.А. Лекции по основам кибернетики. М.: МГУ, 2004.3.
Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.:МГУ, 1984.4. Нигматулин Р. Г. Сложность булевых функций. М.: Наука, 1991.5. Яблонский С.В. Об алгоритмических трудностях синтеза минимальныхконтактных схем. Проблемы кибернетики, вып. 2. - М.:Физматгиз, 1959. С.75-121 (См. также Избранные труды С.В. Яблонского. М.: МАКС Пресс,2004.).6. Яблонский С.В. Надежность управляющих систем. М.: Изд-во МГУ, 1991.Дополнительная:7. Андреев А.Е. О сложности реализации частичных булевых функцийсхемами из функциональных элементов.
Дискретная математика, т. 1 (1989),№4. С. 36-45.8. Кричевский Р.Е. О сложности параллельно-последовательных контактныхсхем, реализующих одну последовательность булевых функций. Проблемыкибернетики, вып. 12. М.: Наука, 1964. С. 45-55.9. Ложкин С.А. Об одном методе получения нижних оценок сложностиконтактных схем и о некоторых минимальных схемах для линейныхфункций. Сб. трудов семинара по дискретной математике и ее приложениям.М.: Изд-во механико-математического ф-та МГУ, 1997.
С. 113-115.10. Ложкин С.А. Оценки высокой степени точности для сложностиуправляющих систем из некоторых классов. Математические вопросыкибернетики, вып. 6 М.: Наука, 1996. С. 189 - 214.11. Ложкин С.А. О глубине функций алгебры логики в произвольном полномбазисе. Вестник МГУ. Математика. Механика, 1996, №2. С.
80-82.12. Ложкин С.А, Кошкин М. А. О сложности реализации некоторых системфункций алгебры логики контактными многополюсниками. ДАН СССР, т.298 (1988), №4. С. 807-811.13. Лупанов О.Б. Об одном подходе к синтезу управляющих систем –принципелокального кодирования. Проблемы кибернетики, вып. 14. М.: Наука, 1965.С. 31-110.14. Шоломов Л.А. О реализации недоопределенных булевых функций схемамиих функциональных элементов.
Проблемы кибернетики, вып. 21. М.: Наука,1969. С. 215 - 226.2.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
