Samarqand davlat universiteti raqamli texnologiyalar fakulteti amaliy matematika yo

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
RAQAMLI TEXNOLOGIYALAR FAKULTETI
AMALIY MATEMATIKA YO’NALISHI
202-GURUH TALABASI
G’AYBULLAYEV DILSHODXONNING
“ALGORITMLAR VA MA’LUMOTLAR STRUKTURASI” FANIDAN
“Farak-Kolton va Bender algoritmi”



KURS ISHI


Tekshirdi:Yusupov O


SAMARQAND –2022


Mundarija
Kirish Uchun qoyiyilgan mavzu…………………………………………………………3
Kirish………………………………………………………………………………………………………………..3
Farak-Kolton va Bender algoritmi…………………………....…………………4
Farak-Kolton va Bender algoritmi yordamida eng kichik umumiy ajdodni toppish…………………………………………………………………..5
Algoritm samaradorligini baholash…………………………………………….9
LCA va statik RMQ o'rtasidagi munosabat…………………………………..10
RMQ ning LCA ga qisqarishi…………………………………………………..11
LCA muammosini RMQ muammosiga qisqartirish…………………………..13
.Xulosa……………………………………………………………………………28
Foydalanilgan adabiyotlar……………………………………………………....29

KIRISH

Biz C++ dasturlash tilida ko’plab har xil masala va misollarni tuzdik va shular bilan massevlar bilan ishlashni ham o’rgandik, Dasturlash tillarida shunday masalalar ham kilishi mumkin, biz u masalalarni boshqa usulda ishlashimiz ham mumkin, ya’ni masala shartini uzgartirmagan holda bir turdan boshqa turga utkazamiz.Bunga misol qilib FKB masalasini RMQ masalasiga kiltirishni kurishimiz mumkin. FKB (eng past umumiy ajdod), Bir juft tugun berilgan, ildizdan eng uzoqda joylashgan umumiy ajdod. RMQ (minimal so'rov oralig'i): Bu algoritm nazariy nuqtai nazardan juda muhim, chunki u nafaqat FKB ni, balki umumiy holatda chiziqli oldindan hisoblash va har bir so'rov uchun doimiy statik RMQ ni ham echishga imkon beradi.