Журнал удивительных идей


Совместный проект учителей и учеников 192 школы


Метровая система

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

Единица массы определялась через единицу длины: один килограмм равен массе воды объемом 1 дм3. Поскольку объем воды меняется в зависимости от температуры, был изготовлен специальный эталон массы в виде небольшого цилиндра из того же сплава. Очевидно, что данный подход избыточен: эталон длины можно использовать и как эталон массы. Примем, что один метр массы равен массе эталона метра.

Общепризнанной единицей для измерения интервалов времени является секунда, которая определялась как 1/86400 часть суток.

Определить новую единицу времени можно по-разному. Например, как время падения эталона метра с высоты в один метр. Мы не будем так издеваться над эталоном, к тому же, такой метод имеет низкую точность. Гораздо более подходящим является использование колебаний: метр времени – это период колебаний эталона метра на гвоздике, торчащем из стены.

 

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

Полную статью о Новой Революционной системе мер читайте на страничке автора, Pомана Парпалака!


 

Принеси то, не знаю что

Часть I. Как Кнут число случайное добывал

Случайные числа играют большую роль не только в компьютерных играх, но и в науке. Особую роль случайные числа играют в математике. Например, численное интегрирование. Определение объема фигуры, ограниченной сложными поверхностями непростая задача. Вот если бы у нас была эта фигура в реальности, скажем, сделанная из стекла, то задача решалась бы элементарно. Достаточно было бы заполнить ее водой, а потом воду взвесить. Зная плотность воды, можно вычислить ее объем, это и будет объем фигуры. Если фигура существует только виртуально и задана формулами поверхностей, ее ограничивающих, то на помощь приходят случайные числа. Поместим фигуру в куб и будем выбирать в нем случайные точки («накидывать» их в куб). Потом посчитаем количество точек, которые попали в фигуру(Nф). Зная количество всех выбранных точек (N), можно приближенно вычислить объем фигуры: (Nф/N)*Vкуба. Если точек достаточно много – приближение получается достаточно хорошим. Этот способ носит название метода Монте-Карло, по названию города, в котором  разрешены азартные игры. Ведь выигрыш на рулетке определяет случайность.

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

Прямо здесь, в статье, проведем эксперимент.
Выберем наугад 50 цифр: 3 4 5 7 5 4 5 8 6 5 1 3 4 8 7 5 9 8 4 3 6 9 9 4 3 2 1 5 8 7 6 5 7 3 4 9 6 3 2 7 8 7 3 4 7 5 9 6 5 8 7

Кажется, что последовательность случайная, но… Двойка встречается только  2 раза, зато пятерка встретилась 8 раз. Оценим нашу последовательность по другому критерию – количеству повторов. Для каждой цифры вероятность совпасть с предыдущей – одна девятая. То есть в одном случае из девяти должен произойти хотя бы один повтор. То есть на 50 чисел это 5-6 повторов. У нас же только в одном месте идут две девятки подряд. И понятно почему. Мы старались получить именно случайные числа, поэтому подсознательно избегали совпадений! Уверен, что если при этом сознательно стараться делать повторы – результат получится еще хуже…

Для компьютера получение случайных чисел вообще невыполнимая задача. Компьютер действует по четкой программе, ему нельзя скомандовать «принеси то, не знаю что». Но есть методы, позволяющие получать последовательности, которые будут казаться случайными, - так называемые, "псевдослучайные числа". Например, если бы удалось получить сто тысяч случайных чисел и затем повторять эту последовательность сначала,  то для практического использования этого будет достаточно. Последовательность из миллиона чисел, полученная десятикратным повтором последовательности из ста тысяч чисел, будет вполне хорошей, случайной. Число 100000 называется периодом, и практически у каждого генератора псевдослучайных чисел есть период.

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

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

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

Проведем исследование на трехзначных числах. Ясно, что период будет меньше 1000 и что невозможно генерировать таким образом числа от 1 до 1000, так как многие из них вообще не будут встречаться в последовательности. Но для генерации, скажем, бросаний монетки метод может вполне подойти. Будем генерировать 10000 чисел, начиная с каждого трехзначного.

int getnext(int prev)
{
    int next = prev * prev;
    next -=  next / 10000 * 10000;//удаляем первую цифру
    next /= 10;//удаляем последнюю
    return next;
}

И посчитаем сколько четных и нечетных чисел выпадет за 1000 бросаний.

Знакомство с результатами показывает, что кандидатами на хорошее начало является достаточно много чисел: 159, 264, 281, 333, 519, 528, 609, 641, 774, 778, 787, 804, 842, 896, 878, 879, 907, 917, 936 и 969. Но... все последовательности с этими начальными числами очень быстро сходятся к ...281, 896, 281, 896, 281 и т.д... Вообще, никакой случайности, хотя орлов и решек ровно пополам.

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

Вот что пишет Дональд Кнут во втором томе "Искусства Программирования", книге, ставшей классикой компьютерной литературы:

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

Алгоритм К (Супергенератор случайных чисел).
(Читатель не обязан изучать данный алгоритм во всех деталях, но рекомендуется обратить внимание на его сложность; отметим, в частности, шаги К1 и К2.)

К1. [Выбрать число итераций.] Присвоить Y наибольшую значащую цифру Х. (Мы выполним шаги К2-К13 точно Y+1 раз, т. е. применим рандомизированные преобразования случайное число раз.)
К2. [Выбрать случайный шаг] Присвоить следующую наибольшую значащую цифру X. Переходим к шагу К(3 + Z), т. е. к случайно выбранному шагу в программе.
КЗ. [Обеспечить > 5 х 109] Если X < 5000000000, присвоить X значение X + 5000000000.
К4. [Средина квадрата.] Заменить X серединой квадрата X.
К5. [Умножить.] Заменить X числом (1001001001 X) mod 1010.
К6. [Псевдодополнение.] Если X < 100000000, то присвоить X значение X + 9814055677; иначе присвоить X значение 1010- X.
К7. [Переставить половины.] Поменять местами пять младших по порядку знаков со старшими.
К8. [Умножить.] Выполнить шаг К5.
К9. [Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа X на единицу.
К10. [Модифицировать на 99999.] Если А' < 105, присвоить X значение - X 2 +99999; иначе присвоить X значение X - 99999.
К11. [Нормировать.] (На этом шаге А' не может быть равным нулю.) Если X <109, то умножить X на 10.
К12. [Модификация метода средин квадратов.] Заменить Х на средние 10 цифр числа Х(Х - 1).
К13. [Повторить?] Если Y > 0, уменьшить У на 1 и возвратиться к шагу К2. Если Y = 0, алгоритм завершен. Значение числа X, полученное на предыдущем шаге, и будет желаемым "случайным" значением.

После рассмотрения всех преобразований алгоритма К, не кажется ли правдоподобным, что можно было бы обеспечить бесконечное снабжение невероятно случайными числами? Нет! На самом деле, когда этот алгоритм впервые был реализован на компьютере, он почти немедленно сошелся к 10-значному числу 6065038420, которое по невероятному совпадению преобразовалось само в себя.

(Продолжение следует)

Ильин В.В.

М
а
т
е
м
а
т
и
к
а
Ф
и
з
и
к
а
Х
и
м
и
я
Б
и
о
л
о
г
и
я
И
н
ф
о
р
м
а
т
и
к
а