Вопросы к экзамену

Описание файла

PDF-файл из архива "Вопросы к экзамену", который расположен в категории "к экзамену/зачёту". Всё это находится в предмете "дополнительные главы кибернетики и теории управляющих систем" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст из PDF

Вопросы к экзамену по курсу«Дополнительные главы кибернетики и теории управляющих систем»(осенний семестр 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.

Свежие статьи
Популярно сейчас