- •Проектирование полнопереборных алгоритмов
- •Содержание
- •1.1. Основные понятия и определения
- •1100, 1010, 1001, 0110, 0101, 0011.
- •1.2. Общие подходы к порождению комбинаторных объектов
- •1.3. Алгоритмы порождения подмножеств
- •1.4. Алгоритмы порождения сочетаний
- •1.5. Алгоритмы порождения перестановок
- •1.6. Алгоритм порождения размещений
- •1.7. Алгоритмы порождения композиций
- •1.8. Алгоритм порождения разбиений
- •2. Проектирование алгоритмов, основанных на полном переборе траекторий задачи выбора
- •2.1. Понятие задачи выбора
- •2.2. Комбинаторный поиск
- •Поиск с возвращением
- •Метод решета
- •2.3. Использование алгоритмов порождения элементарных комбинаторных объектов при проектировании полнопереборных алгоритмов решения задач выбора
- •3. Некоторые вопросы теории сложности
- •4. Задания для самостоятельной работы
- •4.1. Порождение подмножеств
- •4.2. Порождение перестановок
- •4.3. Порождение сочетаний и размещений
- •4.4. Порождение композиций и разбиений
- •4.5. Решение комбинаторных задач
- •4.6. Проектирование полно переборных алгоритмов
- •Список литературы
- •Генерация случайных чисел
- •Приложение 2 функции времени языка Turbo Pascal
- •Текст программы на языке Turbo Pascal реализующей точный алгоритм решения задачи о рюкзаке
- •Проектирование полнопереборных алгоритмов
- •308012, Белгород, ул. Костюкова, 46.
Проектирование полнопереборных алгоритмов
Учебное пособие
Редактор _________________________
Корректор__________________________
Изд.лиц ИД № 00434 от 10.11.99
Подписано к печати __.__.__ Формат 6084/16.
Усл.печ.л.3.5. Уч.-изд.л.4.0
Тираж 200 экз. Заказ __ Цена ___ руб.
Отпечатано в Белгородской государственной технологической академии строительных материалов.
308012, Белгород, ул. Костюкова, 46.
1Мощность бесконечного множества – более сложное понятие. Его можно найти в [1, с. 21-24].
2Другие способы задания множеств см. в [там же, с. 11-13].
3Формальное определение соответствия см. в [там же, с. 19-21].
4 Вопросы, связанные с порождением комбинаторных объектов освещены в [2, с. 182-226].
5 Вопросы, связанные с генерацией случайных чисел, рассматриваются в приложении 1.
6В данном контексте P=(p1,p2,…,pn) рассматривается как преобразование (i) для всех i=1,2,...,n и преобразование, которое задается перестановкой o=(o1,o2,…,on) является обратным к этому преобразованию (формальное определение преобразования см. в [1,с. 24]).
7 Если из контекста ясно, что рассматривается орграф, то ради сокращения речи термин "граф" употребляется вместо термина "орграф".
8 Для реализации алгоритмов рекомендуется использовать язык высокого уровня, например Turbo Pascal.
9 Функции времени языка Turbo Pascal приведены в приложении 2.
10 Для некоторых из приведенных задач (см. ниже) существует более эффективные алгоритмы решения, чем алгоритмы, основанные на простом переборе траекторий.