Волчкова Г. П. Сборник задач по теории алгоритмов. Организация перебора вариантов и приближенные алгоритмы: для студентов спец. 1-31 03 04 «Информатика» / Г. П. Волчкова, В. М. Котов, Е. П. Соболевская. — Минск :БГУ, 2008. —59 с.

ISBN 978-985-485-989-7

В сборник вошли задачи по двум темам, изучаемым в углубленном курсе «Теория алгоритмов». Рассматривается класс NP -трудных задач, которые решаются методами полного перебора и приближенными алгоритмами.

Предназначен для студентов БГУ, обучающихся по специальности 1-31 03 04 «Информатика».

Посмотреть в электронной библиотеке

Оглавление

От авторов

3

1. ОРГАНИЗАЦИЯ ПОЛНОГО ПЕРЕБОРА

1.1. Построение дерева решений

4

1.2. Способы обхода дерева решений

7

1.3. Сокращение числа необходимых для решения подзадач: отсев возможных вариантов ветвления

11

1.4. Функции ветвления

27

1.5. Задачи для самостоятельного решения

29

2. ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ

2.1. Основные понятия

35

2.2. Приближенный жадный алгоритм для задачи о коммивояжере

38

2.3. Приближенный жадный алгоритм для задачи о рюкзаке

39

2.4. Приближенный жадный алгоритм для задачи о суммах элементов подмножеств

40

2.5. Приближенный жадный алгоритм для задачи о раскраске графа

42

2.6. Приближенные алгоритмы с гарантированной оценкой точности

43

2.7. Задача об упаковке в контейнеры

47

2.8. Задача распределения работ на конечное число одинаковых процессоров

53

2.9. Задачи для самостоятельного решения

54

ЛИТЕРАТУРА

59