Вопрос о нотации Art of Computer programming

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 представляет собой единственную функцию, выходы которой определены на основе ее возможных входов. Он имеет только три возможных выхода в этом конкретном примере и может иметь больше (или меньше) в других алгоритмах. Итак, какова цель определения компонентов алгоритма таким образом? Если они определены с использованием формальных обозначений, они также могут быть проанализированы и подвергнуты математическому исследованию, когда дело доходит до анализа конкретных алгоритмов.

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

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

использованная литература

1. Марковский алгоритм алгоритмов вики
2. Моя статья об определении алгоритма.
3. Кнут искусство компьютерного программирования пр. 1.1 .8

Я не уверен на 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)
}

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

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

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

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

Проще говоря, 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 ₀, x ₁, x ₂, ... следующим образом: x < sub> 0 = x и x _{k + 1} = f (x _k) для k ≥ 0.

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

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

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

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