Изменения

[[Файл:chain4Chain4.png|thumb|right|Цепной код для двоичного вектора длиной 4]]'''Цепной код''' — код, состоящий из n-разрядных слов(англ. Следующее слово кода получается из предыдущего сдвигом на один разряд влево с отбрасыванием первого разряда и добавлением нуля или единицы в конец. Другое определение цепного кода ''chain code'') — это кодтакое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого есть циклический сдвиг (можно рассматривать как таблицу из <tex>2^n \times n</tex> элементов) получается из предыдущего циклическим сдвигом вверх на 1 разряд.

== Алгоритм получения цепного кода для двоичного вектора двоичных векторов ==Для получения цепного кода используется жадный алгоритм. Первон слово кода — слово, полностью состоящая из нулей. Образуя каждое следующее слово, мы сдвигаем предыдущее влево на один разряд, отбрасывая старший, затем добавляем в конец 1 и проверяем, не было ли такого слова раньше. Если было, то меняем последнюю единицу на ноль.====Почему алгоритм работает?====[[Файл:chainend.png|thumb|left|последние n строк цепного кода]]Во-первых, в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление 0 или 1) уже были использованы.Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.

Во-вторыхВ качестве первого вектора берём вектор из <tex>n</tex> нулей. Чтобы получить следующий вектор, берём последний добавленный вектор, мы пусть <tex>a_1\dots a_n</tex>. Если в коде до этого не сможем снова вернуться к слову из всех нулейвстречался вектор <tex>a_2\dots a_n 1</tex>, пока то добавляем его. Иначе проверяем на наличие в коде вектора <tex>a_2\dots a_n 0</tex>. Если такой не переберем все встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена. При таком построении видно, что элементы таблицы <mathtex>2a_1^i\dots a_1^{i+n}</tex> равны элементам <tex> a_1^i\dots a_n^i</tex> == Псевдокод алгоритма ==* <tex>\mathtt {current}</tex> — последний добавленный битовый вектор* <tex>\mathtt {result}</mathtex> слов— список битовых векторов  '''string[]''' chain_code('''int''' n): current = '0' * n result = [current] '''while''' ''true'' prefix = current[2..n] '''if''' prefix + '1' '''not in''' result current = prefix + '1' '''else''' prefix + '0' '''not in''' result current = prefix + '0' '''else''' '''break''' result.append(current) '''return''' result ==Доказательство корректности==Разобьем доказательство на две части:# Доказательство того, где что один и тот же вектор встречается в коде не более одного раза.# Доказательство того, что алгоритм перебирает все возможные вектора прежде, чем получит вектор из <tex>n </tex> нулей. ===Доказательство первого пункта===Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — длина словасгенерирован вектор из <tex>n</tex> нулей. Рассмотрим первое такое противоречие: последним добавлен вектор <tex>a_1 a_2 \dots a_n</tex>, вектора <tex>a_2 \dots 1</tex> и <tex>a_2 \dots a_n 0</tex> уже присутствуют в коде. Далее есть две возможных ситуации: вектор <tex>a_2 \dots a_n 0</tex> состоит из <tex>n</tex> нулей или предшествовал другому вектору в коде. Чтобы снова получить эту строкуВ первой ситуации алгоритм завершает работу. Во второй ситуации каждому из векторов <tex>a_2 \dots a_n 1</tex> и <tex>a_2 \dots a_n 0</tex> предшествовали некоторые вектора в коде, пусть <tex>B_1 = b_1 a_2 \dots a_n</tex> и <tex>B_2 = b_2 a_2 \dots a_n</tex>. Так как мы рассматриваем первое противоречие, то <tex>b_1 \neq b_2</tex>. Но в таком случае вектор <tex>a_1 a_2 \dots a_n</tex> совпадает с одним из векторов <tex>B_1</tex> или <tex>B_2</tex>. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации. ===Доказательство второго пункта=== Покажем, что до генерации вектора из <tex>n</tex> нулей генерируются все остальные битовые вектора. Допустим, мы должны будем перебрать всё же получили вектор из всех нулей раньше, чем перебрали все строкивектора. Тогда рассмотрим множество векторов <tex>Z</tex>, которые не были сгенерированы алгоритмом и оканчиваются на ноль. Пусть <tex>a_1 a_2 \dots a_{n - 1} 0 \in Z</tex>. Докажем, в которых есть что <tex>a_2 \dots a_{n - 1} 0 0 \in Z</tex>. От противного, тк мы пусть вектор <tex>a_2 \dots a_{n - 1} 0 0 </tex> был сгенерирован. Тогда ему предшествовал вектор <tex>b_1 a_2 \dots a_{n - 1} 0</tex>. Так как по возможности добавляем именно 1предположению <tex>b_1 \neq a_1</tex>, то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только <tex>a_2 \dots a_{n - 1} 0 только 1</tex>. Значит, если такое число множество <tex>Z</tex> непусто, то оно содержит вектор из <tex>n</tex> нулей. Но это противоречит тому, что вектор из <tex>n</tex> нулей был сгенерирован. Следовательно, это предположение не верно и все вектора с нулём в последней позиции были сгенерированы. Пусть был сгенерирован вектор <tex>a_1 \dots a_{n - 1} 0</tex>. Ему предшествовал некоторый вектор <tex>b_1 a_1 \dots a_{n - 1}</tex>. Так как алгоритм сначала пытается поместить в код вектор <tex>a_1 \dots a_{n - 1} 1</tex>, то на этом шаге вектор <tex>a_1 \dots a_{n - 1} 1</tex> уже былоприсутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида <tex>a_1 \dots a_{n - 1} 0</tex> был добавлен в код, а значит, и вектор вида <tex>a_1 \dots a_{n - 1} 1 </tex> также был добавлен в код. Таким образом, все двоичные вектора присутсвуют в сгенерированном коде. == См. также == *[[Коды Грея]]*[[Коды антигрея]]*[[Коды Грея для перестановок]] == Источники информации ==*[http://en.wikipedia.org/wiki/Chain_code Wikipedia {{---}} Chain code]  [[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]]