2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Как понять неведомый алгоритм?
Сообщение27.03.2013, 16:18 
Здравствуйте!

Собственно суть вопроса в следующем. Вот есть у меня некоторый неведомый алгоритм, и единственное что я про него знаю, что он на N конкретных входах даёт N конкретных результатов. Пусть теперь мне даётся произвольный вход для этого алгоритма, могу я предсказать что выдаст алгоритм в результате работы на этом входе?

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

Спасибо.

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 16:30 
Аватара пользователя
Самая общая идея -- использовать отладчик и читать коды.
Восстановить алгоритм по точкам в общем случае невозможно.

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 16:55 
если это числовые данные (вход и выход) - то без статистики (наука такая) не обойтись

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:02 
Аватара пользователя
Для теории алгоритмов это - задача общерекурсивного расширения заданной функции с конечным графиком. Без дополнительных ограничений (на сложность описания или/и вычислений) неинтересна. Практически тяготеет к "сжатию" файлов без потерь.

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:17 
nikvic в сообщении #702232 писал(а):
Без дополнительных ограничений (на сложность описания или/и вычислений) неинтересна.
Вы же хотели сказать «нерешаема»?

-- Ср мар 27, 2013 22:21:10 --

mihailm в сообщении #702180 писал(а):
если это числовые данные (вход и выход) - то без статистики (наука такая) не обойтись
При чём здесь статистика? Пускай алгоритм вычисляет функцию $x > 12345678910111213 \mathbin? 1 : 0$, а мы проверили его для чисел только меньше ста тысяч. Как статистика поможет узнать, что алгоритм — данный?

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:24 
nikvic, спасибо!

Sphinx Pinastri , оно то конечно так, но только вот нет этих кодов :-( речь идет об абстрактном алгоритме, не программе.

А если скажем N - РЕАЛЬНО БОЛЬШОЕ ЧИСЛО, это как-то влияет на рассмотрение вопроса?

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:28 
Аватара пользователя
arseniiv в сообщении #702240 писал(а):
Вы же хотели сказать «нерешаема»?

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

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:40 
IvanMIPT в сообщении #702246 писал(а):
А если скажем N - РЕАЛЬНО БОЛЬШОЕ ЧИСЛО, это как-то влияет на рассмотрение вопроса?
Никак.

-- Ср мар 27, 2013 22:41:22 --

nikvic в сообщении #702251 писал(а):
Гм, нет проблем алгоритмически доопределить функцию нулём для всех неупомянутых значений аргумента.
Если мы не знаем алгоритма, который надо определить, это же не значит, что его не знает кто-то другой. В условии задачи он есть, и подойдёт только один. А мы не знаем, какой из возможных — тот самый.

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:43 
Аватара пользователя
Или я не вник в суть темы, или это какая-то лажа. :facepalm: Имеем: значения неизвестно как заданной функции в некоторых точках. Найти: значение функции в какой-то другой точке. Решение: интерполируем и заявляем, что может быть приблизительно это и подходит. А может быть и нет. Фиг его знает. И при чём тут алгоритмы, общерекурсивные функции, коды, отладчики?..

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:04 
(Как вы будете интерполировать, например, деревья со строками в вершинах?)

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:05 
Аватара пользователя
Да, я не вник в суть темы полностью, признаю.

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:07 
Аватара пользователя
arseniiv в сообщении #702261 писал(а):
Если мы не знаем алгоритма, который надо определить, это же не значит, что его не знает кто-то другой. В условии задачи он есть, и подойдёт только один. А мы не знаем, какой из возможных — тот самый.

Вы путаете функцию и алгоритм: у вычислимой функции масса имён-алгоритмов.
Ну и задачу с головоломкой, где требуется "изячный" ответ :P

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:13 
IvanMIPT в сообщении #702163 писал(а):
...мне нужны как раз именно самые общие идеи и направления в которых нужно размышлять...
Ваш алгоритм - это неизвестная Вам реализация некоей динамической системы. Для Вас эта система - "черный ящик". Ваша задача называется "задача идентификации систем". Смотрите соответствующую литературу.

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:24 
nikvic в сообщении #702282 писал(а):
Вы путаете функцию и алгоритм: у вычислимой функции масса имён-алгоритмов.
Функцию восстановить в общем случае ведь тоже нельзя. А уж любой из алгоритмов, реализующих её, и подавно!

 
 
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:51 
Аватара пользователя
А ваша функция неизвестна науке или ее просто кто-то вам не показывает?
В последнем случае часто лучше работать с людьми.
Собирайте статистику о времени появления новых значений. О том, что было
в мире до и после. Кто и зачем передавал новое значение.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group