Сложность

Разнообразные использования логических программ слабо влияют на характер мер сложности.Поэтому вместо описания сложности в терминах длины входа при конкретном использовании программы мы обратимся к выводу целей из значения программы. Естественной меройсложности логической программы является длина доказательств, порождаемых при выводе целей из значения логической программы.

Начнем рассмотрение с введения нового определения – размера цели. Размер терма – это число символов в текстовой записи терма. Константы и переменные записываются с помощью одного символа и имеют размер 1. Размер составного терма на единицу больше суммы размеров аргументов терма. Например, список [ b ] имеет размер 3, список [ а,b ] имеет размер 5, цель append([a,b],[c,d]X) имеет размер 12. В общем случае список из п элементов имеет размер 2п + 1.

Сложность длины вывода программы Р равна L(n), если любая цель G, принадлежащая значению программы и имеющая размер n, может быть выведена из программы Р с длиной вывода, не превосходящей L(n).

Сложность длины вывода связана с обычными мерами сложности в теории алгоритмов. В случае последовательной реализации вычислительной модели эта сложность соответствует временной сложности. Программа 3.15, задающая отношение append, имеет линейную сложность длины вывода. Это показано в упражнении (1) в конце раздела.

Применимость этой меры сложности к программам на Прологе, а не к логическим программам, зависит от использования алгоритма унификации без проверки на вхождение. Рассмотрим процесс вычисления простейшей программы соединения двух списков. Соединение двух списков, как показано на рис. 4.3, использует несколько унификации целей вида append с заголовком правила append – append([X | Xs],Ys,[X | Zs]). Потребуется не менее трех унификаций, сопоставляющих переменные со списками (возможно, неполными). Если в каждой унификации должна быть выполнена проверка на вхождение, то списки, соответствующие аргументам, будут найдены. Время этого процесса прямо пропорционально размеру входной цели. Однако если проверка на вхождение не производится, то время унификации ограничено константой. Общая сложность append -вычисления квадратично зависит от размера входных списков при использовании проверки на вхождение и линейно - без использования проверки.

Введем другие полезные меры сложности, основанные на доказательстве.Пусть R – доказательство.Назовем глубиной R самое глубокое использование цели в некоторой резолюции, размер цели в R – максимальный размер редуцируемых в R целей.

Логическая программа Р имеет сложность размера цели G(n), если любая цель А, принадлежащая значению программы и имеющая размер n, может быть выведена из программы Р так, что размер цели в выводе не превысит G(n).

Логическая программа Р имеет сложность глубины вывода D(n) если любая цель А, принадлежащая значению программы и имеющая размер п, может быть выведена из программы Р с глубиной вывода,не превосходящей D(n).

Сложность размера цели связана с емкостью памяти. Сложность глубины вывода связана с объемом запоминаемой информации при последовательных реализациях и с емкостной и временной сложностью при параллельных реализациях.

Дата добавления: 2014-01-07