|
Samarqand davlat universiteti intelektual tizimlar va kompyuter texnalogiyalari fakulteti dasturiy injiniring yo
|
| bet | 1/9 | | Sana | 20.06.2023 | | Hajmi | 1.69 Mb. | | #74642 |
Bog'liq KURS ISHI Algoritmlash 3. Kompyuter tizimlari va tarmoqlari, Elektromagnit maydon energiya, Galiley va Eynshteynning nisbiylik tamoyili, iqtisodiyotda-matematik-modellashtirish, Fizikaviy jarayonlarni modellashtirish imkoniyatini beruvchi das, 2 маъруза Ахборот технологиялар ва уларнинг дидактик имкониятлари (2), Самостоятельная работа №3, (Упражнение) Future Continuous, 6, 9-mavzu. Kesh xotira.(97-110), QULMURODOVDURBEK, 1232sa1s1, 1232sa1s11, Ispaniya, BMI Nodir
OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
INTELEKTUAL TIZIMLAR VA KOMPYUTER TEXNALOGIYALARI FAKULTETI
DASTURIY INJINIRING YO’NALISHI
104 - guruh talabasi
Xabibova Yasmina
“ Fenvik daraxti ” mavzusida
KURS ISHI
Tekshirdi: Absalomova G.
SAMARQAND – 2023
REJA:
Kirish ………………………………………………………………………………3
1. Fenvik daraxti va uning ishlash prinsipi ……………………………………5
2. Dasturlash tillarida amalga oshirish …………………………………………8
3. Fenvik daraxtiga vizual kirish ………………………………………………13
4. Fenvik daraxti / ikkilik indekslangan daraxtlar ………………… 20
/*
5. Rekursiya…………………………………………………………………… 21
6. Rekursiya va dinamik dasturlashni taqqoslash ………………………… 23
Xulosa ………………………………………………………………………… 25
Foydalanilgan adabiyotlar …………………………………………………… 26
*/
EJ
Kirish
Fenvik daraxti yoki ikkilik indekslangan daraxt (ingl. binary indexed tree) - ko'p vazifalarda segmentlar daraxtini almashtiradigan, lekin ayni paytda uch yoki to’rt baravar tezroq ishlaydigan, mumkin bo'lgan minimal xotira miqdorini (bir xil uzunlikdagi massiv bilan bir xil) egallaydigan ma'lumotlar tuzilishi tezroq yoziladi va katta o'lchamlarga osonroq umumlashtiriladi.
Fenvik daraxti-amalga oshirish oson, tez ishlaydi, lekin nazariy jihatdan mutlaqo aniq bo'lmagan ma'lumotlar tuzilishi, bu sizga prefiksdagi summani topishga va o(logN) uchun alohida elementlarni o'zgartirishga imkon beradi. Xuddi shu murakkablikka qaramay, Fenvik daraxti segmentlar daraxtiga qaraganda ancha tezroq ishlaydi. Ushbu ma'ruzada Fenvik daraxtining aniq ishlash printsipi berilmaydi, faqat amalga oshirish va foydalanish usullari ko'rsatiladi.
Fenvik daraxti-bu ma'lumotlar tuzilishi, massivdagi daraxt, quyidagi xususiyatlarga ega:
1) O (log N) vaqtidagi har qanday [L; R] segmentidagi ba'zi qaytariladigan g operatsiyasining qiymatini hisoblash imkonini beradi;
2)har qanday elementning qiymatini O (log N) ga o'zgartirishga imkon beradi;
3) O (N) xotirani talab qiladi, aniqrog'i N elementlar qatori bilan bir xil;
4) Ko'p o'lchovli massivlar uchun osongina umumlashtiriladi. Fenvik daraxtining eng keng tarqalgan ishlatilishi segmentdagi yig'indini hisoblashdir, ya'ni funktsiya G (X1,..., Xk) = X1 + ... + Xk. Fenvik daraxti birinchi marta "a new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994) maqolasi bilan tasvirlangan.
Sum funktsiyasi a qatorining barcha elementlari bo'ylab harakatlanadigan joyga t qatori bo'ylab harakatlanib, iloji boricha segmentlar bo'ylab "sakrash" ni amalga oshiradi. Birinchidan, u [F(R); R] segmentidagi summaning qiymatini javobga qo'shadi, so'ngra [F(F(R)-1); F(R)-1] segmentidagi summani oladi va
hokazo nolga yetguncha. Upd funktsiyasi teskari yo'nalishda - indekslarni ko'paytirish tomon siljiydi, TJ yig'indisi qiymatlarini faqat kerakli pozitsiyalar uchun yangilaydi, ya'ni f(j) <= i <= j bo'lgan barcha j uchun. shubhasiz, ikkala operatsiyaning tezligi F funktsiyasini tanlashga bog'liq bo'ladi. F(X) qiymatini quyidagicha aniqlaymiz:
F(X) = X & (X+1)
F(j) ni topish < = i < = j formulaga mos keladi:
H(X) = X / (X+1)
Fenvik daraxti segmentlar daraxtiga qaraganda bir marta kamroq xotirani doimiy ravishda egallaydi. Buning sababi shundaki, Fenvik daraxti faqat ba'zi elementlar uchun operatsiya qiymatini saqlaydi va segmentlar daraxti elementlarning o'zini va operatsiyaning qisman natijalarini pastki kesmalarda saqlaydi, shuning uchun u kamida ikki baravar ko'p xotirani oladi. Fenvik daraxtini amalga oshirish osonroq. Fenvik daraxti qurilayotgan segmentdagi operatsiya qaytarilishi kerak, ya'ni segmentdagi minimal (maksimal kabi) bu daraxtni segment daraxtidan farqli o'laroq hisoblash mumkin emas. Ammo agar biz prefiksda minimal miqdorni topishimiz kerak bo'lsa, unda Fenvik daraxti bu vazifani bajaradi. Bunday Fenvik daraxti massiv elementlarini kamaytirish operatsiyasini qo'llab-quvvatlaydi. Daraxtdagi minimalni qayta hisoblash prefiksdagi minimum massivini yangilashdan ko'ra tezroq.
|
| |
