Cтраница 3
Теоретически дерево можно построить для любой игры, но практически огромное число ветвей такого дерева делает это совершенно нереальным. Пример дерева для игры Ним, начавшейся с тройки ( 1, 2, 3), приведен на рис. 3.8. Даже для такой тривиальной игры дерево достаточно велико, а для более сложной игры с большим выбором ходов ( скажем, шахмат или бриджа) дерево хотя и конечно, но столь велико, что невозможно построить его полностью. Тем не менее само понятие дерева игры полезно, и многое из того, что делают игровые программы, лучше всего описывается как обработка небольшой части такого дерева. [31]
Теперь обратим внимание на тот факт, что мы можем легко расширить понятие теории, допустив более широкий класс формул. Иначе, оставаясь в рамках языка алгебры отношений, мы не могли бы даже сформулировать теорию, для которой моделями являются произвольные деревья. Язык алгебры отношений слишком слаб, чтобы на нем можно было определить понятие дерева. Но, если в качестве исходного языка использовать язык узкого исчисления предикатов ( мы не можем здесь дать строгое описание этого языка; фактически представление о нем можно получить из книги Ю. А. Шихановича Введение в современную математику), то соответствующая теория легко может быть сформулирована. [32]
Общее число уравнений, составленных для множества сечений и контуров заданного графа может быть намного больше необходимого числа уравнений. Из множества сечений и контуров графа или цепи необходимо выбрать такие сечения и контуры, которые дают линейно-независимые системы уравнений, составленные по законам Кирхгофа. Сечения и контуры, дающие линейно-независимую систему уравнений, называемые главными сечениями и главными контурами, удобно вводить с помощью понятия дерева графа. [33]
Затем изложим алгоритм, выявляющий в данной цепочке вхождение какой-нибудь цепочки из множества, заданного регулярным выражением. Время работы алгоритма равно по порядку произведению длин цепочки х и данного регулярного выражения. Далее Докажем сильный теоретический результат, состоящий в том, что любую проблему распознавания вхождения цепочек, разрешимую на двустороннем детерминированном магазинном автомате, можно решить на РАМ за линейное время. Это замечательный результат, поскольку магазинный автомат может потребовать для решения задачи квадратичное или даже экспоненциальное время. Наконец, введем понятие дерева позиций ( позиционного дерева) и применим его к другим задачам идентификации цепочек, таким, как поиск в данной цепочке самого длинного повторения. [34]