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

Հակադրության խնդիրներում գիտելիքների յուրացման և կիրառման ալգորիթմների և ծրագրերի մշակում

Գրիգորյան, Սեդրակ Վարդանի (2016) Հակադրության խնդիրներում գիտելիքների յուրացման և կիրառման ալգորիթմների և ծրագրերի մշակում. PhD thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

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

Download (694Kb) | Preview
    [img]
    Preview
    PDF (Thesis)
    Available under License Creative Commons Attribution.

    Download (1814Kb) | Preview

      Abstract

      Չլուծված կոմբինատոր խնդիրների դասում առայժմ լուծումներ փնտրելու արդյունավետ եղանակ է համարվում մարդու գիտելիքների կիրառմամբ լուծումների փնտրման մոտեցումը: Այս հետազոտության շրջանակներում ուսումնասիրվում է կոմբինատոր խնդիրների՝ լայն կիրառական նշանակություն ունեցող դաս: Այն ներառում է խնդիրներ, որոնք կարող են ներկայացվել որպես հակադրության պայմաններում որոշման կայացում: Դասը ներառում է այն խնդիրները, որտեղ լուծումների բազմությունը ներկայացվում է վերարտադրելի ծառի տեսքով (RGT problems): Այս դասին են պատկանում այնպիսի կարեւոր խնդիրներ, ինպիսիք են՝ համակարգչային ցանցի պաշտպանումը հարձակումներից, լավագույն ռազմավարության մշակումը կառավարման եւ մարքեթինգի մրցակցային միջավայրերում, ռազմական միավորների պաշտպանությունը տարատեսակ հարձակումներից, կոմբինատոր խաղերը եւ այլն: Այս խնդիրները հաջողությամբ հետազոտվել են ՀՀ ԳԱԱ Ինֆորմատիկայի եւ ավտոմատացման պրոբլեմների ինստիտուտում 1957թ.-ից սկսած: Խնդիրները RGT դասով սահմանափակելու արդյունքում ստանում ենք՝ բովանդակության սահմանափակում՝ կիրառվող գիտելիքների կապ հաղթող ռազմավարությունների հետ, խնդրի բնորոշման (specification) միջոցով նպատակների սահմանում: Է. Պողոսյանի աշխատանքներում հիմնավորված է, որ մրցակցային խնդիրների RGT դասը վերածելի (reducible) է K միջուկային խնդրի, եւ K խնդրի լուծման ուղղությամբ ձեռք բերված նվաճումները ընդհանրացվում են ամբողջ դասի վրա: 1949 թվականից սկսած [Shannon, Programming a Computer for Playing Chess] ռազմավարության փնտրման ալգորիթմները դիտարկվում եւ հետազոտվում են շախմատի համար, եւ մեր հետազոտությունը նույնպես հետեւում է ընդունված մոտեցմանը: Շենոնի եւ նրա հետեւորդների առաջարկված ալգորիթմները, ինչպես նաեւ ներկա շախմատային շարժիչներում (engines) կիրառվող ալգորիթմները, գիտելիքների էությունը արտահայտում են պարամետրերի միջոցով, մինչդեռ հետազոտվող խնդիրների կոմբինատոր բնույթը հակասում է միջինացված մոտեցումներով ներկայացման եղանակներին: Մենք դիտարկում ենք չլուծված խնդիրներում փորձագետի՝ լուծումներ փնտրելու վարքի մոդելները, որի հիմնական բաղադրիչներն են՝ ա) մարդու որոշակի գիտելիքների պաշարը, բ) ըստ գիտելիքների իրավիճակը ճանաչելը եւ որոշումներ կայացնելը գ)կայացված որոշումներից արդյունքներ ստանալը, որոնք նպաստում են գիտելիքների փոփոխմանը, կատարելագործմանը կամ նոր գիտելիքների դուրս բերմանը: Рассматривается класс комбинаторных задач, определяемых как задачи, у которых пространства решений представляют собой воспроизводимые игровые деревья (RGT). Класс RGT включает в себя такие важные задачи, как защита компьютерных сетей от вторжений, разработка оптимальной управленческой и маркетинговой стратегии в условиях конкуренции, защита военных единиц от различного вида атак, шахматы и игры на подобие шахмат. Было показано, что задачи RGT сводятся друг к другу, в частности к выбранной стандартной задаче K класса RGT, к шахматам, в то время, как достижения для K могут быть распространены на весь класс. Класс RGT представляет важные нерешенные проблемы, для которых человеческие подходы для обнаружения решений остаются на данный момент наиболее эффективными. По указанным выше причинам исследования по построению моделей решения RGT задач, основанных на адекватных экспертных знаниях, являются актуальными и успешно проводятся в Институте Информатики и Проблем Автоматизации при Академии Наук Армении с 1957 года. В данной работе разрабатываются алгоритмы и программы, поддерживающие приобретение общих и персонализированных экспертных знаний для RGT задач, и изучаются пути для их эффективного применения. Разработать модели и программы представления RGT знаний и проверки соответствия ситуаций знаниям. Обосновать адекватность разработанных моделей и алгоритмов представления RGT знаний и проверки соответствия ситуаций знаниям для различных RGT задач. Разработать алгоритмы Персонализированного Планирования и Интегрированного Тестирования (PPIT) поиска стратегий для RGT задач на основе обработки планов и целей. Обосновать адекватность алгоритмов поиска стратегий для класса RGT. На основе RGT Solver предоставить инструменты индивидуального интерактивного обучения и разработать модели обучения адекватные методам обучения RGT экспертов. Научная новизна Разработаны модели представления RGT знаний, основанные на языковых категориях "быть-, иметь-, делать-", и алгоритмы проверки соответствия ситуаций знаниям. Экспериментально обоснована адекватность алгоритмов представления и соответствия для различных RGT задач. Разработан алгоритм и программа PPIT поиска стратегий на основе анализа и использования планов и целей. Приводятся эксперименты доказывающие адекватность разработанных алгоритмов поиска стратегий PPIT для RGT задач (в шахматах, на примере этюда Рети, предложенном как тест Ботвинником). На основе RGT Solver разработана модель интерактивного индивидуального обучения шахматам. На основе RGT Solver предоставить инструменты индивидуального интерактивного обучения и разработать модели обучения адекватные методам обучения RGT экспертов. Разработаны модели представления RGT знаний, основанные на языковых категориях "быть-, иметь-, делать-", и алгоритмы проверки соответствия ситуаций знаниям. Экспериментально обоснована адекватность алгоритмов представления и соответствия для различных RGT задач. Разработан алгоритм и программа PPIT поиска стратегий на основе анализа и использования планов и целей. Приводятся эксперименты доказывающие адекватность разработанных алгоритмов поиска стратегий PPIT для RGT задач (в шахматах, на примере этюда Рети, предложенном как тест Ботвинником). На основе RGT Solver разработана модель интерактивного индивидуального обучения шахматам. We consider a class of combinatorial problems defined as problems where spaces of solutions are Reproducible Game Trees. RGT class includes important problems like computer networks intrusion protection, optimal management and marketing strategy elaboration in competitive environments, defense of military units from a variety types of attacks, chess and chess-like games. It was proved that RGT problems are reducible to the standard kernel problem K, particularly to chess, while achievements for K can be expanded to the entire class. RGT class present important unsolved problems where human approaches in finding solutions stay, yet, the most effective. By the above reasons researches in construction of adequate expert knowledge based models of RGT solutions are actual and are successfully continued in the Institute for Informatics and Automation Problems at the Academy of Sciences of Armenia since 1957. In this work we develop algorithms and programs for acquisition of common and personalized expert knowledge of RGT problems and study ways of their effective applications. Provide models and programs for RGT knowledge presentation and matching situations to the knowledge. Prove the adequacy of developed models of knowledge presentation and matching algorithms for various RGT problems. Implement strategy searching Personalized Planning and Integrated Testing (PPIT) algorithms for RGT problems based on processing of plans and goals. Ensure the adequacy of the strategy searching algorithms for RGT class. Provide RGT Solver based tools and develop models for personazlied interactive tutoring adequate to tutoring of RGT experts. Models for presentation of RGT knowledge based on language “be-, have-, do-” categories and algorithms for matching situations to the knowledge are developed. Experiments on adequacy of algorithms of presentation and matching in various RGT problems are provided. Strategy search algorithms and programs based on plans and goals processing are developed. Experiments proving the adequacy of developed PPIT strategy search algorithms for RGT problems (in chess, particularly for etude of Retie suggested by Bottvinnik as a test) are provided. RGT Solver based personalized interactive tool and methods for tutoring chess similar to master are developed.

      Item Type: Thesis (PhD)
      Additional Information: Исследование и разработка алгоритмов и программ приобретения и эффективного использования знаний в задачах противостояния. Research and development of algorithms and programs of knowledge acquisition and their effective application to resistance problems.
      Uncontrolled Keywords: Григорян С. В, Grigoryan Sedrak
      Subjects: Informatics and Computer Systems
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 03 Oct 2016 10:27
      Last Modified: 29 Mar 2017 14:55
      URI: http://etd.asj-oa.am/id/eprint/3550

      Actions (login required)

      View Item