Mavzu: “Ikkkilik qidruv daraxti ” MUNDARIJA Mavzu: “Ikkkilik qidruv daraxti ” ............................................................... 1 MUNDARIJA ................................................................................................. 1 KIRISH ............................................................................................................ 2 1.1.Boshlang’ich tushunchalar va ta’riflar .................................................. 4 Misol: ........................................................................................................... 8 1.3.Ma’lumotlar tuzilmasi va ularning klassifikatsiyasi ........................... 10 Misol: Ketma-ket qidiruv va Binar qidiruv algoritmlarini solishtirishga misol.(C++ tilida) .................................................................................................... 20 Xulosa ............................................................................................................ 22 Foydalanilgan adabiyotlar va internet saytlari nomlari ................................ 29

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