ОС-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).

Чтение курса обеспечивается кафедрой математической кибернетики.

1. Аннотация.

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

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

1. Программа.

I. Минимизация дизъюнктивных нормальных форм (ДНФ) и связанные с ней задачи.

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

II. Основные классы УС; оценка числа схем, их структурные представления и эквивалентные преобразования.

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

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

III. Синтез и сложность УС.

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

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

IV. Надежность и контроль управляющих систем.

Схемы из ненадежных элементов и их надежность. Теорема Неймана для СФЭ и повышение надежности СФЭ с помощью элемента голосования.

Самокорректирующиеся КС и простейшие методы их синтеза. Асимптотически наилучшие методы синтеза КС, корректирующих один обрыв или одно замыкание.

Задача контроля УС, тесты для таблиц. Алгоритм построения всех тупиковых тестов, оценки максимального и типичного значений длины диагностического теста.

V. Некоторые вопросы сложности алгоритмов (в счет часов курса
С.А. Абрамова «Вычислительная сложность алгоритмов»).

Полиномиальная сводимость языков, классы Р и NP, теорема Кука.

1. Литература.

Основная:

1. Ложкин С.А. Лекции по основам кибернетики. М.: МГУ, 2004.

2. Яблонский С.В. Элементы математической кибернетики. М.: Высшая школа, 2007.

3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

4. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики». М.: МГУ, 2002.

5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: ФИЗМАТЛИТ, 2004.

6. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд-во МГУ, 2002.

Дополнительная:

1. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов.
   М.: МГУ, 2000.

2. Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974.

3. Ложкин С.А., Марченко А.М. Математические вопросы проектирования СБИС. http://mathcyb.cs.msu.su (учебники)

4. Лупанов О.Б. Асимптотические оценки сложности управляющих систем.
   М.: МГУ, 1984.

5. Нигматулин Р.Г. Сложность булевых функций. М.: Наука, 1991.

5. Вопросы к экзамену.

1. Предварительный список вопросов к экзамену

по курсу «Основы кибернетики»

(весенний семестр 2010-2011 уч. года, 320-328 группы,
лектор – профессор С.А. Ложкин).

1. Минимизация дизъюнктивных нормальных форм и связанные с ней задачи.

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]).

1. Основные классы дискретных управляющих систем. Оценка числа схем, их структурные представления и эквивалентные преобразования.

1. Формулы, задача эквивалентных преобразований на примере формул ([1: гл.1, §1, гл.3,§1]). Оптимизация подобных формул по глубине ([1:гл.2§2]).

2. Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б₀ ([1:гл.3,§2]).

3. Задание формул графами, схемы из функциональных элементов (СФЭ). Оценка числа формул и СФЭ в базисе Б₀={&,۷,ך} ([1:гл.2,§§2,3]).

4. Эквивалентные преобразования СФЭ, моделирование эквивалентных преобразований формул в классе СФЭ. Моделирование эквивалентных преобразований в различных базисах, теорема перехода. ([1:гл.3, §§1,3]).

5. Контактные схемы (КС) и π-схемы, оценка их числа. Особенности функционирования многополюсных КС ([1:гл.2,§§5,6]).

6. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщенных тождеств ([1:гл.3,§4]).

7. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС ([1:гл.3,§5]).

8. Операция суперпозиции схем и её корректность. Разделительные КС и лемма Шеннона ([1: гл.2, §§1,6]).

9. Некоторые модификации и частные случаи основных классов схем (каскадные КС и BDD, КМОП-схемы, вычисляющие программы и др.) ([1: гл.2, §§4,7]).

1. Синтез и сложность управляющих систем.

1. Задача синтеза. Простейшие методы синтеза схем и связанные с ними верхние оценки сложности функций ([1:гл.4,§1]).

2. Некоторые нижние оценки сложности ФАЛ, нижние мощностные оценки функций Шеннона ([1:гл.4,§§2,4]).

3. Метод каскадов для КС и СФЭ, примеры его применения. Метод Шеннона ([1:гл.4,§3]).

4. Регулярные разбиения единичного куба и моделирование ФАЛ переменными. Синтез схем для некоторых дешифраторов и мультиплексоров ([1:гл.4,§§6,7]).

5. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б₀ ([1:гл.4,§5]).

6. Асимптотически наилучший метод синтеза формул в базисе Б_0, поведение функции Шеннона для глубины ФАЛ ([1:гл.4,§6]).

7. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).

8. Синтез схем для ФАЛ из специальных классов. Оценки сложности индивидуальных ФАЛ, минимальность некоторых схем ([1: гл.4, §§2,4,5], [2:часть I, разделы 2,3], [7: §§5-7], [11:гл.8]).

9. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями ([7: §8], [2: часть I, разд. I, гл.3, §§2-3]).

10. Схемы на КМОП-транзисторах и реализация ими простейших функций. Задача логического синтеза СБИС ([1:гл.2,§7], [9]).

1. Надежность и контроль управляющих систем.

1. Модели ненадежных схем, надежность СФЭ и теорема Неймана. Повышение надежности СФЭ с помощью элемента голосования ([2: ч.3, раздел 1, §§1-3]).

2. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([4:§7], [2: ч.3, раздел 2, §1]).

3. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1:гл.1,§8]).

1. Некоторые вопросы сложности алгоритмов.

1. Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировка теоремы Кука. Примеры NP – полных проблем ([6: §§4.1, 4.5-4.8]).

2. Доказательство теоремы Кука ([6 : §4.6]).

6. Типовые задачи к экзамену.

I. Задачи на ДНФ.

1. По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.

II. Задачи на эквивалентные преобразования и структурное моделирование.

1. По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств.

2. По заданной формуле построить подобную ей формулу минимальной глубины.

3. По заданной формуле с поднятыми отрицаниями построить моделирующую ее π-схему и обратно.

4. По данной каскадной КС построить инверсную каскадную КС.

III. Задачи на синтез схем.

1. По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС.

2. Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.

IV. Задачи на самокоррекцию и тесты.

1. По заданной КС построить эквивалентную ей самокорректирующуюся КС.

2. По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты.

7. План семинарских занятий.

1. Представление ФАЛ с помощью ДНФ. Сокращенная ДНФ и методы ее построения.

а) Теоретический материал: [1:с.27-35], [5:с.47, 296-298].

б) В классе ([5]): гл. I – 2.3(3); гл. IX – 2.1(1,2), 2.5 (1,5), 2.6 (1), 2.3 (1,2), 2.2 (1,2), 2.9 (1,2).

в) На дом: ([5]): гл. I – 2.3(4); гл. IX – 2.1(3), 2.5 (2,6), 2.6 (2), 2.2 (3,4), 2.3 (3,4), 2.9 (6).

1. Проводится на лекции 21.II: Ядро и ДНФ Квайна, ДНФ «сумма тупиковых». Построение всех тупиковых ДНФ.

а) Теоретический материал: [1:с.38-43, 51-55], [5:с. 301-302].