Bilet_2 (1161590), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Как известно, таких стратегийсуществует много, но среди них выделяются две наиболеехарактерные:Iстратегия обхода в ширину , при которой деревостроится (обходится) поярусно — вершина i-го нестроится, до тех пор пока не будут построены все вершины(i − 1)-го яруса;Iстратегия обхода в глубину с возвратом , при которойветви дерева обходятся поочередно — очередная ветвьдерева не обохдится, до тех пор пока не будут пройденывсе вершины текущей ветви.СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в ширину является вычислительно полной,посколькуI каждый запрос имеет конечное число SLD-резольвент, ипоэтому в каждом ярусе дерева SLD-резолютивныхвычислений имеется конечное число вершин;I каждое успешное вычисление завершается на некоторомярусе;I и поэтому каждое успешное вычисление будет рано илипоздно полностью построено.Но строить интерпретатор логических программ на основестратегии обхода в ширину нецелесообразно.

При обходедерева в ширину нужно обязательно хранить в памяти всевершины очередного яруса. Это требует большого расходапамяти. Например, в 100-м ярусе двоичного дерева содержится299 вершин. Вычислительных ресурсов всего земного шара нехватит, чтобы хранить информацию обо всех этих вершинах.СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратом основана наследующих принципах:1. все программные утверждения упорядочиваются;2.

на каждом шаге обхода из текущей вершины Gосуществляется переходIIлибо в новую вершину-потомок G 0 , которая являетсяSLD-резольвентой запроса G и первого по порядкупрограммного утверждения D, ранее не использованногодля этой цели;либо в ранее построенную родительскую вершину G 00(откат), если все программные утверждения уже былиопробованы для построения SLD-резольвент запроса G .СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратомIIимеет эффективную реализацию: в памяти нужно хранитьлишь запросы той ветви, по которой идет обход, и каждыйзапрос должен вести учет использованных программныхутверждений;является, к сожалению, вычислительно неполной.Стратегия обхода в глубину чувствительна к порядкурасположения программных утверждений в логическихпрограммах.

Результат вычисления запроса может изменитьсяпри перестановке программных утверждений. Посколькусоображения эффективности превалируют над требованиямивычислительной полноты, в качестве стандартной стратегиивычисления логических программ выбрана стратегия обхода вглубину. Программист должен сам выбрать нужный порядокрасположения программных утверждений, чтобы стандартнаястратегия вычисления отыскала все вычисленные ответы.КОНЕЦ ОТВЕТА НА БИЛЕТ 2..

Характеристики

Список файлов вопросов/заданий