Markov (yoki normal) algoitmlar

---

________________________________________________________________________________________________________
Markov (yoki normal) algoitmlar
1950-yillarning boshlarida rus matematikasi A. A. Markov
ramzlarning satrlarini bir satrdan boshqasiga mexanik tarzda o'zgartirish muammosiga hujum qilish uchun "normal
algoritmlar" deb atagan narsani taklif
qildi. Biz ularni chaqiramiz
Markov algoritmlari
. Ushbu o'zgarish
bizning ko'plab umumiy muammolarimizdan ajralishdir. Masalan
, ikkita raqamni qo'shish x va y "x + y" qatorini " z " qatoriga aylantirish muammosi deb hisoblash mumkin, bu erda "z" x
va y yig'indisini ifodalaydi. hujjatlar uchun so'rovlarni so'rovni qondiradigan hujjatlarni ifodalovchi satrlarga ifodalash
.
Markov algoritmlari bilan ishlashda yodda tutish kerak bo'lgan bir nechta asosiy ko'rsatmalar:
1. Ipni o'zgartirganda, biz odatda bir vaqtning o'zida butun ipda
(o'zboshimchalik bilan uzun bo'lishi mumkin) ishlashni xohlamaymiz, aksincha uning faqat kichik qo'shni qismi.
2. Ushbu algoritmlardan foydalanadigan qurilma
ma'lum bir satr ichida berilgan substring hodisalarini tanib olishga qodir deb taxmin qiling. Hodisalar
soni bir nechta bo'lishi mumkin va bir-birining ustiga chiqishi mumkin.
3. Substringning ma'lum bir hodisasini uni yulduzcha (*) bilan belgilash bilan ajratish mumkin.
Misol:
so'z
ratatattat
string tat uch keyingi hodisalar o'z ichiga oladi, ya'ni
ra * tat * attat
rata * tat * tat
ratatat*tat *
ushbu uchta hodisaning dastlabki ikkitasi bir harf bilan kesishadi.
Biz sanab sifatida bu hodisalar ko'rib chiqamiz, va b a birinchi yuzaga sifatida mag'lubiyatga B bir mag'lubiyatga a chap-
eng yuzaga murojaat qiladi.
Bu
bo'sh to'plamga o'xshash rol o'ynaydi. Agar berilgan satr bo'lsa A o'z ichiga oladi n belgilar, bo'sh satr V bor deb
hisoblanadi n+1 hodisalar A: birinchi belgidan oldin (birinchi paydo bo'lishi V), oxirgi
belgidan keyin va har ikki qo'shni belgi o'rtasida.
Markov algoritmi tuzilgan transformatsiyalar-bu belgilangan satrning birinchi paydo bo'lishini almashtiradigan
o'zgarishlar a berilgan satrda boshqa belgilangan satr bilan B.Markov algoritmlari
bunday o'zgarishlarning ketma-ketligidan iborat.
Ta'rifi
- Keling, alifbo deb nomlangan berilgan cheklangan belgilar to'plamidan belgilar satrlarini ko'rib chiqaylik. Biz
aytaylik, alifboda belgilar mavjud emas"
→ "va"•".
Oddiy (Markov) ishlab chiqarish-bu satr a → B, bu erda a va B alifbodagi satrlar. A
yakuniy (Markov) ishlab chiqarish-bu satr a → *B, bu erda a va B alifbodagi satrlar.
Ishlab chiqarishda A→ B (A → *B) the
oldingi
a va
natija
bu B.
Ta'rifi
- Ruxsat Bering
→ B (yoki A→ *B) a va B alifbosidagi satrlari bir Markov ishlab chiqarish bo'ling. Ruxsat bering
S alifbosida ramzlari bir mag'lubiyatga bo'lishi. Ishlab chiqarish
amaldagi
uchun S mavjud bo'lganda
kamida bitta hodisa A yilda S.aks holda ishlab chiqarish
qo'llanilmaydi
S. ga
misollar:
alifbo a, b, ingliz alifbosi bo'lsin..., z. satr bo'lsin S "abactababrstc" bo'ling
- ishlab chiqarish to'g'risidagi qonunni qo'llash
→ s bbb, biz "abbbbababrstc" olish
- ishlab chiqarish ba qo'llash → * biz olish S biri "aonectababrstc"
- ishlab chiqarish yorlig'ini qo'llash
→ V dan S gacha biz "abacabrstc" ni olamiz
Cse6339 3.0 hisoblash tilshunosligiga kirish
Insructor: Nik Cercone – 3050 LAS - [e-mail]
Qishki Semestr, 2014 Yil
Markov Algoritmlari
Abc ishlab chiqarish→ rst S uchun amal qilmaydi.