Случайны выбор дневника Раскрыть/свернуть полный список возможностей


Найдено 4086 сообщений
Cообщения с меткой

для начинающих - Самое интересное в блогах

Следующие 30  »
Scally85

Топиарий из кофе и цветов. Мастер класс.

Понедельник, 27 Марта 2017 г. 12:25 (ссылка)
radugamaster.ru/index.php/u...2-13-35-00


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

Комментарии (0)КомментироватьВ цитатник или сообщество
Marsio1968

Топиарий из кофе и цветов. Мастер класс.

Понедельник, 27 Марта 2017 г. 11:03 (ссылка)
radugamaster.ru/index.php/u...2-13-35-00


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

Комментарии (0)КомментироватьВ цитатник или сообщество
assa333

3D Album CS. Создаем альбом.

Суббота, 25 Марта 2017 г. 22:10 (ссылка)

Это цитата сообщения MissKcu Оригинальное сообщение

3D Album CS. Создаем альбом.
















Серия сообщений "Фото-слайд шоу":

Часть 1 - СлайдШоу
Часть 2 - Photo Slideshow Creator 2.55
...
Часть 10 - 3D-Album Commercial Suite 3.30
Часть 11 - 3D-Album
Часть 12 - 3D Album CS. Создаем альбом.
Часть 13 - 3D Album 3.32 Русская версия
Часть 14 - ЛУЧШИЕ СЛАЙД - ШОУ ОНЛАЙН
...
Часть 24 - Kvisoft Flip Book Maker Pro 3.6.5.0 Rus Portable
Часть 25 - Kvisoft FlipBook Maker Pro-создание интерактивных книг и фотоальбомов
Часть 26 - Программа Slideshow Maker. Слайд-шоу


Метки:   Комментарии (4)КомментироватьВ цитатник или сообщество
OlgaShv

Простое плетение браслетиков.Видео.Бисероплетение

Среда, 22 Марта 2017 г. 11:41 (ссылка)






Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
Гелсем

Летний кардиган крючком схема и описание. Связать кардиган коючком | Я Хозяйка

Вторник, 21 Марта 2017 г. 10:47 (ссылка)
yahozayka.com/vyazanie-kryu...yuchkom-2/

Летний кардиган крючком схема и описание. Связать кардиган коючком
Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
Гелсем

Болеро с ананасами крючком. Вязание крючком для начинающих болеро | Я Хозяйка

Среда, 15 Марта 2017 г. 13:10 (ссылка)
yahozayka.com/vyazanie-kryu...yuchkom-2/

Болеро с ананасами крючком. Вязание крючком для начинающих болеро
Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
chaikaya

Мыловарение холодным способом. Для начинающих.

Четверг, 09 Марта 2017 г. 20:20 (ссылка)


Мыловарение холодным способом.



творчество



Как сварить настоящее алеппское мыло: технология и экономика для начинающих мыловаров



от автора



Сегодня, дорогие мои, я предлагаю заняться приготовлением мыла, известного каждому. Это мыло одно из самых популярных и потому самых продаваемых сортов. Рецепт его стал символом Сирии и насчитывает несколько тысяч лет. Мыло это чрезвычайно просто в приготовлении и не имеет себе равных в профилактике и, даже, лечении кожных заболеваний. Оно продается повсеместно и, в то же время, его нигде не сыскать. О нем бесконечно пишут, его восхваляют и превозносят, но никто и никогда не демонстрирует главного – определяющей изюминки его состава. Ибо есть в его составе один компонент, который делает его продуктом «высокой кухни».



 





алеппское мыло




Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
chaikaya

Мыловарение для начинающих.

Среда, 08 Марта 2017 г. 23:11 (ссылка)


Мыло из детского мыла.







Мыло апельсин.






Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Теоретические основы сплайн-интерполяции или почему IQ тесты не имеют решения

Вторник, 07 Марта 2017 г. 18:14 (ссылка)



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



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



Начну с небольшой вводной. Будучи студентом 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
Original source: habrahabr.ru.

https://habrahabr.ru/post/323442/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Решение задач зимнего CrackMe

Четверг, 02 Марта 2017 г. 18:39 (ссылка)

Как известно, важной частью борьбы с киберугрозами является исследование вредоносных файлов, чем у нас занимаются вирусные аналитики — отважные парни (и девушки!) из Anti-Malware Team. На основании своего опыта они регулярно создают специальные тренажеры, CrackMe, которые начинающие аналитики могут использовать для проверки своих знаний.

Не так давно, мы анонсировали конкурс CrackMe, проходивший в рамках event-платформы CoLaboratory. Теперь, когда конкурс завершился и все решения приняты, мы можем рассмотреть задачи подробнее.

image

ВНИМАНИЕ: Если вы не успели поучаствовать в конкурсе, но тем не менее хотите попробовать свои силы — не читайте информацию под катом. Там мы описываем алгоритм решения задания. Скачать свежие задачи CrackMe можно здесь.





Решение CRACKME#1



Итак, зимний CRACKME#1 от Лаборатории Касперского.

При запуске файла нас приветствует вот такое незамысловатое окошко с требованием ввести данные для решения.

image

Требуется ввести e-mail, под которым вы регистрировались на сайте и подобрать для него ключ. При вводе неверного значения окошко ругается – придется решать.

image

Для нашего увлекательного исследования мы будем использовать (барабанная дробь!) всего лишь IDA Pro, вот настолько все просто.

image

В итоге мы видим вполне стандартную картину для оконного приложения. Перед нами фрагмент WinMain, который и делает всю магию. Функция DialogBoxParamW принимает в качестве входных параметров бла-бла-бла. Думаю излишне повторять документацию, поэтому просто переходим на адрес, по которому содержится функция, которая будет что-то делать, если мы нажмем кнопку «Check».

image

Чтобы понять, насколько все просто, посмотрите на рисунок выше, где отображена та самая магическая функция. На самом деле это просто нагромождение кода, который показывает нам сообщение «Serial is invalid», если мы вводим некорректные данные. Изобилие же стандартных названий различных структур, к примеру «ms_exc.registration.TryLevel» наталкивает на мысль, что Crackme написан на C++, именно так с изнанки выглядит конструкция (try-catch) и скорее всего именно обращениями к этой структуре будет окружен код, который производит манипуляции с входными данными.

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

image

Переходим на единственную функцию между обращениями к «ms_exc.registration.TryLevel» и вуаля — мы на главной функции, которая определяет, верно или не верно мы нашли ключ для нашей почты.

image

Для концентрации внимания и красивого отображения вершины графа сгруппированы на рисунке выше, чтобы было видно какая часть за что отвечает. Обычная конструкция if-else. Сосредоточимся на вершине графа «GetText And Check». Единственное, на что мы обратим внимание из этого сгруппированного блока, это вот этот кусочек листинга.

image

Если внимательно посмотреть на команды, которые есть выше, то мы увидим, что полученные поля EMail и Serial сохраняются в памяти. На картинке же выше приведены команды, которые заносят адреса полученных данных в регистры ECX и EDX соответственно. А дальше начинается проверка, собственно, это ее граф и изображен ниже.

image

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

Начинаем просеивать «грунт». Сразу бросается в глаза большое количество команд от адреса 0040DC00 до 0040DC86, которые, на первый взгляд делают что-то математически важное для проверки нашего ключа. Однако, если присмотреться пристальнее, то можно понять, что это пары команд, которые компенсируют действия друг друга. Весь диапазон можно представить, как одну большую nop-команду, пропускаем её. Берем следующий наполненный смыслом модуль. Код, который содержится в этом модуле, не распознался как стандартный, но все операции, проводимые им, просто переводят строки между Wide string в просто string.

image

Для удобства переименуем вызываемые функции, а разбор внутренностей оставим для особенно любознательных читателей. Особое внимание обратим только на функцию с условным названием «Md5». Почему мы так ее назвали? Заглянем внутрь и, чтобы не перегружать статью картинками и объяснениями каждой строчки листинга, посмотрим только на нужный кусок.

image

Код достаточно прямолинеен, поэтому, чтобы понять, что происходит, достаточно просто прочитать названия WinApi функций. На картинке вы видите блок, из которого мы можем определить, ЧТО за алгоритм вообще реализован этой функцией. Порывшись в официальной документации, находим значение 8003h для константы «CALG_MD5». Комментарии излишни.

Обратимся к следующему модулю.

image

Он содержит в себе цикл. Из него видно, что цикл итерирует над последовательностью данных в памяти при помощи двух переменных, значения которых имеют отступ друг от друга в 16 позиций. Над каждым элементом последовательности производится операция XOR с элементом, отстоящим от него на 16 символов. От полученного результата вычисляется MD5 сумма.

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

image

Модуль производит сравнение двух переменных, замусорен командами, в конце сравнивает значения переменной и значение регистра ebx (условие сравнения длин последовательностей?). В итоге производится переход на цикл, который представлен в модуле на картинке ниже. Он на последовательности из 16 символов производит сравнение, увеличивая счетчик на единицу при совпадении и уменьшая на единицу в противном случае. (Это операция сравнения полученного Serial с исходным, который был вычислен и хранился в памяти).

image

После Этого цикла происходит инициализация, и мы видим зеркальный цикл, который начинается не с нуля, а с 16-го символа. Рисунок представлен ниже.

image

После обработки в цикле последовательности, среди замусоренного кода и стандартных процедур, есть модуль, который принимает решение, на основании сравнения двух переменных. Не стоит даже сильно вчитываться в дизассемблированный код. Это сравнение совпадений двух строк Serial и вычисленного значения на основании введенной почты. Рисунок модуля представлен ниже.

image

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

1. получим Md5 сумму от адреса;

2. разделим пополам полученную сумму и произведем операцию xor,

3. снова вычислим Md5 от результата.

В качестве подопытной почты была использована: sam@kakoitodomen.com

В качестве Serial была использована: BB23F6DFA9375ED119237AAC4DE31BCD

Результат на картинке ниже

image

Вот такой простой CRACKME.



Решение CRACKME#2



Во втором крекми нам дан бинарный файл (PE 32-bit). И снова требуется подобрать корректный Serial под EMail.

image

Для начала открываем этот файл в вышеупомянутой IDA. Также полезно при анализе пользоваться Hex-Rays (удобный декомпилятор, который поддерживает множество архитектур).



Мы можем найти место, в котором происходит проверка серийника.

image

По адресу 40E960 (не учитывая ASLR) находится проверочная функция.

image



В начале можно увидеть, что e-mail сжимается до размера 22 байта путём xor всех символов, чьи позиции равны по модулю 22. В случае нехватки расширяется нулевыми байтами.

image

Затем проверяется, что серийник находится в шестнадцатеричной системе счисления, он переводится в байты и над ним также проводится операция xor с адресом почты.

image



image



image

Дальше происходит проверка, что получившаяся xor-сумма удовлетворяет СЛАУ, в которой используются ASCII коды символов некоторого внутреннего секретного значения.

image

image



Уравнений в СЛАУ много, поэтому необходимо рассмотреть некоторый способ автоматического решения. Для этого можно воспользоваться системой компьютерной математики (например NumPy), либо так называемым SMT-решателем z3, который мгновенно находит решение. Также СЛАУ можно попробовать решать с помощью фреймворка angr, который уже содержит внутри себя z3.

В авторском решении используется z3. Но не стоит забывать, что любую СЛАУ можно решить на бумажке методом Гаусса, надо просто постараться.

Решив СЛАУ, мы получаем секретное значение «KL_F4n7a5tiC_chAl1eN63», которому и должен быть равен данный xor всего со всем.

Пример:

EMail: sample@kaspersky.com

Serial: 382d3236580b770a540719262d10033842520a233633

image



Ну вот и всё. Мы с вами разобрали две из трех CrackMe зимнего сезона от «Лаборатории Касперского». Но всех секретов раскрывать не будем. Вполне вероятно что третьий CrackMe мы будем использовать в качестве тестовой задачи и дальше. Так что, если захотите сделать карьеру вирусного аналитика — попробуйте решить его самостоятельно.

Больше CrackMe, вечерних встреч, хакатонов и других событий уже скоро на нашем сайте. Присоединяйтесь!
Original source: habrahabr.ru (comments, light).

https://habrahabr.ru/post/323116/

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество

Следующие 30  »

<для начинающих - Самое интересное в блогах

Страницы: [1] 2 3 ..
.. 10

LiveInternet.Ru Ссылки: на главную|почта|знакомства|одноклассники|фото|открытки|тесты|чат
О проекте: помощь|контакты|разместить рекламу|версия для pda