O’zbekiston respublikasi

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI

SHAROF RASHIDOV NOMIDAGI

SAMARQAND DAVLAT UNIVERSITETI


MATEMATIKA FAKULTETI AMALIY MATEMATIKA TA’LIM YUNALISHI 2-KURS 210-GURUH ALGORITMLASH ASOSLARI VA MA’LUMOTLAR STRUKTURASI FANIDAN


KURS ISHI


MAVZU: Landau-vishkin algoritmi (k nomuvofiqlik).


Bajardi:Xudoyberdiyev.X Tekshirdi:Nurmamatov.M

Mundareja:

1.Kirish________________________________________________ 3
2.Landau-Vishkin algoritmining modifikatsiyasi ________________4
3.Abstrakt ______________________________________________5
4.Sakrab chiquvchi qurbaqa muammosi_______________________6
5.Algoritm haqida tushuncha va malumotlar___________________8
6.Qurilish pm____________________________________________13
7.Landa-vishkin algoritmni amalga oshirish____________________14

Kirish.
Muammoning bayoni: matn va namuna soni berilgan , Naqsh bilan mos kelmaydigan belgilardan kop bulmagan uzunlikdagi matnning barcha pastki qatorlarni toppish talab qilinadi. Bu muommo Landau-Vishkin algoritmi(k nomuovofiqlik) bilan hal qilinadi.
L × L matritsasini to'ldirishning kanonik dinamik dasturlash strategiyasiga alternativa (ikki qatorlar teng uzunlikdagi L bo'lsa), tahrirlar soni ortib borayotgan eng uzun mos keladigan pastki qatorlarni takroriy ravishda topishdir. Bu kontseptsiya birinchi marta Landau va Vishkin ( Landau va Vishkin [1989] ) tomonidan taklif qilingan va ko'pincha Landau-Vishkin algoritmi deb ataladi (garchi Landau-Vishkin deb ham ataladi, bu 1986 yilda nashr etilgan LandauVishkin algoritmi emas ( Landau va Vishkin [1986]). )). Oddiylik uchun biz Landau-Vishkin algoritmiga murojaat qilamiz ( Landau va Vishkin [1989]Ushbu qog'ozni eslatish uchun LV sifatida. LV bilan cheklanishlardan biri shundaki, u faqat Levenshtein masofaviy baholash sxemalari uchun taklif qilingan va u umumiy ball sxemalari uchun ishlashi isbotlanmagan.
Ushbu maqolada biz ilgari taklif qilingan Landau-Vishkin ( Landau va Vishkin [1989] ) algoritmining kengaytmasini taqdim etamiz, bu Smit-Waterman algoritmini optimallashtirish, xususan, Levenshtein masofaviy penalti ballari bilan tarmoqli global tekislash uchun. Biz Landau-Viskhinning xuddi shu printsipi nafaqat Levenshtein masofaviy penalti ballari bilan global taxminiy chiziqni moslashtirishga, balki salbiy bo'lmagan ball sxemalari bilan har qanday tarmoqli global yoki yarim global taxminiy simlarni moslashtirish muammolariga ham qo'llanilishi mumkinligini ko'rsatamiz. Bunga erishish uchun biz birinchi navbatda sakrab yuruvchi qurbaqa deb ataladigan taxminiy satrlarni moslashtirish muammosini umumlashtirishni taklif qilamiz.muammoni ko'rsating va ijobiy penalti ko'rsatkichlariga ega bo'lgan barcha tarmoqli global va yarim global taxminiy qatorlarni moslashtirish muammolarini Leaping Toad muammosiga aylantirish mumkinligini ko'rsating. Keyin biz Landau-Vishkin algoritmiga asoslangan Leaping Toad muammosi uchun umumiy dinamik dasturlash yechimi bo'lgan LEAPni taklif qilamiz. Nihoyat, biz LEAP orqali bitvektorlashtirilgan de Bruijn ketma-ketligiga asoslangan optimallashtirishni taqdim etamiz. Biz ko'rsatamizki, LEAP zamonaviy bit-vektorli Levenshtein masofaviy tatbiqiga qaraganda 7,4 baravar tezroq va Needleman-Wunschning zamonaviy parallel affin bo'shliq penalti ilovalariga qaraganda 32 baravar tezroq.