2014 dxdy logo

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

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




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


14/02/12
17
Здравствуйте!

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

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

Спасибо.

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 16:30 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 16:55 


19/05/10

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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:02 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:17 
Заслуженный участник
Аватара пользователя


27/04/09
24119
Уфа
nikvic в сообщении #702232 писал(а):
Без дополнительных ограничений (на сложность описания или/и вычислений) неинтересна.
Вы же хотели сказать «нерешаема»?

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

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

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


14/02/12
17
nikvic, спасибо!

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

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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:28 
Заслуженный участник
Аватара пользователя


06/04/10
3152
arseniiv в сообщении #702240 писал(а):
Вы же хотели сказать «нерешаема»?

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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:40 
Заслуженный участник
Аватара пользователя


27/04/09
24119
Уфа
IvanMIPT в сообщении #702246 писал(а):
А если скажем N - РЕАЛЬНО БОЛЬШОЕ ЧИСЛО, это как-то влияет на рассмотрение вопроса?
Никак.

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

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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 19:43 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:04 
Заслуженный участник
Аватара пользователя


27/04/09
24119
Уфа
(Как вы будете интерполировать, например, деревья со строками в вершинах?)

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


11/06/12
8625
calm.angel.driven
Да, я не вник в суть темы полностью, признаю.

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:07 
Заслуженный участник
Аватара пользователя


06/04/10
3152
arseniiv в сообщении #702261 писал(а):
Если мы не знаем алгоритма, который надо определить, это же не значит, что его не знает кто-то другой. В условии задачи он есть, и подойдёт только один. А мы не знаем, какой из возможных — тот самый.

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

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:13 
Заслуженный участник


15/05/05
3390
USA
IvanMIPT в сообщении #702163 писал(а):
...мне нужны как раз именно самые общие идеи и направления в которых нужно размышлять...
Ваш алгоритм - это неизвестная Вам реализация некоей динамической системы. Для Вас эта система - "черный ящик". Ваша задача называется "задача идентификации систем". Смотрите соответствующую литературу.

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:24 
Заслуженный участник
Аватара пользователя


27/04/09
24119
Уфа
nikvic в сообщении #702282 писал(а):
Вы путаете функцию и алгоритм: у вычислимой функции масса имён-алгоритмов.
Функцию восстановить в общем случае ведь тоже нельзя. А уж любой из алгоритмов, реализующих её, и подавно!

 Профиль  
                  
 
 Re: Как понять неведомый алгоритм?
Сообщение27.03.2013, 20:51 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group