Прикладная математика и прочее веселье

Накануне мне понадобилось найти гладкую функцию, определенную на $\textbf{R}[a,c]$, равную единице на одном отрезке числовой оси, скажем, $[a, b-\epsilon]$ и нулю на другом, скажем $[b+\epsilon, c]$. Для того, чтобы гладко склеить эти два кусочка, я решил найти монотонно убывающий многочлен $f(x)$, равный $f(0) = 1$ и $f(1) = 0$, а потом "вставить" его в отрезок $[b-\epsilon, b+\epsilon]$. Для гладкости сшивки должны выполняться условия $f'(0) = f'(1) = 0$. Я решил пойти далее и положить $f^{(n)}(0) = f^{(n)}(1) = 0$ для всех $n = 1,2,\cdots,N$. То есть первые N производных должны быть равны нулю в т. $x = 0$ и $x = 1$. Понятно, что это легко сделать при наперед известном N, но как найти общую формулу? Я некоторое время промучился над этой задачей, пока не решил её следующим способом. Пусть искомая функция $f(x) = 1 + x^{N+1}L_{1}(x)$, где $L_{1}(x)$ — некий многочлен. Тогда у нас выполняется условие $f(0) = 1$ и $f^{(n)}(0) = 0$ (так как первая производная будет...

Что такое вейвлет-преобразование? UPD: 21 октября: добавлена новая инфа и пару картинок, исправлены ошибки. Прежде чем рассказать, как я делал свой кодек, расскажу, что же такое вейвлет преобразование. Остановлюсь на его дискретном варианте. Все, у кого в институте была хоть какая-никакая математика, слышали про ряды Фурье. Это когда функцию можно разложить по базису в таком виде: $f(x) = \sum_{k=0}^{\infty} \langle f(x), \psi_{k}(x) \rangle \psi_{k}(x)$ Обычно в виде $\psi_{k}(x)$ берутся всевозможные синусы и косинусы, это называется разложением по гармоническому базису. Я напишу это условно так: $f(x) = \sum_{k=-\infty}^{\infty} \langle f(x), e^{ikx} \rangle e^{ikx}$ Как мы видим, $\psi_{k}(x) = \psi_{1}(kx)$, где $\psi_{1}(x) = e^{ix}$. В результате такого разложения мы получаем набор коэффициентов, где каждый коэффициент отвечает за "наличие" в функции гармонического колебания с частотой 1,2,3 итд. За это мы "забываем" информацию о времени, то ес...

Итак, это завершающий пост про задачу из игры Sanitarium, где будет дано решение для случая восьми зацепов, а также рассмотрен более общий алгоритм решения для произвольного случая зацепов. Итак, напомню, что конфигурацию крестовины и состояние зацепов я обозначаю многочленами, где степень при $x$ — порядковый номер зацепа или "усика" крестовины, а коэффициент обозначает состояние "открыт/закрыт" или конфигурацию крестовины (см первый пост ). Сложение коэффициентов многочленов происходит по модулю $2$, а умножение многочленов — по модулю $x^8 + 1$, что обеспечивает "заворачивание" восьмой степени на нулевую, девятой на первую итд. Напомню также, что ранее я получил частичное решение задачи, отыскав многочлены, имеющие обратный, и открывая зацепы последовательно по одному. Теперь я подошел к задаче иначе. Интересный факт, что для любого $n \geq 1$ справедливо $x^n + 1 = (x+1)(\sum_{i=0}^{n-1}x^i)$ Последний сомножитель есть ни что иное, как многочлен...

В предыдущем посте я рассмотрел задачу из игры Sanitarium, связанную с открытием зацепов, удерживающих камень. Я пришел к выводу, что задача частично сводится к нахождению многочленов $p(x)$, имеющих обратный по отношению к операции умножения, т.е. $p(x)q(x)=1$ на кольце $F_{2}[x]/(x^8+1)$. Был получен результат, что не каждый многочлен имеет обратный, так как генерирующий многочлен факторкольца разлагается на множители: $(x^8+1) = (x+1)^8$. Логично искать обратимые многочлены среди относительно простых по отношению к $x^8+1$, т.е. тех, которые не делятся на $x+1$. Проверим несколько многочленов: $1$ — крестовина из одного элемента, тривиальное решение. $x$ — аналогично. $x+1$ — делится на $x+1$. $x^2$ — опять крестовина из одного элемента. $x^2+1$ — делится на $x+1$. $x^2+x+1$ — не тривиальное решение и не делится на $x+1$ — наш клиент! Написав на своем любимом лиспике простую программку, я подобрал обратный многочлен $q(x) = x^7 + x^5 + x^4 + x^2 + x$. Как это работает? Н...

Sanitarium — невероятно интересный (по мнению автора) квест 1998 года выпуска про учёного-микробиолога по имени Макс, попавшего в сумасшедший дом после потери памяти в результате автомобильной аварии. По ходу игры Макс перемещается между параллельными мирами, придуманными силой воображения… Одним словом, лучше поиграть, а не читать спойлеры. В части игры "Лаборатория" (7 часть) представлена очень интересная задача. Нужно открыть восемь круговых зацепов, охватывающих камень, чтобы тот упал. Зацепами управляет треугольная крестовина (на самом деле, 4-х угольная, но один конец там поломан и не влияет на зацепы) на пульте управления. Крестовину можно повернуть вокруг оси на одну позицию в любую сторону. При нажатии на кнопку, зацепы, соответствующие положению крестовины, меняют своё состояние (запертый зацеп отпирается, открытый — закрывается). Вот скриншот для ясности: Цель оригинальной головоломки, как я сказал, — открыть все зацепы. Я предлагаю усложнённый вариант — ...

В посте про амплитудную модуляцию можно было видеть, что сигнал модулируется на двух частотах, равноотстоящих от частоты сигнала-носителя. Была там даже картиночка с "закодированным" сигналом: Эти 2 сигнала сверху и снизу от частоты несущего сигнала называются upper sideband и lower sideband. Каждый из них равнозначен, в том плане, что исходный сигнал можно восстановить из каждого из них, перемножив sideband на несущий сигнал и пропустив через low-pass фильтр: $\cos \left( \omega_{c} + \omega_{s} \right)t \sin \omega_{c}t = \frac{1}{2} (\sin (\omega_{c} + \omega_{s} - \omega_{c})t + \sin (\omega_{c} + \omega_{s} + \omega_{c})t) = \frac{1}{2} (\sin \omega_{s}t + \sin (2\omega_{c} + \omega_{s})t)$ $\cos \left( \omega_{c} - \omega_{s} \right)t \sin \omega_{c}t = \frac{1}{2} (\sin (\omega_{c} - \omega_{s} - \omega_{c})t + \sin (\omega_{c} - \omega_{s} + \omega_{c})t) = -\frac{1}{2} (\sin \omega_{s}t - \sin (2\omega_{c} - \omega_{s})t)$ Как видим, после фильтрации два во...