Перестановки. Произведение перестановок

Алгоритмы на перестановках

Введение

Понятие алгоритма является основным для всей области компьютерного программирования. Истоки понятия «алгоритм» ассоциируются с процессом нахождения наибольшего общего делителя двух чисел [3].

Алгоритм Евклида (Е). Даны два целых положительных числа m и n. Требуется найти их наибольший делитель, т.е. наибольшее целое число, которое нацело делит оба числа m и n.

Е1. [Нахождение остатка]. Разделим m на n и, пусть остаток от деления будет равен  

  r (где 0 £ r < n).

E2. [Сравнение с нулем]. Если r = 0, то выполнение алгоритма прекращается: n —

  искомое значение.

Е3. [Замещение]. Присвоить m n, n r и вернуться к шагу Е1.

 

Каждый шаг любого алгоритма начинается заключенной в квадратные скобки фразой, которая как можно более кратко выражает содержание

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

В алгоритмах “” обозначает операцию замещения, например, n n +1 (n +1 ® n противоречит стандартным соглашениям).

 

Современное значение слова алгоритм во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа, но все-таки слово алгоритм имеет дополнительный смысловой оттенок.

Алгоритм — это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи. Помимо этого, он имеет 5 важных особенностей:

1) конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов;

2) определенность. Каждый шаг алгоритма должен быть определен;

3) ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т.е. величин, которые задаются до начала его работы или определяются динамически во время его работы;

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

5) эффективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени.

В дальнейшем перейдем к рассмотрению принципов, методов и алгоритмов, используемых при программировании.

Рекурсия

 

Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя [2].

Очевидно, что мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания.

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

С процедурой принято связывать некоторое множество локальных объектов, то есть переменных, констант, процедур, которые определены локально внутри рекурсивной процедуры, а вне ее не существуют или не имеют смысла. Каждый раз, когда такая процедура вызывается рекурсивно, для нее создается новое множество локальных переменных. Хотя они имеют те же имена, что и соответствующие элементы множества локальных переменных, созданного при предыдущем обращении к этой же процедуре, их значения различны. При работе с рекурсивными процедурами следует помнить правило: идентификаторы всегда ссылаются на множество переменных, созданное последним. То же правило относится к параметрам процедуры.

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

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

 

Пример. Реализовать вычисление факториала n! рекурсивно. Решение оформим программой на языке С++.

 

// Вычисление факториала n! рекурсивно

 

#include "stdafx.h"

#include <iostream>

 using namespace std;

#include <conio.h>

 int fact(int i);

 

 

int _tmain(int argc, _TCHAR* argv[])

{

int n;

 

cout<<"Enter n = ";

cin>>n;    

  

cout<<" \n n! = "<<fact(n)<<"\n";       

 

getch();

return 0;

}

 

int fact(int i)

{

if(i<=1) return 1;

return i*fact(i-1);

}

 

 

Информационные структуры

Стеки и очереди

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

В обоих случаях операции включения и исключения производятся только на концах последовательности [3].

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

Правило работы со стеком: «Первым пришел — последним ушел».

 

Очередь — это последовательность, в которой все включения производятся на одном конце списка (в конце очереди), в то время как все исключения производятся на другом (в начале очереди).

Правило работы с очередью: «Первым пришел — первым ушел».

Стеки и очереди имеют важное значение в бухгалтерском деле.

Введем следующие обозначения:

D Ü X Добавить X к D. Если D — стек, то X помещается в вершину, если D — очередь, то Х добавляется в ее конец.

X Ü D Присвоить переменной Х значение верхнего элемента D, если D — стек, или начального элемента, если D — очередь. Этот элемент затем из D исключается.

Последовательная реализация списков

Для стеков это распределение весьма удобно. Все, что нам нужно, это переменная, например t, чтобы следить за вершиной стека S. Предположим, что для S отведены ячейки S (1), S (2), …, S (m), тогда пустой стек соответствует случаю t = 0. Операции включения и исключения в стек при этом следующие:

 

S Ü X tt+1
if t>m then overflow {переполнение}
  else s(t) X

X Ü S if t=0 then underflow {нехватка}
  else X S(t)

              t t-1

 

Здесь overflow означает переполнение или отсутствие в стеке места для добавления X, что означает ошибку.

Underflow означает, что делается попытка удалить элемент из пустого стека, как правило, этот оператор означает окончание алгоритма.

Последовательное распределение очереди сложнее потому, что она растет на одном конце и убывает на другом.

Если ничего не предпринимать, то очередь начнет медленно двигаться и перейдет границу отведенных для нее ячеек. Чтобы это не произошло для очереди Q будем использовать m ячеек Q (0), Q (1), …, Q (m -1), связанных круговым способом, и считаем, что Q (0) следует за Q (m -1). Если использовать переменную f в качестве указателя ячейки, расположенной непосредственно перед началом очереди, а переменную r в качестве указателя ее конца, то очередь будет состоять из элементов Q (f +1), Q (f +2), …, Q (r). Согласно этому определению, пустая очередь соответствует случаю r = f. Мы имеем:

 

Q Ü X r r+1 {ограничено величиной m }
if r > m then overflow
    else Q(r) X

X Ü Q if r = f then underflow
    else X Q(f)

               f f+1

 

Деревья

 

Конечное корневое дерево Т формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m ³ 0 поддеревьев Т₁, Т₂, …, Т _m.

 Узлы, не имеющие поддеревьев, называют листьями, остальные узлы называются внутренними узлами [3]. 

 

Рис. 2.7. Дерево с 11 узлами

 

Узлы D, E, F, H, J, K — листья, А — корень, остальные — внутренние.

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

В описании соотношений между узлами дерева будем использовать терминологию генеалогических деревьев. Т.е. говорим, что в дереве (или поддереве) все узлы, являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Далее корень будем именовать отцом корней его поддеревьев, которые в свою очередь будем называть сыновьями корня. Например, на рис. 2.7 узел А является отцом узлов B, G, I; J и K — сыновья I, а C, E и F — братья и т.д. 

Все рассматриваемые деревья упорядочены, т.е. для них важен относительный порядок поддеревьев каждого узла. Т.е. деревья

 

 

считаются различными.

 

Определим лес как упорядоченное множество деревьев.

Важной разновидностью деревьев является класс бинарных деревьев. Бинарное дерево Т либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого T _l и правого T _r.

Бинарные деревья, вообще говоря, не являются подмножеством множества деревьев, они полностью отличаются своей структурой, поскольку

 

есть разные бинарные деревья.

Различие между бинарным деревом и деревом состоит в том, что не бинарное дерево не может быть пустым, и каждый узел не бинарного дерева может иметь произвольное число поддеревьев. В то же время бинарное дерево может быть пустым и каждая его вершина может иметь 0, 1 или 2 поддерева, также существует различие между левым и правым поддеревьями.

 

 

Представление деревьев

 

Почти все машинные представления деревьев основаны на связанном распределении данных. Каждый узел состоит из поля INFO и полей для указателей (рис. 2.8). На рис. 2.8 показаны связи от потомков к предку.

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

 

   

Рис. 2.8. Дерево, представленное с помощью узлов с полем INFO и указателем FATHER

 

Один из путей обхода этой трудности состоит в построении соответствия между деревьями и бинарными деревьям, поскольку бинарные деревья легко представить узлами фиксированного размера. Каждый узел при этом имеет три поля: LEFT - указатель местоположения корня левого поддерева, INFO - информационная часть содержимого узла и RIGHT - указатель местоположения корня правого поддерева.

 

Рис. 2.9. Представление бинарного дерева с помощью узлов с тремя полями LEFT, INFO, RIGHT

 

Следующее представление дерева (или леса) в виде бинарного дерева будем называть естественным соответствием между деревьями и бинарными деревьями. Оно касается того, что в поле LEFT указывается самый левый сын данного узла, а в поле RIGHT — указывается следующий брат данного узла. Например, лес, показанный на рис. 2.10 преобразуется в бинарное дерево, показанное на рис. 2.11 следующим образом:

 

Рис. 2.10. Лес

 

Рис. 2.11. Представление леса в виде бинарного дерева

 

Прохождение деревьев, леса

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

Основными способами прохождения дерева являются:

 

· в глубину (сверху вниз);

· в ширину (горизонтальный порядок);

· снизу вверх;

· в симметричном порядке (для бинарных деревьев).

 

При прохождении в глубину (прохождение в прямом порядке) узлы леса проходятся в соответствии со следующей рекурсивной процедурой:

 

1) посетить корень первого дерева;

2) пройти в глубину поддеревья первого дерева (если оно есть);

3) пройти в глубину оставшиеся деревья, если они есть.

 

Например, для леса, показанного на рис. 2.10, узлы будут проходиться в следующем порядке: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S.

Для бинарных деревьев эта процедура упрощается и выглядит следующим образом:

 

1) посетить корень;

2) пройти в глубину левое поддерево;

3) пройти в глубину правое поддерево.

 

Заметим, что прохождение леса в глубину в точности такое же, как и прохождение в глубину бинарного дерева, являющегося его представлением. Именно этот факт и делает указанное выше соответствие «естественным».

Прохождение снизу вверх (обратный порядок или концевой порядок) осуществляется согласно следующей рекурсивной процедуре:

1) пройти снизу вверх поддеревья первого дерева, если они есть;

2) посетить корень первого дерева;

3) пройти снизу вверх оставшиеся деревья, если они есть.

При этом порядке прохождения узлы леса рис. 2.10 проходятся в следующем порядке:

 

         B, D, E, F, C, G, J, I, K, L, H, A, O, P, N, R, Q, S, M.

 

Рекурсивная процедура прохождения снизу вверх применительно к бинарным деревьям имеет следующий вид:

 

1) пройти снизу вверх левое поддерево;

2) пройти снизу вверх правое поддерево;

3) посетить корень.

 

        F, E, D, K, J, L, I, H, G, C, B, P, O, R, S, Q, N, M, A.

 

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

 

1) пройти в симметричном порядке левое поддерево;

2) посетить корень;

3) пройти в симметричном порядке правое поддерево.

 

Такой способ прохождения известен как лексикографический порядок или внутренний прядок.

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

Последний способ прохождения дерева — горизонтальный порядок или в ширину. При таком способе узлы дерева проходятся слева направо уровень за уровнем от корня вниз. Т.о. узлы леса рис. 2.10 будут проходиться в следующем порядке:

 

A, M, B, C, G, H, N, Q, S, D, E, F, I, L, O, P, R, J, K.

 

Прямой порядок: A B D G C E H I F

Симметричный порядок: D G B A H E I C F

Обратный порядок: G D B H I E F C A

                    Прямой порядок: A B C E I F J D G H K L

                    Симметричный порядок: E I C F J B G D K H L A

                    Обратный порядок: I E J F C G K L H D B A

 

        Рис. 2.12. Прохождение бинарных деревьев

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

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

равное ему. Таким образом, если входной список равен 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5, то будет построено бинарное дерево, показанное на рис. 2.13.

Рис. 2.13. Бинарное дерево, построенное для сортировки

 

Такое бинарное дерево обладает тем свойством, что содержимое каждого узла в левом поддереве узла n меньше, чем содержимое узла n, а содержимое каждого узла в правом поддереве узла n больше или равно содержимому узла n. Таким образом, если дерево проходится в симметричном порядке (левое поддерево, корень, правое поддерево), то числа печатаются в возрастающем порядке, т.е. 3, 4, 4, 5, 5, 7, 9, 14, 14, 15, 16, 17, 18, 20.

Алгебраическая формула или логическая функция также могут быть представлены бинарным деревом. Например, на рис. 2.14 показано дерево, соответствующее арифметическому выражению a – b (c / d + e / f).

 

Рис. 2.14. Представление формулы в виде дерева

 

Используя дерево, легко выполнить переход от инфиксной (обычной) формы записи арифметического выражения (логической функции) к постфиксной (снизу вверх) и к префиксной (сверху вниз).

Например, A + B — инфиксная запись (левое поддерево, корень, правое поддерево);

     A B + — постфиксная запись (левое поддерево, правое поддерево, корень),

+ A B — префиксная запись (корень, левое поддерево, правое поддерево).

Итак, рис. 2.14 позволяет записать

- сверху вниз – a * b + / c d / e f (префиксная запись)

- снизу вверх a b c d / e f / + * – (постфиксная запись)

Такие формы представления позволяют оперировать без скобок, сохраняя правильность выполнения операций.

 

Высота дерева

Деревья используются не только как способ представления структур данных, но так же как средство для анализа поведения алгоритмов.

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

Наиболее важные количественные характеристики деревьев связаны с уровнями узлов. Уровень p определяется рекурсивно и считается равным 0, если р — корень дерева Т; в противном случае уровень р определяется как 1+ уровень (FATHER (p)). Понятие уровня дает нам возможность просто определить высоту дерева Т: .

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

Рис. 2.13. Бинарное дерево с длиной внешних путей, равной 21, а внутренних равной 9, h = 4

 

Прошитые бинарные деревья

Для прохождения бинарного дерева часто используют стек. Рассмотрим другой подход. Предположим, что верхний элемент стека указывает на тот узел, левое поддерево которого мы только что прошли. Предположим, что узел с правым поддеревом содержит вместо пустого указателя указатель на узел, который находится на вершине стека в данной точке алгоритма. Тогда не будет больше нужды в стеке, поскольку узел будет непосредственно указывать на своего преемника при проходе в симметричном порядке. Такой указатель называется нитью. На рис. 2.14 показано бинарное дерево со связями-нитями, заменяющими пустые указатели в узлах с пустыми правыми поддеревьями. Нити нарисованы штриховыми линиями. Такие деревья называются бинарными деревьями, симметрично прошитыми справа.

Рис. 2.14. Симметрично прошитое справа бинарное дерево

Алгоритмы на графах

Остовные деревья

 

Связанный неориентированный ациклический граф называется деревом. В связанном неориентированном графе G существует по крайней мере один путь между каждой парой вершин. Поэтому, если G — дерево, то между каждой парой вершин существует в точности один путь.

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

Особый интерес представляют остовные деревья графов, т.е. деревья, являющиеся подграфами графа G и содержащие все его вершины. Для построения остовного дерева (леса) неориентированного графа G, нужно последовательно просматривать ребра G, оставляя те, которые не образуют циклов с уже выбранными.

Во взвешенном графе часто бывает нужно определить остовное дерево (лес) с минимальным общим весом ребер, т.е. дерево (лес), у которого сумма весов всех его ребер минимальна. Такое дерево называется минимумом остовных деревьев. Процедура при этом такова. На каждом шаге выбирается новое ребро с наименьшим весом (наименьшее ребро), не образующее циклов с уже выбранными ребрами; этот процесс продолжается до тех пор, пока не будет выбрано | v |–1 ребер, образующих остовное дерево Т, где v — число узлов дерева. Этот процесс известен как жадный алгоритм.

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

Прохождение графа начинается с некоторой произвольной вершины а в заданном графе. Пусть (a, b) — ребро с наименьшим весом, инцидентное a; ребро (a, b) включается в дерево. Затем среди всех ребер, инцидентных либо а, либо b, выбирается ребро с наименьшим весом, и оно включается в частично построенное дерево. В результате в дерево добавляется новая вершина, например c. Повторяя процесс, ищем наименьшее ребро, соединяющее a, b или c с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из G не будут включены в дерево, т.е. пока дерево не станет остовным.

 

 

Примеры. В основе — граф рис. 3.1.

1. Жадный алгоритм

6 — начало:

å = 1,7

Алгоритм ближайшего соседа

å = 1,7

                                          Рис. 3.2. Алгоритмы на графах

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

 

Топологическая сортировка

 

Простейшим случаем использования техники поиска в глубину на ориентированных графах является способ пометки вершины ациклического ориентированного графа G = (V, E) числами 1, 2, …, | V |  так, что если из вершины i в вершину j идет ориентированное ребро, то i < j; такой способ пометки называется топологической сортировкой вершин графа G. Например, вершины графа на рис. 3.4 (б) топологически отсортированы, а на
рис. 3.4 (а) нет.

а)                                                      б)

                                         

Рис. 3.4. Ациклические ориентированные графы

 

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

Топологическая сортировка начинается с отыскания вершины графа G = (V, E), из которой не выходят ребра, и присвоения этой вершине наибольшего номера, а именно | V |. Эта вершина удаляется из графа вместе с входящими в нее ребрами. Поскольку оставшийся ориентированный граф также ациклический, мы повторяем процесс и присваиваем следующий наибольший номер | V | – 1 вершине, из которой не выходят ребра и т. д.

 

 

Поиск кратчайшего пути

 

Предполагаем, что имеем простой взвешенный ориентированный граф. Несуществующие ребра будем считать ребрами с бесконечным весом. Сумму весов ребер пути будем называть весом или длиной этого пути.

Алгоритм поиска кратчайшего пути следующий.

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

Если учесть, что в начале алгоритма вершине s присваивается окончательная метка 0 (нулевое расстояние до самой себя), а каждой из остальных вершин присваивается метка ¥, то на каждом шаге алгоритма одной из вершин присваивается окончательная метка и поиск продолжается дальше.     

Рис. 3.6. Простой взвешенный граф

 

Как видно из нижнего рисунка граф G из b в g имеет три кратчайших пути, длины которых равны 12. Это путь b, c, e, d, g; b, c, a, d, g и b, c, d, g.

На каждом шаге метки меняются следующим образом:

1. Каждой вершине j, не имеющей окончательной метки, присваивается новая временная метка с учетом расстояния от s до j.

2. Находится наименьшая из временных меток, она и становится окончательной меткой своей вершины. В случае равенства выбирается любая из них. Процесс продолжается до тех пор, пока вершине f не присваивается окончательная метка.

 

 

4. Генерирование случайных последовательностей

Джон фон Нейман

 

Числа, которые выбираются случайным образом, находят множество полезных применений в

· моделировании. Это позволяет сделать модели похожими на реальные явления;

· выборочном методе. Часто невозможно исследовать все варианты, но случайная выборка обеспечивает понимание того, что можно назвать «типичным поведением»;

· численном анализе. Для решения сложных задач численного анализа была разработана техника, использующая случайные числа;

· компьютерном программировании. Случайные числа являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов;

· принятии решений;

· эстетике;

· развлечениях.

 

Равномерным распределением на конечном множестве чисел называется такое распределение, при котором любое из возможных чисел имеет одинаковую вероятность появления. Если не задано определенное распределение на конечном множестве чисел, то принято считать его равномерным [8].

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

 

33317792380594909200.

 

Значит, следующим числом будет 7923805949. Претензии к такому подходу касаются вопроса: как может быть случайной последовательность, генерируемая таким образом, если каждое число полностью определяется предыдущим? Ответ состоит в том, что эта последовательность не случайна, но кажется такой. Последовательности, генерируемые детерминистическим путем, таким как этот, называются псевдослучайными или квази- случайными.

Метод середины квадратов фактически является сравнительно бедным источником случайных чисел. Опасность состоит в коротком цикле (периоде) повторяющихся элементов. Рассмотрим методы генерирования последовательности случайных дробей [8], т.е. случайных действительных чисел U_n, равномерно распределенных между нулем и единицей. Будем генерировать целое число Х _n между нулем и некоторым числом U, тогда дробь

U_n = Х _n / m

будет принадлежать [0,1]. Обычно m выбирают равным размеру слова компьютера. Обозначим m = b^e, где b — основание системы счисления, используемой ЭВМ, а e — число разрядов машины. Поэтому Х _n можно по традиции рассматривать как целое число, занимающее все компьютерное слово с точкой в правом конце слова, а U_n — как содержание того же слова с точкой в левом конце слова.

 

Линейный конгруэнтный метод

Выберем четыре числа [5]:

m — модуль, m > 0;

a — множитель, 0 £ a < m;

c — приращение, 0 £ с < m;

Х₀ — начальное значение, 0 £ Х₀ < m.

Последовательность случайных чисел {Х _n } можно получить, полагая

 

Х_n+1 = (a Х_n + c) mod m, n ³ 0                       (4.1)

 

Эта последовательность называется линейной конгруэнтной последовательностью. Например, для m = 10 и Х₀ = a = c = 7 получим последовательность

 

                                7, 6, 9, 0, 7, 6, 9, 0, …

 

В примере отражен факт, что конгруэнтная последовательность всегда образует петли, т.е. обязательно существует цикл, повторяющийся бесконечное число раз. Это свойство является общим для всех последовательностей вида X_{n +1} = f (X_n), где f — функция, преобразующая конечное множество само в себя. Повторяющиеся циклы называют периодами. Задача генерации случайных последовательностей состоит в использовании относительно длинного периода, что связано с выбором довольно большого m, так как период не может иметь больше m элементов. Другой фактор — скорость генерирования. При выборе множителя а следует принимать во внимание выводы следующей теоремы.

Теорема А. Линейная конгруэнтная последовательность, определенная числами m, a, c и X ₀, имеет период длиной m тогда и только тогда, когда:

· числа с и m взаимно простые;

· b = a - 1 кратно p для каждого простого p, являющегося делителем m;

· b кратно 4, если m кратно 4.

 

Пример. Для m = 120 назначить а и построить последовательность случайных чисел в интервале [0,1].

Решение. Выберем с = 7, a = 5, тогда при x ₀ = 1 получим следующие числа: X ₁= 12, X ₂ = 67, X ₃= 102, … Далее генерируем u ₀ = 1/120, u ₁ = 12/120, u ₂ = 67/120, u ₃ = 102/120, …

В связи с довольно простым получением случайных чисел возникает такая общепринятая ошибочная идея — достаточно взять хороший генератор случайных чисел и немного его модифицировать для того, чтобы получить «еще более случайную» последовательность. Часто это не так. Например, известно, что формула (4.1) позволяет получить более или менее хорошие случайные числа. Может ли последовательность, полученная из

 

X_{n +1} = ((a X_n) mod (m + 1) + c) mod m

быть еще более случайной? Ответ: новая последовательность является менее случайной с большей долей вероятности, т.е. мы попадаем в область генераторов типа X_{n +1}= f (X_n) с выбранной на удачу функцией f. Но известно, что эти последовательности, вероятно, ведут себя намного хуже, чем последовательности, полученные при использовании более регулярных функций (4.1). Отметим, что период линейной конгруэнтной последовательности довольно длинный; когда m приблизительно равно длине слова компьютера, обычно получаются периоды порядка 10⁹ или больше и в типичных вычислениях используется лишь маленькая часть последовательности.

Рассмотрим аддитивный генератор, предложенный Дж. Ж. Митчелом (G. J. Mitchell) и Д.Ф. Муром (D.P. Moore):

 

X_n= (X_n-24 + X_n-55) mod m n ³ 55,                        (4.2)

 

где m — четное число, числа 24 и 55 — специальные числа, выбранные для того, чтобы определить такую последовательность, младшие значащие двоичные разряды (X_nmod 2) которой имеют длину периода 2⁵⁵ – 1. Далее рассмотрим реализацию этой последовательности с помощью циклической таблицы [5].

Алгоритм В. (Аддитивный генератор чисел). В ячейки памяти Y [1], Y [2], …, Y [55] записано множество значений X ₅₄, X ₅₃, …, X ₀ соответственно; j вначале равно 24, k равно 55.

При реализации этого алгоритма на выходе последовательно получаем числа X ₅₅, X ₅₆, …

В1. [Суммирование] (Если на выходе мы оказываемся в точке X_n, то Y [ j ] равно
X_{n -24}, а Y [ k ] равно X_{n -55}). Y [ k ] (Y [ k ] + Y [ j ]) mod 2 ^e.

В2. [Продвижение] Уменьшим j и k на 1. Если j = 0, то присвоим j 24, иначе, если k = 0, присвоить k 55.

Числа 24 и 55 в выражении (4.2) называются запаздыванием, а числа X_n, определенные в (4.2) — последовательностью Фибоначчи с запаздыванием.

Вместо рассмотрения исключительно аддитивных или исключительно мультипликативных последовательностей можно построить достаточно хороший генератор случайных чисел, используя всевозможные линейные комбинации X_{n -1}, …, X_{n - k} для малых k. В этом случае наилучший результат получается, когда модуль m является большим простым числом; например, m может быть выбрано так, чтобы оно было наибольшим простым числом, которое можно записать одним компьютерным словом. Формула для генерации может быть выбрана такой:

 

X_n= (a ₁ X_{n -1} + … + a_k X_{n - k}) mod p                            (4.3)

 

с периодом p^k – 1. Здесь X ₀, X ₁, …, X_{k -1}