Теория синтеза и сложности управляющих систем

РУКОВОДЯЩИЙ ДОКУМЕНТ

Белорусского государственного университета

___________________________________________

Одобрена

Научно-методическим советом

Белорусского государственного университета

Протокол № от «___» _________ 200 г.

УТВЕРЖДАЮ

Ректор Белгосуниверситета

профессор

«___» ____________ 200 г.

УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ

ТЕОРИЯ

СИНТЕЗА И СЛОЖНОСТИ УПРАВЛЯЮЩИХ СИСТЕМ

Минск

Предисловие

1. РАЗРАБОТАНА Белорусским государственным университетом.

ИСПОЛНИТЕЛЬ: Г. – ст. преподаватель кафедры уравнений математической физики ММФ БГУ.

ВНЕСЕНА кафедрой уравнений математической физики и Главным управлением учебной и научно-методической работы Белорусского государственного университета.

ОДОБРЕНА Научно-методическим советом Белорусского государственного университета (Протокол от ______________ № ____ ).

2. УТВЕРЖДЕНА И ВВЕДЕНА В ДЕЙСТВИЕ приказом Ректора Белорусского государственного университета от № с 200 г.

3. ВВЕДЕНА ВПЕРВЫЕ

Настоящий руководящий документ (учебная программа дисциплины) не может быть тиражирован и распространен без разрешения Белорусского государственного университета.

_____________________________________________________________________________

Издан на русском языке

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

В настоящее время развитие теории синтеза и сложности управляющих систем сопровождается увеличением ее роли в дискретной математике и вычислительной технике. Тем более, что структура и поведение многих устройств вычислительной техники (ВТ) описываются дискретными (главным образом, булевыми) переменными.

НЕ нашли? Не то? Что вы ищете?

На этапе логического проектирования устройств ВТ возникает задача оптимизации логических схем, как по числу элементов (схемной сложности), так и по быстродействию, что невозможно без привлечения эффективных методов синтеза управляющих систем.

Вопросы, связанные со сложностью управляющих систем, возникают при чтении курсов «Дискретная математика», «Математическая логика», «САПР в микроэлектронике», «Теория автоматов», «Синтез микропрограммных автоматов», «Математические основы кибернетики».

"ТЕОРИЯ СИНТЕЗА И СЛОЖНОСТИ УПРАВЛЯЮЩИХ СИСТЕМ"

Цель курса: повышение уровня профессиональной компетентности, умения ориентироваться в вопросах представления и сложности реализации булевых функций в различных классах управляющих систем.

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

Тематический план курса "Синтез и сложность управляющих систем "

	Название темы	Занятия, ч.
лекции	практические	КСР
1	Задачи теории синтеза и сложности управляющих систем. Примеры основных модельных объектов теории синтеза и сложности (классов управляющих систем). Понятие сложности. Проблема синтеза. Проблема минимизации.	1
2	Формулы в заданном базисе. Реализация функций формулами. Д. Н.Ф. и К. Н.Ф. и их свойства. Линейная функция алгебры логики и ее реализация в классе Д. Н.Ф.	2	1	1
3	Класс произвольных контактных схем (КС). Функция проводимости контактной схемы. Сложность схемы и сложность функции в классе КС. Простейшие способы реализации функций в классе КС. Реализация в классе КС.	2	1
4	Параллельно-последовательные контактные схемы (p-схемы). Связь между p-схемами и формулами в базисе {V, &, – }.Принцип двойственности для формул в базисе {V, &, – } и p-схем. Реализация в классе p-схем.	2	1
5	Схемы из функциональных элементов (СФЭ). Вычисление функции по схеме. Сложность схемы и сложность функции. Простейшие способы реализации функций в классе СФЭ. Реализация в классе СФЭ в базисе {V, &, – }.	2	1	1
6	Сложность L(S) объекта (схемы) SÎW и сложностьбулевой функции f в данном классе управляющих систем W. Определение функции Шеннона для данного класса управляющих систем W. Свойства функции Шеннона (эффект Шеннона).	1
7	Оптимальный по порядку метод Шеннона для класса КС. Верхняя оценка Шеннона для .	2	1
8	Оптимальный по порядку метод Шеннона для класса СФЭ в базисе {V, &, – }. Верхняя оценка Шеннона для .	1	1
9	Разбиение n-мерного булева куба на непересекающиеся сферы единичного радиуса (n=2p).	2	1	1
10	Асимптотически наилучший метод реализации системы всех конъюнкций данной длины в классе КС.	2	1
11	Асимптотически наилучший метод Лупанова для КС. Верхняя оценка Лупанова для .	3	1
12	Мощностной метод Шеннона получения асимптотических нижних оценок для функции Шеннона в различных классах управляющих систем (идея метода). Мощностной метод Шеннона для КС. Нижняя оценка и асимптотика для .	2	1
13	Мощностной метод Шеннона для СФЭ в базисе {V, &, – }. Нижняя оценка и порядок функции Шеннона для СФЭ в произвольном базисе.	2	1
14	Симметрические функции. Ненулевые инвариантные классы Яблонского. Реализация функций из специальных классов.	2
15	Эффективные нижние оценки сложности. Проблема нелинейных нижних оценок для эффективно заданных последовательностей функций. Метод Храпченко и квадратичная нижняя оценка для .	2
	Итого часов	28	11	3

Тема 1.

Задачи теории синтеза и сложности управляющих систем. Примеры основных модельных объектов теории синтеза и сложности (классов управляющих систем). Понятие сложности. Проблема синтеза. Проблема минимизации.

Тема 2.

Формулы в заданном базисе. Реализация функций формулами. Д. Н.Ф. и К. Н.Ф. и их свойства. Линейная функция алгебры логики и ее реализация в классе Д. Н.Ф.

Тема 3.

Класс произвольных контактных схем (КС). Функция проводимости контактной схемы. Сложность схемы и сложность функции в классе КС. Простейшие способы реализации функций в классе КС. Реализация в классе КС.

Тема 4.

Параллельно-последовательные контактные схемы (p-схемы). Связь между p-схемами и формулами в базисе {V, &, – }.Принцип двойственности для формул в базисе {V, &, – } и p-схем. Реализация в классе p-схем.

Тема 5.

Схемы из функциональных элементов (СФЭ). Вычисление функции по схеме. Сложность схемы и сложность функции. Простейшие способы реализации функций в классе СФЭ. Реализация в классе СФЭ в базисе {V, &, – }.

Тема 6.

Сложность L(S) объекта (схемы) SÎW и сложностьбулевой функции f в данном классе управляющих систем W. Определение функции Шеннона для данного класса управляющих систем W. Свойства функции Шеннона (эффект Шеннона).

Тема 7.

Оптимальный по порядку метод Шеннона для класса КС. Верхняя оценка Шеннона для .

Тема 8.

Оптимальный по порядку метод Шеннона для класса СФЭ в базисе {V, &, – }. Верхняя оценка Шеннона для .

Тема 9.

Разбиение n-мерного булева куба на непересекающиеся сферы единичного радиуса (n=2p).

Тема 10.

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

Тема 11.

Асимптотически наилучший метод Лупанова для КС. Верхняя оценка Лупанова для .

Тема 12.

Мощностной метод Шеннона получения асимптотических нижних оценок для функции Шеннона в различных классах управляющих систем (идея метода). Мощностной метод Шеннона для КС. Нижняя оценка и асимптотика для .

Тема 13.

Мощностной метод Шеннона для СФЭ в базисе {V, &, – }. Нижняя оценка и порядок функции Шеннона для СФЭ в произвольном базисе.

Тема 14.

Симметрические функции. Ненулевые инвариантные классы Яблонского. Реализация функций из специальных классов.

Тема 15.

Эффективные нижние оценки сложности. Проблема нелинейных нижних оценок для эффективно заданных последовательностей функций. Метод Храпченко и квадратичная нижняя оценка для .

ЛИТЕРАТУРА

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

1. В. Введение в дискретную математику. М.: Наука, 1986.

2. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ. 1984.

3. Г. Сложность булевых функций. Изд-во Казанского университета. 1983.

4. П., А. Задачи и упражнения по дискретной математике. М.: Наука, 1992.

Разработчик:

Кафедра уравнений математической физики

Белорусского государственного университета

Зав. кафедрой,

профессор Н. И. Юрчук

Согласована: