Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 62834
Создание отчето... 62829
ТЕХНОЛОГИИ ДОСТ... 59361
Пример работы с... 58089
Имитационное мо... 54757
Реклама
Недорогой хостинг украина
Сейчас на сайте
Гостей: 24
На сайте нет зарегистрированных пользователей

Пользователей: 13,074
новичок: gerasim971
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование ЭВМ на GPSS (три класса заданий) + Пояснительная записка
База данных междугородних телефонных разговоров на Delphi
Моделирование процесса обработки заданий пакетным режимом работы с квант...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
10.6. Пролог


Давайте подведем итог и посмотрим, как Пролог вписывается в рассмотренную выше схему. Как было показано, некоторые формулы, представленные в виде совокупности дизъюнктов, выглядят в точности так же, как и утверждения в Прологе, в то время как другие формулы имеют несколько отличный вид. Формулы, имевшие вид утверждений Пролога, есть в действительности не что иное, как формулы, представимые в виде хорновских дизъюнктов. При записи хорновского дизъюнкта в соответствии с принятыми соглашениями, количество атомарных формул слева от знака ';-' не может превышать одну. В общем случае, дизъюнкты могут иметь несколько таких формул (они соответствуют литералам, представляющим атомарные формулы без отрицания). В Прологе непосредственно можно представить только хорновские дизъюнкты. Утверждения программы на Прологе соответствуют хорновским дизъюнктам с заголовком (в рамках определенной процедуры доказательства теорем). А что в Прологе соответствует целевому дизъюнкту? Очень просто, вопрос в Прологе
?- A 1 , A 2 ,…, A n



в точности соответствует хорновскому дизъюнкту без заголовка:- A 1 , A 2 , …, А п
В предыдущем разделе уже говорилось о том, что для решения любой задачи, представленной с помощью хорновских дизъюнктов, достаточно иметь в точности один дизъюнкт без заголовка. В Прологе это соответствует ситуации, когда все утверждения «программы» имеют заголовки и в каждый момент времени рассматривается лишь одно целевое утверждение (не имеющее заголовка).
Пролог-система основывается на процедуре доказательства теорем методом резолюций для хорновских дизъюнктов. Конкретная стратегия, используемая при этом, является разновидностью линейной входной резолюции. При использовании этой стратегии, выбор дизъюнктов для резолюции на каждом шаге ограничен следующими условиями. Процедура начинается с применения правила резолюций к целевому дизъюнкту и к одной из гипотез, что дает новый дизъюнкт. Затем производится резолюция этого дизъюнкта и одной из гипотез, что дает еще один новый дизъюнкт. Затем правило резолюций применяется к последнему полученному дизъюнкту и к одной из гипотез и так далее. На каждом этапе правило резолюций применяется к последнему из вновь полученных дизъюнктов и к одной из исходных гипотез. Правило резолюций никогда не применяется, если оба дизъюнкта были выведены на предыдущих этапах или являются исходными гипотезами. С точки зрения Пролога, последний выведенный дизъюнкт можно рассматривать как конъюнкцию целевых утверждений, которые еще надо доказать (согласовать с базой данных). В начальный момент это вопрос, а в конце процесса, при благоприятных условиях,- это пустое утверждение. На каждом этапе ищется утверждение, заголовок которого сопоставим с одним из целевых утверждений. Если необходимо, происходит конкретизация переменных. Удаляется целевое утверждение, с которым произошло сопоставление, а затем к целевым утверждениям, которые необходимо согласовать, добавляется тело найденного утверждения, в котором произведена конкретизация переменных. Так, например, начав с вопроса
:- мать(джон,Х), мать(Х,Y).



и утверждения
мать(U,V):- родитель(U,V), женщина(V).



получаем
:- родитель(джон,Х), женщина(Х), мать(Х,Y).



В действительности, используемая в Прологе стратегия является более ограниченной по сравнению с общей линейной входной резолюцией. В этом примере для сопоставления был выбран первый литерал целевого дизъюнкта, но с таким же успехом можно было бы сопоставить и второй литерал. В Прологе выбор литерала для сопоставления всегда происходит одним и тем же способом – всегда выбирается первый литерал в целевом дизъюнкте. Кроме того, новые целевые утверждения, полученные при использовании некоторого утверждения помещаются в начале целевого дизъюнкта. Это значит, что Пролог завершит доказательство согласованности всех подцелей прежде чем перейдет к обработке следующих целей.
Все сказанное относится к событиям, происходящим после того, как Пролог выбрал утверждение для сопоставления с первой целью. Но как организуется исследование альтернативных утверждений для удовлетворения той же самой цели? В Прологе используется стратегия поиска вглубь, а не поиска вширь. Это значит, что Пролог в каждый момент времени рассматривает лишь одну альтернативу, упорно следуя подразумеваемому предположению о правильности сделанного выбора. Выбор утверждений для каждой цели производится в строго фиксированном порядке, а пересмотр выбранных ранее утверждений происходит лишь в случае, когда все последующие попытки не привели к решению. В качестве альтернативы можно было бы предложить стратегию, при которой система запоминает одновременно все альтернативные пути решения. При этом система переходила бы по кругу от одной альтернативы к другой, прослеживая каждую альтернативу на небольшую глубину, а затем переходя к следующей. Такая стратегия поиска вширь имеет одно преимущество – если решение существует, то оно обязательно будет найдено. Используемая в Прологе стратегия поиска вглубь может привести к «зацикливанию» и, следовательно, никогда не будут исследованы некоторые альтернативы. С другой стороны такая стратегия намного проще и требует меньших затрат памяти при реализации на вычислительных машинах с традиционной архитектурой.
И наконец, небольшое замечание о возможных различиях между процедурой сопоставления, используемой в Прологе, и процедурой унификации, используемой в методе резолюций. Большинство Пролог-систем допускают обращение с вопросами, подобными следующему:
равны(X,X).
?- равны(foo(Y),Y).



Это возможно по той причине, что в Прологе разрешается сопоставлять некоторый терм с его собственным подтермом. В этом примере foo(Y) сопоставляется с Y , который сам является частью этого терма. В результате этого Y становится равным foo(Y) что в свою очередь равно foo(foo(Y)) (учитывая значение Y ), что равно foo(foo(foo(Y))) и так далее. Так что в результате Y обозначает некоторую бесконечную структуру. Заметим, что хотя Пролог-системы могут допускать использование подобных конструкций, большинство из них будут не в состоянии напечатать окончательный результат сопоставления. В соответствии с формальным определением унификации, подобного вида «бесконечные термы» никогда не должны появляться. Так что, Пролог выполняет эту процедуру неправильно в сравнении с тем, как это делается при доказательстве теорем методом резолюций. Для того чтобы сделать процедуру корректной, необходимо добавить проверку условия, заключающегося в том, что переменная не может быть конкретизирована некоторым значением, содержащим эту переменную. Такая проверка, проверка на вхождение, не представляла бы труда для ее реализации, но значительно замедляла бы выполнение программы на Прологе. Так как число программ, в которых может встретиться такая конструкция, невелико, то в большинстве реализаций такая проверка просто не делается. Уникальный бит торрент трекер http://trax.samaralan.ru/.
Опубликовал Kest July 10 2009 12:30:43 · 0 Комментариев · 8342 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Adapter (пример D...
Игра в крестики н...
Counter [Исходник...
Turbo Pascal for ...
JanReplace
isoCanvas (Редакт...
Самоучитель C++
Иллюстрированный ...
Gold Submitter II...
Создание лабиринт...
Нестандартные при...
TmxOutlookBarPro
Page Promoter 7.7...
Алгоритм DES шифр...
База для Allsubmi...
Atb
База предприятий ...
Трассировка прово...
IpEditAdress
Java Server Pages...

Топ загрузок
Приложение Клие... 100422
Delphi 7 Enterp... 84987
Converter AMR<-... 20062
GPSS World Stud... 11985
Borland C++Buil... 11408
Borland Delphi ... 8388
Turbo Pascal fo... 7008
Visual Studio 2... 4985
Калькулятор [Ис... 4631
FreeSMS v1.3.1 3530
Случайные статьи
Операции с контейн...
Симуляторы и эмуля...
были опубликованы ...
File not open for ...
Проблема универсал...
Создание собственн...
Windows 2000 подде...
Установка коммуник...
Сканеры и камеры и...
— конфигурация 582...
• Для шифрования и...
Netwoork
Работа с директори...
Денежные слоты
Кабель с перекрест...
Элементы управлени...
Глонасс установка
безопасностиТабл
Invalid symbol ref...
Типы сообщений про...
Инициализация пере...
Дальнейшее развити...
Хотя у WWI есть оф...
Как изменить полож...
Генерация программ...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?