ВУЗ:
Составители:
Рубрика:
Познакомьтесь с понятием перестановки и количеством перестановок из n элементов. Оцените возмож-
ность построения всех перестановок из n объектов в предположении, что все перестановки из (n − 1) объектов
уже получены. Изучите метод получения всех перестановок из n натуральных чисел, в соответствии с которым
для каждой перестановки из (n − 1) элементов образуются n других перестановок, помещением числа n на все
возможные места. Рассмотрите и другой метод получения перестановок, в соответствии с которым для каждой
перестановки из {1, 2, …, n − 1} элементов образуются n других перестановок путем присоединения к ней эле-
ментов 1/2, 3/2, …, (n − 1/2) и дальнейшего переименования их числами 1, 2, …, n с учетом значений и сохране-
нием порядка элементов. Познакомьтесь с понятиями лексикографического и антилексикографического порядков.
Изучите алгоритм порождения перестановок в лексикографическом порядке, который сначала генерирует пере-
становки в антилексикографическом порядке, а затем переразмещает их в обратном порядке.
Познакомьтесь с понятием кода Грея порядка n, которое определяют как любую циклическую последова-
тельность всех наборов длины n из нулей и единиц, при этом соседние наборы отличаются ровно в одной циф-
ре. Рассмотрите примеры использования кодов Грея при решении различных задач. В частности, познакомьтесь
с использованием кодов Грея для получения правильной последовательности перемещения дисков в известной
головоломке "Ханойская башня".
Вопросы для самопроверки
1. Какой смысл вкладывается в понятие случайного числа?
2. Какие примеры использования случайных чисел в моделировании, выборке, численном анализе, про-
граммировании, принятии решений и защите информации Вы знаете?
3. Что обычно понимают под законом распределения последовательности случайных чисел?
4. Какое распределение последовательности случайных чисел называют равномерным?
5. Какова история развития способов получения случайных чисел?
6. В чем заключается метод середины квадрата для получения случайных чисел, предложенный Джоном
фон Нейманом?
7. Какие последовательности чисел называются псевдослучайными?
8. Какие методы получения случайных целых чисел, равномерно распределенных между нулем и некоторым
положительным числом, Вы знаете?
9. В чем заключается смысл линейного конгруэнтного метода, дающего схему наилучших датчиков слу-
чайных чисел?
10. Какие четыре "магические" числа являются настроечными параметрами линейного конгруэнтного ме-
тода?
11. Что называется периодом конгруэнтной последовательности?
12. Как в линейном конгруэнтном методе правильно выбирать модуль, и какова связь значения модуля с
длиной периода и скоростью выработки чисел?
13. Каким образом в линейном конгруэнтном методе необходимо выбирать множитель, чтобы получать
период максимальной длины?
14. Что понимают под мощностью линейной конгруэнтной последовательности?
15. Как мощность линейной конгруэнтной последовательности определяется в условиях максимального
периода?
16. Какой метод получения случайных чисел называется квадратичным конгруэнтным методом?
17. Какие методы, базирующиеся на использовании для получения очередного случайного числа более од-
ного из предыдущих значений, Вам знакомы?
18. Каким образом алгоритм А реализует "аддитивный датчик чисел"?
19. В чем заключается главный смысл алгоритма М генерации "вполне случайной последовательности"?
20. В каком случае метод генерации "вполне случайной последовательности" позволяет получать неверо-
ятно большие периоды?
21. Что такое перестановка?
22. Каково количество перестановок из n элементов?
23. Какие методы получения всех перестановок из n объектов на основе всех перестановок из (n−1) объек-
тов Вы знаете?
24. Каким образом образуются все перестановки из 1, 2, …, n объектов известными Вам методами?
25. Какой порядок последовательности перестановок называется лексиграфическим и какой антилексигра-
фическим?
26. Каким образом известный алгоритм порождает перестановки в лексиграфическом порядке?
27. Что обычно понимают под кодом Грея порядка n?
28. Каким образом выглядят коды Грея порядка 1, 2 и 3?
29. Какие примеры использования кодов Грея в решении различных задач Вам знакомы?
30. Каким образом коды Грея определяют правильную последовательность перемещения дисков в известной
головоломке "Ханойская башня"?
Литература: [1, с. 75–77], [2, с. 13–51], [4, с. 283–286],
[5, с. 203–219], [6, с. 141–143].
