Существует ли алгоритм, восстанавливающий неизвестную функцию из множества векторов входных и выходных значений?

К примеру, есть неизвестная функция f(x) = y, для неё известна таблица:
f(0) = 0;
f(1) = 2;
f(2) = 4;
На основе этих данных можно предположить, что f(x) = 2x. Так вот, существует ли алгоритм, который по конечному набору векторов входных и выходных значений мог бы выдать функцию, верную для всех этих векторов?

Провести полином нужного порядка через известные точки, что ли? Ну так это не алгоритм, это аналитически решаемая задача. Тот же wolframalpha это спокойно делает.

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

Не совсем, я привёл простой пример. Скажем так, нужна достаточно оптимальная функция. Притом, может быть множество входных аргументов. К примеру f(x1,x2,...,xN) = y. Или результат не вычисляется явно, типа f(5678) = 3, f(7890) = 4, f(5326) = 1 (подсчитывает количество замкнутых контуров в числе) - т.е. тут уже нужен алгоритм, как я понимаю, и надо его найти, вычислить. Возможно ли это для общего случая, когда мы не знаем в чём состоит задача, а знаем только входные и выходные данные?

Нет, в общем случае эта задача не решается.

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

Критерий сравнения - количество операций, соответственно, чем их меньше, тем лучше. Для моего первого примера можно сказать, что f(x) = 2x, или что f(x) = x^2 + x * sin (pi/2 * x) - оба варианта верны, но первый лучше, потому как количество операций меньше. Насколько я понимаю, задачу можно решить перебором (который становится неэффективным очень быстро), а есть ли более оптимальный алгоритм?

Т.е. для таблицы
f(0) = 0;
f(1) = 2;
f(2) = 4;
f(3) = 6;
Алгоритм должен выдать ответ f(x) = 2x, а если мы добавим
f(4) = 16;
То должен уметь выдать что f(x) = x^2 + x * sin (pi/2 * x), ну или хотя-бы:
для x=0..3, f(x) = 2x;
для x=4, f(x) = x^2; (или хотя-бы = 16)

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

Полином нужной степени чем не угодил?

А разве полином нужной степени решит задачку с подсчётом замкнутых контуров в числе? С другой стороны, алгоритм:
1. Разбить число на цифры
2. 1..5,7 = 0; 0,6,9 = 1; 8 = 2
3. Просуммировать результат
По сути нужен алгоритм построения алгоритмов =)

Вам уже указали, что это приближение полиномом. Выберите нужную степень, нужную точность, и вперед. С задачей даже Excel справляется, не говоря про более заточенные тулзы.
Аналитического решения без дополнительной априорной инфы не существует. Только случайное совпадение в том случае, когда исходная функция сама полином.

Полином хорош для простейшего примера, а если f(x, y, z) = x (z) y, где z = {0 = +, 1 = -, 2 = *, 3 = /}, но мы не знаем самой функции, а только некоторый набор входных и выходных данных?

Что вы тут написали не понял даже я, куда уж там алгоритму.

В общем, насколько я вижу, задача эквивалентна написанию ИИ. Если не по сути, то уж по сложности точно. И перспективы такие же.

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

Ну как бэ нет, не то что нелегко, она вообще так не решается

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

Почему же? Надо будет как-нибудь написать такую программку, чтобы доказать, что в ней нет ничего принципиально сложного =)

Удачи

Угу и проверить на ряде хотя бы из 10 чисел

Ряд из 10 чисел без проблем накрывается полиномом 9-й степени. Алгоритм решения системы линейных уравнений любого конечного числа переменных давно не секрет.

Я в курсе... Но перебор элементарных операций на ряде из 10 чисел с поддержкой скобок будет делаться оооочень долго... потому и был сарказм.

У меня стойкое ощущение, что такой перебор не завершится никогда ни для какого ряда. Вложенность функций же никто не отменял и не ограничивал.

На самом деле мой однокурсник в своё время написал такой алгоритм (не помню точно по какому поводу - я закончил универ в 1997 году) и алгоритм успешно работал перебирая элементарные операции между позициями ряда.... Пока дело не дошло до расстановки скобок... С расстановкой скобок о даже писать не стал - просто посчитал вычислительную сложность и бросил это дело.

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

Приятное упражнение при изучении нового языка.

А задача какая - просто восстановить функцию или непременно записать ее в аналитическом виде?
Если первое, то методы машинного обучения умеют это делать давно и успешно.

На сколько успешно? Оценку погрешности могут давать или наоборот делать с гарантированной погрешностью?

Погрешность оценивается по тестовой выборке. С гарантированной погрешностью - не знаю такого, но я в принципе в этой области не все знаю.

Дык с 97-го года компьютеры же быстрее стали .

Пытаться воспроизводить функцию на основе конечного числа точек - дело заведомо гиблое, если нет каких-то дополнительных гипотез. К примеру. ряд чисел
1, 2, 4, 8, 16, ...
вполне логично можно продолжить вот так: 31, 57, 99. А вот и пруфлинк:

Сссылка

Попробуйте, авось попадете на скрижали истории. Например, такая простенькая задачка: есть две точки на эллипсоиде вращения, заданные широтой и долготой. Найти расстояние между ними. Если найдете эмпирическое решение в элементарных функциях с точностью хотя бы +-1 метр на 100 км, ваше имя будет во всех учебниках. Правда, здесь функция не одной переменной, а четырех: расстояние = F(x1,y1,x2,y2), но принципиально дела это не меняет. Параметры эллипсоида можно считать константами, например, взять эллипсоид WGS-84. Известно штук пять итерационных решений, каждое из которых изрядно тормозное и со своими проблемами. Самое популярное - решение Винценти, более известное, как формула Винценти, хотя это не формула, а алгоритм.

От себя добавлю, что решение существует, но в открытых источниках не найдете. Ибо серьезное ноу-хау.

Разумеется. Имеется ввиду расстояние на эллипсоиде.