|
|
Алгоритмы генерации случайных чиселГенерация случайных чисел оказалась сложной задачей. Дело в том, что такие числа должны быть совершенно не связаны с друг другом и при этом не тяготеть ни к какому конкретному множеству чисел. Скажем, бесполезно просить людей выписывать случайные цифры от 0 до 9: исследования профессор психологии Норманна Гинзбурга (Norman Ginsburg) из университета Макмастера в Канаде показали, что многие люди думают, что «случайные» означают «равномерно распределённые» и выдают мало цепочек повторяющихся или последовательно идущих цифр. Истинная случайность гораздо более подвержена кластеризации, чем кажется людям. Например, почти в половине тиражей национальных лотерей выпадает хотя бы пара последовательных номеров. Для получения рядов чисел, похожих на случайные, выведены специальные математические формулы, но у них есть свои недостатки. В 1970-х годах учёные обнаружили, что одна и формул, применяемых в компьютере и известная как RANDU, даёт небольшое систематическое отклонение. Это поставило под вопрос итоги исследований, использовавших RANDU для получения наборов случайных чисел. Прорыв в генерации истинно случайных чисел произошёл в 1949 году, когда Алан Тьюринг показал, как можно использовать электрические цепи для получения абсолютно случайных флуктуаций, вызванных тепловым движением электронов. В 1955 году корпорация RAND в Калифорнии опубликовала самую скучную книгу в мире - «Миллион случайных цифр со стандартным отклонением 100000»[10]. Весь её текст составляют пятизначные случайные числа, сгенерированные случайным устройством, имеющих особую электрическую цепь, подверженную случайным флуктуациям. Электронная случайность используется и сегодня. Например, устройство ERNIE (Electronic Random Number Indicator Equipment) и служит для генерации номеров в лотерее Premium Bond. ERNIE было построено в 1957 году, в настоящее время этим занимается ERNIE 4.
Программные генераторы пседослучайных чисел: Алгоритм RANDU Метод Фибоначчи с запаздыванием (Lagged Fibonacci generator) Линейный конгруэнтный метод Вихрь Мерсенна (Mersenne Twister) Линейные F2-генераторы Генераторы на регистрах сдвига с линейными обратными связями (LFSR) Генераторы на регистрах сдвига с обобщёнными обратными связями (FFSR) Витковые генераторы на регистрах сдвига с обобщёнными обратными связями (TGFSR) Сложность алгоритмов Когда мы считаем, что алгоритм обеспечивает удовлетворительное решение проблемы? Во-первых, он должен всегда давать правильный ответ. Во-вторых, он должен быть эффективным. Каким образом может быть проанализирована эффективность. Первой мерой эффективности является время, используемое компьютером для решения проблемы при использовании данного алгоритма когда входные данные являются определённого размера. Второй мерой эффективности является количество компьютерной памяти для применения алгоритма для входных данных определённого размера. Подобные вопросы образуют вычислительную сложность алгоритма. Различают два вида сложности алгоритмов: сложность по времени или временная сложность и сложность по памяти. Временная сложность является показателем быстродействия работы алгоритма. Сложность по памяти показывает потребности в оперативной памяти при работе алгоритма. Рассмотрение вопросов сложности по времени и по памяти является очень существенной при использовании алгоритмов. Очевидно, что важно знать, когда алгоритм даёт результат ‑ через миллисекунду, минуту или миллион лет. Также требуемая память должна быть доступна при решении проблемы. Рассмотрение сложности по памяти связано с конкретными структурами данных применяемых в алгоритме. Поскольку структуры данных детально рассматриваться не будут, то не будут и рассматриваться вопросы сложности по памяти. Поэтому мы ограничимся временной сложности. Отчего зависит временная сложность алгоритмов? В ремя выполнения большинства алгоритмов напрямую зависит от размера вводимых данных (т.е. чем больше размер, тем дольше работает алгоритм). Например, довольно долго длится процесс сортировки больших массивов данных, перемножения больших матриц и т.п. Таким образом, временную сложность алгоритма можно описать в виде функции от некоторого параметра п, связанного с размером входных данных. Каковы единицы измерения времени выполнения алгоритма? Для этого можно просто воспользоваться — секундой, миллисекундой и т.д. и с их помощью оценить время выполнения программы, реализующей рассматриваемый алгоритм. Однако у такого подхода существуют явные недостатки -определение единиц измерения времени выполнения алгоритма через единицы измерения времени имеет недостатки, поскольку результаты измерений будут зависеть от: - быстродействия конкретного компьютера; - тщательности реализации алгоритма в виде программы; - типа компилятора, использованного для генерации машинного кода; - точности хронометрирования реального времени выполнения про Поскольку перед нами стоит задача измерения эффективности алгоритма, а не реализующей его программы, мы должны воспользоваться такой системой измерений, которая бы не зависела от приведенных выше посторонних факторов. Один из возможных способов решения этой проблемы состоит в подсчете того, сколько раз выполняется КАЖДАЯ операция алгоритма. Однако подобный подход слишком сложен и, как мы увидим в дальнейшем, чаще всего не нужен. Поэтому мы должны составить список наиболее важных операций, выполняемых в алгоритме, называемых основными, или базовыми операциями (basic operation), определить, какие из них вносят наибольший вклад в общее время выполнения алгоритма, и вычислить, сколько раз эти операции выполняются. Как правило, составить список основных операций алгоритма совсем нетрудно. Обычно в него включают наиболее длительные по времени операции, выполняемые во внутреннем цикле алгоритма. Например, в большинстве алгоритмов сортировки используется метод сравнения двух элементов (ключей) списка, который сортируется. Для подобного типа алгоритмов основной является операция сравнения ключей. В качестве еще одного примера рассмотрим алгоритмы перемножения матриц и вычисления значения многочлена. В них используются две основные операции: умножение и сложение. На большинстве компьютеров команда умножения двух целых чисел выполняется намного дольше, чем сложение. Поэтому она является безусловным кандидатом на включение в список основных операций. Таким образом, временная сложность алгоритмов определяется количеством основных операций, при работе алгоритма с входными данными размерности n. Временная сложность описанная таким образом вместо реального компьютерного времени используется вследствие того, что на разных компьютерах для основных операций требуется разное количество времени. Более того, очень сложно разбить операции на элементарные операции компьютера. Далее заметим, что при малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. Для описания временной сложности алгоритмов используют три условных обозначения: О (прописная «О»), W (прописная греческая «омега») и Q (прописная греческая «тета»). Пусть t(n) и g(n) ‑ неотрицательные функции, определенные на множестве натуральных чисел. Обозначим через t(n) время выполнения алгоритма, выраженное в виде числа основных операций алгоритма, а через g(n) некоторую функцию, с которой будет сравниваться t(n). Говоря нестрого, обозначение О(g(n)) — это множество всех функций t(n), порядок роста которых при достаточно больших п не превышает (т.е. меньше или равен) некоторую константу, умноженную на значение функции g (n). Графически:
Например:
Принято выделять следующие классы временной сложности алгоритмов
Так, например, алгоритм, выполняющий только операции чтения данных и занесения их в оперативную память, имеет линейную сложность O(n). Алгоритм сортировки методом прямого выбора имеет квадратичную сложность O(n2), так как при сортировке любого массива этот алгоритм будет выполнять (n 2- n)/2 операций сравнений (при этом операций перестановок вообще может не быть, например, на упорядоченном массиве). А сложность алгоритма умножения матриц (таблиц) размера n x n будет уже кубической O(n3), т.к. для вычисления каждого элемента результирующей матрицы требуется n умножений и n-1 сложений, а всего этих элементов n 2. Второе обозначение, W(g (n)) — это множество всех функций, порядок роста которых при достаточно больших n не меньше (т.е. больше или равен) некоторой константы, умноженной на значение функции g (n).
Например:
Наконец, обозначение Q (g (n)) — это множество функций, порядок роста которых при достаточно больших п равен некоторой константе, умноженной на значение функции g (n). Таким образом, любая квадратичная функция an2 + bn +c при а > 0 принадлежит множеству Q(n 2).
Пример 1. Анализ временной сложности алгоритма сортировки методом простого выбора. Число сравнений не зависит от начального порядка элементов и равно (n2-n)/2. Таким образом, алгоритм сортировки методом прямого выбора имеет сложность O(n2). Пример 2. Анализ временной сложности алгоритма нахождения максимума конечной последовательности целых чисел. Алгоритм S2. S1. Установить временный максимум равный первому числу в последовательности. S2. Сравнить следующее число в последовательности с временным максимумом, и если оно больше, чем временный максимум, установить временный максимум равный этому числу. S3. Повторить предыдущий шаг, если есть ещё числа в последовательности. S4. Остановиться, если в последовательности нет больше чисел. Текущий временный максимум является максимумом исходной последовательности. Запишем алгоритм на псевдокоде Алгоритм S2. procedure (a1, a2,…, an:integer) max:= a1 for i:=2 to an if max<<ai then max:=ai {max является наибольшим элементом}
Решение. Количество сравнений будет использоваться как временная сложность, поскольку сравнение является основной операцией. Для того, чтобы найти наибольший элемент последовательности из n элементов, установим временный максимум равный первому элементу данной последовательности. Временной максимум сравниваем со следующим элементом последовательности, если она не исчерпана. Измеряем временный максимум, если этот элемент последовательности больше текущего временного максимума. Поскольку для сравнения используются для каждого элемента со второго до n-ого. И одно сравнение используется для выхода из цикла при i=n+1, то при использовании данного алгоритма выполняется 2 (n-1) +1 =2n – 1 сравнений. Следовательно, алгоритм нахождения максимума последовательности чисел имеет временную сложность O(n), измеренную в количестве использованных сравнений.   ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
