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

Առցանց ալգորիթմական մոդելները տվյալների մաքսիմալ կանոնավորված ենթակառուցվածքի խնդիրներում

Մինասյան, Վահագն Գագիկի (2011) Առցանց ալգորիթմական մոդելները տվյալների մաքսիմալ կանոնավորված ենթակառուցվածքի խնդիրներում. PhD thesis, ԵՊՀ.

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

Download (211Kb) | Preview

    Abstract

    Ատենախոսությունը նվիրված է երկու տարբեր կոմբինատոր խնդիրների համար առցանց ալգորիթմներ կառուցելուն: Դրանք են երկկողմանի գրաֆի մաքսիմալ անկախ բազմություն գտնելու, և երկու սիմվոլային հաջորդականությունների ամենաերկար ընդհանուր ենթահաջորդականություն գտնելու խնդիրները: Այս երկու խնդրիները հայտնի կոմբինատոր խնդիրներ են, և դրանցից յուրաքանչյուրը համարվում է ոլորտի դասական խնդիրներից մեկը: Գրականության մեջ երկու խնդիրներն էլ հանգամանալիորեն ուսումնասիրված են, սակայն մուտքային տվյալների առցանց ներկայացման պարագայում այդ խնդիրների համար արդյունավետ ալգորիթմներ կառուցելու հետ կապված հարցերը դեռ բավարար լուծում չունեն: Ատենախոսության մեջ նշված խնդիրները դիտարկվում են հենց այս համատեքստում, և ատենախոսության արդիականությունը պայմանավորված է առցանց ալգորիթմների նկատմամբ հետաքրքրությամբ, որն իր հերթին, բացի տեսական նկատառումներից, պայմանավորված է նաև նշված երկու խնդիրներին վերաբերվող բազմաթիվ կրառություններով՝ կապված դրանցում տվյալների հոսքերի ի հայտ գալու հետ: Առցանց (online) են համարվում այն ալգորիթմները, որոնք կարող են մշակել մուտքային տվյալները մաս առ մաս՝ հաջորդականորեն ստանալով այդ մասերը և դրան զուգընթաց մուտքային տվյալների արդեն մշակված մասին համապատասխան ելք տրամադրելով: Ի տարբերություն դրա՝ սովորական (կամ offline) են համարվում այն ալգորիթմները, որոնք ենթադրում են, որ մուտքային տվյալները տրված են ամբողջությաբ՝ ալգորիթմի աշխատանքի հենց սկզբից: Այսպիսով՝ առցանց ալգորիթմները բաղկացած են հաջորդական իտերացիաներից, որոնցից հերթականը մշակում է մուտքային տվյալների հերթական մասը: Առցանց ալգորիթմների հետազոտման անհրաժեշտությունը պատմականորեն կապված է տարբեր կիրառություններում տվյալների հոսքերի ի հայտ գալու հետ: Տվյալների հոսքեր մշակող ալգորիթմների ուսումնասիրումը որպես ինտենսիվ հետազոտական տիրույթ ձևավորվել է բոլորովին վերջերս: Ոլորտի նախատիպը կարող է համարվել այն, որ դեռ վաղուց, մասնավորապես ավտոմատների տեսության տիրույթի շրջանակներում, իրականցվել են տվյալների մեկանգամյա կամ բազմակի ընթերցումով հաշվարկներ: This thesis is dedicated to designing online algorithms for two different combinatorial problems. The problems are finding a maximal independent set of a bipartite graph, and finding a longest common subsequence of two strings. Both of these are well known combinatorial problems, and each of them is known through the set of important applications. Both problems are thoroughly discussed in publications, but in the case of online representation of input data, the issues related to designing efficient algorithms for these problems yet do not have a sufficient solution. The thesis addresses problems in this context, and in relevance to the interest in online algorithms. The last, in its turn, is due to not only for theoretical reasons, but also due to appearances of data streams in many applications related to the mentioned two problems. The main objective of the thesis is to develop efficient online algorithms. The following problems are addressed in the context of designing efficient online algorithms: the problem of finding a maximum independent set of a bipartite graph, the problem of finding a longest increasing subsequence of a sequence of numbers and finding a longest common subsequences of two strings. The purpose is to solve these problems and study related constructions in the case of the online input data discipline. In theoretical level the thesis is investigating models and data structures of solve these problems, exploring emerging combinatorial relations and integrating them into the final algorithms for mentioned optimization problems. The practical value of dissertation is related to the objectives of global networks, sensor monitoring systems, financial transaction flow analysis, computational genomics, and others.Диссертация посвящена разработке онлайн алгоритмов для двух различных комбинаторных задач. Это задача нахождения максимального независимого множества двудольного графа и задача нахождения наибольшей общей подпоследовательности для двух заданных последовательностей символов. Обе задачи являются известными комбинаторными задачами, и каждый из них является классической задач в своей области. В литературе обе задачи тщательно обсуждены, но в случае онлайн представления входных данных, вопросы, связанные с проектированием эффективных алгоритмов для этих задач все еще не имеют исчерпывающего решения. Диссертация рассматривает эти задачи именно в этом контексте, и его актуальность связна с интересом к онлайн алгоритмам, что в свою очередь обусловено не только теоретическим интересом, но и тем, что во многих приложениях связанных с упомянутыми задачами появляются потоки данных. Разработка эффективных онлайн алгоритмов является основной целью исследования диссертации. В частности, мы обсуждаем задачу нахождения максимального независимого множества двудольного графа, задачу нахождения наибольшей возрастающей подпоследовательности числовой последовательности, и задачу нахождения наибольшей общей подпоследовательности двух последовательностей символов. Работа нацелена на решение этих задач и исследование характерных комбинаторных структур в случае онлайн представления входных данных. Теоретическое значение диссертации состоит в разработке моделей для решениярассматриваемых задач, в изучении возникающих здесь комбинаторных структур и в их объединении в окончательные алгоритмы решения этих задач. Практическое значение диссертации связано с задачами глобальных сетей, систем сенсорного мониторинга, анализа финансовых потоков, вычислительной геномикой и других.

    Item Type: Thesis (PhD)
    Additional Information: Модели онлайн алгоритмов в задачах максимальной канонизированной подструктуры данных. Models of online algorithms in the problems of maximum canonized substructure of data.
    Uncontrolled Keywords: Минасян Ваагн Гакикович, Minasyan Vahagn G.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 30 Nov 2015 09:32
    Last Modified: 10 Mar 2017 14:59
    URI: http://etd.asj-oa.am/id/eprint/48

    Actions (login required)

    View Item