Цепные коды — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод алгоритма)
Строка 4: Строка 4:
 
== Алгоритм получения цепного кода для двоичных векторов ==
 
== Алгоритм получения цепного кода для двоичных векторов ==
  
В качестве первого вектора берём вектор из <tex>n</tex> нулей. Чтобы получить следующий вектор, берём последний добавленный вектор, пусть <tex>a_1\cdots a_n</tex>. Если в коде до этого не встречатся вектор <tex>a_2\cdots a_n 1</tex>, то добавляем его. Иначе проверяем на наличие в коде вектора <tex>a_2\cdots a_n 0</tex>. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.
+
В качестве первого вектора берём вектор из <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>. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.
  
 
== Псевдокод алгоритма ==
 
== Псевдокод алгоритма ==
Строка 30: Строка 30:
  
 
===Доказательство первого пункта===
 
===Доказательство первого пункта===
Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из <tex>n</tex> нулей. Рассмотрим первое такое противоречие: последним добавлен вектор <tex>a_1 a_2 \cdots a_n</tex>, вектора <tex>a_2 \cdots 1</tex> и <tex>a_2 \cdots a_n 0</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 \cdots a_n 0</tex> состоит из <tex>n</tex> нулей или предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу.
+
Далее есть две возможных ситуации: вектор <tex>a_2 \dots a_n 0</tex> состоит из <tex>n</tex> нулей или предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу.
  
Во второй сутиации каждому из векторов <tex>a_2 \cdots a_n 1</tex> и <tex>a_2 \cdots a_n 0</tex> предшествовали некоторые вектора в коде, пусть <tex>B_1 = b_1 a_2 \cdots a_n</tex> и <tex>B_2 = b_2 a_2 \cdots a_n</tex>. Так как мы рассматриваем первое противоречие, то <tex>b_1 \neq b_2</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 \cdots a_n</tex> совпадает с одним из векторов <tex>B_1</tex> или <tex>B_2</tex>. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации.
+
Но в таком случае вектор <tex>a_1 a_2 \dots a_n</tex> совпадает с одним из векторов <tex>B_1</tex> или <tex>B_2</tex>. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации.
  
 
===Доказательство второго пункта===
 
===Доказательство второго пункта===
Строка 42: Строка 42:
 
Покажем, что до генерации веткора из <tex>n</tex> нулей генерируются все остальные битовые вектора. Допустим, мы всё же получили вектор из всех нулей раньше, чем перебрали все вектора. Тогда рассмотрим множество векторов <tex>Z</tex>, которые не были сгенерированы алгоритмом и оканчиваются на ноль.
 
Покажем, что до генерации веткора из <tex>n</tex> нулей генерируются все остальные битовые вектора. Допустим, мы всё же получили вектор из всех нулей раньше, чем перебрали все вектора. Тогда рассмотрим множество векторов <tex>Z</tex>, которые не были сгенерированы алгоритмом и оканчиваются на ноль.
  
Пусть <tex>a_1 a_2 \cdots a_{n - 1} 0 \in Z</tex>. Докажем, что <tex>a_2 \cdots a_{n - 1} 0 \in Z</tex>. От противного, пусть вектор <tex>a_2 \cdots a_{n - 1} 0 0 </tex> был сгенерирован. Тогда ему предшествовал вектор <tex>b_1 a_2 \cdots a_{n - 1} 0</tex>. Так как по предположению <tex>b_1 \neq a_1</tex>, то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только <tex>a_2 \cdots a_{n - 1} 0 1</tex>.
+
Пусть <tex>a_1 a_2 \dots a_{n - 1} 0 \in Z</tex>. Докажем, что <tex>a_2 \dots a_{n - 1} 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>. Так как по предположению <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>Z</tex> непусто, то оно содержит вектор из <tex>n</tex> нулей. Но это противоречит тому, что вектор из <tex>n</tex> нулей был сгенерирован. Следовательно, это предположение не верно и все вектора с нулём в последней позиции были сгенерированы.
  
Пусть был сгенерирован вектор <tex>a_1 \cdots a_{n - 1} 0</tex>. Ему предествовал некоторый вектор <tex>b_1 a_1 \cdots a_{n - 1}</tex>. Так как алгоритм сначала пытается поместить в код вектор <tex>a_1 \cdots a_{n - 1} 1</tex>, то на этом шаге вектор <tex>a_1 \cdots a_{n - 1} 1</tex> уже присутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида <tex>a_1 \cdots a_{n - 1} 0</tex> был добавлен в код, а значит, и вектор вида <tex>a_1 \cdots a_{n - 1} 1 </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> также был добавлен в код. Таким образом, все двоичные вектора присутсвуют в сгенерированном коде.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Версия 15:58, 23 декабря 2014

Chain4.png

Цепной код (англ: chain code) — это такое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого (можно рассматривать как таблицу из [math]2^n \times n[/math] элементов) получается из предыдущего циклическим сдвигом вверх.

Алгоритм получения цепного кода для двоичных векторов

В качестве первого вектора берём вектор из [math]n[/math] нулей. Чтобы получить следующий вектор, берём последний добавленный вектор, пусть [math]a_1\dots a_n[/math]. Если в коде до этого не встречатся вектор [math]a_2\dots a_n 1[/math], то добавляем его. Иначе проверяем на наличие в коде вектора [math]a_2\dots a_n 0[/math]. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.

Псевдокод алгоритма

  • current — последний добавленный битовый вектор
  • result — список битовых векторов
chain_code(n):
  current = string('0', n)
  result = [current]
  while (true):
    prefix = current.substring(2, n)
    if concat(prefix, '1') not in result:
      current = concat(prefix, '1')
    else concat(prefix, '0') not in result:
      current = concat(prefix, '0')
    else:
      break
    result.append(current)
  return result

Доказательство корректности

Разобьем доказательство на две части:

  1. Доказательство того, что один и тот же вектор встречается в коде не более одного раза.
  2. Доказательство того, что алгоритм перебирает все возможные вектора прежде, чем получит вектор из [math]n[/math] нулей.

Доказательство первого пункта

Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из [math]n[/math] нулей. Рассмотрим первое такое противоречие: последним добавлен вектор [math]a_1 a_2 \dots a_n[/math], вектора [math]a_2 \dots 1[/math] и [math]a_2 \dots a_n 0[/math] уже присутствуют в коде.

Далее есть две возможных ситуации: вектор [math]a_2 \dots a_n 0[/math] состоит из [math]n[/math] нулей или предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу.

Во второй сутиации каждому из векторов [math]a_2 \dots a_n 1[/math] и [math]a_2 \dots a_n 0[/math] предшествовали некоторые вектора в коде, пусть [math]B_1 = b_1 a_2 \dots a_n[/math] и [math]B_2 = b_2 a_2 \dots a_n[/math]. Так как мы рассматриваем первое противоречие, то [math]b_1 \neq b_2[/math].

Но в таком случае вектор [math]a_1 a_2 \dots a_n[/math] совпадает с одним из векторов [math]B_1[/math] или [math]B_2[/math]. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации.

Доказательство второго пункта

Покажем, что до генерации веткора из [math]n[/math] нулей генерируются все остальные битовые вектора. Допустим, мы всё же получили вектор из всех нулей раньше, чем перебрали все вектора. Тогда рассмотрим множество векторов [math]Z[/math], которые не были сгенерированы алгоритмом и оканчиваются на ноль.

Пусть [math]a_1 a_2 \dots a_{n - 1} 0 \in Z[/math]. Докажем, что [math]a_2 \dots a_{n - 1} 0 \in Z[/math]. От противного, пусть вектор [math]a_2 dots a_{n - 1} 0 0 [/math] был сгенерирован. Тогда ему предшествовал вектор [math]b_1 a_2 \dots a_{n - 1} 0[/math]. Так как по предположению [math]b_1 \neq a_1[/math], то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только [math]a_2 \dots a_{n - 1} 0 1[/math].

Значит, если множество [math]Z[/math] непусто, то оно содержит вектор из [math]n[/math] нулей. Но это противоречит тому, что вектор из [math]n[/math] нулей был сгенерирован. Следовательно, это предположение не верно и все вектора с нулём в последней позиции были сгенерированы.

Пусть был сгенерирован вектор [math]a_1 \dots a_{n - 1} 0[/math]. Ему предествовал некоторый вектор [math]b_1 a_1 \dots a_{n - 1}[/math]. Так как алгоритм сначала пытается поместить в код вектор [math]a_1 \dots a_{n - 1} 1[/math], то на этом шаге вектор [math]a_1 \dots a_{n - 1} 1[/math] уже присутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида [math]a_1 \dots a_{n - 1} 0[/math] был добавлен в код, а значит, и вектор вида [math]a_1 \dots a_{n - 1} 1 [/math] также был добавлен в код. Таким образом, все двоичные вектора присутсвуют в сгенерированном коде.