Введение к работе
Актуальность темы. Математическая логика оказывает большое влияние на программирование. Однако реализация многих логических идей идет медленно и с большими трудностями. Эта проблема объясняется различиями в природе логики и программирования и является причиной неэффективной работы на компьютере ряда мощных логических средств. С точки зрения методологии ситуация ясна - должны быть проведены исследования, которые позволят сгладить эти противоречия. Однако на практике сделать это довольно сложно: имеющийся сегодня опыт показывает, что при таком "сглаживании" либо проблема эффективности остается нерешенной, либо выхолащивается суть логических методов.
С другой стороны, эффективная реализация нетривиальных логических .методов способна привести к значительным достижениям. В частности, эти методы могут резко повысить уровень "'интеллекта" компьютера, а также снабдить его средствами, решающими те задачи, которые сегодня из-за высокой сложности решению не поддаются. Настоящая диссертационная работа посвящена именно этой проблеме.
Цель работы. Основной целью работы является разработка системы логического программирования в ограничениях, основанной на идеях семантического программирования. Эта система, с одной стороны, должна быть достаточно мощной для решения широкого класса сложных проблем, и, с другой стороны, допускать эффективную реализацию на компьютере. Принципиальная задача, которую необходимо решить для достижения этой цели, - нахождение эффективных стратегий в случае большого пространства поиска.
Методы исследования. Настоящая работа использует средства двух активно развивающихся областей прикладной логики. Во-первых, это семантическое (Е-) программирование, предложенное в работах Ю.Л. Ершова, С.С. Гончарова и Д.И. Свириденко1 2. Во-вторых, это логическое программирование в ограничениях, развитое в работах Ж.-Л. Лассе, Джафара, В. Сарасвата, П. ван Хентенрика и других.
Научная новизна. Результаты диссертации являются новыми и носят теоретический характер. В рамках настоящих исследований была построена эффективная процедурная семантика Е-яоыков; развиты новые стратегии поиска решения в большом комбинаторном пространстве; известные стратегии обобщены на случай произвольных дизъюнкций; разработан метод объединения функционального и логического стилей программирования и па его основе развит функционально-логический язык Флэпг; разработана техника реализации систем логического программирования (например, новый способ восстановления значений во время бэктрекинга); получен ряд других результатов.
Практическая ценность. Метод, развиваемый в настоящей работе, является эффективным средством решения комбинаторных проблем высокой сложности. Это задачи составления расписаний, задачи управления ресурсами, финансовые задачи и другие. Объединение логической системы, способной решать сложные задачи, и гибкого выразительного языка программирования позволяет добиться в рамках одного подхода целей, которые обычно несовместимы друг с
Ю.Л. Ершов. Е-олределимость яа допустимых множествах. ДАН, 285(1985), 1, 792-794
С.С.Гончаров, Д.И. Сиириденко. Е-лроградтетроваиие Вычислительные системы, 107, Новосибирск, 1985, с.24-51.
См., напр., P. Van Heateiiryck. Constraint Satisfaction in Logic Programming. The MIT Press, Cambridge, 1989.
другом. Например, выразительность и легкая модифицируемость программ не противоречат в нашей системе высокой эффективности вычислений. Несмотря на то, что развиваемые в диссертационной работе средства являются универсальными, с их использованием удается решать задачи, сложность которых обычно требует применения узкоспециализированных систем.
Апробация работы. Результаты работы докладывались на международных конференциях по математической логике, прикладной логике, логическому программированию и других. Было сделано 2 приглашенных (PLILP'93, Эстония, NSL'94, Япония), 6 пленарных и несколько секционных докладов. Доклады делались на семинарах ИМ СО РАН, МГУ, ИПМ, КГУ, ИрВЦ, ИГУ и многих других. По результатам исследований была проведена серия докладов в Немецком центре искусственного интеллекта (Кайзерслаутерн, 1992).
Логическая система, развиваемая в диссертации, была реализована в рамках языка Флэнг. С использованием Флзнг-системы был решен ряд классических и практических задач высокой сложности. Практическая работа с методом показала его высокую эффективность, универсальность и гибкость.
Публикации. Результаты диссертации опубликованы в работах [1-27].
Структура и объем работы. Диссертационная работа изложена на 183 страницах и состоит из введения, четырех глав, заключения и списка литературы (150 наименований).
