1. Не знаю. Это имеет отношение к insertion-deletion codes, кажется.

2. Random coding bound в теории информации и кодирования это оценка сверху ошибки оптимального алгоритма кодирования, получаемая случайным выбором кодовых слов в соответствии с условным распределением символов на выходе при заданном символе на входе, при котором достигается минимум в определении rate-distortion function (функция зависимости скорости передачи от искажения) по Шеннону для данного канала. Идея здесь такая: при случайном выборе кода существует по крайней мере один код, средняя ошибка которого не превосходит своего математического ожидания по случайному выбору кодов, и в любом случае оптимальный код будет давать ошибку не больше этой.

3. Несомненно.

4. -

(Reply to this) (Thread)

1. Бывает и просто для строк символов. Иногда применяется и для цепочек ДНК. Смысл в том, что подобие двух строк количественно измеряется как минимальную длину последовательности преобразований из заданного класса (например, вставок и удалений символов, применительно к текстовым строкам туда же включают замены), путем которых одну строку можно превратить в другую. Русского термина, впрочем, не знаю.

(Reply to this) (Parent) (Thread)

Ага, если это и в самом деле то, то называется оно "метрика (или расстояние) Левенштейна".

(Reply to this) (Parent) (Thread)

Не совсем. Расстояние Левенштейна оно только в том случае, если класс преобразований состоит из вставок, удалений и замен. Если разрешены только удаления, то нет, и не для всякой пары строк оно определено. Если разрешены удаления и вставки, то определено везде, но все равно не расстояние Левенштейна. По крайней мере, в его классическом определении.

(Reply to this) (Parent) (Thread)

Спасибо - именно об этом речь, да. Жаль, что не знаете
русского термина! А вот верно ли, что при известной
функции подобия S в ДНК-кодах можно скорректировать
n - 1 + S ошибок, где n - длина слова? Как вообще
корректируют ошибки в ДНК-кодах? И что такое
скорость кода в случае ДНК-кодов (там какое-то
странное определение в статье, которую держу в руках),
и зачем ее оценивать с помощью random coding bound,
если уже известно, что это ДНК-код?

(Reply to this) (Parent) (Thread)

Я ничего этого не знаю! Это у меня остатки общей программистской культуры. В середине 80х было помешательство, что ЯП должны уметь сами восстанавливаться при очепятках в ключевых словах. Про ДНК мне самому интересно.

(Reply to this) (Parent)

Спасибо большое, это отлично!

(Reply to this) (Parent)

3. А нельзя ли сразу убить сами корпоративные ценности? А то очень зае.

(Reply to this) (Thread)

К сожалению, Природа не терпит пустоты.

(Reply to this) (Parent)