Основи дискретної математики (Савченко М.В.)
(odm_2009)

 Для цього курсу потрібне кодове слово


Підписатися на курс (активізуй посилання Реєстрація)

Сайт підтримки очних занять.Проект Савченко М.В.

Основи
Дискретної

Математики
http://dl.kpi.kharkov.ua/techn/nvs14
Цели и задачи дисциплины

Цель курса - освоение обучаемым фундаментальных знаний в области дискретного анализа и выработка практических навыков применения этих знаний.
Задачи курса - изложение основных положений дискретного анализа, их основных применений в современной математике и информатике, дать студенту ориентиры в дальнейшем углубленном изучении отдельных вопросов в специализированных курсах (представления данных, экстремальных задач, математической логики, теории вероятностей).

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

Содержание разделов дисциплины

1. Введение
Место дискретной математики в системе математического образования. Использование элементов дискретной математики в решении прикладных задач автоматизированного проектирования. Связь данной дисциплины с с общепрофессиональными и специальными дисциплинами. Организационно-методические указания по изучению дисциплины.

2. Основные понятия теории множеств и нечетких множеств
Канторовское определение множества. Способы задания множеств. Конечные и бесконечные множества. Пустое и универсальное множества. Мощность множества. Семейство множества.
Операции над множествами. Диаграммы Эйлера-Венна. Декартово про-
изведение множеств. Покрытие и разбиение множеств. Основные тождества алгебры множеств.
Понятие нечеткого множества. Функция принадлежности. Основные операции над нечеткими множествами и их свойства. Расстояние между нечеткими множествами, индексы нечеткости. Декомпозиция нечетких множеств.

3. Отношения и функции. Нечеткие отношения.
Понятие отношения. Бинарные отношения и способы их задания. Операции над бинарными отношениями. Обратные отношения. Композиция бинарных отношений.
Свойства бинарных отношений. Специальные бинарные отношения: порядок, эквивалентность. Представление бинарных отношений порядка с помощью диаграмм Хассе.
Соответствия, отображения и функции. Свойства отображений. Композиция отображений.
Понятие нечеткого отношения. Операции над нечеткими отношениями. Композиции нечетких отношений. Свойства нечетких отношений. Специальные типы нечетких отношений: предпорядок, порядок, подобие, различие, сходство.

4. Элементы общей алгебры
Бинарные алгебраические операции и их свойства. Понятие алгебры. Основные алгебраические структуры: группоид, моноид, полугруппа, группа, кольцо, тело, поле.

5. Комбинаторика
Классификация комбинаторных задач и характеристика их основных типов.
Основные правила комбинаторики. Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Урновые схемы. Разбиения.
Бином Ньютона, биномиальные коэффициенты, треугольник Паскаля. Основные биномиальные тождества. Полиномиальная формула.
Метод включений и исключений.

6. Основы теории графов
Понятие графа. Псевдографы, мультирафы. Ориентированные и неориентированные графы. Подграфы. Способы представления графов. Матрицы смежности и инциндентности. Маршруты, цепи, пути, циклы в графах. Основные типы графов. Операции над графами. Изоморфизм и гомеоморфизм графов.
Метрические характеристики графов. Определение центра, радиуса, диаметра, медианы графа.
Достижимость и связность в графах. Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов.
Деревья. Понятие остова графа. Методы обхода графа (поиск в глубину и в ширину) и их использование для построения остовов. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа.
Циклы и разрезы в графе. Цикломатическое и коцикломатическое числа графа. Построение матриц фундаментальных циклов и разрезов графа.
Обходы графа. Эйлеровы графы, цепи, циклы. Теорема Эйлера. Метод Флери построения эйлерова цикла в графе. Гамильтоновы цепи, пути, циклы в графе. Алгоритм Робертса и Флореса построения гамильтонова цикла в графе.
Независимость и покрытия. Независимые и доминирующие множества графа. Ядро графа. Паросочетания, покрытия, клики.
Реберная и вершинная раскраски графа. Хроматическое число. Эвристическая процедура раскраски графа.
Определение кратчайших путей (маршрутов( в графах. Алгоритм определения пути с минимальным числом дуг. Алгоритмы Дейкстры и Форда определения кратчайшего пути между двумя фиксированными вершинами взвешенного графа. Алгоритм Форда определения кратчайших путей между всеми парами вершин графа.
Потоки в транспортных сетях. Теорема о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона определения максимального потока в сети.
Некоторые прикладные задачи теории графов. Использование алгоритмов теории графов в автоматизированном проектировании.

 

Для цього курсу потрібне кодове слово