IPB
 

Здравствуйте, гость ( Вход | Регистрация )

Поддержать форум
3 страниц V   1 2 3 >  
Ответить в данную темуНачать новую тему
> Восстановление функции по вектору входных данных и результату
AiSee
Отправлено: 16.12.2011, 12:44
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



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

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


--------------------
What do you wish for?
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 16.12.2011, 13:02
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3964
Регистрация: 09.04.2007
Пользователь №: 45663



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

Вообще, как бы очевидно, что для любого набора точек таких функций бесконечно много. Так что очень многое зависит от того, в каком виде искать и какие нужны ограничения.
 
Перейти в начало страницы
AiSee
Отправлено: 16.12.2011, 13:31
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



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


--------------------
What do you wish for?
 
Перейти в начало страницы
lost_shadow
Отправлено: 16.12.2011, 13:53
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 308
Регистрация: 05.02.2007
Из: студгородок
Пользователь №: 40526



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


--------------------
[size="1"][sub]...имею опыт использования Microsoft Windows и операционных систем...[/sub][/size]
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 16.12.2011, 14:03
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3964
Регистрация: 09.04.2007
Пользователь №: 45663



Цитата(AiSee @ 16.12.2011, 14:31) *
Возможно ли это для общего случая, когда мы не знаем в чём состоит задача, а знаем только входные и выходные данные?
Цитата(Eyeless Watcher @ 16.12.2011, 14:02) *
Вообще, как бы очевидно, что для любого конечного набора точек таких функций бесконечно много.


Сможете сформулировать критерий отсечения неподходящих или сравнения между собой - будет о чем разговаривать.
А вообще, вы мне очень вот эту тему напомнили.
 
Перейти в начало страницы
AiSee
Отправлено: 16.12.2011, 14:16
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



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


--------------------
What do you wish for?
 
Перейти в начало страницы
AiSee
Отправлено: 16.12.2011, 14:37
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



Т.е. для таблицы
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)


--------------------
What do you wish for?
 
Перейти в начало страницы
AiSee
Отправлено: 16.12.2011, 14:47
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



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


--------------------
What do you wish for?
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 16.12.2011, 14:52
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3964
Регистрация: 09.04.2007
Пользователь №: 45663



Полином нужной степени чем не угодил?
 
Перейти в начало страницы
AiSee
Отправлено: 16.12.2011, 14:57
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



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


--------------------
What do you wish for?
 
Перейти в начало страницы
livingboy
Отправлено: 16.12.2011, 15:01
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 45373
Регистрация: 10.05.2005
Пользователь №: 9989



Цитата(AiSee @ 16.12.2011, 15:47) *
И опять таки, мне не нужно решение с точки зрения математика (т.е. получение набора функций и условий их применения) или функционального программирования, а достаточно получить решение точки зрения бухгалтера или же императивного программирования, оптимизированное по времени исполнения.
Вам уже указали, что это приближение полиномом. Выберите нужную степень, нужную точность, и вперед. С задачей даже Excel справляется, не говоря про более заточенные тулзы.
Аналитического решения без дополнительной априорной инфы не существует. Только случайное совпадение в том случае, когда исходная функция сама полином.


--------------------
Пусть народ сам решит, что ему обещать. (c)не-знаю-кто
 
Перейти в начало страницы
AiSee
Отправлено: 16.12.2011, 15:17
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



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


--------------------
What do you wish for?
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 16.12.2011, 15:37
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3964
Регистрация: 09.04.2007
Пользователь №: 45663



Цитата(AiSee @ 16.12.2011, 16:17) *
...а если f(x, y, z) = x (z) y, где z = {0 = +, 1 = -, 2 = *, 3 = /}, но мы не знаем самой функции, а только некоторый набор входных и выходных данных?

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

В общем, насколько я вижу, задача эквивалентна написанию ИИ. Если не по сути, то уж по сложности точно. И перспективы такие же.
 
Перейти в начало страницы
AiSee
Отправлено: 16.12.2011, 15:53
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 10.04.2006
Пользователь №: 23047



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


--------------------
What do you wish for?
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 16.12.2011, 16:02
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3964
Регистрация: 09.04.2007
Пользователь №: 45663



Цитата(AiSee @ 16.12.2011, 16:53) *
Эта задача теоретически достаточно легко решается перебором всех возможных сочетаний входных значений и простых операций над ними.

Ну как бэ нет, не то что нелегко, она вообще так не решается smile.gif
 
Перейти в начало страницы

3 страниц V   1 2 3 >
Ответить в данную темуНачать новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



Удалить установленные форумом cookies · Отметить все сообщения прочитанными
RSS Текстовая версия