logo
Русский O'zbekcha
  1. Главная страница
  2. Презентации
  3. Общий
  4. Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash

Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash

Загружено в:

24.12.2024

Скачано:

0

Размер:

739.4 KB
Условия скачивания
O’ZBEKISTON RESBUPLIKASI OLIY TA’LIM FAN VA INNOVATSIYALAR VAZIRLIGI SHAROF RASHIDOV NOMIDAGI SAMARQAND DAVLAT UNIVERSITETI INTELLEKTUAL TIZIMLAR VA KOMPYUTER TEXNOLOGIYALARI FAKULTETI sun’iy intellekt yo’nalishi Ma’lumotlar tuzulmasi fanidan 1-MUSTAQIL ISHI Bajardi: Abduvaitova O’g’iloy 2 -bosqich 201-guruhi talabasi Tekshirdi: Rabbimov G’ Samarqand 2024 Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash : 1. Aho-Korasik algoritmi Aho-Korasik algoritmi va Shiber-Vishkin algoritmi — bu matnni qidirish va tahlil qilish bilan bog‘liq bo‘lgan ikkita muhim algoritmdir. Har biri turli vazifalar uchun optimallashtirilgan va o‘ziga xos strukturalarga ega. Keling, ularning strukturasi va murakkabliklarini batafsil ko‘rib chiqamiz. 1. Aho-Korasik algoritmi Struktura: Aho-Korasik algoritmi ko‘p qismli qidirish algoritmidir va asosan "trie" (prefix tree) va "fail" (ko‘rsatgichlar) strukturalariga asoslanadi. Uning maqsadi bir nechta qidiruv so‘zlarini matnda samarali tarzda qidirishdir. Trie: Trie — bu so‘zlar yoki satrlarni saqlash uchun ishlatiladigan daraxt shaklidagi ma'lumotlar tuzilmasidir. Har bir tugun (node) so‘zning biror belgisini ifodalaydi, va yo‘lni davom ettirish orqali butun so‘zni topish mumkin. Fail: Aho-Korasik algoritmi "fail" deb ataladigan qo‘shimcha ko‘rsatgichlar qo‘shadi. Fail har bir tugun uchun qidiruvning "qayta davom etish" imkoniyatini beradi, ya'ni agar qidiruv to‘xtab qolsa, fail yordamida keyingi mos keladigan holatga o‘tish mumkin. Algoritmning ish tartibi: 1.Trie qurilishi: Dastlab, qidirilayotgan so‘zlarning barcha prefikslarini o‘z ichiga olgan trie daraxti quriladi. 2.Fail qurilishi: Har bir tugun uchun fail ko‘rsatgichlari hisoblanadi, bu ko‘rsatgichlar qidiruv davomida qachon va qanday qilib keyingi holatlarga o‘tishni aniqlashga yordam beradi. 3.Qidiruv: Matnda har bir belgi bilan qidiruv olib boriladi. Agar qidiruv tugunida davom eta olmasa, fail ko‘rsatgichiga asoslanib boshqa tugunga o‘tiladi. Murakkablik: Tayyorlash: Trie daraxtini qurishning va fail ko‘rsatgichlarini yaratishning vaqti O(mn) , bu yerda m — so‘zlar soni, n — har bir so‘z uzunligi. Qidiruv: Har bir belgi uchun qidiruv davomida O(N) , bu yerda N — matn uzunligi. Aho-Korasik algoritmi bir necha so‘zni matnda samarali tarzda qidirishga yordam beradi va qidiruvning vaqt murakkabligi O(N) ga tushadi. 2. Shiber-Vishkin algoritmi Struktura: Shiber-Vishkin algoritmi asosan ikki matnni taqqoslash uchun ishlatiladi va matnni qidirish jarayonida eng qisqa o‘zgartirishlar (edit distance) hisoblashga asoslangan. Dynamic Programming (DP): Algoritm o‘zining dinamik dasturlash metodini ishlatadi. Har bir qadamda ikki matn orasidagi minimal masofani hisoblashga harakat qiladi. DP matritsasi (yoki jadvali) yordamida har bir holatni hisoblashda optimal qaror qabul qilinadi. Algoritmning ish tartibi: 1.Matritsa yaratish: Matnlarning har bir belgisini taqqoslash uchun n × m o‘lchamdagi matritsa yaratiladi (bu yerda n va m — ikki matn uzunliklari). 2.Taqqoslash: Har bir juft belgi o‘rtasidagi farq hisoblanadi va matritsa orqali eng qisqa yo‘l (edit distance) aniqlanadi. Har bir qadamda qo‘shish, o‘chirish yoki almashtirish kabi operatsiyalarni hisoblash kerak bo‘ladi. 3.Tashlash: Algoritm yakunida minimal tahrirlar (operatsiyalar) soni (masofa) chiqadi. Murakkablik: Tayyorlash: DP matritsasini qurishning vaqti O(nm) , bu yerda n va m — matn uzunliklari. Qidiruv: DP jadvalini to‘ldirishning vaqti ham O(nm) bo‘ladi. Shiber-Vishkin algoritmi ikki matn orasidagi farqni topish va ularni moslashtirish uchun eng yaxshi yechimlardan biridir. Taqqoslash Xulosa Aho-Korasik algoritmi ko‘p so‘zli matnni qidirish uchun juda samarali, ayniqsa bir nechta so‘zlarni izlashda juda tezkor ishlaydi. Shiber-Vishkin algoritmi esa ikki matnni tahrir masofasi orqali taqqoslashga mo‘ljallangan va matnlar o‘rtasidagi o‘zgarishlarni aniqlash uchun juda foydalidir. Har ikki algoritm ham o‘zining maxsus vazifalarida samarali ishlaydi, ammo ularning murakkabligi va ishlash sharoitlari turlicha. Murakkablikni baholash: Vaqt murakkabligi : Aho-Korasik algoritmining vaqt murakkabligi asosan matn va naqshlar uzunligiga bog‘liq bo‘ladi. Har bir belgi uchun faqat bir marta qidiruv amalga oshiriladi, shuning uchun umumiy vaqt murakkabligi: O(n+m+z)O(n + m + z)O(n+m+z) n — matn uzunligi. m — naqshlar umumiy uzunligi. z — topilgan mosliklar soni. Xotira murakkabligi : Trie daraxti va fail pointerlarining xotira talabiga bog‘liq. Trie daraxti har bir naqshning uzunligi bo‘yicha joy talab qiladi, shuning uchun xotira murakkabligi: O(m)O(m)O(m) Bu yerda m — naqshlarning umumiy uzunligi. 2. Shiber-Vishkin algoritmi Shiber-Vishkin algoritmi (1989) — bu algoritm eng yaqin mosliklarni qidirish va qidiruvda kiritish, o'chirish va almashtirish operatsiyalarini amalga oshirish uchun ishlatiladi. Algoritm asosan parallel qidiruv va dinamik dasturlashdan foydalanadi . Algoritm strukturasini o ‘ rganish : Shiber - Vishkin algoritmi asosan quyidagi bosqichlardan iborat : 1. Dinamik dasturlash : Algoritmda dinamik dasturlash orqali qidirilayotgan naqsh va matnning mosliklarini kiritish , o ' chirish va almashtirish operatsiyalarini amalga oshirish uchun yaqinlik matritsasini hisoblash kerak bo ' ladi . Yaqinlik matritsasi har bir pozitsiyani va ularning o'zaro mosliklarini hisoblab chiqadi. 2.Parallelizatsiya : Shiber-Vishkin algoritmi parallel ishlov berish orqali samaradorlikni oshiradi. Algoritmda har bir bo‘lakni parallel tarzda ishlov berish imkoniyati mavjud. Bu katta matnlarni va naqshlarni parallel tarzda tezda qidirish imkonini beradi. 1.Yaqinlikni hisoblash : Algoritmda qidirilgan naqsh va matn orasidagi yaqinlikni hisoblashda qo‘llaniladigan operatsiyalar: Substitution (o'zgartirish) — belgi o‘zgartirish. Insertion (kiritish) — yangi belgi kiritish. Deletion (o'chirish) — belgi o'chirish. Yaqinlikni o‘lchash orqali qidiruvni optimallashtirish mumkin bo‘ladi. Murakkablikni baholash: Vaqt murakkabligi : Shiber-Vishkin algoritmi ko‘proq parallelizatsiyaga asoslangan va dinamik dasturlashni qo‘llaganligi sababli, uning vaqt murakkabligi va parallel ishlov berish imkoniyatlari uni katta matnlar bilan ishlashda samarali qiladi. Uning vaqt murakkabligi eng yaxshi holatda O(n) , ammo yomon holatda O(nm) bo'lishi mumkin, bunda n — matn uzunligi, m — naqsh uzunligi. Xotira murakkabligi : Dinamik dasturlash va yaqinlik matritsalarini hisoblashda xotira sarfi talab qilinadi. Bu algoritmda xotira murakkabligi asosan O(nm) bo‘lib, yaqinlik matritsasi saqlanadi. 3. Xulosa: Aho-Korasik algoritmi — bir nechta naqshni matnda bir vaqtning o‘zida izlash uchun samarali ishlaydi, uning vaqt murakkabligi O(n + m + z) va xotira murakkabligi O(m) . Shiber-Vishkin algoritmi esa eng yaqin mosliklarni qidirishda, kiritish, o‘zgartirish va o‘chirish operatsiyalarini hisoblashda yordam beradi. Uning vaqt murakkabligi O(nm) , lekin parallelizatsiya orqali samarali ishlashi mumkin. Xotira murakkabligi O(nm) bo‘lishi mumkin. Har ikkala algoritm ham o'zining samaradorligi va optimallashtirish imkoniyatlari bilan o'ziga xos xususiyatlarga ega. Aho-Korasik algoritmi ko‘proq naqshlarni izlash uchun, Shiber-Vishkin algoritmi esa qidiruvdagi mosliklar va yaqinlikni o‘lchash uchun qulaydir. Geometrik va matematik hisoblashlar uchun algoritmlar kompyuter fanlarida keng tarqalgan va turli muammolarni hal qilish uchun ishlatiladi. Ular turli sohalarda qo'llanilib, turli matematik masalalarni yechishda samarali bo'ladi. Quyida geometrik va matematik hisoblashlar uchun ishlatiladigan ba'zi algoritmlar va ularning strukturalari va murakkabliklarini baholash ko‘rib chiqiladi. 1. Geometrik Algoritmlar : Geometrik algoritmlar oddiy va murakkab geometrik shakllar va ob'ektlar bilan ishlash uchun ishlatiladi. Ular masalan, nuqtalar, chiziqlar, ko'pburchaklar, aylana va boshqa geometrik ob'ektlar bilan ishlaydi. 1.1. Jarayonlar va Strukturasi: Geometrik algoritmlar odatda quyidagi strukturalarga ega: Nuqtalar : Geometrik ob'ektlarni belgilash uchun nuqtalar (x, y) koordinatalari ishlatiladi. Chiziqlar va egri chiziqlar : Geometrik shakllarni belgilash va ularni hisoblash uchun chiziqlar va egri chiziqlar ishlatiladi. Ko‘pburchaklar : Ko‘pburchaklar (poligonlar) uchun algoritmlar, masalan, ko‘pburchaklarni kesish, birlashtirish yoki ko‘pburchaklar orasidagi masofani hisoblash kabi muammolarni hal qilish uchun ishlatiladi. Algoritmlar : Eng ko‘p ishlatiladigan geometrik algoritmlar orasida chiziqlar orasidagi kesish nuqtalarini aniqlash, konveks yopish, Delaunay uchburchaklari va Voronoy diagrammasi kabi algoritmlar bor. 1.2. Misol: Konveks yopish algoritmi (Convex Hull) Konveks yopish algoritmi — bu geometrik nuqtalar to'plamini o‘z ichiga oladigan eng kichik poligonni (konveks ko‘pburchak) topishni maqsad qiladi. Bu algoritmning ko‘plab variantlari mavjud, eng mashhurlari Graham scan va Jarvis march . Algoritm strukturasini o‘rganish : 1.Kirish : Nuqtalar to‘plami (x, y) koordinatalari. 2.Qadamlar : Nuqtalarni x va y bo‘yicha tartiblang. Eng chap nuqtadan boshlang va konveks yopishni qurish uchun nuqtalarni tanlang. Har bir yangi nuqta oldingi nuqtalar bilan tekshiriladi. 1.Chiqish : Eng kichik konveks ko‘pburchak. Vaqt murakkabligi : Graham scan algoritmi uchun O(n log n) va Jarvis march algoritmi uchun O(nh) , bunda n — nuqtalar soni, h — konveks ko‘pburchakning tomonlar soni. Xotira murakkabligi : O(n) , chunki barcha nuqtalar saqlanadi va har bir nuqta bitta safar bilan tekshiriladi. 2. Matematik Algoritmlar : Matematik algoritmlar sonli, algebraik va statistik masalalarni hal qilishda qo‘llaniladi. Ular asosan differensial tenglamalar, optimallashtirish, lineer algebralar, statistik hisoblashlar va boshqa matematik muammolarni yechishda ishlatiladi. 2.1. Jarayonlar va Strukturasi: Matematik algoritmlar odatda quyidagi strukturalarni o‘z ichiga oladi: Sonli hisoblashlar : Sonli integratsiya, differensial tenglamalar yechimi, matritsalarni o‘qish va ularni manipulyatsiya qilish kabi operatsiyalarni amalga oshirish. Optimallashtirish : Funksiyaning maksimal yoki minimal qiymatini topish (masalan, gradient tushishi, genetik algoritmlar). Lineer algebra : Matritsalarni yechish, determinantlarni hisoblash, eigen qiymatlarini topish va boshqa lineer operatsiyalar. Statistik hisoblashlar : Ma'lumotlar tahlili, regressiya, tahliliy model qurish va statistik testlar. 2.2. Misol: Gauss-Seidel algoritmi (Lineer tizimlarni yechish) Gauss-Seidel algoritmi — bu lineer tenglamalar tizimini yechish uchun ishlatiladigan takroriy yondashuvni qo‘llaydi. Algoritm strukturasini o‘rganish : 1.Kirish : Ax = b kabi lineer tizim. 2.Qadamlar : Har bir tenglama uchun yangi qiymatni hisoblash. Har bir qiymatning yangilanishi oldingi iteratsiya natijalariga bog‘liq. Bu jarayon kerakli aniqlikka erishilguncha takrorlanadi. 1.Chiqish : Yechim vektori x. Vaqt murakkabligi : O(n^2) , bunda n — tenglamalar soni, chunki har bir iteratsiya uchun barcha tenglamalar tekshiriladi. Xotira murakkabligi : O(n) , har bir qiymatni saqlash uchun xotira kerak bo‘ladi. 3. Murakkablikni baholash Geometrik va matematik algoritmlar uchun murakkablik ni baholash ikki turga bo‘linadi: vaqt murakkabligi va xotira murakkabligi. 3.1. Geometrik algoritmlarning murakkabligini baholash: Geometrik algoritmlar ko‘pincha nuqtalar, chiziqlar, va poligonlar ustida ishlaydi. Ularning murakkabligi asosan operatsiyalarning (masalan, nuqtalar orasidagi masofa yoki kesish nuqtalarini topish) soniga va algoritmda ishlatiladigan ma'lumotlar tuzilmasiga bog‘liq. Misol uchun, konveks yopish algoritmida vaqt murakkabligi O(n log n) va O(nh) bo‘ladi. Bu holda n — nuqtalar soni, va h — konveks ko‘pburchakning tomonlari soni. 3.2. Matematik algoritmlarning murakkabligini baholash: Matematik algoritmlar, masalan, lineer tizimlarni yechish algoritmlarida, O(n^2) yoki undan ham yuqori bo‘lishi mumkin. Optimallashtirish algoritmlari odatda O(n log n) yoki ba'zi holatlarda O(n^2) bo‘ladi, bu ular qanday optimallashtirish usuli (masalan, gradient tushish) ishlatishiga bog‘liq. 4. Xulosa: Geometrik algoritmlar murakkabligi, asosan, nuqtalar, chiziqlar va poligonlar bilan ishlash jarayonida ma'lumotlar tuzilmalari (masalan, ko‘pburchaklar) va operatsiyalar soniga bog‘liq. Matematik algoritmlar esa asosan sonli hisoblashlar, lineer algebralar va optimallashtirish masalalariga asoslangan. Ularning murakkabligi ko‘pincha iteratsiyalar va matritsa manipulyatsiyalariga bog‘liq bo‘ladi. 1 . Rekursiv Algoritmlar Rekursiv algoritm — bu algoritmning o‘zi o‘zini chaqirishi. Bu usulni qo‘llagan holda masalalarni oddiy va aniq yechish mumkin, ammo samaradorlik masalalari yuzaga kelishi mumkin, chunki ba'zi subproblemalar qayta-qayta hisoblanadi. Rekursiv algoritm misoli: Fibbonachchi sonlari Fibbonachchi sonlarini rekursiv usulda hisoblash: #include <iostream> using namespace std; // Rekursiv Fibbonachchi funksiyasi int fibonacci(int n) { // To'xtash sharti if (n <= 1) { return n; } // Rekursiv chaqiruv return fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n = 10; // Fibbonachchi sonining 10-chi elementini hisoblash cout << "Fibbonachchi sonining " << n << "-chi elementi: " << fibonacci(n) << endl; return 0; } Izohlar: Rekursiv chaqiruvlar : Har bir fibonacci(n) chaqiruvi ikkita yana rekursiv chaqiruvni yaratadi (fibonacci(n-1) va fibonacci(n-2)). To'xtash sharti : Agar n <= 1 bo‘lsa, rekursiya to‘xtaydi. Murakkablik: Vaqt murakkabligi : O(2^n), chunki har bir chaqiruv ikkita chaqiruvni yaratadi. Xotira murakkabligi : O(n), rekursiv stackning balandligi n bo‘ladi. 2. Dinamik Dasturlash Algoritmlari Dinamik dasturlash (DP) — bu masalani kichik subproblemlarga bo‘lib, har bir subproblemning yechimini saqlash va keyin uni ishlatish usulidir. Bu usul rekursiyani optimallashtirish orqali samaradorlikni oshiradi. Dinamik dasturlash misoli: Fibbonachchi sonlari Fibbonachchi sonlarini dinamik dasturlash yordamida hisoblash: #include <iostream> #include <vector> using namespace std; // Dinamik dasturlash orqali Fibbonachchi sonini hisoblash int fibonacci(int n) { // Fibbonachchi sonlarini saqlash uchun massiv vector<int> fib(n + 1); fib[0] = 0; // Fibbonachchi soni 0 fib[1] = 1; // Fibbonachchi soni 1 // Har bir fib(i) sonini hisoblash for (int i = 2; i <= n; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } return fib[n]; // N-chi fibonachchi soni } int main() { int n = 10; // Fibbonachchi sonining 10-chi elementini hisoblash cout << "Fibbonachchi sonining " << n << "-chi elementi: " << fibonacci(n) << endl; return 0; } Izohlar: Dinamik dasturlash da, har bir Fibbonachchi soni bir marta hisoblanadi va saqlanadi. Bu ortiqcha hisoblashlarni oldini oladi. Vektor yordamida barcha Fibbonachchi sonlari saqlanadi. Murakkablik: Vaqt murakkabligi : O(n), har bir fib(i) soni faqat bir marta hisoblanadi. Xotira murakkabligi : O(n), barcha fib(i) qiymatlari saqlanadi. 3. Dinamik Dasturlash: Eng uzun ortib boruvchi subsequence (LIS) Endi eng uzun ortib boruvchi subsequence (LIS) masalasini yechish uchun dinamik dasturlashni ko‘rib chiqamiz. Bu masalani yechishda har bir elementni oldingi elementlar bilan solishtirib, ortib boruvchi subsequence uzunligini hisoblaymiz. #include <iostream> #include <vector> #include <algorithm> using namespace std; // Eng uzun ortib boruvchi subsequence (LIS) funksiyasi int lis(const vector<int>& arr) { int n = arr.size(); vector<int> dp(n, 1); // dp massivini boshlang'ich qiymatlari 1 // Har bir element uchun ortib boruvchi subsequence uzunligini hisoblash for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { dp[i] = max(dp[i], dp[j] + 1); } } } // Maksimal LIS uzunligini qaytarish return *max_element(dp.begin(), dp.end()); } int main() { vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80}; cout << "Eng uzun ortib boruvchi subsequence uzunligi: " << lis(arr) << endl; return 0; } Izohlar: dp massiv : Bu massiv har bir element uchun eng uzun ortib boruvchi subsequence uzunligini saqlaydi. Har bir element uchun oldingi elementlar bilan solishtirib, maksimal uzunlikni hisoblaymiz. Murakkablik: Vaqt murakkabligi : O(n^2), har bir element uchun boshqa barcha elementlar bilan solishtirish. Xotira murakkabligi : O(n), dp massivining har bir qiymatini saqlash. Rekursiv yondashuv: Eng uzun ortib boruvchi subsequence (LIS) Endi rekursiv yondashuv yordamida eng uzun ortib boruvchi subsequence (LIS) masalasini yechamiz. #include <iostream> #include <vector> #include <algorithm> using namespace std; // Rekursiv yondashuv yordamida LIS hisoblash int lis_recursive(const vector<int>& arr, int n) { // To'xtash sharti if (n == 1) { return 1; } int max_len = 1; // Har bir elementni tekshirish for (int i = 1; i < n; i++) { if (arr[i - 1] < arr[n - 1]) { max_len = max(max_len, lis_recursive(arr, i) + 1); } } return max_len; } int main() { vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80}; int n = arr.size(); cout << "Eng uzun ortib boruvchi subsequence uzunligi: " << lis_recursive(arr, n) << endl; return 0; } Izohlar: Rekursiv yondashuv : Bu usulda har bir elementni oldingi elementlar bilan solishtiramiz va ortib boruvchi subsequence uzunligini rekursiv chaqiruv orqali hisoblaymiz. To‘xtash sharti : Agar n == 1 bo‘lsa, rekursiya to‘xtaydi. Murakkablik: Vaqt murakkabligi : O(2^n), rekursiv chaqiruvlar yuqori darajada takrorlanadi. Xotira murakkabligi : O(n), rekursiv stackning balandligi n bo‘ladi. Xulosa Rekursiv algoritmlar oddiy va intuitiv bo‘lishi mumkin, lekin samaradorlik past bo‘lishi mumkin, chunki subproblemalar qayta-qayta hisoblanadi. Dinamik dasturlash esa rekursiyani optimallashtirishga yordam beradi, subproblemalar faqat bir marta hisoblanadi va natijalar saqlanadi. Bu usul ko‘proq samarali. Har ikki yondashuvning murakkabligi va ishlash samaradorligini hisobga olgan holda, mos masalalar uchun to‘g‘ri yondashuvni tanlash zarur. 1. Brute Force algoritmi Brute Force algoritmi — bu masalani yechishning eng oddiy va to‘liq usuli bo‘lib, har bir mumkin bo‘lgan variantni tekshirishni o‘z ichiga oladi. Bu yondashuvda har bir mumkin bo‘lgan yechim o‘rganiladi, bu esa juda ko‘p vaqt talab qilishi mumkin. Brute Force algoritmi misoli: Maksimal elementni topish Masala : Berilgan massivdagi maksimal elementni topish. C++ kodi: #include <iostream> #include <vector> using namespace std; // Brute Force algoritmi orqali maksimal elementni topish int findMax(const vector<int>& arr) { int maxVal = arr[0]; for (int i = 1; i < arr.size(); i++) { if (arr[i] > maxVal) { maxVal = arr[i]; } } return maxVal; } int main() { vector<int> arr = {1, 3, 5, 2, 4}; cout << "Massivdagi maksimal element: " << findMax(arr) << endl; return 0; } Tahlil: Vaqt murakkabligi : O(n), chunki har bir elementni faqat bitta marta tekshiradi. Xotira murakkabligi : O(1), faqat maksimal qiymatni saqlash uchun bitta o‘zgaruvchi kerak bo‘ladi. Brute Force yondashuvi odatda juda samarali bo‘lmasa ham, kichik masalalar uchun juda oddiy va tez bajariladi. 2. Backtracking algoritmi Backtracking algoritmi — bu yechim qidirish algoritmi bo‘lib, bosqichma-bosqich muammo yechimini topish jarayonida noto‘g‘ri yechimlarga borib qolsa, ortga qaytib, yangi yo‘lni sinab ko‘rishga imkon beradi. Backtracking, odatda, mumkin bo‘lgan barcha yechimlarni tekshirib chiqadi, lekin noto‘g‘ri yo‘ldan qaytib, boshqa yo‘llarni sinash imkoniyatiga ega. Backtracking algoritmi misoli: N-Queens masalasi Masala : N ta malika (queen) ni N x N shaxmat doskasiga joylashtiring, shunda hech biri bir-biriga hujum qilmasin (ya'ni, ular bir-birining yo‘nalishida bo‘lmasin). C++ kodi: #include <iostream> #include <vector> using namespace std; bool isSafe(const vector<vector<int>>& board, int row, int col, int n) { // Qatorni tekshirish for (int i = 0; i < col; i++) { if (board[row][i] == 1) { return false; } } // Chap yuqori diagonali tekshirish for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 1) { return false; } } // O'ng yuqori diagonali tekshirish for (int i = row, j = col; j >= 0 && i < n; i++, j--) { if (board[i][j] == 1) { return false; } } return true; } bool solveNQueens(vector<vector<int>>& board, int col, int n) { // Agar barcha malikalarga joy berilgan bo'lsa, yechimni topdik if (col >= n) { return true; } // Har bir qatorni tekshirish for (int i = 0; i < n; i++) { if (isSafe(board, i, col, n)) { board[i][col] = 1; // Malika joylashdi // Rekursiv chaqiruv if (solveNQueens(board, col + 1, n)) { return true; } // Orqaga qaytish (Backtrack) board[i][col] = 0; // Malika o‘chiriladi } } return false; // Agar hech qanday joylashuv bo'lmasa } void printBoard(const vector<vector<int>>& board, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << (board[i][j] ? "Q " : ". "); } cout << endl; } } int main() { int n = 4; vector<vector<int>> board(n, vector<int>(n, 0)); if (solveNQueens(board, 0, n)) { printBoard(board, n); } else { cout << "Yechim mavjud emas!" << endl; } return 0; } Tahlil: Vaqt murakkabligi : O(N!), bu hamma malikalarga joy berish va har bir holatda qayta sinash jarayonida optimallashtirilmagan backtracking algoritmi. Bu vaqtning ko‘p qismini eksploratizmga sarflaydi. Xotira murakkabligi : O(N^2), shaxmat doskasi hajmi. Backtracking haqida qisqacha tahlil: Backtracking algoritmi imkoniyatlarni tekshirishda samarali bo‘lishi mumkin, chunki noto‘g‘ri yechimlar darhol bekor qilinadi. Bu yondashuv optimallashtirilgan bo‘lmasligi sababli, katta N qiymatlari uchun samaradorlikning pasayishi mumkin. Brute Force vs. Backtracking 1.Brute Force : Oddiy va oson tushunarli yondashuv. Barcha mumkin bo‘lgan variantlarni tekshiradi, hatto ba'zi variantlar noto‘g‘ri bo‘lsa ham. Murakkablik : O(n!), ya'ni yechimlar soni juda katta bo‘lgan masalalarda samarasiz bo‘lishi mumkin. 2.Backtracking : Qayta-qayta yechimlarni tekshirishni optimallashtiradi va faqat kerakli yo‘llarni sinab ko‘radi. Noto‘g‘ri yo‘lga borilsa, ortga qaytib, boshqa variantlarni sinaydi. Murakkablik : O(N!), lekin ba'zi masalalarda pruning (kesish) jarayoni orqali samaradorlikni oshirishi mumkin. Xulosa Brute Force har doim barcha variantlarni tekshiradi va bu ba'zan samarali bo‘lmasligi mumkin, ayniqsa katta masalalar uchun. Backtracking esa ba'zi variantlarni bekor qilib, faqat to‘g‘ri yo‘lni izlashni davom ettiradi, lekin bu ham har doim samarali emas, ayniqsa katta o‘lchamli masalalar uchun.

O’ZBEKISTON RESBUPLIKASI OLIY TA’LIM FAN VA INNOVATSIYALAR VAZIRLIGI SHAROF RASHIDOV NOMIDAGI SAMARQAND DAVLAT UNIVERSITETI INTELLEKTUAL TIZIMLAR VA KOMPYUTER TEXNOLOGIYALARI FAKULTETI sun’iy intellekt yo’nalishi Ma’lumotlar tuzulmasi fanidan 1-MUSTAQIL ISHI Bajardi: Abduvaitova O’g’iloy 2 -bosqich 201-guruhi talabasi Tekshirdi: Rabbimov G’ Samarqand 2024

Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash : 1. Aho-Korasik algoritmi Aho-Korasik algoritmi va Shiber-Vishkin algoritmi — bu matnni qidirish va tahlil qilish bilan bog‘liq bo‘lgan ikkita muhim algoritmdir. Har biri turli vazifalar uchun optimallashtirilgan va o‘ziga xos strukturalarga ega. Keling, ularning strukturasi va murakkabliklarini batafsil ko‘rib chiqamiz. 1. Aho-Korasik algoritmi Struktura: Aho-Korasik algoritmi ko‘p qismli qidirish algoritmidir va asosan "trie" (prefix tree) va "fail" (ko‘rsatgichlar) strukturalariga asoslanadi. Uning maqsadi bir nechta qidiruv so‘zlarini matnda samarali tarzda qidirishdir. Trie: Trie — bu so‘zlar yoki satrlarni saqlash uchun ishlatiladigan daraxt shaklidagi ma'lumotlar tuzilmasidir. Har bir tugun (node) so‘zning biror belgisini ifodalaydi, va yo‘lni davom ettirish orqali butun so‘zni topish mumkin. Fail: Aho-Korasik algoritmi "fail" deb ataladigan qo‘shimcha ko‘rsatgichlar qo‘shadi. Fail har bir tugun uchun qidiruvning "qayta davom etish" imkoniyatini beradi, ya'ni agar qidiruv to‘xtab qolsa, fail yordamida keyingi mos keladigan holatga o‘tish mumkin. Algoritmning ish tartibi: 1.Trie qurilishi: Dastlab, qidirilayotgan so‘zlarning barcha prefikslarini o‘z ichiga olgan trie daraxti quriladi. 2.Fail qurilishi: Har bir tugun uchun fail ko‘rsatgichlari hisoblanadi, bu ko‘rsatgichlar qidiruv davomida qachon va qanday qilib keyingi holatlarga o‘tishni aniqlashga yordam beradi. 3.Qidiruv: Matnda har bir belgi bilan qidiruv olib boriladi. Agar qidiruv tugunida davom eta olmasa, fail ko‘rsatgichiga asoslanib boshqa tugunga o‘tiladi. Murakkablik: Tayyorlash: Trie daraxtini qurishning va fail ko‘rsatgichlarini yaratishning vaqti O(mn) , bu yerda m — so‘zlar soni, n — har bir so‘z uzunligi. Qidiruv: Har bir belgi uchun qidiruv davomida O(N) , bu yerda N — matn uzunligi. Aho-Korasik algoritmi bir necha so‘zni matnda samarali tarzda qidirishga yordam beradi va qidiruvning vaqt murakkabligi O(N) ga tushadi. 2. Shiber-Vishkin algoritmi Struktura: Shiber-Vishkin algoritmi asosan ikki matnni taqqoslash uchun ishlatiladi va matnni qidirish jarayonida eng qisqa o‘zgartirishlar (edit distance) hisoblashga asoslangan.

Dynamic Programming (DP): Algoritm o‘zining dinamik dasturlash metodini ishlatadi. Har bir qadamda ikki matn orasidagi minimal masofani hisoblashga harakat qiladi. DP matritsasi (yoki jadvali) yordamida har bir holatni hisoblashda optimal qaror qabul qilinadi. Algoritmning ish tartibi: 1.Matritsa yaratish: Matnlarning har bir belgisini taqqoslash uchun n × m o‘lchamdagi matritsa yaratiladi (bu yerda n va m — ikki matn uzunliklari). 2.Taqqoslash: Har bir juft belgi o‘rtasidagi farq hisoblanadi va matritsa orqali eng qisqa yo‘l (edit distance) aniqlanadi. Har bir qadamda qo‘shish, o‘chirish yoki almashtirish kabi operatsiyalarni hisoblash kerak bo‘ladi. 3.Tashlash: Algoritm yakunida minimal tahrirlar (operatsiyalar) soni (masofa) chiqadi. Murakkablik: Tayyorlash: DP matritsasini qurishning vaqti O(nm) , bu yerda n va m — matn uzunliklari. Qidiruv: DP jadvalini to‘ldirishning vaqti ham O(nm) bo‘ladi. Shiber-Vishkin algoritmi ikki matn orasidagi farqni topish va ularni moslashtirish uchun eng yaxshi yechimlardan biridir. Taqqoslash Xulosa Aho-Korasik algoritmi ko‘p so‘zli matnni qidirish uchun juda samarali, ayniqsa bir nechta so‘zlarni izlashda juda tezkor ishlaydi. Shiber-Vishkin algoritmi esa ikki matnni tahrir masofasi orqali taqqoslashga mo‘ljallangan va matnlar o‘rtasidagi o‘zgarishlarni aniqlash uchun juda foydalidir. Har ikki algoritm ham o‘zining maxsus vazifalarida samarali ishlaydi, ammo ularning murakkabligi va ishlash sharoitlari turlicha.

Murakkablikni baholash: Vaqt murakkabligi : Aho-Korasik algoritmining vaqt murakkabligi asosan matn va naqshlar uzunligiga bog‘liq bo‘ladi. Har bir belgi uchun faqat bir marta qidiruv amalga oshiriladi, shuning uchun umumiy vaqt murakkabligi: O(n+m+z)O(n + m + z)O(n+m+z) n — matn uzunligi. m — naqshlar umumiy uzunligi. z — topilgan mosliklar soni. Xotira murakkabligi : Trie daraxti va fail pointerlarining xotira talabiga bog‘liq. Trie daraxti har bir naqshning uzunligi bo‘yicha joy talab qiladi, shuning uchun xotira murakkabligi: O(m)O(m)O(m) Bu yerda m — naqshlarning umumiy uzunligi. 2. Shiber-Vishkin algoritmi Shiber-Vishkin algoritmi (1989) — bu algoritm eng yaqin mosliklarni qidirish va qidiruvda kiritish, o'chirish va almashtirish operatsiyalarini amalga oshirish uchun ishlatiladi. Algoritm asosan parallel qidiruv va dinamik dasturlashdan foydalanadi . Algoritm strukturasini o ‘ rganish : Shiber - Vishkin algoritmi asosan quyidagi bosqichlardan iborat : 1. Dinamik dasturlash : Algoritmda dinamik dasturlash orqali qidirilayotgan naqsh va matnning mosliklarini kiritish , o ' chirish va almashtirish operatsiyalarini amalga oshirish uchun yaqinlik matritsasini hisoblash kerak bo ' ladi . Yaqinlik matritsasi har bir pozitsiyani va ularning o'zaro mosliklarini hisoblab chiqadi. 2.Parallelizatsiya : Shiber-Vishkin algoritmi parallel ishlov berish orqali samaradorlikni oshiradi. Algoritmda har bir bo‘lakni parallel tarzda ishlov berish imkoniyati mavjud. Bu katta matnlarni va naqshlarni parallel tarzda tezda qidirish imkonini beradi.

Загрузите документ, чтобы увидеть его полностью.

Похожие

Shiber-vishkin algoritmi
Fenvik daraxti va algoritmi
Deykstra Algoritmi
Bit algoritmi
KRASKAL ALGORITMI