Архив рубрики: Математика

Аффинное пространство как груда

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

Обычно аффинное пространство определяется как множество, на котором транзитивно и свободно действует некое линейное пространство. В этом определении нет ничего плохого, но можно избавиться от линейного пространства, задав аффинное аксиоматически. Здесь поможет структура, известная как груда (heap). Она получается, если «забыть» нейтральный элемент группы, откуда её связь с аффинным пространством очевидна — это «коммутативная» груда \((A, [\cdot,\cdot,\cdot])\) с некоторой дополнительной структурой, связывающей её с некоторым полем \(K\). (В исходных терминах \([x,y,z] = x + \overrightarrow{yz}\equiv x-y+z\).)

Читать далее Аффинное пространство как груда

it is closed!

hello!
~( (a & b > c) | d > a > b > c | d )
((((a & b) > c) | d) & (a & (b & ~(c | d))))
try to close corresponding tableau...
it is closed!
((((a & b) > c) | d) & (a & (b & ~(c | d))))		[1]
(((a & b) > c) | d)		[2, from 1]
(a & (b & ~(c | d)))		[3, from 1]
1. ((a & b) > c)		[1, from 2′]
1. a		[2, from 3′]
1. (b & ~(c | d))		[3, from 3′]
1. 1. ~(a & b)		[1, from 1′]
1. 1. b		[2, from 3′]
1. 1. ~(c | d)		[3, from 3′]
1. 1. 1. ~a		[1, from 1′]
1. 1. 1. [x]
1. 1. 2. ~b		[1, from 1′]
1. 1. 2. [x]
1. 2. c		[1, from 1′]
1. 2. b		[2, from 3′]
1. 2. ~(c | d)		[3, from 3′]
1. 2. ~c		[4, from 3]
1. 2. [x]
2. d		[1, from 2′]
2. a		[2, from 3′]
2. (b & ~(c | d))		[3, from 3′]
2. b		[4, from 3]
2. ~(c | d)		[5, from 3]
2. ~c		[6, from 5]
2. ~d		[7, from 5]
2. [x]

Чему равно N?

Думаю, многие часто спрашивают себя: чему равно \(k\)? чему равно \(m\)? чему, наконец, равно \(N\)? Целые числа далеко не все простые, а многие даже откровенно загадочны. Но математика, выворачивавшаяся и не из таких передряг, смогла-таки (и даже в обход дебрей теории чисел, что уже восхищает!) найти ответ. И даже не один. Итак,

Чему равна длина последовательности \(a=(a_0,\ldots,a_{N-1})\)? Возьмите от него дискретное преобразование Фурье\[(\mathcal Fa)_m = \sum_{n=0}^{N-1} a_n e^{-i\tau mn/N}\]четыре раза. Результат будет равен исходной последовательности, покомпонентно умноженной на квадрат своей длины!

Чему равна размерность векторного пространства \(V\)? Она равна \(\operatorname{tr}\mathrm{id}_V\). Если поле скаляров конечное, размерность придётся искать обычным способом, хотя этот в некоторых случаях и даёт правильный ответ.

Чему равна степень многочлена \(P = a_0 + a_1x + \ldots + a_Nx^N\)? Степень равна (!) числу штрихов, после приписывания которых к выражению \(P’\) то станет равным нулю.

Некоторые вопросы о целых числах не так просты, и для этого есть OEIS.

Оригинальное чувство юмора имели люди, подготовившие книжку для инженеров с такой иллюстрацией:

Распутай сам

Фибоначчи, Haskell, O(log n)

(Внимание: дальше не написано ничего нового, но если вы не знаете о возведении в степень за \(O(\log n)\), можете чуть-чуть почитать.)

Не секрет, что числа Фибоначчи можно вычислить за экспоненциальное время, используя наивную рекурсию; за линейное время, используя более аккуратный способ; и даже за константное время, используя округление \(\frac{\phi^n}{\sqrt5}\) до ближайшего целого и скрещивая пальцы, что знаков хватит.

Так же не секрет, что, не используя floating point, можно обойтись и \(O(\log n)\) с помощью вычисления степени за \(O(\log n)\). Но всё равно опишу это.

Читать далее Фибоначчи, Haskell, O(log n)