126.Kalit hosil qiluvchi xesh funksiyalar
Kalit hosil qiluvchi xesh funksiyalar: bcrypt, PBKDF2, scrypt.
Kriptografik xesh funksiyalarning esa quyidagi turlari mavjud:
1) kalitli xesh funksiya; 2) kalitsiz xesh funksiya.
Kalitli xesh funksiyalar simmetrik shifrlash algoritmi tizimlarida
qo‘llaniladi. Kalitli xesh funksiyalar berilgan ma’lumot
autentifikatsiyasi kodi (message authentication code(MAC)) deb ham
yuritiladi. Ushbu kod bir-biriga ishonchi mavjud foydalanuvchilarga
berilgan ma’lumotining haqiqiyligi va to‘laligini kafolatini qo‘shimcha
vositalarsiz ta’minlash imkoniyatini tugʻdiradi.
pic
Kalitsiz xesh funksiyalar xatolarni topish kodi (modification
detection code(MDC) yoki manipulation detection code, massage
integrrity code(MIC) deb ataladi. Ushbu kod qo‘shimcha vositalar
(masalan: himoyalangan aloqa tarmogʻi, shifrlash yoki ERI
algoritmlari) yordamida berilgan ma’lumot to‘laligini kafolatlaydi. Bu
turdagi xesh funksiyalardan bir-biriga ishonch bildiruvchi va ishonchi
bo‘lmagan tomonlar foydalanishlari mumkin
127. Graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari
Eng kichik uzunlikdagi daraxt – berilgan grafning eng kam
darajaga ega boʻlgan daraxti, bu yerda daraxtning darajasi uning qirralari
daajalari yigʻindisi sifatida tushuniladi
Minimal uzunlikdagi daraxtni topish uchun bir nechta algoritmlar
mavjud. Eng mashhurlari quyida keltirilgan:
1) Prima algoritmi;
2) Kruskal algoritmi;
3) Boruvka algoritmi,
4) Orqadan o'chirish algoritmi
128. Eng kichik uzunlikdagi daraxt
Eng kichik uzunlikdagi daraxt – berilgan grafning eng kam
darajaga ega boʻlgan daraxti, bu yerda daraxtning darajasi uning qirralari
daajalari yigʻindisi sifatida tushuniladi.
Misol. Minimal uzunlikdagi daraxtni topish muammosi ko'pincha
xuddi shunday sharoitda uchraydi: masalan, har qanday shahardan
boshqasiga (to'gʻridan-to'gʻri yoki boshqa shaharlar orqali) o'tish uchun
n ta shaharlarni yo'llar bilan bogʻlash kerak. Berilgan juft shaharlar
o'rtasida yo'llar qurishga ruxsat beriladi va har bir bunday yo'lni qurish
qiymati ma'lum. Qurilishning umumiy narxini minimallashtirish uchun
qaysi yo'llarni qurish kerakligini hal qilish talab qilinadi.
Ushbu muammoni grafika nazariyasi nuqtai nazaridan
shakllantirish mumkin. Bu yerda berilgan grafnin uchlari shaharlarni,
qirralari esa to'gʻri yo'l qurilishi mumkin bo'lgan va qirralarning
ogʻirliklari teng bo'lgan shaharlarni ifodalaydigan minimal daraxtini
topish muammosidir.
129.Kruskal algoritmi
Kruskal algoritmida qirralarning butun birlashtirilgan ro'yxati
kamaymaydigan uch darajalariga muvofiq tartiblangan. Bundan tashqari,
qirralar darajalari kichikroq bo'lgan qirralardan yuqori tomonga siljiydi
va keyingi uch ilgari tanlangan qirralar bilan sikl hosil qilmasa, karkasga
qo'shiladi. Xususan, grafdagi minimal darajadagi qirralaridan biri har
doim birinchi bo'lib tanlanadi.
Tanlangan qirralarning sikl hosil qilmasligini tekshirish uchun biz
grafni bir nechta bogʻlangan komponentlarning birlashishi sifatida
namoyish etamiz. Eng boshida, grafning chekkalari tanlanmaganida, har
bir uch alohida bogʻlangan komponent hisoblanadi. Yangi qirralar
qo'shilganda, ulanish komponentlari bitta umumiy ulanish komponenti
bo'lguncha birlashadi. Barcha bogʻlangan tarkibiy qismlarni
raqamlaymiz va har bir uch uchun uning ulangan qismlarini sonini
saqlaymiz, shuning uchun har bir uch uchun boshida uning bogʻlangan
komponentlari soni uchning o'zi soniga teng bo'ladi va oxirgi barcha
176
uchlar bir-biriga bogʻlangan komponentning bir xil raqamlariga tegishli
bo'ladi.
Keyingi qirrani ko'rib chiqayotganda, ushbu qirraning uchlariga
to'gʻri keladigan ulangan komponentlarning raqamlarini ko'rib chiqamiz.
Agar bu raqamlar bir xil bo'lsa, unda qirra allaqachon bir xil bogʻlangan
komponentda joylashgan ikkita uchni birlashtiradi, shuning uchun bu
qirrani qo'shish siklni tashkil qiladi. Agar qirra ikki xil bogʻlangan
komponentni, masalan, 𝑎 va 𝑏 raqamlari bilan bogʻlasa, u holda qirra
asosiy daraxtning bir qismiga qo'shiladi va bu ikkita bogʻlangan
komponentlar birlashtiriladi. Buning uchun, masalan, ilgari 𝑏
komponentida bo'lgan barcha uchlar uchun komponent raqamini 𝑎 ga
o'zgartirish kerak.
Kruskal algoritmini amalga oshirish bosqichlari quyidagicha:
1) Barcha qirralarni quyidan yuqorigacha saralash.
2) Vazni eng kichik qirrasini oling va uni daraxtga qo'shing. Agar qirra
qoʻshilganda, sikl hosil boʻlsa, u holda bu qirrani olib tashlang.
3) Barcha uchlarga yetguncha qirralarni qo'shishni davom eting.
130.Kruskal algoritmining bajarilish ketma ketligi.
Kruskal algoritmini amalga oshirish bosqichlari quyidagicha:
1) Barcha qirralarni quyidan yuqorigacha saralash.
2) Vazni eng kichik qirrasini oling va uni daraxtga qo'shing. Agar qirra
qoʻshilganda, sikl hosil boʻlsa, u holda bu qirrani olib tashlang.
3) Barcha uchlarga yetguncha qirralarni qo'shishni davom eting.
Quyidagi rasmda minimal uzunlikka kiritilgan qirralar qizil rang
bilan, qora rang bilan esa nomzodlar ulardan eng kam darajadagi qirra
tanlangan.
pic
Kruskal algoritmini realizatsiya qilish (C++ kodi)
int n, m;
cin >> n >> m;
vector > edges(m, vector(3));
for (int i = 0; i < m; ++i)
cin >> edges[i][1] >> edges[i][2] >> edges[i][0];
sort(edges.begin(), edges.end());
vector comp(n);
for (int i = 0; i < n; ++i)
comp[i] = i;
int ans = 0;
for (auto & edge: edges)
{
int weight = edge[0];
int start = edge[1];
int end = edge[2];
if (comp[start] != comp[end])
{
ans += weight;
int a = comp[start];
int b = comp[end];
for (int i = 0; i < n; ++i)
if (comp[i] == b)
178
comp[i] = a;
}
}
131.prima algoritmi.
pic
132.prima algoritmining C++da kodi.
Quyidagi dastur Primaning algoritmini C ++ da amalga oshiradi.
Grafni ko'rsatish uchun qo'shnilik matritsa ishlatilgan bo'lsa-da, ushbu
algoritm samaradorligini oshirish uchun qo'shnilik ro'yxati yordamida
ham amalga oshirilishi mumkin.
#include
#include
using namespace std;
#define INF 9999999
// grafdagi uchlar soni
#define V 5
//Qo'shnilik matritsasini ifodalash uchun
//5x5 o'lchamdagi ikki o'lchamli massivni yaratish
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}
180
};
int main () {
int no_edge; // qirralar soni
// tanlangan uchni kuzatish uchun massiv yaratish
int selected[V];
// dastlab false qiymatini berish
memset (selected, false, sizeof (selected));
// qiralar soniga 0 ni berish
no_edge = 0;
selected[0] = true;
int x; // qator raqami
int y; // ustun raqami
// qirra va ogʻirlikni chop etish
cout << "Qirra" << " : " << "Masofasi";
cout << endl;
while (no_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]) {
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
181
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
selected[y] = true;
no_edge++;
}
return 0;
}
133.Prima algoritmining murakkabligini baholang.
Algoritmni 1930 yilda chex matematikasi Voytox Yarnik, keyinroq mustaqil ravishda
1957 yilda kompyuter olimi Robert C. Prim tomonidan ishlab chiqilgan. 1959 yilda
Edsger Dijkstra tomonidan qayta kashf qilingan. Algoritm uchta asosiy bosqichda
ifodalanishi mumkin;
N tugunlari va har bir qirraning tegishli og'irligi bilan bog'langan grafikni hisobga
olgan holda,
1. Grafikdan ixtiyoriy tugunni tanlang va uni T daraxtiga qo'shing (bu birinchi tugun bo'ladi)
2. Daraxtdagi tugunlarga ulangan har bir qirraning og'irligini ko'rib chiqing va minimalini tanlang.
T daraxtining boshqa uchidagi chekka va tugunni qo'shing va qirrani grafikdan olib tashlang.
(Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Daraxtga n-1 qirralari qo'shilmaguncha, 2-qadamni takrorlang.
Bu usulda daraxt bitta ixtiyoriy tugun bilan boshlanadi va har bir tsikl bilan
shu tugundan boshlab kengayadi. Demak, algoritm to'g'ri ishlashi uchun grafik
bog'langan grafik bo'lishi kerak. Prim algoritmining asosiy shakli O (V 2 ) vaqt
murakkabligiga ega.
134.Kruskal algoritmining murakkabligini baholang.
Jozef Kruskal tomonidan ishlab chiqilgan algoritm Amerika matematik jamiyati ishida 1956 yilda paydo bo'lgan.
Kruskal algoritmini uchta oddiy qadam bilan ifodalash mumkin.
N tugunli grafik va har bir qirraning tegishli og'irligi hisobga olinsa,
1. Butun grafikning eng kichik og'irligi bo'lgan yoyni tanlang va daraxtga qo'shing va grafikdan o'chiring.
2. Qolganlardan, tsikl hosil qilmaydigan tarzda, eng kam vaznli chekkani tanlang. Daraxtga chekkasini qo'shing
va grafikdan o'chiring. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Jarayonni 2 -bosqichda takrorlang.
Bu usulda algoritm eng kam qirrali bilan boshlanadi va har bir tsiklda har bir chekkani tanlashda davom etadi.
Shuning uchun algoritmda grafikni ulash shart emas. Kruskal algoritmining vaqt murakkabligi O (logV)
135.Minimal yo'lni topish masalasi
Amaliyotda uchraydigan ko‘plab masalalarda marshrut uzunligi
maksimallashtirilishi yoki minimallashtirilishi talab etiladi. Shunday
masalalardan biriga, aniqrogʻi, kommivoyajer masalasiga Gamilton
graflari bilan shugʻullanganda duch kelamiz.
G = (V,U )
oriyentirlangan graf berilgan bo‘lsin, bu yerda
V = {1,2,..., m}
. G
grafning biror
s(tegishli)V
uchidan boshqa
t (tegishli)V
uchiga boruvchi yo‘llar
orasida uzunligi eng kichik bo‘lganini topish masalasi bilan
shugʻullanamiz. Bu masalani minimal uzunlikka ega yo‘l haqidagi
masala deb ataymiz. Quyida bu masalaning umumlashmasi hisoblangan
masalani qarab, uni ham o‘sha nom bilan ataymiz.
G grafda umumiy uzunligi
manfiy bo‘lgan sikl mavjud emas deb hisoblaymiz, chunki aks holda
uzunligi eng kichik bo‘lgan yo‘l mavjud emas
Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari
orasida Deykstra
tomonidan taklif etilgan algoritm ko‘p qo‘llaniladi.
Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul
qilamiz) grafdagi ixtiyoriy
k uchgacha (bu uchni oxirgi uch deb
hisoblaymiz) eng qisqa uzunlikka ega yo‘lni topish imkonini beruvchi
Deykstra algoritmi keltirilgan
136.Minimal yo'lni topish masalasini yechish uchun ishlab chiqilgan algoritmlar.
Floyd Algoritmi
Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell
algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan
graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni
topishga xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy
og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan
ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat
Ushbu algoritm Dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki u har
qanday ikki ustun o'rtasida eng qisqa yo'llarni topadi.
Floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan NxN matritsasi
ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy
qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori
qismidan masofaga teng.
Dijkstra algoritmi grafning tepalaridan biriga eng qisqa yo'lni topish uchun algoritm
bo'lib u faqat salbiy og'irlikdagi qovurg'alarsiz grafikalar uchun ishlaydi.
Floyd algoritmi grafning har qanday ikki uchi orasidagi eng qisqa yo'lni topish uchun algoritmdir.
To'lqin algoritmi-kenglikdagi qidiruvga asoslangan va ikki bosqichdan iborat:
to'lqinning tarqalishi va teskari harakat.Eng qisqa yo'l-bu ustundagi yo'l, ya'ni ikki
qo'shni tepalikda va uning uzunligi bilan bog'liq bo'lgan tepaliklar va qovurg'alar ketma-ketligi.
Graflarda eng qisqa yo'lni topishning eng samarali algoritmlari Dijkstra algoritmi,
Floyd algoritmi va Bulkhead algoritmlarini o'z ichiga oladi. Ushbu algoritmlar juda oz sonli vertikalar uchun samarali
137.Deykstra algoritimining murakkabligini baholang.
pic
138.Satrlarda qismiy satrlarni qidirish algoritmlari.
Rabin Karp algoritmi.
Boyer Mur algoritmi.
Primitiv Algoritmi.
Primitiv algoritmning muvaffaqiyatsizligi. Agar satrlar birdan
boshlab raqamlangan deb hisoblasak, eng oddiy “qo'pol kuch” (Brute
force) algoritmi (sodda algoritm) quyidagicha boʻladi:
for i=0...|haystack|-|needle|
for j=0...|needle|
if haystack[i+j + 1]<>needle[j]
then goto 1
output("Topildi: ", i+1)
1:
Eng oddiy qidirish algoritmi, eng yaxshisi, |haystack| - |needle| +1
taqqoslash; agar bir-biriga o'xshashliklar ko'p bo'lsa, tezlik
O(|haystack|·|needle|) ga tushadi.
Primitiv algoritm o'rtacha 2 soatlik taqqoslashda ishlayotgani
isbotlangan.
Bugungi kunda qismiy satrlarni qidirish algoritmlarining xilmaxilligi mavjud.
Dasturchi bunday omillarga qarab, mosini tanlashi kerak.
Rabin-Karp algoritmi. Rabin-Karp algoritmi-bu matnni xeshlash
yordamida berilgan satrdan ichki satrni qidiradigan qidirish algoritmi. U
1987-yilda Maykl Rabin va Richard Karp tomonidan ishlab chiqilgan.
Algoritm kamdan-kam hollarda bitta qismiy satrni topish uchun
ishlatiladi, lekin muhim nazariy ahamiyatga ega va bir xil uzunlikdagi
bir nechta qismiy satr uchun moslikni topishda juda samarali. n
uzunlikdagi matn va m uzunlikdagi qismiy satr uchun uning o'rtacha va
eng yaxshi bajarilish vaqti to'gʻri xesh funksiyasi bilan O (n) dir, lekin
eng yomon holatda uning samaradorligi O (nm) ga teng. Bu esa keng
qo'llanilmasligining sabablaridan biridir.
Rabin-Karp algoritmining eng oddiy amaliy qo'llanmalaridan biri
plagiatni aniqlashdir. Rabin-Karp algoritmi tekshirilgan maqoladagi
manba materiallardan ba'zi jumlalar paydo bo'lishining misollarini tezda
topishi mumkin. Algoritmning kichik farqlarga sezgirligini yo'q qilish
uchun siz ularni olib tashlash orqali harf yoki tinish belgi kabi
tafsilotlarni e'tiborsiz qoldirishingiz mumkin. Biz qidirayotgan qatorlar
soni juda katta bo'lgani uchun, bitta satrlarni topishning an'anaviy
algoritmlari samarasiz bo'lib qoladi.
Boyer-Mur algoritmi. 1977-yilda Robert Boyer va Jey Mur
tomonidan ishlab chiqilgan, matnda oldindan ishlov berish imkoniyati
bo'lmagan taqdirda, satrda qismiy satrni topish algoritmlari orasida eng
tezkori hisoblanadi.
Algoritm gʻoyasi quyidagicha:
- Chapdan o'ngga skanerlash, o'ngdan chapga taqqoslash.
- To'xtash belgisini topish
o agar taqqoslanadigan birinchi harf mos kelmasa, shablon eng
yaqiniga o'tkaziladi
o to'xtash belgisi bo'lmasa, shablon uning orqasiga siljiydi
- Mos keladigan qo'shimchani topish
o agar 1 yoki undan ortiq belgi mos kelsa, shablon bu
qo'shimchaning birinchi mos kelishiga qadar o'ngga siljiydi
139.Qismiy satrlarda izlashda primitiv algoritmining kamchiligi.
Primitiv algoritmning muvaffaqiyatsizligi. Agar satrlar birdan
boshlab raqamlangan deb hisoblasak, eng oddiy “qo'pol kuch” (Brute
force) algoritmi (sodda algoritm) quyidagicha boʻladi:
for i=0...|haystack|-|needle|
for j=0...|needle|
if haystack[i+j + 1]<>needle[j]
then goto 1
output("Topildi: ", i+1)
1:
Eng oddiy qidirish algoritmi, eng yaxshisi, |haystack| - |needle| +1
taqqoslash; agar bir-biriga o'xshashliklar ko'p bo'lsa, tezlik
O(|haystack|·|needle|) ga tushadi.
Primitiv algoritm o'rtacha 2 soatlik taqqoslashda ishlayotgani
isbotlangan.
Bugungi kunda qismiy satrlarni qidirish algoritmlarining xilmaxilligi mavjud. Dasturchi bunday omillarga qarab, mosini tanlashi kerak.
1. Optimallashtirish kerakmi yoki primitiv algoritm yetarlimi?
Jimlik boʻyicha, bu dasturlash tillarining standart kutubxonalari
amalga oshiradi.
2. Foydalanuvchining "dushmanligi". Boshqacha aytganda:
foydalanuvchi ataylab algoritm sekin bajariladigan
ma'lumotlarni aniqlaydimi? Eng oddiy holatda O (|haystack| · |
needle|) ball qo'yadigan juda oddiy algoritmlar mavjud, lekin
"muntazam" ma'lumotlarda solishtirishlar soni | haystack | dan
ancha kam. Faqat 1990-yillarda O (| haystack |) ning
murakkabligini, eng yomon holatda va | haystack | o'rtacha.
3. Tilning grammatikasi qidiruvni "o'rtacha" tezlashtiradigan ba'zi
evristikalarga dushman bo'lishi mumkin.
4. Protsessor arxitekturasi. Ba'zi protsessorlarda avtomatik
kattalashtirish yoki SIMD amallari mavjud bo'lib, ular sizga
188
ikkita operativ xotirani tez taqqoslashga imkon beradi (masalan,
x86-da rep cmpsd). Bunday protsessorlarda “needle”ni
“haystack” bilan taqqoslaydigan algoritmni qo'llash juda qiziq -
albatta, hamma pozitsiyalarda emas.
5. Alifbo o'lchami. Ko'p algoritmlar (ayniqsa, oxirigacha
taqqoslashga asoslangan), mos kelmaydigan belgi bilan bogʻliq
evristikaga ega. Katta alifbolarda ramzlar jadvali ko'p xotirani
egallaydi, kichik alifbolarda tegishli evristik samarasiz bo'ladi.
6. “haystack”ni indekslash qobiliyati. Agar mavjud bo'lsa,
qidiruv juda tezlashadi.
7. Bir vaqtning o'zida bir nechta satrlarni qidirish kerakmi? Ba'zi
algoritmlarning yon xususiyatlari (Axo-Korasik, ikkilik
algoritm) bunga imkon beradi.
Qoida tariqasida, matn tahrirlovchisida Boyer-Mur-Xorspul kabi
eng oddiy evristik algoritmni olish kifoya-hatto juda sekin kompyuter
ham bir soniya ichida qidirishni amalga oshira oladi. Agar matn hajmi
gigabaytda o'lchanadigan bo'lsa yoki qidiruv ko'plab so'rovlarni
bajaradigan serverda ishlayotgan bo'lsa, siz eng muvaffaqiyatli
algoritmni tanlashingiz kerak bo'ladi. Masalan, plagiatni aniqlash
dasturlari o'z ma'lumotlar bazasida saqlanadigan ko'plab hujjatlar orasida
qismiy satr qidirish algoritmlari yordamida onlayn tekshiruvlarni amalga
oshiradi.
140.Qismiy satrlarda qidirish algoritmlarining turlari.
Rabin-Karp algoritmi. Rabin-Karp algoritmi-bu matnni xeshlash
yordamida berilgan satrdan ichki satrni qidiradigan qidirish algoritmi. U
1987-yilda Maykl Rabin va Richard Karp tomonidan ishlab chiqilgan.
Algoritm kamdan-kam hollarda bitta qismiy satrni topish uchun
ishlatiladi, lekin muhim nazariy ahamiyatga ega va bir xil uzunlikdagi
bir nechta qismiy satr uchun moslikni topishda juda samarali. n
uzunlikdagi matn va m uzunlikdagi qismiy satr uchun uning o'rtacha va
eng yaxshi bajarilish vaqti to'gʻri xesh funksiyasi bilan O (n) dir, lekin
eng yomon holatda uning samaradorligi O (nm) ga teng. Bu esa keng
qo'llanilmasligining sabablaridan biridir.
141.Rabin Karp algoritmi
Rabin-Karp algoritmi. Rabin-Karp algoritmi-bu matnni xeshlash
yordamida berilgan satrdan ichki satrni qidiradigan qidirish algoritmi. U
1987-yilda Maykl Rabin va Richard Karp tomonidan ishlab chiqilgan.
Algoritm kamdan-kam hollarda bitta qismiy satrni topish uchun
ishlatiladi, lekin muhim nazariy ahamiyatga ega va bir xil uzunlikdagi
bir nechta qismiy satr uchun moslikni topishda juda samarali. n
uzunlikdagi matn va m uzunlikdagi qismiy satr uchun uning o'rtacha va
eng yaxshi bajarilish vaqti to'gʻri xesh funksiyasi bilan O (n) dir, lekin
eng yomon holatda uning samaradorligi O (nm) ga teng. Bu esa keng
qo'llanilmasligining sabablaridan biridir.
189
Rabin-Karp algoritmining eng oddiy amaliy qo'llanmalaridan biri
plagiatni aniqlashdir. Rabin-Karp algoritmi tekshirilgan maqoladagi
manba materiallardan ba'zi jumlalar paydo bo'lishining misollarini tezda
topishi mumkin. Algoritmning kichik farqlarga sezgirligini yo'q qilish
uchun siz ularni olib tashlash orqali harf yoki tinish belgi kabi
tafsilotlarni e'tiborsiz qoldirishingiz mumkin. Biz qidirayotgan qatorlar
soni juda katta bo'lgani uchun, bitta satrlarni topishning an'anaviy
algoritmlari samarasiz bo'lib qoladi.
Quyidagi misol orqali Rabin-Karp algoritmini koʻrib chiqamiz.
Berilgan matn S= “aevesapng”
Izlanadigan satr P= “esap”
0 1 2 3 4 5 6 7 8
a e v e s a p n g
0 1 2 3
e s a p
Quyida simvollar uchun xesh-kod keltirilgan:
a → 1
b → 2
c → 3
d → 4
e → 5
f → 6
… → …
z → 26
1-qadam. Belgilarga tayinlangan xesh kodi yordamida qismiy
satrning xesh kodi qiymatini topamiz.
0 1 2 3
e s a p
↓ ↓ ↓ ↓
5 19 1 16
Xesh-kod qiymati: 5+19+1+16=41
2-qadam. Agar m qismiy satr uzunligi bo'lsa, biz matn satrining
boshidan m uzunlikdagi qismiy satrni olishni boshlaymiz. Shundan
so'ng, qismiy satr uchun xesh-kod qiymatini topamiz va shablon
satrining xesh-kod qiymatiga mos kelishini tekshiramiz. Agar u mos
keladigan bo'lsa, belgini birma-bir tekshiradi, aks holda keyingi qismiy
satrga o'tadi.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
1 5 22 5
Xesh kod qiymati: 1+5+22+5 = 33
Xesh-kod qiymati mos kelmaydi, keyin biz m (4) uzunlikdagi
keyingi satrga o'tamiz.
3-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
5 22 5 19
Xesh kod qiymati: 5+22+5+19 = 51
Xesh-kod qiymati mos kelmaydi, keyin m uzunlikdagi keyingi
satrga o'tamiz.
4-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
22 5 19 1
Xesh kod qiymati: 22+5+19+1 = 47
Xesh-kod qiymati mos kelmaydi, keyin biz m uzunlikdagi keyingi
satrga o'tamiz.
5-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
5 19 1 16
Xesh kod qiymati: 5+19+1+16 = 41
Bu yerda xesh-kodining qiymati bir xil, shuning uchun biz ichki
qismiy belgilarini qidiriluvchi satr bilan birma -bir tekshiramiz.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
e s a p
Barcha belgilar mos keladi, keyin biz ichki satrning boshlangʻich
indeksini chop etamiz va iloji bo'lsa, m uzunlikdagi keyingi qismiy
satrga o'tamiz.
6-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
19 1 16 14
Xesh kod qiymati: 19+1+16+14 = 50
Joriy ichki satrning xesh qiymati qismiy satrning xesh qiymatiga
mos kelmaydi. Shunday qilib, iloji bo'lsa, m uzunligining keyingi ichki
satriga oʻtamiz, aks holda to'xtatamiz.
7-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
1 16 14 7
Xesh kod qiymati: 1+16+14 +7= 38
Bu yerda ham xesh kodi qiymati mos kelmaydi va bu m
uzunligining oxirgi ichki satri. Shunday qilib, bu yerda o'z jarayonimizni
to'xtatamiz.
Eslatma: Bu yerda xesh funksiyasini yaratish yoki aniqlashning
turli usullari mavjud. Yaxshi tushunish uchun oddiy xesh funksiyasidan
foydalanildi.
Rabin-Karp algoritmi (C++)
#include
using namespace std;
void rabin_karp(string &text,string &pattern, int q)
{
/*qismiy satr uzunligi*/
int m = pattern.length();
/*Berilgan satr uzunligi*/
int n = text.length();
int p=0,t=0,h=1,d=26; // bu yerda p - matn uchun xesh qiymati, t – qismiy
satrning xesh qiymati;
/*h=pow(d,M-1) bu yerda d - 26, agar matnda faqat katta harflar bo'lsa.*/
for(int i=0;i{
h=(h*d)%q;
}
/* matn va m uzunligining birinchi ichki satri uchun xesh qiymatini hisoblash
*/
for(int i=0;i{
p=(d*p+pattern[i])%q;;
t=(d*t+text[i])%q;
}
/* m uzunlikdagi qolgan satr uchun */
for(int i=0;i<=n-m;i++)
{
194
/* agar xesh qiymatlari bir xil bo'lsa, xeshni ichki satr va qismiy satridagi
belgilar bo'yicha tekshirish */
if(p==t)
{
int flag=0;
for(int j=0;j{
if(text[i+j]!=pattern[j])
{
flag=1;
break;
}
}
/* agar barcha belgilar mos keladigan bo'lsa, ichki satrning boshlangʻich
indeksini chop etish.*/
if(flag==0)
{
cout<<" Indeksda berilgan satr osti topildi:"<}
}
/*oldingi ichki satrdan birinchi belgini olib tashlash orqali keyingi ichki
satrning xesh qiymatini toping va keyingi satrni oldingi satr oxiriga qo'shing*/
/*xesh qiymatlarini topish uchun O (1) vaqt kerak bo'ladi*/
if(i{
t=(d*(t-text[i]*h)+text[i+m])%q;
if(t<0)
{
t=(t+q);
}
}
}
}
int main()
{
/*oʻzgaruvchilarni kiritish*/
string text;
cin>>text;
string pattern;
cin>>pattern;
rabin_karp(text,pattern,97);
return 0;
}
142.Boyer Mur Algoritmi
Boyer-Mur algoritmi. 1977-yilda Robert Boyer va Jey Mur
tomonidan ishlab chiqilgan, matnda oldindan ishlov berish imkoniyati
bo'lmagan taqdirda, satrda qismiy satrni topish algoritmlari orasida eng
tezkori hisoblanadi.
Algoritm gʻoyasi quyidagicha:
- Chapdan o'ngga skanerlash, o'ngdan chapga taqqoslash.
- To'xtash belgisini topish
o agar taqqoslanadigan birinchi harf mos kelmasa, shablon eng
yaqiniga o'tkaziladi
o to'xtash belgisi bo'lmasa, shablon uning orqasiga siljiydi
- Mos keladigan qo'shimchani topish
o agar 1 yoki undan ortiq belgi mos kelsa, shablon bu
qo'shimchaning birinchi mos kelishiga qadar o'ngga siljiydi
1. q w t e e q e w q r w q w r q r
q w r q r
2. q w t e e q e r q r w q w r q r
q w r q r
3. q w t e e q e w q r w q w r q r
q w r q r
4. q w t e e q e w q r w q w r q r
q w r q r
To'xtatish belgisi jadvali. Qismiy satrdagi elementning oxirgi o'rnini
belgilaydi (oxirgi harfdan tashqari). Agar qismiy satrda element
bo'lmasa, jadvalga 0 kiritiladi (bittadan raqamlash uchun)
Misol. Qismiy satr: qwrqr
Simvol q w r e t
Oxirgi pozitsiya 4 2 3 0 0
1. q t e e q r w q w r e e
q w r q r
2. q t e e q r w q w r e e
q w r q r
Suffiks jadvali. Mumkin bo'lgan barcha qo'shimchalar uchun
jadvalda qismiy satrni o'zgartirish kerak bo'lgan eng kichik miqdor
ko'rsatilgan, u yana qo'shimchaga mos keladi. Agar bunday siljishning
iloji bo'lmasa, satrning uzunligi ko'rsatilgan.
Misol. Qismiy satr: qwrqr
Suffiks Boʻsh r qr rqr wrqr qwrqr
qadam 1 2 5 5 5 5
1. q t e e q r w q w r e e
q w r q r
2. q t e e q r w q w r e e
q w r q r
3. q t e e q r w q w r e e
q w r q r
4. q t e e q r w q w r e e
q w r q r
143.Boyer Mur algoritmining murakkabligini baholang.
Algoritmning murakkabligi. O (| haystack | + | needle | + | Σ |)
davriy bo'lmagan qismiy satrlar bo'yicha
O (| haystack | · | needle | + | Σ |) davriy
haystack - berilgan satr, needle – qismiy satr, Σ - solishtirish uchun
alifbo
1991-yilda Koul shuni ko'rsatdiki, davriy bo'lmagan sxemalar
bo'yicha, algoritm satr bo'ylab to'liq o'tishda 3·|haystack| tadan ko'p
bo'lmagan taqqoslashni amalga oshiradi.
Boyer-Mura algoritmi (C++)
#include
using namespace std;
# define NO_OF_CHARS 256
void badCharHeuristic( string str, int size, int badchar[NO_OF_CHARS])
{
int i;
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
int s = 0;
while(s <= (n - m))
{
int j = m - 1;
while(j >= 0 && pat[j] == txt[s + j])
j--;
if (j < 0)
{
cout << s << endl;
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
s += max(1, j - badchar[txt[s + j]]);
}
198
}
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
144.qismiy satrlarn iizlash algoritmlarini foydalanish samaradorligigini taqqoslang.
145.Suffiks jadvali
Suffiks jadvali. Mumkin bo'lgan barcha qo'shimchalar uchun
jadvalda qismiy satrni o'zgartirish kerak bo'lgan eng kichik miqdor
ko'rsatilgan, u yana qo'shimchaga mos keladi. Agar bunday siljishning
iloji bo'lmasa, satrning uzunligi ko'rsatilgan.
Misol. Qismiy satr: qwrqr
Suffiks Boʻsh r qr rqr wrqr qwrqr
qadam 1 2 5 5 5 5
1. q t e e q r w q w r e e
q w r q r
2. q t e e q r w q w r e e
q w r q r
3. q t e e q r w q w r e e
q w r q r
4. q t e e q r w q w r e e
q w r q r
146.Robin Karp va Boyer Mura algoritmlarini taqqoslang.
shu ikkita algoritmni urganim murakkabligini baholab keyin taqqosla
147.Satrlar uchun xesh funklsiyasini qo'llang.
Berilgan matn S= “aevesapng”
Izlanadigan satr P= “esap”
0 1 2 3 4 5 6 7 8
a e v e s a p n g
0 1 2 3
e s a p
Quyida simvollar uchun xesh-kod keltirilgan:
a → 1
b → 2
c → 3
d → 4
e → 5
f → 6
… → …
z → 26
1-qadam. Belgilarga tayinlangan xesh kodi yordamida qismiy
satrning xesh kodi qiymatini topamiz.
0 1 2 3
e s a p
↓ ↓ ↓ ↓
5 19 1 16
Xesh-kod qiymati: 5+19+1+16=41
2-qadam. Agar m qismiy satr uzunligi bo'lsa, biz matn satrining
boshidan m uzunlikdagi qismiy satrni olishni boshlaymiz. Shundan
so'ng, qismiy satr uchun xesh-kod qiymatini topamiz va shablon
satrining xesh-kod qiymatiga mos kelishini tekshiramiz. Agar u mos
keladigan bo'lsa, belgini birma-bir tekshiradi, aks holda keyingi qismiy
satrga o'tadi.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
1 5 22 5
Xesh kod qiymati: 1+5+22+5 = 33
Xesh-kod qiymati mos kelmaydi, keyin biz m (4) uzunlikdagi
keyingi satrga o'tamiz.
3-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
5 22 5 19
Xesh kod qiymati: 5+22+5+19 = 51
Xesh-kod qiymati mos kelmaydi, keyin m uzunlikdagi keyingi
satrga o'tamiz.
4-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
22 5 19 1
Xesh kod qiymati: 22+5+19+1 = 47
Xesh-kod qiymati mos kelmaydi, keyin biz m uzunlikdagi keyingi
satrga o'tamiz.
5-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
5 19 1 16
Xesh kod qiymati: 5+19+1+16 = 41
Bu yerda xesh-kodining qiymati bir xil, shuning uchun biz ichki
qismiy belgilarini qidiriluvchi satr bilan birma -bir tekshiramiz.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
e s a p
Barcha belgilar mos keladi, keyin biz ichki satrning boshlangʻich
indeksini chop etamiz va iloji bo'lsa, m uzunlikdagi keyingi qismiy
satrga o'tamiz.
6-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
19 1 16 14
Xesh kod qiymati: 19+1+16+14 = 50
Joriy ichki satrning xesh qiymati qismiy satrning xesh qiymatiga
mos kelmaydi. Shunday qilib, iloji bo'lsa, m uzunligining keyingi ichki
satriga oʻtamiz, aks holda to'xtatamiz.
7-qadam.
0 1 2 3 4 5 6 7 8
a e v e s a p n g
↓ ↓ ↓ ↓
1 16 14 7
Xesh kod qiymati: 1+16+14 +7= 38
Bu yerda ham xesh kodi qiymati mos kelmaydi va bu m
uzunligining oxirgi ichki satri. Shunday qilib, bu yerda o'z jarayonimizni
to'xtatamiz.
148.Tekislikda chiziqlar kesishgan sohalarni qidirish algoritimi(Sweep Line).
Tekislikda chiziqlar kesishgan sohalarni qidirish
algoritmi(Sweep Line) - bu Yevklid fazosidagi turli xil muammolarni
hal qilish uchun kesishgan sohalardan foydalanadigan algoritmik
paradigma. Bu hisoblash geometriyasidagi asosiy texnikalardan biridir.
158
Ushbu turdagi algoritmlarning gʻoyasi ba'zi bir nuqtalarda to'xtab,
tekislik bo'ylab harakatlanadigan xayoliy to'gʻri chiziqni (ko'pincha
vertikal) tasavvur qilishdir. Geometrik amallar, kesishgan chiziqqa
qo'shni bo'lgan geometrik obyektlar bilan cheklanadi va chiziq barcha
obyektlardan o'tib ketganda to'liq yechim mavjud boʻladi.
Sweep Line – bu tekislik bo'ylab to'gʻri yo'nalishda siljigan
xayoliy vertikal chiziq. Shuning uchun bu konsepsiyaga asoslangan
algoritmlarni ba'zan tekisliklarni tozalash algoritmlari deb ham
atashadi. Chiziqni diskretlashtirish uchun biz ba'zi hodisalarga asoslanib
tozalaymiz.
Yana shuni ta'kidlash kerakki, bu texnikaning samaradorligi biz
foydalanadigan ma'lumotlar tuzilmalariga bogʻliq. Umuman olganda, biz
C++ da setdan foydalanishimiz mumkin, lekin ba'zida biz qo'shimcha
ma'lumotlarni saqlashni talab qilamiz, shuning uchun biz
muvozanatlashgan ikkilik daraxtga o'tamiz.
149.#include
C++ dasturlash tilida xesh jadvallarni hosil qilish uchun map
konteyneri aniqlangan. map konteyner vector, list, deque kabi boshqa
konteynerlarga juda o'xshaydi, lekin ozgina farqi mavjud. Bu
konteynerga birdaniga ikkita qiymat qo'yish mumkin. Shunday qilib, bu
map misolni batafsil ko'rib chiqaylik:
#include
#include
|
