Руководящий документ белорусского государственного университета - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Руководящий документ белорусского государственного университета 1 140.07kb.
"Книга в формировании духовной культуры и государственности белорусского... 6 712.59kb.
Конспект лекций для студентов I курса исторического факультета Белорусского... 4 570.33kb.
Гафарова Ю. Необходимость Белорусского университета как транскультурной... 1 16.72kb.
Учебная программа по интегрированному модулю «Политология», включающему... 1 270.49kb.
Руководящий документ отрасли 15 3191.52kb.
Кандидата исторических наук по специальности 07. 00 1 312.75kb.
Гостехкомиссия россии руководящий документ 1 93.06kb.
Руководящий документ Средства вычислительной техники. Межсетевые... 1 171.36kb.
Первое письмо 5 th International Conference for New Generation Networks... 1 99.83kb.
Эволюция мифологической идеи вечного возвращения в европейской культуре 4 737.88kb.
Министерство экономического Министерство 1 330.72kb.
Направления изучения представлений о справедливости 1 202.17kb.

Руководящий документ белорусского государственного университета - страница №1/1


РД БГУ УПрД - 0001 – 2001





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

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

___________________________________________




Одобрена

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

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

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



УТВЕРЖДАЮ

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

профессор

Стражев В.И

«___» ____________ 200 г.


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



ТЕОРИЯ

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



© БГУ (Электронный документ)

Минск

Предисловие

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

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


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

© БГУ (Электронный документ)

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

_____________________________________________________________________________

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


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

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

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

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


"ТЕОРИЯ СИНТЕЗА И СЛОЖНОСТИ УПРАВЛЯЮЩИХ СИСТЕМ"
Цель курса: повышение уровня профессиональной компетентности, умения ориентироваться в вопросах представления и сложности реализации булевых функций в различных классах управляющих систем.

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




Название темы



Занятия, ч.

лекции

практи­ческие

КСР

1

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

1







2

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

2

1

1

3

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

2

1




4

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

2

1




5

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

2

1

1

6

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

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.

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



Тема 5.

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



Тема 6.

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



Тема 7.

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



Тема 8.

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



Тема 9.

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



Тема 10.

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



Тема 11.

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



Тема 12.

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



Тема 13.

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



Тема 14.

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



Тема 15.

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



ЛИТЕРАТУРА

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




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

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

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

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

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

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

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

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


Согласована:
Главное управление учебной и научно-методической работы

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


Начальник Е.Ф. Бондаренко








Легче быть любовником, чем мужем, ибо труднее быть остроумным каждый день, чем шутить от случая к случаю. Оноре Бальзак
ещё >>