Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Տրամաբանական ծրագրերի օպտիմիզացման մասին

Խաչատրյան, Սուրեն Արտաշեսի (2014) Տրամաբանական ծրագրերի օպտիմիզացման մասին. PhD thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (124Kb) | Preview

    Abstract

    Աշխատանքը նվիրված է տրամաբանական ծրագրավորման խնդիրներին։ Հետազոտության առարկա են հանդիսանում տրամաբանական ծրագրերը և հարցումները, իսկ դիտարկվող հիմնական խնդիրը՝ տրամաբանական ծրագրերի օպտիﬕզացումը, այն իմաստով, որ ծրագրի և իր ցանկացած թույլա- տրելի հարցման ցանկացած SLD-ծառ դառնա վերջավոր: Այլ կերպ ասած, ծրագիրը դառնա որոշված (terminating) իր թույլատրելի հարցուﬓերի նկատմամբ: Տրամաբանական ծրագրավորումը սկիզբ է առնում Ռ. Կովալսկիի1 և Ա. Կոլմերոյի2 աշխատանքներից, որտեղ առաջարկվում է Prolog լեզուն և դրվում դրա տեսական հիմքերը: Տրամաբանական ծրագրավորման համակարգերի հիմնական խնդիրն է պարզել արդյո՞ք հարցումը տրամաբանորեն հետևում է ծրագրից թե ոչ, և եթե այո, ապա հարցման փոփոխականների ո՞ր արժեքների դեպքում: Տրամաբանական ծրագրավորման համակարգերում որպես արտածման կանոն հիﬓա- կանում օգտագործվում է SLD-ռեզոլյուցիան (Selective Linear Definite clause resolution), որը նկարագրվել է Ռ. Կովալսկիի աշխատանքում: SLD-ռեզոլյուցիայի դերը տրամաբանական ծրագրավորման մեջ ամրապնդվում է 3 աշխատանքում, որտեղ սահմանվում են ծրագրերի տրամաբանական և անշարժ կետի սեմանտիկաները և ցույց է տրվում, որ այս սեմանտիկաները համընկնում են SLD-ռեզոլյուցիայի միջոցով տրվող պրոցեդուրային սեմանտիկայի հետ։ Սակայն SLD-ռեզոլյուցիայի վրա հիմնված տրամաբանական ծրագրավորման համակարգերը մուտքում ստանալով ծրագիր և հարցում կարող են աշխատել անվերջ: Առաջանում է խնդիր՝ օպտիﬕզացնել ծրագրերը այնպես, որ ծրագրի և իր ցանկացած թույլատրելի հարցման ցանկացած SLD-ծառ դառնա վերջավոր: Հաշվի առնելով Չորչի թեորեմը, կարելի է ակնկալել, որ բավականաչափ հարուստ լեզուների համար դրված օպտիﬕզացման խնդիրը կլինի անլուծելի։ Իրոք՝ աշխատանքից հետևում է, որ այն անլուծելի է։ Հետևաբար բնական է ուսոմնասիրել խնդիրը ծրագրերի որոշ դասերի համար: Մ. Բեզմեմի5 աշխատանքում նկարագրված են ռեկուրենտ ծրագրերի և սահմանափակ հարցուﬓերի գաղափարները: Ցույց է տրվում, որ ռեկուրենտ ծրագրերը որոշված են սահմանափակ հարցուﬓերի նկատմամբ: В данной работе исследуются проблемы логического программирования. Предметом исследования являются логические программы и запросы, а рассматриваемая основная проблема – оптимизация логических программ в том смысле, что любое SLD-дерево программы и любого допустимого запроса этой программы становится конечным. Другими словами, исследуется проблема оптимизации логических программ с помощью которой программа становится завершаемой по отношению к ее допустимым запросам. Логическое программирование организовано вокруг языка Пролог, созданного А. Кольмероэ на основе процедурной интерпретации предложений Хорна, предложенной Р. Ковальским. По сути, логические программы – это базы знаний. Делается запрос к системе логического программирования, на который она должна ответить на основе программы. Система логического программирования должна ответить, является ли запрос логическим следствием программы или нет, и, если да, то при каких значениях переменных, использованных в запросе. В системах логического программирования в качестве правила вывода в основном используется SLD-резолюция (Selective Linear Definite clause resolution). Но для некоторых программ и запросов системы логического программирования, основанные на SLD-резолюции, могут работать бесконечно. Возникает проблема, оптимизации программы таким образом, чтобы любое SLD-дерево программы и любого допустимого запроса этой программы стало конечным. В общем случае, проблема оптимизации неразрешима. Таким образом, представляется целесообразным изучить специальные случаи логических программ. В рамках данной работы проблема оптимизации рассматривается для следующих видов программ: логических программ, не использующих переменные, логических программ не использующих функциональные символы местности > 1 и монадических программ (программы, которые не используют функциональные символы местности > 1, и используют только предитакные символы местности 1). М. Безем ввел понятия так называемых рекурентных программ и ограниченных запросов и показал, что рекурентные программы завершаемы по отношению к ограниченным запросам. В работе представлены трансформации, при которых программы вышеуказанного типа и их допустимые запросы преобразовываются в рекуррентные программы и ограниченные запросы с использованием методов ограниченного логического программирования (constraint logic programming). В результате, решается проблема оптимизации для данных видов программ. Запрос допустим для программы, если он использует только предикатные символы, которые используются в этой программе. Следует отметить, что рассматривая только допустимые запросы, мы не нарушаем общности, так как если запрос не является допустимым для программы, то, очевидно, он не является логическим следствием этой программы. The thesis is devoted to the study of some problems of logic programming. The objects of study are logic programs and goals. The main problem studied is the optimization of logic programs in the sense that any SLD-tree of a program and any permitted goal of this program become finite. In other words, the optimization problem is studied by which a program becomes terminating with respect to its permitted goals. Logic programming is organised around Prolog language, which was created by A. Colmerauer, based on R. Kowalski’s procedural interpretation of Horn clauses. Logic programs are in essence knowledge bases. The logic programming system is queried, to which it should answer based on the knowledge in the program. The logic programming system should answer whether a goal is a logical consequence of a logic program or not and, if yes, for which values of the variables used in the goal it happens. In a logic programming system SLD-resolution (Selective Linear Definite clause resolution) is basically used as an inference rule. But for some programs and goals logic programming systems based on SLD-resolution can work infinitely. A problem arises, namely to optimize programs such that any SLD-tree of a program and any permitted goal of this program will become finite. In general, the optimization problem is unsolvable. Thus, it seems appropriate to study specific cases of logic programs. In the framework of this thesis the optimization problem is considered for the following three program classes: variable-free logic programs (programs which do not use variables), functional symbol-free logic programs (programs which do not use functional symbols of arity > 1), and monadic programs (programs which do not use functional symbols of arity > 1 and use only predicate symbols of arity 1). M. Bezem introduced the concepts of the so-called recurrent programs and bounded goals. It is shown that recurrent programs are terminating with respect to bounded goals. In the thesis transformations are introduced by which programs of the above-mentioned classes and their permitted goals are transformed into recurrent programs and bounded goals by the use of constraint logic programming methods. As a result, the optimization problem is resolved for these classes. For a program, a goal is permitted if it uses only predicate symbols which are used in that program. It is to be noted that considering only permitted goals does not break the generality because if a goal is not permitted for a program it obviously is not a logical consequence of that program.

    Item Type: Thesis (PhD)
    Additional Information: Об оптимизации логических программ. On optimization of logic programs.
    Uncontrolled Keywords: Хачатрян Сурен Арташесович , Khachatryan Suren A.
    Subjects: Informatics and Computer Systems
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 04 Oct 2016 16:05
    Last Modified: 05 Oct 2016 17:06
    URI: http://etd.asj-oa.am/id/eprint/3563

    Actions (login required)

    View Item