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

Տրամաբանական ծրագրավորման որոշ ալգորիթմական պրոբլեմների մասին

Հայկազյան, Լևոն Արշալույսի (2012) Տրամաբանական ծրագրավորման որոշ ալգորիթմական պրոբլեմների մասին. PhD thesis, ԵՊՀ.

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

Download (108Kb) | Preview

    Abstract

    Աշխատանքը նվիրված է տրամաբանական ծրագրավորման խնդիրներին: Ուսումասիրության առարկան են հանդիսանում այսպես կոչված մաքուր տրամաբանական ծրագրերը' ծրագրեր որոնք չեն պարունակում ներդրված պրեդիկատներ: Ուսումասիրության հինական խնդիրն են հետևման, համարժեքության և Հորնի ծրագրերի համար նաև այսպես կոչված ∆-համարժեքության պրոբլեմերը: Տրամաբանական ծրագրավորումը սերում է թեորեմերի ավտոմատ ապացուցման հետազոտություններից: Հիշվելով Հերբրանի աշխատանքի վրա' Ռոբինսոնի աշխատանքում ներկայացվում է թեորեմերի ապացուցման ռեզոլյուցիայի մթոդը, որն առավել հարմար է ավտոմատացման համար: Տրամաբանական ծրագրավորման հիմքում ընկած է Կովալսկիի, աշխատանքներում առաջ քաշվող այն գաղափարը, որ ալգորիթմը բաղկացած է երկու տարբեր կոմպոնենտներից' տրամաբանություն և կառավարում: Ալգորիթմ տրամաբանությունը նկարագրում է թե որն է պրոբլեմը, իսկ կառավարումը' թե ինչպե՞ս պետք է լուծել պրոբլեմը: Տրամաբանական ծրագիրը նկարագրում է միայն ալգորիթմ տրամաբանությունը, իսկ կառավարում իրականուցնում է տրամաբանական ծրագրավորման համակարգը' հիմնվելով թեորեմերի ավտոմատ ապացուցման մթոդների վրա: Ժամանակակից տրամաբանական ծրագրավորումը սկիզբ է առնում Կովալսկիի և Կոլմրոյի աշխատանքներից, որտեղ առաջարկվում է PROLOG լեզուն և դրվում դրա տեսական հիմքերը: PROLOG լեզվում օգտագործվում են Հորնի ծրագրեր' դրական լիտերալ պարունակող Հորնի դիզյունկտների վերջավոր բազմություններ: Սա հնարավորին է դարձնում SLD-ռեզոլյուցիայի կիրառումը որպես պրոցեդուրային սեմանտիկա: Վերջինս հանդիսանում է Ռոբինսոնի ռեզոլյուցիայի էֆեկտիվ տարատեսակ: Հորնի ծրագրերի դերը տրամաբանական ծրագրավորման մջ ամրապնդվում է 7,8 աշխատանքումերում, որտեղ սահմանվում են այդպիսի ծրագրերի տրամաբանական և անշարժ կետի սեմանտիկաները և ցույց է տրվում, որ այս սեմանտիկաները համընկնում են SLD-ռեզոլյուցիայի միջոցով տրվող պրոցեդուրային սեմանտիկայի հետ: Диссертация посвящена проблемам логического программирования. Предметом исследования являются так называемые чистые логические программы, т.е. логические программы, не использующие встроенные предикаты. Основными задачами являются проблемы следования и эквивалентности, а для хорновских программ также проблема Д-эквивалентности. Корни логического программирования ведут к исследованиям в области машинного доказательства теорем. Логическое программирование основано на идее Ковальского о том, что алгоритм состоит из двух отдельных компонент - логики и управления. Логика алгоритма описывает в чем состоит проблема, а управление - как ее решить. Логическая программа описывает только логику алгоритма, а yправление организовывается системой логического программирования основываясь на методах машинного доказательства теорем. Современное логическое программирование организовано вокруг языка ПРОЛОГ, в котором используются хорновские и обобщённые логические программы. При создании систем логического программирования возникает множество алгоритмических проблем. Логические программы по сути являются базами знаний. Система логических программ получает запросы, на которые она должна ответить на основе знаний, имеющихся в программе. Таким образом, важнейшей проблемой для логического программирования является проблема следования: является ли запрос следствием логической программы. Известно, что эта проблема является Е^-полной для хорновских программ. Эта проблема может быть исследована как для обобщённых логических программ, так и для подклассов программ и запросов. В системах логического программирования часто требуется преобразовать одну программу в другую, которая по определённым признакам является более предпотительной. Ввиду этого возникает необходимость проверить являются ли две программы эквивалентными. The thesis is devoted to problems of logic programming. The objects of the study are so called pure logic programs, that are logic programs that do not use built-in predicates. The main problems studied are the problems of consequence and equivalence and for Horn programs also the problem of A-equivalence. The roots of logic programming go to the research in automated theorem proving. Logic programming is based on the idea of Kowalski that algorithms consist of two separate com-ponents - logic and control. The logic of an algorithm describes what the problem is and the control - how to solve the problem. A logic program only describes the logic of the algorithm, while the control is left to the logic programming system, which is based on methods of au-tomated theorem proving. Contemporary logic programming is organised around PROLOG language, which uses both Horn and general programs. A number of algorithmic problems arise in construction of logic programming systems. 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. Thus, the most important problem in logic programming is the problem of the consequence - whether a query is a consequence of a logic program. This problem is known to be £0-complete for Horn programs. This problem can be studied for general logic programs as well as for subclasses of programs and queries. In logic programming systems a program often needs to be transformed into another one, which is by some characteristic preferable to the original one. So there is a need to test whether two programs are equivalent. This problem also can be studied for general logic programs as well as subclasses of programs. Each Horn program has a least Herbrand model, which is the set of atoms that are consequences of the program. So for Horn programs another notion of equivalence - the equality of least models can be considered. This notion is called A-equivalence. The problem of A-equivalence can also be studied for subclasses of Horn programs.

    Item Type: Thesis (PhD)
    Additional Information: О некоторых алгоритмических проблемах логического программирования. On some algoritmic problems of logic programming.
    Uncontrolled Keywords: Айказян Левон Аршалуйсович, Haykazyan Levon A.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 01 Dec 2015 10:31
    Last Modified: 13 Mar 2017 14:20
    URI: http://etd.asj-oa.am/id/eprint/63

    Actions (login required)

    View Item