ВУЗ:
Составители:
Рубрика:
21. Что обычно понимают под двусвязным графом, компонентой двусвязности графа и точкой сочленения?
22. Какую практическую задачу можно решить путем анализа компонент двусвязности графа?
23. Какие способы обнаружения точек сочленения Вы знаете?
24. Как найденные точки сочленения определяют компоненты двусвязности графа?
25. Что понимают под транзитивным бинарным отношением и замыканием транзитивного отношения?
26. Какая прикладная задача может быть решена с помощью замыкания по транзитивности?
27. Каким образом замыкание транзитивного отношения выполняет известный Вам алгоритм?
28. Что обычно понимают под остовным деревом и минимальным остовным деревом?
29. В каких практических задачах может использоваться понятие минимального остовного дерева?
30. Каким образом алгоритм Дейкстры-Прима строит минимальное остовное дерево?
31. Как минимальное остовное дерево строит алгоритм Крускала?
32. Что Вы понимаете под кратчайшим путем из одной вершины ориентированного графа в другую во
взвешенном и невзвешенном графах?
33. В каких практических приложениях используется понятие кратчайшего пути в графе?
34. Каким образом находит кратчайший путь в графе алгоритм Дейкстры?
35. Как можно построить дерево кратчайших путей из начальной вершины графа в любую другую его
вершину с помощью алгоритма, основанного на итерационном уточнении этого дерева кратчайших путей?
36. Каким образом определяется дерево кратчайших путей из любой вершины графа до конечной вершины
с использованием алгоритма, основанного на методе динамического программирования?
Литература: [4, с. 159–196], [5, с. 92–109], [6, с. 189–209],
[7, с. 141–193].
Т е м а 5. ГЕНЕРАЦИЯ ПСЕВДОСЛУЧАЙНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ И АЛГОРИТМЫ
ПОРОЖДЕНИЯ ПЕРЕСТАНОВОК
Программа
5.1. Генерация псевдослучайных последовательностей
Моделирование равномерно распределенных случайных величин. Методы моделирования дискретных и
непрерывных случайных величин.
5.2. Алгоритмы порождения перестановок
Алгоритмы порождения перестановок в лексикографическом порядке, циклическим сдвигом и в порядке ми-
нимального изменения. Коды Грея.
Методические указания
5.1. Генерация псевдослучайных последовательностей
Познакомьтесь с понятием случайных чисел и рассмотрите примеры их использования в моделировании,
выборке, численном анализе, программировании, принятии решений и защите информации. Рассмотрите поня-
тие закона распределения последовательности случайных чисел и обратите внимание на то, какое распределе-
ние последовательности случайных чисел называется равномерным. Познакомьтесь с историей развития спосо-
бов получения случайных чисел, в частности, с методом середины квадрата, предложенным Джоном фон Ней-
маном. Определитесь, какие последовательности чисел называются псевдослучайными. Рассмотрите методы
получения последовательности случайных целых чисел, равномерно распределенных между нулем и некото-
рым положительным числом. Изучите линейный конгруэнтный метод, дающий схему наилучших датчиков
случайных чисел, которые определяются четырьмя "магическими" числами: начальное значение, множитель,
приращение и модуль. Обратите внимание на то, что линейные конгруэнтные последовательности всегда име-
ют повторяющийся цикл, называемый периодом. Проанализируйте, как правильно выбирать модуль, поскольку
от него зависит длина периода последовательности и скорость выработки чисел. Разберитесь с тем, как пра-
вильно выбирать множитель, чтобы получать период максимальной длины. Познакомьтесь с теоремой, опреде-
ляющей необходимые и достаточные условия равенства модуля и длины периода линейной конгруэнтной по-
следовательности. Изучите понятие мощности линейной конгруэнтной последовательности и познакомьтесь с
тем, как определяется мощность в условиях максимального периода. Рассмотрите и другие методы, предло-
женные для ЭВМ в качестве источников случайных чисел: квадратичный конгруэнтный метод; методы, бази-
рующиеся на использовании для получения очередного случайного числа более одного из предыдущих значе-
ний. Рассмотрите алгоритм А реализации "аддитивного датчика чисел" и познакомьтесь с его анализом. Позна-
комьтесь с алгоритмом М генерации "вполне случайной последовательности" на основе двух последовательно-
стей случайных чисел, полученных независимыми способами. Обратите особое внимание на то, что последний
метод можно усиленно рекомендовать, поскольку он позволяет получать невероятно большие периоды в случа-
ях, когда периоды исходных последовательностей являются взаимно простыми числами.
5.2. Алгоритмы порождения перестановок
