Sazerlend-Koena algoritmi: Kesishma algoritmlarini tahlil qilish
![Kesishma algoritmlari quyidagi asosiy vazifalarni bajaradi:
1. Ikki tartiblangan massivning kesishmasini topish.
2. Ko‘p to‘plamlarning kesishmasini topish.
3. Dinamik to‘plamlarning kesishmasini hisoblash.
4. Qisman mos kelishlarga asoslangan kesishma.
Kesishma algoritmlari turlari
Oddiy chiziqli qidiruv algoritmlari
Eng oddiy usul – har bir elementni boshqa to‘plamda chiziqli qidirish.
def linear_intersection(A, B):
result = []
for a in A:
for b in B:
if a == b:
result.append(a)
break
return result
Murakkablik: O(n*m) vaqt, O(min(n,m)) xotira.
Ikkilik qidirishga asoslangan algoritmlar
Tartiblangan massivlar uchun samarali usul:
def binary_search_intersection(A, B):
result = []
for a in A:
10](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_10.png?v=1)
![if binary_search(B, a):
result.append(a)
return result
Murakkablik: O(n log m) vaqt, O(min(n,m)) xotira.
Hash-jadvallardan foydalanish
Eng samarali usullardan biri:
def hash_intersection(A, B):
hash_set = set(A)
result = []
for b in B:
if b in hash_set:
result.append(b)
return result
Murakkablik: O(n + m) vaqt, O(n) xotira.
Ikki ko‘rsatgich usuli
Tartiblangan massivlar uchun optimal usul:
python
def two_pointer_intersection ( A , B ):
i , j = 0 , 0
result = []
while i < len ( A ) and j < len ( B ):
if A [ i ] < B [ j ]:
i += 1
elif A [ i ] > B [ j ]:
j += 1
11](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_11.png?v=1)
![else :
result . append ( A [ i ])
i += 1
j += 1
return result
Murakkablik: O(n + m) vaqt, O(min(n,m)) xotira.
Ko‘p to‘plamlarning kesishmasi
k ta to‘plamning kesishmasini topish uchun quyidagi usullar qo‘llaniladi:
1. Qadamma-qadam kesishma:
python
def multi_set_intersection ( sets ):
if not sets :
return []
result = sets [ 0 ]
for s in sets [ 1 :]:
result = intersection ( result , s )
return result
2. Kichik to‘plamdan boshlash usuli:
python
def smart_multi_intersection ( sets ):
# To'plamlarni hajmi bo'yicha tartiblash
sorted_sets = sorted ( sets , key = len )
result = sorted_sets [ 0 ]
for s in sorted_sets [ 1 :]:
result = intersection ( result , s )
if not result :
break
return result
Maxsus holatlar
Intervallar kesishmasi
python
def interval_intersection ( A , B ):
# A va B - [(start, end), ...] ko'rinishidagi intervallar
12](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_12.png?v=1)
![i , j = 0 , 0
result = []
while i < len ( A ) and j < len ( B ):
a_start , a_end = A [ i ]
b_start , b_end = B [ j ]
# Kesishmani hisoblash
start = max ( a_start , b_start )
end = min ( a_end , b_end )
if start <= end :
result . append (( start , end ))
# Keyingi intervalga o'tish
if a_end < b_end :
i += 1
else :
j += 1
return result
Ko'p o'lchovli kesishma
python
def multi_dim_intersection ( A , B ):
# Har bir o'lchov bo'yicha alohida kesishma
result = []
for point_a in A :
for point_b in B :
if all ( a == b for a , b in zip ( point_a , point_b )):
result . append ( point_a )
break
return result
ALGORITMLARNI QIYOSIY TAHLILI
13](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_13.png?v=1)
![o Ma'lumotlar tuzilishi
o Vaqt cheklovlari
o Xotira resurslari
o Natijaning aniqlik darajasi
EKSPERIMENTAL TADQIQOT . Tadqiqot metodologiyasi
Dasturiy ta'minot. Tadqiqot uchun quyidagi dasturiy vositalar ishlatildi:
Python 3.9 (asosiy dasturlash tili)
NumPy (ma'lumotlar generatsiyasi)
Matplotlib (grafiklar chizish)
Timeit (vaqt o'lchovlari)
Memory-profiler (xotira iste'moli)
Ma'lumotlar generatsiyasi
Tajribalar uchun turli xususiyatdagi ma'lumotlar yaratildi:
python
import numpy as np
import random
def generate_sorted_data ( n ):
"""Tartiblangan ma'lumotlar yaratish"""
data = sorted ([ random . randint ( 1 , 10 * n ) for _ in range ( n )])
return data
def generate_random_data ( n ):
"""Tasodifiy ma'lumotlar yaratish"""
data = [ random . randint ( 1 , 10 * n ) for _ in range ( n )]
return data
def generate_unique_data ( n ):
"""O'ziga xos elementlardan iborat ma'lumotlar"""
17](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_17.png?v=1)
![data = random . sample ( range ( 10 * n ), n )
return data
Kesishma algoritmlari tajribasi
Vaqt o'lchovlari
Har bir algoritm uchun turli hajmdagi ma'lumotlar bilan o'lchovlar olindi:
python
import time
def measure_time ( algorithm , A , B , iterations = 100 ):
"""Algoritm ishlash vaqtini o'lchash"""
times = []
for _ in range ( iterations ):
start = time . perf_counter ()
algorithm ( A , B )
end = time . perf_counter ()
times . append ( end - start )
return np . mean ( times ), np . std ( times )
Natijalar grafiklari
Tajriba natijalari grafik shaklida taqdim etildi:
1. Vaqt murakkabligi grafigi: Algoritmlarning ma'lumotlar hajmiga
bog'liqligi
2. Xotira iste'moli grafigi: Algoritmlarning xotira talabi
3. Samaradorlik grafigi: Turli sharoitlarda algoritmlarning o'zaro
taqqoslanishi
Sazerlend-Koena algoritmi tajribasi
SAT masalalarini generatsiya qilish
python
def generate_sat_problem ( n_vars , n_clauses ):
"""Tasodifiy SAT masalasi yaratish"""
problem = []
for _ in range ( n_clauses ):
clause = []
18](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_18.png?v=1)
![# Har bir klauzada 3 ta literal
for _ in range ( 3 ):
var = random . randint ( 1 , n_vars )
negated = random . choice ([ True , False ])
clause . append (( - var if negated else var ))
problem . append ( clause )
return problem
Algoritm implementatsiyasi
python
class CookLevinSolver :
def __init__ ( self , n_states , n_symbols ):
self . n_states = n_states
self . n_symbols = n_symbols
def reduce_to_sat ( self , turing_machine , input_string , steps ):
"""Turing mashinasini SAT masalasiga o'tkazish"""
n = len ( input_string )
p = steps
# O'zgaruvchilarni yaratish
variables = {}
var_count = 0
# T(i,j,t) - t vaqtda i katakda j belgi
for i in range ( p + 1 ):
for j in range ( self . n_symbols ):
for t in range ( p + 1 ):
variables [ f'T_ { i } _ { j } _ { t } ' ] = var_count
var_count += 1
# Formulani yaratish
clauses = []
# 1. Har bir katakda har bir vaqtda faqat bitta belgi
for i in range ( p + 1 ):
for t in range ( p + 1 ):
for j1 in range ( self . n_symbols ):
for j2 in range ( self . n_symbols ):
if j1 != j2 :
clause = [
19](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_19.png?v=1)
![- variables [ f'T_ { i } _ { j1 } _ { t } ' ],
- variables [ f'T_ { i } _ { j2 } _ { t } ' ]
]
clauses . append ( clause )
# 2. Kirish ma'lumotini kodlash
for i , symbol in enumerate ( input_string ):
clauses . append ([ variables [ f'T_ { i } _ { symbol } _ { 0 } ' ]])
# ... qolgan shartlar
return clauses , variables
Natijalar tahlili
Kesishma algoritmlari natijalari
Tajribalar shuni ko'rsatdiki:
1. Kichik ma'lumotlar uchun (n < 1000): Barcha algoritmlar taxminan bir xil
tezlikda ishlaydi.
2. O'rta hajmdagi ma'lumotlar (1000 < n < 100000): Hash usuli eng tezkor,
ikki ko'rsatgich usuli esa eng kam xotira talab qiladi.
3. Katta ma'lumotlar (n > 100000): Faqat hash va ikki ko'rsatgich usullari
amaliy hisoblanadi.
Sazerlend-Koena algoritmi natijalari
1. Kichik masalalar (n < 20): Algoritm qoniqarli tezlikda ishlaydi.
2. O'rta masalalar (20 < n < 40): Vaqt sezilarli darajada oshadi.
3. Katta masalalar (n > 40): Amaliy foydalanish mumkin emas.
SAZERLEND-KOENA ALGORITMINING ZAMONAVIY
MODIFIKATSIYALARI
Parallel Sazerlend-Koena algoritmi
Parallel hisoblash texnologiyalari rivojlanishi bilan Sazerlend-Koena algoritmini
parallel versiyalari ishlab chiqildi:
python
20](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_20.png?v=1)
![class ParallelCookLevin :
def __init__ ( self , num_processors ):
self . num_processors = num_processors
def parallel_reduction ( self , problem , input_data ):
"""Parallel kamaytirish algoritmi"""
import multiprocessing as mp
# Vazifalarni bo'lish
chunks = self . split_problem ( problem )
# Parallel ishlash
with mp . Pool ( self . num_processors ) as pool :
results = pool . map ( self . solve_chunk , chunks )
# Natijalarni birlashtirish
return self . combine_results ( results )
def split_problem ( self , problem ):
"""Masalani qismlarga bo'lish"""
n = len ( problem )
chunk_size = n // self . num_processors
return [ problem [ i : i + chunk_size ]
for i in range ( 0 , n , chunk_size )]
Afzalliklari:
Tezlikni oshirish: O(n³/p) gacha, bu yerda p - protsessorlar soni
Katta masalalarni yechish imkoniyati
Resurslardan samarali foydalanish
Kamchiliklari:
Kommunikatsiya xarajatlari
Muvozanatlash muammolari
Maxsus apparat talabi
Kvant Sazerlend-Koena algoritmi
21](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_21.png?v=1)
![Kvant hisoblashda Sazerlend-Koena algoritmini kvant versiyasi:
python
# Kvant sxemasi namoyishi
def quantum_cook_levin ( turing_machine , input_str ):
"""
Kvant versiyasi - Grover algoritmi bilan birlashtirilgan
"""
# Kvant registrlarni yaratish
n = len ( input_str )
qc = QuantumCircuit ( 3 * n + 2 )
# Superpozitsiya holatini yaratish
for i in range ( n ):
qc . h ( i )
# Oracle funktsiyasi (SAT formulasi)
qc . append ( sat_oracle , range ( n ))
# Grover diffuser
qc . append ( grover_diffuser ( n ), range ( n ))
# O'lchash
qc . measure_all ()
return qc
def sat_oracle ( circuit , qubits ):
"""SAT formulasi uchun kvant orakuli"""
# 3-SAT uchun kvant sxemasi
# Har bir klauza uchun Toffoli darvozasi
for clause in get_clauses ():
control_qubits = []
for var in clause :
if var < 0 :
circuit . x ( abs ( var ) - 1 )
control_qubits . append ( abs ( var ) - 1 )
else :
control_qubits . append ( var - 1 )
22](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_22.png?v=1)
![current = neighbor
return None
2. Genetik algoritm yondashuvi:
python
class GeneticSATSolver :
def __init__ ( self , population_size = 100 ):
self . population_size = population_size
def solve ( self , formula , generations = 1000 ):
# Boshlang'ich populyatsiya
population = [ random_assignment ( formula . n_vars )
for _ in range ( self . population_size )]
for gen in range ( generations ):
# Baholash
fitness = [ self . evaluate_fitness ( ind , formula )
for ind in population ]
# Selektsiya
selected = self . tournament_selection ( population , fitness )
# Krossover
offspring = self . crossover ( selected )
# Mutatsiya
offspring = [ self . mutate ( ind ) for ind in offspring ]
# Yangi populyatsiya
population = self . replacement ( population , offspring )
# Yechimni tekshirish
best = max ( population , key = lambda x : self . evaluate_fitness ( x , formula ))
if self . evaluate_fitness ( best , formula ) == 1.0 :
return best
return None
24](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_24.png?v=1)
![KESISHMA ALGORITMLARINING ILG‘OR USULLARI
Bloom filtrlari bilan kesishma
Bloom filtri - ehtimoliy ma'lumotlar strukturasi bo'lib, kesishma hisobini
optimallashtiradi:
python
class BloomFilterIntersection :
def __init__ ( self , size , hash_functions ):
self . size = size
self . hash_functions = hash_functions
self . bit_array = [ 0 ] * size
def add ( self , element ):
"""Elementni filterga qo'shish"""
for hash_func in self . hash_functions :
index = hash_func ( element ) % self . size
self . bit_array [ index ] = 1
def contains ( self , element ):
"""Element borligini tekshirish"""
for hash_func in self . hash_functions :
index = hash_func ( element ) % self . size
if self . bit_array [ index ] == 0 :
return False
return True
def bloom_intersection ( self , set_a , set_b ):
"""Bloom filter yordamida kesishma"""
# Set A uchun bloom filter yaratish
bloom = BloomFilterIntersection ( self . size , self . hash_functions )
for item in set_a :
bloom . add ( item )
# Set B dan filtr orqali o'tkazish
result = []
for item in set_b :
if bloom . contains ( item ):
# False positive ehtimolini kamaytirish
25](https://docx.uz/documents/fb5a56af-ba2b-4d19-b088-3ea0816cab91/page_25.png?v=1)
Sazerlend-Koena algoritmi: Kesishma algoritmlarini tahlil qilish