Математика для программиста

← →
Юрий Зотов © (2006-03-31 19:29) [120]

> Jeer © (31.03.06 18:36) [116]

> То, что лично я могу "нарисовать" кучу "школьных" вариантов решения
> такой задачи - надеюсь, ты не сомневаешься:))

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

> На "старость" фору даду

Хех, вряд ли она потребуется. 2-3 часа - это вполне реальная оценка.

> default © (31.03.06 18:53) [118]

1. График любой ф-ции есть именно кривая. Прямая она на самом деле, или ломаная, или кусочно-гладкая, или кусочно-непрерывная, или еще что-то - неважно. Все это есть частные случаи общего термина "кривая".

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

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

← →
default © (2006-03-31 19:35) [121]

Юрий Зотов © (31.03.06 19:29) [120]
я имел ввиду как Jeer предлагал
например, через первые три точки проводим кусок параболы
решая систему трёх линейных уравнений с тремя неизвестными
(f(x)=ax^2+bx+c)
через следующие три точки(первая из которых является последней для первых трёх точек) проводим кусок кубического полинома
решая четыре линейных уравнения с четырьмя неизвестными
(f(x)=ax^3+bx^2+cx+d) чётвёртое уравнение это для равенства производных
далее, опять через следующие три точки кусок кубического полинома и тд
все операции школьные

← →
TUser © (2006-03-31 19:54) [122]

Задача изначально ставилась - нарисовать красивую кривую по точкам. В этом задании никакой задачи (в математическом смысле) просто нет. Но такие задания дает сама жизнь, причем регулярно. Поэтому дальше следует формализация задачи, приведение ее к математически строгому виду. Не поверю, что Jeer или Юрий Зотов этого не понимают. Тогда о чем спор?

← →
Юрий Зотов © (2006-03-31 21:26) [123]

> TUser © (31.03.06 19:54) [122]

Тоже не понимаю. Человек утверждал, что для рисования красивых графиков математика не нужна. Именно "красивый", это ЕГО слово, не мое.

ОК, ему именно такую задачу и предложили - вот тебе, мол, точки, нарисуй по ним красивый график. Любым способом, но чтобы было красиво. На глаз плавненько, на глаз гладенько. На глаз - и не более того. При том, что задача совершенно точно имеет решение, и даже много решений, выбирай любое, лишь бы красиво было.

НИ-КА-КОЙ формализации для этого АБ-СО-ЛЮТ-НО не требуется. Более того, кто знает, что такое аппроксимация/интерполяция, тот легко поймет, что задача поставлена совершенно корректно даже и в математическом смысле. Стандартная постановка - есть набор точек, по ним надо провести кривую, и вся любовь. Никаких ограничений, хошь - аппроксимируй (и пусть она себе на здоровье идет между точками), хошь - интерполируй (и пусть она себе на здоровье идет прямо по точкам).

Вообще, меня часто удивляют споры на этом форуме. Если сказать, что птицы летают, то тут же посыплется "а как же страусы?"; "а как же пингвины?"; "а вот куры летают, но плохо"; "а вот птицам подрезают крылья" - и т. д. Как будто непонятно, что человек имел в виду.

Воистину, прав анекдот - есть программисты (и, видимо, не только программисты), которые, ложась спать, ставят на прикроватный столик 2 стакана. Один с водой (если ночью захочется пить), другой пустой (если пить не захочется).

> All

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

Я же по-прежнему утверждаю (и готов доказать на деле), что с применением ВУЗовской математики эта задача легко решается за 2-3 часа.

← →
TGX © (2006-04-01 00:10) [124]

Математика нужна всем, еслиб она бала не столь не обходима её б не преподавали в школах и вузах.... Многи из великих высказывались о математике не плохо! А программисту матиматика нужна тем более! Желательна вся... чем больше будет знать программер тем более глубже он будет мыслить и приходить к нужной цели за более короткий промежуток времени! Так что лучше учить, учить и ещё раз учить математику!

← →
Petr V. Abramov © (2006-04-01 00:30) [125]

> аппроксимация/интерполяция
а разве про это не рассказывают в старших классах, по верхам, ессно?

← →
Юрий Зотов © (2006-04-01 00:49) [126]

> Petr V. Abramov © (01.04.06 00:30) [125]

Нам - не рассказывали. Сейчас, если и рассказывают, то не сомневаюсь, что НАСТОЛЬКО по верхам, что прилично аппроксимировать заданный набор точек - не получится. Только неприлично. :о)

← →
Германн © (2006-04-01 02:47) [127]

> Юрий Зотов © (01.04.06 00:49) [126]
>
> > Petr V. Abramov © (01.04.06 00:30) [125]
>
> Нам - не рассказывали. Сейчас, если и рассказывают, то не
> сомневаюсь, что НАСТОЛЬКО по верхам, что прилично аппроксимировать
> заданный набор точек - не получится. Только неприлично.
> :о)
>

Подтверждаю, что и нам - не рассказывали.
Сейчас, если и твориться что, так это "уменьшение уровня" знаний. И опыта их применений.

Но стараюсь, поелико возможно, держать свою дщерь на "уровне". И подстёгиваю её стремления изучить что-то самостоятельно.

← →
Думкин © (2006-04-01 05:58) [128]

> default © (31.03.06 18:53) [118]

Можно брать, но уже получится система ЛУ. А это уже - не школа.

← →
Думкин © (2006-04-01 06:07) [129]

> Petr V. Abramov © (01.04.06 00:30) [125]

Насколько знаю - не рассказывают.

А провести кривую. Если речь о "программистах", то они могут решить так: из проги на Дельфи(например - не важно), подцепить Эксель, запихать точки и построить график подходящей категории. Полученный файл - выложить. Математики 0. Или пользуя TChart.
:о)
В общем ветка скучнее чем "про калькулятор" вышла.

← →
isasa © (2006-04-01 11:15) [130]

default © (31.03.06 19:35) [121]
:)
Все уже украдено до нас.
Справочник по математике. Для инженеров и учвщихся втузов. Наука. 1986.

стр 504. п.7.1.2.6.2.Сплайн-интерполяция.
Самое оно. Удовлетворяет всем указанным(в самом начале) условиям постановки. Остальное фантазии, для того, чтобы не делать.

← →
isasa © (2006-04-01 11:33) [131]

TUser © (31.03.06 19:54) [122]
Совершенно верно.
По заданным точкам нарисовать график -> Через заданные точки( Pn(Xi)=Yi ) провести гладкую кривую. -> Интерполяция.(Обычная или сплайн)

← →
Юрий Зотов © (2006-04-01 11:41) [132]

> isasa © (01.04.06 11:33) [131]

Либо аппроксимация, по собственному выбору. Тоже задача вполне понятна.

← →
isasa © (2006-04-01 11:51) [133]

Юрий Зотов © (01.04.06 11:41) [132]
Аппроксимация, все-таки, требует дополнительных условий.
1. Уравнение кривой. (Чем "рисуем")
2. Метод получения коэффициентов( классический - наименьших квадратов, с учетом весов точек, или без ....)

Для графического отображения интерполяция самое оно. Я, например, не видел использования сплайна для аналитики заданного массива. Неудобно. Он, же "не сплошной" на весь диапазон (например, тот-же кубический из [130]).

← →
Юрий Зотов © (2006-04-01 12:40) [134]

> isasa © (01.04.06 11:51) [133]

> 1. Уравнение кривой. (Чем "рисуем")
Чем угодно, на выбор, не оговаривалось. Естественно, простой полином будет явно нефизичен, но ведь существуют и методы подбора функций.

> 2. Метод получения коэффициентов.
Любой, тоже не оговаривалось. Лишь бы "красиво" получилось. :о)

← →
isasa © (2006-04-01 14:56) [135]

Юрий Зотов © (01.04.06 12:40) [134]
Ну если так, тогда все условия созданы. Отговорки не принимаются. Подсказка, где искать мат. инструментарий есть. Вперед и с песней. :)

Единственное замечание. Задача, все-таки, выходит за рамки школьной программы. И тогда, когда я учился(ужас :) ), и сейчас, думаю так, потому что школьный курс математики со временем упростили(!! опять же, как никому не нужный!!!). Что не есть хорошо.

← →
isasa © (2006-04-01 14:57) [136]

← →
isasa © (2006-04-01 15:03) [137]

Сорри за дубль. У меня летитошибка при отправке тем.
Home › Tools › Babel Fish Translation › Translation Error Error decoding translated text. We"re sorry we"ve encountered an error with your request. If you think this is a bug we should know about send us e-mail and let us know the following: * What browser you were using. * The operating system you are on. * The type of translation you were trying when this error occurred. The error encountered is: 157

← →
Юрий Зотов © (2006-04-01 16:42) [138]

> isasa © (01.04.06 14:57) [136]
> Задача, все-таки, выходит за рамки школьной программы.

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

← →
TUser © (2006-04-01 18:55) [139]

> НИ-КА-КОЙ формализации для этого АБ-СО-ЛЮТ-НО не требуется.
> Более того, кто знает, что такое аппроксимация/интерполяция,
> тот легко поймет, что задача поставлена совершенно корректно
> даже и в математическом смысле.

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

← →
Jeer © (2006-04-03 16:53) [140]

TUser © (01.04.06 18:55) [139]

>Извините, не согласен. Задача жизненная.

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

Это задачи сглаживания экспериментальных данных, регрессионный анализ,
интерполяция и экстраполяция - для них придумано много методов и довольно сложных.
Но не всегда сложность является гарантией удовлетворительного решения.
В некоторых случаях, достаточно более простых методов о чем я и утверждал, говоря о возможности решения задачи, "поставленной" Юрием Зотовым методами, доступными школьнику-старшекласнику.
При этом предполагается, что этот самый школьник умеет программировать (кодить).:))

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

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

2. Еще один из возможных "простых" методов - моделирование движения физической точки по траектории, заданной набором узловых точек.
Разумеется, тут нужна еще и физика, но также вполне достаточно школьной программы.
В этом случае, такое движение можно расматривать как аналог движения лыжника по склону между флажками, погоня "волк-заяц", движение тела в поле тяготения под воздействием заданного множества узловых точек-тел.
Приближенные уравнения, описывающие такое движение не потребуют ничего
кроме знаний планиметрии и законов Ньютона.

Вернемся, однако, к способу №1 и рассмотрим школьное решение.

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

Сначала постановка:

Уравнение кривой второго порядка в общем виде y = A*X^2 + B*X + C
У нас есть координаты трех точек, которые должны лечь на параболу X1,X2,X3,Y1,Y2,Y3

Образуется система уравнений (школьная программа)
Y1 = A*X1^2 + B*X1 + C
Y2 = A*X2^2 + B*X2 + C
Y3 = A*X3^2 + B*X3 + C

Школьники умеют ее решать не как СЛАУ через матрицы-определители (хотя и это тоже известно им), а методом последовательного исключения:
Находим выражение для С из ур-ния (3), подставляем в (2), находим B из (2) подставляем в (1)
После преобразований получаются уравнения для определения A,B,C
A = ((Y1-Y3)*(X2-X3) -(X1-X3)*(Y2-Y3)) /(X2-X3)*(X1-X3)*(X1-X2)
B = (Y2-Y3)/(X2-X3) - A*(X2+X3)
C = Y3 +X3*(A*X3+B)

После этого мы можем по уравнению y = A*X^2 + B*X + C определять значения y по x, т.е. интерполировать между точками.

Для каждой новой тройки координат повторяются вычисления нового уравнения параболы (A,B,C) и рисуется кривая между точками.

Разумеется, этот вид интерполяции далек от совершенства, хотя и его можно улучшить (домашнее задание для желающих).
Тем не менее, для системы точек заданных Зотовым имеем вполне удовлетворительное решение.
Смотрим здесь:
Для Ю.З. http://hlab.newmail.ru/snap/snap-01.png
Для параболы http://hlab.newmail.ru/snap/snap-02.png
Для экспоненты http://hlab.newmail.ru/snap/snap-03.png
Для синусоиды http://hlab.newmail.ru/snap/snap-04.png
Для импульсного отклика звена второго порядка http://hlab.newmail.ru/snap/snap-05.png

Вуаля !

Код очень прост:

arX,arY: array of double;
// Решение для A,B,C. k - текущая точка
procedure SolveParabolic(k: integer; var vA,vB,vC: double);
var
Y23, Y13: double;
X12, X13, X23, XA23: double;
begin
X12 := arX[k] - arX[k+1];
X13 := arX[k] - arX[k+2];
X23 := arX[k+1] - arX[k+2];
XA23 := arX[k+1] + arX[k+2];
Y23 := arY[k+1] - arY[k+2];
Y13 := arY[k] - arY[k+2];
vA := (Y13*X23 - X13*Y23)/(X23*X13*X12);
vB := Y23 / X23 - vA * XA23;
vC := arY[k+2] - arX[k+2] * (vA * arX[k+2] + vB);
end;

// Тело цикла

procedure btnRunClick(Sender: TObject);
var A,B,C, Xa, Ya: double;
i,j,k: integer;
Xsi,Xsii, Ys: integer;

begin
Canvas.Pen.Color := clRed;
Canvas.MoveTo(XW2S(arX[0]), YW2S(arY[0]));

k := High(arX) - 2;
for i:= 0 to k do begin
SolveParabolic(i,A,B,C);
Xsi := XW2S(arX[i]);
if i < k then
Xsii := XW2S(arX[i+1])
else
Xsii := XW2S(arX[i+2]); // дорисовывание до последней точки
for j := Xsi to Xsii do begin
Xa := XS2W(j);
Ya := A*Xa*Xa + B*Xa + C;
Ys := YW2S(Ya);
Canvas.LineTo(j, Ys);
end;
end;
end;

//функции XW2S(),XS2W() - преобразование из "мировых" координат в экранные, не приведены, т.к. не существенно.

← →
Юрий Зотов © (2006-04-04 02:13) [141]

> Jeer © (03.04.06 16:53) [140]

Согласен, это уже доказательство. Того, что:

1. Задачу действительно МОЖНО решить школьными методами.

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

ИМХО, из числа людей, чье математическое образование ограничивается только школой, п. 2 все же отвечают лишь очень немногие. Но таких людей значительно больше среди тех, чье математическое образование школой НЕ ограничивается. Так что даже и для данной задачи ВУЗовское образование все же весьма полезно.

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

← →
Юрий Зотов © (2006-04-04 02:29) [142]

> All

Видимо, пора раскрыть "секрет": при любом масштабе изображения кривая будет выглядеть "красиво", если заданные точки аппроксимировать функцией Y=A+B*(X+C)^D*exp(E*X)

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

← →
Юрий Зотов © (2006-04-04 02:39) [143]

И теперь, после всех этих дискуссий, хотелось бы спросить автора ветки: Вы по-прежнему убеждены, что программисту математика не нужна, или этот пример с "красивым" графиком все же как-то поколебал Ваше мнение?

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

Юрий Зотов © (04.04.06 02:13) [141]

ч.т.д. :))

> 2. Школьными методами ее может решить человек, свободно
> этими методами владеющий.

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

> P.S.
В твоем решении куски парабол не состыкованы по первой производной

Это было оговорено выше - на точки "сшивания" не наложено никаких дополнительных условий, кроме совмещения координат.

> если заданные точки аппроксимировать функцией Y=A+B*(X+C)^D*exp(E*X)

Это задача регрессионного анализа и обычные школьники не знакомы с этими методами.

P.S.
Собственно говоря и пример Ю.Зотова, возможно с несколько "расплывчатой" постановкой и мои упражнения тут преследуют одну цель - показать, что одним "батонокидательством" и "размышлениями" на тему, что есть программист - программистом не стать без знания математики.

> Jeer © (04.04.06 10:22) [145]

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

Думкин © (04.04.06 10:31) [146]

> Если на точки сшивания, кроме совпадения координат

Не читаешь [140] - наложено условие - кривая втрого порядка - парабола + совпадение.
Там же и сказано - основа сплайн-метода - композитный полином.

Думкин © (04.04.06 10:31) [146]

> Школьник решить может - но это ВНЕ школьной программы и

Вероятно, в наше время 63-73 были другие "обычные" школьники, которые
почитывали Перельмана, Магницкого, Адамара, Болтянского с Ягломом, а на закуску Клейна, Колмогорова и Радемахера с Теплицем.

Jeer © (04.04.06 10:51) [149]
...которые почитывали Перельмана, Магницкого, Адамара, Болтянского с Ягломом, а на закуску Клейна, Колмогорова и Радемахера с Теплицем.

:)
не, ну это перебор. Не поверю, что 17-летний пацан все это читает. Одного двух авторов - да, но всех - это мат-маньяк какой-то :)

Да, еще забыл - заканчивали 10-ку по классу фоно и тоже сразу:)))

Математика для программиста Найти похожие ветки