Matritsalarni ko‘paytirish algoritmlari

Информация о документе

Цена	10000UZS
Размер	355.0KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	docx
Раздел	Курсовые работы
Предмет	Информатика и ИТ

Matritsalarni ko‘paytirish algoritmlari

Купить

KIRISH
Mavzuning dolzarbligi .Bugungi kunda ma‘lumotlar oqimining ko‘pligi
tufayli ularni qisqa vaqt ichida qayta ishlash muommosi ham ortib bormoqda.
Hozirgi vaqtda axborot- kommunikasiya vositalari barcha turdagi tashkilot va
muassasalarga shiddat bilan kirib kelmoqda. Axborotlarning haddan tashqari
ko‘pligi bu axborotlarni saqlashda, qayta ishlashda, hamda har xil turdagi
tizimlarni yaratish, ulardan keng foydalanishni va axborot tizimlari yaratishni talab
qiladi. O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi PF-4947-son
Farmoni bilan tasdiqlangan 2017-2021 yillarda O‘zbekiston Respublikasini
rivojlantirishning beshta ustuvor yo‘nalishi bo‘yicha harakatlar strategiyasi
mamlakatning davlat va jamiyat rivojlanishi istiqbolini strategik rejalashtirish
tizimiga sifat jihatdan yangi yondashuvlarni boshlab berdi[1]. Unda belgilangan
vazifalar sirasida ta‘lim va fan sohasini rivojlantirish ham aloxida ko‘zda tutilgan.
O‘zbekiston Respublikasi birinchi Prezidentining 2012 yil 21 martdagi
“Zamonaviy axborot-kommunikasiya texnologiyalarini yanada joriy etish va
rivojlantirish chora-tadbirlari to‘g‘risida”gi PQ-1730 Qarori hamda “O‘zbekiston
Respublikasida —Elektron ta‘lim milliy tarmog‘ini yaratish” investision loyihasini
amalga oshirish chora-tadbirlari to‘g‘risida” gi PQ-1740 Qarori va me‘yoriy
hujjatlar asosida algoritmik ta‘minot ishlab chiqish va joriy etish keng ko‘lamli
hisoblanadi. Barcha tashkilot va muassasalarda avtomatlashtirilgan tizimlar
yaratish ulardan keng ko‘lamda foydalanish uchun algoritmlash tillarini o‘rni katta
hisoblanadi.
Axborot tizimlari axborotni to‘plash, saqlash va qayta ishlash uchun, keng
imkoniyatli maqsadlarda samarali foydalanish uchun xizmat qiladi. Zamonaviy
axborotlashtirish tizimi, ma‘lumotlar integratsiyasi konsepsiyasiga asoslangan
katta hajmdagi ma‘lumotlarni saqlash bilan tavsiflanadi va ko‘p sondagi
foydalanuvchilarning turli xildagi talablariga javob berishi kerak bo‘ladi. Axborot
tizimi va axborot texnologiyalarining avtomatlashtirilgan elementlarini qo‘llash va
avtomatlashtirish asosida yangi axborot texnologiyasini yaratish avtomatlashtirish
tizimlarini loyihalashtiruvchilarning asosiy vazifalaridan biri hisoblanadi.
Avtomatlashtirilgan tizimlarni yaratish uchun albatta birinchi navbatda muommo
obektini infologik yoki diskretli modelini qurish dolzarb hisoblanadi. Infologik
yoki diskretli modelni muommo obektiga qarab algoritmlash tillarini qaysi biri
asosida yaratish kerakligini tanlab olinish kerak. Elektron hisoblash mashinalarini
birinchi avlodlari yaratilishi bilan algoritmlash tillarini rivojlanishi ham boshlandi.
2

Yuqoridagi keltirilgan vazifalarni amalga oshirish uchun algoritmlar va
ma‘lumotlar strukturasi fani asosiy fan sifatida xizmat qiladi. Katta hajmdagi
ma‘lumotlarni kompyuterda saqlash muommosini hal etish yo‘llari, algoritmlar va
ma‘lumotlar strukturasi fanining maxsus algoritmlari orqali amalga oshiriladi.
Ikkilik (binar) qidirish algoritmi
Qidirilayotgan elementni saralangan ro‘yxatning o‘rtasidagi element bilan
taqqoslash natijasida quyidagi uchta holatdan biri bo‘lishi mumkin: qidirilayotgan
element topildi, o‘rtadagi elementdan kichik yoki katta. Birinchi (eng yaxshi)
holatda qidiruv tugallanadi. Qolgan ikki holatda ro‘yxatning yarmini tashlab
yuborish mumkin.
Qidirilayotgan qiymat o‘rta elementdan kichik bo‘lsa, u holda bu qiymat
o‘rta qiymatdan oldin, aks holda (katta bo‘lsa), o‘rta qiymatdan keyin
joylashganbo‘ladi. Bu protsedura yana takrorlanishi natijasida ajratib olingan
qismro‘yxatning yana yarmini tashlab yuborish mumkin bo‘ladi.
Kurs ishining maqsadi: Tasodifiy ikkilik qidiruv daraxti mavzusini
o’rganish
Kurs ishining tuzilishi : Kurs ish kirish, 2 bob, 6 bo‘lim, umumiy xulosalar
va tavsiyalar, foydalanilgan adabiyotlar ro‘yhatidan iborat bo‘lib, jami 30 sahifani
tashkil qiladi
3

I Bob. MA’LUMOTLAR TUZILMASI VA ALGORITMLAR
NAZARIYASIGA KIRISH
1.1. Boshlang’ich tushunchalar va ta’riflar
Kompyuter - bu ma‘lumotlarni qayta ishlovchi mashina. EHM (kompyuter)
haqidagi fanlarni o‘rganishda, shunday savollar tug‘iladi: axborotlar kompyuter
ichida qanday ko‘rinishda tashkil etiladi, uni qanday qayta ishlaydi va qanday
ko‘rinishda tasvirlaydi? SHu bilan birgalikda fanni o‘rganishda asosan
ma‘lumotlar bilan ishlash va ma‘lumotlarni tashkil etish kontseptsiyalarini
o‘rganishimiz zarur bo‘ladi.
Demak, kompyuterning asosiy tushunchalaridan biri axborot tushunchasi
bo‘ladigan bo‘lsa, axborot (ma‘lumot) nima? - degan savol tug‘iladi. Bu savolga
bir qiymatli javob topish mushkuldir. CHunki bu tushuncha informatika va
informatsion texnologiyalari sohasidagi fanlarning asosiy tushunchasi hisoblanadi.
Ma‘lumki, fanning asosiy tushunchalari ta‘riflarsiz, izohlarsiz qabul qilinadi.
Masalan, geometriya fanidagi «nuqta», «to‘g‘ri chiziq», «tekislik» kabi
tushunchalar bunga misoldir. Sababi, bu kabi tushunchalarni ularga nisbatan
elementar bo‘lgan tushunchalar orqali izohlash mumkin emas.
Axborotning asosiy birligi sifatida, o‘zaro bir-biriga bog‘liq bo‘lmagan
ikkita qiymatni qabul qilishi mumkin bo‘lgan bit tushunchasi kiritilgan. Bu birlik
qabul qila oladigan qiymatlar ikkilik sanoq sistemasida - nol va bir hisoblanadi.
Aniq bir kompyuterda belgilarni kodlashtirish uchun bitning bir nechtasi
orqali guruhlarga ajratib olinadi. Ajratilgan guruhdagi bitlar to‘plami bayt deb
ataladi. Ko‘pchilik kompyuterlarda bayt o‘lchami 8 bitdan tashkil topadi.
Hisoblash mashinasining xotira qurilmalari bitlar majmuasidan tashkil
topadi, ya‘ni ixtiyoriy vaqt momentida kompyuter xotirasida 0 yoki 1 qiymat
mavjud bo‘ladi. Bit holati uning qiymati yoki mazmunini bildiradi.
Bitlar guruhi EHM xotirasida katta hajmdagi elementlarni ifodalaydi.
Masalan, baytlarda o‘lchanadigan elementlar. Ba‘zi bir kompyuterlarda baytlar
guruhlarga ajratilib mashina so’zi deb nomlanadi. Har bir shunday element o‘z
nomi (identifikatori)ga ega bo‘lgan adreslarni ifodalaydi. Bu adreslar odatda sonli
formatga ega bo‘ladi. U yacheyka deb ataladi, bu yacheykalar o‘zida bitlar
majmuasini saqlab turadi.
4

Demak, yuqoridagilardan kelib chiqadigan bo‘lsak, kompyuterda axborot
tushunchasi haqida aniq fikr yuritish imkonini bermaydi. Lekin, aniq berilgan
bitlar kombinatsiyasi ixtiyoriy fikrni anglatuvchi qiymatni berishi mumkin.
Bitli ma‘lumotlarni interpritatsiya qilish usuli ba‘zan ma’lumotlar turi deb
ataladi. Har bir mashina o‘zining ma‘lumotlar turiga ega.
1.2.Ma’lumotlarning standart turlari va ular ustida bajariladigan amallar
Matematikada o‘zgaruvchilarni sinflarga ajratish, ularning ba‘zi
xususiyatlariga mos ravishda amalga oshiriladi. Ya‘ni, biz bu sinflarni haqiqiy,
kompleks va mantiqiy o‘zgaruvchilar deb nomlaymiz. Bu o‘zgaruvchilar o‘z
xarakteristikasidan kelib chiqqan holda alohida qiymatlarni qabul qiladi.
Ma‘lumotlarni kompyuterda qayta ishlash jarayonida ham xuddi shunday sinflarga
ajratish katta ahamiyatga ega. Shuning uchun ham ixtiyoriy o‘zgarmas (konstanta),
o‘zgaruvchi, ifoda yoki funktsiya o‘zining turiga ega bo‘lishini ta’kidlash lozim.
Ko‘pgina dasturlash tillarida ma’lumotlarning turlari standart va
foydalanuvchi turi kabi farqlanadi. Standart turlarga 5 turdagi ma‘lumotlar mansub
bo‘lib, ular:
a) butun;
b) haqiqiy;
c) mantiqiy;
d) belgili;
e) ko‘rsatkichli.
Foydalanuvchi turi esa 2 ta:
a) sanaladigan (sanoqli);
b) diapozonli.
Har qanday ma‘lumot turi o‘z xarakteristika sohasiga va bu tur ustida
bajarish mumkin bo‘lgan amallar to‘plamiga ega.
Butun tur. Bu tur o‘z tarkibida butun sonlarning mashina razryadliligi
darajasiga mos qism to‘plamini saqlaydi, ya'ni butun turga tegishli o‘zgaruvchilar
o‘lchami mashina razryadiga bog'liq bo‘ladi. Agar mashina n-razryadli bo‘lsa,
shuningdek, qo‘shimcha kodni qo‘llay olsa, u holda butun turchegarasi -2 n-1
< x <
2 n-1
kabi aniqlanadi.
5

Ushbu tur ustida bajariladigan amallar aniq va mos ravishda oddiy
arifmetika qoidalarga asoslanadi. Agar bajarilgan amal natijasi belgilangan
chegaradan chiqib ketsa, u holda hisoblash jarayonida uzilish paydo bo‘ladi. Bu
xabar to‘lib-toshib ketish deb yuritiladi.
Butun sonlar ishorali va ishorasiz turlarga bo‘linadi. Bularning har biri o‘z
diapozoniga ega:
ishorasiz butun sonlar uchun - (0..2 n
-1);
ishorali butun sonlar uchun (-2 n-1
.. 2 n-1
-1).
0 1 15
ishora butun son
Mashina sonlarni qayta ishlaganda sonlar ishorali formatda qo‘llaniladi.
Agar mashina so‘zi yozuv, komanda va ko‘rsatkichlarni qayta ishlasa, u holda
ishorasiz son qo‘llaniladi.
Butun tur ustida qo‘llash mumkin bo‘lgan amallar:
a) qo‘shish.
b) ayirish.
c) ko‘paytirish.
d) butunli bo‘lish.
e) qoldiqli bo‘lish.
f) ekstremumini aniqlash (minimum va maksimum).
g) relyatsion amallar (taqqoslash amallari) (<,>,<=, >=,=,<>).
Misollar:
A div B = C
A mod B = D
C * B + D = A
7 div 3 = 2
7 mod 3 = 1
6

Yuqorida keltirilgan relyatsion amallardan boshqa barchasining natijasi
butun son bo‘ladi.
Haqiqiy tur. Haqiqiy tur haqiqiy sonlar qism to‘plami qatoridan iborat
bo‘lib, mashina formatida qo‘zg‘aluvchi nuqtali shaklda ifodalanadi.
Qo‘zg‘aluvchi nuqtali formatdagi sonlar butun qiymatli mantissa va o‘zgarish
diapozonini aniqlovchi tartib orqali ifodalanadi. Haqiqiy sonni anglatuvchi aniq
belgilar sonidan iborat bo‘ladi. X = ± M * q ' p
sonning yarimlogarifmik shakli. Bu
yerda M - sonning mantissasi, p -sonning tartibi deyiladi. Masalan, 937,56 = 93756
* 10 -2
= 0,93756 * 10 3
1.2-rasm. Haqiqiy sonning mashina xotirasida tasvirlanishi
Mantiqiy tur. Standart mantiqiy tur bir bayt o‘lchamga ega bo‘lib, ixtiyoriy
True va False qiymatlarini qabul qiluvchi elementlardan tashkil topadi.
Mantiqiy turga tegishli ma‘lumotlarning standart turlari ustida mantiqiy
amallarni bajarish mumkin. Bu amallarning asosiylari quyidagilardan iborat:
a) inkor (NOT);
b) kon‘yunktsiya (AND);
a) diz‘yunktsiya (OR).
1. 3-rasm. Asosiy mantiqiy amallarning rostlik jadvali
7 10 1 5
M
antissa
is
horasi T
artib
i
shorasi

Belgili tur. Belgili tur - 26 ta lotin yozuvining bosh va 26 ta kichik
harflarini, 10 ta arab raqamlari va bir necha boshqa grafik belgilarni (masalan,
ajratuvchi belgilar) o‘z ichiga oladi.
Harflar va raqamlar qismto‘plami tartiblanadi:
("A"<= x)&(x <= "Z") - bu yerda x bosh harflarni qabul qiladi.
("0"<= x ) & ( x <= "9") - bu yerda x raqamlarni qabul qiladi.
Bundan tashqari, belgili tur tarkibida chop qilinmaydigan bir necha belgilar
ham mavjud, masalan probel. Bu belgilardan ajratuvchi sifatida foydalaniladi. Bu
turga tegishli ma‘lumotlar ustida quyidagi amallarni bajarish mumkin:
a) o‘zlashtirish (ta‘minlash);
b) taqqoslash;
c) berilgan belgining kodlashdagi tartib nomerini aniqlash;
d) tartib nomeri bo‘yicha belgini aniqlash;
e) bitta keyingi belgini chiqarish;
f) bitta oldingi belgini chiqarish.
Ko‘rsatkichli tur. Ko‘rsatkichli turdagi o‘zgaruvchi tayanch miqdor bo‘lib,
axborot tashuvchi fizik qurilmalarning adresini aniqlaydi. Standart ko‘rsatkichli tur
hech qanday aniq tayanch turga bog'liq bo‘lmagan ko‘rsatkichni aniqlaydi.
Bu tur ixtiyoriy boshqa ko‘rsatkichli turga mos keladi.
Ko‘rsatkichli tur ustida ishorasiz butun sonlar bilan bajariladigan barcha
amallarni bajarish mumkin (masalan, o‘zlashtirish, taqqoslash va h.k).
Bu amallar yordamida ma‘lumotning adresini hisoblash mumkin. Bu turning
mashinadagi ko‘rinishi mumkin bo‘lgan maksimal uzunlikni egallaydi.
Misol:
ABCD:1234 - o‘n oltilik sanoq sistemasida berilgan ko‘rsatkich qiymati -
nisbiy adres.
Bu yerda birinchi son (ABCD) - segment adresi;
Ikkinchi son (1234) - segmentning ichki adresi.
8

Nisbiy adresdan absolyut adresni hisoblash - absolyut adresni olish uchun
segment adresini chapga siljitish amali bajariladi va olingan natijaga segment ichki
adresi qo‘shiladi.
Masalan:
1) ABCD ni bir razryad chapga siljitamiz. ABCD0 qiymat hosil bo‘ladi;
2) Hosil bo‘lgan qiymtga 1234 ni qo‘shamiz. Olingan natija absolyut adresni
ifodalaydi.
ABCD 0
+
12 34
A C F 0 4
Hosil bo‘lgan natija A C F 0 4 berilgan sonning absolyut adresi.
Sanoqli tur. Sanoqli turga tegishli o‘zgaruvchilar turning e'lon qilinishida
aniq sondagi qiymatlar to‘plamini tashkil etadi. Bu to‘plamdagi qiymatlar
joylashish ketma-ketligidagi mos tartib raqami orqali aniqlanadi.
Sanoqli turni e’lon qilish formati quyidagicha:
TYPE <nom> = (<ro‘yxat>);
<ro‘yxat>: := <identifikator>,[<ro‘yxat>].
Agar identifikatorning sanoqli tur ro‘yxatidagi qiymati ko‘rsatilgan bo‘lsa, u
o‘zgarmas sifatida qabul qilinadi. E‘lon qilingan sanoqli tur qiymatlari tartib
raqami ro‘yxatda egallagan pozitsiyasiga qarab aniqlanadi. Jumladan, birinchi
o‘zgarmasning tartib raqami 0 ga teng. Masalan, ranglar nomi to‘plamidan iborat
tur aniqlash (e‘lon qilish) quyidagicha bo‘ladi:
TYPE rang = (qizil, yashil, ko'k);
Sanoqli turga tegishli ma‘lumotlar ustida aynan belgili turda bajarish
mumkin bo‘lgan amallarni bajarish mumkin.
9

1.3.Ma’lumotlar tuzilmasi va ularning klassifikatsiyasi
Ma’lumotlar tuzilmasi bu ma‘lumotlarni tashkil etuvchi elementlar va ular
o‘rtasidagi munosabatlar majmuasidir. Ma‘lumot elementlari oddiy bir qiymat yoki
ma‘lumotlarning tuzilmasi sifatida e‘tiborga olinadi. Munosabatlar sifatida
elementlar o‘rtasidagi funktsional bog‘lanish va bu ma‘lumotning qaerda
joylashganligini bildiruvchi ko‘rsatkichlar tushiniladi.
Ma‘lumotlar tuzilmasi elementini sxematik shaklda quyidagicha tasvirlash
mumkin:
1.4-rasm. Ma ’lumotlar tuzilmasining sxematik ko‘rinishi
Munosabatlar elementi - bu ma‘lumot elementining ushbu tuzilmadagi
boshqa elementlar bilan bog‘lanish majmuasi hisoblanadi.
Ma‘lumotlar tuzilmasini quyidagicha analitik ifodalash mumkin:
S :=( D,R ),
bu yerda S - ma‘lumotlar tuzilmasi, D -ma‘lumotlar elementlari va R -
munosabatlar.
Ma‘lumotlar tuzilmasi qanchalik murakkab bo‘lmasin, ular oddiy
ma‘lumotlardan tashkil topadi.
Kompyuterning ichki dunyosi biz o‘ylagandek sodda emas. Masalan, uning
xotira qurilmasi kiruvchi ma‘lumotlarni qayta ishlovchi millionlab triggerlardan
tashkil topgan. Kompyuterga ma‘lumotlarni kiritishda ularga ma‘lum bir ko‘rinish,
ya‘ni qandaydir ma‘noni anglatuvchi tartib beramiz. Mashina kiritilgan
10

ma‘lumotlar uchun xotiradan zarur maydonlar ajratib, ularga adres tayinlaydi.
Inson ma‘lumotlarni mantiqiy darajada mavhum holda, kompyuter esa fizik
darajada qayta ishlaydi.
Mantiqiy tuzilmadan fizik tuzilmaga o‘tish ketma-ketligini 1.5-rasmdagidek
tasvirlash mumkin.
Ma'lumotlar tuzilmalari quyidagi xususiyatlari bilan sinflarga ajratilishi
mumkin:
Tuzilmada ma‘lumotlarning o‘zaro bog‘lanish darajasi asosida:
- agar tuzilmada ma‘lumotlar kuchsiz bog‘lanishga ega bo‘lsa, u holda bu
tuzilma bog‘lanmagan tuzilma deyiladi (masalan, vektor, massiv, satr, stek);
agar tuzilmada elementlar o‘rtasida bog‘lanishlar mavjud bo‘lsa, bunday
tuzilma bog‘langan tuzilma deyiladi (masalan, bog‘langan ro‘yxatlar).
Dastur bajarilishi jarayonida yoki vaqtga bog‘liq holda tuzilmaning
o‘zgaruvchanligi asosida:
statik tuzilmalar - bu dastur bajarilishi davomida o‘zgarmay qoladigan
tuzilmalar bo‘lib, unga misol sifatida yozuvlar, massivlar, satrlar, vektorlarni olish
mumkin;
yarimstatik tuzilmalar - bunday tuzilmalarda elementlarga murojaat faqat bir
tomonlama (kirish yoki chiqish, o‘qish yoki yozish) amalga oshirilishi mumkin,
masalan, steklar, deklar, navbat kabi tuzilmalar;
dinamik tuzilmalar - bu dastur bajarilishi jarayonida to‘liq o‘zgaruvchan
tuzilmalar bo‘lishi mumkin.
Tuzilmaning tartiblanganligi bo‘yicha:
chiziqli (vektor, massiv, stek, dek, yozuv);
chiziqli bo‘lmagan (ko‘pbog‘lamli ro‘yxatlar, daraxtsimon tuzilmalar,
graflar).
11

1 .5-rasm.Ma ’lumotlarning tasvirlanish darajasi
12

II-bob . Qidiruv tizimlari va ikkilik daraxt bo’yicha qidirish
2.1. Qidirish algoritmlari va ularni baholash
Kerakli ma’lumotni ro yxatdan qidirish nazariy dasturlashtirishning asosiyʻ
masalalaridan biri hisoblanadi. Qidirish algoritmlarni muhokama qilishda
ma’lumotlar qandaydir ro yxatni hosil qiluvchi yozuvlardan tuzilgan deb faraz
ʻ
qilamiz, qaysiki dasturdagi ma’lumotlar massivini namoyon qiladi. Yozuvlar yoki
ro yxat elementlari massivda ketma-ket joylashadi va ular orasida bo sh joy yo q.
ʻ ʻ ʻ
Yozuvlarning barchasi ro yxatda 1 dan N gacha raqamlangan. Qoidaga ko ra
ʻ ʻ
yozuvlar maydonlardan tuzilgan bo lishi mumkin, lekin bizni bu maydonlardan
ʻ
kalit deb ataluvchi qiymat qiziqtiradi. Ro yxatlar kalit maydon qiymatiga ko ra
ʻ ʻ
saralangan yoki saralanmagan bo lishi mumkin. Saralanmagan ro yxatda yozuvlar
ʻ ʻ
tartibi tasodifiy, saralanganida esa kalitning o sish tartibida joylashgan bo ladi.
ʻ ʻ
Saralanmagan ro yxatda kerakli yozuvni qidirish butun ro yxatni yozuv
ʻ ʻ
topilgunga qadar ko rib chiqishga olib keladi. Bu qidirish algoritmlarining oddiy
ʻ
ko rinishi. Ko rishimiz mumkin bu algoritm uncha samarador emas, lekin u
ʻ ʻ
ixtiyoriy ro yxatda ishlaydi.
ʻ
Saralangan ro yxatda ikkilik qidirishdan foydalanish mumkin. Ikkilik
ʻ
qidirish tartiblanganlikka ko ra bir solishtirishda birdan ortiq elementlarni tashlab
ʻ
yuborishga asoslangan. Natijada qidirish samarador bo ladi.
ʻ
Odatda qidirish nafaqat kerakli elementni ro yxatda bor yo qligini aniqlash
ʻ ʻ
uchun, balki topilgan kalit qiymatiga bog liq ma’lumotlarni olish uchun xizmat
ʻ
qiladi. Masalan, kalit qiymat xodimning raqami yoki tartib raqami yoxud boshqa
istalgan yagona identifikator bo lishi mumkin. Kerakli kalit topilgandan so ng,
ʻ ʻ
dastur unga bog langan ma’lumotlarni o zgartirishi mumkin yoki butun yozuvni
ʻ ʻ
chiqarishi mumkin. Oxir oqibatda qidirish algoritmi oldida muhim vazifa kalitning
o rnini topish masalasi turadi. Shuning uchun qidirish algoritmlari kerakli kalitni
ʻ
saqlovchi yozuv indeksini beradi. Agar kalit qiymat topilmasa, u holda qidirish
algoritmi massiv yuqori chegarasidan chiquvchi indeks qiymatini beradi.
Maqsadimiz uchun faraz qilamizki, ro yxat elementlari 1 dan N gacha
ʻ
raqamlangan. Bu agar maqsad elementi topilmasa 0 ni berishga imkon beradi.
Oddiylik uchun kalit qiymat takrorlanmaydi deb faraz qilamiz.
2.2. Ketma-ket qidirish algoritmi
Qidirish algoritmlarida qandaydir maqsad elementini ro yxatdan qidirish
ʻ
jarayoni qiziqtiradi. Ketma-ket qidirishda biz doim ro yxat saralanmagan deb faraz
ʻ
13

qilamiz, ammo ayrim qidirish algoritmlari saralangan ro yxatlarda yaxshiʻ
unumdorlik ko rsatadi.
ʻ
Ketma-ket qidirish algoritmi ro yxat elementlarni birinchisidan boshlab to
ʻ
maqsad elementi topilgunga qadar birma bir ko rib chiqadi. Ravshanki, aniq kalit
ʻ
qiymati qanchalik uzoqda joylashgan bo lsa, shunchalik uni qidirishga ko p vaqt
ʻ ʻ
sarflanadi. Buni ketma-ket qidirish algoritmi tahlilida hisobga olish kerak.
Ketma-ket qidirish algoritmining umumiy ko rinishi quyidagicha:
ʻ
SequentialSearch(list,target,N)
l i s t
ko’riladigan ro’yxat
target maqsad qiymati
N
ro’yxat elementlari soni
for i=1 to N do
if (target=list[i])
return i
end if
end for
return 0
Eng yomon holat tahlili
Ketma-ket qidirish algoritmida ikkita eng yomon hol uchraydi. Birinchi
holda maqsad elementi ro yxatning eng oxirida joylashgan bo ladi. Ikkinchisida u
ʻ ʻ
ro yxatda umuman bo lmaydi. Bu ikki holda ham N solishtirishlar bajariladi (N –
ʻ ʻ
ro yxat elementlari soni). Tushunarliki, istalgan qidirish algoritmi uchun N
ʻ
qiyinlikning yuqori chegarasini beradi. Agar solishtirishlar N dan katta bo lsa,u
ʻ
holda solishtirish qaysidir elementda ikki marta bajarilgan, demak, ortiqcha
harakatlar qilingan va algoritmni yaxshilash kerak.
Qiyinlik yuqori chegarasi va qiyinlikning eng yomon holi tushunchalari
orasida farq bor. Yuqori chegara masaladan bog liq bo lsa, eng yomon hol esa uni
ʻ ʻ
14

yechuvchi ma’lum algoritmdan bog liqdir. Eng yomon holi ko rsatilgan yuqoriʻ ʻ
chegara N dan kichik bo lgan qidirish algoritmi bilan tanishamiz.
ʻ
O rtacha hol tahlili
ʻ
Qidirish algoritmlari uchun ikki o rtacha hol mavjud. Birinchisida qidirish
ʻ
muvaffaqiyatli yakunlanadi, ikkinchisi maqsad qiymati ro yxatda umuman
ʻ
bo lmagan hol.
ʻ
Agar maqsad qiymati ro yxatda mavjud bo lsa, u holda u mumkin bo lgan N
ʻ ʻ ʻ
imkoniyatlarning birini egallaydi: u birinchi, ikkinchi, uchinchi va h.k. bo lishi
ʻ
mumkin. Biz bu barcha holatlarni teng ehtimolli deb faraz qilamiz va ularning har
biri 1/N ga teng. Natijada o rtacha holdagi qiyinlik uchun quyidagi tenglikka ega
ʻ
bo lamiz
ʻ
A(N )= 1
N ∑i=1
N
i= 1
N⋅N (N +1)
2 = N +1
2
Agar maqsad qiymati ro yxatda uchramasa, u holda imkoniyatlar soni N + 1
ʻ
gacha o sadi. Ma’lumki, bu holda qidirish N solishtirish talab qiladi. Agar barcha
ʻ
N +1 imkoniyatlar teng ehtimolli deb faraz qilsak, u holda quyidagiga ega
bo lamiz:
ʻ
A(N )= 1
N +1(∑i=1
N
i+N )= 1
N +1∑i=1
N
i+ 1
N +1⋅N = 1
N +1⋅N (N +1)
2 + N
N +1= N
2 + N
N +1≈ N +2
2 .
( N juda katta bo lsa 1/(
ʻ N + 1) qiymat 0 ga yaqinlashadi.)
Ko rinib turibdiki, elementning yo qligi o rtacha holni qiyinligini 1/2 ga
ʻ ʻ ʻ
oshiradi.
2.3.Ikkilik daraxt bo yicha qidirish
ʻ
Maqsad qiymatni saralangan ro yxatning o rtadagi qiymati bilan solishtirish
ʻ ʻ
uch xil natija berishi mumkin: qiymatlar teng, maqsad qiymati ro yxat elementidan
ʻ
kichik va maqsad qiymati ro yxat elementidan katta. Birinchi va eng yaxshi holda
ʻ
qidirish tugaydi. Qolgan ikki holda ro yxat yarmini tashlab yuborishimiz mumkin.
ʻ
Agar maqsad qiymati o rta elementdan kichik bo lsa, u holda u bu o rta
ʻ ʻ ʻ
element oldida joylashgan bo ladi. Agar u o rta elementdan katta bo lsa, u holda u
ʻ ʻ ʻ
o rta elementdan keyin joylashgan bo ladi. Bu ro yxat yarmini tashlab yuborishga
ʻ ʻ ʻ
15

yetarlicha sabab bo ladi. Bu jarayonni takrorlab biz ro yxatning qolgan qismlariniʻ ʻ
yarmini tashlab yuborishimiz mumkin. Natijada quyidagi algoritmga kelamiz:
BinarySearch(list,target,N)
list
ko’rilayotgan ro’yxat
target maqsad qiymati
N
ro’yxat eleamentlari soni
s t a r t = 1
end=N
whil e start <=end do
middle=(start+end)/2
select(Compare(list[middle] ,target)) from
case -1: start=middle+ 1
case 0: return middle
case 1: end=middle- 1
en d s el ec t
end while
return 0
Bunda Compare(х,у) funksiyasi -1, 0 yoki 1 qiymatlarni mos holda x<y,
x=y yoki x>y shartlarda beradi. Algoritmlar tahlilida Compare funksiyani
chaqirish bir solishtirish deb hisoblanadi.
Ushbu algoritmda agar maqsad qiymat topilgan o rta elementdan katta
ʻ
bo lsa
ʻ start o zgaruvchi ʻ middle qiymatidan 1 ga oshiqqa ta’minlanadi. Agar
maqsad qiymat topilgan o rta elementdan katta bo lsa
ʻ ʻ end o zgaruvchi ʻ middle
qiymatidan 1 ga kamga ta’minlanadi. Silijish 1 esa o rta element izlanayotgan
ʻ
qiymatga teng bo lmagan hol bilan tushuntiriladi.
ʻ
Sikl har doim to xtaydimi? Agar maqsad qiymat topilsa buni
ʻ return operatori
ta’minlaydi. Agar kerakli qiymat topilmasa, u holda har bir sikl iteratsiyasida yo
start ning qiymati oshadi yo start o zgaruvchining qiymati kamayadi. Bu ularning
ʻ
qiymati bir biriga yaqinlashishini ko rsatadi. Qandaydir vaziyatda ular tenglashadi
ʻ
va sikl start=end=middle da yana bir bor bajariladi. Bu o tishdan keyin (agar
ʻ
16

qidirilayotgan element ushbu indeksga mos kelmasa) yo start qiymati middle va
end lardan 1 ga katta bo ladi, yo teskarisi, end o zgaruvchi middle va start larʻ ʻ
qiymatidan 1 ga kam bo ladi. Ikki holatda ham sikl
ʻ while yolg on bo ladi va sikl ʻ ʻ
boshqa bajarilmaydi. Shu tufayli sikl har doim to xtaydi.
ʻ
Algoritm har doim ro yxatni yarimga bo ladi va biz tahlilda qandaydir k
ʻ ʻ
uchun N=2 k
-1 deb faraz qilaylik. Agar shunday bo lsa, ikkinchi o tishda nechta
ʻ ʻ
element qoladi? Uchinchidachi? Umuman olganda, tushunarliki, agar sikl
qandaydir o tishda 2
ʻ j
-1 element ro yxat bilan ishlasa, u holda ro yxatning birinchi ʻ ʻ
yarmida 2 j-1
-1 element bo ladi, bitta element o rtada va 2
ʻ ʻ j-1
-1 elementlar
ro yxatning ikkinchi yarmida bo ladi. Shuning uchun keyingi o tishga 2
ʻ ʻ ʻ j -1
-1
element qoladi (1<j<k).
Eng yomon holat tahlili
Yuqorida ko rdikki, ro yxatning qolgan qismlarida barcha o tishda ikkining
ʻ ʻ ʻ
darajalari birga kamayadi. Yana siklning oxirgi iteratsiyasi qolgan qism o lchami 1
ʻ
ga teng bo lganda bajariladi. Bu esa j=1(ya’ni 2
ʻ 1
-1=1) da bajariladi. Bu shuni
ko’rsatadiki, N=2 k
-1 da o’tishlar soni k dan oshmaydi. Oxirgi tenglikdan eng
yomon holda o’tishlar soni k=log
2 (N+1) ga tengligini topamiz.
Tahlilda qidirish jarayoni uchun yechim daraxti ham yordam berishi
mumkin. Yechim daraxti tugunlarida mos o tishda tekshiriladigan elementlar
ʻ
turadi. Yetti elementdan iborat ro yxat uchun yechim daraxti 2-rasmda keltirilgan.
ʻ
Umumiy holda daraxt nibatan balanslashtirilgan, ya’ni biz har doim ro yxat turli
ʻ
qismlarining o rtasini tanlaymiz. Shuning tufayli solishtirishlar sonini sanash
ʻ
uchun binar daraxtlar uchun keltirilgan formulalardan foydalanamiz.
Madomiki biz N=2 k
-1 deb faraz qilarkanmiz mos keluvchi yechim daraxti
doim to’liq bo’ladi. Unda k daraja, ya’ni k=log
2 (N+1) bo’ladi. Biz har qaysi
darajada bittadan solishtirish bajaryapmiz, shuning uchun solishtirishlar umumiy
soni log
2 (N+1) dan oshmaydi.
2-rasm. Yetti elementli ro’yxatda qidirish uchun yechim daraxti
O rtacha hol tahlili
ʻ
17

Xuddi ketma-ket qidirish algoritmidagi kabi tahlilda ikki holatni qaraymiz.
Birinchisi maqsad qiymat ro yxatda aniq mavjud hol va ikkinchisi u umuman yo qʻ ʻ
holat.
Birinchi holda maqsad qiymat uchun mumkin bo lgan holatlar N ta va ular
ʻ
teng ehtimolli hamda ularning har biri 1/N ga teng. Agar qidirish jarayonini
tavsiflovsi binar daraxtni qaraydigan bo lsak, u holda 1 darajada daraxt ildiz
ʻ
elementidan qidirish uchun bitta solishtirish, ikkinchi darajadagi tugunlar
elementlaridan qidirish uchun ikkita solishtirish va uchinchi darajada uchta
solishtirish talab qilinadi. Umuman i darajadagi elementlardan qidirish uchun i
solishtirish talab qilinadi. i darajada 2 i
-1 ta tugun mavjud va N=2 k
-1 da daraxtda k
daraja mavjud. Bu shuki, barcha mumkin bo lgan hollar uchun to liq solishtirishlar
ʻ ʻ
sonini har qaysi darajadagi solishritirishlarni tugunlar soniga ko paymalarini
ʻ
yig indisi hisoblab topish mumkin. Natijada o rtacha hol tahlili quyidagini beradi:
ʻ ʻ

A(N )= 1
N ∑i=1
k
i2i−1= 1
N
1
2∑i=1
k
i2i (
N=2k−1
uchun )
Endi maqsad qiymat ro yxatda mavjud bo lmagan holni qaraymiz.
ʻ ʻ
Elementnin mumkin bo lgan holatlari soni N ga teng, ammo bu holda yana N + 1
ʻ
maqsad qiymat ro yxatda yo qligi uchun imkoniyatlar bor. Imkoniyatlar soni N + 1
ʻ ʻ
ga teng, ya’ni maqsad qiymat ro yxatdagi birinchi elementdan kichik, birinchidan
ʻ
katta ikkinchidan kichik, ikkinchidan katta uchinchidan kichik va h.k. maqsad
qiymat N elementdan katta bo lishi mumkin. Har qaysi bu elementlar yo qligi
ʻ ʻ
hollar к solishtirishda bajariladi. Hammasi bo lib hisoblashda 2N + 1 imkoniyatlar
ʻ
ishtirok etadi. Nihoyat, hosil qilamiz:
A(N )= 1
2N+1(∑i=1
k
i2i−1+(N+1)k)
N=2k−1
uchun.
Yuqoridagi kabi almashtirishlar quyidagini beradi :
A(N )= ((k−1)2k+1)+(N +1)k
2N +1 = ((k−1)2k+1)+(2k−1+1)k
2(2k−1)+1
= (k2k−2k+1)+2kk
2k+1−1
= k2k+1−2k+1
2k+1−1
≈ k2k+1−2k+1
2k+1
¿k− 1
2= log 2(N +1)− 1
2
N=2k−1
учун.
18

Oxirgi tenglik element ro yxatda mavjud bo lgan holda natijani farqsizʻ ʻ
oshiradi. Masalan 2020-1=1 048 575 elementdan iborat ro yxat uchun birinchi
ʻ
holda 19 ga yaqin natijaga, ikkinchi holda 19.5 ga yaqin natijaga ega bo lamiz.
ʻ
2.4.
Qidirish algoritmlarining qiyosiy harakteristikalari
Saralanmagan fayllar va massivlar uchun bir tur qidirish usullari ishlatilsa,
saralangan fayl va massivlar uchun boshqa turdagi qidirish algoritmlari ishlatiladi.
Quyida ularning ayrimlari bilan tanishamiz:
№ Algorit
m nomi Qi
yinlik
bahosi Afzalli
gi Kam
chiligi
1
. Ketma
-ket qidirish O(
(n-
m+1)m) Sarala
nmagan
massivlarda
ishlatiladi,
oddiy, kichik
ro yxatlarda
ʻ
juda tez Katt
a
ro yxatlard
ʻ
a sekin
ishlaydi
2
. Ikkilik
qidirish O(l
og n) Katta
ro yxat-larda
ʻ
tez ish-laydi,
satrli
ma’lumotlar
bilan yengil
ishlaydi
3
. Interpo
lotsion
qidirish O(l
og n) Katta
ro yxatlarda
ʻ
tez ishlaydi Mur
akkab
satrli
ma’lumotl
19

ar bilan
qiyin
ishlaydi
Misol: Ketma-ket qidiruv va Binar qidiruv algoritmlarini solishtirishga
misol.(C++ tilida)
Dastur kodi:
#include <iostream>
using namespace std;
int a[101];
int main(){
int n , l=0 , r=100 , m , count1=0, count2=0;
for(int i=1; i<101; i++){
a[i-1]=i;
}
cout<<"Qidirilayotgan sonni kiriting: ";
cin>>n;
for(int i=0; i<101; i++){
if(a[i]==n) break;
count1++;
}
while(l!=r){
m=(l+r)/2;
if(m==n) break;
else if(m<n) l=m+1;
20

$else r=m-1; count2++; } cout<<"Ketma-ket qidiruv algoritmi yordamida n soni "<<count1<<" ta qadamda topildi!!!\n"; cout<<"Binar qidiruv algoritmi yordamida n soni "<<count2<<" ta qadamda topildi!!!"; return 0; } Dastur natijasi: 21$

Xulosa
Bu kurs ishida men ketma-ket qidiuv va ikkilik qidiruv usullarini
kurib chiqdim. Bundan shunday xulosaga keldimki binar qidiruv algoritmi ketma-
ket qidiruv algoritmidan ancha tez ishlar ekan. Bu degani binar qidiruv algoritmi
juda yaxshi degani emas, har ikkalasiniyam vaziyatga qarab ishlatsa bo’ladi. Binar
qidiruv algoritmi juda katta ro’yxatlarda tez ishlaydi, shuning uchun bu vaziyatda
binar qidiruv algoritmidan foydalanish maqsadga muvofiq.Kurs ishini yozish
orqali o’z bilimlarimni yanada mustahkamladim. Binar daraxti ikkilik ifodalarni
ifodalash uchun ishlatiladigan dastur tili hisoblanadi. Binar daraxti ifodalashi
mumkin bo lgan ikkita keng tarqalgan ikkilik ifoda turiʻ algebraik [1] va mantiqiy
ifoda turlari hisoblanadi. Binar daraxti birlik va ikkilik operatorlarni o z ichiga
ʻ
olgan ifodalarni ifodalashi mumkin.
Binar ifoda daraxtining har bir tugunida nol, bitta yoki ikkita son mavjud.
Ushbu cheklangan struktura ifoda daraxtlarini qayta ishlashni soddalashtiradi.
22

(a+b)*c+7 ifodaning ifodalar daraxti
Umumiy ko rinishiʻ
Ikkilik ifoda daraxtining barglari operandlar, masalan, doimiylar yoki
o zgaruvchilar nomlari va boshqa tugunlarda operatorlar mavjud. Bu alohida
ʻ
daraxtlar ikkilik bo ladi, chunki barcha operatsiyalar ikkilikdir va bu eng oddiy
ʻ
holat bo lsa-da, tugunlarda ikkitadan ortiq son bo lishi mumkin. Bundan tashqari,
ʻ ʻ
birlik minus operatorida bo lgani kabi, tugunning har biri faqat bitta songa ega
ʻ
bo lishi mumkin. Ifodalar daraxti
ʻ T ni chap va o ng pastki daraxtlarni rekursiv ʻ
baholash natijasida olingan qiymatlarga ildizdagi operatorni qo llash orqali
ʻ
baholash mumkin.
O tish
ʻ
Algebraik ifoda ikkilik ifoda daraxtidan qavs ichiga olingan chap ifodani
rekursiv ishlab chiqarish, so ngra operatorni ildizga chiqarish va nihoyat, qavs
ʻ
ichiga olingan o ng ifodani rekursiv ishlab chiqarish orqali ishlab chiqarilishi
ʻ
mumkin. Ushbu umumiy strategiya (chap, tugun, o ng) <b>tartibli o'tish</b>
ʻ
sifatida tanilgan. Muqobil o tish strategiyasi chap pastki daraxtni, o ng pastki
ʻ ʻ
daraxtni va keyin operatorni rekursiv ravishda chop etishdir. Ushbu o tish
ʻ
strategiyasi odatda <b>buyruqdan keyingi o'tish</b> sifatida tanilgan. Uchinchi
strategiya — avval operatorni chop etish, so ngra oldindan tartibli o tkazish deb
ʻ ʻ
nomlanuvchi chap va o ng pastki daraxtni rekursiv ravishda chop etish.
ʻ
Ushbu uchta standartdan birinchi o tish uch xil ifoda formatlarining
ʻ
ifodasidir: infiks, postfiks va prefiks. Infiks ifodasi tartibni kesib o tish orqali,
ʻ
postfiks ifodasi buyruqdan keyingi o tish orqali va prefiks ifodasi oldindan tartibli
ʻ
o tish orqali hosil bo ladi.
ʻ ʻ
23

Infiks o tishʻ
Infiks ifodasi chop etilganda, har bir ifodaning boshiga va oxiriga ochilish
va yopish qavslari qo shilishi kerak. Har bir pastki daraxt pastki ifodani
ʻ
ifodalaganligi sababli, uning boshida ochilish qavslari va barcha sonlarni qayta
ishlagandan so ng, yopish qavslari chop etiladi.
ʻ
Psevdokod:
Algoritm infix ( daraxt )
Algorithm infix (tree)
/*Print the infix expression for an expression tree.
Pre : tree is a pointer to an expression tree
Post: the infix expression has been printed*/
if (tree not empty)
if (tree token is operator)
print (open parenthesis)
end if
infix (tree left subtree)
print (tree token)
infix (tree right subtree)
if (tree token is operator)
print (close parenthesis)
end if
end if
end infix
Postfiksdan o tish
ʻ
Postfiks ifodasi har qanday binar daraxtning asosiy buyruqdab keyingi o tish
ʻ
orqali hosil bo ladi. Qavslar kerak emas.
ʻ
24

Algoritm postfiks ( daraxt )
Algorithm postfix (tree)
/*Print the postfix expression for an expression tree.
Pre : tree is a pointer to an expression tree
Post: the postfix expression has been printed*/
if (tree not empty)
postfix (tree left subtree)
postfix (tree right subtree)
print (tree token)
end if
end postfix
Prefiks o tishʻ
Psevdokod:
Algoritm prefiks ( daraxt )
Algorithm prefix (tree)
/*Print the prefix expression for an expression tree.
Pre : tree is a pointer to an expression tree
Post: the prefix expression has been printed*/
if (tree not empty)
print (tree token)
prefix (tree left subtree)
prefix (tree right subtree)
end if
end prefix
Ifodalar daraxtini qurish
25

Daraxtning qurilishi postfiks ifodasini bir vaqtning o zida bitta belginiʻ
o qish orqali amalga oshiriladi. Agar belgi operand bo lsa, bitta tugunli daraxt
ʻ ʻ
yaratiladi va uning ko rsatkichi stekga suriladi. Agar belgi operator bo lsa,
ʻ ʻ
ikkita T1 va T2 daraxtiga ko rsatgichlar stekdan chiqariladi va ildizi operator
ʻ
bo lgan va chap va o ng sonlari mos ravishda
ʻ ʻ T2 va T1 ni ko rsatadigan yangi ʻ
daraxt hosil bo ladi. Keyin ushbu yangi daraxtga ko rsatgich stekka suriladi
ʻ ʻ [2] .
Misol
Postfiks yozuvidagi kirish: ab + cde + * * Birinchi ikkita belgi operandlar
bo lganligi sababli, bitta tugunli daraxtlar yaratiladi va ularga ko rsatgichlar stekga
ʻ ʻ
suriladi. Qulaylik uchun stek chapdan o ngga o sadi.
ʻ ʻ
Stek chapdan o ngga o sadi
ʻ ʻ
Keyingi belgi „+“ belgisidir. U ikkita ko rsatgichni daraxtlarga ko chiradi,
ʻ ʻ
yangi daraxt hosil bo ladi va unga ko rsatgich stekga suriladi.
ʻ ʻ
Yangi daraxtning shakllanishi
Keyin c, d va e o qiladi. Har biri uchun bitta tugunli daraxt yaratiladi va mos
ʻ
keladigan daraxtga ko rsatgich stekga suriladi.
ʻ
26

Bir tugunli daraxt yaratish
Davom etishda „+“ belgisi o qiladi va u oxirgi ikkita daraxtni birlashtiradi.ʻ
Ikki daraxtni birlashtirish
Endi „*“ o qiladi. Oxirgi ikkita daraxt ko rsatkichi ochiladi va ildiz sifatida
ʻ ʻ
„*“ belgisi bilan yangi daraxt hosil bo ladi.
ʻ
27

Ildiz bilan yangi daraxtni shakllantirish
Nihoyat, oxirgi belgi o qiladi. Ikki daraxt birlashtiriladi va oxirgi daraxtdaʻ
ko rsatgich stekda qoladi.
ʻ
28

Foydalanilgan adabiyotlar va internet saytlari nomlari
1. Boltayev B.J , Azamatov A.R , Rahimov A.D “Algoritmlash va dasturlash
asoslari” kitobi
2. A.M. Po’latov “Algoritmlash va C++ dasturlash asoslari” kitobi
3. A.R. Azamatov “Algoritmlash asoslari” kitobi
4. hozir.org
5. uzvikipediya.org
6. arxiv.uz
29

Matritsalarni ko‘paytirish algoritmlari

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish

Информация о документе

Продавец

Matritsalarni ko‘paytirish algoritmlari

Похожие документы