3 заметки с тегом

математика

Алгоритмы поиска чисел Фибоначчи

Для лучшего понимания статьи, можно почитать про виды сложностей алгоритмов и операции с матрицами.

Числа Фибоначчи — последовательность чисел, где каждое следующее число это сумма двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Их мельком проходят в школе на алгебре и примерно в то же время на геометрии говорят про золотое сечение.
Так Евклид назвал формулу почти идеального для построения правильного пятиугольника. Большая величина относится к меньшей так же, как сумма этих величин к большей. В виде формулы это выглядит так: \(\frac ab = \frac {a+b}{a}\), a — большая величина и b — меньшая.

Золотое сечение обозначается греческой буквой ФИ и объясняется вот такой формулой: \(\phi = \frac {1 + \sqrt 5}{2}\), с точностью до пяти знаков ФИ равно 1,61803.

И тут появляются числа Фибоначчи: отношение одного числа к предыдущему постоянно приближается к значению золотого сечения. Чем больше числа, тем точнее приближение \(\frac {55}{34} \approx 1.61764, \frac {377}{233} \approx 1.61802\).

Число спиралей на большинстве шишек и ананасов, расположение листьев растений, длина и ширина учётных карточек, окна, игральные карты равны последовательным числам ряда Фибоначчи. Все вещи где встречаются числа Фибоначчи почитайте в статье на медиуме.

Вычисление чисел Фибоначчи

Чтобы найти какое-то конкретное число есть четыре способа. Некоторые эффективны только до какого-то числа, но все вычисляют точно.

Рекурсивный — самый медленный

Каждый раз рекурсивно вызываем функцию, чтобы дойти до двух первых чисел Фибоначчи. После этого, цепочка вызовов заканчивается и начинает сворачиваться.

Это работает сносно, пока не нужно вычислять числа стоящие выше 30 номера в последовательности, потому что при каждом вызове функции она вызывает себя дважды и вычисляет одни и те же значения много раз.

Алгоритмическая сложность — экспоненциальная, \(\mathbf O(2^n)\)

Хорошее быстрое решение — динамическое программирование

Из определения последовательности Фибоначчи становится понятно, что для вычисления нам нужны только два последних числа. Тогда теперь переменно записываем только два последних вычисленных числа, а не всю последовательность.

Алгоритмическая сложность — линейная, O(n)

Самое быстрое точное решение — возведение матриц в степень

Это работает потому что возведение матрицы в степень можно сделать за \(\mathbf O(log_2 n)\).
Существует вот такое матричное уравнение:
$$\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} =
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$$
Правую матрицу обычно называют Ку-матрицой и если понизить её степень на один, то индексы в левой матрице тоже понизятся.

После понижения степени получается такое уравнение:
$$\begin{bmatrix} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end{bmatrix} =
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}$$

Теперь делаем так: возводим Ку-матрицу в степень n − 1 и берём элемент из первой строки, первого столбца. В программировании всё считается с нуля, поэтому там нулевой элемент, нулевого столбца

Алгоритмическая сложность — логарифмическая, \(\mathbf O(log_2 n)\)

Формула Бине

Тоже быстрое решение, но после семидесятого числа начинаются погрешности, потому что там очень длинная дробь, а точность чисел в компьютере ограничена.
Формула: \(F_n = \frac {\phi^n}{\sqrt 5}, \phi = \frac {1 + \sqrt 5}{2}\).

Например, вычисление 25 числа будет выглядеть так:

  1. Вычисляем ФИ: \(\phi = \frac {1 + 2.23606797749979}{2} = 1.618033988749895\)
  2. Вычисляем формулу: \(F_{25} = \frac {1.618033988749895^{25}}{2.23606797749979} = \frac {167761.000005961}{2.23606797749979} = 75024.99999733428 \approx 75025\)
  3. Получаем 25 число: \(F_{25} = 75025\)

Алгоритмическая сложность — постоянная, O(1)

Мы запустили все способы на своих печках и посчитали их время, чтобы показать разницу в скорости.
Рекурсивному алгоритму мы отдали вычислять 43 число, он считал его чуть меньше 7 минут.
Динамический и матричный алгоритмы сильнее, поэтому пускай вычисляют 1 000 000 число.
Матричный алгоритм справился за пол секунды, динамический за 12 секунд.

 31   23 дн   алгоритмы   математика

Введение в алгоритмы

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

Алгоритмы

Это набор инструкций для выполнения какой-нибудь задачи. Рецепт приготовления шарлотки, правила расстановки запятых, ПДД — это всё алгоритмы.
Хороший кодер понимает как работают алгоритмы и какой подходит для его задания.

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

Скорость работы

Скорость работы выражается в О-большом. Оно показывает насколько сильно растёт количество операций в зависимости от аргумента.

Измерять в секундах не круто, потому что на разных компьютерах стоит разное железо и разная архитектура. Код, который на домашнем ПК выполнится за 3 минуты, на мейнфрейме IBM выполнится за 5 секунд. Поэтому у О-большого нет обозначения единиц измерения, просто значения.

У О-большого есть аргумент — аргумент алгоритма. То есть, какое число стоит в скобках, такое число передается алгоритму на вход.
Например, скорость работы алгоритма = O(n). Это значит, что чтобы пройтись по списку из 16 значений, ему нужно будет 16 операций.
Алгоритму со скоростью работы O(log n) нужна будет 4 операции, потому что O(log n) = O(log 16) = O(4).

В кодинге сложилось несколько основных типов сложностей алгоритмов: линейная, логарифмическая, квадратичная и экспоненциальная. Есть и другие, но встречаются они реже, чем эти.

Чтобы понять смысл графиков, представим что компьютер работает медленно и выполняет одну операцию в секунду.

На самом деле, домашние компьютеры работают в 3 миллиарда раз быстрее.

Количество занимаемой памяти

Чтобы понять сколько памяти нужно для выполнения программы, нужно посчитать объём входных данных, данных для хранения самой функции и объём выходных данных. Существует два способа посчитать объём памяти: посчитать руками или через скрипт.

Руками
Выделяем кусок кода и смотрим, какие данные и операции там есть. Число типа int — добавляем 24 байта, строка — добавляем 49 байт и так далее. Мы писали про размеры в статье про типы данных и сколько они занимают.
Если функция рекурсивная, то после подсчёта объёма, нужно умножить его на количество вызовов. После всех подсчётов получится примерное количество используемой памяти в байтах.

a = 7  # Занимает 24 байта
b = 3.0  # Занимает 24 байта

string = 'test'  # Занимает 53 байта: 49 на пустую строку и по байту на каждый символ
# Всего получается 24 + 24 + 53 = 101 байт

Через скрипт
Скачиваем библиотеку memory_profiler через pip3. Пишем в терминале python3 -m memory_profiler имя_файла.py.
Он построчно посчитает код и сразу добавит сколько это займёт вместе с интерпретатором и системными штуками, которые никто не видит.

memory_profiler считает и объём пайтон-интерпретатора, потому что он запускается чтобы выполнить скрипт

Матрицы

Если вы уже изучали матрицы и поняли как они работают, можете листать дальше.

Мы сделали статью про матрицы отдельной, потому что они нужны не только программистам, но ещё и старшеклассникам и первокурсникам физматов.
Погружение в мир матриц.

Матрицы в пайтоне

Чтобы использовать матрицы в пайтоне, нужно установить библиотеку NumPy.

Для винды
pip install numpy

Для линукса/мака
pip3 install numpy

Матрица лежит в памяти как массив. Создаётся матрица вот так

import numpy as np


# Матрица 3×3 с элементами от 0 до 8
matrix = np.arange(9).reshape(3, 3)
print(matrix)

Сложение и вычитание матриц

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)
matrix_b = np.arange(9).reshape(3, 3)

print(matrix_a + matrix_b)
print(matrix_a - matrix_b)

Умножение матрицы на число

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)

print(matrix_a * 3)

Умножение матрицы на матрицу делается через функцию dot

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)
matrix_b = np.arange(9).reshape(3, 3)

print(np.dot(matrix_a, matrix_b))

Возведение в степень

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)
print(np.linalg.matrix_power(matrix_a, 5))

В следующей статье по алгоритмам и математике мы хотим рассказать про числа Фибоначчи.

 33   4 мес   алгоритмы   математика

Математика. Матрицы и операции с ними

Мы решили поделить статью на две части: про алгоритмы полезна для программистов, а статьёй про матрицы можно поделиться со знакомыми старшеклассниками и первокурсниками физматов.



Матрица это таблица с числами. Обозначается большой буквой, строки обозначаются буквой i, столбцы буквой j.
Например, матрица размером 3×3 выглядит так.
$$
A =
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 \\
\end{bmatrix}
$$
Чтобы выбрать конкретный элемент из матрицы, нужно написать название матрицы и индекс элемента.
Сначала строка, потом столбец — \(A_{3;2}\) = 8

Операции с матрицами

Пока что мы расскажем про транспонирование, сложение, вычитание, умножение на число, умножение матрицы на матрицу и возведение в степень. Если будет нужно что-нибудь по-сложнее — потом расскажем.



Транспонирование
У элемента матрицы индексы строки и столбца меняются местами.
$$
A =
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 \\
\end{bmatrix}

A =
\begin{bmatrix}
1 & 4 & 7 \\
2 & 5 & 8 \\
3 & 6 & 9 \\
\end{bmatrix}
$$
Было \(A_{1;2}\) = 4, после транспонирования станет \(A_{1;2}\) = 2.



Сложение и вычитание
Чтобы сложить матрицы, нужно сложить элемент с индексом i;j в первой матрице и элемент с таким же индексом во второй матрице. Складывать и вычитать можно только одинаковые по размеру матрицы.
Например
$$
\begin{bmatrix}
3 & 1 & 5 \\
6 & 2 & 8
\end{bmatrix}
+
\begin{bmatrix}
1 & 3 & 4 \\
2 & 5 & 0
\end{bmatrix}
=
\begin{bmatrix}
3 + 1 & 1 + 3 & 5 + 4 \\
6 + 2 & 2 + 5 & 8 + 0
\end{bmatrix}
=
\begin{bmatrix}
4 & 4 & 9 \\
8 & 7 & 8
\end{bmatrix}
$$


$$
\begin{bmatrix}
3 & 1 & 5 \\
6 & 2 & 8
\end{bmatrix}

\begin{bmatrix}
1 & 3 & 4 \\
2 & 5 & 0
\end{bmatrix}
=
\begin{bmatrix}
3 — 1 & 1 — 3 & 5 — 4 \\
6 — 2 & 2 — 5 & 8 — 0
\end{bmatrix}
=
\begin{bmatrix}
2 & -2 & 1 \\
4 & -3 & 8
\end{bmatrix}
$$



Умножение матрицы на число
Просто умножаем каждый элемент на это число
$$
2 \cdot
\begin{bmatrix}
3 & 1 & 5 \\
6 & 2 & 8
\end{bmatrix}
=
\begin{bmatrix}
2 \cdot 3 & 2\cdot 1 & 2\cdot 5 \\
2\cdot 6 & 2\cdot 2 & 2\cdot 8
\end{bmatrix}
=
\begin{bmatrix}
6 & 2 & 10 \\
12 & 4 & 16
\end{bmatrix}
$$



Умножение матрицы на матрицу
Чтобы умножить матрицу на матрицу нужно одно условие: число столбцов первой матрицы должно совпадать с числом строк во второй. После умножения, получается матрица с количеством строк первой матрицы и столбцов второй.
Матрицу 5×2 можно умножить на матрицу 2×4, но не на матрицу 3×4.

Алгоритм умножения:

  1. Разметьте будущую матрицу с количеством строк от первой матрицы и столбцов от второй, у нас это 4×5.
  2. Умножьте первый элемент первой строки первой матрицы — 3 на первый элемент первого столбца второй матрицы — 4.
    Второй элемент первой строки из первой матрицы умножьте на второй элемент из первого столбца второй матрицы — 2×3. Третий с третьим, и так до конца строки в первой матрице.
    Когда строка закончилась, результаты умножения сложить вот так: 3×4 + 2×3 = 18.
    Тут помогает правило для возможности умножения, потому что количество строк и столбцов одинаковое.
  3. Результат сложения внести в элемент в новой матрице с индексом строки из первой матрицы и столбца со второй матрицы. Первые строка и столбец, значит \(C_{1;1}\) = 18, это показано на втором слайде ниже.
  4. Теперь те же числа из первой матрицы, умножить на второй, третий, Nый столбик и складывать, пока не закончатся столбики во второй матрице.
  5. Если закончились столбики, переходим на следующую строку в первой матрице и повторяем действия второго пункта.
  6. Если закончились строки — всё готово.



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

$$
\begin{bmatrix}
3 & 1 & 5 \\
6 & 2 & 8 \\
9 & 4 & 1
\end{bmatrix}
*
\begin{bmatrix}
3 & 1 & 5 \\
6 & 2 & 8 \\
9 & 4 & 1
\end{bmatrix}
*
\begin{bmatrix}
3 & 1 & 5 \\
6 & 2 & 8 \\
9 & 4 & 1
\end{bmatrix}
=
\begin{bmatrix}
582 & 222 & 528 \\
1044 & 402 & 900 \\
1008 & 414 & 546
\end{bmatrix}
$$



Пока что с матрицами это всё.
Если у вас есть предложения для тем разбора по математике, пишите нам в телеграм @cmp_sci.

 26   4 мес   алгоритмы   математика