07.03.2017 15:14
WieRuindl 61 12800 Источник

Доброго времени, Хабр!

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

Начну с небольшой вводной. Будучи студентом 4-го, на тот момент, курса бакалавриата, я изучал курс «Компьютерная графика». Много там было разных интересных (и не очень) заданий, но одно прямо особо запало мне в душу: интерполяция кубическими сплайнами с заданными первыми производными на концах интервала. Пользователь должен был задавать значения первых производных, а программа — считать и выводить на экран интерполяционную кривую. Особенность и основная сложность задания заключена в том, что задаются именно первые производные, а не вторые, как в классической постановке сплайн-интерполяции.
Как я ее решал, и к чему оно в итоге пришло, я как раз и изложу в этой статье. И да, если по описанию задачи вы не поняли ни в чем ее смысл, ни в чем сложность, не переживайте, все это я также постараюсь раскрыть. Итак, поехали.

А, нет, погодите один момент. Вот вам два числовых ряда:
a) 2, 4, 6, 8, ?
b) 1, 3, ?, 7, 9

Какие числа должны стоять на месте вопросов и почему? Вы действительно уверены в своем ответе?

Интерполяция


Интерполяция, интерполирование (от лат. inter-polis – «разглаженный, подновлённый, обновлённый; преобразованный») – в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. (с) Википедия

Поясню на примерах. Существуют задачи, когда нам требуется узнать, условно, «закон распределения» (взял в кавычки, так как это, вообще говоря, термин из другой области математики) некого параметра по нескольким известным его значениям. Чаще всего речь идет об изменении некого параметра во времени: координаты движущегося тела, температуры объекта, колебания курса валюты, etc. При этом в силу каких-либо обстоятельств у нас не было возможности наблюдать за этим параметром непрерывно, мы могли узнавать его значения лишь в какие-то отдельные моменты времени. Исходными данными в таком случае у нас является множество точек вида value(time), а целью задачи – восстановить кривую, проходящую через эти точки и непрерывно описывающую изменение этого параметра.

Следует понимать, что невозможность постоянного наблюдения за соответствующим параметром – это обычно какого-либо рода технологическое ограничение. С развитием техники таких ситуаций становится все меньше и меньше. Из современных задач такого плана – траектория движения, например, марсохода. Поддерживать непрерывный сеанс связи (пока что) все еще не представляется возможным, а контролировать его перемещение и рисовать красивые траектории хочется. Получается, что конкретные координаты можно узнать только в те моменты, когда связь все-таки налажена, а траекторию целиком приходится восстанавливать по полученным таким образом время от времени точкам.
Другой вариант применения интерполяции. Некоторые современные телевизоры показывают изображение с частотой обновления картинки до >=1000Гц (хотя это все еще запредельные значения). Большинство телевизоров так не умеет, но даже так многие отображают картинку на частоте 100Гц — такая величина уже вполне себе классика. А если верить википедии, то в кинематографе «частота 24 кадра в секунду является общемировым стандартом». Для того, чтобы превратить 24 кадра в секунду исходного видеопотока в 100 кадров в секунду результата, телевизор использует интерполяцию. А именно какие-нибудь алгоритмы в стиле «взять два соседних кадра 1 и 2, посчитать разницу между ними и сформировать из нее 3 дополнительных кадра, которые надо впихнуть между теми двумя изначальными» -> получаются кадры 1, 1_1, 1_2, 1_3, 2

Для дальнейших рассуждений возьмем более простой пример. Представим себе, например, лабораторную работу по географии в каком-нибудь 6-ом классе (кстати, у меня когда-то и правда была такая). Необходимо каждые 3 часа измерять температуру воздуха и записывать данные, а потом сдать учителю график изменения температуры от времени суток. Допустим, по результатам измерений у нас получилась вот такая табличка (данные придуманы случайным образом и никак не претендуют на какую-либо правдоподобность):



Отобразим полученные данные на графике:



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

Количество условий и степень интерполирующего полинома


Можем ли мы вообще гарантировать, что такая функция, которая соединяет все заданные точки, вообще существует?

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





Однако есть и способ задать интерполяционную кривую однозначно. В самом классическом случае, в качестве интерполяционной кривой берут полином:

$P_n(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$

Для того, чтобы провести через имеющиеся точки такой полином единственным образом, необходимо и достаточно, чтобы степень полинома была на 1 меньше, чем количество условий (я специально выделил это слово, потому что в конце этого раздела я вернусь к этой формулировке). Пока что, простоты ради, условием будут являться координаты точки. Говоря человеческим языком, через 2 точки однозначным образом можно провести прямую (полином 1-ой степени), через 3 точки – параболу (полином 2-ой степени) и т.д.

Возвращаясь к нашей задаче с температурой – в ней мы определили 6 точек, значит, для того, чтобы провести полином единственным образом, он должен быть 5-ой степени



Интерполирующий полином тогда будет выглядеть так:

$inline$-\frac{x^5}{14580}+\frac{13x^4}{1944}-\frac{41x^3}{162}+\frac{983x^2}{216}-\frac{2273x}{60}+117$inline$

А сейчас следует сделать важное замечание и пояснить, что я имел ввиду под «условием». Полином можно задать не только координатами точек, через которые он проходит, условиями могут быть любые параметры этого полинома. В простейшем случае это действительно координаты точек. Но в качестве условия можно взять, например, первую производную этого полинома в какой-либо из точек. Вторую производную. Третью производную. В общем, любую возможную производную в любой из точек, в которой этот полином существует. Поясню на примере:
Прямую можно задать однозначно, как я уже говорил, двумя точками:



Ту же прямую, с другой стороны, можно определить координатой одной точки и углом наклона альфа к горизонтали:



С полиномами более высоких степеней можно использовать и более сложные условия (вторая производная, третья производная, etc.), и каждый такой параметр будет идти в общий счет количества условий, которые однозначным образом определят этот полином. Чтобы не быть голословным, вот еще пример:

Пусть нам заданы такие три условия:

$y(0)=1, y'(0)=1, y''(0)=2$

Условий три, значит, мы хотим получить полином второй степени:

$y(x)=ax^2+bx+c$

Подставляем $x=0 \to y(x=0)=c \to c=1$

Считаем первую производную и считаем $y'(x)=2ax+b \to [x=0] \to y'(x=0)=b \to b=1$

Считаем вторую производную и считаем $y''(x)=2a \to [x=0] \to y''(x=0)=2a \to a=1$

Отсюда получаем, что наш полином выглядит так:

$y(x)=x^2+x+1$

Интерполяция кубическими сплайнами


Вот, по тиху, мы и подбираемся к моей задаче. Полиномиальная интерполяция – не единственно возможный способ интерполяции. Среди всех прочих методов существует метод интерполяции кубическими сплайнами.

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

Каждый из этих полиномов – это полином третьей степени (строго говоря, степени не выше третьей, так как на каком-то из интервалов интерполирующая кривая может становиться квадратичной параболой или даже линейной функцией, но в общем случае это все-таки полином именно третьей степени). Записывая вышесказанное формульно, получим что все наши точки будут соединены некоей кривой $S=\{S_1,S_2,S_3,S_4,S_5\}$, где каждый $S_i$ – это полином третьей степени, а именно:

$S_i(x)=ax^3+bx^2+cx+d$

Возвращаясь к рассказанному в предыдущем пункте, для того, чтобы однозначно задать один полином 3-ей степени, необходимо 4 условия. В этой задаче у нас 5 полиномов, то есть, чтобы задать их все, нам нужно суммарно 5•4=20 условий. И вот как они получаются:

1) Первый полином определен на первой и второй точках – это два условия. Второй полином определен на второй и третьей точках – еще два условия. Третий полином, четвертый, пятый – каждый из них определен на 2-х точках – суммарно это дает 10 условий.

2) Для каждой промежуточной точки из множества (а это 4 точки с временами 12:00, 15:00, 18:00, 21:00) должно выполняться условие, что первые и вторые производные для левого и правого полиномов должны совпадать. Формульно:

$S_{1}^{'}(x=12:00)=S_{2}^{'}(x=12:00)$

$S_{1}^{''}(x=12:00)=S_{2}^{''}(x=12:00)$

$etc.$

По два таких условия на каждую из промежуточных точек дает еще 8 условий. Следует добавить, что мы задаем только сам факт равенства, а какое конкретно значение они при этом принимают – это совершенно иная задача и считается она довольно сложно.

3) Остаются два условия, которые пока еще не определены. Это так называемые «граничные условия», от задания которых и зависит, какой именно сплайн получится. Обычно задают вторые производные на концах интервала равными 0:

$S_{1}^{''}(x=9:00)=0$

$S_{5}^{''}(x=21:00)=0$

Если сделать так, то мы получим так называемый «естественный сплайн». Для вычисления таких сплайнов написано уже огромное количество библиотек, бери и используй любую.

Отличие моего задания от классической постановки задачи, мои размышления над заданием и само решение


И вот мы подошли к условию моей задачи. Преподаватель придумал такое задание, что задаваться должны первые производные $S_{1}^{'}(x_1)=k_1$ и $S_{n-1}^{'}(x_n)=k_2$ на левом и правом концах интервала, а программа должна считать интерполирующую кривую. А для такого требования готовых алгоритмов я не нашел…
Я, разумеется, не стану описывать весь твой «творческий» путь от момента, когда я услышал задание, до того, как я его сдал. Расскажу лишь саму идею и покажу ее реализацию.

Сложность задания состоит в том, что, задавая первые производные на концах интервала, да, мы задаем этот сплайн. Теоретически. А вот посчитать его на практике – задача довольно сложная и совершенно неочевидная (желающие могут посмотреть код нахождения естественного сплайна на Вики – ru.wikipedia.org/wiki/Кубический_сплайн – и попробовать его понять хотя бы). Разумеется, я совершенно не хотел провести кучу времени, закопавшись в матан и пытаясь вывести нужные мне формулы. Я хотел более простое и элегантное решение. И я его нашел.
Рассмотрим наш сплайн и возьмем первый из его интервалов. На этом интервале уже заданы 3 условия:

$S_1(x_1 )=y_1$

$S_1(x_2 )=y_2$

$S_{1}^{'}(x_1 )=k_1$ — задается пользователем

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

$S_{1}^{''}(x_1)=0$ — ничем не обоснованное предположение

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

$S_2(x_2)=y_2$

$S_2(x_3)=y_3$

$S_{2}^{'}(x_2)=S_{1}^{'}(x_2)$ — вычисляется из $S_1$

$S_{2}^{''}(x_2)=S_{1}^{''}(x_2)$ — вычисляется из $S_1$

Аналогично мы считаем третий полином, четвертый, пятый и так далее, сколько бы их ни было. То есть, по факту, воссоздаем весь сплайн. Но поскольку мы взяли $S_{1}^{''}(x_1)=0$ совершенно случайным образом, это приведет к тому, что производная $k_2$, заданная пользователем на правом конце сплайна, не будет совпадать с производной $S_{n-1}^{'}(x_n)$, которая получилась у нас в ходе таких вычислений. Но получается, что значение производной $S_{n-1}^{'}(x_n)$ на правом конце сплайна – это функция, зависящая от значения второй производной $S_{1}^{''}(x_1 )$ на левом конце:

$S_{n-1}^{'}(x_n)=f(S_{1}^{''}(x_1))$

А поскольку такой сплайн, который бы удовлетворял заданным условиям, гарантированно существует, и существует в единственном экземпляре, это значит, что мы можем рассмотреть разность:

$delta=S_{n-1}^{'}(x_n)-k_2$

и попытаться найти такое значение $S_{1}^{''}(x_1)$, при котором $delta$ обращалась бы в 0 – и это будет тем самым правильным значением $S_{1}^{''}(x_1)$, которое строит искомый пользователем сплайн:



Самое замечательное в моей идее то, что эта зависимость оказалась линейной (вне зависимости от количества точек, через которые мы проводим сплайн. Этот факт доказан теоретическими подсчетами), а значит можно случайным образом взять любые два начальные значения $S_{11}^{''}(x_1)$ и $S_{12}^{''}(x_1)$, посчитать $delta_1$ и $delta_2$, и сразу же посчитать то самое верное значение, которое построит нам искомый сплайн:

$S_{REAL}^{''}(x_1)=-delta_2\frac{S_{12}^{''}(x_1)-S_{11}^{''}(x_1)}{delta_2-delta_1}$

Итого, мы гарантированно находим искомый сплайн за 3 прогонки таких вычислений.

Немного кода и скриншотов программы


class CPoint
{
    public int X { get; }
    public int Y { get; }

    public double Df { get; set; }
    public double Ddf { get; set; }

    public CPoint(int x, int y)
    {
        X = x;
        Y = y;
    }
}



class CSplineSubinterval
{
    public double A { get; }
    public double B { get; }
    public double C { get; }
    public double D { get; }

    private readonly CPoint _p1;
    private readonly CPoint _p2;

    public CSplineSubinterval(CPoint p1, CPoint p2, double df, double ddf)
    {
        _p1 = p1;
        _p2 = p2;

        B = ddf;
        C = df;
        D = p1.Y;
        A = (_p2.Y - B * Math.Pow(_p2.X - _p1.X, 2) - C * (_p2.X - _p1.X) - D) / Math.Pow(_p2.X - _p1.X, 3);
    }

    public double F(int x)
    {
        return A * Math.Pow(x - _p1.X, 3) + B * Math.Pow(x - _p1.X, 2) + C * (x - _p1.X) + D;
    }

    public double Df(int x)
    {
        return 3 * A * Math.Pow(x - _p1.X, 2) + 2 * B * (x - _p1.X) + C;
    }

    public double Ddf(int x)
    {
        return 6 * A * (x - _p1.X) + 2 * B;
    }
}



class CSpline
{
    private readonly CPoint[] _points;
    private readonly CSplineSubinterval[] _splines;

    public double Df1
    {
        get { return _points[0].Df; }
        set { _points[0].Df = value; }
    }
    public double Ddf1
    {
        get { return _points[0].Ddf; }
        set { _points[0].Ddf = value; }
    }
    public double Dfn
    {
        get { return _points[_points.Length - 1].Df; }
        set { _points[_points.Length - 1].Df = value; }
    }
    public double Ddfn
    {
        get { return _points[_points.Length - 1].Ddf; }
        set { _points[_points.Length - 1].Ddf = value; }
    }

    public CSpline(CPoint[] points)
    {
        _points = points;
        _splines = new CSplineSubinterval[points.Length - 1];
    }

    public void GenerateSplines()
    {
        const double x1 = 0;
        var y1 = BuildSplines(x1);
        const double x2 = 10;
        var y2 = BuildSplines(x2);

        _points[0].Ddf = -y1 * (x2 - x1) / (y2 - y1);

        BuildSplines(_points[0].Ddf);

        _points[_points.Length - 1].Ddf = _splines[_splines.Length - 1].Ddf(_points[_points.Length - 1].X);
    }

    private double BuildSplines(double ddf1)
    {
        double df = _points[0].Df, ddf = ddf1;
        for (var i = 0; i < _splines.Length; i++)
        {
            _splines[i] = new CSplineSubinterval(_points[i], _points[i + 1], df, ddf);

            df = _splines[i].Df(_points[i + 1].X);
            ddf = _splines[i].Ddf(_points[i + 1].X);

            if (i < _splines.Length - 1)
            {
                _points[i + 1].Df = df;
                _points[i + 1].Ddf = ddf;
            }
        }
        return df - Dfn;
    }
}






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

Достоинства и недостатки алгоритма


Признаюсь честно, я не проводил сколь-либо серьезного анализа. По-хорошему стоило бы написать тесты, проверить, как оно работает в разных условиях (мало/много точек интерполяции, равное/произвольное между точками, линейные/квадратные/кубические/тригонометрические/etc. функции и так далее), но я этого не сделал, простите :)

Навскидку можно сказать, что сложность алгоритма — O(N), так как, как я уже говорил, вне зависимости от количества точек, достаточно двух прогонов вычислений, чтобы получить правильное значение второй производной на левом конце интервала, и еще одного, чтобы построить сплайн.

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

Так а в чем провинились тесты IQ?


В самом начале статьи я написал два числовых ряда и попросил их продолжить. Это довольно частый вопрос во всяких IQ тестах. В принципе, вопрос как вопрос, но если копнуть чуть глубже, окажется, что он довольно бредовый, потому что при некотором желании можно доказать, что «правильного» ответа на него не имеется.

Рассмотрим для начала ряд «2, 4, 6, 8, ?»
Представим себе этот числовой ряд как множество пар значений ${x_i,y_i}$:



, где в качестве $y_i$ мы берем само число, а в качестве $x_i $– порядковый номер этого числа. Какое значение должно быть на месте $y_5$?

Мысль, к которой я стараюсь плавно подвести – это то, что мы можем подставить абсолютно любое значение. Ведь что по факту проверяют такие задачи? Способность человека найти некое правило, которое связывает все имеющиеся числа, и по этому правилу вывести следующее число в последовательности. Говоря научным языком, здесь стоит задача экстраполяции (задача интерполяции состоит в том, чтобы найти кривую, проходящую через все точки внутри некоторого интервала, а задача экстраполяции – продолжить эту кривую за пределы интервала, «предсказав» таким образом поведение кривой в дальнейшем). Так вот, экстраполяция не имеет однозначного решения. Вообще. Никогда. Если бы было иначе, люди давным-давно бы предсказали прогноз погоды на всю историю человечества вперед, а скачки курса рубля никогда не были бы неожиданностью.

Разумеется, предполагается, что верный ответ в этой задаче все-таки есть и он равен 10, и тогда «закон», связывающий все эти числа, – это $y=2x_i$



Однако возьмем любое другое значение – и мы также сможем найти закон, который бы обосновывал именно его:

$y_5=12 \to y=\frac{x^4}{12}-\frac{5x^3}{6}+\frac{35x^2}{12}-\frac{13x}{6}+2$


$y_5=16 \to y=\frac{x^4}{4}-\frac{5x^3}{2}+\frac{35x^2}{4}-\frac{21x}{2}+6$


$y_5=-1 \to y=-\frac{11x^4}{24}+\frac{55x^3}{12}-\frac{385x^2}{24}+\frac{299x}{12}-11$


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



Я считаю, верный ответ $y_3=1$. Кто сможет оспорить? :)

$y=-x^4+12x^3-49x^2+80x-41$


Git-репозиторий


В прошлый раз меня ругали за то, что я выложил проект в виде архива в облаке, а не в виде кодов в репозиторий, поэтому в этот раз я исправляю эту свою ошибку: github.com/WieRuindl/Splines
Поделиться с друзьями
-->

Комментарии (61)


  1. habradante
    07.03.2017 18:34
    #10107676
    +7

    Тесты IQ проверяют может ли человек найти решение исходя из имеющихся условий, т.е. способен ли он анализировать и делать выводы. Еще раз, анализировать и делать выводы, а не находить математическое оправдание случайно возникшей в мозгу цифре.
    А у вас тут попытка притянуть ответ к задаче. IQ тесты это не набор математических задач.


    1. lorc
      07.03.2017 18:53
      #10107738
      +11

      Можно зайти на https://oeis.org/, ввести свою последовательность и получить пяток разных правил, которые её описывают.
      И ладно бы задачи были уровня 2,4,6,8. Тут всё очевидно. А ведь бывают такие последовательности, для которых находишь несколько правил и потом просто пытаешься угадать, какое же из них задумал составитель теста. У вас такого никогда не случалось?


      1. PretorDH
        07.03.2017 20:23
        #10107898
        +1

        Я заканчивал Матфак… потому любой IQ тест на последовательности для меня, это набор множеств из множества возможных решений… среди которых надо угадать СТАНДАРТНОЕ загаданное. :) И самое интересное, что ответ на вопрос в IQ не всегда сводится даже к «математически простому» решению.

        Что само по себе бредово, ибо человек мыслящий стандартно никогда не взлетит над общей массой. А значит IQ это тест на посредственность.


        1. habradante
          07.03.2017 21:47
          #10107998

          Потому что тест на IQ, это не математическая задачка. Я понимаю, что ваш «молоток» математика и все задачки это гвозди, но смысл как раз в том, что эти тесты не проверка на знания математики.
          Нестандартность она разная бывает, что для одних гениальность, для других — идиотизм. А действительно умные и нестандартные люди заметны несмотря на результаты тестов. Или у вас по месту жительства набравших меньше всего баллов со скалы скидывают? :)


        1. 3aicheg
          08.03.2017 08:35
          #10108350

          Вам просто обидно, что результаты низкие.


          1. bopoh13
            10.03.2017 11:00
            #10111264

            Наличие аналитического аппарата и опыта решения широкого круга задач перевешивают любые доводы в необходимости получения абстрактных баллов за решение линейных алгоритмов индивидуумов неопределённого уровня развития, которые часто именуются «задачами на логику».


      1. habradante
        07.03.2017 21:41
        #10107992
        +1

        Нет, у меня такого не случалось. Но если бы IQ тесты были бы заточены на математику, то все условные «гуманитарии» были бы, по результатам тестов «дураками», а это не так. Более того, есть два вида IQ тестов, на врожденный интеллект и приобретенный. И вот как раз в тестах на приобретенный интеллект, составители этих тестов, пытаются изголяться кто во что горазд. Отсюда и претензии.


        1. napa3um
          07.03.2017 23:57
          #10108140

          Все IQ-тесты нацелены на психометрический интеллект, который концептуально расположен примерно посередине между биологическим (врождённым) и социальным (приобретённым), при этом степень «реальной» генетической детерминации интеллекта в тестах IQ не выражается в результатах теста. И это дефинитивно, просто по определению Айзенка, автора концепции IQ, а не объективно, как если бы интеллектом было некое самостоятельное и объективно существующее в отрыве от топологии генетической и социальной динамики явление.


      1. MegaVaD
        08.03.2017 13:17
        #10108604
        +1

        С номерами парковочных мест не проканало :)


      1. DrLivesey
        09.03.2017 10:48
        #10109706

        C последовательностью случайных чисел https://oeis.org/ не справились… Так же как и с (5,57,6,67,8,87,9)...


  1. vconst
    07.03.2017 18:41
    #10107702
    +20

    Не совсем в тему, просто вспомнилось.

    — Очень хорошо, — кивнул мальчик, — вытащи бумажку и посмотри, так ли это.

    Гермиона извлекла листочек из кармана и развернула его.

    «Три действительных числа в порядке возрастания, от меньшего к большему.»

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


    1. Nordicx86
      09.03.2017 10:50
      #10109716

      всетаки лучше указать источник — Гарри Поттер и Методы Рационального Мышления


      1. vconst
        09.03.2017 11:06
        #10109750

        В данном случае — не обязательно, количество плюсов говорит о том, что источник тут хорошо известен :)
        И если уж давать ссылки, то на оригинал: Harry Potter and the Methods of Rationality и перевод: Гарри Поттер и методы рационального мышления.
        (Блин… Снова с трудом сдерживаюсь, что бы не перечитать ее в четвертый раз.)


  1. Zenitchik
    07.03.2017 18:55
    #10107746
    +2

    По умолчанию полагается, что нужно найти многочлен наименьшей возможной степени.


    1. janatem
      07.03.2017 19:29
      #10107794
      +4

      Идея здравая, но не универсальная. Например, довольно типичный вариант:


      1, 2, ?, 8, 16


      (Напомню, экспонента довольно плохо приближается многочленом.)


      Я некогда размышлял над корректностью IQ тестов и нащупал универсальное решение. А именно, пусть изначально будет задан язык описания правила (алгоритма). Тогда легко дать определение того, что является правильным ответом на тест — среди всех возможных правил, удовлетворяющих заданию, нужно найти самое короткое. Если повезет, то такое правило будет единственным. Ну или хотя бы все кратчайшие правила будут давать один и тот же ответ. Тогда этот ответ объявляем решением задания, а само задание называем корректным.


      Например, в качестве языка можно выбрать язык формул, содержащий только элементарные функции, скобки, одну переменную (номер ячейки) и числа в десятичной системе. Для первого примера из статьи очевидной формулой для правильного ответа является "2*x", хотя придется повозиться, чтобы доказать, что она самая короткая.


      1. Zibx
        07.03.2017 20:02
        #10107868

        Это простые случаи. Ряды могут оказаться не совсем про чистую математику. 11, 22, ?, 48


        1. Zenitchik
          07.03.2017 20:11
          #10107880

          Если это о форматах, то список сильно неполный.


        1. janatem
          07.03.2017 23:46
          #10108132

          Вопрос к тому, что язык формул слишком беден? Конечно. На практике нужно подобрать язык побогаче, например, полноценный язык программирования.


        1. Andy_U
          08.03.2017 13:17
          #10108602
          +1

          Стоимость мороженого в СССР?


        1. Alexeyslav
          09.03.2017 14:17
          #10110052

          сразу в голову пришло число 24, прежде чем уловил закономерность…


      1. Uranix
        07.03.2017 20:19
        #10107890
        +1

        Звучит как дополнение с минимальной колмогоровской сложностью.


        1. PretorDH
          07.03.2017 20:40
          #10107926

          Невычислимость колмогоровской сложности[править | править вики-текст]
          Первое следствие заключается в том, что нет эффективного способа вычисления {\displaystyle K} K.


          1. Uranix
            07.03.2017 21:09
            #10107954

            Именно


        1. janatem
          07.03.2017 23:43
          #10108126

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


          Тогда после сдачи теста испытуемый может ознакомиться с «правильными» ответами и там, где «ошибся», может потребовать апелляции — привести к своему ответу текст правила и сравнить его с авторским. Если его правило не длиннее, то зачет.


  1. Karpion
    07.03.2017 20:09
    #10107876
    +5

    Нильс Бор, "как измерить высоту башни с помощью барометра".


    1. elmigranto
      08.03.2017 13:17
      #10108600
      +1

      Но ведь в вопрос был про барометр, а не про барометр и верёвку. А то так можно сказать что-нибудь в духе «взять книгу с описанием ТТХ башен мира, открыть на странице про нашу, придавить барометром соседние листы, чтобы книга не закрывалась; посмотреть высоту.»


  1. zagayevskiy
    07.03.2017 20:16
    #10107886

    В прошлый раз меня ругали за то, что я выложил проект в виде архива в облаке, а не в виде кодов в репозиторий, поэтому в этот раз я исправляю эту свою ошибку: github.com/WieRuindl/Splines

    Тем не менее, гитом вы пользоваться толком не научились. Это же замечательная технология, пользуйтесь!


    1. WieRuindl
      08.03.2017 22:00
      #10109222

      А в чем конкретно моя оплошность заключается в этот раз?


      1. zagayevskiy
        09.03.2017 00:20
        #10109344

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


        1. WieRuindl
          09.03.2017 01:11
          #10109372

          Окей, то есть по существу нареканий нет. Я уж думал все совсем плохо) В остальном же попробую оправдаться.
          Коммит месседж добавлен самой Visual Studio и я даже не заметил, когда именно. На работе я использую java и Idea и привык к тамошнему интерфейсу, а в VS я просто потыкал какие-то кнопочки, убедился, что оно закоммитилось и со спокойной душой выложил статью. Таки да, в данный момент мне было нужно именно хранилище, а не СКВ-функционал.
          А гитом как СКВ я, разумеется, пользуюсь постоянно, хотя, возможно, глубинные «суть и смысл» я все еще и не познал)


          1. DrLivesey
            09.03.2017 11:06
            #10109748

            а в VS я просто потыкал какие-то кнопочки

            Поэтому лично я пользуюсь исключительно коммандной строкой GIT ибо так я имею единый интерфейс на все IDE.


  1. koldyr
    07.03.2017 20:32
    #10107914
    +1

    Продолжаю предлагать к прочтению статью Вадима Шивякова Условие как компромисс.
    Она не имеет отношения к интерполяции, но объясняет почему указанные присутствуют в тестах.


    1. WieRuindl
      08.03.2017 22:05
      #10109230

      Отличная статья, спасибо!
      Мысль, которая там излагается, навеяла воспоминания о вот этом материале: Пол Локхард — Плач математика


  1. Uranix
    07.03.2017 20:39
    #10107924
    +1

    А что сказал ваш преподаватель, увидевший такое решение? Ваше решение достаточно оригинально, пусть даже его сложность в пару раз выше сложности построения такого сплайна «в лоб». Кстати, ваша задача очень красиво решается через эрмитовы элементы, из которых составляется сплайн. Кстати, любые граничные условия довольно легко реализуются для такого сплайна. Если интересно, можете заглянуть в мои слайды.


    1. WieRuindl
      08.03.2017 21:50
      #10109204

      Мой преподаватель — увы — не обратил какого-либо внимания на такое мое решение. Типа «работает и ладно». Я был разочарован, честно говоря, мне, разумеется, хотелось обсудить решение.
      Про эрмитовы элементы ничего не слышал, спасибо за ссылки, я их почитаю.


  1. smind
    07.03.2017 21:16
    #10107964

    Хех, тема моего курсовика 15ти летней давности…


  1. andreishe
    07.03.2017 21:26
    #10107978
    +4

    Некоторые современные телевизоры показывают изображение с частотой обновления картинки до >=1000Гц

    Это ненастоящие, маркетологические, герцы. Пиксели в ЖК матрице не могут с такой скоростью переключаться. А если речь про плазму, то это скорее всего частота ШИМ, которым управляется яркость пикселей.


    1. WieRuindl
      08.03.2017 21:52
      #10109208

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


  1. mickvav
    08.03.2017 00:36
    #10108180
    +5

    Автор все же поленился дойти до библиотеки и взять учебник по вычислительной математике. Почти любой. Кабы не поленился, нашел бы, что реально задача, которую он решал, сводится к системе линейных алгебраических уравнений на трёхдиагональной, кажется, матрице, которая таки да, решается методом прогонки. Очень быстро.
    Вот вам ссылочка, на презентацию, где это разжевано — https://mipt.ru/upload/medialibrary/48a/splines.pdf
    А ещё про всякое готовое по теме — http://srv6.crec.mipt.ru/drupal/?q=node/155


    1. SergeyUstinov
      08.03.2017 14:46
      #10108718

      К сожалению, не у всех хорошие способности к математике и не всем она настолько нравится, чтобы выучить на хорошем уровне.
      Посмотрел ссылку — может, и «разжевано», только мне это не очень заметно. :)))
      А эту статью я понял практически на 100%.


      1. WieRuindl
        08.03.2017 21:57
        #10109214

        Спасибо, мне очень приятно слышать такой комментарий! Я специально старался писать этот материал так, чтобы он был понятен людям, которые не знакомы с этой темой, и я рад, что мне это удалось :)


    1. WieRuindl
      08.03.2017 21:56
      #10109212

      Я, разумеется, начал с учебников по математике и нашел эти трехдиагональные матрицы для естественных сплайнов. Но мне искренне не хотелось вдаваться в такое решение и адаптировать его к моему случаю, оно мне как-то сразу не понравилось. Плюс мне всегда нравилось придумывать свои собственные алгоритмы, пусть, возможно, и более костыльные, чем общепринятые, но зато свои) Т — творчество.
      С другой стороны, когда речь заходит о матрице, пусть даже большая часть элементов которой равны 0, мы сталкиваемся с вычислительной сложностью O(N^2). Мой алгоритм имеет сложность O(N). Поправьте меня, если я где-то ошибаюсь.


      1. mickvav
        08.03.2017 22:56
        #10109272

        Трёхдиагональная матрица решается методом прогонки, который O(N).


      1. mickvav
        08.03.2017 23:05
        #10109284

        Тут вот какая проблема — вы неявным образом приходите к решению известной задачи, не вдаваясь в работы предшественников и теорию. Что отлично работает, пока вы не упрётесь в задачу, в которой теория таки нужна. А не развив в студенческие годы скилла по чтению статей и проспав нужные лекции — будете потом страдать. Как вы думаете, что лучше — взять с полки готовый инструмент и решить содержательную задачу за 15 минут, или строить велосипед в течение двух вечеров?


        1. WieRuindl
          08.03.2017 23:25
          #10109308

          Зависит от задачи. В свои рабочие часы я не занимаюсь велосипедостроением, потому что там иные приоритеты, но если в свободное от работы время я могу себе это позволить, то почему бы и нет? Брать готовый инструмент — это, разумеется, хороший план с точки зрения эффективности соотношения результат/время, но построение велосипедов как минимум неплохо сказывается на соображалке


        1. WieRuindl
          08.03.2017 23:27
          #10109310

          Математика — это творчество, искусство, а не только лишь инструмент


  1. Skyrocker
    08.03.2017 13:17
    #10108596
    +5

    Извините
    image


    1. WieRuindl
      08.03.2017 21:58
      #10109216

      Я хотел вставить эту картинку себе в статью, но — увы — не сумел ее нагуглить. Спасибо за нее! Она и правда шикарная :)


    1. KvanTTT
      09.03.2017 02:38
      #10109400

      А чему равны последующие члены?


      1. mickvav
        09.03.2017 10:11
        #10109656
        +1

        Там, похоже, что-то удобное перестает сокращаться. У меня maxima для следующего члена выдала —
        17708695183056190642497315530628422295569865119 %pi
        ---------------------------------------------------
        35417390788301195294898352987527510935040000000

        Но сожрала полтора гига рамы, пока считала и нехило так подгрузила машину секунд на 30-40, кажется.


    1. Uranix
      09.03.2017 19:16
      #10110534
      +1

      Разрешите добавить ссылку на статью здесь же — замечательно объясняется причина феномена.


  1. Dim0v
    08.03.2017 13:17
    #10108598

    нужно найти многочлен наименьшей возможной степени.


    То есть на вопрос
    «Продолжите последовательность 2, 4, 8, 16, ?, ?»
    надо отвечать 30, 52?

    Именно эти числа дает полином наименьшей возможной степени:
    x^3/3-x^2+8x/3


  1. amarao
    08.03.2017 14:00
    #10108674

    Главная проблема с тестами на IQ, что они не подразумевают процесса обучения.

    Представьте себе, что у вас такая же задача, но с более сложной последовательностью (например, квадратичная последовательность фибоначчи (следующее число — сумма двух предыдущих, возведённая в квадрат)). Вам дали последовательность в 20 чисел, пропущенное число и возможность пробовать, даже со встроенным калькулятором (интерпретатором любимого языка) снизу, чтобы удобно было. Для предотвращения брутфорса кажая следующая попытка может быть сделана с всё большей задержкой.

    Ведь это уже другого уровня задача. Цель — не «знать» ответ, а найти его. Если последовательность нетривиальная, брутфорс не сработает, а дальше там — чистой воды интеллект, то самое легендарное IQ, которого все хотят.

    Пожалуй, в этой идее что-то есть…


  1. BubaVV
    08.03.2017 14:31
    #10108700
    +1

    Моя любимая картинка на тему
    image


    1. KvanTTT
      09.03.2017 02:40
      #10109402

      Я бы ответил 11 как следующее простое.


      1. WieRuindl
        09.03.2017 02:44
        #10109404

        Неа, не подходит. 1 — не простое число, а 2 зато пропущена


        1. KvanTTT
          09.03.2017 11:19
          #10109760

          Да, действительно, двойку точно нельзя было пропускать. Не надо такими вещами заниматься ночью :)


    1. webserfer
      09.03.2017 12:40
      #10109890

      А разве не 31?


  1. saproman88
    08.03.2017 17:30
    #10108932

    Несколько лет назад приходилось сталкиваться со сплайн-интерполяцией.
    Но мне тогда помогли подсказали что нужно смотреть работы по кубическим-сплайнам автор Снигирев В.Ф., часть работ опубликовано в книге: Конструкция самолетов, под редакцией О.А. Гребенькова, издания 1999 г(именно в этом издании есть глава 11).
    А также есть редкая монография: Снигирев В.Ф. Применение сплайнов для задания обводов ЛА.


  1. IIvana
    12.03.2017 07:11
    #10113182

    У меня был похожий случай. Как-то потребовалось мне решить задачу: задана функция f(x) = kx + b, надо найти ее корень. Поскольку изучать весь этот ваш матан мне, как и автору статьи, не улыбалось (яжпрограммист), я взял готовый математический пакет, который находит корни уравнений. Но потом задача радикально усложнилась — потребовалось находить такие x, при которых значение исходной функции было бы равно не нулю, а заданной константе с! Я не нашел готовых пакетов и библиотек, реализующих данный функционал. Но я придумал гениальный метод — я определяю новую функцию g(x) = f(x) — c и ищу ее корень математическим пакетом! Наверное надо тоже про это статью на Хабре написать. Ну и про тесты на IQ добавить, для объема контента. Как считаете?


  1. dmitry_pavlov
    14.03.2017 13:39
    #10116874

    Синие отрезки могут иметь разную длину, обозначая зону влияния в точке данных. Это будет влиять на форму сплайна. При неравномерно распределенных данных в областях, где точек мало форма кривой интерполируется менее однозначно. Я пробовал моделировать кубическими сплайнами геологические складчатые структуры.