Основная часть

Основная часть

Важной частью курса «Дискретная математика» является индивидуальная самостоятельная работа студентов над выполнением элективных заданий, цельюкоторойявляется закрепление теоретического материала и выработка умения решать примеры и задачи для последующего применения методов теории множеств, булевой алгебры и теории графов в прикладных областях информатики и вычислительной техники, а также при разработке и администрировании информационных систем.

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

· владение методологией и культурой библиографической работы, позволяющей осуществлять сбор и систематизацию отечественной и зарубежной научно-технической информации по теме исследований с привлечением современных информационных технологий;

· умение обрабатывать полученные результаты, осмысливать их с учетом имеющихся знаний и опыта;

· навыки составления отчета по результатам исследований и умение представлять результаты в соответствии с требованиями, с привлечением средств редактирования и печати.

Теоретическая часть индивидуальной работы включает:

1. Элементы алгебры множеств

Понятие множества и способы его задания. Включение и равенство множеств. Операции над множествами: объединение, пересечение, разность, дополнение. Основные свойства операций над множествами. Доказательство равенств с множествами. Покрытие и разбиение множеств. Упорядочение элементов и прямое произведение множеств. Операции проектирования и инверсии множества. Композиция множеств, свойства операций композиций.

2. Соответствия

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

3. Отношения

Определение и способы задания отношений. Основные свойства отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, асимметричность, транзитивность, связность. Отношение эквивалентности. Отношение порядка. Отношение строгого порядка. Отношение доминирования. Морфизмы отношений.

4. Нечеткие множества

Определение и способы задания нечетких множеств. Нечеткие высказывания. Операции над нечеткими множествами. Нечеткие соответствия. Нечеткие отношения.

5. Элементы общей алгебры

Понятие алгебры и подалгебры. Алгебраические структуры. Числовые кольца, числовые поля. Определение алгебраической операции и обратной ей операции. Произвольное кольцо и поле. Универсальная алгебра. Алгебра Буля и Жегалкина. Переход от одной алгебры к другой.

6. Булевы функции

Разложение булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы булевых функций. Пять классов булевых функций: класс функций, сохраняющих константу 0, класс функций, сохраняющих константу 1, класс самодвойственных функций, класс монотонных и класс линейных функций. Понятие функциональной полноты системы булевых функций. Теорема о функциональной полноте системы булевых функций.

7. Минимизация булевых функций

Постановка задачи минимизации булевых функций в классе дизъюнктивных нормальных форм. Определение минимальной ДНФ. Алгоритм минимизации булевых функций Квайна и Мак-Класки. Минимизация булевых функций с помощью диаграмм Вейча (карт Карно).

⇐ Предыдущая 123 Следующая ⇒