Как понять неведомый алгоритм?

[IvanMIPT]

Здравствуйте!

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

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

Спасибо.

[Sphinx Pinastri]

Самая общая идея -- использовать отладчик и читать коды.
Восстановить алгоритм по точкам в общем случае невозможно.

[mihailm]

если это числовые данные (вход и выход) - то без статистики (наука такая) не обойтись

[nikvic]

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

[arseniiv]

nikvic в сообщении #702232 писал(а):

Без дополнительных ограничений (на сложность описания или/и вычислений) неинтересна.

Вы же хотели сказать «нерешаема»?

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

mihailm в сообщении #702180 писал(а):

если это числовые данные (вход и выход) - то без статистики (наука такая) не обойтись

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

[IvanMIPT]

nikvic, спасибо!

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

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

[nikvic]

arseniiv в сообщении #702240 писал(а):

Вы же хотели сказать «нерешаема»?

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

[arseniiv]

IvanMIPT в сообщении #702246 писал(а):

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

Никак.

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

nikvic в сообщении #702251 писал(а):

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

Если мы не знаем алгоритма, который надо определить, это же не значит, что его не знает кто-то другой. В условии задачи он есть, и подойдёт только один. А мы не знаем, какой из возможных — тот самый.

[Aritaborian]

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

[arseniiv]

(Как вы будете интерполировать, например, деревья со строками в вершинах?)

[Aritaborian]

Да, я не вник в суть темы полностью, признаю.

[nikvic]

arseniiv в сообщении #702261 писал(а):

Если мы не знаем алгоритма, который надо определить, это же не значит, что его не знает кто-то другой. В условии задачи он есть, и подойдёт только один. А мы не знаем, какой из возможных — тот самый.

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

[Yuri Gendelman]

IvanMIPT в сообщении #702163 писал(а):

...мне нужны как раз именно самые общие идеи и направления в которых нужно размышлять...

Ваш алгоритм - это неизвестная Вам реализация некоей динамической системы. Для Вас эта система - "черный ящик". Ваша задача называется "задача идентификации систем". Смотрите соответствующую литературу.

[arseniiv]

nikvic в сообщении #702282 писал(а):

Вы путаете функцию и алгоритм: у вычислимой функции масса имён-алгоритмов.

Функцию восстановить в общем случае ведь тоже нельзя. А уж любой из алгоритмов, реализующих её, и подавно!

[Sphinx Pinastri]

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