Елисеев Д.
Рассказы о математике с примерами на языках Python и C
Версия текста 1.4. (с) 2017
Введение
Как сказал еще Галилей, “Книга природы написана на языке математики”, и с этим сложно не согласиться. Математика это универсальный язык науки, это базовые принципы, на которых построена вся Вселенная. 2+2=4 независимо от того, верим мы в это или нет, знаем мы это или нет, существуем мы вообще или нет, и это будет верно не только для нас, но и для жителя Альфы Центавра.
Из этого следует важное правило: математические законы нельзя придумать, их можно только открыть. Треугольник подчинялся теореме Пифагора еще до того, как Пифагор открыл и сформулировал известную теорему. Число Пи было вычислено в древнем Китае, но его значение было таким всегда - еще до того как появился не только Китай, но и наша планета Земля.
Именно поэтому я надеюсь, что кто-то из читателей с помощью этой книги откроет для себя в математике что-то новое. Увы, в представлении большинства, математика - это достаточно скучная наука, вероятно так ее преподают в школе. Если кто-то с помощью этой книги найдет для себя что-то новое, можно считать что время было потрачено не зря.
Эта книга не задачник, а скорее сборник рассказов о тех или иных математических вопросах. Т.к. математические примеры без цифр бессмысленны, “практическая” часть дается на языках программирования Python и Си.
Номер версии в заголовке указан неслучайно. Эта книга не закончена, и по мере появления каких-то новых интересных вопросов она будет дополняться. Желающие также могут присылать свои истории или задачи по адресу dmitryelj@gmail.com, наиболее интересные из них будут включены в текст. Обо найденных неточностях также просьба писать на этот адрес.
Книга распространяется бесплатно в электронном виде, в различных форматах (PDF, FB2) ее можно скачать по ссылке . Там же доступен и архив с примерами программ.
Приятного чтения.
Елисеев Дмитрий
История версий текста
04.2017 - 1.0
09.2017 - 1.1, 1.2 - добавлены главы 19 и 20 про нейронные сети
11.2017 - 1.3, добавлена глава 21 про фракталы
11.2017 - 1.4, дополнена глава 7 про магические квадраты, добавлены главы 22 и 23 про “горн Гавриила” и построение графиков функций, в “Приложения” добавлен пример оптимизации кода на Python.
1. Основы языков Python и Си
Математика немыслима без расчетов и примеров вычислений. Примеры в данной книге иллюстрируются фрагментами кода на языке Python. Этот язык удобен тем, что он очень прост и подходит для начинающих, поэтому кратко рассмотрим как им пользоваться.
Для использования языка Python нужно установить интерпретатор языка с сайта / или воспользоваться онлайн-версией, например на странице . Все примеры из книги тестировались на Python версии 2.7.
Для запуска Python-программы необходимо:
- Сохранить файл в Блокноте с любым именем и расширением .py, например test1.py.
- Открыть консоль (нажать Win+R и набрать cmd), в консоли набрать команду (без кавычек) “python путь_к_файлу.py”, например “python C:\PythonApps\test1.py”.
Как более удобный вариант, можно скачать бесплатную среду разработки PyСharm community edition, и редактировать и запускать файлы в ней. Скачать PyСharm можно со страницы /.
Кстати, чтобы запустить короткую программу на Python, ее необязательно сохранять в файл, код можно ввести непосредственно в интерпретатор. Для этого достаточно запустить (Win+R) программу python.exe и просто ввести подряд соответствующие строки:
Для запуска программы на языке Си, ее сначала надо сохранить файле с расширением .c, и выполнить команду “gcc имя_файла.c”. Будет создан exe-файл, который можно запустить. Бесплатный компилятор С/C++ можно установить с помощью утилиты mingw-get, скачать которую можно на странице /. Также можно воспользоваться и любой онлайн-версией c++ компилятора, например этой.
Минимальная программа на Си выглядит так:
#include <stdio.h>
int main()
{
printf("Hello world\n");
return 0;
}
Рассмотрим простые примеры использования.
Объявление и вывод переменных
Python: достаточно ввести имя и значение.
x = 3
y = 10
print("x=", x)
print(x+y)
В отличие от языка С++, тип переменной будет определен автоматически, указывать его не нужно. Его можно при необходимости узнать, введя print (type(x)).
Cи: необходимо явно указать тип и значение переменной.
int x = 3;
int y = 10;
printf("x=%d\n", x);
printf("%d\n", x+y);
Циклы
В отличие от того же С++ или Java, циклы в Python задаются отступами, что после других языков программирования может быть непривычным. Часть кода, находящаяся внутри цикла, будет выполнена заданное количество раз.
Python
Вывод чисел от 1 до 9:
for p in range(1,10):
print (p)
Для сравнения, вот такой код без отступов работать не будет, и это важно помнить, например при копировании кода из этой книги:
for p in range(1,10):
print (p)
Вывод чисел от 1 до 9 с шагом 2:
for p in range(1,10,2):
print (p)
Кстати, в Python 2.7 функция range возвращает объект “список”, и соответственно выделяет память заданного размера. Для большинства примеров в книге это не критично, но если нужно написать код типа for p in range(1,10000000), то range следует заменить на xrange, в противном случае программа вполне может занять гигабайт памяти даже на простом с виду цикле. Для Python 3.xx это не требуется.
Си
Вывод чисел от 1 до 9:
for(int i=1; i<10; i++) {
printf("%d\n", i);
}
Вывод чисел от 1 до 9 с шагом 2:
for(int i=1; i<10; i+=2) {
printf("%d\n", i);
}
Массивы
Массив это линейный набор чисел, с которыми удобно выполнять однотипные операции, например вычисление суммы или среднего арифметического.
Python:
Объявляем массив чисел:
values = [1,2,3,5,10,15,20]
Добавляем элемент в массив:
values.append(7)
Выводим массив на экран:
print (values)
Выводим элементы массива построчно:
for p in values:
print (p)
Это же можно сделать с помощью индексов (нумерация элементов массива начинается с 0):
for i in range(0,len(values)):
print (values[i])
Можно создать массив определенного размера, заполненный определенными числами. Создадим массив из 100 элементов, заполненный нулями.
values = [0.0] * 100
print (values)
Есть немного более сложный, но и более гибкий вариант создания массива. Создадим массив из 100 элементов, заполненный нулями:
values = [0.0 for i in range(100)]
Создадим массив, заполненный числами 0,1,..,99:
values = [i for i in range(100)]
Создадим массив, заполненный квадратами чисел:
values = [i*i for i in range(100)]
Создать двухмерный массив в Python также несложно:
matrix4x4 = [ [0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]
matrix4x4[0][0] = 1
print (matrix4x4)
Аналогично вышеописанному способу, можно создать 2х-мерный массив 100x100:
values100x100 = [ [0.0 for j in range(100)] for i in range(100)]
Си:
Динамические массивы поддерживаются только в C++, статические массивы создаются так:
int values[7] = { 1,2,3,5,10,15,20 };
for(int i=0; i<7; i++) {
printf("%d\n", values[i]);
}
При желании можно слегка схитрить, если максимальный размер массива заранее известен.
int values[255] = { 1,2,3,5,10,15,20 }, cnt = 7;
for(int i=0; i<cnt; i++) {
printf("%d\n", values[i]);
}
values[cnt] = 7;
cnt++;
Можно пользоваться динамическим распределением памяти, хотя это немного сложнее:
int *valuesArray = (int*)malloc(10*sizeof(int));
valuesArray[0] = 1;
valuesArray[1] = 3;
valuesArray[2] = 15;
valuesArray = (int*)realloc(valuesArray, 25*sizeof(int));
valuesArray[20] = 555;
valuesArray[21] = 777;
for(int i=0; i<25; i++) {
printf("%d\n", valuesArray[i]);
}
free(valuesArray);
Важно заметить, что неинициализированные значения массива, например valuesArray[16], будут содержать “мусор”, некие значения которые были до этого в памяти. Си достаточно низкоуровневый язык, и такие моменты нужно учитывать. Хорошим тоном является инициализация всех переменных при их описании. Вот такой код формально не содержит ошибок:
int x;
printf("x=%d\n", x);
Однако при его запуске выведется значение 4196608, или 0, или 32, результат непредсказуем. В большой программе такие ошибки может быть сложно найти, тем более что проявляться они могут не всегда.
Арифметические операции
Сложение, умножение, деление:
x1 = 3
x2 = (2*x1*x1 + 10*x1 + 7)/x1
Возведение в степень:
x3 = x1**10
print (x1,x2,x3)
Переменную также можно увеличить или уменьшить:
x1 += 1
x1 -= 10
print (x1)
Остаток от деления:
x2 = x1 % 6
print (x2)
Условия в Python кстати, задаются отступами, аналогично циклам:
print (x1)
if x1 % 2 == 0:
print("x1 четное число")
else:
print("x1 нечетное число")
Подсчитаем сумму элементов массива:
values = [1,2,3,5,10,15,20]
s = 0
for p in values:
s += p
print(s)
Также для этого можно воспользоваться встроенной функцией sum:
values = [1,2,3,5,10,15,20]
print(sum(values))
В Си вычисление суммы элементов массива выглядит так:
int sum = 0;
for(int i=0; i<cnt; i++) {
sum += values[i];
}
printf("Sum=%d\n", sum);
Для более сложных операций в Python необходимо подключить модуль math. Вычисление квадратного корня:
import math
print (math.sqrt(x3))
Python может делать вычисления с большими числами, что достаточно удобно:
import math
x1 = 12131231321321312312313131124141
print (10*x1)
print (math.sqrt(x1))
Можно вывести даже факториал числа 1024, что не сделает ни один калькулятор:
import math
print(math.factorial(1024))
Пожалуй, этого не хватит чтобы устроиться на работу программистом, но вполне достаточно для понимания большинства примеров в книге. Теперь вернемся к математике.
2. Математические фокусы
Для “разминки” рассмотрим несколько фокусов, имеющих отношение к числам. Никаких особых сложностей в них нет, но их знание поможет развеселить или удивить знакомых знанием математики.
Умножение в уме числа на 11
Рассмотрим простой пример:
26*11 = 286
Сделать это в уме просто, если взять сумму чисел и поместить в середину:
26*11 = 2 [ 2+6 ] 6
Аналогично 43*11 = 473, 71*11 = 781 и так далее.
Чуть длиннее расчет, если сумма чисел больше либо равна 10. Но и тогда все просто: в середину кладется младший разряд, а 1 уходит в старший разряд:
47*11 = [4] [4+7=11] [7] = [4+1] [1] [7] = 517
94*11 = [9] [9+4=13] [4] = [10] [3] [4] = 1034
Возведение в квадрат числа, оканчивающегося на 5
Подсчитать это тоже просто. Если число рассмотреть как пару NM, то первая часть результата - это число N, умноженное на (N+1), вторая часть числа - всегда 25.
352 = [3*4] [25] = 12 25
Аналогично:
252 = [2*3] 25 = 625 852 = [8*9] 25 = 7225 и так далее.
Отгадывание результата
Попросим человека загадать любое число. Например 73. Затем чтобы еще больше запутать отгадывающего, попросим сделать следующие действия:
- удвоим число (146)
- прибавляем 12 (158)
- разделим на 2 (79)
- вычтем из результата исходное число (79-73 = 6)
В конце мы отгадываем, что результат - 6. Суть в том, что число 6 появляется независимо от того, какое число загадал человек.
Математически, это доказывается очень просто:
(2*n + 12)/2 - n = n + 6 - n = 6, независимо от значения n.
Отгадывание чисел
Есть другой фокус с отгадыванием чисел. Попросим человека загадать трехзначное число, числа в котором идут в порядке уменьшения (например 752). Попросим человека выполнить следующие действия:
- записать число в обратном порядке (257)
- вычесть его из исходного числа (752 - 257 = 495)
- к ответу добавить его же, только в обратном порядке (495 + 594)
Получится число 1089, которое “фокусник” и объявляет публике.
Математически это тоже несложно доказать.
- Любое число вида abc в десятичной системе счисления представляется так:
abc = 100*a + 10*b +c.
- Разность чисел abc - cba:
100*a + 10*b +c + 100 - 100*c-10*b - a = 100*a - 100*c - (a - c) = 100*(a-c) - (a-c)
- Т.к. по условию a - c > 0, то результат можно записать в виде:
100*(a-c) - (a-c) = 100*(a-c) - 100 + 90 + 10 - (a-c) = 100*(a-c-1) + 10*9 + (10-a+c)
Мы узнали разряды числа, получающегося в результате:
a1=a-c-1, b1 = 9, c1 =10-a+c
- Добавляем число в обратном порядке:
a1b1c1 + c1b1a1 = 100*(a-c-1) + 10*9 + (10-a+c) + 100* (10-a+c) + 10*9 + a-c-1
Если раскрыть все скобки и сократить лишнее, в остатке будет 1089.
3. Число Пи
Вобьем в стену гвоздь, привяжем к нему веревку с карандашом, начертим окружность. Как вычислить длину окружности? Сегодня ответ знает каждый школьник - с помощью числа Пи. Число Пи - несомненно, одна из основных констант мироздания, значение которой было известно еще в древности. Оно используется везде, от кройки и шитья до расчетов гармонических колебаний в физике и радиотехнике.
Сегодня достаточно нажать одну кнопку на калькуляторе, чтобы увидеть его значение:
Pi = 3.1415926535… Однако, за этими цифрами скрывается многовековая история. Что такое число Пи? Это отношение длины окружности к ее диаметру. То что это константа, не зависящая от самой длины окружности, знали еще в древности. Но чему она равна? Есть ли у этого числа какая-то внутренняя структура, неизвестная закономерность? Узнать это хотели многие. Самый простой и очевидный способ - взять и измерить. Примерно так вероятно и поступали в древности, точность разумеется была невысокой. Еще в древнем Вавилоне значение числа Пи было известно как 25/8. Затем Архимед предложил первый математический метод вычисления числа Пи, с помощью расчета вписанных в круг многоугольников. Это позволяло вычислять значение не «напрямую», с циркулем и линейкой, а математически, что обеспечивало гораздо большую точность. И наконец в 3-м веке нашей эры китайский математик Лю Хуэй придумал первый итерационный алгоритм — алгоритм, в котором число вычисляется не одной формулой, а последовательностью шагов (итераций), где каждая последующая итерация увеличивает точность. С помощью своего метода Лю Хуэй получил Пи с точностью 5 знаков: π = 3.1416. Дальнейшее увеличение точности заняло сотни лет. Математик из Ирана Джамшид ибн Мас‘уд ибн Махмуд Гияс ад-Дин ал-Каши в 15-м веке вычислил число Пи с точностью до 16 знаков, а в 17-м веке голландский математик Лудольф вычислил 32 знака числа Пи. В 19-м веке англичанин Вильям Шенкс, потратив 20 лет, вычислил Пи до 707 знака, однако он так и не узнал, что в 520-м знаке допустил ошибку и все последние годы вычислений оказались напрасны (в итерационных алгоритмах хоть одна ошибка делает все дальнейшие шаги бесполезными).
Что мы знаем о числе Пи сегодня? Действительно, это число весьма интересно:
- Число Пи является иррациональным: оно не может быть выражено с помощью дроби вида m/n. Это было доказано только в 1761 году.
- Число Пи является трансцендентным: оно не является корнем какого-либо уравнения с целочисленными коэффициентами. Это было доказано в 1882 году.
- Число Пи является бесконечным.
- Интересное следствие предыдущего пункта: в числе Пи можно найти практически любое число, например свой собственный номер телефона, вопрос лишь в длине последовательности которую придется просмотреть. Можно подтвердить, что так и есть: скачав архив с 10 миллионами знаков числа Пи, я нашел в нем свой номер телефона, номер телефона квартиры где я родился, и номер телефона своей супруги. Но разумеется, никакой “магии” тут нет, лишь теория вероятности. Можно взять любую другую случайную последовательность чисел такой же длины, в ней также найдутся любые заданные числа.
И наконец, перейдем к формулам вычисления Пи, т.к. именно в них можно увидеть красоту числовых взаимосвязей - то, чем интересна математика.
Формула Лю-Хуэя (3й век):
Формула Мадхавы-Лейбница (15 век):
Формула Валлиса (17 век):
Формула Мэчина (18 век):
Попробуем вычислить число Пи по второй формуле. Для этого напишем простую программу на языке Python:
sum = 0.0
sign = 1
for p in range(0,33):
sum += 4.0*sign/(1+2*p)
print (p,sum)
sign = -sign
Запустим программу в любом онлайн-компиляторе языка Питон (например ). Получаем результат:
Шаг Значение
0 4.0
1 2.666666666666667
2 3.466666666666667
3 2.8952380952380956
4 3.3396825396825403
5 2.9760461760461765
6 3.2837384837384844
7 3.017071817071818
8 3.2523659347188767
9 3.0418396189294032
10 3.232315809405594
11 3.058402765927333
12 3.2184027659273333
13 3.0702546177791854
14 3.208185652261944
15 3.079153394197428
16 3.200365515409549
17 3.0860798011238346
18 3.1941879092319425
19 3.09162380666784
20 3.189184782277596
21 3.0961615264636424
22 3.1850504153525314
23 3.099944032373808
24 3.1815766854350325
25 3.1031453128860127
26 3.1786170109992202
27 3.1058897382719475
28 3.1760651768684385
29 3.108268566698947
30 3.1738423371907505
31 3.110350273698687
32 3.1718887352371485
Как можно видеть, сделав 32 шага алгоритма, мы получили лишь 2 точных знака. Видно что алгоритм работает, но количество вычислений весьма велико. Как известно, в 15м веке индийский астроном и математик Мадхава использовал более точную формулу, получив точность числа Пи в 11 знаков:
Попробуем воспроизвести ее в виде программы, чтобы примерно оценить объем вычислений.
Первым шагом необходимо вычислить √12. Возникает резонный вопрос - как это сделать? Оказывается, уже в Вавилоне был известен метод вычисления квадратного корня, который сейчас так и называется “вавилонским”. Суть его в вычислении √S по простой формуле:
Здесь x0 - любое приближенное значение, например для √12 можно взять 3.
Запишем формулу в виде программы:
from decimal import Decimal
print ("Квадратный корень:")
number = Decimal(12)
result = Decimal(3)
for p in range(1,9):
result = (result + number/result)/Decimal(2)
difference = result**2 - number
print (p, result, difference)
sqrt12 = result
Результаты весьма интересны:
Шаг Значение Погрешность
1 3.5 0.25
2 3.464285714285714 0.00127
3 3.464101620029455 3.3890E-8
4 3.464101615137754 2.392873369E-17
Результат: √12 = 3.464101615137754
Как можно видеть, сделав всего 4 шага, можно получить √12 с достаточной точностью, задача вполне посильная даже для ручных расчетов 15 века.
Наконец, запрограммируем вторую часть алгоритма - собственно вычисление Пи.
sum = Decimal(1)
sign = -1
for p in range(1,32):
sum += Decimal(sign)/Decimal((2*p+1)*(3**p))
sign = -sign
print(p, sqrt12*sum)
print("Result:", sqrt12*sum)
Результаты работы программы:
Шаг Значение
1 3.079201435678004077382126829
2 3.156181471569954179316680000
3 3.137852891595680345522738769
4 3.142604745663084672802649458
5 3.141308785462883492635401088
6 3.141674312698837671656932680
7 3.141568715941784242161823554
8 3.141599773811505839072149767
9 3.141590510938080099642754230
10 3.141593304503081513121460820
11 3.141592454287646300323593597
12 3.141592715020379765581606212
13 3.141592634547313881242713430
14 3.141592659521713638451335328
15 3.141592651733997585128216671
16 3.141592654172575339199092210
17 3.141592653406165187919674184
18 3.141592653647826046431202391
19 3.141592653571403381773710565
20 3.141592653595634958372427485
21 3.141592653587933449530974820
22 3.141592653590386522717511595
23 3.141592653589603627019680710
24 3.141592653589853940610143646
Уже на 24м шаге мы получаем искомые 11 знаков числа Пи. Задача явно требовала больше времени чем сейчас, но вполне могла быть решена в средние века.
Современные формулы не столь просты внешне, зато работают еще быстрее. Для примера можно привести формулу Чудновского:
Для сравнения, те же 24 итерации по этой формуле дают число Пи со следующей точностью:
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249.
Если сделать 100 итераций и вычислить 1000 знаков Пи, то можно увидеть так называемую “точку Фейнмана”:
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420207
Это последовательность “999999”, находящаяся на 762м знаке от начала. Желающие могут поэкспериментировать дальше самостоятельно с помощью программы на языке Python:
from math import factorial
from decimal import *
def chudnovsky(n):
pi = Decimal(0)
k = 0
while k < n:
pi += (Decimal(-1)**k)*(Decimal(factorial(6*k))/((factorial(k)**3)*(factorial(3*k)))* (13591409 + 545140134*k)/(640320**(3*k)))
k += 1
print("Шаг: {} из {}".format(k, n))
pi = pi * Decimal(10005).sqrt()/4270934400
pi = pi**(-1)
return pi
# Требуемая точность (число знаков)
N = 1000
getcontext().prec = N
val = chudnovsky(N/14)
print(val)
Эта программа не оптимизирована, и работает довольно-таки медленно, но для ознакомления с сутью алгоритма этого вполне достаточно. Кстати, с помощью формулы Чудновского два инженера Александр Йи и Сингеру Кондо в 2010 году объявили о новом мировом рекорде вычисления Пи на персональном компьютере: 5 трлн знаков после запятой. Компьютеру с 12 ядрами, 97Гб памяти и 19 жесткими дисками потребовалось 60 дней для выполнения расчетов.
На этом мы закончим с числом Пи, хотя с ним конечно, связано куда больше интересных фактов. Например 3 марта (т.е. 03.14) отмечается международный “день числа Пи”, ну а другие факты читатели могут поискать самостоятельно.
4. Вычисление радиуса Земли
О том, что Земля круглая сегодня знает каждый школьник, и никого не удивить таким видом планеты из космоса.
Однако в историческом плане, увидеть планету свысока мы смогли совсем-совсем недавно. Как же мог греческий ученый Эратосфен измерить радиус Земли, в 240 году до нашей эры? Оказывается мог, используя 2 научных “инструмента” - транспортир и верблюда, ну и разумеется, математику.
Эратосфен жил в Александрии - крупнейшем городе того времени, центром науки и искусств древнего мира. В Александрии по преданию, находился маяк высотой 120 метров - даже сегодня такое сооружение не просто построить, а в то время маяк считался одним из 7 чудес света. Эратосфен же был не только ученым, но и хранителем Александрийской библиотеки, содержащей до 700000 книг.
Читая труды по географии, Эратосфен нашел интересный факт - в городе Сиене в день летнего солнцестояния Солнце стоит так высоко, что предметы в полдень не отбрасывают тени. Другой может и не обратил бы на это внимание, но Эратосфен не зря интересовался и математикой и астрономией. Он знал что в его городе Александрии тень в этот же день имеет другой угол. Эратосфен дождался солнцестояния, измерил угол солнечных лучей и получил величину 7,2 градуса.
Что это значит? Объяснение данному факту могло быть только одно - Земля круглая, и угол падения солнечных лучей в разных точках Земли в одно время различается.
Картинка с сайта physicsforme.com
Дальше, как говорится, дело техники. Зная примерное расстояние между Сиеном и Александрией (которое было известно из времени в пути каравана верблюдов) и угол, легко получить длину всей окружности. К чести Эратосфена, его результат отличается от сегодняшнего всего лишь на 1%. Так, задолго до эпохи авиации и воздухоплавания, человек впервые смог измерить радиус планеты, даже при этом не отрываясь от нее. Увидеть настоящую кривизну Земли сумели лишь пилоты стратостатов в начале 20 века, более чем через 2000 лет после описанного опыта.
Разумеется, повторить подобный эксперимент сегодня легко может любой школьник. Нужно лишь сделать простейший угломер из транспортира и отвеса, и с помощью знакомых в другом городе, сделать измерения высоты Солнца в двух точках в одно и то же время.
5. Простые числа
Каждый знает, что простые числа — такие числа, которые делятся только на единицу и самих себя. Но так ли они просты, как кажутся, и актуальны ли сегодня? Попробуем разобраться.
То, что существуют числа, которые не делятся ни на какое другое число, люди знали еще в древности. Последовательность простых чисел имеет следующий вид:
1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …
Доказательство того, что этих чисел бесконечно много, дал еще Евклид, живший в 300 г до н.э. Примерно в те же годы уже известный нам греческий математик Эратосфен, придумал довольно-таки простой алгоритм получения простых чисел, суть которого была в последовательном вычеркивании чисел из таблицы. Те оставшиеся числа, которые ни на что не делились, и были простыми. Алгоритм называется «решето Эратосфена» и за счет своей простоты (в нем нет операций умножения или деления, только сложение) используется в компьютерной технике до сих пор.
Видимо, уже во время Эратосфена стало ясно, что какого-либо четкого критерия, является ли число простым, не существует — это можно проверить лишь экспериментально. Существуют различные способы для упрощения процесса (например, очевидно, что число не должно быть четным), но простой алгоритм проверки не найден до сих пор, и скорее всего найден не будет: чтобы узнать, простое число или нет, надо попытаться разделить его на все меньшие числа.
Это несложно записать в виде программы на языке Python:
import math
def is_prime(n):
if n % 2 == 0 and n > 2:
return False
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
# Вывод всех простых чисел от 1 до N
N = 100
for p in range(1, N, 2):
if is_prime(p): print(p)
# Вывод результата, является ли заданное число простым
print(is_prime(2147483647))
Желающие могут поэкспериментировать с программой самостоятельно.
Подчиняются ли простые числа каким-либо законам? Да, и они довольно любопытны. Так, например, французский математик Мерсенн еще в 16 веке обнаружил, что много простых чисел имеет вид 2N — 1, эти числа названы числами Мерсенна. Еще незадолго до этого, в 1588 году, итальянский математик Катальди обнаружил простое число 219 — 1 = 524287 (по классификации Мерсенна оно называется M19). Сегодня это число кажется весьма коротким, однако даже сейчас с калькулятором проверка его простоты заняла бы не один день, а для 16 века это было действительно огромной работой. На 200 лет позже математик Эйлер нашел другое простое число 231 — 1 = 2147483647. Необходимый объем вычислений каждый может представить сам. Он же выдвинул гипотезу, названную позже «проблемой Эйлера», или «бинарной проблемой Гольдбаха»: каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел. Например, можно взять 2 любых четных числа: 123456 и 888777888. С помощью компьютера можно найти их сумму в виде двух простых чисел: 123456 = 61813 + 61643 и 888777888 = 444388979 + 444388909. Интересно здесь то, что точное доказательство этой теоремы не найдено до сих пор, хотя с помощью компьютеров она была проверена до чисел с 18 нулями.
Существует и другая теорема, называемая теоремой Ферма-Эйлера, открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4*k+1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4*111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197*19197 + 8710*8710. Теорема была доказана Эйлером лишь через 100 лет.
И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.
Так что с простыми числами не все так просто. Есть и удивительные факты. Например, в 1883 г. русский математик И.М.Первушин из Пермского уезда доказал простоту числа 261 — 1 = 2305843009213693951. Даже сейчас компьютеру с запущенной вышеприведенной программой требуется несколько минут на проверку данного числа, а на то время это была поистине гигантская работа.
Кстати интересно, что существуют люди, обладающие уникальными способностями мозга — так например, известны аутисты, способные находить в уме (!) 8-значные простые числа. Как они это делают, непонятно. Такой пример описывается в книге известного врача-психолога Оливера Сакса “Человек, который принял жену за шляпу”. По некоторым предположениям, такие люди обладают способностью “видеть” числовые ряды визуально, и пользуются методом “решета Эратосфена” для определения, является ли число простым или нет.
Еще одна интересная гипотеза была выдвинута Ферма, который предположил, что все числа вида
являются простыми. Эти числа называются “числами Ферма”. Однако, это оказалось верным только для 5 первых чисел: F0=3, F1=5, F2=17,F3=257, F4=65537. В 1732 году Эйлер опроверг гипотезу, найдя разложение на множители для F5: F5= 641·6700417. Существуют ли другие простые числа Ферма, пока неизвестно до сих пор. Такие числа растут очень быстро (для примера, F7=340282366920938463463374607431768211457), и их проверка является непростой задачей даже для современных компьютеров.
Актуальны ли простые числа сегодня? Еще как! Простые числа являются основой современной криптографии, так что большинство людей пользуются ими каждый день, даже не задумываясь об этом. Любой процесс аутентификации, например, регистрация телефона в сети, банковские платежи и прочее, требуют криптографических алгоритмов. Суть идеи тут крайне проста и лежит в основе алгоритма RSA, предложенного еще в 1975 году. Отправитель и получатель совместно выбирают так называемый «закрытый ключ», который хранится в надежном месте. Этот ключ представляет собой, как, наверное, читатели уже догадались, простое число. Вторая часть — «открытый ключ», тоже простое число, формируется отправителем и передается в виде произведения вместе с сообщением открытым текстом, его можно опубликовать даже в газете. Суть алгоритма в том, что не зная «закрытой части», получить исходный текст невозможно.
К примеру, если взять два простых числа 444388979 и 444388909, то «закрытым ключом» будет 444388979, а открыто будут передано произведение 197481533549433911 (444388979*444388909). Лишь зная вторую половинку, можно вычислить недостающее число и расшифровать им текст.
В чем хитрость? А в том, что произведение двух простых чисел вычислить несложно, а вот обратной операции не существует — если не знать первой части, то такая процедура может быть выполнена лишь перебором. И если взять действительно большие простые числа (например, в 2000 символов длиной), то декодирование их произведения займет несколько лет даже на современном компьютере (к тому времени сообщение станет давно неактуальным). Гениальность данной схемы в том, что в самом алгоритме нет ничего секретного — он открыт и все данные лежат на поверхности (и алгоритм, и таблицы больших простых чисел известны). Сам шифр вместе с открытым ключом можно передавать как угодно, в любом открытом виде. Но не зная секретной части ключа, которую выбрал отправитель, зашифрованный текст мы не получим. Для примера можно сказать, что описание алгоритма RSA было напечатано в журнале в 1977 году, там же был приведен пример шифра. Лишь в 1993 году при помощи распределенных вычислений на компьютерах 600 добровольцев, был получен правильный ответ.
В завершение темы простых чисел, приведем вид так называемой “спирали Улама”. Математик Станислав Улам открыл ее случайно в 1963 году, рисуя во время скучного доклада на бумаге числовую спираль и отмечая на ней простые числа:
Как оказалось, простые числа образуют вполне повторяющиеся узоры из диагональных линий. В более высоком разрешении изображение выглядит так (картинка с сайта ):
В общем, можно предположить что далеко не все тайны простых чисел раскрыты и до сих пор.
Кстати, самым большим известным на момент написания книги простым числом, является число Мерсенна 274207281 - 1, содержащее 22 338 618 знаков. А совсем недавно, в августе 2017 года, участники проекта распределенных вычислений PrimeGrid нашли простое число 9194441048576 + 1, содержащее 6 253 210 знаков.
6. Совершенные числа
Еще одно удивительное свойство мира чисел было доказано еще Евклидом: если число вида 2p-1 является простым (уже известное нам число Мерсенна), то число 2P-1(2p-1) является совершенным, т.е. равно сумме всех его делителей.
Рассмотрим пример для p=13:
213-1 = 8191. Как показывает приведенная ранее программа, 8191 - действительно простое число.
212*(213-1) = 33550336.
Чтобы найти все делители числа и их сумму, напишем небольшую программу:
def is_perfect(n):
sum = 0
for i in range(1, int(n/2)+1):
if n % i == 0:
sum += i
print(i)
print("Сумма",sum)
return sum == n
is_perfect(33550336)
Действительно, 33550336 делится на числа 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8191, 16382, 32764, 65528, 131056, 262112, 524224, 1048448, 2096896, 4193792, 8387584, 16775168. И сумма этих чисел равна искомому 33550336.
Совершенные числа встречаются довольно-таки редко, их последовательность согласно Википедии, образует вид:
6,
28,
496,
8128,
33 550 336,
8 589 869 056,
137 438 691 328,
2 305 843 008 139 952 128,
2 658 455 991 569 831 744 654 692 615 953 842 176,
Кстати, еще Эйлер доказал, что все совершенные числа имеют только вид 2p-1(2p-1). А вот нечетных совершенных чисел пока не обнаружено, но и не доказано что их не существует. Интересно проверить этот факт практически. Совершенное число 137438691328 обнаружил еще немецкий математик Иоганн Мюллер в 16 веке. Сегодня такое число несложно проверить на компьютере.
Во-первых, слегка оптимизируем приведенную выше программу. Как нетрудно видеть, если число N делится нацело на P, то мы “автоматом” сразу находим и второй делитель N/P. Например, если 10 делится нацело на 2, то оно делится и на 10/2=5. Это позволяет заметно сократить число вариантов перебора. Во-вторых, используем тип чисел Decimal, позволяющий использовать большие числа. Обновленная программа выглядит так:
from decimal import *
def is_perfect(n):
s = Decimal(1)
p = Decimal(2)
while p < n.sqrt()+1:
if n % p == 0:
s += p
if p != n/p: s += n/p
p += 1
return s == n
print(is_perfect(Decimal('137438691328')))
Запускаем, программа работает - число '137438691328' действительно является совершенным. Оно делится на 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524287, 1048574, 2097148, 4194296, 8388592, 16777184, 33554368, 67108736, 134217472, 268434944, 536869888, 1073739776, 2147479552, 4294959104, 8589918208, 17179836416, 34359672832 и 68719345664, сумма этих чисел равна 137438691328. Однако, на моем компьютере проверка “совершенности” данного числа заняла … 54 секунды. Это конечно быстро по сравнению с 16м веком, но совершенно недостаточно чтобы проверить все числа, хотя бы до миллиарда. Значит пора использовать более тяжелую артиллерию - перепишем программу на языке Си. Все-таки Python это интерпретатор, и работает заметно медленнее. Получаемый код не намного сложнее:
#include <string.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
bool isPerfect(unsigned long long int n)
{
unsigned long long int sum = 1, i;
for(i=2; i<=sqrt(n)+1; i++)
{
if (n%i==0) {
sum += i;
if (i != n/i) {
sum += n/i;
}
}
}
return sum == n;
}
int main()
{
unsigned long long int n = 137438691328LL;
bool res = isPerfect(n);
printf("%d\n", res);
return 0;
}
Компилируем программу с помощью компилятора gcc, запускаем получившийся exe-файл: время выполнения меньше секунды, уже гораздо лучше. Теперь несложно поменять функцию main для перебора всех чисел от 1 до 200000000000. В код также добавлен вывод промежуточных результатов каждые 1000000 итераций, чтобы видеть ход выполнения программы.
int main()
{
unsigned long long int MAX = 200000000000LL;
unsigned long long int p;
for (p=1; p<MAX; p++) {
if (isPerfect(p))
printf(" %llu ", p);
if (p % 1000000 == 0)
printf("*%llu,%llu*", 100*p/MAX, p);
}
}
Увы, прогноз относительно скорости расчетов оказался слишком оптимистичным. Примерно за час работы программы, было перебрано лишь 100млн вариантов, а для перебора всех 200млрд понадобился бы не один день. Желающие могут продолжить процесс самостоятельно, однако с уверенностью можно сказать что в диапазоне от 1 до 100000000 действительно нет совершенных чисел кроме 6, 28, 496, 8128 и 33550336.
Проверка числа 2 305 843 008 139 952 128 является непростой задачей даже для современного домашнего компьютера - во-первых, в языке C/C++ нет встроенных типов данных для столь большого числа, а во-вторых, число вариантов перебора весьма велико.
Разумеется, выше было приведено самое простое решение “в лоб”, можно оптимизировать и саму программу, например разбить вычисление на несколько процессорных ядер, однако данная задача выходит за рамки этого материала. Немного про параллельные вычисления будет рассказано в конце книги.
7. Магический квадрат
Еще одна старинная математическая головоломка - магический квадрат. Магическим называют квадрат, заполненный неповторяющимися числами так, что суммы чисел по горизонталям, вертикалям и диагоналям одинаковы. Такие квадраты известны давно, самым старым из известных является магический квадрат Ло Шу, изображенный в Китае в 2200г до нашей эры.
Если подсчитать количество точек, то можно перевести квадрат в современный вид, изображенный справа.
Магический квадрат 4х4 был обнаружен в индийских надписях 11 века:
И наконец, известный квадрат 4х4, изображенный на гравюре немецкого художника Дюрера “Меланхолия”. Этот квадрат изображен не просто так, 2 числа 1514 указывают на дату создания гравюры.
Как можно видеть, уже математики прошлого умели строить магические квадраты разной размерности. Интересно рассмотреть их свойства.
Сумма чисел магического квадрата размера NxN зависит только от N, и определяется формулой:
Это несложно доказать, т.к. сумма всех чисел квадрата равна сумме ряда 1..N2. Действительно, для квадрата Дюрера M(4) = 34, что можно посчитать на картине. Для квадратов разной размерности суммы равны соответственно: M(3) = 15, M(4) = 34, M(5) = 65, M(6) = 111, M(7) = 175, M(8) = 260, M(9) = 369, M(10) = 505.
Напишем программу для построения магических квадратов размерности N. Первый подход будет “в лоб”, напрямую. Создадим массив, содержащий все числа от 1 до N2 и получим все возможные перестановки этого массива. Их число довольно-таки велико, и составляет 1*2*..*N = N! вариантов. Также для каждого массива необходимо проверить, является ли он “магическим”, т.е. выполняется ли требование равенства сумм.
Для получения всех перестановок воспользуемся алгоритмом, описанным здесь - -cpp.ru/permutation/.
Код программы приведен ниже:
def swap(arr, i, j):
arr[i],arr[j] = arr[j],arr[i]
def next_set(arr, n):
j = n - 2
while j != -1 and arr[j] >= arr[j + 1]: j -= 1
if j == -1:
return False
k = n - 1
while arr[j] >= arr[k]: k -= 1
swap(arr, j, k)
l = j + 1
r = n - 1
while l < r:
swap(arr, l, r)
l += 1
r -= 1
return True
def is_magic(arr, n):
for i in range(0, n):
sum1 = 0
sum2 = 0
sum3 = 0
sum4 = 0
for j in range(0, n):
sum1 += arr[i*n + j]
sum2 += arr[j*n + i]
sum3 += arr[j*n + j]
sum4 += arr[(n-j-1)*n + j]
if sum1 != sum2 or sum1 != sum3 or sum1 != sum4 or sum2 != sum3 or sum2 != sum4 or sum3 != sum4:
return False
return True
def show_squares(n):
N = n*n
arr = [i+1 for i in range(N)]
cnt = 0
while next_set(arr, N):
if is_magic(arr, n):
print(arr)
cnt += 1
return cnt
# Требуемая размерность
cnt = show_squares(3)
print("Число вариантов:", cnt)
Программа выдала 8 вариантов для N=3, время вычисления составило 2 секунды:
[2, 7, 6, 9, 5, 1, 4, 3, 8] [6, 1, 8, 7, 5, 3, 2, 9, 4]
[2, 9, 4, 7, 5, 3, 6, 1, 8] [6, 7, 2, 1, 5, 9, 8, 3, 4]
[4, 3, 8, 9, 5, 1, 2, 7, 6] [8, 1, 6, 3, 5, 7, 4, 9, 2]
[4, 9, 2, 3, 5, 7, 8, 1, 6] [8, 3, 4, 1, 5, 9, 6, 7, 2]
Действительно, как известно, существует только 1 магический квадрат 3х3:
Остальные являются лишь его поворотами или отражениями (очевидно что при повороте квадрата его свойства не изменятся).
Теперь попробуем вывести квадраты 4х4. Запускаем программу… и ничего не видим. Как было сказано выше, число вариантов перебора для 16 цифр равняется 16! или 20922789888000 вариантов. На моем компьютере полный перебор такого количества занял бы 1089 дней!
Однако посмотрим на магический квадрат еще раз:
Суммы всех элементов по горизонтали и вертикали равны. Из этого мы легко можем записать равенство его членов:
x11 + x12 + x13 + x14 = x21 + x22 + x23 + x24
x11 + x12 + x13 + x14 = x14 + x24 + x34 + x44
x11 + x12 + x13 + x14 = x13 + x23 + x33 + x43
x11 + x12 + x13 + x14 = x12 + x22 + x32 + x42
x11 + x12 + x13 + x14 = x11 + x21 + x33 + x44
x11 + x12 + x13 + x14 = x31 + x32 + x33 + x34
И наконец, общая сумма: т.к. квадрат заполнен числами 1..16, то если сложить все 4 строки квадрата, то получаем 4S = 1+..+16 = 136, т.е. S=34 (что соответствует приведенной в начале главы формуле).
Это значит, что мы легко можем выразить последние элементы через предыдущие:
x14 = S - x11 - x12 - x13
x24 = S - x21 - x22 - x23
x34 = S - x31 - x32 - x33
x41 = S - x11 - x21 - x31
x42 = S - x12 - x22 - x32
x43 = S - x13 - x23 - x33
x44 = S + x14 - x14 - x24 - x34
Что это дает? Очень многое. Вместо перебора 16 вариантов суммарным количеством 16!=20922789888000 мы должны перебрать лишь 9 вариантов, что дает 9!=362880 вариантов, т.е. в 57657600 раз меньше! Как нетрудно догадаться, мы фактически выразили крайние строки квадрата через соседние, т.е. уменьшили размерность поиска с 4х4 до 3х3. Это же правило будет действовать и для квадратов большей диагонали.
Обновленная программа выглядит более громоздко (в ней также добавлены проверки на ненулевые значения и проверки на уникальность элементов), зато расчет происходит в разы быстрее. Здесь также используется возможность работы со множествами в языке Python, что легко позволяет делать перебор нужных цифр в цикле:
set(range(1,16+1)) - множество чисел [1..16]
set(range(1,16+1)) - set([x11]) - множество чисел [1..16] за исключением x11.
Также добавлена простая проверка на минимальность суммы: очевидно, что сумма всех элементов не может быть меньше чем 16+1+2+3 = 22.
digits = set(range(1,16+1))
cnt = 0
for x11 in digits:
for x12 in digits - set([x11]):
for x13 in digits - set([x11, x12]):
for x14 in digits - set([x11, x12, x13]):
s = x11 + x12 + x13 + x14
if s < 22: continue
for x21 in digits - set([x11, x12, x13, x14]):
for x22 in digits - set([x11, x12, x13, x14, x21]):
for x23 in digits - set([x11, x12, x13, x14, x21, x22]):
x24 = s - x21 - x22 - x23
if x24 <= 0 or x24 in [x11, x12, x13, x14, x21, x22, x23]: continue
for x31 in digits - set([x11, x12, x13, x14, x21, x22, x23, x24]):
for x32 in digits - set([x11, x12, x13, x14, x21, x22, x23, x24, x31]):
for x33 in digits - set([x11, x12, x13, x14, x21, x22, x23, x24, x31, x32]):
x34 = s - x31 - x32 - x33
x41 = s - x11 - x21 - x31
x42 = s - x12 - x22 - x32
x43 = s - x13 - x23 - x33
x44 = s - x14 - x24 - x34
if x34 <= 0 or x41 <= 0 or x42 <= 0 or x43 <= 0 or x44 <= 0: continue
data = [x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44]
if len(data) != len(set(data)): continue
if is_magic(data, 4):
print data
cnt += 1
print cnt
В результате, программа проработала всего лишь около часа (вместо 3х лет!), всего было выведено 7040 квадратов размерностью 4х4. Разумеется, большинство из них являются поворотами или отражениями друг друга. Было доказано что уникальных квадратов всего 880.
Вспомним магический квадрат Дюрера, в его строке есть цифры 1514, соответствующие году создания гравюры. С помощью программы можно решить еще одну задачу: посмотреть сколько всего возможно квадратов с такими цифрами. Здесь число вариантов перебора меньше, т.к. еще 2 цифры фиксированы. Оказывается, помимо “авторского”, возможны всего 32 варианта, например:
1 15 14 4 2 15 14 3
5 11 8 10 5 10 7 12
12 6 9 7 11 8 9 6
16 2 3 13 16 1 4 13
Интересно, что верхний ряд помимо цифр 15 и 14 может содержать либо 1,4 либо 2,3, других вариантов нет. Разные варианты содержат лишь перестановки этих цифр.
Если же говорить о квадратах большей размерности, то число вариантов перебора для них получается слишком большим. Так для квадрата 5х5, даже если выразить крайние члены через соседние, получаем 4х4 остающихся клеток, что даст нам те же самые 16! вариантов перебора. В архиве с книгой приложен файл “07 - magic5.c” для расчета квадратов 5х5, но автору так и не хватило терпения дождаться всех результатов.
В качестве примера алгоритма построения квадратов любой нечетной размерности без полного перебора, можно назвать так называемый сиамский метод, известный уже с 17 века. Его описание можно найти в Википедии, пример программы на языке Python можно найти в приложении к книге.
Для N=9, программа сгенерировала следующий квадрат:
47 58 69 80 1 12 23 34 45
57 68 79 9 11 22 33 44 46
67 78 8 10 21 32 43 54 56
77 7 18 20 31 42 53 55 66
6 17 19 30 41 52 63 65 76
16 27 29 40 51 62 64 75 5
26 28 39 50 61 72 74 4 15
36 38 49 60 71 73 3 14 25
37 48 59 70 81 2 13 24 35
Существует множество других алгоритмов построения, например метод Франклина, Россера, Рауз-Болла, желающие могут поискать их самостоятельно.
И наконец, можно вспомнить так называемые “пандиагональные” магические квадраты. Это квадраты, в которых учитываются суммы также “косых” диагоналей, которые получаются если вырезать квадрат из бумаги и склеить его в тор. Желающие могут добавить в программу вывод таких квадратов самостоятельно.
8. Магический квадрат из простых чисел
Существует еще одна разновидность магического квадрата - составленного из простых чисел. Пример такого квадрата показан на рисунке:
29
131
107
167
89
11
71
47
149
Приведенную выше программу легко модифицировать для такого расчета: достаточно лишь заменить множество digits = set(range(1,16+1)) на другое, содержащее простые числа.
Для примера будем искать квадраты среди трехзначных простых чисел от 101 до 491.
Заменим в предыдущей версии программы строку digits = set([1,2,3,4,5,6,7,8,9]) на
primes = [ 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491 ]
digits = set(primes)
Таких квадратов нашлось 40, например:
233
167
389
419
263
107
137
359
293
Сумма чисел равна вполне красивому числу 789.
Т.к. число вариантов перебора больше, программа работает дольше. Время поиска составило 724с для Python-версии и 316c для программы на C++.
Если же рассматривать минимально возможный квадрат из простых чисел, то его сумма равняется тоже вполне “красивому” числу 111:
7
61
43
73
37
1
31
13
67
Примером квадрата 4х4 может быть квадрат с также “красивой” суммой 222:
97
41
73
11
17
47
83
75
59
79
13
71
49
55
53
65
9. Числа Фибоначчи
Возьмем 2 числа: 0 и 1. Следующее число рассчитаем как сумму предыдущих чисел, затем повторим процесс.
Мы получили последовательность, известную как числа Фибоначчи:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...
Эта последовательность была названа в честь итальянского математика 12 века Леонардо Фибоначчи. Фибоначчи рассматривал задачу роста популяции кроликов. Если предположить, что новорожденная пара кроликов 1 месяц растет, через месяц начинает спариваться, и затем через каждый месяц дает потомство, то количество пар кроликов несложно подсчитать:
Как можно видеть, число пар образует как раз те самые числа Фибоначчи. Сама последовательность Фибоначчи кажется простой. Но чем она интересна? Пример с кроликами не случаен - эти числа действительно описывают множество природных закономерностей:
- Множество растений имеют количество лепестков, равное одному из чисел Фибоначчи. Количество листьев на стебле также может описываться этим законом, например у тысячелистника.
- Другое известное изображение - спираль Фибоначчи, которая строится по похожему принципу соотношения размеров прямоугольников:
Это изображение также часто встречается в природе, от раковин моллюсков, до формы атмосферного циклона или даже спиральной галактики.
Для примера достаточно взять фотографию циклона из космоса, и наложить обе картинки вместе:
- Если взять и разделить друг на друга 2 любых соседних члена последовательности, например 233/377, получится число 0,618. Случайно это или нет, но это число - то самое “золотое сечение”, считающееся наиболее эстетичной пропорцией.
Числа Фибоначчи несложно вывести в программе на языке Python:
from decimal import *
def printNumbers(n):
i1 = Decimal(0)
i2 = Decimal(1)
for p in range(1, n+1):
print("F({}) = {}".format(p, i2))
fib = i1 + i2
i1 = i2
i2 = fib
getcontext().prec = 100
N = 100
printNumbers(N)
Интересно заметить, что растет последовательность Фибоначчи весьма быстро, уже F(300) = 222232244629420445529739893461909967206666939096499764990979600.
10. Высота звуков нот
Еще в древности человек заметил, что натянутая струна порождает колебания звука. Во времена Пифагора было замечено, что струны издают мелодичный звук, если их длина соотносится как небольшие целые числа (1:2, 2:3, 3:4 и т. д.). Звук от струны длиной 2/3 дает чистую квинту, 3/4 струны дает кварту а половина струны - октаву.
Рассмотрим струну с условной длиной = 1. Будем умножать длину струны на 3/2, если полученное число больше 2, разделим еще на 2.
1
3/2 = 1,5
1.5 * 3/2 = 2.25, 2.25/2 = 1,125 = 9/8
9/8 * 3/2 = 1,6875 = 27/16
Похожий ряд, если его упорядочить по возрастанию, называется пифагоровым строем:
“до” - 1
“ре” - 9/8
“ми” - 81/64
“фа” - 4/3
“соль” - 3/2
“ля” - 27/16
“си” - 243/128
“до” - 2
Он также называется квинтовым, т.к. ноты получались увеличением на квинту, т.е. на 3/2. Считается, что этот строй использовался еще при настройке лир в древней Греции, и сохранился вплоть до средних веков. Названия нот разумеется, были другие - современные названия придумал только через 1000 лет итальянский теоретик музыки Гвидо д’Ареццо в 1025 г..
Разумеется, в древней Греции никто не знал про частоту колебаний звука, зато древние греки были хорошими геометрами, и проблем с умножением и делением у них не было. Современная теория колебаний струны появилась гораздо позже, работы Эйлера и Д’Аламбера были написаны в 1750х годах.
Как математически определяются частоты звуков нот? Сейчас мы знаем, что октава (от “до” до “до” следующей октавы) - это умножение частоты на 2 (или укорочение струны в 2 раза). Для остальных нот с 18 века используется так называемый “хорошо темперированный строй”: октава делится на 12 равных промежутков, а последовательность частот образует геометрическую прогрессию.
Для одной октавы получаются следующие коэффициенты: 1,0594, 1,1224, 1,1892, …, 2. На клавиатуре они отображаются всем известным образом, образуя 12 полутонов:
Таким образом, если знать частоту любой ноты, все остальные легко рассчитываются по вышеприведенной формуле.
Очевидно, что “базовая” частота может быть любой. Традиционно принято например, что частота камертона ноты “Ля” 440Гц. Остальные ноты первой октавы:
ДО
261.6
ДО#
277
РЕ
293.7
РЕ#
311
МИ
329.6
ФА
349.2
ФА#
370
СОЛЬ
392
СОЛЬ#
415
ЛЯ
440
ЛЯ#
466
СИ
494
Интересно заметить, что квинта в этой системе имеет соотношение частот 27/12 = 1.49, что чуть-чуть отличается от “пифагорейского” чистого тона с соотношением 1.5. На слух “современная квинта” имеет небольшие биения 0,5Гц, соответствующие разности частот 392 - 392.4. До сих пор есть любители исполнения старинной музыки в квинто-терцевом строе, называемым “чистым”. В 18м же веке дебаты между приверженцами “старого” и “нового” строя были довольно-таки острыми. Впрочем, преимущества равномерно темперированного строя в виде четкого соотношения между частотами нот и возможности транспонирования музыки в любую другую тональность “без потери качества” оказались решающими. Сейчас “чистый строй” имеет лишь историческое значение, и используется лишь иногда для исполнения старинных произведений.
И традиционно, программа на языке Python, выводящая частоты полутонов в обе стороны от ноты “Ля”:
import math
freqLa = 440
for p in range(-32,32):
freq = freqLa*math.pow(2, p/12.0)
print p,freq
11. Вращение планет
Еще в древней Греции ученые знали, что планеты движутся по небу, но каким образом? Сотни лет господствовала геоцентрическая система мира - в центре была Земля, вокруг которой по окружностям двигались Луна, планеты (на то время их было известно 5) и Солнце:
Такая система казалась вполне логичной и интуитивно понятной (даже сейчас люди говорят что солнце “всходит” и “заходит”), однако не объясняла астрономам почему планеты движутся по небу неравномерно, и временами даже в обратную сторону.
Вот так, к примеру, выглядит перемещение по небу планеты Марс, что никак не укладывается в теорию движения по кругу:
Впрочем геоцентрическая система просуществовала более 1500 лет, только в 16м веке Коперник издал свой труд «О вращениях небесных сфер», где описывал вращение планет по круговым орбитам вокруг Солнца. Однако проблемой было то, что и при этой схеме фактические движения планет не совпадали с расчетными.
Объяснить это не мог никто, пока в 1600 году немецкий математик Иоганн Кеплер не стал изучать многолетние результаты наблюдений, сделанные астрономом Тихо Браге. Кеплер был великолепным математиком, но и у него ушло несколько лет чтобы понять суть и вывести законы, которые и сейчас называются законами Кеплера.
Как оказалось, движение планет подчиняется 3м математическим законам:
1) Планеты движутся по эллиптическим орбитам, в одном из фокусов эллипса находится Солнце
2) Планеты движутся неравномерно: скорость планеты увеличивается при движении к Солнцу и уменьшается в обратном направлении. Но за равные промежутки времени вектор движения описывает равные площади: площади участков “А” одинаковы:
3) Квадраты периодов обращений планеты пропорциональны кубу расстояний до орбиты:
Кеплер считал, что весь мир подчиняется гармонии, и что солнечная система больше похожа на часовой механизм, чем на божественное творение. Найденные им законы не только красивы и гармоничны, но и совпали с реальными наблюдениями (уже позже выяснилось, что законы Кеплера могут быть выведены из законов Ньютона и закона всемирного тяготения, желающие могут найти доказательства в Википедии).
Что касается Марса, то его орбита более вытянутая, чем орбита Земли, чем и объясняется разница как в скорости движения, так и в яркости планеты. Картинка с сайта журнала “Наука и жизнь”:
Кстати, эта картинка хорошо объясняет, почему только некоторые годы благоприятны для запуска космических кораблей к Марсу - те годы, в которые расстояние между планетами минимально.
12. Парадоксы теории вероятности
На интуитивном уровне понимание теории вероятности довольно-таки просто. Возьмем кубик с 6 гранями, подбросим и посмотрим какая грань выпала. Интуитивно ясно, что вероятность выпадения 1 грани из 6 будет 1/6. Действительно, вероятностью называют отношение числа равновероятных событий к числу всех возможных вариантов:
Какова вероятность что выпадут 2 цифры подряд? Она равна произведению вероятностей: (1/6)*(1/6) = 1/36.
Вроде все просто, однако несмотря на простоту, есть довольно-таки много задач, где математика не всегда совпадает с бытовым “здравым смыслом”. Рассмотрим несколько таких парадоксов.
Дети мистера Смита
Эту задачу описывал Мартин Гарднер. Известно что у мистера Смита двое детей, и один из них мальчик. Какова вероятность, что второй из них тоже мальчик? Интуитивно кажется, что вероятность пола ребенка всегда равна 1/2, но не все так просто.
Рассмотрим возможные варианты семей с двумя детьми:
- мальчик-мальчик
- мальчик-девочка
- девочка-мальчик
- девочка-девочка
Исходя из списка вариантов, ответ понятен. Вариант “девочка-девочка” по условию не подходит. Всего остается 3 варианта семей где есть мальчик (М+М, М+Д, Д+М), значит вероятность что второй ребенок окажется мальчиком, равна 1/3.
Бросание кубика
Вернемся к бросанию кубика. Допустим, мы бросили кубик 5 раз, и все разы выпала цифра “3”. Какова вероятность, что мы бросим кубик еще раз, и выпадет снова цифра “3”?
Ответ прост. Интуитивно кажется, что вероятность такого события очень мала. Но в реальности кубик не имеет какой-либо встроенной “памяти” на предыдущие события. Какие бы числа не выпадали до текущего момента, вероятность нового числа также равна 1/6 (а вот если говорить о вероятности выпадения такой серии “в целом”, то она действительно равна 1/(6*6*6*6*6*6) = 1/46656.
Кстати, такая вероятность это много или мало? Интуитивно кажется что мало, и в принципе оно так и есть. Одному человеку пришлось бы бросать кубик каждые 10 секунд 4 дня, чтобы дождаться выпадения 6 цифр подряд. Однако если рассматривать большие числа, то такие вероятности становятся неожиданно большими. Например, если 6 раз кубик бросят все 5 миллионов жителей Петербурга, то 6 цифр подряд выпадут примерно у 100 человек - довольно-таки значительное количество. Это на самом деле важный момент: даже довольно-таки маловероятные события гарантированно произойдут, если речь идет о большом числе попыток. Это важно при прогнозировании таких событий как ДТП, аварии, катастрофы, и прочие негативные явления, которые в большом городе увы, не редкость. По этой же причине редкие заболевания эффективнее лечить в большом городе - редкая болезнь, встречающаяся 1 раз на 100000 человек, может практически не встречаться в небольшом городе и у врачей не будет опыта борьбы с ней, а в мегаполисе таких больных наберется в несколько раз больше.
Парадокс Монти Холла
Этот известный парадокс хорошо описан в Википедии.
Представьте, что вы стали участником игры, в которой вам нужно выбрать одну из трёх дверей. За одной из дверей находится автомобиль, за двумя другими дверями — козы. Вы выбираете одну из дверей, например, номер 1, после этого ведущий, который знает, где находится автомобиль, открывает одну из оставшихся дверей, за которой находится коза. После этого он спрашивает вас, не желаете ли вы изменить свой выбор. Увеличатся ли ваши шансы выиграть автомобиль, если вы примете предложение ведущего и измените свой выбор?
Интуитивно кажется, что если автомобиль спрятан за одной из дверей, то вероятность его найти равна 1/3, и смена двери ничего не даст. Однако это неверно.
Принцип прост: если игрок изначально правильно указал дверь с автомобилем (а вероятность этого действительно ⅓), то замена двери приведет его к проигрышу. Однако в обеих других случаях изначального выбора неверной двери (а вероятность этого ⅔) смена двери приведет к выигрышу. Таким образом, смена двери приведет к выигрышу с вероятностью ⅔ вместо ⅓.
Парадокс дней рождений
Допустим, в организации работает 24 человека. Какова вероятность что хотя бы двое отмечают день рождения в один и тот же день? Интуитивно кажется, что эта вероятность весьма мала и будет равна 24/365, но и в этом случае интуиция ошибается. В реальности, мы должны рассматривать количество пар, которые могут образовать данные люди. Это число довольно-таки велико, например, если обозначить 5 человек как ABCDE, то количество возможных пар будет 10 (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE), а для группы из 24 человек возможно 276 пар.
Для точного расчета воспользуемся принципом произведения вероятностей. Вероятность того, что для 2х людей день рождения не совпадает, равна 364/365. Для 3х человек вероятность что все дни не совпадут, равна произведению 364/365 * 363/365, и так далее. Для n-человек формула приведена в Википедии:
(n! - обозначение факториала, n! = 1*2*..*(n-1)*n)
Нужная нам вероятность обратного события равна обратной величине:
Вывести все значения несложно с помощью программы на Python:
import math
def C(n):
return 1000 - 1000*math.factorial(365)/(math.factorial(365-n)*365**n)
for n in range(3,50):
print("{} - {}%").format(n, 0.1*C(n))
365! это очень большое число, поэтому здесь использованы целочисленные вычисления языка Python, уже затем значение было переведено в проценты.
В результате получаем следующую таблицу:
3 0.0082 4 0.0163 5 0.0271
6 0.0404 7 0.0562 8 0.0743
9 0.0946 10 0.1169 11 0.1411
12 0.1670 13 0.1944 14 0.2231
15 0.2529 16 0.2836 17 0.3150
18 0.3469 19 0.3791 20 0.4114
21 0.4436 22 0.4756 23 0.5072
24 0.5383 25 0.5686 26 0.5982
27 0.6268 28 0.6544 29 0.6809
30 0.7063 31 0.7304 32 0.7533
33 0.7749 34 0.7953 35 0.8143
36 0.8321 37 0.8487 38 0.8640
39 0.8782 40 0.8912 41 0.9031
42 0.9140 43 0.9239 44 0.9328
45 0.9409 46 0.9482 47 0.9547
48 0.9605 49 0.9657 50 0.9703
Как видно из таблицы, уже при количестве сотрудников 50 человек, хотя бы 1 день рождения почти гарантированно совпадет (вероятность 97%), а для 24 человек получаем вероятность равную 0.538, т.е. более 50%.
13. Поверхность Луны
Посмотрим на фотографию поверхности Луны. Эта фотография была сделана автором через телескоп с балкона:
Что мы видим? Очевидно, лунную поверхность, покрытую кратерами, оставшимися от предыдущих столкновений метеоритов с Луной.
Казалось бы, причем здесь математика? При том, что столкновение с метеоритом - случайное событие, его частота подчиняется теории вероятности. На Луне нет атмосферы, нет эрозии и ветра, поэтому лунная поверхность - идеальная “книга”, в которой записаны события последних десятков тысяч лет. Изучая поверхность Луны, можно подсчитать какого размера объекты падали на ее поверхность.
Исследование поверхности Луны камерами высокого разрешения ведется и сейчас. Было подсчитано, что за последние 7 лет на Луне образовались не менее 220 новых кратеров. Это важно еще и потому, что данные подсчеты помогут оценить опасность для Земли.
Есть ли кратеры на Земле? Разумеется есть. Данная фотография сделана вовсе не на Луне или на Марсе, а в США:
Так называемый Аризонский кратер возник около 50тыс лет назад после падения метеорита диаметром 50 метром и весом 300 тысяч тонн. Диаметр кратера составляет более километра. В Сибири находится кратер Попигай размером 100км, он был открыт в 1946 году.
Разумеется, такие большие кратеры довольно-таки редки. Последнее же падение крупного метеорита было по историческим меркам весьма недавно, всего лишь около 100 лет назад. В 1908г в тунгусской тайге упал метеорит, мощность взрыва оценивалась от 10 до 50 мегатонн. По отзывам, взрывная волна обогнула земной шар, а световые явления в атмосфере были столь сильны, что в Лондоне ночью можно было читать газету. Лишь по случайности падение метеорита пришлось на малонаселенные районы Сибири - если бы удар был чуть раньше или позже, такой мощности хватило бы, чтобы полностью уничтожить город размером с Санкт-Петербург. Совсем же недавно, в 2013 году, метеорит размером около 20 метров разрушился в атмосфере, а его многочисленные обломки упали в районе Челябинска. Пострадало примерно 1500 человек, в основном от выбитых ударной волной стекол. По оценкам NASA суммарная мощность составила до 400 килотонн.
Увы, то, что для определенного района Земли может быть катастрофой, для космоса совершенно заурядный момент. Это лишь вопрос времени, достаточно посмотреть на поверхность Луны. По одной из гипотез, 66 миллионов лет назад наша планета столкнулась с большим астероидом, в результате чего было уничтожено 75% видов живых существ, в том числе и динозавры. Поэтому задача наблюдения и прогнозирования астероидной опасности должна быть в обязательном списке дел для человечества, если мы не хотим повторить их судьбу.
14. Так ли случайны случайные числа?
В каждом языке программирования существует функция генерации случайных чисел. Они используются в различных областях, от игр до криптографии или генерации паролей.
На языке Python вывести случайное число можно так:
import random
print(random.randint(0,9))
Но как это работает? Задача вывода действительно случайного числа далеко не так проста как кажется. Чтобы вывести что-то на компьютере, это что-то надо сначала запрограммировать. Но очевидно, что задать формулой случайный, хаотический процесс, невозможно - по определению формула и хаос противоречат друг другу. Именно поэтому числа на самом деле являются псевдослучайными - они лишь похожи на случайные, а в реальности являются результатом вполне конкретного алгоритма.
Одним из наиболее популярных и простых алгоритмов, является линейный конгруэнтный метод (linear congruential generator). Его формула проста:
Рассмотрим пример реализации на языке Python:
x = 123456789
m = 2**31 - 1
for p in range(10):
x = (1103515245*x + 12345) % m
print(x)
Программа действительно выводит числа, которые вполне похожи на случайные: 295234770, 465300796, 1475666158, 588454008, 929838277, 50298429, 1089988954, 698778454, 2010473888, 36125306. Как нетрудно догадаться, при повторном запуске программы числа будут одни и те же. Чтобы числа не повторялись, такой генератор обычно инициализируют значением текущего системного времени.
Увы, такой генератор имеет определенные недостатки: во-первых, его последовательность рано или поздно начинает повторяться, во-вторых, он не является криптостойким - зная текущее значение, можно вычислить следующее, что к примеру, может позволить злоумышленнику узнать “случайно” сгенерированный пароль по его первым буквам.
Существуют другие алгоритмы генерации псевдослучайных чисел, например на основе простых чисел Мерсенна (Mersenne Twister generator). Существуют также аппаратные генераторы случайных чисел, например такая функция присутствует в процессорах Intel. Есть даже сайт , с помощью которого можно сгенерировать случайную последовательность чисел. По заверениям авторов, они используют 3 радиоприемника, настроенных на частоту шума атмосферных помех.
Разумеется, в большинстве обычных программ, например при написании компьютерной игры, “качеством” случайных чисел можно пренебречь, встроенные алгоритмы вполне неплохи. Но при разработке специализированного ПО, где вопрос криптостойкости имеет значение, стоит уже обратить внимание на то, насколько надежен применяемый алгоритм.
15. Распределение случайных величин
С теорией вероятности связан еще один интересный момент - законы распределения случайных величин. Огромное количество процессов в реальности подчиняются всего лишь нескольким законам распределения.
Равномерное распределение
Возьмем игральный кубик и бросим его много раз. Очевидно, что вероятность выпадения каждого числа одинакова. На графике это можно изобразить примерно так:
Другим примером может быть время ожидания автобуса. Если человек пришел на остановку в случайное время, то период ожидания может быть любым, от нуля до максимума интервала движения.
Нормальное распределение
Возьмем группу людей, например в 100 человек, и измерим их рост. Очевидно, что будет некоторое количество людей небольшого роста, некоторое количество высоких людей, совсем мало очень высоких, и совсем мало очень низких. Такое распределение естественно для многих объектов, не только людей, потому оно и называется нормальным.
Формула нормального распределения совпадает с формулой Гаусса:
Подбирая коэффициенты, можно получить разные виды распределения.
Касаемо роста людей, согласно сайту , график роста для мужчин и женщин имеет следующий вид:
Распределение Пуассона
Следующий вид распределения не менее интересен. Рассмотрим события, происходящие с некоторой известной интенсивностью независимо друг от друга, например приход покупателей в магазин. Допустим, в магазин приходит в среднем 10 покупателей в минуту. Какова вероятность, что в какой-то момент времени в магазин придет 20 покупателей?
Вероятность таких событий описывается распределением Пуассона:
График распределения имеет примерно такой вид (в нашем примере λ=10):
Этим же распределением описываются различные случаи, от вероятности неисправностей (если 0.01% телевизоров имеют неисправность, какова вероятность что в партии из 20 штук окажется 2 неисправных телевизора), до скорости роста колоний в чашке Петри.
Вернемся к нашему примеру с 20 покупателями. В интернете можно найти таблицы значений Пуассона для λ=10. По ним можно найти, что вероятность прихода сразу 20 человек составляет 0,19%.
16. Измерение скорости света
С бытовой точки зрения, скорость света практически мгновенна. Действительно, свет за секунду может обогнуть Землю 8 раз, а за 2 секунды пролетает расстояние от Земли до Луны. Поэтому до 17 века про реальную скорость света никто не знал. Как же ее вычислили?
Сегодня опыт по измерению скорости света можно провести даже в школе - достаточно длинного куска кабеля, генератора импульсов и осциллографа. Действительно, задержка сигнала в куске кабеля длиной 50м, будет равна 50/300000000, или 0.016мкс - величина которую покажет даже дешевый осциллограф с максимальной частотой 10-20МГц. Но как же это сделали в 17 веке, когда не было не то что осциллографов, даже до появления лампы накаливания было еще 200 лет ожидания? Помогли астрономия, геометрия, и разумеется, математика.
Говоря точнее, помогло наблюдение Юпитера и его спутников. Спутники Юпитера были открыты еще Галилеем, увидеть их может каждый, даже с балкона в небольшой телескоп. С увеличением около 300х они видны примерно так:
Период вращения спутников Юпитера невелик, и составляет примерно 2 дня. Уже в 17м веке измерение времени было достаточно точным (маятниковые часы изобрел голландский физик и математик Гюйгенс в 1657г), чтобы датский астроном Олаф Ремер в 1676 году обнаружил расхождение расчетного и реального положения спутника примерно в 16 минут (величина, которую трудно не заметить даже при технологиях 17 века). Для измерения орбит спутников Юпитера Ремер использовал момент, когда спутник входит в тень Юпитера - момент, который можно измерить довольно-таки точно.
Как догадался Ремер, запаздывание во времени было связано с движением Земли по орбите.
Картинка с сайта -light.info:
В момент второго измерения расстояние до Юпитера больше примерно на диаметр орбиты Земли (период обращения Юпитера вокруг Солнца - 12 лет, что гораздо больше земного). Это и приводило к тому, что свет от Юпитера приходил с большим запаздыванием, чем при первом измерении. Сделав подсчеты, Ремер получил значение скорости света в 220000км/c. В то время конечность скорости света казалась настолько невероятной, что после публикации во французской академии наук далеко не все поверили молодому ученому. Разумеется, последующие измерения подтвердили правильность метода.
Более точное значение было получено лишь через 200 лет, французский физик Луи Физо с помощью зубчатого колеса и двух зеркал получил значение в 312000км/c. Расстояние между зеркалами было 8,6км, одно зеркало было расположено в доме отца Физо недалеко от Парижа, второе зеркало было расположено на Монмартре. Физо нашел такую скорость вращения колеса, при котором луч света проходящий через зубец колеса затемнялся, что означало что запаздывание света соответствует скорости вращения колеса.
17. Можно ли своими глазами увидеть прошлое?
С предыдущим вопросом связан простой забавный факт. Можно ли лично своими глазами увидеть событие, происходящее например, миллион лет назад? Да, и это очень просто сделать - достаточно посмотреть на небо.
Как наверное читатели уже догадались, все дело в скорости света. Расстояние от Земли до Солнца составляет 150млн километров, свет преодолевает его за 8 минут. Таким образом, когда мы смотрим на небо, мы видим Солнце таким, каким оно было 8 минут назад. Смотря на Юпитер, мы видим его с запаздыванием примерно в полчаса. Расстояние до других звезд гораздо больше. Сириус мы видим таким, каким он был 8 лет назад, звезда Вега имеет расстояние в 25 световых лет, столько нужно свету чтобы долететь до Земли. Туманность Андромеды мы видим с запаздыванием в 2.5 миллиона лет - время сопоставимое с периодом жизни мамонтов и первобытных людей. Если бы там висело гигантское зеркало, в котором отражалась бы Земля, гипотетически можно было бы их увидеть, хотя такого размера телескоп конечно же физически невозможен.
А если серьезно, то данный факт запаздывания света очень помогает астрономам изучать историю Вселенной - наблюдая удаленные галактики, находящиеся на расстоянии миллиардов световых лет, мы видим их в прошлом - их свет шел до нас эти самые миллиарды лет. И таким образом, чем мощнее телескоп, тем дальше во времени он позволяет заглянуть, тем самым, позволяя видеть то время, когда и галактики и звезды еще были молодыми.
С другой стороны, в запаздывании света есть и большой минус. Даже если будут созданы космические корабли, способные долететь до другой звезды, обмениваться сообщениями с космонавтами придется с тем же запаздыванием. К примеру, радиосообщение до Сириуса дойдет до получателя через 8,6 лет, и столько же придется ждать ответа. Уже сейчас можно поговорить по телефону с астронавтами на МКС (в 2015 году британский астронавт Тим Пик ошибся номером, и удивил неизвестную женщину вопросом “Здравствуйте, это Земля?”), а вот для Марса время задержки составит около 15 минут - так что поговорить по телефону или по Скайпу с марсианской колонией было бы невозможно.
18. Сколько вольт в электросети?
Глупый вопрос, подумают многие. Каждый школьник в России знает что напряжение в сети 220 вольт (в США каждый школьник знает что напряжение в сети 110 вольт). Полезно привести такую картинку:
Кстати, в 90е годы, когда поездки за границу только становились доступными, некоторые привозили американскую электронику, но работала она зачастую не долго, из-за того что сетевое напряжение отличается в 2 раза. А сейчас даже чуть больше, по российскому стандарту 2003 года, напряжение в сети должно составлять 230В. Предельно допустимым отклонением считается 10%, т.е. значения 210-250В в принципе возможны.
Но вопрос заголовка не в этом. Будем для простоты считать напряжение равным “условным” 220 вольт. Однако подключим осциллограф к электросети, и увидим примерно такую картинку:
Что это значит? Где “наши” 220 вольт?
Все просто (хотя и не совсем). Ток в сети переменный - он меняет свое направление с частотой 50 раз в секунду. В отличие к примеру, от батарейки - если на ней написано 1.5 вольта, это значит что на ней действительно 1.5 вольта и направление тока не меняется. Но вернемся к розетке. Ток в нее подается не просто так, а с целью выполнения какой-либо работы. Как измерить работу переменного тока, который в разные моменты времени движется то в одну, то в другую сторону? Для этого было введено понятие действующего напряжения - величины постоянного тока, способного выполнить ту же работу (например нагрев спирали электроплитки). Напряжение, которое показывает осциллограф - называется амплитудным. Эти величины связаны простой формулой:
220 умноженное на √2, дает как раз 310В. Разумеется, обычный тестер откалиброван в “бытовых” единицах, в режиме измерения переменного тока он покажет 220В. А если выпрямить напряжение, например диодным мостиком, то тестер покажет как раз 310В постоянного тока.
И еще немного про переменный ток. Откуда берется напряжение в 380 вольт? Ток от трансформатора подается по 3м фазам: это 3 линии, напряжение в которых сдвинуто на разный угол друг относительно друга.
Картинка из Википедии:
Нулевой провод - общий. В квартиры подается напряжение с одной из фаз, значением в стандартные 220 вольт. Это напряжение называется фазным. Если же используется 3х-фазная сеть целиком, то напряжение между двумя фазами, например в точках a и с на рисунке, составляет как раз 380 вольт. Это напряжение называется линейным.
Математически, оба напряжения связаны простой формулой:
Действительно, 220*√3 = 380.
Кстати, обрыв нулевого провода в доме - серьезная неисправность, из-за чего в квартиры может быть подано линейное напряжение, составляющее те самые 380В. Такой случай произошел лично с автором, впрочем ущерб оказался невелик, перегорели лишь настенные электронные часы и несколько блоков питания. Но при отсутствии в доме людей это может привести и к пожару, такие случаи не редкость. Так что тем, у кого в квартире старая проводка, рекомендуется установить в электрощиток устройство защиты от перенапряжения, его цена невелика, и явно дешевле ремонта в квартире.
19. Нейронные сети
Нейроны - биологическая основа всей разумной жизни на Земле, и казалось, бы при чем здесь математика? При том, что как выяснилось еще в 50е годы, модель нейрона математически очень проста:
Нейрон состоит из определенного числа “входов” (синапсов), каждый из которых имеет определенный весовой коэффициент Wij, собственно ячейки нейрона, суммирующей значения “входов”, некоторой функции активации (упрощенно говоря, нейрон переходит в “активное” состояние, если сумма больше некоторого порога), и выхода (аксона), который в свою очередь, может передать сигнал на следующий нейрон.
Можно написать, что:
Sum = w11*x1 + w12*x2 + … + w1n*xn
Out = f(Sum)
В качестве функции активации f часто используется “сигмоида” (хотя бывают и другие варианты):
Как можно видеть, все весьма просто - математически нейрон лишь чуть сложнее чем обыкновенный сумматор. Выходы нейрона благодаря функции активации лежат в диапазоне 0..1.
Что может делать один нейрон? Практически ничего полезного, но если объединить их в сеть, возможности возрастают кардинально. Например, сеть из 6 нейронов уже способна воспроизвести любую логическую функцию, что мы сейчас и продемонстрируем.
Рассмотрим структуру сети, называемую “многослойный перцептрон” (multilayer perceptron):
Как можно видеть, она состоит из входного слоя нейронов (input layer), скрытого слоя (hidden layer) и выходного слоя (output layer). Каждый нейрон скрытого слоя соединен со всеми входными нейронами, плюс введено дополнительное “смещение” (bias), которое можно представить как нейрон, вход которого всегда = 1 и вес равен константе (например 0.5). Дальше структура повторяется. Количество входных, выходных и скрытых нейронов может быть различно.
Процесс перехода сигнала по сети называется прямым распространением (forward propagation). Допустим, на входе имеются значения: x1 = 0, x2 = 1. Тогда прямое распространение выглядит так:
Шаг-1: передача сигнала от входа во внутренний (hidden) слой
h1 = f(x1*w1 + x2*w2 + 0.5*1)
h2 = f(x1*w3 + x2*w4 + 0.5*1)
Шаг-2: передача сигнала от внутреннего в наружный (output) слой
o1 = f(h1*w5 + h2*w6 + 0.5*1)
o2 = f(h1*w7 + h2*w8 + 0.5*1)
Собственно и все, мы подали на вход сети сигнал “х” и получили на выходе сигнал “о”. Однако внимательный читатель может задать вопрос - а как задаются коэффициенты w1, w2,..,w8? Это собственно, самое интересное и сложное, процесс настройки параметров сети и называется обучением. Задавая различные наборы входных и выходных данных, мы можем обучить сеть воспроизводить требуемые нам функции. Для данного типа сетей используется так называемый алгоритм обратного распространения (back propagation). Его суть в модификации коэффициентов w от конца сети к началу, примерно это можно выразить так:
Шаг-0: Значение коэффициентов w1..w8 заполняются некоторыми случайными величинами.
Шаг-1: Берем набор входных данных, получаем значения выхода (output) методом уже рассмотренного “прямого распространения”.
Шаг-2: Сравниваем значения output с “целевыми” значениями (target). Для удобства сравнения часто используется функция квадрата разности: Err = (output - target)2
Шаг-3: Модифицируем “выходные” коэффициенты w5..w8 так, чтобы значение Err уменьшалось. Для этого используется метод так называемого “градиентного спуска”: функцию output всей нейронной сети в целом легко можно выразить как последовательность сумм и произведений (x1*w1 + x2*w2 …), это значит, что продифференцировав ее по нужному весовому параметру, легко найти производную, например dOutput/dw5. Как известно, производная показывает направление роста функции, что нам и нужно - мы можем изменить параметр w5 на величину, обратную производной.
Шаг-4: Выполняем аналогичный процесс для “входных” коэффициентов w1..w4, формулы тут примерно аналогичны предыдущему пункту.
Шаги 1..4 повторяются до тех пор, пока ошибка не станет меньше некоторой величины. Этот процесс весьма медленный, и может требоваться несколько тысяч итераций, однако выполняется он лишь однократно. Далее коэффициенты можно сохранить, и сеть уже обучена воспроизводить указанный при обучении набор данных. Эти весовые коэффициенты фактически и являются аналогом нейронных связей, появляющихся после обучения в “биологической” сети.
Более подробно формулы с примерами вычислений можно найти здесь. А мы рассмотрим программу на языке Python, реализующую данный метод.
import math, random
class MLP(object):
def __init__(self, n_in, n_hidden, n_out):
self.n_in = n_in
self.n_hidden = n_hidden
self.n_out = n_out
# Входные данные: массив [n_in + 1] инициализирован значениями 1.0
self.inputLayer = [1.0] * (n_in + 1)
# Веса входного-скрытого слоя: матрица [n_in+1]x[n_hidden] заполнена 0..1
self.wIH = [[random.random() for x in range(n_in+1)] for y in range(n_hidden)]
# Скрытые нейроны: [n_hidden + 1]
self.hiddenLayer = [1.0] * (n_hidden + 1)
# Веса нейронов скрытого-выходного слоя: [n_hidden+1]x[n_out], 0..1
self.wHO = [[random.random() for x in range(n_hidden+1)] for y in range(n_out)]
# Выходной слой: массив
self.outputLayer = [1.0] * n_out
def printValues(self):
print "Network: input/hidden/output: {}/{}/{}".format(self.n_in, self.n_hidden, self.n_out)
print "Вход", self.inputLayer
print "wIH", self.wIH
print "Скрытый слой", self.hiddenLayer
print "wHO", self.wHO
print "Выход", self.outputLayer
def printOutput(self):
print "Вход", self.inputLayer
print "Выход", self.outputLayer
def sigmoid(self, x):
# Функция активации
return 1.0/(1.0 + math.exp(-x))
def derivative(self, x):
# Производная функции активации
return x*(1 - x)
def forwardPass(self, x):
# Прямое распространение
# Input
for p in range(len(x)):
self.inputLayer[p] = x[p]
# Input-Hidden
for h in range(self.n_hidden):
sum = 0.0
for i in range(len(self.inputLayer)):
sum += self.inputLayer[i]*self.wIH[h][i]
self.hiddenLayer[h] = self.sigmoid(sum)
# Hidden-Output
for o in range(self.n_out):
sum = 0.0
for h in range(len(self.hiddenLayer)):
sum += self.hiddenLayer[h]*self.wHO[o][h]
self.outputLayer[o] = self.sigmoid(sum)
def backPass(self, input, target):
# Обратное распространение
# Формулы основаны на статье
# /a-step-by-step-backpropagation-example/
learn_rate = 0.5
# Output->hidden layer adjust weights
for o in range(self.n_out):
for h in range(self.n_hidden):
deout = -(target[o] - self.outputLayer[o])
der = self.derivative(self.outputLayer[o])
hid = self.hiddenLayer[h]
der = deout*der*hid
prev = self.wHO[o][h]
self.wHO[o][h] -= learn_rate*der
# Hidden->input layer adjust weights
for h in range(self.n_hidden):
for i in range(self.n_in):
derSum = 0.0
for o in range(self.n_out):
deout = -(target[o] - self.outputLayer[o])
derOut = self.derivative(self.outputLayer[o])
der = deout*derOut*self.wHO[o][h]
derSum += der
derH = self.derivative(self.hiddenLayer[h])
derI = self.inputLayer[i]
der = derSum*derH*derI
prev = self.wIH[h][i]
self.wIH[h][i] -= learn_rate*der
def calcError(self, x, target):
# Вычисление ошибки: 0.5*Sum(dV^2)
err = 0.0
for p in range(self.n_out):
err += 0.5*((self.outputLayer[p] - target[p])**2)
return err
Как можно видеть, создан класс MLP, принимающий на входе 3 параметра: число входных нейронов, число скрытых нейронов, число выходных нейронов.
Рассмотрим пример использования этой сети для логической функции XOR. Как известно, она имеет следующую таблицу истинности:
Таким образом, в нашей сети будет 2 входных параметра (их еще называют “характеристиками”) и 1 выходной. Количество скрытых нейронов пусть будет 2.
Код на языке Python выглядит следующим образом.
mlp = MLP(n_in=2, n_hidden=2, n_out=1)
print("Тренировка сети")
inputs = [ [0.0, 0.0], [0.0, 1.0], [1.0, 0.0], [1.0, 1.0] ]
targets = [ [0.0], [1.0], [1.0], [0.0] ]
N = 500000
for p in range(N):
rand_index = random.randrange(0, len(inputs))
mlp.forwardPass(inputs[rand_index])
mlp.backPass(inputs[rand_index], targets[rand_index])
err = mlp.calcError(inputs[rand_index], targets[rand_index])
if p % 10000 == 0:
print("Step", p, "error", err)
print("")
print("Done")
mlp.printValues()
print("")
print("Результаты")
mlp.forwardPass([ 0.0, 0.0 ])
mlp.printOutput()
mlp.forwardPass([ 0.0, 1.0 ])
mlp.printOutput()
mlp.forwardPass([ 1.0, 0.0 ])
mlp.printOutput()
mlp.forwardPass([ 1.0, 1.0 ])
mlp.printOutput()
Как можно видеть, мы создаем сеть с заданными параметрами, затем выполняем большое количество раз функции прямого и обратного распространения. При каждом вызове функции backPass коэффициенты чуть корректируются в сторону уменьшения ошибки.
В результате получаем следующие наборы параметров W:
Wih = [[10.276084, 9.57721341, 0.11424834], [0.86694222, 0.86379, 0.728575]]
Who = [53.976871, -61.523507, 0.13521682]
Напомним, что весовые коэффициенты фактически соответствуют нейронным связям, возникающим в “настоящих” биологических сетях. Тестирование показывает, что обученная сеть действительно воспроизводит функцию XOR практически достоверно, лишь с небольшой погрешностью:
Input [0.0, 0.0], output [0.0000266]
Input [0.0, 1.0], output [0.95193190]
Input [1.0, 0.0], output [0.95074983]
Input [1.0, 1.0], output [0.07137252]
Как показывает тестирование, если увеличить число скрытых нейронов до 3х, обучение происходит гораздо быстрее, и не требует столь большого числа итераций. Уже 50000 итераций достаточно для приемлемой точности, лог программы выглядит примерно так:
Network: input/hidden/output: 2/3/1
Train phase:
Step 0 error 0.418338057819
Step 10000 error 0.00320960246906
Step 20000 error 0.00115714673178
Step 30000 error 0.00176164027913
Step 40000 error 4.34585435915e-05
wIH [[6.243515, -4.35533, 0.1199493], [5.040033, 5.132244, 0.35661004], [-4.4208235, 6.207919, 0.2522050]]
wHO [-11.2227881, 14.0531446, -11.2731065, 0.9389702]
Test phase:
Input [0.0, 0.0], output [0.0436959]
Input [0.0, 1.0], output [0.9712140]
Input [1.0, 0.0], output [0.9721711]
Input [1.0, 1.0], output [0.0075550]
Как можно видеть, даже такая простая нейронная сеть, изначально заполненная случайными коэффициентами, смогла обучившись на наборе данных, корректно воспроизвести его. Разумеется, количество как входов, так и выходов, может быть другим, функция XOR была взята лишь для наглядности.
Разумеется, описанная выше сеть является очень простой, в качестве более сложного примера можно привести архитектуру так называемой “сверточной сети” (convolutional neural network, CNN). Такая сеть “разбивает” входные данные на фрагменты, каждый из которых в свою очередь выделяет на изображении следующими подсетями какие-то ключевые детали. Подобные сети используются например, в задачах распознавания образов, в частности, рукописного текста.
Фото с сайта
Несмотря на всю сложность (сети могут содержать тысячи нейронов, а их обучение может занимать не один день), принципы функционирования модели нейрона в общем, практически те же, что и в вышеописанной функции XOR.
И еще один философский вопрос, который может возникнуть при рассмотрении нейронных сетей - возможен ли искусственный интеллект, сможет ли компьютер мыслить. Ответ не так прост как кажется. С физической точки зрения - ответ однозначно “да”. По отдельности нейроны нашего мозга состоят из весьма простых компонентов, и нет никакого принципиального запрета смоделировать их работу на компьютере. С алгоритмической точки зрения - узнать как работает самосознание, пока что никто не смог, данный вопрос еще открыт, как для математиков, так и для физиологов. Таким образом, запрограммировать на компьютере процесс мышления пока невозможно, но лишь потому, что собственно принцип еще неизвестен. Впрочем, учитывая скорость развития современных технологий, можно предположить что это лишь вопрос времени, причем возможно не очень дальнего. Хорошо это или нет - вопрос другой, выходящий за рамки данного текста. Ну и для понимания сложности данной задачи - для симуляции лишь 1% человеческого мозга (а это 1.7млрд нервных клеток и 10.4трлн синапсов) в течении 1 секунды, в 2013 году понадобилось 40 минут расчетов на суперкомпьютере из 82000 процессоров.
Что касается нейронных сетей, рассмотренных выше (MLP, CNN), то разумеется, никаким сознанием они обладать не могут, такие сети могут лишь научиться выполнять какую-то одну, пусть и весьма сложную, задачу. Тут еще важно не путать два принципиально разных момента - можно создать “симулятор чата”, загрузив в компьютер сотни тысяч фраз и ответов на них, и даже человек не сможет отличить такого “собеседника” от живого (что-то похожее работает например, в Siri), но полноценным интеллектом с собственным сознанием (есть даже термин “strong AI”) это не является.
20. Нейронные сети - распознавание текста
Рассмотрим практический пример - распознавание выше написанной нейронной сетью рукописного текста. Для тренировки сети воспользуемся имеющейся в открытом доступе базой MNIST, содержащей 60000 черно-белых рукописных изображений цифр размером 28x28пкс.
Выглядят изображения примерно так:
Массив изображений каждой цифры хранится в виде чисел float в диапазоне от 0 до 1, длина массива равна 28х28 = 784 значения. Кстати, при выводе массива в консоль форма цифры вполне узнаваема:
(картинка соответствует числу “5”)
Всего таких чисел, как было сказано, 60000, что вполне хватит для тренировки нашей сети.
Воспользуемся уже готовым классом MLP, изменим лишь некоторые параметры:
- Число входов будет равно 28х28 = 784, т.к. на вход нейросети будет подаваться массив целиком.
- На выходе нейросеть должна давать значения от 0 до 9, однако мы не можем получить значение > 1, так что воспользуемся другим путем: нейросеть будет иметь 10 выходов, где “1” будет соответствовать указанной цифре. Т.е. для числа “0” мы получим [1,0,0,0,0,0,0,0,0,0], для “1” [0,1,0,0,0,0,0,0,0,0], и так далее.
- Число скрытых нейронов мы берем наугад, например 48. Это значение мы позже можем скорректировать по результатам тестирования сети.
В итоге, мы имеем такую структуру сети:
Рассмотрим подробнее программу на языке Python.
Тренировка сети
Создаем нейронную сеть и подготавливаем 2 массива тестовых данных (исходные и целевых значения). Массив “digits” загружается из зараннее подготовленного текстового файла базы MNIST. Для каждой цифры содержится исходный массив в 784 цифры, и правильное значение числа, которое и будет использоваться для тренировки.
mlp = MLP(n_in=28*28, n_hidden=48, n_out=10)
print "1. Загрузка данных"
with open("digitsMnist.txt", 'rb') as fp:
digits = cPickle.load(fp)
print "2. Подготовка данных"
batch = 50
inputs = []
targets = []
for p in range(batch):
data = digits[p]["data"]
resulVal = digits[p]["result"]
# Конвертация целевого числа в массив: “3” => [0,0,0,1,0,0,0,0,0,0]
result_flat = [0.0]*10
result_flat[resulVal] = 1.0
inputs.append(data)
targets.append(result_flat)
Собственно тренировка ничем по сути не отличается от предыдущего примера с функцией XOR. Т.к. процесс идет несколько часов, были также добавлены функции сохранения и чтения состояния сети, чтобы процесс можно было прервать и затем продолжить. Прервать тренировку можно в любой момент нажатием Ctrl+C. Для удобства визуализации процесса выводится суммарная ошибка по всем тестируемым цифрам.
print "3. Обучение"
mlp.load()
try:
N = 10000
for p in range(N):
errSum = 0.0
for d in range(batch):
mlp.forwardPass(inputs[d])
mlp.backPass(inputs[d], targets[d])
errSum += mlp.calcError(inputs[d], targets[d])
print "Step", p, "error", errSum
except KeyboardInterrupt:
pass
mlp.save()
Всего было проведено около 50000 итераций на блоке размером 50 цифр, весь массив в 60000 цифр не использовался. Обучение сети заняло порядка 2х часов на компьютере с Core i7. Разумеется, этот проект учебный, и программа никак не оптимизирована по быстродействию. С использованием специальных фреймворков типа Keras тренировка такой сети занимает не более 5 минут.
Тестирование сети
И наконец, тестирование. В качестве теста, “от руки” была нарисована цифра “3”, которая получилась в виде массива примерно такой:
t = [[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ]]
Следующий код выводить на экран цифру, и значения параметров выходного слоя:
for digit in t:
printDigit(digit)
mlp.forwardPass(digit)
mlp.printOutput()
Результат весьма интересен:
[0.019443, 0.0102247, 0.0091067, 0.467039, 0.0000103, 0.0150096, 0.0008709, 0.0004573, 0.655264, 0.0867915]
На тренировочных значениях сеть должна была выдавать “1” в том разряде, который соответствует “загаданному” числу. И хотя нигде явным образом это не планировалось и специально не программировалось, сеть выдала максимальные значения в тех разрядах массива, где “по ее мнению”, степень схожести максимальна. Как можно видеть, эти разряды соответствуют числам “3” и “8”, что визуально действительно похоже на нарисованное число. Строго говоря, результат не совсем верный, картинка больше похожа на “3” чем на ”8”, но и тренировка не была закончена полностью.
Для следующего теста число нейронов было увеличено до 128, а количество итераций обучения было увеличено до 75000.
Результаты теста на том же массиве:
[0.0044085, 0.219943, 0.0118179, 0.816858, 0.0002372, 0.06267359, 0.0008674, 0.00020319, 0.55439027, 0.00061541]
Максимальное значение теперь действительно соответствует числу “3”, можно сказать что сеть работает как задумывалось.
Для тех кто захочет поэкспериментировать самостоятельно, исходный текст программы и база чисел MNIST находятся в архиве, ссылка на который есть в начале книги.
21. Фракталы
Фракталы - интересные математические объекты, которые долгое время не замечались математиками. В 1872 году, объекты такого типа впервые описал немецкий математик Карл Вейерштрасс, “придумавший” функцию следующего вида:
Это непрерывная функция, но при этом не являющаяся гладкой, для нее невозможно вычислить производную ни в одной из точек.
В Википедии можно найти ее график:
Во времена Вейерштрасса математики назвали такую функцию “оскорблением здравого смысла”, практической применимости не мог найти никто. Лишь через 100 лет, в историческом плане совсем недавно, в 1975 году, математик Мандельброт ввел термин “фрактал”. Фракталы стали широко известны после выхода в 1977 году его книги “Фрактальная геометрия природы” - как оказалось, такие структуры распространены в природе гораздо чаще, чем это можно представить. От ветвей деревьев или рисунка береговой линии, до сосудов человека или колебаний курса акций - все эти процессы имеют природу, схожую с фрактальной.
Основное свойство фракталов - самоподобие, увеличенный фрагмент повторяется большое (в идеале бесконечное) число раз. Простейший пример, знакомый каждому - ветви дерева. Возьмем линию, которая через определенное расстояние делится надвое, для каждой из половинок повторим вышеуказанное правило. Получим знакомый рисунок:
Другим примером служит так называемый “парадокс береговой линии”. При измерении длины государственной границы между Испанией и Португалией, выяснилось, что по измерениям из Португалии, длина границы составила 987км, а по измерениям с Испанской стороны - 1214км. Т.к. противоречие было налицо, им заинтересовался английский математик Льюис Ричардсон, который выяснил, что все дело в масштабе - чем меньше масштаб, тем больше получается длина. Поразительным оказалось то, что при теоретически бесконечном масштабе, длина линии также будет бесконечной!
Впрочем, фигуры такого типа были известны и раньше (хотя их рассматривали скорее как математический курьез), например описанная в 1904 году кривая Коха. Построить ее весьма просто: возьмем линию, разделим ее в центре равносторонним треугольником, для каждой новой линии повторим процесс:
Эта фигура теоретически также имеет конечную площадь, но при этом бесконечную длину края. Также как и функция Вейерштрасса, кривая Коха нигде не дифференцируема. Также очевидно, что при увеличении любого фрагмента кривой Коха, он не будет отличаться от “оригинала”, деление будет продолжаться и дальше.
Если замкнуть 3 такие линии, получится так называемая “снежинка Коха”. Нарисовать ее несложно на языке Python, благодаря встроенной библиотеке рисования Turtle. Она позволяет управляя виртуальной “черепашкой”, рисовать примитивы простыми командами, типа “повернуть на угол” или “сдвинуться на расстояние”.
Для рисования линии Коха, нам потребуются всего 3 команды: сдвинуться вперед, повернуть на 60 градусов, и повернуть на -60 градусов. Повторив процедуру 3 раза, мы получим “снежинку Коха”.
Код на языке Python выглядит так:
import turtle
def koch(size, order):
if order > 0:
koch(size/3, order - 1)
turtle.left(60)
koch(size/3, order - 1)
turtle.right(120)
koch(size/3, order - 1)
turtle.left(60)
koch(size/3, order - 1)
else:
turtle.forward(size)
turtle.ht()
turtle.speed(20)
for i in range(3):
koch(size=400, order=4)
turtle.right(120)
turtle.exitonclick()
В результате работы программы мы получаем следующую картинку:
Можно увеличив количество итераций и размер картинки, убедиться что шаблон повторяется.
Может возникнуть вопрос, как длина линии может быть бесконечной при конечной длине. Примерной аналогией может быть сумма ряда:
S = 0.9 + 0.09 + 0.009 + …
Как нетрудно догадаться, сам по себе ряд бесконечный, но его сумма стремится ко вполне определенному числу 0.999999… = 1.
“Снежинка Коха” интересна своей простотой, но есть и более сложные варианты фракталов. Рассмотрим множество Мандельброта, которое строится по следующему алгоритму: для каждой точки c=x + j*y на комплексной плоскости, эта точка попадает в множество при условии что ряд Zn+1 = Zn2 + c не расходится при z0 = 0.
Рассмотрим пример.
При c = (0,0) = 0 + 0j, ряд очевидно, всегда равен нулю, т.е. не расходится, значит точка (0,0) попадает в множество.
При с = (0.5, 0.5) = 0.5 + 0.5j, получаем следующие значения:
Z0 = 0
Z1 = Z0 + c = 0.5+0.5j
Z2 = Z1 + c = 0.5+1j
Z3 = Z2 + c = -0.25+1.5j
Z4 = Z3 + c = -1.6875-0.25j
Z5 = Z4 + c = 3.28515625+1.34375j
Z6 = Z5 + c = 9.48658752+9.32885j
Легко видеть, что ряд расходящийся, числа увеличиваются, значит (0.5, 0.5) не попадает в множество.
При с = (0.25, 0.25) = 0.25 + 0.25j, имеем следующий ряд:
Z0 = 0
Z1 = Z0 + c = 0.25+0.25j
Z2 = Z1 + c = 0.25+0.375j
Z3 = Z2 + c = 0.171875+0.4375j
Z4 = Z3 + c = 0.088134+0.400390625j
Z5 = Z4 + c = 0.09745508+0.32057666j
Z6 = Z5 + c = 0.15672809+0.31248365j
Z7 = Z6 + c = 0.17691766+0.34794993j
Z8 = Z7 + c = 0.160230+0.37311697j
Z9 = Z8 + c = 0.1364575+0.36956959j
Как можно видеть, ряд не расходится, т.е. точка (0.25, 0.25) попадает в множество.
Разумеется, вручную делать такие проверки было бы крайне неудобно, собственно это одна из основных причин, по которой фракталы не были известны до появления компьютеров. Чтобы заметить какие-либо закономерности фрактальной природы, необходима возможность их автоматического рисования. Кстати, сам Мандельброт работал в IBM и имел доступ к весьма мощным компьютерам своего времени.
На языке Python проверку попадания точки в множество легко записать в виде функции. Для нас удобно то, что Python умеет работать с комплексными числами, что делает запись кода более короткой.
Сама функция имеет следующий вид:
def countMandelbrotIterationsForPt(pt):
z = 0
c = pt
threshold = 64
for iteration in xrange(threshold):
z = z*z + c
if abs(z) > 4:
break
return iteration
Здесь вычисляется 64 итерации, которых вполне достаточно чтобы определить, является ли ряд расходящимся или нет.
Чтобы сохранить весь фрактал, нужно перебрать все точки в диапазоне [-2, 2], программа, сохраняющая фрактал в файл, приведена ниже:
from PIL import Image
points = 1000
img = Image.new('RGB', (2*points,2*points), "black")
pixels = img.load()
# Range.X: -2..2,
# Range.Y: -2..2
for ix in xrange(-points, points, 1):
for iy in xrange(-points, points, 1):
pt = complex(2.0*ix/points, 2.0*iy/points)
i = countMandelbrotIterationsForPt(pt)
if i > 16:
colR, colG, colB = 4*i, 4*i, 0
if colR >= 255: colR = 255
if colB >= 255: colB = 255
if colB >= 255: colB = 255
img_x = points + ix
img_y = points + iy
pixels[img_x, img_y] = (colR, colG, colB)
if ix % 10 is 0:
print "Done: {}%".format(100.0*(ix + points)/(2*points))
img.save("fractal.png")
Как можно видеть, программа содержит 2 вложенных цикла ix, iy, затем значение преобразуются в комплексное число, для которого и выполняется описанная выше функция проверки.
Результат выполнения программы для 1000 точек, показан на рисунке:
Если в несколько раз увеличить количество точек, можно увидеть структуру верхней части более детально:
Немного изменив формулу, можно получить другие виды фракталов. Например, множество Жюлиа, описывается также, но Z0 = pt, и c = const. Казалось бы, небольшое отличие, приводит к совершенно другому рисунку фрактала:
Кстати, этот рисунок напоминает сорт цветной капусты “Романеско”:
Наконец, если в формуле фрактала Мандельброта Zn+1 = Zn2 + c, вычислять абсолютное значение Z*Z в виде (|a| + j|b|)*(|a| + j|b|), мы получим фрактал с названием “горящий корабль”:
Сложно сказать, насколько форма напоминает корабль, верхняя часть под увеличением скорее напоминает береговую линию, видимую с высоты:
Кстати, фрактальные алгоритмы - неотъемлемая часть современных методов рисования ландшафтов, таких как горы, деревья, облака и пр, эти объекты действительно имеют фрактальную природу.
В youtube можно найти интересные трехмерные визуализации фракталов, например, набрав в поиске “mandelbrot 3d”:
Для желающих поэкспериментировать самостоятельно, исходные коды программы генерации фракталов, приведены в приложении к книге. В приложении также есть готовые изображения фракталов, сгенерированные с высоким разрешением более 10000х10000 пикселов.
22. Горн Гавриила
В математике есть некоторые парадоксы, связанные с бесконечностью.
Так называемый “Горн Гавриила” (Gabriel's Horn) - это фигура, образованная функцией y = 1/x, если создать из нее 3х-мерную фигуру:
Интерес данного объекта в том, что “горн” имеет конечный объем - но при этом бесконечную площадь поверхности. Если бы такая фигура существовала в реальности, ее можно было бы заполнить краской, а вот покрасить целиком не получилось бы.
Действительно, формулы площади (V) и объема (A) “горна” легко найти в Википедии:
Из них видно, что при a = ∞, V становится равным ℼ, а A действительно стремится к бесконечности.
23. Построение графиков функций
Очень многие закономерности гораздо легче исследовать графически. Очень просто и эффективно строить графики с помощью языка Python и библиотеки matplotlib.
Выведем графики функций y = x2 и у = 0.5x2.
import matplotlib.pyplot as plt
plt.title('Graph')
plt.xlabel('X')
plt.ylabel('Y')
x_values = range(0,10)]
y_values1 = map(lambda x: 0.5*x*x, x_values)
y_values2 = map(lambda x: x*x, x_values)
plt.axis([0, 10, 0, 20]) # xmin, xmax, ymin, ymax
plt.plot(x_values, y_values1, 'ro', label='0.5*x*x')
plt.plot(x_values, y_values2, marker='o', linestyle='--', label='x*x')
plt.legend()
plt.show()
Результат работы программы выглядит так:
Как можно видеть, мы имеем массив входных данных x_values = range(0,20), и 2 массива выходных данных y_values1 и y_values2, вычисляемых по соответствующим формулам. Все остальное за нас делает библиотека matplotlib. Команда plt.plot выводит график на экран, причем можно задать разные варианты оформления. Команда выводит подсказку (“легенду”), и является опциональной. Команды plt.title, plt.xlabel и plt.ylabel задают названия графика и осей. Команда plt.show выводит окно с графиком на экран.
Рассмотрим более сложный пример.
Выведем график так называемой “функции распределения простых чисел”, показывающий количество простых чисел меньше либо равных числу x.
Программа вывода графика выглядит так:
import matplotlib.pyplot as plt
import math
def is_prime(n):
if n % 2 == 0 and n > 2:
return False
for i in xrange(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
def get_primes(n):
cnt = 0
for i in xrange(1, n):
if is_prime(i):
cnt += 1
return cnt
N = 400
x_values = range(2, N)
y_values = map(lambda n: get_primes(n), x_values)
plt.axis([0, N, 0, N/4])
plt.plot(x_values, y_values, 'ro', markersize=1)
plt.show()
Кстати, согласно Википедии, еще в 18м веке Гауссом и Лежандром было высказано предположение что функция распределения простых чисел выглядит так:
Это легко проверить графически, добавив строчку вывода второго графика:
plt.plot(x_values, map(lambda n: n/math.log(n), x_values), marker='o', linestyle='--')
Окончательный график выглядит так:
С помощью библиотеки numpy строить графики еще проще.
График функции sin(t) в диапазоне 0..2𝜋:
import matplotlib.pyplot as plt
import numpy as np
t = np.arange(0.0, 2.0, 0.01)
s = np.sin(2*np.pi*t)
plt.plot(t, s)
plt.show()
Важно заметить, что t здесь - не одно число, а целый массив - в данном примере используется возможность numpy работать непосредственно с массивами.
И наконец, с помощью matplotlib можно строить даже 3х-мерные графики функции двух переменных, для этого используется модуль mplot3d:
from mpl_toolkits.mplot3d import axes3d
import matplotlib.pyplot as plt
import math
fig = plt.figure()
ax = fig.gca(projection='3d')
# Axis
ax.set_xlabel('X')
ax.set_xlim(0, 20)
ax.set_ylabel('Y')
ax.set_ylim(0, 20)
ax.set_zlabel('Z')
ax.set_zlim(0, 20)
# Graph
for x in range(0,20):
for y in range(0,20):
z = 10*math.sin(0.1*x + 0.1*y)
ax.scatter(x, y, z, c='r', s=1)
plt.show()
Результат показан на рисунке:
Интересно отметить кросплатформенность кода на Python - приведенная выше программа работает и на Windows и на OSX без каких-либо изменений.
Приложение 1 - Вычисления с помощью видеокарты
Еще 20 лет назад, во времена процессоров 80386, пользователям приходилось покупать математический сопроцессор, позволяющий быстрее выполнять вычисления с плавающей точкой. Сейчас такой сопроцессор покупать уже не надо - благодаря прогрессу в игровой индустрии, даже встроенная видеокарта компьютера имеет весьма неплохую вычислительную мощность. Например, даже бюджетный видеочип Intel Graphics 4600 имеет 20 вычислительных блоков, что превышает количество ядер “основного” процессора. Разумеется, каждое ядро GPU по отдельности слабее CPU, но здесь как раз тот случай, когда количество дает преимущество над качеством. Вычисления с помощью GPU сейчас очень популярны - от майнинга биткоинов до научных расчетов, диапазон ценовых решений также различен, от “бесплатной” встроенной видеокарты до NVIDIA Tesla ценой более 100тыс рублей. Поэтому интересно посмотреть, как же это работает.
Есть две основные библиотеки для GPU-расчетов - NVidia CUDA и OpenCL. Первая обладает большими возможностями, однако работает только с картами NVIDIA. Библиотека OpenCL работает с гораздо большим числом графических карт, поэтому мы рассмотрим именно ее.
Основной принцип GPU-расчетов - параллельность вычислений. Данные, хранящиеся в “глобальной памяти” (global & constant memory) устройства, обрабатываются модулями (каждый модуль называется “ядром”), каждый из которых работает параллельно с другими. Модуль имеет и свою собственную память для промежуточных данных (private memory). Так это выглядит в виде блок-схемы:
Таким образом, если задача может быть разбита на небольшие блоки, параллельно обрабатывающие небольшой фрагмент блока данных, такая задача может эффективно быть решена на GPU.
Рассмотрим пример: необходимо проверить, какие числа в массиве являются простыми. Массив может быть большим, например миллион элементов. Такая задача идеальна для распараллеливания: каждое число может быть проверено независимо от предыдущего.
Для решения такой задачи с помощью OpenCL необходимо выполнить ряд шагов.
Написать код микроядра (kernel):
Этот код будет запускаться непосредственно на графических процессорах видеокарты. Код пишется на языке C. В данном примере мы для упрощения храним код прямо в виде строки в программе.
const char *KernelSource = "\n" \
"__kernel void primes( \n" \
" __global unsigned int* input, \n" \
" __global unsigned int* output) \n" \
"{ \n" \
" unsigned int i = get_global_id(0); \n" \
" //printf(\"Task-%d\\n\", i); \n" \
" output[i] = 0; \n" \
" unsigned int val = input[i]; \n" \
" for(unsigned int p=2; p<=val/2; p++) { \n" \
" if (val % p == 0) \n" \
" return; \n" \
" } \n" \
" output[i] = 1; \n" \
"} \n" \
"\n";
Суть кода проста. Массив input хранит числа, которые нужно проверить, функция get_global_id возвращает индекс задачи, которую выполняет данное ядро. Мы берем число с нужным индексом, проверяем его на простоту, и записываем 0 или 1 в зависимости от результата, в массив output.
Инициализировать подготовку вычислений:
int gpu = 1;
clGetDeviceIDs(NULL, gpu ? CL_DEVICE_TYPE_GPU : CL_DEVICE_TYPE_CPU, 1, &device_id, NULL);
cl_context context = clCreateContext(0, 1, &device_id, NULL, NULL, &err);
cl_command_queue commands = clCreateCommandQueue(context, device_id, 0, &err);
На этом этапе можно выбрать где будут производиться вычисления, на основном процессоре или на GPU. Для отладки удобнее основной процессор, окончательные расчеты быстрее на GPU.
Подготовить данные
#define DATA_SIZE 1024
cl_uint *data = (cl_uint*)malloc(sizeof(cl_uint) * DATA_SIZE);
cl_uint *results = (cl_uint*)malloc(sizeof(cl_uint) * DATA_SIZE);
Загрузить данные и программу из основной памяти в GPU
cl_program program = clCreateProgramWithSource(context, 1, (const char **) & KernelSource, NULL, &err);
clBuildProgram(program, 0, NULL, NULL, NULL, NULL);
cl_kernel kernel = clCreateKernel(program, "primes", &err);
cl_mem output = clCreateBuffer(context, CL_MEM_WRITE_ONLY, sizeof(cl_uint) * count, NULL, NULL);
clEnqueueWriteBuffer(commands, input, CL_TRUE, 0, sizeof(cl_uint) * count, data, 0, NULL, NULL);
clSetKernelArg(kernel, 0, sizeof(cl_mem), &output);
clGetKernelWorkGroupInfo(kernel, device_id, CL_KERNEL_WORK_GROUP_SIZE, sizeof(local), &local, NULL);
Запустить вычисления на GPU и дождаться их завершения
global = DATA_SIZE;
clEnqueueNDRangeKernel(commands, kernel, 1, NULL, &global, &local, 0, NULL, NULL);
clFinish(commands);
Загрузить результаты обратно из GPU в основную память
clEnqueueReadBuffer( commands, output, CL_TRUE, 0, sizeof(cl_uint) * count, results, 0, NULL, NULL );
Освободить данные
free(data);
free(results);
clReleaseMemObject(input);
clReleaseMemObject(output);
clReleaseProgram(program);
clReleaseKernel(kernel);
clReleaseCommandQueue(commands);
clReleaseContext(context);
Как можно видеть, процесс довольно-таки громоздкий, но оно того стоит. Для примера, проверка простоты 250000 чисел заняла на процессоре Core i5 около 6 секунд. И всего лишь 0.5 секунд заняло выполнение вышеприведенного кода на встроенной видеокарте. Для дешевого нетбука с процессором Intel Atom этот же код выполнялся 34 секунды на основном процессоре, и 6 секунд на GPU. Т.е. разница весьма прилична.
Разумеется, еще раз стоит повторить, что “игра стоит свеч” лишь в том случае, если задача хорошо распараллеливается на небольшие блоки, в таком случае выигрыш будет заметен.
Владельцы видеокарт NVIDIA (особенно игровых и достаточно мощных) могут также посмотреть в сторону библиотеки NVIDIA CUDA, расчеты с ее помощью должны быть еще быстрее.
Приложение 2 - Быстродействие языка Python
Язык Python очень удобен своей краткостью и лаконичностью, возможностью использования большого количества сторонних библиотек. Однако, один из его минусов, который может быть ключевым для математических расчетов - это быстродействие. Python это интерпретатор, он не создает exe-файл, что разумеется, сказывается на скорости выполнения программы.
Рассмотрим простой пример: рассчитаем сумму квадратов чисел от 1 до 1000000. Также выведем время выполнения программы.
Программа на языке Python выглядит так:
import time
start_time = time.time()
s = 0
for x in xrange(1,1000001):
s += x*x
print("Sum={}, T={}s".format(s, time.time() - start_time))
Результаты работы:
Sum = 333333833333500000, T = 0.47s
Учитывая, что чисел всего миллион, не так уж и быстро. Попробуем ускорить программу, для этого по возможности используем функции встроенных библиотек. Они зачастую написаны на С, и работают быстрее.
import time
start_time = time.time()
l = xrange(1000001)
s = sum(x*x for x in l)
print("Sum = {}, T = {}s".format(s, time.time() - start_time))
Результаты работы:
Sum = 333333833333500000, T = 0.32s
Быстрее, но лишь чуть-чуть.
И наконец, призываем “тяжелую артиллерию”: перепишем программу на языке Cи.
Код выглядит так:
#include <stdio.h>
#include <time.h>
int main()
{
clock_t start = clock();
unsigned long long int sum = 0, i;
for(i=1; i<1000001; i++) {
sum += i*i;
}
clock_t end = clock();
printf("Sum = %llu, T = %fs", sum, (float)(end - start)/CLOCKS_PER_SEC);
return 0;
}
Как можно видеть, он ненамного сложнее python-версии. Перед запуском программы, ее надо скомпилировать, выполнив команду C:\GCC\bin\gcc.exe "Appendix-2 - speedTest.c" -o"Appendix-2 - speedTest". Результат очевиден: T = 0.007 секунд. И еще чуть-чуть: добавляем флаг оптимизации по скорости, выполнив команду C:\GCC\bin\gcc.exe "Appendix-2 - speedTest.c" -o"Appendix-2 - speedTest" -O3. Результат: 0.0035 секунд, разница в быстродействии более 100 раз!
Увы, в более сложных задачах такого прироста реально не бывает (в последнем примере очень короткий код, который видимо полностью помещается в кеш-памяти процессора), но на некоторое улучшение быстродействия можно рассчитывать. Хотя переписывание программы - это крайний случай, сначала целесообразно поискать стандартные библиотеки, которые возможно уже решают данную задачу. К примеру, следующий код на языке Python вычисляет сумму элементов массива за 0.1с:
a = xrange(1000001)
s = 0
for x in a:
s += x
print(s)
Можно использовать встроенную функцию sum:
a = range(1000001)
s = sum(a)
print(s)
Данный код выполняется за 0.02 секунды, т.е. в 5 раз быстрее первого варианта.
Вопрос, что выбрать, на самом деле, не так однозначен - язык Си быстрее, но и сложнее в использовании. Но если заранее известно, что задача состоит в обработке большого набора чисел (например поиск простых чисел или магических квадратов), то может быть более целесообразным сразу писать программу на Си или С++, в принципе это не намного сложнее, а работать программа будет быстрее. С другой стороны, при наличии в программе сложной логики или структур данных, написание ее на Python будет гораздо проще. Поэтому, на практике целесообразно прототип программы делать на языке Python, и только в том случае, если проблема быстродействия становится критичной и не решаемой доступными средствами, переходить на более низкоуровневые средства разработки.
Кстати, для тех, кто захочет максимально широко использовать Python в математических расчетах, крайне рекомендуется ознакомиться с библиотекой numpy, она является стандартом де-факто для всех серьезных расчетов.
Приложение 3 - Пример оптимизации программы
Рассмотрим практический пример сравнения скорости вычислений на Python. Допустим, есть массив целых чисел, для каждого числа надо найти количество его делителей.
Функцию нахождения делителей числа будем использовать “как есть”, без какой-либо оптимизации: перебираем все числа, если число делится без остатка, увеличиваем счетчик.
def get_dividers(n):
divs = 0
for i in xrange(1, n+1):
if n % i == 0:
divs += 1
return divs
Рассмотрим способы решения задачи. Исходные данные: массив целых чисел:
values = [41212317, 4672313, 4342311, 46512319, 51212317, 5672313, 5342311, 56512319]
Способ-1
Решение “в лоб” (заодно показан способ измерения времени выполнения).
import timeit
start_time = timeit.default_timer()
res = []
for v in values:
res.append(get_dividers(v))
print(res)
print("T =", timeit.default_timer() - start_time)
Время выполнения кода на компьютере с процессором Core i7: 10c.
Способ-2
Используем функцию map, позволяющую применить функцию сразу к массиву.
res = map(get_dividers, values)
print(list(res))
Время выполнения: те же 10с, пока мы выиграли разве что в краткости записи.
Способ-3
Используем многопоточность, класс multiprocessing.Pool, позволяющий разбить вычисления над массивом на несколько потоков.
p = multiprocessing.Pool(processes=4)
res = p.map(get_dividers, values)
print(list(res))
Время выполнения: 3.7с, что уже лучше. Интересно, что несмотря на разбивку на 4 процесса, реальное время выполнения уменьшилось лишь вдвое. Многопоточные вычисления - достаточно дорогостоящая в плане накладных расходов операция, множество ресурсов процессора тратится на синхронизацию и передачу данных между процессами.
Способ-4
Используем библиотеку параллельных вычислений ipyparallel. Она имеет большие возможности, даже позволяет производить вычисления параллельно на нескольких компьютерах.
Перед тестом запустим сервер вычислений на том же компьютере, командой
ipcluster start -n 4.
Код запуска вычислений не намного больше:
import ipyparallel as ipp
rc = ipp.Client()
dv = rc[:]
res = dv.map_sync(get_dividers, values)
print(list(res))
Как можно видеть, синтаксис практически тот же, библиотека сама делает всю работу по распараллеливанию вычислений. Впрочем, время выполнения практически то же - 3.4с, ведь мы выполняем вычисления на одном компьютере. При желании читатели могут повторить эксперимент с несколькими компьютерами самостоятельно, описание процесса есть на странице .
Способ-5
Как говорилось еще в начале книги, Python - это интерпретатор, и код выполняется достаточно медленно. Кардинально повысить скорость можно, используя компиляцию программы перед выполнением, что было реализовано в библиотеке Numba. Ее можно поставить, выполнив команду “pip install numba”.
Метод очень простой и эффективный, и практически не требует изменения кода: всего лишь добавляем перед описанием функции ключевое слово @numba.jit.
Данный код скопирован в отдельный файл Appendix3_test2.py:
import numba
@numba.jit
def get_dividers(n):
divs = 0
for i in xrange(1, n+1):
if n % i == 0:
divs += 1
return divs
Запуск ничем не отличается от предыдущего варианта:
import Appendix3_test2 as test2
res = map(test2.get_dividers, values)
print(list(res))
Время выполнения в обычном, однопоточном режиме - 1.5с. Это уже заметная разница!
И наконец, повторяем вышеописанные процедуры, но функцию заменяем на новый вариант.
Многопоточность:
p = multiprocessing.Pool(processes=8)
res = p.map(test2.get_dividers, values)
Время выполнения: 1.04c.
И последний вариант, библиотека ipyparallel:
res = dv.map_sync(test2.get_dividers, values)
print(list(res))
Время выполнения: 0.57c.
Таким образом, по сравнению с изначальным вариантом, мы увеличили скорость расчетов почти в 20 раз, при этом сам код изменять или переписывать практически не пришлось.
В целом, можно предложить следующий алгоритм оптимизации вычислений на языке Python:
1) По возможности, стараться использовать встроенные функции, имеющиеся в библиотеках math, numpy и др. Они уже написаны на C или C++, и работают максимально эффективно.
2) Использовать библиотеку numba, указав в начале функции префикс @numba.jit. Это самый простой и “безболезненный” способ, он чуть увеличит время запуска программы, но скорость расчетов может вырасти в 10 раз. Правда, этот способ не поможет, если код уже состоит только из вызовов встроенных функций из п1. Если же код содержит циклы, условия, другие проверки, то скорость выполнения вырастет значительно.
3) Если скорость расчета нужно еще увеличить, переходим к более тяжелой артиллерии - многопоточности. Используя библиотеку multiprocessing, можно разбить вычисления на несколько ядер процессора - это может увеличить скорость в 2-4 раза. Но важно иметь в виду, что межпроцессное взаимодействие - сама по себе довольно-таки долгая операция, так что делать ее имеет смысл для действительно долго выполняющихся фрагментов кода. Небольшая функция, вызывающаяся много раз в разных потоках, будет работать в итоге даже медленнее за счет дополнительных “накладных расходов”.
4) И наконец, если скорость расчета нужно еще увеличить, можно разбить вычисления на несколько компьютеров в сети, используя библиотеку ipyparallel. Как и в предыдущем случае, заранее следует продумать структуру алгоритма, чтобы производить вычисления крупными блоками, это сделает метод более эффективным.
Кстати, заранее бывает довольно сложно предсказать, насколько хорошо сработает тот или иной метод. Более того, результат может оказаться даже хуже чем был, если например накладные расходы на передачу данных превышают выигрыш. Поэтому каждый шаг оптимизации следует обязательно проверять тестами, чтобы убедиться, что процесс идет в правильном направлении.
Заключение
На этом данная книга закончена, хотя надеюсь, что не навсегда - по возможности и по мере появления новых идей, новые главы будут дописываться. Автор надеется, что хоть немного удалось познакомить читателей с увлекательным миром математики и программирования.
Продолжение следует.
Обо найденных неточностях или дополнениях просьба писать на электронную почту dmitryelj@gmail.com. Наличие новой версии можно проверить на странице .
Fueled by Johannes Gensfleisch zur Laden zum Gutenberg
Комментарии к книге «Рассказы о математике с примерами на языках Python и C», Д. Елисеев
Всего 0 комментариев