Викиконспекты - Вклад участника [ru]

Счётчик Кнута

2014-03-03T18:52:30Z

178.70.112.21:

'''Счетчик Кнута''' (англ. ''Knuth's Counter'') - структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к любому разряду выполняется за <tex>O(1)</tex>.

''Избыточная двоичная система счисления'' - двоичная система счисления, где кроме 0 и 1 допустима 2 в записи числа.
== Алгоритм ==
''Примечание: этот алгоритм работает не за истинное <tex>O(1)</tex>. Например, чтобы прибавить 1 к 0111...111, нужно <tex>O(n)</tex> действий.''

Имеется число, записанное в избыточной двоичной системе счисления, необходимо добавить 1 к какому-либо разряду. Будем поддерживать следующий инвариант: в следующем за любой двойкой разряде всегда стоит 0.

Разберем случаи добавления единицы:
* a) Если 1 нужно добавить к 2, то в текущем разряде установить 1, в следующем 1.
* б) Если 1 нужно добавить к 1 и в следующем разряде 0, то в текущем разряде установить 2.
* в) Если 1 нужно добавить к 1 и в следующем разряде 1, то в текущем разряде установить 0, повторить алгоритм для следующего разряда.
* г) Если 1 нужно добавить к 1 и в следующем разряде 2, то в следующем за двойкой разряде установить 1, в разряде с двойкой установить 1, в текущем установить 0.
* д) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 0, то в предыдущем разряде установить 0, в текущем 2.
* е) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 1, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
* ж) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 2, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
* з) Если 1 нужно добавить к 0 и в предыдущем разряде не 2, установить в текущем разряде 1.

== Доказательство ==
Покажем, что инвариант не нарушится.

Инвариант можно нарушить в 2 случаях: когда к единице прибавляют 1, и в следующем разряде стоит не 0, и когда к нулю прибавляется 1, а в предыдущем разряде стоит 2.

В первом случае, если в следующем разряде 1, алгоритм будет устанавливать в текущий разряд 0 и запускаться от следующего разряда. Если в следующем разряде 2, то, согласно инварианту, следующий за 2 разряд 0, и, если установить в следующий за двойкой и в разряд с двойкой единицы, то инвариант не нарушится.

Во втором случае, если в следующем разряде 0, то предыдущий установится в 0, текущий в 2 и так как в следующем 0 инвариант не нарушится. Если в следующем разряде не 0, то предыдущий установится в 0 и алгоритм запустится от следующего.

== Пример ==
Рассмотрим пример для каждого варианта, добавление 1 происходит в 3 разряд.

а) <tex>200_{2} \Rightarrow 1100_{2}</tex>

б) <tex>0100_{2} \Rightarrow 0200_{2}</tex>

в) <tex>1100_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>

г) <tex>2100_{2} \Rightarrow 11000_{2}</tex>

д) <tex>10020_{2} \Rightarrow 10200_{2}</tex>

е) <tex>1020_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>

ж) <tex>2020_{2} \Rightarrow 2000_{2}</tex> повторение алгоритма для 4 разряда, по варианту а <tex>2000_{2} \Rightarrow 11000_{2}</tex>

з) <tex>010_{2} \Rightarrow 110_{2}</tex>

== Амортизационная оценка алгоритма ==
Воспользуемся методом предоплаты. Будем считать, что каждый раз когда мы начинаем выполнять алгоритм мы берем 2 монетки. Одна будет тратится на изменение текущего разряда и одна запасаться. Таким образом, если в разряде стоит 1, то для него запасена 1 монетка, если стоит 2, то запасено 2 монетки. Проверим все варианты.

а) Так как в текущем разряде было 2, то уже запасено 2 монеты, а так же согласно инварианту после 2 стоит 0, тогда возьмем одну из запасенных у двойки монет и потратим их на присвоение следующему разряду 1, вторую запасенную передадим этой единице. Одну монету потратим на установку в текущий разряд 1, вторую запасем для это единицы.

б) Так как в текущем разряде было 1, то прибавим наши монеты к уже запасенной от единицы. Одну монету потратим, что бы установить 2, останется 2 монеты.

в) Так как в текущем разряде было 1, то прибавив наши монеты к запасенной получим 3. Одну монету потратим, что бы установить 0, оставшиеся 2 потратим на повторение алгоритма для следующего разряда.

г) Так как в текущем разряде было 1, в следующем 2, то уже запасено 3 монеты и еще 2 наши. 3 монеты потратим, что бы следующему за 2 разряду установить 1, разряду с 2 установить 1, текущему установить 0. Останется 2 монеты, которые распределятся между двумя единицами.

д) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 0, то уже запасено 2 монеты. Одну монету потратим на изменение предыдущего разряда, одну на изменение текущего разряда, наши две монеты запасем для двойки в текущем разряде.

е) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 1, то уже запасено 3 монеты. Одну монету потратим на изменение предыдущего разряда, одну сохраним с единицей, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.

ж) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 2, то уже запасено 4 монеты. Одну монету потратим на изменение предыдущего разряда, две сохраним с двойкой, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.

з) Одну монету потратим на изменение разряда, оставшуюся запасем с единицей.

Получается 2 монет достаточно для прибавления 1 к любому разряду, тогда наш алгоритм работает в среднем за <tex>O(1)</tex>

== Смотри также ==
* [[Амортизационный анализ]]
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Счётчик Кнута

2014-03-03T17:12:26Z

178.70.112.21: /* Алгоритм */

'''Счетчик Кнута''' (англ. ''Knuth's Counter'') - структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к любому разряду выполняется за <tex>O(1)</tex>.

''Избыточная двоичная система счисления'' - двоичная система счисления, где кроме 0 и 1 допустима 2 в записи числа.
== Алгоритм ==
''Примечание: этот алгоритм работает на за истинное <tex>O(1)</tex>. Например, чтобы прибавить 1 к 0111...111, нужно <tex>O(n)</tex> действий.''

Имеется число, записанное в избыточной двоичной системе счисления, необходимо добавить 1 к какому-либо разряду. Будем поддерживать следующий инвариант: в следующем за любой двойкой разряде всегда стоит 0.

Разберем случаи добавления единицы:
* a) Если 1 нужно добавить к 2, то в текущем разряде установить 1, в следующем 1.
* б) Если 1 нужно добавить к 1 и в следующем разряде 0, то в текущем разряде установить 2.
* в) Если 1 нужно добавить к 1 и в следующем разряде 1, то в текущем разряде установить 0, повторить алгоритм для следующего разряда.
* г) Если 1 нужно добавить к 1 и в следующем разряде 2, то в следующем за двойкой разряде установить 1, в разряде с двойкой установить 1, в текущем установить 0.
* д) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 0, то в предыдущем разряде установить 0, в текущем 2.
* е) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 1, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
* ж) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 2, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
* з) Если 1 нужно добавить к 0 и в предыдущем разряде не 2, установить в текущем разряде 1.

== Доказательство ==
Покажем, что инвариант не нарушится.

Инвариант можно нарушить в 2 случаях: когда к единице прибавляют 1, и в следующем разряде стоит не 0, и когда к нулю прибавляется 1, а в предыдущем разряде стоит 2.

В первом случае, если в следующем разряде 1, алгоритм будет устанавливать в текущий разряд 0 и запускаться от следующего разряда. Если в следующем разряде 2, то, согласно инварианту, следующий за 2 разряд 0, и, если установить в следующий за двойкой и в разряд с двойкой единицы, то инвариант не нарушится.

Во втором случае, если в следующем разряде 0, то предыдущий установится в 0, текущий в 2 и так как в следующем 0 инвариант не нарушится. Если в следующем разряде не 0, то предыдущий установится в 0 и алгоритм запустится от следующего.

== Пример ==
Рассмотрим пример для каждого варианта, добавление 1 происходит в 3 разряд.

а) <tex>200_{2} \Rightarrow 1100_{2}</tex>

б) <tex>0100_{2} \Rightarrow 0200_{2}</tex>

в) <tex>1100_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>

г) <tex>2100_{2} \Rightarrow 11000_{2}</tex>

д) <tex>10020_{2} \Rightarrow 10200_{2}</tex>

е) <tex>1020_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>

ж) <tex>2020_{2} \Rightarrow 2000_{2}</tex> повторение алгоритма для 4 разряда, по варианту а <tex>2000_{2} \Rightarrow 11000_{2}</tex>

з) <tex>010_{2} \Rightarrow 110_{2}</tex>

== Амортизационная оценка алгоритма ==
Воспользуемся методом предоплаты. Будем считать, что каждый раз когда мы начинаем выполнять алгоритм мы берем 2 монетки. Одна будет тратится на изменение текущего разряда и одна запасаться. Таким образом, если в разряде стоит 1, то для него запасена 1 монетка, если стоит 2, то запасено 2 монетки. Проверим все варианты.

а) Так как в текущем разряде было 2, то уже запасено 2 монеты, а так же согласно инварианту после 2 стоит 0, тогда возьмем одну из запасенных у двойки монет и потратим их на присвоение следующему разряду 1, вторую запасенную передадим этой единице. Одну монету потратим на установку в текущий разряд 1, вторую запасем для это единицы.

б) Так как в текущем разряде было 1, то прибавим наши монеты к уже запасенной от единицы. Одну монету потратим, что бы установить 2, останется 2 монеты.

в) Так как в текущем разряде было 1, то прибавив наши монеты к запасенной получим 3. Одну монету потратим, что бы установить 0, оставшиеся 2 потратим на повторение алгоритма для следующего разряда.

г) Так как в текущем разряде было 1, в следующем 2, то уже запасено 3 монеты и еще 2 наши. 3 монеты потратим, что бы следующему за 2 разряду установить 1, разряду с 2 установить 1, текущему установить 0. Останется 2 монеты, которые распределятся между двумя единицами.

д) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 0, то уже запасено 2 монеты. Одну монету потратим на изменение предыдущего разряда, одну на изменение текущего разряда, наши две монеты запасем для двойки в текущем разряде.

е) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 1, то уже запасено 3 монеты. Одну монету потратим на изменение предыдущего разряда, одну сохраним с единицей, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.

ж) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 2, то уже запасено 4 монеты. Одну монету потратим на изменение предыдущего разряда, две сохраним с двойкой, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.

з) Одну монету потратим на изменение разряда, оставшуюся запасем с единицей.

Получается 2 монет достаточно для прибавления 1 к любому разряду, тогда наш алгоритм работает в среднем за <tex>O(1)</tex>

== Смотри также ==
* [[Амортизационный анализ]]
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Счётчик Кнута

2014-03-03T17:08:28Z

178.70.112.21: /* Алгоритм */

'''Счетчик Кнута''' (англ. ''Knuth's Counter'') - структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к любому разряду выполняется за <tex>O(1)</tex>.

''Избыточная двоичная система счисления'' - двоичная система счисления, где кроме 0 и 1 допустима 2 в записи числа.
== Алгоритм ==
''Примечание: этот алгоритм работает не за <tex>O(1)</tex>. Например, чтобы прибавить 1 к 0111...111, нужно <tex>O(n)</tex> действий.''

Имеется число, записанное в избыточной двоичной системе счисления, необходимо добавить 1 к какому-либо разряду. Будем поддерживать следующий инвариант: в следующем за любой двойкой разряде всегда стоит 0.

Разберем случаи добавления единицы:
* a) Если 1 нужно добавить к 2, то в текущем разряде установить 1, в следующем 1.
* б) Если 1 нужно добавить к 1 и в следующем разряде 0, то в текущем разряде установить 2.
* в) Если 1 нужно добавить к 1 и в следующем разряде 1, то в текущем разряде установить 0, повторить алгоритм для следующего разряда.
* г) Если 1 нужно добавить к 1 и в следующем разряде 2, то в следующем за двойкой разряде установить 1, в разряде с двойкой установить 1, в текущем установить 0.
* д) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 0, то в предыдущем разряде установить 0, в текущем 2.
* е) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 1, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
* ж) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 2, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
* з) Если 1 нужно добавить к 0 и в предыдущем разряде не 2, установить в текущем разряде 1.

== Доказательство ==
Покажем, что инвариант не нарушится.

Инвариант можно нарушить в 2 случаях: когда к единице прибавляют 1, и в следующем разряде стоит не 0, и когда к нулю прибавляется 1, а в предыдущем разряде стоит 2.

В первом случае, если в следующем разряде 1, алгоритм будет устанавливать в текущий разряд 0 и запускаться от следующего разряда. Если в следующем разряде 2, то, согласно инварианту, следующий за 2 разряд 0, и, если установить в следующий за двойкой и в разряд с двойкой единицы, то инвариант не нарушится.

Во втором случае, если в следующем разряде 0, то предыдущий установится в 0, текущий в 2 и так как в следующем 0 инвариант не нарушится. Если в следующем разряде не 0, то предыдущий установится в 0 и алгоритм запустится от следующего.

== Пример ==
Рассмотрим пример для каждого варианта, добавление 1 происходит в 3 разряд.

а) <tex>200_{2} \Rightarrow 1100_{2}</tex>

б) <tex>0100_{2} \Rightarrow 0200_{2}</tex>

в) <tex>1100_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>

г) <tex>2100_{2} \Rightarrow 11000_{2}</tex>

д) <tex>10020_{2} \Rightarrow 10200_{2}</tex>

е) <tex>1020_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>

ж) <tex>2020_{2} \Rightarrow 2000_{2}</tex> повторение алгоритма для 4 разряда, по варианту а <tex>2000_{2} \Rightarrow 11000_{2}</tex>

з) <tex>010_{2} \Rightarrow 110_{2}</tex>

== Амортизационная оценка алгоритма ==
Воспользуемся методом предоплаты. Будем считать, что каждый раз когда мы начинаем выполнять алгоритм мы берем 2 монетки. Одна будет тратится на изменение текущего разряда и одна запасаться. Таким образом, если в разряде стоит 1, то для него запасена 1 монетка, если стоит 2, то запасено 2 монетки. Проверим все варианты.

а) Так как в текущем разряде было 2, то уже запасено 2 монеты, а так же согласно инварианту после 2 стоит 0, тогда возьмем одну из запасенных у двойки монет и потратим их на присвоение следующему разряду 1, вторую запасенную передадим этой единице. Одну монету потратим на установку в текущий разряд 1, вторую запасем для это единицы.

б) Так как в текущем разряде было 1, то прибавим наши монеты к уже запасенной от единицы. Одну монету потратим, что бы установить 2, останется 2 монеты.

в) Так как в текущем разряде было 1, то прибавив наши монеты к запасенной получим 3. Одну монету потратим, что бы установить 0, оставшиеся 2 потратим на повторение алгоритма для следующего разряда.

г) Так как в текущем разряде было 1, в следующем 2, то уже запасено 3 монеты и еще 2 наши. 3 монеты потратим, что бы следующему за 2 разряду установить 1, разряду с 2 установить 1, текущему установить 0. Останется 2 монеты, которые распределятся между двумя единицами.

д) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 0, то уже запасено 2 монеты. Одну монету потратим на изменение предыдущего разряда, одну на изменение текущего разряда, наши две монеты запасем для двойки в текущем разряде.

е) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 1, то уже запасено 3 монеты. Одну монету потратим на изменение предыдущего разряда, одну сохраним с единицей, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.

ж) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 2, то уже запасено 4 монеты. Одну монету потратим на изменение предыдущего разряда, две сохраним с двойкой, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.

з) Одну монету потратим на изменение разряда, оставшуюся запасем с единицей.

Получается 2 монет достаточно для прибавления 1 к любому разряду, тогда наш алгоритм работает в среднем за <tex>O(1)</tex>

== Смотри также ==
* [[Амортизационный анализ]]
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]