Для полного раскрытия информации, я недавно написал статью о понимании формального определения Кнута (предварительный пример) алгоритм. Значительная часть нижеприведенного - это просто копия / вставка соответствующего текста из статьи, подробно отвечающего на ваш первый вопрос;
Ваш первый вопрос по (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.1 .8
person
Rudi Kershaw
schedule
22.02.2015