ОС-320-328-11 (программа 3 потока, 2011 год) (Программа курса)

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

Курс завершается экзаменом, накоторый выносятся как теоретические вопросы, изложенные на лекциях, так и задачи,рассмотренные на семинарских занятиях.В течение семестра проводятся 3 основных (по 2 часа), 3 промежуточных(по 1 часу) и несколько текущих тестов (контрольных) на знание определений,формулировок утверждений и т.п., а также умение решать задачи. По их результатам(с учетом посещаемости) выставляется предварительная оценка, которая играетсущественную роль при формировании окончательной оценки на экзамене(см. раздел 9).Чтение курса обеспечивается кафедрой математической кибернетики.2.

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

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

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

Особенности ДНФ для ФАЛ из некоторыхклассов. Функция покрытия и алгоритм построения всех тупиковых ДНФ, оценкадлины градиентного покрытия. Алгоритмические трудности минимизации ДНФ,оценки максимальных и типичных значений некоторых параметров ДНФ.II. Основные классы УС; оценка числа схем, их структурные представления иэквивалентные преобразования.1Различные классы УС (классы схем) как структурные математические моделиразличных типов электронных схем, систем обработки информации и управления,алгоритмов и программ.

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

Простейшие методысинтеза схем, реализация некоторых ФАЛ и оценка их сложности. Метод каскадов дляКС и СФЭ, метод Шеннона. Мощностные методы получения нижних оценок дляфункций Шеннона. Асимптотически наилучшие методы синтеза формул, СФЭ и КС.Синтез схем для ФАЛ из специальных классов и индивидуальных ФАЛ.Автоматные функции, их реализация схемами из функциональных элементов иэлементов задержки, схемы с «мгновенными» обратными связями. Схемы на КМОПтранзисторах, задача логического и «физического» синтеза СБИС.IV.

Надежность и контроль управляющих систем.Схемы из ненадежных элементов и их надежность. Теорема Неймана для СФЭ иповышение надежности СФЭ с помощью элемента голосования.Самокорректирующиеся КС и простейшие методы их синтеза. Асимптотическинаилучшие методы синтеза КС, корректирующих один обрыв или одно замыкание.Задача контроля УС, тесты для таблиц. Алгоритм построения всех тупиковыхтестов, оценки максимального и типичного значений длины диагностического теста.V. Некоторые вопросы сложности алгоритмов (в счет часовС.А. Абрамова «Вычислительная сложность алгоритмов»).Полиномиальная сводимость языков, классы Р и NP, теорема Кука.курса4.

Литература.Основная:1. Ложкин С.А. Лекции по основам кибернетики. М.: МГУ, 2004.2. Яблонский С.В. Элементы математической кибернетики. М.: Высшая школа,2007.3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.4. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., СапоженкоА.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики». М.: МГУ,2002.5. Гаврилов Г.П., Сапоженко А.А.

Задачи и упражнения по дискретнойматематике. М.: ФИЗМАТЛИТ, 2004.6. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд-во МГУ,2002.Дополнительная:7. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов.М.: МГУ, 2000.8. Дискретная математика и математические вопросы кибернетики. М.: Наука,1974.9.

Ложкин С.А., Марченко А.М. Математические вопросы проектированияСБИС. http://mathcyb.cs.msu.su (учебники)10. Лупанов О.Б. Асимптотические оценки сложности управляющих систем.М.: МГУ, 1984.11. Нигматулин Р.Г. Сложность булевых функций. М.: Наука, 1991.25. Вопросы к экзамену.1. Предварительный список вопросов к экзаменупо курсу «Основы кибернетики»(весенний семестр 2010-2011 уч. года, 320-328 группы,лектор – профессор С.А.

Ложкин).I.Минимизация дизъюнктивных нормальных форм и связанные с ней задачи.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,§§,3,7]). ТеоремаЮ.И. Журавлева о ДНФ сумма минимальных ([1:гл.1,§5]).II.Основные классы дискретных управляющих систем. Оценка числа схем, ихструктурные представления и эквивалентные преобразования.8. Формулы, задача эквивалентных преобразований на примере формул ([1: гл.1,§1, гл.3,§1]). Оптимизация подобных формул по глубине ([1:гл.2§2]).9.

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