Информационные материалы

Курс «Основы кибернетики»для бакалавров (интегрированных магистров)направления 01400 «Прикладная математика иинформатика» профиля «Математические методыобработки информации и принятия решений»1. Общая информация (учебная нагрузка, формы контроля и др.)Курс является обязательным для всех бакалавров (интегрированных магистров) направления01400 – «Прикладная математика и информатика». При этом объём и, в некоторой степени,программа курса варьируются в зависимости от профиля.Для бакалавров 3 курса профиля «Математические методы обработки информации ипринятия решений» (311-319 группы) курс «Основы кибернетики» читается в 5 семестре в объёме3 часов лекций и 2 часов семинарских занятий в неделю.

Курс завершается экзаменом, на которыйвыносятся как теоретические вопросы, изложенные на лекциях, так и задачи, рассмотренные насеминарских занятиях.В разделах 2-6, 9 данного описания приводится подробная информация о содержании курса,программе и планах его изучения в 2017-2018 уч. году, методических материалах, а в разделах 7и 8 – об особенностях организации учебного процесса, формах и сроках проведения контрольныхмероприятий.В соответствии с этими планами в течение семестра проводятся 3 основные (по 2 часа)контрольные работы и, возможно, несколько промежуточных (до 1 часа) тестов.

По результатамконтрольных и тестов с учётом посещаемости студентов, их работы на лекциях и семинарах, атакже самостоятельной работы (см. раздел 7) выставляется предварительная оценка, котораяиграет существенную роль при формировании окончательной оценки на экзамене (см. раздел 8).Чтение курса обеспечивается кафедрой математической кибернетики, лектор 2017-2018 уч.года – профессор Ложкин С.А. (lozhkin@cs.msu.ru).2. АннотацияКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основнымлектором которого был чл.-корр.

РАН С.В. Яблонский, читается на факультете ВМК с первых летего существования. Он является продолжением курса «Дискретная математика» и посвящёнизложению основных моделей, методов и результатов математической кибернетики, связанных стеорией дискретных управляющих систем (УС), с задачей схемной или структурной реализациидискретных функций и алгоритмов.В нём рассматриваются различные классы УС (классы схем), представляющие собойдискретные математические модели различных типов электронных схем, систем обработкиинформации и управления, алгоритмов и программ. Для базовых классов УС (схем изфункциональных элементов, формул, контактных схем, автоматных схем), а также некоторыхдругих типов УС, ставятся и изучаются основные задачи теории УС: задача минимизациидизъюнктивных нормальных форм (ДНФ), задача эквивалентных преобразований и структурногомоделирования УС, задача синтеза УС, задача повышения надёжности и контроля УС изненадёжных элементов и др.

В программу курса входят классические результаты К. Шеннона,С.В. Яблонского, Ю.И. Журавлева и О.Б. Лупанова, а также некоторые результаты последних лет.Показывается возможность практического применения этих результатов на примере задачипроектирования СБИС, которые составляют основу программно-аппаратной реализацииалгоритмов.Продолжением курсов «Дискретная математика» и «Основы кибернетики» являетсячитаемый для бакалавров данного профиля в 7 семестре курс «Дополнительные главы дискретнойматематики и кибернетики».13. ПрограммаМинимизация дизъюнктивных нормальных форм и связанные с ней задачиЕдиничный куб и функции алгебры логики (ФАЛ), представление ФАЛ с помощью ДНФ.Сокращённая ДНФ и тупиковые ДНФ, их «геометрический» смысл.

Способы построенияоднозначно получаемых ДНФ (сокращённой, пересечения тупиковых, Квайна, суммы тупиковых).Особенности ДНФ для ФАЛ из некоторых классов. Функция покрытия и алгоритм построениявсех тупиковых ДНФ, оценка длины градиентного покрытия. Алгоритмические трудностиминимизации ДНФ, оценки максимальных и типичных значений некоторых параметров ДНФ.I.II.

Основные классы дискретных управляющих систем, структурные представления схем иоценка их числа. Эквивалентные преобразования управляющих системРазличные классы УС (классы схем) как структурные математические модели различныхтипов электронных схем, систем обработки информации и управления, алгоритмов и программ.Основные классы УС – формулы и схемы из функциональных элементов (СФЭ), контактныесхемы (КС), – их структура, меры сложности, функционирование, эквивалентность, полнота.Оценка числа схем различных типов.Понятие подсхемы и принцип эквивалентной замены.

Тождества и связанные с нимиэквивалентные преобразования УС. Построение полных систем тождеств для формул, СФЭ и КС.Отсутствие конечной полной системы тождеств для КС.III. Синтез и сложность управляющих системЗадача синтеза УС, сложность ФАЛ и функция Шеннона. Простейшие методы синтеза схем,реализация некоторых ФАЛ и оценка их сложности. Операция суперпозиции схем и еёкорректность, лемма Шеннона.

Метод каскадов для КС и СФЭ, метод Шеннона. Мощностныеметоды получения нижних оценок для функций Шеннона. Асимптотически наилучшие методысинтеза формул, СФЭ и КС. Синтез схем для ФАЛ из специальных классов и индивидуальныхФАЛ.IV. Надёжность и контроль управляющих системСамокорректирующиеся КС и простейшие методы их синтеза. Асимптотически наилучшиеметоды синтеза КС, корректирующих один обрыв или одно замыкание.Задача контроля УС, тесты для таблиц.

Алгоритм построения всех тупиковых тестов, оценкимаксимального и типичного значений длины диагностического теста.V. Некоторые вопросы и классы схем, связанные с программно-аппаратной реализациейалгоритмовНекоторые модификации основных классов схем, связанные с программной реализациейФАЛ. Автоматные функции, их реализация схемами из функциональных элементов и элементовзадержки, схемы с «мгновенными» обратными связями.

Схемы на КМОП-транзисторах, задачалогического и «физического» синтеза СБИС, основные этапы её решения. Некоторые вопросы«аппаратной» информационной безопасности.24. Предварительный список вопросов к экзамену по курсу «Основыкибернетики» (осенний семестр 2017-2018 уч. года; 311-319 группы),ориентировочный график их рассмотрения на лекцияхI.Минимизация дизъюнктивных нормальных форм и связанные с ней задачи (1.IX-22.IX)1.

Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальными формами(ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ и критерийединственности ДНФ. См. [1:гл.1,§§2,5]. (1.IX)2. Сокращённая ДНФ и способы её построения [1:гл.1,§3]. (4.IX)3. Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых. ДНФ Квайна, критерий вхожденияпростых импликант в тупиковые ДНФ и его локальность. См. [1:гл.1,§4]. (8.IX)4. Особенности ДНФ линейных и монотонных ФАЛ. Функция покрытия, таблица Квайна ипостроение всех тупиковых ДНФ. См. [1:гл.1,§§5,6]. (11.IX)5.

Градиентный алгоритм и оценка длины градиентного покрытия, лемма о «протыкающих»наборах. Использование градиентного алгоритма для построения ДНФ. См. [1:гл.1,§6].(15.IX, 18.IX)6. Задача минимизации ДНФ. Поведение функции Шеннона и оценки типичных значений дляранга и длины ДНФ [1:гл.1,§7]. (22.IX)7. Алгоритмические трудности минимизации ДНФ и оценки максимальных значенийнекоторых связанных с ней параметров [1:гл.1,§§1,3,7]. Теорема Ю.И.

Журавлёва о ДНФсумма минимальных [1:гл.1,§5]. (25.IX)II. Основные классы дискретных управляющих систем, структурные представления схем иоценка их числа. Эквивалентные преобразования управляющих систем (29.IX–23.X)8. Формулы алгебры логики, их эквивалентные преобразования с помощью тождеств.Полнота системы основных тождеств для эквивалентных преобразований формул базисаБ0={&,۷,‫}ך‬.

См. [1:гл.3,§2]. (29.IX)9. Задание формул с помощью деревьев, функционалы их сложности и соотношения междуними. Оптимизация подобных формул по глубине. См. [1:гл.2,§2]. (2.X)10. Схемы из функциональных элементов (СФЭ). Изоморфизм и эквивалентность схем,функционалы их сложности, операции приведения. Верхние оценки числа формул и СФЭ вбазисе Б0. См. [1:гл.2,§3].

(16.X, 20.X)11. Контактные схемы (КС) и π-схемы, их изоморфизм, эквивалентность, сложность, операцииприведения. Структурное моделирование некоторых формул и π-схем. Оценки числа КС ичисла π-схем. Особенности функционирования многополюсных КС.

См. [1:гл.2,§§5,6]. (6.X)12. Эквивалентные преобразования СФЭ и моделирование с их помощью формульныхпреобразований. Моделирование эквивалентных преобразований формул и схем вразличных базисах, теорема перехода. См. [1:гл.3,§§1,3]. (20.X, 23.X)13. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных иобобщённых тождеств. См. [1:гл.3,§4]. (10.X)14. Полнота системы основных тождеств.

Отсутствие конечной полной системы тождеств вклассе всех КС. См. [1:гл.3,§5]. (13.X, 16.X)III. Синтез и сложность управляющих систем (27.X–27.XI)15. Задача синтеза. Методы синтеза схем на основе ДНФ и связанные с ними верхние оценкисложности функций. См. [1:гл.4,§1]. (27.X, 30.X)16. Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторыхсхем. См.

[1:гл.4,§2], [6:§7]. (3.XI)17. Разложение ФАЛ и операция суперпозиции схем. Корректность суперпозиции длянекоторых типов схем, разделительные КС и лемма Шеннона. См. [1:гл.2,§§6,7]. (7.XI)18. Каскадные КС и СФЭ. Метод каскадов и примеры его применения, метод Шеннона.См. [1:гл.4,§3]. (10.XI)319. Нижние мощностные оценки функций Шеннона, их обобщение на случай синтеза схем дляФАЛ из специальных классов [1:гл.4,§4].