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.

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