Искусство нотации компьютерного программирования
Я только начинаю читать 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, aj), если Tj не встречается в s; f (s, j) = (pYj w, bj), если p - кратчайшая строка, для которой s = pYj w f (s, N) = (s, N)
Я понимаю концепцию создания наборов строк, но не понимаю всего, что он пытается здесь сказать. Зачем мне Q, я, Омега? Что мне действительно объясняет f (зачем мне 3 функции в f?)??
Кто-нибудь может помочь пролить свет?
5 ответов
Q = набор состояний (так что (s, j) представляет государство s вовремя j)I = начальные состояния (отсюда требование j == 0)Omega = конечные состояния (отсюда требование j == N)f = переходная функция
Кроме того, нет трех названных функций f скорее f кусочно определяется тремя уравнениями.
Для полного раскрытия я недавно написал статью о понимании формального определения алгоритма Кнутом (до примера). Существенная часть ниже - просто копия / вставка соответствующего текста из статьи, подробно отвечающей на ваш первый вопрос;
Ваш первый вопрос (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 представляет отдельную функцию, выходы которой определены на основе возможных входов. В этом конкретном примере он имеет только три возможных выхода и может иметь больше (или меньше) других алгоритмов. Итак, какова цель определения компонентов алгоритма таким образом? Определив их с помощью формальных обозначений, они также могут быть проанализированы и подвергнуты математическому анализу, когда дело доходит до анализа конкретных алгоритмов.
Вопрос о трактовке алгоритма как набора строк
Я ответил на другой вопрос по этому вопросу здесь. Но, по сути, Кнут делает здесь использование алгоритма Маркова для достижения того, что он уже описал. Стоит изучить (и проработать несколько примеров) марковские алгоритмы, чтобы помочь вам точно понять, что здесь происходит.
Рекомендации
Помните, что мы определяем "вычислительный метод", а не алгоритм. что такое вычислительный метод наивно?
"Процедура", которая имеет все характеристики алгоритма, за исключением того, что ей, возможно, не хватает конечности, может называться вычислительным методом.
Проще говоря, 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 определяет вычислительную последовательность x0, x1, x2,... следующим образом: x0 = x и xk+1 = f (xk) для k ≥ 0.
Как х0 = х? Не забывайте, что входной x является последовательностью, поэтому начальная входная последовательность будет x0. Поскольку мы имеем дело с последовательностью и когда речь идет о состояниях "k", порядок и положение элементов в последовательности имеют значение. И так, вычислительное правило f таково, что позиция или более точное слово "состояние" k-го элемента будет k+1-м состоянием. таким образом, мы можем отдельно применить функцию к каждому новому состоянию, чтобы получить следующее состояние.
если xk+1 не входит в Ω, то это не имеет смысла по определению функции. Отсюда и формулировка Кнута.
Считается, что вычислительная последовательность заканчивается k шагами, если k - наименьшее целое число, для которого xk находится в Ω, и в этом случае говорят, что она выдает выходной сигнал xk из x.
Таким образом, это определение вычислительного метода. вычислительным правилом является алгоритм.
Если бы вы прошли алгоритм gcd евклида, который он изложил ранее в книге. идея состоит в том, чтобы отметить начало каждой итерации как начальную стадию, а затем определить количество состояний, которые появятся в одной итерации цикла (а именно N). теперь, как вы помните, мы приняли ответ и остановили вычисления, когда остаток от m, деленный на n, равен нулю. то есть мы искали конкретное вхождение строки Yj. когда вычисление достигает последней ступени в цикле, оно останавливается или повторяется.
Я не уверен на 100%, но похоже, что Q - это набор всех упорядоченных пар (s, j) для 0 <= J <= N. Это будет ваш домен. Это множество всех возможных состояний, заданных N и строкой s.
I - это ваше подмножество Q, где все упорядоченные пары содержат J=0 или ваши начальные состояния. Омега - это ваше подмножество Q, где все упорядоченные пары содержат J=N, или ваши конечные состояния.
f - фактическая функция над областью Q.
РЕДАКТИРОВАТЬ
Представьте, что определение функции является чем-то похожим на одну функцию, но в разных случаях в зависимости от заданного ввода. Подумайте о функции, которую вы бы написали на языке. например:
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)
}
Другим примером является определение функции Фибоначчи. Видите, как это определяется? Есть смысл?