Дерево вычислений
Дерево вычислений — это представление шагов вычислений недетерминированной машины Тьюринга на заданных входных данных. [1] вычислений Дерево — это корневое дерево узлов и ребер. Каждый узел в дереве представляет собой одно вычислительное состояние, а каждое ребро представляет собой переход к следующему возможному вычислению. Количество узлов дерева — это размер дерева, а длина пути от корня до данного узла — это глубина узла. Наибольшая глубина выходного узла — это глубина дерева. Листья дерева называются выходными узлами.
В дереве вычислений для задачи решения каждый выходной узел помечен Да или Нет. Если дерево T с входным пространством X, если и путь для x заканчивается узлом с меткой «да», тогда входной сигнал x принимается. В противном случае оно будет отклонено. [2]
Глубина дерева вычислений для данного входа — это время вычислений машины Тьюринга на этом входе. [1]
Деревья вычислений также использовались для изучения вычислительной сложности задач вычислительной геометрии и вычислений с действительными числами . [3] [4]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Гриффор, Э.Р. (1999), Справочник по теории вычислимости , Исследования по логике и основам математики, том. 140, Эльзевир, с. 595, ISBN 9780080533049 .
- ^ Море, Бернард М.Е. (1998), Теория вычислений , Аддисон-Уэсли, стр. 338, ISBN 9780201258288 .
- ^ Бен-Ор, М. (1983), «Нижние оценки для деревьев алгебраических вычислений», Proc. 15-летие. Симп. Теория вычислений , стр. 80–86, номер документа : 10.1145/800061.808735 .
- ^ Григорьев Дима; Воробьев, Николай (1996), "Нижние оценки сложности деревьев вычислений с элементарными вентилями трансцендентных функций", Теория. Вычислить. наук. , 157 (2): 185–214, doi : 10.1016/0304-3975(95)00159-X .