Вопрос о формальном доказательстве обхода в порядок

Question

В знаменитой серии книг Дона Кнута, Искусство компьютерного программирования, раздел 2.3.1, он описывает алгоритм для пересечения бинарного дерева в порядке, используя вспомогательный стек:

T1 Инициализировать.] Установите стек $ rm a $ пусто и установите переменную ссылки $ rm P Get T $

Т2 $ rm p = lambda $?] Если $ rm p = lambda $, перейдите к шагу T4.

T3 Stack $ rm ; Leatharrow P $] (теперь $ rm P $ указывает на непустовое двоичное дерево, которое должно быть пройденным.) Выдвиньте значение $ rm p $ на стек $ rm a $, тогда Установите $ rm P Get Llink (P) $

T4 $ rm P LeateRrow Stack $] Если стек $ rm a $ пуст, алгоритм завершается; В противном случае выберите вершину $ rm $ to $ rm p $.

T5 Посетите $ rm P $] Посетите $ rm Узел (P) $. Затем установите $ rm P Get rlink (p) $ и вернитесь к шагу T2.

Мы можем построить блок -схему алгоритма. В последующем абзаце он дает Формальное доказательство алгоритма:

Начиная с шага T2 с $ rm p $ указатель на двоичное дерево узлов $ n $ и со стеком $ rm a $, содержащая $ rm a [1] dotcc a [m] $ за некоторое время $ m ge 0 $, процедура шагов T2-T5 будет пересекать рассматриваемое двоичное дерево, и затем будет достигнут шаг T4 со стеком $ rm a $ возвращено в свое исходное значение $ rm a [1] dotsc А [м] $.

Однако, насколько я знаю, такое формальное доказательство сильно отличается от общего метода, описанного в разделе 1.2.1:

Для каждой коробки в блок -схеме, если утверждение, прикрепленное к любой стрелке, ведущей в коробку, верно до того, как операция в этом поле будет выполнена, то все утверждения о соответствующих стрелках, ведущих от коробки, верны после операции.

На самом деле, такой метод несколько эквивалентен Логика Хоре, который используется для официальной проверки достоверности алгоритмов.

Можем ли мы превратить упомянутое утверждение, чтобы доказать алгоритм обхода в схему логики Хоара, или утверждение схемы блок-схемы?

Спасибо!

Answer 1

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

Tree = Leaf N | Node N LTree RTree
Inorder(Leaf N) = N
Inorder(Node N LTree RTree) = Inorder(LTree) || N || Inorder(RTree)

Здесь n - «Имя» узла, и || это сознание списка. Вооружившись этими понятиями, это упражнение для построения требуемых тройков Hoare. Вам, вероятно, нужно будет придумать еще больше понятий (например, вам нужно будет объяснить, каково содержимое стека, когда узел P выскочил).

Что мы получаем от этого упражнения? Мы понимаем алгоритм лучше? Возможно нет. Но мы понимаем, как точно рассуждать об алгоритмах, что полезно, если вы планируете выполнять проверку программного обеспечения или теорию языка программирования, области, формирующие так называемую «теорию B». Если вы больше вроде «Теории А» типа (алгоритмы и сложность), то, как и я, вы найдете такие упражнения в некоторой степени, кроме этого.