O‘zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Yakuniy nazorat ishi

Variant № 9

1. 
   Chiziqli qidirish algoritmining tahlili.
   
2. 
   Ketma-ket qidiruv va indeksli ketma-ket qidiruvlarning qaysi biri samaraliroq va nima sababdan?
   
3. 
   NP bilan bogʼliq muammolarni xal qilish yoʼllari.
   

Bajardi: Donayev Islom.

Tekshirdi:Eshmuhammedov Aziz.

Guruh:CAO021

TOSHKENT-2020

1.Chiziqli qidirish algoritmining tahlili.

Chiziqli qidiruv – bunda berilgan kalit chiziqli ketma ketlikda to’plam elementlari orasidan qidirib chiqiladi. Bu algoritm ancha sodda lekin sekin hisoblanadi.


Intervalli qidirish: Ushbu algoritmlar maxsus ajratilgan ma'lumotlar tuzilmalarida qidirish uchun mo'ljallangan. Ushbu turdagi qidiruv algoritmlari Linear Search-ga qaraganda ancha samaralidir, chunki ular qayta-qayta qidiruv tuzilmasi markaziga yo’naladi va qidiruv maydonini ikkiga bo’ladi. Masalan: Ikkilik qidiruv.

Chiziqli qidirish algoritmi qanday ishlaydi

Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga ham oson.Arrayning birinchi elementidan tekshirish boshlanadi.Element olinadi va u berilgan shartga tekshirib ko’riladi.Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki shunchaki true) qaytariladi va algoritm tugaydi.Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladiArray tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1 yoki false…)

Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.

Algoritm murakkabligi

Chiziqli qidirish algoritmining vaqt bo’yicha murakkabligi uning nomidan ham ma’lum, ya’ni chiziqli O(n). Ya’ni, eng yomon holat sifatida element array bo’lmagan holat qaraladi va bunda algoritm maksimum n ta qadam ish bajarishi kerak bo’ladi.

Xotira jihatidan, algoritm ortiqcha joy talab qilmaydi.

Chiziqli qidirish algoritmi ko’pincha real hayotdagi holatlar uchun ancha sekinlik qiladi. Shuning uchun ham bunday holatlarda undan boshqa tezroq ishlaydigan algoritmlar qo’llanilishi kerak bo’ladi (masalan, ikkilik qidirish). Lekin, bu algoritmning ham ikkilik qidirishdan o’ziga yarasha avfzal tomonlari mavjud. Bunga ikkilik qidirish (binary search)

2. Qidirish jarayoni

Chiziqili qidirish algoritmi elementni array boshidan tartib bilan qidiradi. Ikkilik qidirish algoritmida esa bu jarayon array o’rtasidan boshlanib turlicha davom etishi mumkin. Dasturlashda bu jarayon tasodifiy elementga murojaat (random access) deb ataladi. Bu narsa qidirish algoritmi ish bajarayotgan ma’lumot tuzilmasi uchun muhim. Chunki ba’zi tuzilmalarda tasodifiy elementga birdan murojaat qilishning iloji yo’q. Masalan, stack, queue, linked list va h.k.

3. Solishtirish

Elementni qidirishda solishtirish jarayoni ham ikki xil bo’ladi. Chiziqli qidirish algoritmi faqat tenglikka asoslanadi. Ikkilik qidirish esa tenglik, katta yoki kichiklikka qarab, o’z ishini davom ettiradi.

4. Vaqt bo’yicha murakkablik

Ikkita bir xil vazifani bajaruvchi algoritmlarni solishtirayotgan paytda ularning ishlash tezligini solishtirib ko’rmasdan iloj yo’q albatta. Demak,

Chiziqli qidirish ishlash tezligi:

Eng yaxshi holatda: O(1)

O’rtacha holatda: n(n+1)/2n = O(n)

Eng yomon holatda: O(n)

Ikkilik qidirish ishlash tezligi:

Eng yaxshi holatda: O(1)

O’rtacha holatda: logn(logn+1)/2logn = O(logn)

Eng yomon holatda: O(logn)

Shunday qilib yuqorida sanab o’tganlarimiz chiziqli qidirish va ikkilik qidirish algoritmlari farqlari va umumiy jihatlari edi.

2.Ketma-ket qidiruv va indeksli ketma-ket qidiruvlarning qaysi biri samaraliroq va nima sababdan?

Мазкур кўринишдаги қидирув агар маълумотлар тартибсиз ёки улар тузилиши ноаниқ бўлганда қўлланилади. Бунда маълумотлар бутун жадвал бўйича оператив хотирада кичик адресдан бошлаб, то катта адресгача кетма-кет қараб чиқилади.

Массивда кетма-кет қидирув (search ўзгарувчи топилган элемент рақамини сақлайди).

Algoritm quyidagicha

Kiritish massiv a va key

For i=0,1,…,n

if (a[i]==key) operatorlar; chiqish;

For ni yopish

Tugatish

Массивда кетма-кет қидирув алгоритми самарадорлигини бажарилган таққослашлар сони М билан аниқлаш мумкин. М_min = 1, M_max = n. Агар маълумотлар массив ячейкасида бир ҳил эхтимоллик билан тақсимланган бўлса, у ҳолда М_ср » (n + 1)/2 бўлади.

Агар керакли элемент жадвалда бўлмаса ва мазкур элементни жадвалга қўшиш лозим бўлса, у ҳолда юқоридаги дастурдаги охирги иккита оператор қуйидагига алмаштирилади.

Агар маълумотлар жадвали бир боғламли рўйхат кўринишида берилган бўлса, у ҳолда кетма-кет қидирув рўйхатда амалга оширилади.

Рўйхатли тузилманинг афзаллиги шундан иборатки, рўйхатга элементни қўшиш ёки ўчириш тез амалга ошади, бунда қўшиш ёки ўчириш элемент сонига боғлиқ бўлмайди, массивда эса элементни қўшиш ёки ўчириш тахминан барча элементларни яримини силжитишни талаб қилади. Рўйхатда қидирувни самарадорлиги тахминан массивники билан бир ҳил бўлади.

Умуман олганда кетма-кет қидирув самарадорлигини ошириш мумкин.

Фараз қилайлик, кун давомида маълумотлар йиғилиб, кечқурун улар қайта ишлансин. Маълумотлар тўплангандан кейин улар сараланади

Фараз қилайлик, ўсиш тартибида тартибланган сонлар массиви берилган бўлсин. Ушбу усулни асосий ғояси шундан иборатки, тасодифий қандайдир A_M элемент олинади ва у Х қидирув аргументи билан таққосланади. АгарA_M=Х бўлса, у ҳолда қидирув якунланади; агар A_M M >X бўлса.

М ихтиёрий танланганда ҳам таклиф қилинаётган алгоритм коррект ишлайди. Шу сабабали М ни шундай танлаш лозимки, тадқиқ қилинаётган алгоритм самаралироқ натижа берсин, яъни уни шундай танлайликки, иложи борича келгуси жараёнларда иштирок этувчи элементлар сони кам бўлсин. Агар биз ўртача элементни, яъни массив ўртасини танласак ечим мукаммал бўлади.

Қуйидаги чизма кўринишида берилган массивни қараб чиқайлик. Фараз қилайлик, биздан калити 52 га тенг бўлган элементни топиш талаб қилинсин. Дастлабки таққосланадиган элемент 49 бўлади. 49<52 бўлгани учун сабабли, кейинги қидирув 49 дан юқорида турган элементлар орасида амалга оширилади. Янги хосил бўлган массив ўртаси 86. Агар берилган калит билан ушбу калитни таққосласак 86>52 бўлади. Демак, навбатдаги қидирувлар 86 билан 49 орасидаги элементлар ичида амалга оширилиши лозим. Кейинги қадамда маълум бўлдики, қаралаётган элементлар ўртасидаги элемент калити 52 га тенг. Шундай қилиб, массивда берилган калитга тенг бўлган элементни топдик.



Чизиқли қидирув самарадорлиги: M=1÷n, Мўртача = (n + 1)/2=O(n)

Массив ва боғланган рўйхатда керакли элементни бор ёки йўқлигини аниқлаш самарадорлиги бир хил, аммо топилган элементни ўчириш ёки бундай элемент жадвалда бўлмаса, уни жадвалга қўйиш талаб қилинган бўлса, у ҳолда қидирувни амалга ошириш рўйхатда самаралироқ бўлади.

Бинар қидирув самарадорлиги: С = O(log₂n).

Saralash самарадорлиги mezonlari:

саралашга кетган вақт T(n)=C(n)+M(n), бунда C(n) - таққослашлар сони;

M(n)-эса ўринлаштиришлар сони);

T дастурни ишлаб чиқишга кетган вақт;

талаб қилинадиган хотира хажми.

Саралашга кетган вақт учун қуйидаги ўринли бўлади:

O(nlogn)  T(n)  O(n²);

T(n)=O(n) – идеал ҳолатда.

3.NP bilan bogʼliq muammolarni xal qilish yoʼllari.

Taxminiy echimni qidirish (masalan, sayohat qiluvchi sotuvchi, xalta bilan bog'liq muammolarni hal qilishda ochko'z algoritmlardan foydalanish);

2. "Aqlli" qidiruv strategiyasini tashkil qilish (masalan, filial va bog'langan usul);

3. N P-to'liq muammolarni bir-birlariga kamaytirish (masalan, sayohat qiluvchi sotuvchi muammosini chiziqli dasturlash muammosiga qadar kamaytirish);

4. Samarali hal qilinadigan maxsus ishlarning NP-to'liq muammosidan ajratish.

Vaqtinchalik hisob-kitoblarni e'tiborsiz qoldirish mumkin.

• Agar yaratilgan dastur bir necha bor ishlatilsa, dasturni yozish va disk raskadrovka qilish qiymati ushbu dasturning umumiy qiymatidan oshib ketadi.

• Agar dastur faqat "kichik" kirish ma'lumotlari bilan ishlasa, unda ish vaqtining ko'payishi darajasi ish vaqti formulasida mavjud bo'lgan doimiydan kamroq ahamiyatga ega bo'ladi.

Agar tayyor dasturlar ularni tushunishga qodir bo'lmagan odamlar tomonidan qo'llab-quvvatlansa, samarali, ammo murakkab algoritmlar kerak bo'lmasligi mumkin.

• Samarali algoritmlar shu qadar katta hajmdagi kompyuter xotirasini talab qiladigan bir nechta misollar mavjudki, bu omil ularning afzalliklarini inkor etadi.

Raqamli algoritmlarda aniqlik va barqarorlik vaqtinchalik samaradorligidan kam emas.

Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:

1. U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.

2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.

Odatda yahshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlaydigan va barcha test topshiriqlariga javob beradigan algoritmni tuzdik, lekin uning to’g’riligini isbotlab bilmaymiz. Shunday isbot berilmaguncha, algoritm evristik deb tushuniladi.

Evristika (boshqa yunon tilidan: εὑρίσκω - "qidiraman", "kashf qilaman") - bu bilim sohasi, ijodiy faoliyatning o'ziga xos xususiyatlarini o'rganadigan ilmiy soha. Evristika deganda kognitiv, konstruktiv, amaliy masalalarni hal qilishni osonlashtiradigan sodda usullar va uslublarning umumlashgan majmuasi tushuniladi.

Evristik algoritm (evristik) - bu masalani hal qilish algoritmi, shu jumladan aniq yoki optimal bo'lishi kafolatlanmagan, ammo qo’yilgan masalani hal qilish uchun yetarli bo'lgan amaliy usul. Aniq yechimni topa olmagan holatlarda muammoni hal qilishni tezlashtirishga imkon beradi.

Evristik algoritm - bu barcha mumkin bo'lgan holatlarda uning to'g'riligi isbotlanmagan, ammo ko'p hollarda juda yaxshi yechim topishi ma'lum bo'lgan masalani hal qilish algoritmi. Aslida, hatto evristik algoritm rasman noto'g'ri ekanligi ham ma'lum bo'lishi mumkin (ya'ni isbotlangan). Agar u bir vaqtning o'zida noto'g'ri natijani faqat alohida, juda kam uchraydigan va alohida ajratilgan hollarda bersa yoki noaniq, ammo baribir maqbul natijani beradigan bo'lsa, undan foydalanish mumkin.

Oddiy qilib aytganda, evristika mutlaqo matematik asoslangan emas (yoki "umuman to'g'ri emas"), ammo bu amaliy foydali algoritmdir. Masalani hal qilishning aniq algoritmidan farqli o'laroq, evristik algoritmlar quyidagi xususiyatlarga ega ekanligini tushunish muhimdir:

• 
  yaxshiroq yechimni kafolatlamaydi.
  
• 
  garchi u aniq mavjud bo'lsa ham, yechimni topishga kafolat bermaydi.
  
• 
  Ba'zi hollarda u noto'g'ri qaror qabul qilishi mumkin.
  

Hisoblash murakkabligi yuqori bo’lgan masalalarni hal qilish uchun evristik algoritmlardan keng foydalaniladi. Ya’ni ko’p vaqt talab qiladigan va ba’zan texnik jihatdan imkonsiz barcha variantlarni to’liq qayta ko’rib chiqadigan algoritm o’rniga ancha tezroq, ammo yetarlicha nazariy asoslanmagan algoritm qo’llaniladi.

• 
  Taqribiy va evristik usullar - yechim elementlarini tanlash uchun evristikadan foydalanish.
  
• 
  Psevdopolinomial algoritmlar - dinamik dasturlash sinfiga oid algoritmlar.
  
• 
  Local yahshilash usuli - ba'zi bir mavjud yechim atrofida eng maqbul yechim izlash.
  
• 
  Tarmoqlar va chegaralar usuli - ba'zi baholashga ko'ra maqbul bo'lmagan yechimlarning barcha sinflarini bekor qilish.
  
• 
  Tasodifiy qidiruv usuli - tanlovni tasodifiy tanlovlar ketma-ketligi bilan ifodalash.
  

Yaqinlashtiruvchi(approksimatsion) algoritmlar polinomial vaqt ichida bajariladi va optimal darajaga yaqin bo'lish kafolati bo'lgan yechimlarni topadi.

Algoritmlarni ishlab chiqish uchun to'rtta umumiy metodologiya:

1. 
   Birinchi umumiy metodologiya tez va oson bajariladigan ochko'z algoritmlardir. Asosiy muammo bu optimalga yaqin maqbul yechimlarga olib keluvchi ochko'z algoritm qoidalarini topishdir.
   
2. 
   Ikkinchi umumiy metodologiya – narxlarni belgilash usuli - iqtisodiy asoslangan; masaladagi har bir cheklovga rioya qilish uchun to'lanishi kerak bo'lgan narxni ko'rib chiqiladi.
   
3. 
   Uchinchi umumiy metodologiya – Butun sonli chiziqli dasturlash usulidir. Butun sonli dasturlash masalasi ham chiziqli dasturlash masalasidek qo’yilib, optimal yechim o’zgaruvchilarning qiymati butun musbat son bo’lsin, degan qo’shimcha talab qo’yiladi.
   
4. 
   To’rtinchi umumiy metodologiya – dinamik dasturlash usuli bo’lib, optimallashtirish muammolarini hal qilishda, ma'lum cheklovlarni hisobga olgan holda, maksimal yoki minimal echimni qidiradigan muammolar uchun foydali usuldir, chunki u barcha mumkin bo'lgan kichik muammolarni ko'rib chiqadi va hech qachon biron bir sub-muammoning yechimini qaytarmaydi.
   

Yaqinlashtiruvchi(approksimatsion) algoritmlarning tasnifi:

• 
  kafolatlangan faoliyat ko’rsatuvchi algoritmlari;
  
• 
  lokal optimallashtirish algoritmlari va evristik protseduralar;
  
• 
  lokal optimallashtirish algoritmlari va evristik protseduralardan foydalanuvchi birlashtirilgan algoritmlar;
  
• 
  taqribiy yechimlarga erishish uchun aniq usullarning elementlaridan foydalanuvchi algoritmlar;
  
• 
  "tarmoqlar va chegaralar" kabi birlashtirilgan algoritmlar, katta o'lchamdagi masalalarni hal qilish algoritmlari.
  

NP toʼliq masalalarni yechish usullarining tasnifi.