20
правок
Изменения
→Почему алгоритм работает?
== Алгоритм получения цепного кода для двоичного вектора ==
Для получения цепного кода используется жадный алгоритм. Первое слово кода — слово, полностью состоящее из нулей. Образуя каждое следующее слово, мы сдвигаем предыдущее влево на один разряд, отбрасывая старший, затем добавляем в конец 1 и проверяем, не было ли такого слова раньше. Если было, то меняем последнюю единицу на ноль. Повторяем, пока снова не вернемся к первому слову
====Почему алгоритм работает?Доказательство корректности====
Требуется доказать, что алгоритм не повторит 2 слова в коде до того, как закончит цикл и то, что он переберет все возможные варианты.
Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на 1 и кончающиеся на 0.
Докажем, что 2-й группы нет.
Рассмотрим слово {ххabc..ххyz}0, не попавшее в код, где {abc.. Раз его нет в кодеyz} — некоторая последовательность 1 и 0. Рассмотрим два слова, то его конец которые могут быть от него образованы: {bc..yz}01 и {bc..yz}00. Они могли быть получены из слов {abc..yz}0 и {х(not a)bc..ххyz}0 . Но даже если второе слово встречается в коде, то в коде не может быть более одного разаиз рассматриваемых слов, значит аторого не может быть вообще (так как алгоритм по возможности добавляет 1, а следовательно слова не 0). То есть слово {xbc..xxyz}00 тоже нет в коде. Так эту цепочку можно продолжить до слова 00..000 и прийти к противоречию.
А раз 2-й группы нет, то не может быть и 1-й, так как если в коде есть слово, кончающееся на 0, то мы не можем получить его, если не было слова с таким же началом, но с единицей в конце.
