“Eng katta qismiy ketma-ketlikni qidirish” MUNDARIJA KIRISH. .......................................................................................................... 2 I Qismiy ketma-ketlikni qidirish ..................................................................... 3 1.1 Ketma-ket qidiruv algoritmi .................................................................. 3 1.2 Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi ......................... 5 1.3 Dastur kodi: ........................................................................................... 6 1.4 Indeksli ketma-ket qidiruv algoritmi. .................................................... 9 II. Qismiy ketma-ketlikni qidirish uchun Knut Morris Pratt algoritmi ......... 12 2.1 Knut Morris Pratt algoritmi haqida ..................................................... 12 2.2 Patterndan DFA yasash: ...................................................................... 14 2.3 Knuth-Morris-Pratt algoritmini kodda ifodalash ................................. 15 III. Deykstra algoritmi .................................................................................. 20 XULOSA ....................................................................................................... 22 FOYDALANILGAN ADABIYOTLAR ....................................................... 24

KIRISH. Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisobanadi. Algoritm ma’lum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi qoida hisoblanadi. “Qismiy ketma-ketlikni qidirish” asosan, algoritmda bu mavzuni yoritishimizda qidiruv nima ekanligiga to’xtalib o’tsak. Ma’lumotlarni qidirish algoritmlari bu- to’plam ma’lumotlar orasidan ma’lum bir kalit so’zga mos keluvchi elimentlarni qidirishga aytiladi. Ma’lumotlarni qidirish algoritmlari odatda ikki toifaga bo’linadi va bular quydagilar: Tarkibiy qidiruv: Bunda ro’yxat yoki qator ketma- ket o’tkaziladi va har bir eliment tekshiriladi. Bunga misol sifatida chiziqli qidiruvni keltirsak bo’ladi. Qidirish algoritmining eng soddasi bo’lgan chiziqli qidirish algoritmi, chiziqli ma’lumotlar tuzulmalaridan biror bir shart yoki qiymat bo’yicha eliment qidirishga mo’ljallangan va uning algoritmik murakkabligi quydagicha: Chiziqli qidirish algoritmining vaqt bo’yicha murakkabligi uning nomidan ham ma’lum, ya’ni chiziqli O(n). Ya’ni, eng yomon holat sifatida eliment array bo’lmagan holat qaraladi va bunda algoritm maximum n ta qadam ish bajarishi kerak bo’ladi. Intervalli qidirish- bu algoritmar maxsus ajratilgan ma’lumotlar tuzilmalarida qidirish uchun mo’ljallangan. Ushbu turdagi qidiruv algoritmlari Linear Search-ga qaraganda ancha samaralidir, chunki ular qayta-qayta qidiruv tuzulmasi markaziga yo’naladi va qidiruv maydonini ikkiga bo’ladi. Masalan: Ikkilik qidiruv. Ikkilik qidiruv- bu algoritmi asosan to’plamni ikkiga bo’lishlar orqali qidirishdan iborat. Ya’ni unda bo’linishlar toki kalit so’z topulmaganicha davom etadi. 2

I Qismiy ketma-ketlikni qidirish Kompyuterda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri hisoblanadi. Uning vazifasi berilgan argument bo’yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topish yoki bunday ma’lumot yo’qligini aniqlashdan iborat. Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yoki tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagona bo’lishi mumkin. Bunday noyob kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali ham qidiruvni amalga oshirish mumkin. Ma’lumotlar kalitini bir joyga yig’ish (boshqa jadvalga) yoki yozuv sifatida ifodalab bitta maydonga kalitlarni yozish mumkin. Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya’ni yozuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi. Kalitni berilgan argument bilan mosligini aniqlovchi algoritmga berilgan argument bo’yicha qidiruv deb ataladi. Qidiruv algoritmi vazifasi kerakli ma’lumotni jadvaldan topish yoki yo’qligini aniqlashdan iboratdir. Agar kerakli ma’lumot yo’q bo’lsa, u holda ikkita ishni amalga oshirish mumkin: 1. Ma’lumot yo’qligini indikatsiya qilish (belgilash) 2. Jadvalga ma’lumotni qo’yish. Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) – ma’lumot mavjud. Key – qidiruv argumenti. Unga rec - informatsion yozuv mos qo’yiladi. Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvning bir necha turlari mavjud. 1.1 Ketma-ket qidiruv algoritmi Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi. Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan element tartib raqamini saqlaydi). 3

Ketma-ket qidiruv algoritmi C++ tilida quyidagicha bo’ladi: int qidiruv(int key) { for (int i=0;i<n;i++)< p=""></n;i++)<> if (k[i]==key) { search = i;return search;} search = -1; return search; } } Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. M min = 1, M max = n. Agar ma’lumotlar massiv yacheykasida bir xil ehtimollik bilan taqsimlangan bo’lsa, u holda M o’rt  (n + 1)/2 bo’ladi. Agar kerakli element jadvalda yo’q bo’lib, uni jadvalga qo’shish lozim bo’lsa, u holda yuqorida keltirilgan algoritmdagi oxirgi ikkita operator quyidagicha almashtiriladi . n=n+1; k[n-1]:=key; r[n-1]:=rec; search:=n-1; return search; Agar ma’lumotlar jadvali bir bog’lamli ro’yhat ko’rinishida berilgan bo’lsa , u holda ketma-ket qidiruv ro’yhatda amalga oshiriladi. 1-Rasm Chiziqli bir bog’lamli ro’yhatdan key kalitga mos elementni ketma-ket qidiruv usuli yordamida izlab topish dasturi. Node *q=NULL; Node *p=lst; while (p !=NULL){ 4

if (p->k == key){ search = p; return search; } q = p; p = p->nxt; } Node *s=new Node;; s->k=key; s->r=rec; s->nxt= NULL; if (q == NULL){ s->nxt=lst; lst = s; } else q->nxt = s; search= s; return search; Ro’yhatli tuzilmaning afzalligi shundan iboratki, ro’yhatga elementni qo’shish yoki o’chirish tez amalga oshadi, bunda qo’shish yoki o’chirish element soniga bog’liq bo’lmaydi, massivda esa elementni qo’shish yoki o’chirish o’rta hisobda barcha elementlarning yarmini siljitishni talab qiladi. Ro’yhatda qidiruvning samaradorligi taxminan massivniki bilan bir xil bo’ladi. 1.2 Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi Faraz qilaylik, o’sish tartibida tartiblangan sonlar massivi berilgan bo’lsin. Ushbu usulning asosiy g’oyasi shundan iboratki, tasodifiy qandaydir A M element olinadi va u X qidiruv argumenti bilan taqqoslanadi. Agar A M =X bo’lsa, u holda qidiruv yakunlanadi; agar A M >X bo’lsa, u holda indekslari M dan katta bo’lgan barcha elementlar kelgusi qidiruvdan chiqarib yuboriladi. 5