Взаимосвязанные вычисления

[tac]

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

Существует последовательность N чисел, начальные значения которых от 1 до N. Примем N=60. Тогда вначале имеем $x_1=1, x_2=2, x_3=3, ... , x_{60}=60$.

Изменять числа в последовательности можно только следующим способом: начиная с любого выбранного числа можно применить одну из двух последовательностей $x_{current}=x_{current}+1$ или $x_{current}=x_{current}-1$, но так чтобы пройти обязательно до конца последовательности.

Например, применяя последовательность $x_{current}=x_{current}+1$ к 3 числу, значения последовательности изменятся так: $x_1=1, x_2=2, x_3=4, x_4=5, ... , x_{60}=61$.

Требуется так изменить значения последовательности, чтобы нижеследующие пары чисел стали одинаковые:

* 9-27
* 10-26
* 11-25
* 12-24
* 13-23
* 14-22
* 36-51
* 37-50
* 38-49
* 39-48
* 40-47

Конечно, чем более общие решение тем лучше. Но хотя бы интересно как следует размышлять решая подобные задачи?

[Vince Diesel]

Т.е. $x_9=x_{27}$ и т.д.?

[tac]

Vince Diesel в сообщении #573218 писал(а):

Т.е. $x_9=x_{27}$ и т.д.?

да.

[AV_77]

Если обозначить через $f_i$ преобразование вида $x_j \mapsto x_{j+1}$ при $j \geq i$, а через $g_i$ преобразование вида $x_j \mapsto x_j-1$ при $j \geq i$, то $g_{j+1}f_i$ увеличивает значение $x_i$ на 1, а все остальные не меняет. Аналогично, $f_{i+1} g_i$ уменьшает $x_i$ на 1, а остальные не меняет.

[gris]

Если алгоритмически сказать:
К массиву из чисел, заполненному некоторыми начальными значениями, можно применять две процедуры:
увеличение/уменьшение на 1 всех элементов, начиная с указанного номера. Требуется привести массив к нужному виду.
Можно обозначить процедуры $N_+$ и $N_-$.
Например, представим результат некоторой последовательности процедур к небольшому массиву:
$1 2 3 4 5 6 7 8 9 10$ - массив
$3_+;6_-;4_-;9_+$ - последовательность процедур

$1 2 4 5 6 7 8 9 10 11$

$1 2 4 5 6 6 7 8 9 10$

$1 2 4 4 5 5 6 5 8 9$

$1 2 4 4 5 5 6 5 9 10$ -результат.

Интересно, что последовательность двух процедур $8_+$ и $9_-$ просто увеличивает восьмой элемент массива на 1, а последовательность двух процедур ]$8_-$ и $9_+$ просто уменьшает восьмой элемент массива на 1.

То есть за конечное число таких вот пар можно привести массив к любому виду.

Наверное, Вас интересует минимизация количества процедур, либо числа изменяемых элементов?

Я правильно понял задачу?

И вот чего я это писал столько времени???

[tac]

AV_77 в сообщении #573230 писал(а):

Если обозначить через $f_i$ преобразование вида $x_j \mapsto x_{j+1}$ при $j \geq i$, а через $g_i$ преобразование вида $x_j \mapsto x_j-1$ при $j \geq i$, то $g_{j+1}f_i$ увеличивает значение $x_i$ на 1, а все остальные не меняет. Аналогично, $f_{i+1} g_i$ уменьшает $x_i$ на 1, а остальные не меняет.

Хорошие наблюдение. Как я понимаю это означает надо одним шагом увеличить на единицу, а затем для числа на единицу больше уменьшить на единицу. И таким образом, мы делаем вычисления НЕ взаимосвязанными.

И следующие наблюдение тоже самое

gris в сообщении #573240 писал(а):

Интересно, что последовательность двух процедур $8_+$ и $9_-$ просто увеличивает восьмой элемент массива на 1, а последовательность двух процедур ]$8_-$ и $9_+$ просто уменьшает восьмой элемент массива на 1.

Хорошо, тогда надо усложнить задачу. Задачу сформулировать тоже отдельная задача :)

-- Сб май 19, 2012 13:35:12 --

gris в сообщении #573240 писал(а):

Можно обозначить процедуры $N_+$ и $N_-$.

Вот хорошие обозначение. Для усложнения мы должны ввести такие процедуры $N_+$ и $N_-$, которые не имеют строго обратных. И кроме того зависят от предшествующего числа.

Например, что измениться если эти процедуры станут такими $x_{current}=x_{prev}+1$ или $x_{current}=x_{prev}-1$. Т.е. последующие число зависит от предыдущего. И еще кроме плюс/минус единицы может быть любое число.

-- Сб май 19, 2012 14:00:39 --

gris в сообщении #573240 писал(а):

Например, представим результат некоторой последовательности процедур к небольшому массиву:
$1 2 3 4 5 6 7 8 9 10$ - массив
$3_+;6_-;4_-;9_+$ - последовательность процедур

$1 2 4 5 6 7 8 9 10 11$

$1 2 4 5 6 6 7 8 9 10$

$1 2 4 4 5 5 6 5 8 9$

$1 2 4 4 5 5 6 5 9 10$ -результат.

И вот чего я это писал столько времени???

Вот именно нахождение нужной последовательности процедур и является задачей. Единственно, сейчас получилось так что во имя упрощения вы нашли "замечательное свойство" вида "последовательность двух процедур $8_+$ и $9_-$ просто увеличивает восьмой элемент массива на 1".

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

[gris]

tac, я чувствую родственную душу!
Я прочитал Ваше сообщение и сразу накарябал программку и стал смотреть, что там такое интересное. Потом начирикал сообщение, и только в конце его сообразил о возможности изменения одного элемента массива. Отправил, а оказывается это давным-давно обнаружил уважаемый AV_77! Приоритет открытия был утерян

Это вот такой подход: "Чего там думать, трясти надо."

У Вас та же ситуация. Судя по тому, с какой лёгкостью Вы меняете условия задачи, математичская модель фолдинга не продумана основательно. Сначала надо тщательнее формализовать задачу, и это часто значительно труднее, чем последующий анализ математической модели.

Ваш последний абзац звучит просто замечательно! Гораздо научнее, чем "Поди туда, не знаю куда."

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

[tac]

gris в сообщении #573285 писал(а):

Это вот такой подход: "Чего там думать, трясти надо."

У Вас та же ситуация. Судя по тому, с какой лёгкостью Вы меняете условия задачи, математичская модель фолдинга не продумана основательно. Сначала надо тщательнее формализовать задачу, и это часто значительно труднее, чем последующий анализ математической модели.

Математической модели фолдинга вообще нет (ни у кого нет). По поводу трести, я тут на хабре написал множество статей, вот последняя и в зависимости от желания покружаться там есть ссылка на предыдущие История одного реинжиниринга или RNAInSpace v.1.3. Demo.

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

"Например, что измениться если эти процедуры станут такими $x_{current}=x_{prev}+1$ или $x_{current}=x_{prev}-1$. Т.е. последующие число зависит от предыдущего. И еще кроме плюс/минус единицы может быть любое число."

Это хотелось бы обсудить подробнее.

Вы накидали программку? И как с ней экспериментируете, что поменяется если изменить эти условия. Идеи может какие есть.

[gris]

Да я в общем, себя имел в виду. Сама ситуация повеселила. Программка примитивная в пять строк. Просто меняет массив при вводе соответствующей команды. Отнюдь не поиск оптимальной последовательности процедур, что Вы. Это, я думаю, довольно сложный вопрос. Вот почему я не подумал, а сразу стал чего-то моделировать, это вот меня обеспокоило.

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

Что касается новых процедур, то они не очень хороши, так как значения изменённых элементов зависят только от значения первого изменяемого элемента. Например, $2_+$ после любой последовательности процедур возвращает первоначальное состояние массива. Это как-то не соответствует реальности.

[tac]

gris в сообщении #573296 писал(а):

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

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

Что касается новых процедур, то они не очень хороши, так как значения изменённых элементов зависят только от значения первого изменяемого элемента. Например, $2_+$ после любой последовательности процедур возвращает первоначальное состояние массива. Это как-то не соответствует реальности.

Да, нет - ни каких проблем, и скорее вы правы по поводу "родственных душ" :) И я вполне рад, добродушному разговору.

А вот по поводу не очень хороших процедур не очень понял. Действительно $2_+$ возвратит первоначальное состояние. Но можно же использовать другие наборы. Скажем $6_-$ последовательность 123456789 изменит на 1234554321. Т.е. имеем как бы веревку согнутую пополам. На этом то и можно сыграть. Хотя конечно для более сложных случаев этого будет мало.

[gris]

Я имел в виду, что в любой последовательности таких процедур любая процедура убивает результат предыдущих процедур с бОльшими номерами. То есть их можно смело вычеркнуть и любая актуальная последовательность процедур должна быть возрастающей по номеру. То есть $2_+; 4_+; 5_-.$ При этом первая же процедура убивает хвост массива, то есть генерирует его заново.
Это нехорошее свойство. Другое дело, что процедура может зависеть и от текущего и от предыдущего номера.
Два вопроса. Начальное состояние массива именно $1,2,3..n$ или могут быть варианты? Допустимы только целые значения?
Есть ли какие ограничения или требования к количеству процедур?
Насколько я знаю, в игровом фолдинге речь не идёт об оптимальности, лишь бы получить результат.

[tac]

gris в сообщении #573417 писал(а):

Я имел в виду, что в любой последовательности таких процедур любая процедура убивает результат предыдущих процедур с бОльшими номерами. То есть их можно смело вычеркнуть и любая актуальная последовательность процедур должна быть возрастающей по номеру. То есть $2_+; 4_+; 5_-.$ При этом первая же процедура убивает хвост массива, то есть генерирует его заново.
Это нехорошее свойство. Другое дело, что процедура может зависеть и от текущего и от предыдущего номера.
Два вопроса. Начальное состояние массива именно $1,2,3..n$ или могут быть варианты? Допустимы только целые значения?
Есть ли какие ограничения или требования к количеству процедур?
Насколько я знаю, в игровом фолдинге речь не идёт об оптимальности, лишь бы получить результат.

> любая процедура убивает результат предыдущих процедур с бОльшими номерами

Вот это и есть нужное и важное свойство. Именно так и происходит в реальности. Только тут пока упрощение, нужно несколько сложнее, не просто "убивает", а "связанно изменяет". Т.е. процедура $2_+.$ должна возвращать не в исходное положение, а несколько видоизмененное, зависящие от истории изменений. И наверное вариант "зависеть и от текущего и от предыдущего номера" - будет лучше. Тогда может $x_{current}=x_{current} + x_{prev} + 1$ или $x_{current}=x_{current} + x_{prev} - 1$ ? Будет лучше?

Начальное состояние массива лучше оставить $1,2,3..n$ - это как бы символизирует веревку вытянутую в линию. Как бы координаты по одной оси. Возможно нужно подумать о введении 3- мерности, но пока это очевидно не нужно будет - лучше не усложнять.

Работать можно с любыми числами, только целые значения более наглядны, но если это чему-то мешает - это легко можно изменить и работать с любыми.

Ограничений на число процедур нет ни каких, хотя конечно их лучше минимизировать. Я выбрал две - чтобы иметь возможно просто увеличивать и уменьшать числа. Скорее можно использовать скажем логарифм чего-то, и синус чего-то. Причем один со знаком плюс, а другой со знаком минус. Тогда просто будет сложно и не эффективно искать прямую и обратную процедуру. Т.е. вариант, что "последовательность двух процедур $8_+$ и $9_-$ просто увеличивает восьмой элемент массива на 1" - просто будет значительно затруднен.

И да тут важно получить результат, пусть равенство двух чисел в массиве, и если работать с не целыми числами, то не просто равенство, а приближение с заданной погрешностью.