Откуда p?

Присоединённый файл ( Кол-во скачиваний: 79 )
 IMAG0051.jpg 127,43 Kb

Опечатки бывают даже в Кнутах.

Там нет никакой опечатки.

russians, поймите одно, труд Кнута - жертва крупномасштабной PR-кампании. Куда ни плюнь, всюду советуют Кнута, советуют бездумно. У этого труда при всех его достоинствах есть пара недостатков:

• Материал отнюдь не для новичков. С самого начала требуются неплохие математические навыки, материал слишком академичен.
• Материал избыточен для среднестатистического программиста.

То есть Кнут - для тех, кто всерьёз решил заниматься проектированием и анализом алгоритмов.

В качестве чего-то более полезного рекомендую Н. Вирт, Алгоритмы и структуры данных.

После можно почитать А. Левитин, Алгоритмы. Введение в разработку и анализ.

gustavomarginale, исключено, книга существует с 1968 года. За это время Кнут успел ввести грант за найденную ошибку в оригинале - 3000$. Но не будем отвлекаться  

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


Это сообщение отредактировал(а) russians - 3.8.2010, 13:10

А как Вы представляете себе ответ на такой вопрос? В его нынешней формулировке он начисто лишен смысла.

Кнут использует в качестве метода строгого обоснования понятия алгоритм метод вычислений. Вроде как он и автор этого метода. Там всё написано, собственно.

Q - множество состояний;
I - множество начальных состояний;
Omega - множество конечных состояний;
f - функция перехода.

Ниже приведён вариант формализации алгоритма Евклида. Кнут выбирает Q, I, Omega и f, так как описано в книге. Обратите внимание на слово "пусть" в начале каждого из предложений. Выбранные Кнутом множества и функция перехода - действительно формализация алгоритма Евклида. Единственный ли это способ? Не думаю, это просто пример.



Это сообщение отредактировал(а) kemiisto - 3.8.2010, 14:03

Фантом, ладно, почему в четвёртой строчке f((m, n, p, 3)) = (n, p, p, 1), а не f((m, n, r, 3)) = (n, r, r, 1)?
Мне хочется понять, откуда взялась p, в алгоритме Евклида её нет…

При этом внизу он пишет, что соответствие записи и алгоритма очевидно  Издевается?)

Это сообщение отредактировал(а) russians - 3.8.2010, 14:05

Разве нет?


Да ниоткуда. Просто Кнут так определил обсуждаемые множества.

kemiisto, не думаю, что просто, ведь в третьей строчке он делает отсылку на (m, n, r, 3), на третий шаг, а на третьем шаге у нас (n, p, p, 1), и шагаем на первый шаг... то есть по логике, получается, что p - пустая ни для чего не определённая переменная, а r проскакивает?

если подразумевается, что значение r кладётся в p, так и скажите 

Добавлено через 7 минут и 14 секунд
Всё, до меня дошло.
В четвёртой строчке мы определяем, что функция делает, а в третьей применяем эту функцию, так?
То есть по логике запись заканчивается на третьей строчке.

Это сообщение отредактировал(а) russians - 3.8.2010, 14:18

Во всех четырёх строках мы даём определение функции f. Так как эта функция определена на множестве Q, мы должны дать определение для всех возможных аргументов из множества Q.

kemiisto, ну а какие у нас могут быть возможные аргументы по исходному алгоритму? m, n, r, где  
0 <= r  < n

Так, стоп. Начнём с начала. Алгоритм Евклида - нахождение НОД для двух положительных чисел. В начала текста они обозначены m и n.

Теперь формализуем этот алгоритм методом вычислений. Пусть элементами множества Q ... и далее по тексту.

Во-первых, после определения множеств, m, n, p и r никакого отношения к описанному ранее не имеют. m и n - это не аргументы алгоритма Евклида, r - не остаток от деления. Это просто целые числа. Как и p. Причём m, n, p - положительные, а r - неотрицательное целое число.

Теперь определим функцию перехода для каждой группы элементов множества Q:

• для величин (n) функция перехода f((n)) = (n)
• для упорядоченных пар (m, n) - f((m, n)) = (m, n, 0, 1)
• ...

 

Все определения приведены в книге.

Теперь для любого элемента множества I можно найти соответсвующий элемент множества Omega, использую функцию перехода. Каждое входное значение x из множества I определяет вычисляемую последовательность x0, x1, x2, ... следующим образом

x[0] = x и x[k+1] = f(x[k]) для k >= 0.

Говорят, что вычисляемая последовательность заканчивается через k шагов, если k - наименьшее целое число, для которого x[k] принадлежит Omega...

Пример: элемент множества I пара чисел (2, 3). Найдём соответствующий ему элемент множества Omega. 

Ну вот. x[0] = (3, 2). Теперь будем применять функцию f до тех пор, пока на выходе не получим элемент множества Omega. До тех пор, пока не получим просто величину (а не пару или четвёрку).

k = 1: x[1] = f(x[1-1]) = f(x[0]) = f((3, 2)) = (3, 2, 0, 1) по определению функции f на первой строчке
k = 2: x[2] = f(x[1]) = f((3, 2, 0, 1)) = (3, 2, 1, 2) по определению функции f на второй строчке
k = 3: x[3] = f(x[2]) = f((3, 2, 1, 2)) = (3, 2, 1, 3) ...
k = 4: x[4] = f(x[3]) = f((3, 2, 1, 3)) = (2, 1, 1, 1) ...
k = 5: x[5] = f(x[4]) = f((2, 1, 1, 1)) = (2, 1, 0, 2) ...
k = 6: x[6] = f(x[5]) = f((2, 1, 0, 2)) = 1

Всё. Приплыли. Последовательность закончилась. 

И Кнут прав, что соответствие между данной записью и алгоритмом Евклида очевидно. Элементами множества конченых состояний, полученными из элементов множества начальных состояний применением функции перехода как описано выше, будут значения НОД.

Это сообщение отредактировал(а) kemiisto - 3.8.2010, 16:28

k = 1: x[1] = f(x[1-1]) = f(x[0]) = f((3, 2)) = (3, 2, 0, 1) по определению функции f на первой строчке


то, что описание методом вычислений верно для алгоритма евклида, мне понятно  Очень сильно благодарю вас за то, что потратили время на развёрнутый ответ!

Но у меня вопрос на понимание, какую роль в указанной последовательности имеет p, зачем мы её используем и почему запись вида: f((m, n, r, 3)) = (n, r, r, 1) в четвёртой строчке - неверно? В вышеуказанном описании ответа ИМЕННО на этот вопрос я не нашёл  Мы же используем в четвёртой строчке значение r из третьей, так? Только оно почему то хранится в p, а не в r.

Это сообщение отредактировал(а) russians - 3.8.2010, 16:21

Итак, среди членов множества Q могут встречаться 3 вида упорядоченных троек:

• (m, n , r, 1)
• (m, n , r, 2)
• (m, n , p, 3)

r - число неотрицательное (r >= 0), а p - положительное (p > 0).

То есть, среди четвёрок множества Q с последним элементом равным 3 нет таких, в которых предпоследний элемент был бы равен нулю. Поэтому нельзя использовать для обозначения этого элемента символ r (ведь r >= 0).

Всё, теперь понятна необходимость использования  Спасибо 

Это сообщение отредактировал(а) russians - 3.8.2010, 16:37