Опишем, например, один простейший датчик, предложенный в 1949 году Д.Х. Лемером и в дальнейшем получивший название линейного конгруэнтного метода. Для заданного начального числа a0 он вырабатывает бесконечную последовательность натуральных чисел {ak} по следующему рекуррентному закону:
ak=d+ak−1 ∙ ℓ(modN).
Здесь параметры датчика d, ℓ, N — некоторые целые числа. Запись a=b(modN), вообще говоря, означает, что a−b делится на число N; в данном случае в качестве ak берется остаток от деления d+ak−1 ∙ ℓ на N.
Поскольку все члены последовательности {ak} — неотрицательные целые числа, не превосходящие N−1, то среди них найдутся два одинаковых, скажем ai и ai+t. Тогда, как легко видеть, ai=ai+t для k≥i, т.е. последовательность — периодическая с длиной периода t. Конечно, периодичность не вполне согласуется с нашими представлениями о случайности, но, оказывается, можно подбирать такие параметры датчика, чтобы период был достаточно большим и у последовательности были многие признаки случайности.
Следует отметить, что «хорошей во всех отношениях случайной последовательности» практически не существует: насколько «хорошей» является случайная последовательность, зависит от ее назначения.
Подумайте сами:
1. Докажите следующее утверждение: вероятность того, что при k подбрасываниях кривой монеты ℓ раз выпадет орёл, равняется:
2. Придумайте такие числа d, ℓ и N, чтобы N было не слишком маленьким и длина периода последовательности, полученной линейным конгруэнтным методом, была близка к N.
3. Придумайте какой-нибудь свой датчик случайных чисел.
2.3. Что такое алгоритм и его сложность
Под алгоритмом, если говорить неформально, можно понимать четко описанную последовательность действий, приводящую к определенному результату.
Понятие алгоритма очень долго оставалось интуитивным понятием. Только в 30-е годы XX века в работах выдающихся математиков Д. Гильберта, А. Черча, С. Клини, Э. Поста и А. Тьюринга были предложены формальные определения алгоритма на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Тем самым формировалась теория алгоритмов — новое направление в математике, которое стало впоследствии теоретической основой развития вычислительной техники. В настоящее время теория алгоритмов бурно развивается, многие ее понятия проясняются и уточняются (доказуемость, разрешимость, эффективность и др.).
С нематематическими алгоритмами мы постоянно встречаемся в жизни (таковыми можно считать, например, рецепт приготовления борща или инструкцию о проведении экзамена в школе). Простейшим примером математического алгоритма может служить хорошо известный алгоритм Евклида, при помощи которого можно найти наибольший общий делитель двух чисел. А такой вид деятельности, как программирование — это постоянная работа с алгоритмами.
Очень важным понятием в математике (интуитивно ясным, но не очень просто формализуемым) является сложность алгоритма. Приведем простой пример. Пусть требуется угадать задуманное число, про которое известно, что оно натуральное и не превосходит 1000. Разрешается задавать вопросы, на которые можно ответить «да» или «нет». Одним из способов (алгоритмов) угадывания может быть такой: последовательно перебираются все числа от 1 до 1000 до тех пор, пока нужное число не будет найдено. В худшем случае для этого потребуется 999 вопросов. Однако можно предложить и другой алгоритм, позволяющий угадать число за 10 вопросов: сначала выясняется, больше ли угаданное число 500 или нет, если да, то больше 750 или нет и т.д. С каждым шагом число возможных кандидатов уменьшается в два раза. Здесь сложностью алгоритма можно считать число вопросов. Тогда первый алгоритм в 100 раз «сложнее» второго.
Если алгоритм проводит серии вычислений, сложностью алгоритма можно считать число совершаемых операций. При этом, если в алгоритме встречаются только умножение и сложение, под сложностью часто понимается только число умножений, поскольку эта операция требует существенно большего времени. На практике необходимо также учитывать стоимость операций, выполняемых алгоритмом, и т.п.
В математической теории сложности вычислений рассматриваются алгоритмы решения не конкретных задач, а так называемых массовых задач. Массовую задачу удобно представлять себе в виде бесконечной серии индивидуальных задач. Индивидуальная задача характеризуется некоторым размером, т.е. объемом входных данных, требуемых для описания этой задачи. Если размер индивидуальной задачи — некоторое натуральное число n, тогда сложность алгоритма решения массовой задачи становится функцией от n. Приведем два примера.