Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Сложность





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

Начнем рассмотрение с введения нового определения – размера цели. Размер терма – это число символов в текстовой записи терма. Константы и переменные записываются с помощью одного символа и имеют размер 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; Просмотров: 256; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.