Информационные материалы (С.А. Ложкин - Лекции по основам кибернетики (2016))

Курс «Основы кибернетики»для бакалавров (интегрированных магистров)направления 01400 «Прикладная математика иинформатика» профиля «Системноепрограммирование и компьютерные науки»1. Общая информация (учебная нагрузка, формы контроля и др.)Курс является обязательным для всех бакалавров (интегрированных магистров) направления01400 – «Прикладная математика и информатика». При этом объём и, в некоторой степени,программа курса варьируются в зависимости от профиля.Для бакалавров 3 курса профиля «Системное программирование и компьютерные науки»(320-328 группы) курс «Основы кибернетики» читается в 6 семестре в объёме 48 часов лекций,сопровождаемых 16 часами семинарских занятий.

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

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

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

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

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

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

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

Автоматные функции, их реализация схемами из функциональных элементов и элементовзадержки, схемы с «мгновенными» обратными связями. Схемы на КМОП-транзисторах, задачалогического и «физического» синтеза СБИС, основные этапы её решения.24. Предварительный список вопросов к экзамену по курсу «Основыкибернетики» (весенний семестр 2015-2016 уч.

года; 320-328 группы).I.Минимизация дизъюнктивных нормальных форм и связанные с ней задачи (8.II-29.II)1. Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальными формами(ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ и критерийединственности ДНФ. См. [1:гл.1,§§2,5].2. Сокращённая ДНФ и способы её построения [1:гл.1,§3].3. Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых.

ДНФ Квайна, критерий вхожденияпростых импликант в тупиковые ДНФ и его локальность. См. [1:гл.1,§4].4. Особенности ДНФ линейных и монотонных ФАЛ. Функция покрытия, таблица Квайна ипостроение всех тупиковых ДНФ. См. [1:гл.1,§§5,6].5. Градиентный алгоритм и оценка длины градиентного покрытия, лемма о «протыкающих»наборах. Использование градиентного алгоритма для построения ДНФ. См. [1:гл.1,§6].6. Задача минимизации ДНФ. Поведение функции Шеннона и оценки типичных значений дляранга и длины ДНФ [1:гл.1,§7].7.

Алгоритмические трудности минимизации ДНФ и оценки максимальных значенийнекоторых связанных с ней параметров [1:гл.1,§§1,3,7]. Теорема Ю.И. Журавлёва о ДНФсумма минимальных [1:гл.1,§5].II. Основные классы дискретных управляющих систем, структурные представления схем иоценка их числа. Эквивалентные преобразования управляющих систем (04.III–28.III)8. Формулы и способы их задания, эквивалентность формул и функционалы их сложности[1:гл.1,§1, гл.3,§1]. Оптимизация подобных формул по глубине [1:гл.2,§2].9. Схемы из функциональных элементов (СФЭ) и операции их приведения.

Оценка числаформул и СФЭ в базисе Б0={&,۷,‫}ך‬. См. [1:гл.2,§§2,3].10. Контактные схемы (КС) и π-схемы, моделирование формул и π-схем. Оценки числа КС ичисла π-схем, особенности функционирования многополюсных КС. См. [1:гл.2,§§5,6].11. Эквивалентные преобразования формул с помощью тождеств. Полнота системы основныхтождеств для эквивалентных преобразований формул базиса Б0. См. [1:гл.3,§2].12. Эквивалентные преобразования СФЭ и моделирование с их помощью формульныхпреобразований. Моделирование эквивалентных преобразований формул и схем вразличных базисах, теорема перехода.

См. [1:гл.3,§§1,3].13. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных иобобщённых тождеств. См. [1:гл.3,§4].14. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств вклассе всех КС. См. [1:гл.3,§5].III. Синтез и сложность управляющих систем (31.III–25.IV)15. Задача синтеза. Методы синтеза схем на основе ДНФ и связанные с ними верхние оценкисложности функций. См. [1:гл.4,§1].16. Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторыхсхем. См. [1:гл.4,§2], [7:§7].17.