Интерполяция алгоритмов

[Rock`n`Rolla]

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

[nikvic]

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

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

[Rock`n`Rolla]

Цитата:

Нельзя - если предполагается, что использована не вся область применимости этого неизвестного алгоритма.

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

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

[Sergeevich]

Rock`n`Rolla в сообщении #796229 писал(а):

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

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

[profrotter]

Rock`n`Rolla в сообщении #796247 писал(а):

преобразовать символьные последовательности в числа и работать уже с ними

Ну тогда, если дополнительно известно, что алгоритм линейный, то следует отыскать ЧХ, поделив спектр выходной последовательности на спектр входной.

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

[nikvic]

Rock`n`Rolla в сообщении #796247 писал(а):

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

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

[Rock`n`Rolla]

Цитата:

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

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

Цитата:

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

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

Цитата:

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

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

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

[_Ivana]

Встречный вопрос вам - если вы в каком-то конкретном простом случае угадаете алгоритм, вы считаете, что он будет единственным?

[Rock`n`Rolla]

_Ivana в сообщении #796367 писал(а):

Встречный вопрос вам - если вы в каком-то конкретном простом случае угадаете алгоритм, вы считаете, что он будет единственным?

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

[Sergeevich]

Rock`n`Rolla в сообщении #796363 писал(а):

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

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

[oveka]

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

[Joker_vD]

Sergeevich
По-моему, это был не пример алгоритма, а просто арифметизация.