Гродно: ГрГу им. Я.Купалы, 2007. — 128 с.
В пособии содержатся теоретический материал, примеры и задания по следующим разделам курса «Дискретная математика»: теория множеств, логика высказываний, нахождение минимального дерева-остова, построение кратчайших путей в графе, нахождение максимального потока в сети, решение задачи коммивояжера. Показаны возможности использования электронных таблиц MS Excel и надстройки «Поиск решения» для решения указанных типов задач. Содержание.
Множества.
Задачи для самостоятельного решения.
Логика высказываний.
Задачи для самостоятельного решения.
Основные понятия теории графов.
Нахождение минимального дерева-остова.
Решение задачи о нахождении минимального дерева-остова с использованием надстройки MS Excel «Поиск решения».
Задачи для самостоятельного решения.
Задачи о поиске путей.
Поиск путей с заданным количеством дуг.
Алгоритм Дейкстры для поиска кратчайшего пути между заданной парой вершин.
Решение задачи о поиске кратчайшего пути с использованием надстройки MS Excel «Поиск решения».
Поиск всех кратчайших путей (алгоритм Флойда).
Решение задачи о поиске всех кратчайших путей с использованием MS Excel.
Задачи для самостоятельного решения.
Задача о максимальном потоке и минимальном разрезе в сети.
Решение задачи о максимальном потоке и минимальном разрезе с использованием надстройки MS Excel «Поиск решения».
Задачи для самостоятельного решения.
Решение задачи коммивояжера методом ветвей и границ.
Решение задачи коммивояжера с использованием надстройки MS Excel «Поиск решения».
ε-подход к решению задачи коммивояжера.
Задачи для самостоятельного решения.
Список рекомендуемой литературы.
В пособии содержатся теоретический материал, примеры и задания по следующим разделам курса «Дискретная математика»: теория множеств, логика высказываний, нахождение минимального дерева-остова, построение кратчайших путей в графе, нахождение максимального потока в сети, решение задачи коммивояжера. Показаны возможности использования электронных таблиц MS Excel и надстройки «Поиск решения» для решения указанных типов задач. Содержание.
Множества.
Задачи для самостоятельного решения.
Логика высказываний.
Задачи для самостоятельного решения.
Основные понятия теории графов.
Нахождение минимального дерева-остова.
Решение задачи о нахождении минимального дерева-остова с использованием надстройки MS Excel «Поиск решения».
Задачи для самостоятельного решения.
Задачи о поиске путей.
Поиск путей с заданным количеством дуг.
Алгоритм Дейкстры для поиска кратчайшего пути между заданной парой вершин.
Решение задачи о поиске кратчайшего пути с использованием надстройки MS Excel «Поиск решения».
Поиск всех кратчайших путей (алгоритм Флойда).
Решение задачи о поиске всех кратчайших путей с использованием MS Excel.
Задачи для самостоятельного решения.
Задача о максимальном потоке и минимальном разрезе в сети.
Решение задачи о максимальном потоке и минимальном разрезе с использованием надстройки MS Excel «Поиск решения».
Задачи для самостоятельного решения.
Решение задачи коммивояжера методом ветвей и границ.
Решение задачи коммивояжера с использованием надстройки MS Excel «Поиск решения».
ε-подход к решению задачи коммивояжера.
Задачи для самостоятельного решения.
Список рекомендуемой литературы.