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

Դիսկրետ մոդելներում մասնակի բնութագրմամբ տրվող կառուցվածքների գոյություն, կառուցում, նկարագրում

Սահակյան, Հասմիկ Արտեմի (2018) Դիսկրետ մոդելներում մասնակի բնութագրմամբ տրվող կառուցվածքների գոյություն, կառուցում, նկարագրում. Doctor of Sciences thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

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

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

    Download (1400Kb) | Preview

      Abstract

      Աշխատանքը նվիրված է դիսկրետ մոդելավորման մաթեմատիկական խնդիրների ուսումնասիրմանը: Դիսկրետ մոդելները, որոնցում հայտնի են առարկայի միայն որոշակի մասնակի բնութագրեր, առնչվում են ըստ տրված բնութագրերի առարկայի գոյության, կառուցման և նկարագրման խնդիրների հետ: Նրանք առաջ են գալիս գիտական տարբեր տիրույթներում և բազմաթիվ կիրառական խնդիրներում, ինչպիսիք են, օրինակ, ցանցերի մոդելավորումը, փորձերի նախագծումը, պատկերների ճանաչումը, և շատ ուրիշներ: Ամբողջի և նրա մասերի հարաբերակցման սկզբունքների ուսումնասիրումը մաթեմատիկայի զարգացման լուրջ խթան է հանդիսացել: Նշենք երկու խումբ հարակից խնդիրներ և տեսություններ, որոնք ձևավորվել և ուսումնասիրվել են ժամանակի ընթացքում: 1936 թ. Վ. Համբարձումյանը ձևակերպեց հակադարձ խնդիրների մոդելը' մաթեմատիկական խնդիրների դասեր, որոնք ծագում են, երբ հարկ կա ստանալ/հաշվել ինֆորմացիա ներքին կամ թաքնված տվյալների մասին, - արտաքին /կամ հասանելի/ չափումների միջոցով: 1965 թ. Յու. Ժուռավլյովը իր “Ինֆորմացիայի հաշվարկման լոկալ ալգորիթմներ” աշխատանքում ձևավորեց լոկալ շրջակայքերի օգնությամբ ընդհանրական գիտելիքի ձեռքբերման սխեման և ապացուցեց, որ որոշ բնական սահմանափակումների դեպքում կան խնդիրներ, որոնք այս դեպքում ալգորիթմական լուծում չունեն: Այսօր դիսկրետ մոդելավորման տիրույթը ներկայանում է մի շարք ստանդարտ մաթեմատիկական մոտեցումների տեսքով, որոնք ձևավորվել և օգտագործվում են կիրառական խնդիրների լայն դասերի շուրջ: Դիսկրետ մոդելավորման գործիքների թվում են գրաֆների/հիպերգրաֆների տեսությունը, կոմբինատորիկան, գծային և ամբողջարժեք ծրագրավորումը, դիսկրետ տոմոգրաֆիան, խաղերի տեսությունը, ստոխաստիկ պրոցեսների և Մարկովյան շղթաների սխեմաները, բինար ծառերը, և այլք: Ներկա աշխատանքում դիտարկվում են տիրույթում դեռևս չլուծված խնդիրներ՝ մասնակի բնութագրմամբ տրվող կառուցվածքների գոյության, կառուցման, նկարագրման մոդելների տեսքով' հիպերգրաֆների, դիսկրետ տոմոգրաֆիայի, բազմաչափ-բազմարժեք խորանարդի/ցանցի, բինար ծառերի տերմիններով, որոնք մի կողմից ունեն տեսական կարևորություն, մյուսից' մասն են հանդիսանում տարբեր կիրառությունների: Հիպերգրաֆներ: Հիպերգրաֆները մաթեմատիկական մոդելավորման կարևոր գործիք են տարբեր տիրույթների խնդիրների մեկնաբանման համար: Դրանց թվում են ցանցերի մոդելավորման, տվյալների պեղման, գործընթացների պլանավորման և այլ խնդիրներ, որտեղ հիպերգրաֆի գագաթներով ներկայացվում են առարկաներ, իսկ հիպերկողերով տրվում են առարկաների միջև առկա բարդ հարաբերությունները: Հիպերգրաֆի գագաթների աստիճանները, հիպերկողերի հզորությունները, նրանց տարբեր լինելը, մեկը մյուսին չկլանելը, և այլ հատկություններ հանդես են գալիս որպես մոդելի բնութագրեր կամ սահմանափակումներ: Հիպերգրաֆային մոդելների տիրույթի հայտնի և բաց խնդիրներից մեկը' հիպերգրաֆային հաջորդականությունների խնդիրը ներկա աշխատանքի հիմնական նպատակներից մեկն է: Կ. Բերժի1 ձևակերպմամբ այս խնդիրը հանդիսանում է կարևորագույն տեսական թիրախ, իսկ կիրառություններն ընդգրկում են տրանսպորտային ցանցերի գեներացման, մեծածավալ վեբ ինֆորմացիոն համակարգերի և սոցիալական ցանցերի համագործակցային կառուցվածքների վերլուծման և նման այլ խնդիրներ: Արդեն երեք տասնամյակ հիպերգրաֆային հաջորդականությունների խնդիրը ակտիվ հետազոտման առարկա է' Ա.Դյուդնեյ, Չ.Կոլբորն, Դ.Սթինսոն, Վ.Կոկեյ, Դ.Բիլինգտոն, Պ.Լի, Մ.Կորեն, Ն.ԲհանուՄուրթի, Մ.Սրինիվասան, Ռ.ԻնիԼյու, Կ.Կլիվանս, Վ.Ռեյներ, Ս.Բեհրենս, Մ.Ֆեռարա, և ուրիշներ (տարված հետազոտությունները և ստացված արդյունքները հիմնականում վերաբերվում են համասեռ հիպերգրաֆների մասնավոր դեպքերին), սակայն մինչև այսօր այն մնում է բաց խնդիր ինչպես բարդության գնահատման տեսանկյունից, այնպես էլ լուծումների տիրույթի բնութագրման հարցում: Խնդիրը համարժեք է բազմաչափ բինար խորանարդի գագաթների ենթաբազմությունների տրոհումների հզորությունների նկարագրման խնդրին, որն առաջադրվել է Լ.Ասլանյանի կողմից դիսկրետ իզոպերիմետրիկ խնդրի լուծման կապակցությամբ2: Ներկա աշխատանքում ստացված արդյունքները, որոնք ներկայացվում են ինչպես բազմաչափ խորանարդի, այնպես էլ հիպերգրաֆի տերմիններով, առաջինն են, որոնք վերաբերվում են հիպերգրաֆների ընդհանուր դեպքին, և որտեղ տրվում է լուծումների տիրույթի ամբողջական նկարագիրը, այդ տիրույթի կառուցվածքն ու հատկությունները: Работа посвящена изучению математических задач дискретного моделирования. Дискретные модели, в которых известны частичные характеристики данного объекта, связаны с задачами существования, построения и описания объектов с данными характеристиками. Они возникают в разных научных областях и приложениях, таких как моделирование сетей, дизайн экспериментов, распознавание образов и многие другие. В работе рассматриваются нерешенные задачи в терминах гиперграфов, дискретной томографии, многомерной многозначной решетки и бинарных деревьев, которые, имеют теоретическую значимость и являются неотъемлемой частью различных приложений. Исследования проводились по следующим основным направлениям: ^ Изучение проекционных и окрестностных отображений в задачах дискретного моделирования в терминах существования, построения и описания гиперграфов по заданной последовательности степеней вершин. Это одна из хорошо известных и открытых задач в области гиперграфических моделей и, поэтому, является важной теоретической мишенью; приложениями являются задачи генерации транспортных сетей, документо–интенсивные информационные системы и т. д. Основной целью является получение точного описания множества всех гиперграфических последовательностей, которое впервые получено и проанализировано в этой работе. Исследования в области дискретной томографии, где основной целью является привлечение новых ограничений в область задачи в виде полосовых проекций, и в виде не повторяемости элементов. Это те ограничения, которые возникают в разных прикладных задачах отражая условия обобщенных степенных последовательностей и простоты гиперграфов. В этой части работы важными достижениями являются эффективные приближенные алгоритмы задач дискретной томографии. Получено полное описание множества всех гиперграфических последовательностей простых гиперграфов с п узлами и т ребрами в виде подмножества решетки S^+1, в терминах граничных элементов, где граничные элементы генерируются обычными монотонными булевыми функциями п переменных [7], [8], [13]. Получены важные структурные характеристики [9], [14], [21], [22], [24], [25], [26], [27], [29], в том числе: найдены граничные элементы минимального веса; доказано, что они соответствуют начальным отрезкам длины т обратного лексикографического упорядочения вершин бинарного куба Еп, и что они единственны с точностью до перестановки координат; граничные элементы максимального веса соответствуют т-сферическим подмножествам Еп с центром 1; задача их описания эквивалентна задаче описания гиперграфических последовательностей для однородных гиперграфов; найдены пороги rmin и гтах , такие что все последовательности ранга меньший, чем fmin, - являются гиперграфическими, и все последовательности с рангом, больше чем гтах, не гиперграфические; найдено необходимое и достаточное условие существования простого регулярного гиперграфа по заданной последовательностью степеней вершин. Получение указанных результатов частично основано на методе кубическего разбиения решетки Е1^+1 [11], [15], [28], [31]. Разработан эффективный алгоритм G построения бинарных матриц с заданными весами столбцов и отличающимися строками [1], [10], [12], [16], [17], [18], [19], [23], [30]: доказано, что построение очередного столбца матрицы в локальном шаге алгоритма оптимально при рассмотрении в качестве целевой функции числа пар разных строк /оптимальное значение получена простая, в терминах весов столбцов, формула гарантированного результата работы алгоритма. This work is about the studies of mathematical problems of discrete modeling. The discrete models, in which only certain partial characteristics of a given object are known, are connected to the problems of existence, construction and description of objects by the given characteristics. They arise in different scientific domains and application problems, such as network modeling, design of experiments, image recognition, and many others. This work considers still unsolved problems of the domain with the terms of hypergraphs, discrete tomography, multi-dimensional multi-valued grid, and binary trees, which, on the one hand, are of theoretical importance, and on the other are part of different applications. The research is carried out in the following main directions: Studies of projection and neighborhood type mappings in discrete modeling in the form of existence, construction and description problems of hypergraphs, by the given degree sequence. This is one of the well-known and open problems of the hypergraphic field and, thus, stands as a major theoretical target, and its applications include: generation of transport networks, document-intensive web information systems, and others. The main purpose of this part is to obtain a precise description of the set of hypergraphic sequences, — which is presented and analyzed in this work for the first time. Research in the field of discrete tomography, where the main purpose is to include new constraints into the domain, in the form of strip-based projections and non-repeatative elements. These are the constraints, that appear in different application problems and models, reflecting the conditions of generalized degree sequences and the simplicity property of the hypergraphs. In this part of the work important achievements are the efficient approximate algorithms of the discrete tomography problems. The complete description of the set of the degree sequences of simple hypergraphs with n nodes and m edges in a form of a subset of integral grid E£+1 in terms of boundary elements and their convexity closures is obtained, where the boundary elements are generated by monotone Boolean functions [7], [8], [13]. Significant structural features are obtained [9], [14], [21], [22], [24], [25], [26], [27], [29], including: the boundary elements of the minimal weight corresponding to the m-length initial segments of the colex ordering of En are found which are unique up to coordinate permutations; the boundary elements of the maximal weight correspond to the spheric m-subsets of En, centred at 1; the problem of characterization of those elements is equivalent to the degree sequence problem for uniform hypergraphs; thresholds rmin, rmax such that all sequences with rank less than rmin are hypergraphic, and all sequences with rank greater than rmax are not hypergraphic are found; necessary and sufficient condition for existence of simple regular hypergraph with the given degree sequence are found. Obtaining of the mentioned results is partially based on the medhod of cube-type spliting of the grid “£+i [11], [15], [28], [31]. An effective algorithm G for column-by-column constructioning of tomography matrices with the given column weights and with all different rows is developed [1], [10], [12], [16], [17], [18], [19], [23], [30]: it is proven that the each column construction in local step of the algorithm is optimal, when the objective function is defined as the number of pairs of differing rows /the optimal value of which provides the differentity of the rows/; a theoretical estimate of the guarantee of the algorithm result is achieved in the form of a simple formula (given by the column weighs).

      Item Type: Thesis (Doctor of Sciences)
      Additional Information: Существование, построение и описание структур, заданных в частичной характеризации в дискретных моделях. Existence, construction and description of structures given by partial characterization in discrete models.
      Uncontrolled Keywords: Саакян Асмик А., Sahakyan Hasmik A.
      Subjects: Informatics and Computer Systems
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 06 Jul 2018 12:03
      Last Modified: 26 Dec 2018 09:28
      URI: http://etd.asj-oa.am/id/eprint/7483

      Actions (login required)

      View Item