II. Основные классы дискретных управляющих систем, структурные представления схем и оценка их числа. Эквивалентные преобразования управляющих систем
Курс «Основы кибернетики» для бакалавров (интегрированных магистров) направления 01400 «Прикладная математика и информатика» профиля «Системное программирование и компьютерные науки»
Общая информация (учебная нагрузка, формы контроля и др.)
Курс является обязательным для всех бакалавров (интегрированных магистров) направления 01400 – «Прикладная математика и информатика». При этом объём и, в некоторой степени, программа курса варьируются в зависимости от профиля. Для бакалавров 3 курса профиля «Системное программирование и компьютерные науки» (320-328 группы) курс «Основы кибернетики» читается в 6 семестре в объёме 48 часов лекций, сопровождаемых 16 часами семинарских занятий. Курс завершается экзаменом, на который выносятся как теоретические вопросы, изложенные на лекциях, так и задачи, рассмотренные на семинарских занятиях.
В разделах 2-7 данного описания приводится подробная информация о содержании курса, программах и планах его изучения в 2017-2018 уч. году, методических материалах, а в разделах 8 и 9 – об особенностях организации учебного процесса, формах и сроках проведения контрольных мероприятий.
В соответствии с этими планами в течение семестра проводятся 3 основные (по 2 часа) контрольные работы и, возможно, несколько промежуточных (до 1 часа) тестов. По результатам контрольных и тестов с учётом посещаемости студентов, их работы на лекциях и семинарах, а также самостоятельной работы (см. раздел 8) выставляется предварительная оценка, которая играет существенную роль при формировании окончательной оценки на экзамене (см. раздел 9).
|
|
|
Чтение курса обеспечивается кафедрой математической кибернетики; лектор 2018-2019 уч. года – доцент Романов Д.С. (romanov@cs.msu.ru).
Аннотация
Курс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого был чл.-корр. РАН С.В. Яблонский, читается на факультете ВМК с первых лет его существования. Он является продолжением курса «Дискретная математика» и посвящён изложению основных моделей, методов и результатов математической кибернетики, связанных с теорией дискретных управляющих систем (УС), с задачей схемной или структурной реализации дискретных функций и алгоритмов. Методическая, и, частично, содержательная концепции данного варианта курса разработаны профессором Ложкиным С.А., который читал его для студентов программистских кафедр около 30 лет.
В курсе «Основы кибернетики» рассматриваются различные классы УС (классы схем), представляющие собой дискретные математические модели различных типов электронных схем, систем обработки информации и управления, алгоритмов и программ. Для базовых классов УС (схем из функциональных элементов, формул, контактных схем, автоматных схем), а также некоторых других типов УС, ставятся и изучаются основные задачи теории УС: задача минимизации дизъюнктивных нормальных форм (ДНФ), задача эквивалентных преобразований и структурного моделирования УС, задача синтеза УС, задача повышения надёжности и контроля УС из ненадёжных элементов и др. Рассматриваются также некоторые вопросы сложности алгоритмов. В программу курса входят классические результаты К. Шеннона, С.В. Яблонского, Ю.И. Журавлева и О.Б. Лупанова, а также некоторые результаты последних лет, полученные Ложкиным С.А. Показывается возможность практического применения этих результатов на примере задачи проектирования СБИС, которые составляют основу программно-аппаратной реализации алгоритмов.
|
|
|
Программа
I. Минимизация дизъюнктивных нормальных форм и связанные с ней задачи
Единичный куб и функции алгебры логики (ФАЛ), представление ФАЛ с помощью ДНФ. Сокращённая ДНФ и тупиковые ДНФ, их «геометрический» смысл. Способы построения однозначно получаемых ДНФ (сокращённой, пересечения тупиковых, Квайна, суммы тупиковых). Особенности ДНФ для ФАЛ из некоторых классов. Функция покрытия и алгоритм построения всех тупиковых ДНФ, оценка длины градиентного покрытия. Алгоритмические трудности минимизации ДНФ, оценки максимальных и типичных значений некоторых параметров ДНФ.
|
|
|
II. Основные классы дискретных управляющих систем, структурные представления схем и оценка их числа. Эквивалентные преобразования управляющих систем
Различные классы УС (классы схем) как структурные математические модели различных типов электронных схем, систем обработки информации и управления, алгоритмов и программ. Основные классы УС – формулы и схемы из функциональных элементов (СФЭ), контактные схемы (КС), – их структура, меры сложности, функционирование, эквивалентность, полнота. Оценка числа схем различных типов.
Понятие подсхемы и принцип эквивалентной замены. Тождества и связанные с ними эквивалентные преобразования УС. Построение полных систем тождеств для формул и СФЭ, представление об эквивалентных преобразованиях КС.
Дата добавления: 2019-03-09; просмотров: 166; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!