SICP по-русски

Comment from Sergey Khenkin
Date: January 26, 2008, 7:27 pm

Очень симпатичную попытку обоснования того, почему порядок расположения номиналов монет в списке не влияет на результат вычисления количества способов размена, пытается привести Эли Бендерски у себя на странице http://eli.thegreenplace.net/2007/08/10/sicp-section-221/.

Его идея заключается в том, чтобы рассмотреть дерево рекурсии вызовов процедуры cc до глубины 2 (то есть первые два уровня рекурсии). Пусть нам нужно разменять сумму N монетами номиналов a, b, c, …, z.
Тогда дерево вызовов процедуры cc можно описать схематично так:

(N; a, b, c, ..., z)
|
+-- (N; b, c, ..., z)
|   |
|   +-- (N; c, ..., z)
|   |
|   +-- (N-b; b, c, ..., z)
|
+-- (N-a; a, b, c, ..., z)
    |
    +-- (N-a; b, c, ..., z)
    |
    +-- (N-a-a; a, b, c, ..., z)

К сожалению, Эли делает небольшую ошибку (скорее всего, играет свою пагубную роль wishful thinking) и записывает последнюю строчку как (N-a-b; a, b, c, …, z), после чего утверждает, что полученные 4 результата симметричны относительно a и b, то есть их можно переставить и ничего не поменяется.
Очень красивое доказательство, но, к сожалению, с ошибкой.

Мне кажется, для доказательства отсутствия влияния порядка следования номиналов на результат достаточно доказательства корректности применяемого алгоритма, так как это автоматически исключает два разных решения одной и той же задачи (ведь число ваирантов размена очевидно не может зависеть от порядка номиналов).

Comment from gorilych
Date: July 19, 2008, 7:32 am

Лемма. Пусть C(S, a_0, a_1, .., a_n) – количество способов размена суммы S монетами номиналов a_0, a_1, .., a_n. Тогда

C(S, a_0, a_1, .., a_n) = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)

Доказательство<<<<<<<< расширенный набор входит в L. При этом он содержит добавленную монету номиналом a_0 => входит в L1. При убирании монеты номиналом a_0, получим исходный набор и при этом по способу построения L1′ он будет туда входить – противоречие.

Таким образом, мощность L1 = мощность L1` = C(S – a_0, a_0, a_1, .., a_n)

C(S, a_0, a_1, .., a_n) = мощность L = Мощность L2 + мощность L1 = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)

чтд
>>>>>>>>>>

Доказанная лемма показывает, что способ разветвления в алгоритме правилен

Докажем теперь следующее утверждение: алгоритм, используемый в задаче, корректен, то есть находит все возможные варианты и при этом не учитывает один и тот же вариант более одного раза.

Доказательство методом индукции по количеству номиналов монет n для набора произвольной суммы S.<<<<<<<<<

При n = 1 утверждение доказывается элементарно. Алгоритм отнимает от S номинал монеты, пока не дойдёт до нуля, либо до отрицательного числа. Первое означает, что S кратно номиналу, имеется один единственный вариант и возвращается 1. Во втором случае алгоритм вернёт 0, поскольку S не делится на номинал нацело. При подсчёте алгоритм не разветвляется, поскольку второй вызов сразу возвращает ноль для пустого списка.

Допустим, что утверждение верно для n номиналов. Докажем его для n + 1.

пусть k = S mod a_0

алгоритм подсчёта C(S, a_0, a_1, .., a_n) рекурсивно вызывает сам себя для подсчёта

C(S, a_1, .., a_n), C(S – a_0, a_0, a_1, .., a_n);
C(S – a_0, a_1, .., a_n), C(S – a_0 – a_0, a_0, a_1, .., a_n);
C(S – a_0 – a_0 – a_0, a_0, a_1, .., a_n), C(S – a_0 – a_0 – a_0, a_1, .., a_n);
…
C(S – (k-2)*a_0, a_1, .., a_n), C(S – (k-1)*a_0, a_0, a_1, .., a_n);
C(S – (k-1)*a_0, a_1, .., a_n), C(S – k*a_0, a_0, a_1, .., a_n);
C(S – k*a_0, a_1, .., a_n), C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n)

Поскольку [S – (k+1)*a_0] = 0, то алгоритм обрубается:

– либо на подсчёте C(S – k*a_0, a_0, a_1, .., a_n), при [S – k*a_0] = 0
– либо на подсчёте C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n), при [S – k*a_0] > 0

Корректность вычисления каждой суммы зависит от корректности вычисления последующих, что следует из леммы.

Корректность вычисления каждой C(S – j*a_0, a_1, .., a_n) вытекает из предположения индукции.

Следовательно, нам нужно доказать только корректность вычисления C(S – (k-1)*a_0, a_0, a_1, .., a_n), поскольку из этого следует по цепочке корректность вычисления всех остальных сумм вида C(S – j*a_0, a_0, a_1, .., a_n) вплоть до C(S, a_0, a_1, .., a_n).

Возможны два случая:

1) [S – k*a_0] = 0

Тогда [S – (k-1)*a_0] = a_0, C(S – (k-1)*a_0, a_0, a_1, .., a_n) = C(a_0, a_0, a_1, .., a_n).

Множество L1, обсуждаемое в лемме, состоит всего из одного набора, в который включается одна монета номиналом a_0. Следовательно

C(a_0, a_0, a_1, .., a_n) = 1 + C(a_0, a_1, .., a_n). Вспомним при этом, что именно 1 возвращает алгоритм, в случае равенства нулю передаваемой ему суммы (а ему и передастся [a_0 – a_0] = 0). Ну а подсчёт C(a_0, a_1, .., a_n) опять же корректен по предположению индукции.

2) [S – k*a_0] > 0.

При этом [S – (k+1)*a_0] [S – k*a_0] … C(S – j*a_0, a_0, a_1, .., a_n) … => подсчёт C(S, a_0, a_1, .., a_n) корректен

чтд
>>>>>>>>>>

Comment from gorilych
Date: July 19, 2008, 7:35 am

Зря я угловых скобок напихал…

Ещё раз. ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ АЛГОРИТМА

Лемма. Пусть C(S, a_0, a_1, .., a_n) – количество способов размена суммы S монетами номиналов a_0, a_1, .., a_n. Тогда

C(S, a_0, a_1, .., a_n) = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)

Доказательство
==============

Очевидно, что множество всевозможных различных наборов монет L, составлющих сумму S, можно разделить на два непересекающихся подмножества – подмножество L1 наборов, содержащих монету номиналом a_0, и подмножество L2, без монет с таким номиналом. Действительно, в наборе либо есть, либо нету такой монеты, поэтому нет такого набора, который входит одновременно в оба подмножества и поэтому они не пересекающиеся. Следовательно мощность множества L равна сумме мощностей подмножеств.

Мощность L2 равна C(S, a_1, .., a_n), поскольку любой набор из монет a_1, .., a_n с суммой S входит в L и при том входит в L2, поскольку не содержит монет с номиналом a_0.

Поскольку каждый набор в L1 содержит хотя бы одну монету номинала a_0 то из L1 можно получить равномощное множество L1′, убрав из каждого набора по одной монете ном. a_0. При этом сумма каждого набора уменьшится на величину номинала и будет равна (S – a_0).

Покажем от противного, что L1′ содержит все возможные наборы монет номиналами a_0, a_1, .., a_n с суммой (S – a_0). Пусть есть такой набор, не входящий в L1′, сумма которого равна (S – a_0). Добавим к этому набору монету номиналом a_0. Сумма набора станет равной S => расширенный набор входит в L. При этом он содержит добавленную монету номиналом a_0 => входит в L1. При убирании монеты номиналом a_0, получим исходный набор и при этом по способу построения L1′ он будет туда входить – противоречие.

Таким образом, мощность L1 = мощность L1` = C(S – a_0, a_0, a_1, .., a_n)

C(S, a_0, a_1, .., a_n) = мощность L = Мощность L2 + мощность L1 = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)

чтд
==============

Доказанная лемма показывает, что способ разветвления в алгоритме правилен

Докажем теперь следующее утверждение: алгоритм, используемый в задаче, корректен, то есть находит все возможные варианты и при этом не учитывает один и тот же вариант более одного раза.

Доказательство методом индукции по количеству номиналов монет n для набора произвольной суммы S.
==============

При n = 1 утверждение доказывается элементарно. Алгоритм отнимает от S номинал монеты, пока не дойдёт до нуля, либо до отрицательного числа. Первое означает, что S кратно номиналу, имеется один единственный вариант и возвращается 1. Во втором случае алгоритм вернёт 0, поскольку S не делится на номинал нацело. При подсчёте алгоритм не разветвляется, поскольку второй вызов сразу возвращает ноль для пустого списка.

Допустим, что утверждение верно для n номиналов. Докажем его для n + 1.

пусть k = S mod a_0

алгоритм подсчёта C(S, a_0, a_1, .., a_n) рекурсивно вызывает сам себя для подсчёта

C(S, a_1, .., a_n), C(S – a_0, a_0, a_1, .., a_n);
C(S – a_0, a_1, .., a_n), C(S – a_0 – a_0, a_0, a_1, .., a_n);
C(S – a_0 – a_0 – a_0, a_0, a_1, .., a_n), C(S – a_0 – a_0 – a_0, a_1, .., a_n);
…
C(S – (k-2)*a_0, a_1, .., a_n), C(S – (k-1)*a_0, a_0, a_1, .., a_n);
C(S – (k-1)*a_0, a_1, .., a_n), C(S – k*a_0, a_0, a_1, .., a_n);
C(S – k*a_0, a_1, .., a_n), C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n)

Поскольку [S – (k+1)*a_0] = 0, то алгоритм обрубается:

– либо на подсчёте C(S – k*a_0, a_0, a_1, .., a_n), при [S – k*a_0] = 0
– либо на подсчёте C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n), при [S – k*a_0] > 0

Корректность вычисления каждой суммы зависит от корректности вычисления последующих, что следует из леммы.

Корректность вычисления каждой C(S – j*a_0, a_1, .., a_n) вытекает из предположения индукции.

Следовательно, нам нужно доказать только корректность вычисления C(S – (k-1)*a_0, a_0, a_1, .., a_n), поскольку из этого следует по цепочке корректность вычисления всех остальных сумм вида C(S – j*a_0, a_0, a_1, .., a_n) вплоть до C(S, a_0, a_1, .., a_n).

Возможны два случая:

1) [S – k*a_0] = 0

Тогда [S – (k-1)*a_0] = a_0, C(S – (k-1)*a_0, a_0, a_1, .., a_n) = C(a_0, a_0, a_1, .., a_n).

Множество L1, обсуждаемое в лемме, состоит всего из одного набора, в который включается одна монета номиналом a_0. Следовательно

C(a_0, a_0, a_1, .., a_n) = 1 + C(a_0, a_1, .., a_n). Вспомним при этом, что именно 1 возвращает алгоритм, в случае равенства нулю передаваемой ему суммы (а ему и передастся [a_0 – a_0] = 0). Ну а подсчёт C(a_0, a_1, .., a_n) опять же корректен по предположению индукции.

2) [S – k*a_0] > 0.

При этом [S – (k+1)*a_0] [S – k*a_0] … C(S – j*a_0, a_0, a_1, .., a_n) … => подсчёт C(S, a_0, a_1, .., a_n) корректен

чтд
==============

Comment from gorilych
Date: July 19, 2008, 7:46 am

Ну всё.. заменил угловые скобки на “меньше”

Последний раз, надеюсь:

ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ АЛГОРИТМА

Лемма. Пусть C(S, a_0, a_1, .., a_n) – количество способов размена суммы S монетами номиналов a_0, a_1, .., a_n. Тогда

C(S, a_0, a_1, .., a_n) = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)

Доказательство
==============

Очевидно, что множество всевозможных различных наборов монет L, составлющих сумму S, можно разделить на два непересекающихся подмножества – подмножество L1 наборов, содержащих монету номиналом a_0, и подмножество L2, без монет с таким номиналом. Действительно, в наборе либо есть, либо нету такой монеты, поэтому нет такого набора, который входит одновременно в оба подмножества и поэтому они не пересекающиеся. Следовательно мощность множества L равна сумме мощностей подмножеств.

Мощность L2 равна C(S, a_1, .., a_n), поскольку любой набор из монет a_1, .., a_n с суммой S входит в L и при том входит в L2, поскольку не содержит монет с номиналом a_0.

Поскольку каждый набор в L1 содержит хотя бы одну монету номинала a_0 то из L1 можно получить равномощное множество L1′, убрав из каждого набора по одной монете ном. a_0. При этом сумма каждого набора уменьшится на величину номинала и будет равна (S – a_0).

Покажем от противного, что L1′ содержит все возможные наборы монет номиналами a_0, a_1, .., a_n с суммой (S – a_0). Пусть есть такой набор, не входящий в L1′, сумма которого равна (S – a_0). Добавим к этому набору монету номиналом a_0. Сумма набора станет равной S => расширенный набор входит в L. При этом он содержит добавленную монету номиналом a_0 => входит в L1. При убирании монеты номиналом a_0, получим исходный набор и при этом по способу построения L1′ он будет туда входить – противоречие.

Таким образом, мощность L1 = мощность L1` = C(S – a_0, a_0, a_1, .., a_n)

C(S, a_0, a_1, .., a_n) = мощность L = Мощность L2 + мощность L1 = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)

чтд
==============

Доказанная лемма показывает, что способ разветвления в алгоритме правилен

Докажем теперь следующее утверждение: алгоритм, используемый в задаче, корректен, то есть находит все возможные варианты и при этом не учитывает один и тот же вариант более одного раза.

Доказательство методом индукции по количеству номиналов монет n для набора произвольной суммы S.
==============

При n = 1 утверждение доказывается элементарно. Алгоритм отнимает от S номинал монеты, пока не дойдёт до нуля, либо до отрицательного числа. Первое означает, что S кратно номиналу, имеется один единственный вариант и возвращается 1. Во втором случае алгоритм вернёт 0, поскольку S не делится на номинал нацело. При подсчёте алгоритм не разветвляется, поскольку второй вызов сразу возвращает ноль для пустого списка.

Допустим, что утверждение верно для n номиналов. Докажем его для n + 1.

пусть k = S mod a_0

алгоритм подсчёта C(S, a_0, a_1, .., a_n) рекурсивно вызывает сам себя для подсчёта

C(S, a_1, .., a_n), C(S – a_0, a_0, a_1, .., a_n);
C(S – a_0, a_1, .., a_n), C(S – a_0 – a_0, a_0, a_1, .., a_n);
C(S – a_0 – a_0 – a_0, a_0, a_1, .., a_n), C(S – a_0 – a_0 – a_0, a_1, .., a_n);
…
C(S – (k-2)*a_0, a_1, .., a_n), C(S – (k-1)*a_0, a_0, a_1, .., a_n);
C(S – (k-1)*a_0, a_1, .., a_n), C(S – k*a_0, a_0, a_1, .., a_n);
C(S – k*a_0, a_1, .., a_n), C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n)

Поскольку [S – (k+1)*a_0] меньше 0 а [S – k*a_0] >= 0, то алгоритм обрубается:

– либо на подсчёте C(S – k*a_0, a_0, a_1, .., a_n), при [S – k*a_0] = 0
– либо на подсчёте C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n), при [S – k*a_0] > 0

Корректность вычисления каждой суммы зависит от корректности вычисления последующих, что следует из леммы.

Корректность вычисления каждой C(S – j*a_0, a_1, .., a_n) вытекает из предположения индукции.

Следовательно, нам нужно доказать только корректность вычисления C(S – (k-1)*a_0, a_0, a_1, .., a_n), поскольку из этого следует по цепочке корректность вычисления всех остальных сумм вида C(S – j*a_0, a_0, a_1, .., a_n) вплоть до C(S, a_0, a_1, .., a_n).

Возможны два случая:

1) [S – k*a_0] = 0

Тогда [S – (k-1)*a_0] = a_0, C(S – (k-1)*a_0, a_0, a_1, .., a_n) = C(a_0, a_0, a_1, .., a_n).

Множество L1, обсуждаемое в лемме, состоит всего из одного набора, в который включается одна монета номиналом a_0. Следовательно

C(a_0, a_0, a_1, .., a_n) = 1 + C(a_0, a_1, .., a_n). Вспомним при этом, что именно 1 возвращает алгоритм, в случае равенства нулю передаваемой ему суммы (а ему и передастся [a_0 – a_0] = 0). Ну а подсчёт C(a_0, a_1, .., a_n) опять же корректен по предположению индукции.

2) [S – k*a_0] > 0.

При этом [S – (k+1)*a_0] меньше 0 => [S – k*a_0] меньше a_0. Раз сумма для подсчёта [S – k*a_0] меньше номинала a_0, то монеты номинала a_0 не могут входить в возможные наборы. это значит, что

C(S – k*a_0, a_0, a_1, .., a_n) === C(S – k*a_0, a_1, .., a_n) + 0

Вспомним, что именно ноль вернёт алгоритм при отрицательной сумме

Значит, в обоих случаях подсчёт C(S – (k-1)*a_0, a_0, a_1, .., a_n) корректен => … C(S – j*a_0, a_0, a_1, .., a_n) … => подсчёт C(S, a_0, a_1, .., a_n) корректен

чтд
==============

Comment from gorilych
Date: July 19, 2008, 7:52 am

поскольку в доказательстве нигде не учитывался порядок номиналов, следовательно и корректность алгоритма от него не зависит.