Prolog

        подсп3( Спис, Подспис) :-

                конк( Спис1, Спис2, Спис),

                конк( Подспис, _, Спис2).

8. 2.    Определите отношение

        добавить_в_конец( Список, Элемент, НовыйСписок)

добавляющее Элемент в конец списка Список; результат - НовыйСписок. Оба списка представляйте разностными парами.

Посмотреть ответ

8. 3.    Определите отношение

        обратить( Список, ОбращенныйСписок)

где оба списка представлены разностными парами.

Посмотреть ответ

8. 4.    Перепищите процедуру собрать из разд. 8.5.2, используя разностное представление списков, чтобы конкатенация выполнялась эффективнее.

Резюме

Для оценки качества программы существует несколько критериев:

        правильность

        эффективность

        простота, читабельность

        удобство модификации

        документированность

Принцип пошаговой детализации - хороший способ организации процесса разработки программ. Пошаговая детализация применима к отношениям, алгоритмам и структурам данных.

Следующие методы часто помогают находить идеи для совершенствования программ на Прологе:

Применение рекурсии:  выявить граничные и общие случаи рекурсивного определения.

Обобщение:  рассмотреть такую более общую задачу, которую проще решить, чем исходную.

Использование рисунков:  графическое представление помогает в выявлении важных отношений.

Полезно следовать некоторым стилистическим соглашениям для уменьшения опасности внесения ошибок в программы и создания программ, легких для чтения, отладки и модификации.

В пролог-системах обычно имеются средства отладки. Наиболее полезными являются средства трассировки программ.

Существует много способов повышения эффективности программы. Наиболее простые способы включают в себя:

изменение порядка целей и предложений

управляемый перебор при помощи введения отсечений

запоминание (с помощью assert) решений, которые иначе пришлось бы перевычислять

Более тонкие и радикальные методы связаны с улучшением алгоритмов (особенно, в части повышения эффективности перебора) и с совершенствованием структур данных.

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

Часть 2

ПРОЛОГ

В ИСКУССТВЕННОМ ИНТЕЛЛЕКТЕ

Глава 9

ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ

Один из фундаментальных вопросов программирования - это вопрос о представлении сложных объектов (таких как, например, множества), а также вопрос об эффективной реализации операций над подобными объектами. В этой главе мы рассмотрим несколько часто используемых структур данных, принадлежащих к трем большим семействам: спискам, деревьям и графам. Мы изучим способы представления этих структур на Прологе и составим программы, реализующие некоторые операции над ними, в том числе, сортировку списков, работу с множествами как древовидными структурами, запись элементов данных в дерево, поиск данных в дереве, нахождение пути в графе и т.п. Мы подробно разберем несколько примеров, чрезвычайно поучительных с точки зрения программирования на Прологе.

9. 1.    Представление списков. Сортировка

9. 1. 1.    Замечания в некоторых альтернативных способах представления списков

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

пуста, либо

состоит из головы и хвоста, причем хвост должен быть сам списком.

Поэтому для представления этой структуры нам необходимо иметь всего лишь два языковых средства: специальный символ, обозначающий пустой список, и функтор для соединения головы с хвостом. Мы могли бы, например, выбрать

        ничего_не_делать

в качестве символа, обозначающего пустой список, и атом

        затем

в качестве инфиксного оператора для построения списка по заданным голове и хвосту. Этот оператор мы можем объявить в программе, например, так:

        :- ор( 500, xfy, затем).

Список

        [ войти, сесть, поужинать]

можно было бы тогда записать как

        войти затем сесть затем поужинать

        затем ничего_не_делать

Важно заметить, что на соответствующем уровне абстракции специальная прологовская нотация и всевозможные альтернативные способы обозначения списков сводятся, фактически, к одному и тому же представлению. В связи с этим типовые операции над списками, такие как

        принадлежит ( X, L)

        конк( L1, L2, L3)

        удалить( X, L1, L2)