-72-

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ

ФЕДЕРАЦИИ

Белгородская государственная технологическая академия

строительных материалов

В.В. Муромцев

ДИСКРЕТНАЯ МАТЕМАТИКА

Проектирование полнопереборных алгоритмов

Утверждено советом академии в качестве учебного пособия

Белгород 2002

УДК 519.6

ББК 22.12

М 91

Рецензенты:

Доктор технических наук, профессор кафедры программного обеспечения вычислительной техники и автоматизированных систем Белгородской государственной технологической академии строительных материалов Н.И.Корсунов

Кандидат технических наук, доцент кафедры информационных систем и технологий Белгородского университета потребительской кооперации В.В.Нешвеев

Муромцев В.В. Проектирование полнопереборных алгоритмов:

М 91 Учебное пособие.- Белгород: Изд-во БелГТАСМ,

2001.- 67 с.

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

Учебное пособие предназначено для студентов технических и экономических вузов, изучающих программирование.

Табл. 5 Ил. 13. Список лит.: 6 назв.

УДК 519.6

ББК 22.12

 Белгородская государственная технологическая академия строительных материалов (БелГТАСМ), 2002

Содержание

1. ЭЛЕМЕНТАРНЫЕ КОМБИНАТОРНЫЕ ОБЪЕКТЫ И

АЛГОРИТМЫ ИХ ПОРОЖДЕНИЯ ....................................... 4

1.1. Основные понятия и определения ....................................... 5

1.2. Общие подходы к порождению комбинаторных

объектов ................................................................................. 10

1.3. Алгоритмы порождения подмножеств ....................... 11

1.4. Алгоритмы порождения сочетаний ...................................... 16

1.5. Алгоритмы порождения перестановок ........................ 17

1.6. Алгоритм порождения размещений ...................................... 20

1.7. Алгоритмы порождения композиций ........................ 20

1.8. Алгоритм порождения разбиений ...................................... 20

2. ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ, ОСНОВАННЫХ

НА ПОЛНОМ ПЕРЕБОРЕ ТРАЕКТОРИЙ ЗАДАЧИ

ВЫБОРА ................................................................................. 22

2.1. Понятие задачи выбора .................................................... 22

2.2. Комбинаторный поиск .................................................... 25

2.3. Использование алгоритмов порождения элементарных

комбинаторных объектов при проектировании

полнопереборных алгоритмов решения задач выбора..... 28

3. НЕКОТОРЫЕ ВОПРОСЫ ТЕОРИИ СЛОЖНОСТИ ........ 29

4. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ........ 36

4.1. Порождение подмножеств .................................................... 36

4.2. Порождение перестановок .................................................... 36

4.3. Порождение сочетаний и размещений ....................... 37

4.4. Порождение композиций и разбиений ....................... 37

4.5. Решение комбинаторных задач ..................................... 38

4.6. Проектирование полно переборных алгоритмов ......... 43

СПИСОК ЛИТЕРАТУРЫ .................................................... 57

Приложение 1. ГЕНЕРАЦИЯ СЛУЧАЙНЫХ ЧИСЕЛ ......... 58

Приложение 2. ФУНКЦИИ ВРЕМЕНИ ЯЗЫКА Turbo Pascal 60

Приложение 3. ТЕКСТ ПРОГРАММЫ НА ЯЗЫКЕ Turbo

Pascal РЕАЛИЗУЮЩЕЙ ТОЧНЫЙ АЛГО-

РИТМ РЕШЕНИЯ ЗАДАЧИ О РЮКЗАКЕ.... 61

1. ЭЛЕМЕНТАРНЫЕ КОМБИНАТОРНЫЕ ОБЪЕКТЫ И

АЛГОРИТМЫ ИХ ПОРОЖДЕНИЯ

Введение

Комбинаторика – один из разделов дискретной математики, который приобрел большое значение в связи с использованием его в теории вероятностей, математической логики, теории чисел, вычислительной технике, кибернетике.

Приведем пример простейшей комбинаторной задачи. Из Киева до Новгорода–Северского можно добираться пароходом, поездом, автобусом, самолетом; из Чернигова до Новгорода–Северского – пароходом и автобусом. Сколькими способами можно осуществить путешествие по маршруту Киев – Чернигов – Новгород–Северский?

Решение. Очевидно, число разных путей из Киева до Новгорода–Северского равно 42=8, так как, выбрав один из четырех возможных способов путешествия от Киева до Чернигова, имеем два возможных способа путешествия от Чернигова до Новгорода–Северского.

Исходя из этих соображений, сформулируем основное правило комбинаторики – правило произведения.

Правило произведения. Если некоторый выбор A можно осуществить m способами, а для каждого из этих способов некоторый другой выбор B можно осуществить n способами, то выбор “A и B” в указанном порядке можно осуществить mn способами.

Это правило можно обобщить следующим образом.

Пусть требуется выполнить одно за другим k действий. Если первое действие выполнить n₁ способами, второе действие – n₂ способами, третье действие – n₃ способами и так до k действия, которое можно выполнить n_k способами, то все k действий могут быть выполнены n₁n₂n₃…n_k способами.

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

Правило суммы. Если некоторый выбор A можно осуществить m способами, а выбор B другими n способами, то выбор “либо A, либо B” можно осуществить m+n способами.

Правило суммы также может быть обобщено на произвольное число действий.