Graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari

Mavzu yuzasidan savollar:
1. Minimal yo’lni topish masalasi yechish uchun qanday algoritmlar ishlab chiqilgan?
2. Deykstra algoritmining murakkabligini baholang.

17-ma’ruza. Satrlarda qismiy satrlarni qidirish algoritmlari

17.1. Qismiy satrlarni izlashda primitiv algoritmlarning kamchiligi

Satrlardan qismiy satrni qidirish algoritmi – bu matnda (text) qismiy satr (pattern) topishga imkon beradigan satrlar ustidagi algoritmlar sinfi. U matn muharrirlari, MBBT, qidiruv tizimlari, dasturlash tillari va boshqalarda o'rnatilgan funksiya sifatida ishlatiladi.
Qidiruv vazifalarida qidiruv satrni “igna” (inglizchadan - "needle") va qidiruv o'tkaziladigan satrni “g’aram” (ingliz tilidan - "haystack") deb belgilash odat tusiga kirgan. Shuningdek, biz qidirish olib boriladigan alifboni Σ bilan belgilaymiz.
Primitiv algoritmning muvaffaqiyatsizligi. Agar satrlar birdan boshlab raqamlangan deb hisoblasak, eng oddiy “qo'pol kuch” (Brute force) algoritmi (sodda algoritm) quyidagicha bo’ladi:

for i=0...|haystack|-|needle|

for j=0...|needle|
if haystack[i+j + 1]<>needle[j]
then goto 1
output("Topildi: ", i+1)
1:
Eng oddiy qidirish algoritmi, eng yaxshisi, |haystack| - |needle| +1 taqqoslash; agar bir-biriga o'xshashliklar ko'p bo'lsa, tezlik O(|haystack|·|needle|) ga tushadi.
Primitiv algoritm o'rtacha 2 soatlik taqqoslashda ishlayotgani isbotlangan.
Bugungi kunda qismiy satrlarni qidirish algoritmlarining xilma-xilligi mavjud. Dasturchi bunday omillarga qarab, mosini tanlashi kerak.

1. 
   Optimallashtirish kerakmi yoki primitiv algoritm yetarlimi? Jimlik bo’yicha, bu dasturlash tillarining standart kutubxonalari amalga oshiradi.
   
2. 
   Foydalanuvchining "dushmanligi". Boshqacha aytganda: foydalanuvchi ataylab algoritm sekin bajariladigan ma'lumotlarni aniqlaydimi? Eng oddiy holatda O (|haystack| · | needle|) ball qo'yadigan juda oddiy algoritmlar mavjud, lekin "muntazam" ma'lumotlarda solishtirishlar soni | haystack | dan ancha kam. Faqat 1990-yillarda O (| haystack |) ning murakkabligini, eng yomon holatda va | haystack | o'rtacha.
   
3. 
   Tilning grammatikasi qidiruvni "o'rtacha" tezlashtiradigan ba'zi evristikalarga dushman bo'lishi mumkin.
   
4.