Лабораторная работа №17 Тема: Разработка алгоритмов и программ с использованием комбинаторных алгоритмов

Цель: Сформировать умения разрабатывать алгоритмы и программы с использованием комбинаторных алгоритмов

Программное обеспечение: TURBO PASCAL 7.1

Оснащение: персональный компьютер, практикум

Время проведения: 2 уч. часа

 

Литература:

Павловская Т.А. Паскаль. Программирование на языке высокого уровня. Учебник для вузов. СПб.: Питер, 2008. С. 153-162.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Опишите принцип организации динамической памяти типа стек.

2. Приведите пример описания списка.

3. Дайте определение очереди и стека.

4. Приведите пример занесения элемента в стек.

5. Сформулируйте определение двоичного дерева.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

При изучении различных комбинаторных объектов, в первую очередь, необходимо отвечать на ряд классических вопросов:

1. Сколько элементов содержит изучаемое множество?

2. Каким образом можно перебрать элементы данного множества?

3. Как можно перенумеровать эти элементы? Т. е. как, зная количество элементов n, сформировать взаимно-однозначное соответствие между элементами и числами 1:n?

Перебор 0-1 векторов

Расмотрим в качестве исследуемого комбинаторного объекта множество Bm наборов из m нулей и единиц. Для этого множества дадим ответы на поставленные вопросы.

Понятно, что множество наборов из m нулей и единиц содержит ровно 2^m элементов.

Для того, чтобы создать вычислительный процесс, при котором на каждом шаге будет формироваться новый, не встречавшийся ранее, элемент рассматриваемого множества, достаточно заметить, что существует взаимно-однозначное соответствие между числами из 0…2^m−1 и наборами 0-1 векторов. Т. е. достаточно первым взять число 0 и его двоичное представление 0, …, 0, а затем просто добавлять по единице, имитируя это на текущем наборе, пока мы не дойдем до набора из одних единиц.

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

1. Фиксируем нулевое значение m -й компоненты и перебираем все наборы длины m −1 для оставшихся компонент.

2. Меняем значение m -й компоненты с 0 на 1. Перебираем наборы длины m −1 в обратном порядке.

Приведем таблицу, показывающую процесс перебора наборов длины 4. Столбец it показывает номер текущей итерации, а столбец k_it — номер компоненты, которая подлежит обновлению.

Также легко можно дать ответ на вопрос о том, как перенумеровать наборы множества. Действительно, текущий набор множества — это двоичное представление некоторого числа, которое и является номером нашего набора. Таким образом, мы каждому набору можем сопоставить его численный эквивалент.

Коды Грея

Ранее мы рассматривали рекурсивный алгоритм перебора 0-1 наборов. Этот алгоритм позволяет перебирать все наборы B^m так, чтобы каждый следующий набор отличался от предыдущего только в одном разряде. Построенная с помощью этого алгоритма последовательность наборов (приводится в таблице) называется кодом Грея. Вообще, n -разрядный код Грея — это упорядоченная (возможно, циклическая) последовательность, состоящая из 2 ⁿ n -разрядных кодовых слов, каждое из которых отличается от соседнего в одном разряде.

 

Алгоритм Дейкстры

Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Дейкстры.

Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города А в город В (который может проходить как по железным, так и по шоссейным дорогам) и места пересадок с одного вида транспорта на другой на этом пути.

Рассмотрим алгоритм Дейкстры, который позволяет определить минимальный путь в орграфе между двумя заданными вершинами при условии, что этот путь существует.

Пусть s – начальная вершина, t – конечная вершина. На каждой итерации любая вершина v имеет метку l ^*(v), которая может быть постоянной или временной. Постоянная метка l ^*(v) – это длина кратчайшего пути от s к v, временная метка l (v) – это вес кратчайшего пути из s в v, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма.

Вторая метка Q(v) – это вершина, из которой вершина v получила свою метку.

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Приведем еще один (нерекуррентный) алгоритм генерации кодов Грея. Будем рассматривать бинарные коды Грея порядка n. Итак, на вход алгоритма подается единственное число n, которое указывает порядок кода Грея. По ходу выполнения алгоритма мы получим последовательность всех подмножеств n -элементного множества, в которой каждое последующее подмножество получается из предыдущего добавлением или удалением единственного элемента (наименьшим возможным изменением) — код Грея. При этом каждое подмножество будет представляться бинарной последовательностью B [1], …, B [ n ].

Gray-Generation(n)

for i:= 1 to n do B[i]:= 0;

i:= 0;

repeat

write (B[i], …, B[n]);

i:= i + 1; p:= 1; j:= i;

while j mod 2 = 0 do

begin

j:= j/2; p:= p + 1;

end;

if p ≤ n then B[p]:= 1 − B[p];

until p > n

Последовательность полученных подмножеств можно проиллюстрировать на графе (n -мерном кубе), вершины которого соответствуют бинарным последовательностям длины n и две вершины которого соединены ребром, если соответствующие последовательности отличаются лишь в одной позиции. Тогда эта последовательность соответствует гамильтонову пути в этом графе, т. е. пути, содержащему каждую вершину графа только один раз.

СОДЕРЖАНИЕ РАБОТЫ: Написать алгоритм и отладить программу.

Вариант	Задание
№1, 7, 13	Определить размещения , где n=1, 2, … 7, а m=12.
№2, 8, 14	Определить биномиальные коэффициенты по формуле Ньютона, .
№3, 9, 15	Определить размещения , где n=1, 2, … 9, а m=14.
№4, 10, 16	Определить биномиальные коэффициенты по формуле Ньютона, .
№5, 11, 17	Определить размещения , где n=1, 2, … 5, а m=11.
№6, 12, 18	Определить биномиальные коэффициенты по формуле Ньютона, .

 

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Сформулируйте определение размещения.

2. Сформулируйте определение сочетания.

3. Приведите примеры переборов от 0 до 1.

4. Что такое факториал?

ДОМАШНЕЕ ЗАДАНИЕ

Выучить комбинаторные алгоритмы.