WikiDer > Дерево вычислений

Computation tree

А дерево вычислений представляет собой представление шагов вычисления недетерминированная машина Тьюринга на указанном входе.[1] Вычисление дерево это укоренившееся дерево узлов и ребер. Каждый узел в дереве представляет отдельное вычислительное состояние, а каждое ребро представляет переход к следующему возможному вычислению. Количество узлов дерева - это размер дерева, а длина пути от корня до данного узла - это глубина узла. Наибольшая глубина выходного узла - это глубина дерева. Листья дерева называются выходными узлами.

В дереве вычислений для проблема решения, каждый выходной узел помечен как Да или Нет. Если дерево T с входным пространством X, если и путь для x заканчивается узлом, помеченным как да, тогда ввод x принимается. В противном случае он отклоняется.[2]

Глубина дерева вычислений для заданного входа - это время вычисления для машины Тьюринга на этом входе.[1]

Деревья вычислений также использовались для изучения вычислительной сложности задач в вычислительная геометрия и настоящий номер расчеты.[3][4]

Рекомендации

  1. ^ а б Гриффор, Э. Р. (1999), Справочник по теории вычислимости, Исследования по логике и основам математики, 140, Elsevier, стр. 595, ISBN 9780080533049.
  2. ^ Морет, Бернард М. Э. (1998), Теория вычислений, Эддисон-Уэсли, стр. 338, г. ISBN 9780201258288.
  3. ^ Бен-Ор, М. (1983), "Нижние оценки для алгебраических вычислительных деревьев", Proc. 15-й год. Symp. Теория вычислений, стр. 80–86, Дои:10.1145/800061.808735.
  4. ^ Григорьев, Дима; Воробьев, Николай (1996), "Нижние оценки сложности для вычислительных деревьев с элементарными трансцендентными функциональными вентилями", Теор. Comput. Sci., 157: 185–214, Дои:10.1016 / 0304-3975 (95) 00159-X.