C++
Algorithms
Mathematics
Programming
Game development
Comments 58
+1
вообще не требует никаких знаний математики

Эм… ну да, фигня, начальная школа.
Как же все относительно в мире.
+1
Про начальную я не говорил; но вообще решение систем линейных уравнений — седьмой класс школы. Производные — десятый. Программирование на таком уровне — десятый. Что я упустил?
-4
Статья безусловно классная. Формулы страшные. Ну вот чисто внешне пугают. Как у Хоккинга: «каждая новая формула сокращает число читателей вдвое».

Я довольно востребованный прикладной программист с большим опытом. Но без образования и знаний математики. И с этой точки зрения статья обманула мои ожидания фразой «вообще не требует знаний».

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

На всю статью вообще одна формула:
Скрытый текст


Я убеждён, что для того, чтобы понять, что происходит в математике, равно как и в программировании, нужно внимательно читать текст не один раз, и запускать весь код, изменяя входные параметры. Именно поэтому я не просто развожу руками в воздухе, но даю вполне конкретные куски исполняемого кода и сопровождающие картинки.
+2
Математические формулы на первый взгляд совершенно непонятны. Трюк в том чтобы читать медленно, по слогам. Сначало смотрим, что означает каждая буква, находим эти буквы в формуле, найдя все смыслы всех букв и их места в формуле быстро проходимся еще разок отмечая все буквы и смыслы. Затем начинаем смотреть на преобразования, многократно перечитывая и сверяя куда каждая буква пошла. И так в конце концов дойдем до конца блока формул. Это займет значительно больше времени чем обычное чтение.
На лирическое отступление из этой статьи, нужно потратить минут 5.
-4
Программист не знающий самой элементарной математики скорее всего говнокодер (да, говнокодеры тоже могут востребованы), а не программист.
+1

Подавляющее число задач не связаны с математикой вообще никак. CRUD и бизнес-логика редко требуют сложных вычислений. А вот знания 100500 библиотек на все случаи жизни, умение писать простой и понятный код (поддерживаемый), умение расставлять приоритеты, изучать постоянно что-то новое — нужно всегда.
Программисты решают задачи бизнеса. Если задача решается с приемлемым качеством и в приемлемый срок — он профи.
Если появится проблема, требующая знаний — получить эти знания или нанять человека, специализирующегося на них — не проблема.
Ставить ярлык "говнокодер" я бы не стал, если человек не умеет в диффуры.

0
Нанять человека — это не уже не программист, а к управляющий.

Скрытый текст
На всякий случай: я понимаю, что вы отвечаете не на мой комментарий, но лично я никаких ярлыков не вешал, иначе бы не писал статьи :)
0
При чем здесь диффуры? Есть масса других, более универсальных вещей, которые называются «дискретная математика». Про теорию алгоритмов слышали? Сбалансированные деревья, алгоритмы на графах и все такое? Да, в чистом виде сбалансированные деревья реализовывать в «бизнес-логике» приложения надо нечасто, да и с графами работать тоже. А вот в менее явной форме вполне. Кто сказал что горе-программист, для которого система линейных уравнений (не говоря уже про логарифмы и прочие элементарные вещи начальной школы) это непостижимо сложная вещь, может написать простой, понятный и эффективнй код? Такой же программист-неуч? А может быть, на самом деле можно написать намного более эффективный код, практически не теряя в его читабельности?

И я все-таки не утверждаю что каждый программист-неуч обязательно говнокодер. Хороший программист не обязан обладать знаниями Д. Кнута чтобы быть действительно хорошим программистом. Скорее всего, примеры таких программистов все же есть. Но, повторяю, чтобы утверждать что код, написанный неучем, действительно хороший, нужно какая-то точка отсчета. И желательно, чтобы оценку качества проводили не такие же неучи.
0
Частная задача — 1-2-3 неизвестных — 7-8 класс.
Общая задача — N неизвестных чуть выше уровень…
+1
Покажете мне восьмиклассника, который умеет решать систему с тремя неизвестными, но не сможет решить с четырьмя?
+1
Сын мой :)

Они решают 2-3 неизвестных, без обобщений на n неизвестных. Так прописано в библии по подготовке к ЕГЭ. Им больше 3 и не надо…
Они в ступор встают, когда им пишешь что-то типа «а в степени n, где n=3»…
0
А вы можете попробовать ему дать следующую систему уравнений? Что он скажет?
{x1-x2 = 0
x2-x3 = 0
x3-x4 = 0
x4 = 2
0
Ну я ему потихоньку мозги вставляю. Сомневаюсь, что учителя это делают и остальные родители.
+1
как отец шестиклассницы скажу, что она решила эту систему «обученным в школе» способом (т.е. без обобщений) по цепочке снизу вверх.
0
Пример вызова реализации МНК в пакете Maxima:

/* Задаём матрицу с данными */
M:matrix([-1, -0.5], [0, 0], [1, 0.5], [2, 0.9], [3, 1]);

/* Модель: U - переменная, A, B, C - неизвестные параметры */
f(U,A,B,C):=A*exp(B*U)+C*U^2;

/* Загружаем модуль пакета для МНК */
load(lsquares);

/* Вызываем реализацию МНК в пакете */
klist:lsquares_estimates(M, [U,I], I=f(U,A,B,C), [A,B,C]);

/* Подставляем найденные параметры в модель */
I(U):=float(ev(f(U,A,B,C), klist));

/* Определяем коэффициент детерминации R^2. Сначала найдём среднее значение */
mny:0;
for i:1 thru length(M) step 1 do mny:mny+M[i,2];
mny:mny/length(M);

/* Находим суммы квадратов */
sum1:0;
sum2:0;
for i:1 thru length(M) step 1 do (sum1:sum1+(M[i,2]-I(M[i,1]))^2, sum2:sum2+(M[i,2]-mny)^2);

/* Вычисляем до целой части коэффициент R^2 и выводим его */
Rsq:round((1-sum1/sum2)*100)$
printf(true, "R^2 = ~d%", Rsq)$

/* Сформируем из матрицы M список точек */
plist:create_list(M[k], k, 1, length(M));

/* Строим график */
plot2d([['discrete,plist], I(U)], [U, -1, 4], [style, [points, 2, 1, 1], lines], [color, red, blue]);

Я не так давно для одной модели использовал в Maxima не lsquares_estimates, а решал экстремальную задачу на минимум суммы квадратов остатков модели (модуль lbfgs — метод Бройдена-Флетчера-Гольдфарба-Шанно). lsquares_estimates умеет определять линейность модели относительно неизвестных параметров. Если линейность имеет место, получаемую нормальную систему линейных уравнений пакет решает аналитически (ответ в обыкновенных дробях выдаёт), иначе вызывает численное решение экстремальной задачи указанным методом. При этом не всегда удачно подбирает начальное приближение к решению. Надо как-нибудь сюда статью об этом написать.
0
Спасибо за пример! Буду им пользоваться в качестве шпаргалки для построения графиков в максиме. Жаль только, что он не имеет прямого отношения к рассмотренным в статье примерам. И скромная просьба прятать впредь длинный код под тег <spoiler>, иначе сильно загромождается страница комментариев. Ещё раз спасибо!
0
Небольшое дополнение. Если пакет обламывается на plot2d в Windows, то, скорее всего, Вы работаете в системе под пользователем, в имени которого есть русские буквы. Дело в том, что пакет пытается создать временный текстовый файл для Gnuplot. Поэтому надо перенаправить директорию для временных файлов в другое место, например, в корень диска d:

maxima_tempdir:"d:\\";

Если экспериментальных данных много, забивать их списком долго (например, переносить из Excel). В Maxima есть возможность чтения данных в матрицу из текстового файла:

M:read_matrix("d:\data.txt");

Файл data.txt выглядит просто (без пустой строки в конце):

Скрытый текст
-1 -0.5
0 0
1 0.5
2 0.9
3 1

Если Maxima не может прочитать существующий файл, то попробуйте в пути к файлу наклонить слэш в другую сторону (как /).

Если встроенный МНК не идёт, то, как я писал, нужно решать задачу на минимум суммы квадратов:

Скрытый текст
/* Формируем выражение для суммы квадратов остатков модели */
delta:0$
for i:1 thru length(M) step 1 do delta:delta+(M[i,2]-f(M[i,1],A,B,C))^2;
s(A,B,C):=''delta$

/* Загружаем модуль пакета для экстремальной задачи на минимум */
load(lbfgs);

/* Ищем минимум ошибки модели */
klist:lbfgs(s(A,B,C),[A,B,C],[1,1,1],1e-6,[1,1]);


Как видно из кода, кое-где вместо ; стоит $, чтобы пакет не дублировал вывод длинных формул при большом объёме экспериментальных данных или длинной формуле для модели.
0
Спасибо за интересную статью! Кажется, потребуется к ней несколько раз вернуться после Википедии, чтобы осознать, что же тут написано по части математики.
0
А что из математики вы не поняли без википедии? Все пассажи про эллиптические дифференциальные уравнения тут, мягко скажем, необязательные. А решение СЛАУ, вроде, должно быть достаточно прозрачным, нет?
+1
Если с математикой постоянно не работаешь, то математический язык очень сложно воспринимать. Могу без проблем преобразовать через матрицы систему координат, но когда лезу в Википедию что-либо подсмотреть, обычно хочется всё переписать с нуля после того, как пойму, что там написано.

Математика без пояснения на бытовых примерах очень сложна для восприятия большинству. И каждый пример должен быть подкреплён практическим использованием. В Вашем случае любопытные примеры получились.
0
В целом, пост понравился, но несколько сбивают с толку резкие перескоки с 3D-сканов на график функции из двух ступенек. Почему бы как-то не свести иллюстративную базу воедино? К примеру, как-то так:
Заголовок спойлера
image
0
Отличный совет. Немного настораживает правая нижняя точка, но это мы починим, выкладывайте код с вождём!
0
Правую нижнюю точку специально зафиксировал (уже отпустил). Ну вроде так:

Заголовок спойлера
import cv2
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

#tracing the chief with OpenCV
im = cv2.imread('lenin_bw.png')
im = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
ret, thresh = cv2.threshold(im, 0, 255, 0)
im2, c, hierarchy = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_TC89_KCOS)
xs, ys = c[0][:, :, 0], c[0][:, :, 1]
xs, ys = [x.transpose()[0].tolist() for x in [xs, ys]]
y_max = max(ys)
ys = [y_max - y for y in ys]

#laplacian smoothing
def smooth_ex1(X):
	return [(m[0] + m[2])/2 for m in zip([X[-1]] + X, X, X[1:] + [X[0]])]

#animated plot of the results
fig, ax = plt.subplots()
ln, = plt.plot(xs, ys, animated = True)
def init():
	plt.axis('equal')
	return ln,
	
def update(frame):
	global xs, ys
	xs = smooth_ex1(xs)
	ys = smooth_ex1(ys)
	ln.set_data(xs + [xs[0]], ys + [ys[0]])
	return ln,

ani = FuncAnimation(fig, update, init_func = init, blit = True)
plt.show()



Профиль первого попавшегося на Яндексе Ильича в профиль, трэйсил контур через OpenCV, к теме не особо относится, но для полноты картины пусть будет:
Заголовок спойлера
image


У кого нет OpenCV — можно выкинуть всё до комментария про laplacian smoothing и вместо этого захардкодить готовый контур:
Заголовок спойлера
xss = [282, 282, 277, 274, 266, 259, 258, 249, 248, 242, 240, 238, 240, 239, 242, 242, 244, 244, 247, 247, 249, 249, 250, 251, 253, 252, 254, 253, 254, 254, 257, 258, 258, 257, 256, 253, 253, 251, 250, 250, 249, 247, 245, 242, 241, 237, 235, 232, 228, 225, 225, 224, 222, 218, 215, 211, 208, 203, 199, 193, 185, 181, 173, 163, 147, 144, 142, 134, 131, 127, 121, 113, 109, 106, 104, 99, 95, 92, 90, 87, 82, 78, 77, 76, 73, 72, 71, 65, 62, 61, 60, 57, 56, 55, 54, 53, 52, 51, 45, 42, 40, 40, 38, 40, 38, 40, 40, 43, 45, 45, 45, 43, 42, 39, 36, 35, 22, 20, 19, 19, 20, 21, 22, 27, 26, 25, 21, 19, 19, 20, 20, 22, 22, 25, 24, 26, 28, 28, 27, 25, 25, 20, 20, 19, 19, 21, 22, 23, 25, 25, 28, 29, 33, 34, 39, 40, 42, 43, 49, 50, 55, 59, 67, 72, 80, 83, 86, 88, 89, 92, 92, 92, 89, 89, 87, 84, 81, 78, 76, 73, 72, 71, 70, 67, 67]
yss = [0, 76, 81, 83, 87, 93, 94, 103, 106, 112, 117, 124, 126, 127, 130, 133, 135, 137, 140, 142, 143, 145, 146, 153, 156, 159, 160, 165, 167, 169, 176, 182, 194, 199, 203, 210, 215, 217, 222, 226, 229, 236, 240, 243, 246, 250, 254, 261, 266, 271, 273, 275, 277, 280, 285, 287, 289, 292, 294, 297, 300, 301, 302, 303, 301, 301, 302, 301, 303, 302, 300, 300, 299, 298, 296, 294, 293, 293, 291, 288, 287, 284, 282, 282, 280, 279, 277, 273, 268, 267, 265, 262, 260, 257, 253, 245, 240, 238, 228, 215, 214, 211, 209, 204, 203, 202, 200, 197, 193, 191, 189, 186, 185, 184, 179, 176, 163, 158, 154, 152, 150, 147, 145, 142, 140, 139, 136, 133, 128, 127, 124, 123, 121, 117, 111, 106, 105, 101, 94, 92, 90, 85, 82, 81, 62, 55, 53, 51, 50, 48, 48, 47, 47, 48, 48, 49, 49, 51, 51, 53, 54, 54, 58, 59, 58, 56, 56, 55, 54, 50, 48, 46, 44, 41, 36, 31, 21, 16, 13, 11, 7, 5, 4, 2, 0]

+1
Реально круто! Это ведь и к любому рельефу и фактуре можно применить!
+3
Статью пробежал минуты за 2, всё это знакомо. Но меня всегда удивляло, как вы на Хабре так непринуждённо классные иллюстрации делаете к постам? Мне кажется, это самое сложное при подготовке материала. У каждого блогера свой велосипед или на Хабре есть какой-то единый крутой инструментарий?
+1
У каждого свой велосипед. На картинки в этой статье я потратил несколько дней.
Спасибо на добром слове, приятно видеть, что они нравятся людям!
+2
То чувство когда увидел пост в твиттере хабра, узнал лицо, понял что будет интересно и зашёл прочитать
0
Решение линейных систем довольно обширная тема. Методы делятся на прямые и итерационные, матрицы на плотные и разреженные. Для вычислительных задач число неизвестных достигает миллионов и есть множество открытых пакетов, которые решают линейные системы с использованием MPI, в разработку которых вложены сотни человеко-лет. Многосеточные методы хорошо работают только для определенных классов матриц.
"… данная процедура сходится к истинному решению" — подобная фраза просто находка для экзаменатора по математике.
0
Какие именно солверы использовать — это отдельная тема, в статью не входящая. А в целом вы что сказать-то хотели? Что я где-то глупость сморозил? Так отлично, поправьте её. Про находки: мне часто доводится экзаменовать студентов, но я не очень понимаю, о каких находках вы говорите.
0
"… данная процедура сходится к истинному решению" — так понятнее?
0
Хорошо. Решение может быть точным, приближенным, единственным, неединственным… Но что такое истинное решение? Это скорее из области веры, чем вычислительной математики.
0
На самом деле это из области метрологии «просочился» термин.
+2
подобная фраза просто находка для экзаменатора по математике

Что-то мне кажется, что это не очень хорошая находка для экзамена. Или хорошая находка для не очень хорошего экзаменатора.

0
Такое понятие вычислительной математики как «истинное решение» мне неизвестно. За всю математику не скажу, возможно, где-то оно и используется. Вот, например, откуда «истинное решение» появилось в данном, написанном вполне профессиональном языком, посте? Для экзаменатора — это возможность построить логическую беседу на тему — что такое решение, чем истинное решение отличается от неистинного решения.
0
Скажите, пожалуйста, что вы думаете по поводу следующей фразы:
1000 явлется решением системы x=0

0
Это утверждение неверно. А вы ожидали что-то другого? :)
0
Так, не сочтите за труд, напишите, пожалуйста, чего вы ожидали.
-1
Вы зря ёрничаете, я, вроде, ничего плохого вам не говорил.
Я лишь хотел вас подвести к мысли о том, что система сама по себе решений не имеет. Решают задачи, а не уравнения. А когда мы договоримся про то, какую задачу решали, тогда можно будет договариваться про прилагательные рядом со словом решение.
+1

Скажите, вы когда-либо преподавали студентам? Вы считаете, что задача экзаменатора это "построить логическую беседу на тему"? Это, возможно, задача при проведении семинара, но вряд ли при проведении экзамена.

0
Задача экзамена выяснить какими знаниями обладает студент и как умеет пользоваться ими: решать задачи, объяснять решения и свои утверждения. Выясняется это, в частности, в виде беседы, в которой студенту задаются вопросы. Что непонятного? Студентам не преподавал, но экзамены иногда принимаю.
0

Я не знаю, как вы себе это представляете, но у меня перед глазами встает такая картина. Экзамен. Студент, волнуясь, рассказывает про решение СЛАУ, и тут экзаменатор, который до этого слушал его с несколько скучающим видом, вскидывается и, едва пряча ехидную улыбку, спрашивает: так-так-так, голубчик! Вот вы говорите — истинное решение, да? Расскажите-ка, а почему же оно "истинное"? И какие такие не истинные бывают?


Жуткая картинка, на самом деле.

+1
Что-то сглаживание из первого примера выглядит как-то странно.
Формула f[i] = (f[i-1] + f[i+1])/2 вроде бы как предполагает локальное (зависящее лишь от ближайших соседей) и симметричное преобразование, но приведенный алгоритм реализует нечто другое.

Если предположить, что в начале очередной итерации f = [f0, f1, f2, ..., f31], то проделав несколько шагов итерации вручную, видно, что при этом происходят следующие замены:
f0 -> f1
f1 -> (f0+f2)/2 == (f1+f2)/2
f2 -> (f1+f3)/2 == (f1+f2+2*f3)/4
f3 -> (f2+f4)/2 == (f1+f2+2*f3+4*f4)/8
f4 -> (f3+f5)/2 == (f1+f2+2*f3+4*f4+8*f5)/16
...
f30 -> (f29+f31)/2 == (f1+f2+2*f3+4*f4+...+(2**29)*f31)/(2**30)
f31 -> f30 == (f1+f2+2*f3+4*f4+...+(2**29)*f31)/(2**30)

Это преобразование 1) нелокальное (все значения зависят от f1, хоть и с экспоненциально убывающим коэффициентом); 2) асимметричное (значения с большими индексами зависят от всех значений с меньшими индексами, но обратное неверно); 3) от f0 вообще ничего не зависит.

Да, при этом некое «сглаживание» несомненно происходит (с каждой итерацией значения всё меньше отличаются), но то ли это сглаживание, которое имелось в виду?
+1
Ага, тут должно быть два буфера — на вход и выход, которые после каждого прохода меняются местами.
+1
Кстати, внимательный читатель должен был бы заметить, что, строго говоря, у меня в коде системы линейных уравнений решаются не методом Якоби, но методом Гаусса-Зейделя

Ну вот вы и есть тот самый внимательный читатель :)
Сравните имплементации метода Якоби и метода Гаусса-Зейделя.

А вот так выглядит первая итерация обоих методов:
Скрытый текст
Якоби:



Гаусс-Зейдель:


0
Надо образец сделать не сглаживанием одного лица, а усреднением по выборке лиц, вот тогда будет настоящий генератор карикатур.
+1
Да, может получиться хороший проект, но тут есть технические сложности. Сосканировать много лиц несложно, но вот что с ними дальше делать, это уже интересный вопрос. Две поверхности легко «смешать», если они имеют одинаковую сетку треугольников. Даже если мы умеем смешивать разные сетки, нам нужно точно сопоставить нос одной модели с носом другой, глаза с глазами и т.п. Это всё решается, но задача нетривиальная.
0
Можно попробовать построить для каждого лица карту высот от сглаженной версии, и совмещать разные карты поиском максимума корреляции. Максимумы и минимумы высот — характерные точки, из их координат формируем вектор признаков, по этому вектору усредняем. Как-то так.
+1
Ну это один из вариантов, но лица имеют разные пропорции, и кросс-корреляция поможет весьма относительно. Без построения карт и корреляции можно обойтись совсем, использовав методы кросс-параметризации поверхностей. Но это уже довольно тяжёлая артиллерия, и явно выходит за пределы статьи с пометкой «обучающий материал».
+1
в названии статьи присутствуют наименьшие квадраты. Увидели ли вы их в тексте?
Скажу честно — не увидел. Зато увидел свёртку.
Only those users with full accounts are able to leave comments. , please.