Re: Получить функцию

From

Вадим Зеленин ()

To

Dmitriy Gatsura

Date

2002-11-14T12:03:31Z

Area

RU.ALGORITHMS

From: "Вадим Зеленин" <green@vista.spb.su>

Hello, Dmitriy!
You wrote in conference fido7.ru.algorithms to Vitaly Slobodskoy on Tue, 12
Nov 2002 22:31:00 +0300:

 DG> Как поживаете, Vitaly ?

 DG>>> Есть набор чисел 0,1,2..n из которого некоторым образом выбираются
 DG>>> к чисел (к<=n). Существуют ли алгоритмы для вычисления ф-ции,
 DG>>> которая бы проходила через все к точек?
 VS>>  Интерполяция, однако - интерполяционный многочлен Лагранжа.
 DG> Если я правильно помню метод, то ф-ция проходящая через k точек
 DG> будет представлять собой полином к-ой степени?
 DG> Т.е. если имеем 1 00 000 точек то получим очень и очень не приятное
 DG> выражение.

Дай-ка я тоже встряну :)
и напомню, что просто таблица точек - это тоже функция, только область
определения у неё диапазон целых чисел... поскольку ты не задал область
определения, может быть тебе подойдёт таблица? :)
И алгоритм приятный - int f(int x) { assert(0<=x&&x<k); return
(MyTable[x]); }

Говоришь, что нужна функция определённая на диапазоне действительных
значений? а чем плоха ступенчатая функция? не непрерывная? а где сказано,
что функция должна быть непрерывной? :)

Для непрерывных функций есть линейная интерполяция. Смотри-ка - экологически
чистая непрерывная функция построенная передовым методом линейной
интерполяции - и вычисляется просто и непрерывна :) У неё только производные
подкачали :) Но в исходной задаче нигде не говорится про непрерывность
производных... Кстати, есть способ представить такую функцию в виде суммы
f(x) := Sum(i:=1..k; c[i]*abs(X[i]-x)). Будет вполне как-бы аналитично.
Только по таблице считать быстрее :)

Далее - есть замечательные сплайны - будет и функция непрерывна, и первые
производные вполне :)

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

 DG> А нет ли алгоритма способа нахождения некой хеш-функции которая бы
 DG> описывала все эти точки и которую можно было бы запомнить или
 DG> записать к примеру на бумаге(не слишком большом ее количестве)?

как-это, "хеш-функции которая бы описывала все эти точки"? Обычно
хеш-функции служат для отображения данных (ключей в б.д.,  идентификаторов в
компиляторах и пр.) в целые числа для ускорения поиска. Мы же ничего не
ищем? :))

 DG> ЗЫ  Мне кажется что таких методов просто не существует, но чем черт
 DG> не шутит:)

Это ты, должно быть, шутишь ;)
Из исходной задачи я могу выделить две особенности данных -  у тебя есть
такая табличка целых чисел, что:
1) Значения принадлежат интервалу [0, n].
2) Значения не повторяются.
Оба ограничения довольно слабы. Если отбросить второе (всё равно мы пока не
знаем как его применить; это гарантия того, что существует обратная функция,
но она нам сейчас не нужна...), то задача отыскания более компактной записи
чем таблица превращается в задачу написания архиватора :) При этом мы все
знаем, что для любого архиватора найдутся данные, которые в архиве займут
места больше, чем в исходном состоянии.

Удачи!
Вадим Зеленин.  E-mail: green@vista.spb.su

--- ifmail v.2.15dev5
 * Origin: Vista (2:5020/400)