Введение к работе
Настоящая работа посвящена построению и исследованию процедурной семантики для функционально-логических языков программирования в ограничениях, основанной на идеях Е—программирования и параллельного программирования в ограничениях. Основные исследования проводились для случая когда отношение равенства удовлетворяет теории равенства Кларка.
Актуальность темы. Расширение влияния вычислительной техники в различных областях жизни привело к появлению множества языков программирования. Известно, что многие языки программирования не отличаются выразительностью и нелегки для понимания. Одним из перспективных подходов в разрешении проблем, связанных с созданием языков программирования, является использование методов математической логики. Логические методы, реализованные в языках программирования, предоставляют программисту мощные и гибкие средства, которые позволяют создавать компактные и легкие для понимания программы.
Большое количество проблем в искусственном интеллекте и других областях кибернетики может рассматриваться как специальные случаи задач удовлетворения ограничений. К таким проблемам, в частности, относятся: машинное зрение, поддержка достоверности, планирование, вывод во временных логиках, проблемы графов, проектирование микросхем и т.д. Логическое программирование в ограничениях является одним из направлений развития программирования в ограничениях. Использование методов удовлетворения ограничений позволяет создавать вычислительные системы, которые гибко управляют процессом поиска решения и освобождают программиста от большой части работы по организации стратегии вычислений. Языки программирования, ориентированные на использование ограничений, отличаются большой недетерминированностью вычислений. Ключевой особенностью языков программирования в ограничениях является то, что они позволяют решать большие комбинаторные задачи и эффективно работать с дизъюнктивными ограничениями общего вида.
Большое значение при создании функционально-логического языка программирования имеет вопрос о том, какой формализм положен в его основу. Выбор формализма определяет денотационную семантику языка и эффективность описания на нем задач. В настоящей работе, для описания основных структур языка были использованы идеи Е-программирования и параллельного программирования в ограничениях. Актуальность работы заключается в том, что в ней вводится обобщенный подход к построению логических языков программирования в ограничениях, модель которых является моделью теории равества Кларка. На основе этого обобщенного подхода построены конкретные стратегии поиска решения в комбинаторном пространстве, что имеет важное прикладное значение. Немаловажно, что рассматриваемая процедурная семантика допускает реализацию на многопроцессорных системах и содержит средства, позволяющие эффективно решать комбинаторные задачи.
Цель работы — построение и исследование процедурной семантики для системы удовлетворения ограничений, имеющей эффективные средства для работы с дизъюнктивными ограничениями.
Научная новизна работы.
Построение процедурной семантики на основе Е-программирования1 и параллельного программирования в ограничениях (се - программирование2) позволило:
оперировать широким классом логических формул, допускающих эффективную процедурную семантику;
использовать ограниченные кванторы для реализации методов работы с дизъюнктивными ограничениями;
описать процедурную семантику, которая может быть положена в основу реализации логических языков программирования на многопроцессорных системах.
В диссертации рассматривается наиболее важный случай работы с равенством, а именно, когда отношение равенства удовлетворяет теории равенства Кларка. Именно этот вариант отношения равенства наиболее распространен в логическом программировании.
'Гончаров С.С, Свириденко Д.И. ^-программирование// Вычислительные системы, 107, Новосибирск, 1985, с.24-51.
2V. Sarasvat. Concurrent Constraint Programming// the MIT Press, 1993, 486p.
Исследовано поведение различных стратегий поиска решения комбинаторных задач. Сформулированы и доказаны теоремы о полноте и корректности +-машины на моделях теории равенства Кларка.
Практическая ценность работы. Предложенные в диссертации методы оптимизации работы с дизъюнктивными ограничениями реализованы в функционально - логическом языке программирования Флэнг. С помощью Флэнга было проведено тестирование методов при решении сложных комбинаторных задач. Наши исследования показали, что предложенные методы значительно улучшили выполнение Флэнг-программ. Так, например, имеется много задач, в которых использование методов локальной совместности при работе с произвольными дизъюнктивными ограничениями значительно эффективней, чем использование локальной совместности при работе с конечными доменами. Результаты данных исследований могут быть применены к решению индустриальных комбинаторных задач, задач теории расписаний, задач дискретной оптимизации.
Апробация работы. Изложенные в работе результаты были представлены на Российских и международных конференциях. С помощью Флэнга были проведено тестирование предложенных методов удолвлетворения дизъюнктивных ограничений при решении сложных комбинаторных задач. По теме диссертации опубликовано 7 работ.
Структура и объем дисертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации 110 страниц, список литературы содержит 93 пункта, включая работы автора.