Mustaqil ishisi

Muhammad Al-Xorazmiy nomidagi Toshkent Axborot texnologiyalari Universiteti Farg’ona filiali Komputer inginiring fakulteti Kompyuter inginiring yo’nalishi 716 -21guruh talabasi



Roxataliyev Javohir

Ma’lumotlar tuzilmasi va algoritmlari FANIDAN
MUSTAQIL ISHISI

MAVZU : Qidiruv binar daraxti.. Qidiruv binary daraxtini qurish

REJA:

Kirish

1. Qidiruv algoritmlarning samaradorliklari va ularni mukammallashtirish

2. Algoritmlarni sozlash\

3. binar qidruv

4. Xulosa

KIRISH

Qidiruv algoritmlarining Ma'lumki, o'rganishning maqsadi - harakatni qanday qilishdan iborat:

topilgan yozuvni o'qish Qidirilayotgan yozuv topilmasa, uni jadvalga qo'yish topilgan yozuvni o'chirish. Qidiruv algoritmlarining samaradorlik mezonlari: kalitlarni hisoblashlar soni; dasturning ishlab chiqarishga ketgan vaqt; talab qilish xotira xajmi.
Qidiruv algoritmlari ishlab chiqilayotganida, asosan, ko'proq, jadvaldagi kalitlarni taqqoslashlar soniga e'tibor qaratiladi.
Faraz qilaylik, ketma-ket hisoblash algoritmida hisoblashlar soni -M, indeksli ketma-ket hisobda esa - S bo'lsin. U holda: Massivda ketma-ket hisoblashning hisoblash bo'ladi, O(n):
M =1 n, Mo'rtacha = (n + 1)/2.
Qidiruv algaritimlarining samaradorlik mezonlari

Qidiruv algaritimlarining samaradorlik mezonlari

Qidiruv algoritmlarining samaradorlik mezonlari

Qidiruv algoritmlarining samaradorlik mezonlari Normallashtirilgan diskontlangan jami daromad

MAPni uchun sizga chegara ballini orqali hujjat yaxshi tavsiya tasniflash kerak. Misol uchun, ok, yaxshi va ajoyib yorliqlarga ega bo'lgan hujjat va hisob so'rovlari juftligi (ya'ni 0 dan katta ballar) tegishli deb tasniflanadi. Ammo ok va ajoyib juftliklarning rivojlanishidagi farqlar e'tiborga olinmaydi.
Dis jami daromad (DC) ushbu kamchilikni ikkilik bo'lmagan ballni saqlab, logarifmik kiritilgan omilini qo'shish orqali hal qiladi - DCG yordamning maxraji ro'yxatdagi pastroqqa ega bo'lgan tavsiya etilgan narsalarni jazolaydi. DCG - bu hujjatlarning sifat to'plamidagi o'rnini tekshirish ko'rsatkichi.
Qidiruv algoritmi nima?
Qidiruv algoritmlari muammolarni muammolarni hal qilishda yordam beradigan algoritmlardir. Qidiruv muammosi aniq maydoni, xavfsizlik'ich holati va maqsad holatidan iborat. Qidiruv algoritmlari AI agentlariga statoriylar va alternativalarni amalga oshirish orqali maqsadni kuzatishga yordam beradi.
Algoritmlar dastlabki holatni maqsad holatiga aylantiruvchi ketma-ketligi orqali yechimlarini taqdim etadi. Ush algoritmlarsiz AI mashinalari va o'qish usullarini amalga oshira olmadi va hayotiy echimlarni topa olmadi.

Qidiruv algoritmlarning samaradorliklari va ularni mukammallashtirish

Algoritm nima uchun muhim?
Kichik ko'rgazmali dasturlarni yozganingizda, sizning algoritmingiz samaralimi yoki yo'qmi, unchalik muhim emas; zamonaviy kompyuterda juda tez erishasiz. narsa, real dunyo ilovalarida samaradorlik juda narsa. Katta dastur yoki dastur ko'plab algoritmlarga ega bo'ladi. Samarasizlik tez kuchayadi va dasturlar sekin va javobsiz bo'lib qoladi.
Hisoblashdagi so'nggi tendentsiya - bu juda katta ma'lumotlar to'plamlari bilan ma'lumot "katta ma'lumotlar". Algoritmning ko'pincha ma'lumotlar to'plamining hajmi oshgani sayin tez yomonlashadi. Katta ma'lumotlar bizdan yangi algoritmlarni ishlab chiqarishni qiladi va foydali vaqt uchun foydalanish uchun samaradorlik juda talabchan. samaralilar kechikishlarga juda sezgir. Sevimli hisoblash tizimi o'n baravar sekinlashsa, o'zingizni qanday his qilasiz?
Kompyuterlar tezlashayotgan bo'lsa-da, biz har doim ulardan ko'proq narsani kutamiz. Samarali algoritmlarga bo'lgan yo'qolmadi.
Ba'zi vaqtni talab qiladi. Ertangi kunga qadar hisoblab chiqa olmasangiz, ertangi kun uchun ob-havoni aniq bashorat muhim emas!
Ko'pgina zamonaviy tajriba va baholash tizimlari, logistika kompaniyalari va prognozlar va tibbiy tahlillar bilan shug'ullanadigan kompaniyalar kabi eng tezkor algoritmlarga tayanadi.
Aida mashhur algoritmlari
Sun'iy intellekt - bu axborot agentlarini bilish fanidir. O'z-o'zini tutishlarini boshqarish uchun bu agentlar har doimgidek algoritmlar har doim fonda hisoblashidan tekshiriladi.
Ush agentlar yordamida katta kombinatsion murakkablikdagi harakatni hal qilish mumkin. Muammo bir nechta echimlarga bo'lishi mumkinligi tufayli, bu agentlar barcha mumkin bo'lgan birikmalar uchun qidiradi va yakuniy joy olish uchun eng qisqa yo'lni yoki eng mos yo'lni aniqlash usullaridan foydalanish.
Katta, ishonchli agentlar bilan birgalikda Sun'iy intellektda muhim rol o'ynaydi. Qidiruv turli xil usullar strategiyalari va algoritmlari uchun asosni ta'minlash, jihozni uslubiy himoya orqali AI mashinasi/tizimining to'g'ri qo'llab-quvvatlashni kafolatlaydi.Algoritm nima
Algoritmlarni sozlash: - Algoritmni sozlash tasvirlashning turli usullari mavjud: -
Tabiiy til:- Biz algoritmlarni odamlarga tushunarli bo'lgan har qanday tabiiy tilda yordamimiz mumkin.. Tabiiy til - bu inson tili. masalan. Ingliz, hind, frantsuz, xitoy va boshqalar. tabiiy tillar samarali til emas. Bu noaniq til. U aniq fikr bildirmaydi.
Pseudo code:-Pseudo-kodlar har qanday algoritmlar uchun aniq fikr beradi. Bu tabiatan bir ma'noga ega. For,if,while,do va joy kabi ko'plab boshqaruv iboralari mavjud.Algoritm yukni oshirgan iterativ kodlarni beradi.Biz bundan bundan foydalanamiz. aniq kodlarni uchun til.
Oqim usuli:-Grafik usulda bosqichma-bosqich hal qilish uchun algoritmning yana bir usuli. Biz bu texnikani kelajakda ma'ruzalarimizda o'rganamiz.

Binar haqida

Binar qidruv
Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan tartibga solinadigan funktsiyalarini tuzish sharti qo'yilsin.
Bu holatda eng oson yo'l sifatida chiziqli o'lchashni misol keltirish mumkin. Ammo bu usulning vaqt ni tashkil qilish O(n) qiladi. keyin shu vazifa uchun biz binar qidirib algoritmini ishlatsak bo'ladi.
Binar haqida
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1)
Eng ko'rsatkichi(vaqt): O(log n)
O'rtacha ko'rsatkichi(vaqt): O( log n)
Binar yashash uchun olinadigan g'oyalaridan biri-ket ikkiga bo'lishga asos, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi tashqari massivni oladi, agar kichkina bo'lsa boshi. va o'rtasi tufayli massivni oladi, va har safar shu jarayon qaytalanib boradi toki x element solishtiriladi massivning elementga teng bo'lg'unicha yoki massivning qaytalanib qolmaguncha.

binar qidruv

Biz bitta farqshdan so'ng massivning yarimladini komplekt bo'lmasak ham bo'ladi.
1. x ni o‘rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar hisobni amalga oshiramiz.
hisob Binar hisobning rekursiya orqali amalga oshiramiz.

Algoritm qadamlari

Algoritm qadamlari

Algoritm qadamlari
Algoritm qanday yordamni tushundingiz degan umiddaman. Endi uning qadamlariga o'tadigan bo'lsak.
Eslatma: Ikkilik aniqlash algoritmi to'g'ri ishlatish uchun array saralangan bo'lishi shart!
Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz chegarasini belgilash uchun l (chap) va (o'ng) ko'rsatkichlardan aniqlanadimiz. Ular array indekslarini ko'rsatib turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini

Indeksli ketma-ket xabardor

joy

Indeksli ketma-ket xabardor
joy
Kompyuterda ma'lumotlarni qayta ishlashda foydali amallardan biri hisoblanadi. unga berilgan argument bo'yicha massiv ma'lumotlari ichidan ushbu argumentga mos ma'lumotlarni topish yoki bunday ma'lumotlardan iborat. Ixtiyoriy ma'lumotlar majmuasi jadval yoki fayl deb hisoblanadi.
Ixtiyoriy ma'lumot (yoki tuzilma elementi) boshqa ma'lumotdan biron bir belgisi bilan farq qiladi. Bu belgi deb kalit uchun. Kalit no bo'lishi, ya'ni ushbu kalitga ega ma'lumot jadvalda yagona bo'lishi mumkin. Bunday noyob kalitga yordam'ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali ham uni amalga oshirish mumkin. Ma'lumotlar kalitini bir joyda yig'ish (boshqa jadvalga) yoki yozuv sifatida ifodalab bitta maydonga kalitlarni mumkin. Agar kalitlar ma'lumotlar jadvalidan olinadigan alohida fayl sifatida saqlansa, u holda bunday kalitlar tarkibi kalitlar deyiladi. Aks holda, ya'ni yozuvning bir ichki maydoni jadvalda saqlansa kalitadi. Kalitni berilgan argument bilan mosligini aniqlovchi algoritmga berilgan argument bo'yicha olingan deb hisoblanadi. Qidiruv algoritmi qulay ma'lumotni jadvaldan topish yoki yo'qligini aniqlashdan iboratdir. Agar kerakli ma'lumot yo'q bo'lsa u holda ishni amalga oshirish mumkin:

Indeksli ketma-ket xabardor joy

Faraz qilaylik, o'sish tartibida tartiblangan sonlar massivi berilgan bo'lsin. Ush usulning asos g'oyasi iboratki, qandaydir AM element va u X hisobga argumenti bilan taqqoslanadi. Agar AMX bo'lsa, u holda yakunlanadi; agar AM >X bo'lsa, u holda indekslari M dan katta bo'lgan barcha mahsulotlar kelgusida yuboriladi.
M ixtiyoriy nazoratda ham taklif qilinayotgan algoritm korrekt ishlaydi. Shu tarzda M ni shunday sababki, tadqiq qilinayotgan algoritm samaraliroq natija bersin, ya'ni uni shunday tanlaylikki, iloji bo'ladigan jarayonlarda ishtirok etuvchi dasturiy ta'minot soni kam bo'lsin. Agar biz o'rtacha elementni, ya'ni massiv o'rtasini tanlasak yechim mukammal bo'ladi. Misol uchun butun sonlardan iborat, o'zining bo'yicha tartiblangan ikkilik yordamida massivdan usuli vosita kalit kalitga mos element izlash dasturini ko'rib chiqamiz.

Indeksli ketma-ket xabardor joy

Topilgan elementni ro'yhat boshiga qo'yish orqali qayta tartibga keltirish

Topilgan element biriga ro'yhat boshdan joy oldi. Tuzilmadan safar har birorta element izlab topilsa va u ro'yhat boshiga borib borib qo'yilaversa, natijada izlangan mahsulotlar ro'yhat boshiga joylashib qoladi va biz oxirgi vaqtlarda izlangan narsalarni tez izlab topish imkoniga ega bo'lamiz.
Boshida q ko'rsatkich bo'sh, p esa ro'yhat boshini ko'plab; p elementni ko'rsatganda q birinchini ko'rsatadi. Ro'yhat boshi ko'rsatkichi (jadval) birinchi elementni ko'rinishi. Ro'yda kalit kalitli element topilsa, up ko'rsatkich bilan, oldin element esa q ko'rinish bilan bog'liq. Shu topilganni ro'yhat boshiga elementdi.

Qidiruv samardorligi

Ketma-ket hisoblashni mumkin Ixtiyoriy hisoblash soni – S bilan baxolanishi mumkin. Agar taqqoslashlar (solishtirish) soni qancha kichik bo'lsa, hisoblash algoritmi qanchalik yaxshi bo'ladi. Massivda ketma-ket kiritishning hisoblash bo'ladi: C = 1 n, C = (n + 1)/2. Umuman olganda, ro'yxatda xam samaradorlik yuqoridagi kabi bo'ladi. Garchi massivda xam bog'langan ro'yxatda xam o'ziga xos bir xil bo'lsada, ma'lumotlarni massiv va ro'yxatda ko'rinishda tasvirlashning oziga xos kamchilik va bahosi mavjud. Qidiruvning maqsadi - harakatni boshqarishdan iborat:

Xulosa
chiziqli bir uchidan boshlanadigan va kerakli element topilgunga qadar ro'yxatning har bir elementi bo'ylab o'tadigan ketma-ket quvvat algoritmi belgilangan, aks holda ma'lumotlar to'plamining oxirigacha davom etadi. Bu eng oson hisoblash algoritmidirhiziqli hisoblash - ket ro'xatdan keyin elementni topish usulidir. Moslik topilmaguncha yoki butun ro'yxat qidirilmaguncha u ro'yxatning har bir elementini ketma-ket tekshiradi. [1]

Chiziqli ta'sir eng yomon chiziqli vaqtida amalga oshirish va ko'pi bilan amalga oshirish, bu erdan - ro'yxatga olish. Agar har bir elementning izlanishi teng darajada bo'lsa, chiziqli hisobda o'rtacha holat bo'ladi