- •Цели и задачи дисциплины
- •Учебная нагрузка по дисциплине Курс 1 Семестр 1
- •Курс 1 Семестр 2
- •Структура дисциплины
- •Раздел 1. Задачи оптимизации на конечных множествах
- •Вопросы для самопроверки
- •Раздел 2. Задачи оптимизации на графах.
- •Вопросы для самопроверки
- •Раздел 3. Булевы функции и алгоритмические преобразования
- •Вопросы для самопроверки
Структура дисциплины
Раздел 1. Задачи оптимизации на конечных множествах
Материал раздела излагается во время лекционных занятий в первом семестре.
Дополнительную информацию по данному разделу можно получить из следующих источников:
[2] стр. 4…55;
Задание на контрольную работу № 1 состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:
Вопросы и задачи к параграфу 1.2.6 стр. 24 (задание В)
Вопросы и задачи к параграфу 1.2.8 стр. 31 (задание Д)
Вопросы и задачи к параграфу 1.4.3 стр. 44 (задание В)
Вопросы для самопроверки
Отношения. Основные свойства отношений.
Отношение эквивалентности. Отношение толерантности.
Отношения порядка. Линейное упорядочение.
Наибольший и максимальный элементы.
Задача о покрытии. Минимальные и кратчайшие покрытия.
Сокращение таблицы покрытий.
Разложение таблицы покрытий по столбцу.
Совместимые подмножества. Метод граничного перебора.
Комбинаторика. Основные виды наборов.
Раздел 2. Задачи оптимизации на графах.
Материал раздела излагается во время лекционных занятий во втором семестре. Дополнительную информацию по данному разделу можно получить из следующих источников:
[2] стр. 55…116;
Задание на курсовую работу (Часть1) состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:
Вопросы и задачи к параграфу 2.1 стр. 57
Вопросы и задачи к параграфу 2.2 стр. 66 (задание В)
Вопросы и задачи к параграфу 2.4 стр. 77 (задания А, Б, В)
Параграф 2.7.4 Построение максимального потока. Варианты стр.102
Вопросы для самопроверки
Пути в графе. Кратчайший путь. Волновой алгоритм в
не взвешенном и во взвешенном графе.
Алгоритм Дейкстры построения кратчайшего пути.
Понятие связности. Построение компоненты связности в
ненаправленном и направленном графах.
Циклы в графе. Понятие системы независимых циклов.
Цикломатическое число. Построение фундаментальной системы циклов на основе остова.
Алгоритм построения остова. Алгоритм Краскала
построения минимального остова.
Задача о раскраске графа. Хроматическое число. Алгоритм
решения задачи кратчайшей раскраски графа.
Определение потока в сети. Задача о максимальном потоке.
Алгоритм Форда-Фалкерсона.
Определение потока в сети. Задача о минимальном потоке.
Планарные графы. Теорема о четырех красках и системе циклов.
Алгоритм построения плоского изображения графа.
Раздел 3. Булевы функции и алгоритмические преобразования
Материал раздела излагается во время лекционных занятий в третьем семестре. Дополнительную информацию по данному разделу можно получить из следующих источников:
[2] стр. 116…197;
Задание на курсовую работу (Часть2) состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:
Вопросы и задачи к параграфу 3.2 стр. 136 (задание Б)
Вопросы и задачи к параграфу 3.5 стр. 171 (задание А, В, Г)
