Oc3-3-09 (Программа курса)

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

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

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

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

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

Основные классы УС – формулы и схемы изфункциональных элементов (СФЭ), контактные схемы (КС), – их структура, мерысложности, функционирование, полнота. Некоторые частные случаи и обобщенияосновных классов, оценка числа схем различных типов.Эквивалентность схем. Понятие подсхемы и принцип эквивалентной замены.Тождества и связанные с ними эквивалентные преобразования УС. Построениеполных систем тождеств для формул, СФЭ и КС. Отсутствие конечной полнойсистемы тождеств для КС.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 (учебники)210. Лупанов О.Б. Асимптотические оценки сложности управляющих систем.М.: МГУ, 1984.11. Нигматулин Р.Г. Сложность булевых функций. М.: Наука, 1991.5. Вопросы к экзамену.1. Предварительный список вопросов к экзаменупо курсу «Основы кибернетики»(весенний семестр 2008-2009 уч. года, 320-328 группы,лектор – профессор С.А. Ложкин).I.Минимизация дизъюнктивных нормальных форм и связанные с ней задачи.1.

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

ДНФ Квайна и ДНФ сумма тупиковых (∑Т). Критерий вхождения простыхимпликант в ДНФ ∑Т , его локальность ([1:гл.1,§4]). Теорема Ю.И. Журавлева оДНФ сумма минимальных ([1:гл.1,§5]).4. Особенности ДНФ монотонных ФАЛ. Функция покрытия, таблица Квайна ипостроение всех тупиковых ДНФ ([1:гл.1,§§5,6]).5. Градиентный алгоритм и оценка длины градиентного покрытия, лемма о«протыкающих» наборах.

Использование градиентного алгоритма дляпостроения ДНФ ([1:гл.1,§6]).6. Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичныхзначений для ранга и длины ДНФ ([1:гл.1,§7]).7. Алгоритмические трудности минимизации ДНФ и оценки максимальныхзначений некоторых связанных с ней параметров – длины сокращенной ДНФ,числа тупиковых ДНФ ([1:гл.1, §§ 1,3,7]).II.Основные классы дискретных управляющих систем. Оценка числа схем, ихструктурные представления и эквивалентные преобразования.8. Задание формул деревьями, схемы из функциональных элементов (СФЭ).Оценка числа формул и СФЭ в базисе Б0={&,٧,‫[( }ך‬1:гл.2,§§2,3]).9. Задача эквивалентных преобразований на примере формул ([1:гл.3,§1]).Оптимизация подобных формул по глубине ([1:гл.2§2]).10. Полнота системы основных тождеств для эквивалентных преобразованийформул базиса Б0 ([1:гл.3,§2]).11. Эквивалентныепреобразования СФЭ,моделированиеэквивалентныхпреобразований формул в классе СФЭ.

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

Полнота системы основных тождеств. Отсутствие конечной полной системытождеств в классе всех КС ([1:гл.3,§5]).15. Операция суперпозиции схем и её корректность. Разделительные КС и леммаШеннона ([1: гл.2, §§1,6]).316. Некоторые модификации и частные случаи основных классов схем (каскадныеКС и СФЭ, BDD, вычисляющие программы и др.) ([1: гл.2, §§4,7]).III.Синтез и сложность управляющих систем.17. Задача синтеза. Простейшие методы синтеза схем и оценки сложности функций,нижние мощностные оценки функций Шеннона ([1:гл.4,§§1,2,4]).18. Метод каскадов для КС и СФЭ, примеры его применения.

Метод Шеннона([1:гл.4,§3]).19. Регулярные разбиения единичного куба и моделирование ФАЛ переменными.Оценкисложностинекоторыхдешифраторовимультиплексоров([1:гл.4,§§6,7]).20. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучшийметод О.Б. Лупанова для синтеза СФЭ в базисе Б0 ([1:гл.4,§5]).21. Асимптотически наилучший метод синтеза формул в базисе Б0, поведениефункции Шеннона для глубины ФАЛ ([1:гл.4,§6]).22. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).23. Синтез схем для ФАЛ из специальных классов. Оценки сложностииндивидуальных ФАЛ, минимальность некоторых схем ([1: гл.4, §§2,4,5],[2:часть I, разделы 2,3], [7: §§5-7], [11:гл.8]).24.

Реализация автоматных функций схемами из функциональных элементов иэлементов задержки, схемы с «мгновенными» обратными связями ([7: §8], [2:часть I, разд. I, гл.3, §§2-3]).25. Схемы на КМОП-транзисторах и реализация ими простейших функций. Задачалогического синтеза СБИС ([1:гл.2,§7], [9]).IV.Надежность и контроль управляющих систем.26.

Модели ненадежных схем, надежность СФЭ и теорема Неймана. Повышениенадежности СФЭ с помощью элемента голосования ([2: ч.3, раздел 1, §§1-3]).27. Самокорректирующиеся КС и методы их построения. Асимптотическинаилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([4:§7],[2: ч.3, раздел 2, §1]).28. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов,оценки длины диагностического теста ([1:гл.1,§8]).V.Некоторые вопросы сложности алгоритмов.29. Полиномиальная сводимость языков. Классы P и NP, формулировка теоремаКука. Примеры NP – полных проблем ([6: §§4.1, 4.5-4.8]).30.