Искусство нотации компьютерного программирования - PullRequest
Новая
       17

Искусство нотации компьютерного программирования

9 голосов
/ 19 февраля 2009

Я только начинаю читать TAOCP Том 1, и у меня возникают проблемы с пониманием стиля.

Кнут упоминает, что вычислительный метод является четырехкратным (Q, I, Omega, f) - но у меня возникают проблемы с пониманием того, для чего предназначен каждый из них. Я понимаю его первый пример, но не понимаю его второй

Я смотрю на стр. 8 третьего издания.

В конце главы описан алгоритм, который говорит о множествах строк.

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

Пусть A - конечный набор букв, а A * - набор всех строк на A. Идея состоит в том, чтобы закодировать состояния вычислений так, чтобы они были представлены строками A *

Q = (s,j) where s is in A* and j is an integer, 0 <= j <= N 
I = subset of Q with j = 0
Omega = subset with j = N
f = function below

(обратите внимание, что p & w являются строками) Если и s - строки в A *, мы говорим, что T встречается в s, если s имеет форму pTw для строк p и w. 

f(s,j) = (s,a<sub>j</sub>)             if T<sub>j</sub> does not occur in s;
f(s,j) = (pY<sub>j</sub>w,b<sub>j</sub>)   if p is the shortest possible string for which s = pY<sub>j</sub>w
f(s,N) = (s,N)

Я понимаю концепцию создания наборов строк, но не понимаю всего , что он пытается здесь сказать. Зачем мне Q, я, Омега? Что мне действительно объясняет f (зачем мне 3 функции в f?) ??

Может ли кто-нибудь помочь пролить свет?

Ответы [ 5 ]

14 голосов
/ 19 февраля 2009

Q = набор состояний (так что (s, j) представляет состояние s во время j)
I = начальные состояния (отсюда требование j == 0)
Omega = конечные состояния (отсюда требование j == N)
f = функция перехода

Кроме того, нет трех функций с именем f, а скорее f кусочно определяется тремя уравнениями.

11 голосов
/ 22 февраля 2015

Для полного раскрытия я недавно написал статью о понимании формального определения алгоритма Кнутом (до примера). Существенная часть ниже - это просто копия / вставка соответствующего текста из статьи, подробно отвечающей на ваш первый вопрос;

Ваш первый вопрос (Q, I, Ω, f)

Давайте формально определим вычислительный метод как четырехкратный (Q, I, Ω, f), в которой Q - множество, содержащее подмножества I и Ω, а f - это функция из Q в себя.

Когда Кнут ссылается на вычислительный метод как на четверку, он просто говорит, что вычислительный метод состоит из четырех четко определенных частей. Эти четыре части он помечает как (Q, I, Ω, f). Затем он переходит к краткому описанию каждого компонента этого четверки. I и Ω являются наборами (коллекциями вещей), а Q также является набором, который содержит вещи в наборах I и Ω. В этот момент легко ошибочно предположить, что он имеет в виду, что Q содержит только наборы I и Ω и ничего больше. Но позже мы обнаружим, что это не так. Наконец, он описывает f как функцию от Q в себя. Это означает, что f - это процесс, который принимает входные данные, являющиеся элементом из набора Q, и возвращает или выводит другой элемент из Q.

Кроме того, f должен оставлять Ω точечно фиксированным; то есть f (q) должен равно q для всех элементов q из Ω.

По сути это означает, что то, что возвращает наша функция f, будет таким же, как ее аргумент (т.е. значение не изменится), если аргумент является членом или элементом (вещь в) набора Ω. Это имеет больше смысла, когда Кнут делает разъяснение в своем следующем заявлении; Оповещение о спойлере - Ω - это набор возможных выходных данных нашего вычислительного метода. Как только мы узнаем это, это станет немного легче понять. Передача вывода обратно в нашу функцию не изменит его.

Четыре величины Q, I, Ω, f предназначены для представления соответственно состояния вычислений, вход, выход и вычислительное правило.

Итак, Q - это набор, который содержит все возможные состояния вычисления, то есть все возможные вариации ввода, вывода и все промежуточные этапы. Набор I содержит все возможные входы. Набор Ω содержит все возможные выходы (извините, если я испортил это откровение для вас ранее). И наконец, f представляет вычислительное правило; то есть процессы применяются к каждому состоянию, чтобы получить следующее состояние, в конце концов (надеюсь), пока мы не получим наш вывод.

Для пояснения, f представляет одну функцию, выходы которой определены на основе ее возможных входов. В этом конкретном примере он имеет только три возможных выхода и может иметь больше (или меньше) других алгоритмов. Итак, какова цель определения компонентов алгоритма таким образом? Определив их с помощью формальных обозначений, они также могут быть проанализированы и подвергнуты математическому анализу, когда дело доходит до анализа конкретных алгоритмов.

Вопрос о трактовке алгоритма как набора строк

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

Ссылки

  1. Марковские алгоритмы Wiki
  2. Статья «Определение алгоритма».
  3. Кнут искусства компьютерного программирования из 1.1.8
1 голос
/ 01 ноября 2016

помните, что мы определяем «вычислительный метод», а не алгоритм. что такое вычислительный метод наивно?

«Процедура», которая имеет все характеристики алгоритма, за исключением того, что ей, возможно, не хватает конечности, может называться вычислительным методом.

Проще говоря, Q - вычислительный метод. 

Q = {all possible states of computations, I, Ω}
I = {all possible inputs}
Ω = {all possible outputs}
f = computational rule

f - это функция из Q в себя. 

f: Q  --->  Q
  [I]      [Ω]

f должен оставить Ω точечным фиксированным, что означает:

f (q) = q, ∀ q ∈ Ω обратите внимание, что это не какая-то другая функция, а та же самая вычислительная правило, разделенная на Ω

Теперь процедура будет иметь последовательность. И очевидно, что вычислительный метод также должен иметь последовательность. Следовательно,

Каждый вход x в наборе I определяет вычислительную последовательность x 0 , x 1 , x 2 , ..., следующим образом: x 0 = x и x k + 1 = f (x k ) для k ≥ 0.

Как х 0 = х? Не забывайте, что входной x - это последовательность, поэтому начальная входная последовательность будет x 0 . Поскольку мы имеем дело с последовательностью и когда мы говорим о «k» состояниях, порядок и положение элементов в последовательности имеют значение. Итак, вычислительное правило f таково, что позиция или более точное слово 'состояние' элемента k th будет k + 1 th state. таким образом, мы можем отдельно применить функцию к каждому новому состоянию, чтобы получить следующее состояние.

если x k + 1 не в Ω, то это не имеет смысла по определению функции. Отсюда и формулировка Кнута.

Считается, что вычислительная последовательность заканчивается k шагами, если k - наименьшее целое число, для которого x k находится в Ω, и в этом случае говорят, что оно выдает выходной x k от х.

Таким образом, это определение вычислительного метода. вычислительное правило - это алгоритм.

1 голос
/ 14 июня 2011

если бы вы прошли алгоритм gcd евклида, который он изложил ранее в книге. Идея состоит в том, чтобы отметить начало каждой итерации как начальную стадию, а затем определить количество состояний, которые появятся в одной итерации цикла (а именно N). теперь, как вы помните, мы приняли ответ и остановили вычисления, когда остаток от m, деленный на n, равен нулю. то есть мы искали конкретное вхождение строки Yj. когда вычисление достигает последней ступени в цикле, оно останавливается или повторяется.

1 голос
/ 19 февраля 2009

Я не уверен на 100%, но, похоже, Q - это набор всех упорядоченных пар (s, j) для 0 <= J <= N. Это будет ваш домен. Это множество всех возможных состояний, заданных некоторым N и строкой s. </p>

I - это ваше подмножество Q, где все упорядоченные пары содержат J = 0 или ваши начальные состояния. Омега - это ваше подмножество Q, где все упорядоченные пары содержат J = N, или ваши конечные состояния.

f - фактическая функция в домене Q.

EDIT

Представьте, что определение функции является чем-то похожим на одну функцию, но разные случаи в зависимости от заданного ввода. Подумайте о функции, которую вы бы написали на языке. например: 

tuple f(string s, int i)
{
    if (Tj not in s)
        (s, aj)
    else if ( p is shortest possible length such that s = pYjw)
        (pYjw,bj)
    else if ( i == N )
        (s, N)
}

Другим примером является определение функции Фибоначчи . Видите, как это определяется? Имеет смысл?

...