Дискретная производная или Коротко о том, как суммировать ряды

3 min

18K

Вступление

Бывало когда-нибудь такое, что вы хотите просуммировать какой-то бесконечный ряд, но не можете подобрать частичную сумму ряда? Вы все ещё не пользовались дискретной производной? Тогда мы идём к вам!

Определение

Дискретной производной последовательности

$inline$ назовем такую последовательность

$\Delta a_n$ , что для любых натуральных

$inline$ выполняется:

$\Delta a_n = a_n - a_{n-1}$

Рассмотрим примеры:

$a_n = 1\\ \Delta a_n = a_n - a_{n-1} = 1 - 1 = 0$
$a_n = n\\ \Delta a_n = a_n - a_{n-1} = n - (n - 1) = 1$
$a_n = n^2\\ a_n = n^2 - (n - 1)^2 = n^2 - (n^2 - 2n + 1) = 2n-1$
$a_n = n^3\\ \Delta{a_n} = n^3 - (n - 1)^3 = 3n^2 - 3n + 1$
$a_n = k^n\\ \Delta{a_n} = k^n - k^{n-1} = k^{n-1}(k-1)$

Ну, суть вы поняли. Чем-то напоминает производную функции, правда? Мы поняли как вычислять дискретные производные «простейших» последовательностей. Кхм, но что делать с суммой, разностью, произведением и частным последовательностей? У «обычной» производной есть некоторые правила дифференцирования. Давайте-ка придумаем для дискретной!

Читать дальше →

+22

code_batya Feb 1 2019 at 19:25

Сжатие данных алгоритмом Хаффмана

15 min

64K

Algorithms*Data compression*Java*

From sandbox

Вступление

В данной статье я расскажу вам о широко известном алгоритме Хаффмана, и вы наконец разберетесь, как все там устроено изнутри. После прочтения вы сможете своими руками(а главное, головой) написать архиватор, сжимающий реальные, черт подери, данные! Кто знает, быть может именно вам светит стать следующим Ричардом Хендриксом!

Да-да, об этом уже была статья на Хабре, но без практической реализации. Здесь же мы сфокусируемся как на теоретической части, так и на программерской. Итак, все под кат!

Читать дальше →

+26