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

Դիսկրետ էքստրեմալ խնդիրների հետազոտում

Դանոյան, Հայկազ Էդվարդի (2013) Դիսկրետ էքստրեմալ խնդիրների հետազոտում. PhD thesis, ԵՊՀ.

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

Download (1116Kb) | Preview

    Abstract

    Ներկա աշխատանքը նվիրված է կոմբինատոր փնտրման խնդիրների մի մասնավոր դասի և դրա հետ կապված որոշ դիսկրետ օպտիմիզացիոն խնդիրների ուսումնասիրմանը: Համակագչային գիտությունը և ինֆորմացիոն տեխնոլոգիաները, որոնք միտված են լուծելու ինֆորմացիոն արդյունաբերության զարգացման և ինֆորմացիոն հասարակության ստեղծման խնիրները, գործ ունեն ինֆորմացիայի գերմեծ և աճող ծավալների և դրանց տարաբնույթ ալգորիթմական մշակումների հետ: Այսօր նշվում է օրինակ, որ պատմականորեն, մինչև 2003 թվականը մարդկությունը կուտակել է շուրջ (five exabyte) ինֆորմացիա այն պարագայում, երբ ներկայումս այդ նույն ծավալի ինֆորմացիա արտադրվում է յուրաքանչյուր երկու օրվա ընթացքում: Պարզ է, որ նախկինում ստեղծված ալգորիթմները կարող են բավարար արդյունավետ չլինել մուտքային տվյալների նման ծավալների և դրաց աճի նման արագությունների դեպքում: Ըստ այդմ՝ անհրաժեշտություն է առաջանում մշակել նոր ալգորիթմներ և խնդիրների դիտարկման նոր մոդելներ, որոնք իրենց մեջ կներառեն մուտքային տվյալների մեծ և դինամիկ աճող քանակության իրողությունը: Oրինակ` որպես այդպիսի մոդել այսօր հաճախ քննարկվում է տվյալների հոսքի մոդելը (data stream model): Տվյալների հավաքածուների/պարունակության հետ իրականացվող հիմնական տեխնիկական գործողությունները ընդգրկում են տվյալների գրանցման, խմբագրման, հեռացման և փնտրման գործողությունները: Սակայն վերջնական արդյունքում պահանջը որոշակի գիտելիքի կորզումն է, որը կարող է հանդիսանալ փնտրումից հետո իրականացվող մեկ առանձին փուլի աշխատանքի արդյունք, բայց և այն կարող է ինտեգրված լինել փնտրման/ընտրման փուլի հետ: В работе рассматривается ранее предложенный алгоритм (алгоритм Элиаса), который предполагает использование второго методa. Балансированные схемы хешкодирования ассоциируются с покрытиями пространства Хемминга с непересекающимися подмножествами (блоками) равной мощности. В работе: Рассматривается эффективность данного алгоритма в случае кодов Хемминга и Голея. Получены аналитические выражения для эффективности алгоритма при использовании этих кодов. Поскольку совершенные коды существуют лишь в очень «узких» областях значений параметров, то: Рассматривается алгоритм в случаях схем хеш-кодирования, которые получаются разными обобщениями совершенных кодов, таких как квазисовершенные коды, равномерно упакованные коды, почти совершенные коды и т.д. Получены аналитические выражения для эффективности алгоритма в некоторых случаях, а именно для примитивных кодов БЧХ исправляющих двойные ошибки и для расширенных кодов Хемминга. Рассматривается задача оптимальности алгоритма в зависимости от геометрических свойств блоков (в случае балансированных схем хеш-кодирования). Доказано, что алгоритм является оптимальным, если отмеченные блоки изопериметрические множества, частным случаем которых являются сферы. Рассматривается также алгоритм в случае схем хеш-кодирования, когда блоки не пересекаются и являются декартовым произведением сфер более низких размерностей. В работе рассматривается задача нахождения множества ближайших соседей к данному вектору из данного множества в метрике Хемминга. Эффективность решения данной задачи во многом зависит от представления множеств, в которой выполняется поиск. Одним из широко известных методов – представление данных в виде деревьев, а другой-хеширование. In this dissertation the problem of finding of the set of the nearest neighbors to a given vector from a given set in Hamming metric is considered. The efficiency of the solution to this problem in many respects depends on structural representation of sets in which search is carried out. One of the widely known approaches is the data representation in the form of trees, and the other alternative one is the use of hashing technique. Dissertation considers the earlier proposed algorithm (Elias's algorithm), which assumes the second approach. The balanced hash-coding schemes are associated with the coverings of a unit cube by non-intersecting subsets (blocks) of equal power. The efficiency of the algorithm in case of Hamming and Golay codes is considered. Analytical expressions for efficiency of algorithm for these cases are obtained. As perfect codes exist only for very "narrow" domain of parameters then the algorithm is considered special hash-coding schemes obtained by different generalizations of perfect codes such as quasi-perfect codes, uniformly packed codes, nearly perfect codes, etc. Analytical expressions for efficiency of algorithm in certain cases are obtained namely for the primitive double error correcting BCH codes and for the extended Hamming codes. The problem of optimality of the algorithm depending on geometrical properties of blocks (in case of balanced hash-coding schemes) is considered. It is proved that the algorithm is optimum, if the mentioned blocks are isoperimetric sets, the special cases of which are spheres. The algorithm is considered also in case of hash coding schemes when the blocks do not intersect and they are a Cartesian product of spheres of lower dimensions.

    Item Type: Thesis (PhD)
    Additional Information: Исследование дискретных экстремальных задач. Research of discrete extreme problems.
    Uncontrolled Keywords: Даноян Айказ Эдвардович, Danoyan Haykaz E.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 16 Mar 2017 10:31
    Last Modified: 16 Mar 2017 10:31
    URI: http://etd.asj-oa.am/id/eprint/4294

    Actions (login required)

    View Item