2014 dxdy logo

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

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




 
 Интерполяция алгоритмов
Сообщение04.12.2013, 15:30 
Задача: Есть большое количество сопоставленных друг другу входных и выходных данных некоторого алгоритма. Исходя из этих данных определить алгоритм, по которому они были получены. То есть, алгоритм в данном случае выступает как функция, на вход которой подаётся некоторый набор символов, что-то с ним внутри неё происходит и получается некоторый другой набор символов из того же алфавита. Нам нужно узнать что именно с ним происходит.
Вопрос: Можно ли в принципе решить такую задачу, и если да, то как?

 
 
 
 Re: Интерполяция алгоритмов
Сообщение04.12.2013, 15:40 
Аватара пользователя
Нельзя - если предполагается, что использована не вся область применимости этого неизвестного алгоритма.
Но можно ставить задачу по-колмогоровски, отыскивая минимальную программу, реализующую зависимость между массивом входных и выходных данных.

А можно ещё и сложность вычислений ограничивать :wink:

 
 
 
 Re: Интерполяция алгоритмов
Сообщение04.12.2013, 15:49 
Цитата:
Нельзя - если предполагается, что использована не вся область применимости этого неизвестного алгоритма.

А как это определить и что такое "область применимости"?

ИМХО, можно попробовать преобразовать символьные последовательности в числа и работать уже с ними. Формула это же суть алгоритм, записанный в аналитической форме.

 
 
 
 Re: Интерполяция алгоритмов
Сообщение04.12.2013, 15:59 
Rock`n`Rolla в сообщении #796229 писал(а):
на вход которой подаётся некоторый набор символов, что-то с ним внутри неё происходит и получается некоторый другой набор символов из того же алфавита.

Это задача декодирования?

 
 
 
 Re: Интерполяция алгоритмов
Сообщение04.12.2013, 16:09 
Аватара пользователя
Rock`n`Rolla в сообщении #796247 писал(а):
преобразовать символьные последовательности в числа и работать уже с ними
Ну тогда, если дополнительно известно, что алгоритм линейный, то следует отыскать ЧХ, поделив спектр выходной последовательности на спектр входной.

И следует учесть, что преобразование "символов в числа" потребует введение операций сложения между символами и умножения на число.

 
 
 
 Re: Интерполяция алгоритмов
Сообщение04.12.2013, 16:48 
Аватара пользователя
Rock`n`Rolla в сообщении #796247 писал(а):
Формула это же суть алгоритм, записанный в аналитической форме.

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

 
 
 
 Re: Интерполяция алгоритмов
Сообщение04.12.2013, 21:31 
Цитата:
Это задача декодирования?

Нет, это задача о распознавании алгоритма по его входным и выходным данным.

Цитата:
обычная "формула" определяется конечным деревом своих подформул, так что формулы реализуют простенькие функции

Окей, но можно же представить формулу в виде алгоритма.

Цитата:
преобразование "символов в числа" потребует введение операций сложения между символами и умножения на число

Я имею ввиду немного другой переход от символов к числам. Продемонстрирую на примере. Пусть у входных и выходных значений алгоритма, который мы хотим определить, один и тот же алфавит: "abcd1234". Тогда сопоставим символу "а" число 1, "b" - 2, "c" - 3, ..., "aa" - 9, "ab" - 10 и так далее.

Я вот что думаю, если набор сопоставленных входных-выходных значений действительно порождается каким-нибудь алгоритмом, и больше никаких других входных значений этот алгоритм не принимает (кроме тех, что есть у нас), то в принципе, этот алгоритм можно угадать. То есть решить эту задачу для простых алгоритмов можно, вопрос: можно ли это сделать для сложных?

 
 
 
 Re: Интерполяция алгоритмов
Сообщение04.12.2013, 21:36 
Встречный вопрос вам - если вы в каком-то конкретном простом случае угадаете алгоритм, вы считаете, что он будет единственным?

 
 
 
 Re: Интерполяция алгоритмов
Сообщение05.12.2013, 10:28 
_Ivana в сообщении #796367 писал(а):
Встречный вопрос вам - если вы в каком-то конкретном простом случае угадаете алгоритм, вы считаете, что он будет единственным?

Никак нет, их может быть и несколько.

 
 
 
 Re: Интерполяция алгоритмов
Сообщение05.12.2013, 10:31 
Rock`n`Rolla в сообщении #796363 писал(а):
Я имею ввиду немного другой переход от символов к числам. Продемонстрирую на примере. Пусть у входных и выходных значений алгоритма, который мы хотим определить, один и тот же алфавит: "abcd1234". Тогда сопоставим символу "а" число 1, "b" - 2, "c" - 3, ..., "aa" - 9, "ab" - 10 и так далее.

То что вы изобразили, как пример, не может быть выражен какой-то формулой ( ну, по крайней мере, матрицей еще можно) или он неудачный.
У вас последовательность "ab" и число 10, и два числа 1 и 2.
Для разбора таких вещей должен существовать еще один алфавит - динамический, но это из другой области знаний.

 
 
 
 Re: Интерполяция алгоритмов
Сообщение05.12.2013, 19:15 
1. Вы можете предположить, что у вас алгоритмы известны и их есть перечень. Составить программу проверки и выбрать подходящий. Если он будет.
2. Предположить, что алгоритм может быть подан в виде композиции известных типов преобразований- элементарных алгоритмов. Составить самоорганизующуюся систему, котора создаст гирлянду элементарных алгоритов.
Ура!!! Если это подходящий класс алгоритмов под те данные.

 
 
 
 Re: Интерполяция алгоритмов
Сообщение05.12.2013, 20:23 
Sergeevich
По-моему, это был не пример алгоритма, а просто арифметизация.

 
 
 [ Сообщений: 12 ] 


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