ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : ‚ ¤Ё¬ ‡Ґ«Ґ­Ё­                        2:5020/400     14 Nov 2002  13:03:31
 To : Dmitriy Gatsura
 Subject : Re: Получить функцию
 -------------------------------------------------------------------------------- 
 

 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]); }
 
 Говоришь, что нужна функция определённая на диапазоне действительных
 значений? а чем плоха ступенчатая функция? не непрерывная? а где сказано,
 что функция должна быть непрерывной? :)
 
 Для непрерывных функций есть линейная интерполяция. Смотри-ка - экологически
 чистая непрерывная функция построенная передовым методом линейной
 интерполяции - и вычисляется просто и непрерывна :) У неё только производные
 подкачали :) Hо в исходной задаче нигде не говорится про непрерывность
 производных... Кстати, есть способ представить такую функцию в виде суммы
 f(x) := Sum(i:=1..k; c[i]*abs(X[i]-x)). Будет вполне как-бы аналитично.
 Только по таблице считать быстрее :)
 
 Далее - есть замечательные сплайны - будет и функция непрерывна, и первые
 производные вполне :)
 
 А интерполяционные полиномы должны знать своё место :) Типа служить только
 для "гладких" данных и немногих точек. К сожалению, у них препоганое
 поведение между точками, особенно если данные не "гладкие". Больно уж это
 дорогое удовольствие - и через точки пройти и все производные непрерывные
 :(.  Особенный привет интерполяционному полиному в форме Лагранжа. Если
 вычислять нужно много и быстро, лучше перейти к форме Hьютона. Кстати, и на
 бумаге выглядит аккуратнее...
 
  DG> А нет ли алгоритма способа нахождения некой хеш-функции которая бы
  DG> описывала все эти точки и которую можно было бы запомнить или
  DG> записать к примеру на бумаге(не слишком большом ее количестве)?
 
 как-это, "хеш-функции которая бы описывала все эти точки"? Обычно
 хеш-функции служат для отображения данных (ключей в б.д.,  идентификаторов в
 компиляторах и пр.) в целые числа для ускорения поиска. Мы же ничего не
 ищем? :))
 
  DG> ЗЫ  Мне кажется что таких методов просто не существует, но чем черт
  DG> не шутит:)
 
 Это ты, должно быть, шутишь ;)
 Из исходной задачи я могу выделить две особенности данных -  у тебя есть
 такая табличка целых чисел, что:
 1) Значения принадлежат интервалу [0, n].
 2) Значения не повторяются.
 Оба ограничения довольно слабы. Если отбросить второе (всё равно мы пока не
 знаем как его применить; это гарантия того, что существует обратная функция,
 но она нам сейчас не нужна...), то задача отыскания более компактной записи
 чем таблица превращается в задачу написания архиватора :) При этом мы все
 знаем, что для любого архиватора найдутся данные, которые в архиве займут
 места больше, чем в исходном состоянии.
 
 Удачи!
 Вадим Зеленин.  E-mail: green@vista.spb.su
 
 --- ifmail v.2.15dev5
  * Origin: Vista (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор