N3 = 3 * 3 + 3 + 2 = 14 amallarni bajarish zarurligini aniqladik. n– tartibli detenminantni hisoblash uchun quyidagi formuladan foydalanishimiz mumkin.
Bundan ko`rishimiz mumkinki, arifmetik amallar sonini quyidagi tengsizlik orqali hisoblashimiz mumkin ekan.
Bizni – tartibli determinantlarni umumiy ta’rifidan shunday xulosaga kelishimiz mumkinki, unda barcha mumkin bo`lgan amallarning yig`indisi ga teng bo`ladi, ularning xar biri esa n-1 ko`paytmaga va ularning yig`indisi (ayirmasi) ga teng bo`ladi. Shunday qilibbiz, quyidagiga egabo`lamiz.
(1)
Bu (1) formuladan ko`rinib turibdiki, yuqori tartibli determinantlarni hisoblash juda ko`p arifmetik amallarni bajarishga to`g`ri keladi. Masalan, n=9 va n=10 gazteng bo`lganda biz quyidagi sonlarga egabo`lamiz.
N9=3265919, N10=36287999.
Ushbu ma’lumotlardan ko`rinib turibdiki, arifmetik amallar sonini deyarli qabul qilish mumkin emas. Tasavvur qiling, o`nta noma’lum bo`lgan o`nta chiziqli algebraik tenglamalar sistemasini Kramer usuli yordamida yechmoqchimiz. U holdabiz 11 ta shunday determinantni hisoblashimiz kerak bo`ladi, ularning har biri uchun N10 ta amallarni bajarishimiz kerak bo`ladi.
Muammolarning NP sinfiga tegishliligini ko`rsatadigan vaqt keldi. Belgilaridan biri sifatida biz murakkablik darajasini olishimiz mumkin kerakli arifmetik amallar soni ga proporsional va bu son shunchalik tez o`sadiki, ma’lum bir qiymatdan boshlab u juda katta songa aylanadi. Bunday masalalarni zamonaviy super kompyuterlarda ham hal qilish imkoniyati bo`lmay qoladi.
62. NP - tolıq máselelerdi sheshiw algoritmlerin qıyınlıǵın bahalaw.
Áwele sorawdıń teoriyalıq tárepleri haqqında toqtalamiz P hám NP quramalılıq klasslarınıń teńligi máselesi dúnya matematikalıqları juwap izlayotgan algoritmler teoriyasınıń makaziy ashıq máselelerinen biri bolıp tabıladı Bul másele algoritmler teoriyasınıń esaplaw teoriyası quramalılı bóliminde kórip shigılıp atır Ol malum bir máseleni sheshiw ushın zárúr bolǵan dereklerdi úyrenedi Eń keń tarqalǵan derekler waqıt (arifmetik ámeller sanı ) hám yad (kompyuter yadı ushın zárúr bolǵan kólem) Toliq máseleler P hám NP klassları ortasida teńlik máselesi mıń jıllıq máselelerden biri bolib, onı sheshiw ushın Kley Matematika institutı bir million AQSH dolları muǵdarında sıylıq elon etdi Bul máseleni eslatamiz
1 P hám NP klasslar teńligi;
2 Xodja gipotezasi;
3 Puankare gipotezasi (sheshilgen);
4 Riman gipotezasi;
5 Yang-Mixlsning kvant teoriyası teńlemesi sheshimi;
6 Sortye- Stokstıń teńlemeleri sheshimleriniń bar ekenligi hám tegisligi;
7 Berg-Svinnerton-Drayerlarning gipotezasi;
Mashqalanı ápiwayı formada súwretlewge háreket qilaylik Máseleniń má ⁇ lum bir sheshiminiń tuwrılıǵın tekseriw ushın polinominal waqıt kerek bolsa, ol halda sheshimdi ózin tabıw ushın bizge polinom waqtı kerek bolsa, hám máseleni sheshiwde biz polinomli yaddan paydalanamız? Basqasha aytqanda, máseleniń sheshimin tuwrılıǵın tekseriw, onı tabıwdan ańsat emesligin kóriw múmkin emespe?
Mısalı, {-2,-3, 15, 14, 7,-10,... } sanları arasında olardıń jıyındısı nolge teń bola ma (tómen jıynaqlar jıyındısı máselesi) sonday rostligi ekanmi? Juwapbiy, ijochunki -2-3+15-10=0 tuwrıdan-tuwrı qosıp qanǵana esaplanadı Juwaptıń tap ' g ' riligini tekseriw ushın zárúr bo ' lgan má ' lumot SERTIFIKAT dep ataladı Sonnan kelip shıǵadıki, bul sanlardı alıw jaysha ańsatmi? Bunı da tekseriw sonshalıq ańsatmi sertifikattı tabıw sıyaqlı? Sanlardı tańlaw qıyınlaw tuyuladi, lekin bul tastıyıqlanbaǵan Bul P hám Np sinflarning tarifidan kelip shıǵadı, biraq sol payıtqa deyin bul qatnastıń qatiyligi haqqında hechnarsa málum emes Endi NP klasındaǵı eń qıyın máseleler (NP-tolıqmasalalari) eksponensial waqıt ishinde sheshiliwi múmkin, biraq bul ámeliy kózqarasınan qabıl etiliwi múmkin emes.
Mashqalalardıń NP klasına tiyisliligin kórsetetuǵın waqıt keldi Belgilerinen biri retinde biz quramalılıq dárejesin alıwımız múmkin kerekli arifmetik ámeller sanı ǵa proporsional jáne bul san sonshalıq tez ósediki, málum bir bahadan baslap ol kútá úlken sanǵa aylanadı Bunday máselelerdi zamanagóy super kompyuterlerde de sheshiw múmkinshiligi bolmay qaladı Sonı da ta kidlash kerekki, sheshiletuǵın barlıq dáslepki máseleler tiyisli úskeneler tárepinen belgilenetuǵın ko'rstgichlar, sáykes keletuǵın qurılmalar tárepinen anıqlanatuǵın ko∂rsatgichlar pútinlengen hám ba zi fizikalıq ko∂rsatgichlarning bahaları ámeliy bo∂ladi Arifmetik ámellerdi orınlawda bul to̅g̅irlab bo̅lmas aljasıqlar to̅planib, qabıl etiliwi múmkin bo̅lmagan úlken aljasıqlarǵa alıp keliwi múmkin. Sol qatnas menen, bunday máselelerdiń ámeliy sheshimlerin tabıw ushın hár qıylı sanlı usıllar payda boldı Solay etip, úlken n lar ushın sızıqlǵ algebraik teńlemeler sistemasın sheshimlerdi tabıw ushın ápiwayı tákirarlaw usılı yamasa Zeydel usılı qollanıladı
63. NP-tolıq máseleler haqqında túsinik beriń
Kóp qızıqlı hám ámeliy máselelerdi polynomial waqıtta sheshiw múmkin emes yamasa olar ushın házirgi waqıtta polinomial algoritmler tabilǵan zatǵan. NP (Nondeterminictic Polinomial) quramalılıq klası daǵı másele - bul sonday máseleler klasıdirki, olardı sheshiw ushın polinomial algoritm bar bolmasligi múmkin, lekin eger biz onıń sheshimin bilsek (mısalı, biz bunı shama menen tapqan bolsaq ), ol jaǵdayda polinominal waqıt ishinde onıń tuwrılıǵın tekseriw múmkin. Bul klass ishinde NP-tolıq máselelerge bólek itibar beriledi. Bul máselelerdi sheshiw ushın polynomial algoritmler ele tabilǵan zatǵan. Biraq bul klasstaǵı barlıq máselelerdi bir-birine keltiriw múmkin. Yaǵnıy, eger NP tolıq máselelerdiń qanday da qandayda birsin polynomial waqıt ishinde sheshiw múmkin bolsa, bul bul klasstaǵı barlıq basqa máselelerpolinomial waqıtta nátiyjeli hal etiliwin ańlatadı.
Búgingi kunga shekem, kópshilik qánigeler NP tolıq máselelerdi polinomial waqıt ishinde hal etip bolmaydı, yaǵnıy NP≠P dep esaplasadı (bul jerde P - polinomial waqıt ishinde sheshiliwi múmkin bolǵan máseleler klası ), biraq bunı tastıyıqlay almadılar. Biraq sońǵı payıtlarda bul kózqarastı biykar etiwge urınıslar bar. Yaǵnıy, bul ilimiy tartıs daǵı noqat ele anıqlanbaǵan. NP klası daǵı kóplegen máseleler ushın (bunday máseleler bir neshe mińlaǵan anıqlanǵan) sheshimlerdiń nátiyjeli algoritmleri qashannan berli islep shıǵılǵan yamasa olardıń tolıqlıǵı tastıyıqlanǵan. Soǵan qaramay, bul máselede esaptan tısqarılar bar.
NP tolıq máselerni sheshiwdiń keskin ámeliy mútajlikleri bizni olardı sheshiw menen baylanıslı qıyınshılıqlardı jeńiw jolların izlewge májbúr etedi. Bunday jollar retinde tómendegilerdi atap kórsetiw múmkin: evristik (jaqınlasqan ) sheshimlerdi tabıw, qıdırıw algoritmlerin jetilistiriw, máselelerdiń ólshemlerine eksponential dárejede baylanıslı bolǵan kestelerden paydalanıwshı dinamikalıq programmalastırıw. Jańa máselege dus kelińanda, birinshi náwbette soraw tuwılıwı tábiyiy: " Kórip shıǵılıp atırǵan máseleni polinomial algoritm járdeminde hal qilsa bola ma? ". Eger bul sorawǵa juwap unamlı bolıp shıqsa, ol jaǵdayda NP-tolıqlıq teoriyası kózqarasınan mashqala haqqında hesh nárse deyiw múmkin emes. Keyingi háreketlerimizni ılajı bolǵanınsha eń nátiyjeli polinomial algoritmlerdi tabıwǵa jıynashimiz múmkin. Biraq, eger máseleni sheshiw ushın polinomial algoritmi málim bolmasa, ekinshi soraw tuwıladı : " Bul másele NP-tolıqlıǵı rostmi? " Sonı eslep qalıńki, ayırım jaǵdaylarda bizni qızıqtırarlıq máseleniń polinomial sheshimge iyeligi ańsatǵana ornatıladı, basqalarında bolsa onıń NP-tolıqlıǵı ayqın kórinip turadı.
NP-tolıq máseleni sheshiwdiń maqul túsetuǵın algoritmin tabıw mashqalasın sheshiwde eki taypa daǵı jantasıw bar bolıp tabıladı. Birinshi gruppa qıdırıw kólemin minimallastırıwǵa qaratılǵan jantasıwdı óz ishine aladı, biraq usı waqıtta eksponentsial waqıt sarp etiw etiliwiniń anıqlıǵı tán alınadı. Izbe-iz tańlap alıw usılı ushın eń kóp qollanıladıgen usıllar qatarına “tarmaqlar hám shegaralar” usılı yamasa " uǵımsız tańlap alıw" usılına tiykarlanǵan usıllar kiredi.
NP-tolıq máselelerdiń úlgileri:
Bool formulalarınıń atqarılıw máselesi
“On beslik” oyınınıń eń qısqa sheshimi
Kommivoyajer máselesi
Shteyner mashqalası
Grafni boyaw mashqalası
Graf shıńın oraw máselesi, Jıynaqtı oraw máselesi, Graf shıńlarınıń ǵárezsiz jıynaqları máselesi
64. Graflarda erkin úshlarin tańlaw, boyaw.
Graflar nazariyasini o`rganayotganimizda, graflarni bo`yash bo`lmida biz bir xil rangdagi uchlarning bo`lmasligi sharti bilan graf uchlari masalasini ko`rib chiqqan edik. Shu bilan birga, ushbu masalani hal qilish uchun zarur bo`lgan ranglarning minimal sonini aniqlash to`g`risida savol tug`ildi. Xuddi shu masala, shunday shart ostida graf qirralarini bo`yash masalasi paydo bo`ladi. Bir xil ranglardagi qirralari hech bir uchlarida kesishmasligi kerak. Ushbu masalani vizual ravishda, grafning geometrik tasviri mavjud bo`lganda, tanlov usuli bilan hal k
qilish mumkin.
Bizga G –garf V={1,2,3,4,5,6} uchlari bilan berilgan bo`lsin va uning 11 ta qirralari U={a,b,c,d,e,f,g,h,k,e,n} bo`lsin (1-rasm).
Graf uchlarini bo`yashning mumkin bo`lgan variantlaridan biri quyidagicha bo`lishi mumkin. Birinchi uchini yashilrangga bo`yaymiz. Savol tug`iladi yana qaysi uchlarni yashilrangga bo`yashimiz mumkin, ya’ni bo`sh (ozod) uchini olishimiz uchun. Bu holda, biz 2-chi, 4-chi, 5-chi, 6-chi uchlarni olmaymiz ular 1-chi bilan bog`langan, shu sababli 3-chini olamiz u 1-chi bilan bog`lanmagan. Shunday qilib, biz 1- chiva 3-chi uchlarni yashilrangga bo`yaymiz. Qolgan uchlarni bo`yash uchun boshqarangni tanlaymiz, masalan sariq rangni 2-chi uchi uchun tanlaymiz. Shunday qilib, biz 1,2,3 uchlarni bo`yab bo`ldik. Keyinggi bosqichda biz bo`sh, ya’ni ushbu uchlar bilan bog`lanmagan uchlarni topishga harakat qilamiz. Bunday uch yo`q, shundan so`ng rang berib bo`yash uchun biz boshqa yangi rang tanlashimiz kerak bo`ladi. Endi 6-chi uch uchun biz qizil rangni tanlaymiz. Keyin, masalaning talablariga rioya qilgan holda, 4-chi uch uchun sariq rangni, 5-chi uch uchun esa qizil rangni tanlashimiz mumkin. Natijada, uchlarni bo`yash uchun uchta rang yetarli degan xulosaga keldik. Ushbu jarayonni avtomatlashtirish uchun qo`shni (aralash) matrisa asosida uchlarning ranglarini tanlash algoritmini tuzib, va uning dasturini tuzish kerak bo`ladi.
Graf qirralarini bo`yashni boshlash uchun biz eng katta karrali uchlarini tanlab va bu uchlaridan chiqadigan qirralariga xar xil ranglarni tanlashimiz lozim. Keyin iloji boricha qolgan qirralarni bo`yash paytida ushbu ranglarni kombinasiyalashtiramiz (almashtiramiz). Xususan, biz misol uchun quyidagi qirralarni bo`yash variantini ko`rib chiqamiz.
Bu yerda 1,2,3,4,5 raqamlar bilan xar hil ranglar belgilangan.
Axborot texnologiyalaridagi aktual amaliy dolzarb muammolaridan biri bu ma’lum bir sinf masalalarini hal qilish uchun zarur bo`lgan belgilarning sonni aniqlashdir. Elektron kompyuterlarni yaratish arafasida biz bunday muammoga duch keldik. Bu muammo asosan amaliy, texnik jixatidan amalga oshiriladigan va axborot xarakteridagi masalalardir. Shu nuqtai nazardan, eng maqbul bo`lgan, faqati kkita 0 va 1 raqamlari asosida qurilgan hisoblashning ikkilik tizimi bo`lib, butun axborot va operasion tizimlar shu asosida qurilgan.
65. Graflar ústinde algoritmler
Graflar ustida algoritmlarni o'rganish qiziqarli va murakkab bo'lgan mavzulardan biridir. Graflar ustidagi asosiy algoritmlar quyidagilardir:
1. Chuqurlik-birinchi izlash (Depth-First Search - DFS):
- Grafning tuguni yoki yoqlarini ketma-ket tartibda aylanib chiqishda ishlatiladi.
- Rekursiv yoki iterativ usullarda amalga oshirilishi mumkin.
- Masalalar: maksimal/minimal yoqlar topish, birlashish komponentlarini aniqlash.
2. Kenglik-birinchi izlash (Breadth-First Search - BFS):
- Grafning tug'unlarini kenglik bo'yicha ketma-ket aylanib chiqishda ishlatiladi.
- Navbat yordamida amalga oshiriladi.
- Masalalar: eng qisqa yo'l topish, birlashish komponentlarini aniqlash.
3. Dijkstra algoritmi:
- Og'irlangan graflar uchun eng qisqa yo'lni topish uchun ishlatiladi.
- Natijaviy yo'l qiymati eng kichigi bo'lgan yo'lni topadi.
- Massiv yoki navbat yordamida amalga oshiriladi.
4. Kruskal algoritmi:
- Og'irlangan graflar uchun minimum daraxtini topish uchun ishlatiladi.
- Yoqlarni og'irlikka ko'ra tashqi-ichki tartiblaydi va kerakli yoqlarnigina birlashtiradi.
- Disjoint-set ma'lumotlar tuzilmasidan foydalanadi.
5. Prim algoritmi:
- Og'irlangan graflar uchun minimum daraxtini topish uchun ishlatiladi.
- Tug'unlarni ketma-ket tanlash orqali minimum daraxtni qurib boradi.
- Navbat yordamida amalga oshiriladi.
6. Topologik saralash:
- Yo'naltirilgan ayklik graflar uchun tug'unlarni saralash algoritmi.
- Tug'unlarni oldinga-keyingi tartibda saralaydi.
- Kenglik-birinchi va chuqurlik-birinchi izlash orqali amalga oshiriladi.
Bulardan tashqari, graflar ustida bir qator boshqa algoritmlar ham mavjud bo'lib, ular graflarning xususiyatlariga qarab qo'llaniladi.
66. Toplamlardıń toplam astıların anıqlaw, birlestiriw.
To'plamlarning to'plam ostidagi qismlarini aniqlash masalasi to'plamlar nazariyasida muhim o'rin tutadi. Bu masala quyidagicha amalga oshiriladi:
1. Berilgan to'plam (A) uchun barcha mumkin bo'lgan qism to'plamlarni aniqlash:
- To'plam A ning qism to'plamlari soni 2^n ta bo'ladi, bunga A dagi n ta element sababchi bo'ladi.
- Qism to'plamlarni aniqlash uchun rekursiv yoki iterativ usullar qo'llaniladi.
- Masalan, A = {1, 2, 3} bo'lsa, uning qism to'plamlari: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.
2. Ikkita to'plam (A va B) uchun ularning birlashma, kesishuv, farq va simmetrik farqini aniqlash:
- Birlashma: A ∪ B = {x | x ∈ A yoki x ∈ B}
- Kesishuv: A ∩ B = {x | x ∈ A va x ∈ B}
- Farq: A \ B = {x | x ∈ A va x ∉ B}
- Simmetrik farq: A △ B = (A \ B) ∪ (B \ A)
3. To'plamlar orasidagi munosaballarni aniqlash:
- A ⊆ B: A to'plami B to'plamining qism to'plami
- A = B: A va B to'plamlari bir-biriga teng
- A ⊂ B: A to'plami B to'plamining to'liq qism to'plami
4. To'plamlar ustida amallar bajarish:
- Ikki to'plam yig'indisi: A + B = {x + y | x ∈ A, y ∈ B}
- Ikki to'plam ko'paytmasi: A × B = {(x, y) | x ∈ A, y ∈ B}
- To'plam quvvatini aniqlash: |A| - A dagi elementlar soni
To'plamlar nazariyasi graflar nazariyasi, matematik analiz va boshqa matematik sohalarda keng qo'llaniladi. To'plam ostidagi qismlarni aniqlash masalasi, to'plamlar orasidagi munosabatlar va to'plamlar ustida amallar bajarish muhim ahamiyatga ega.
To'plamlarning to'plam ostidagi qismlarini aniqlash va ularning birlashtirmasini topish quyidagi algoritm asosida amalga oshiriladi:
1. Berilgan to'plam A uchun qism to'plamlarni aniqlash:
- Qism to'plamlar soni 2^n ta bo'ladi, bu yerda n - A ning elementlari soni.
- Qism to'plamlarni aniqlash uchun rekursiv yoki iterativ usul qo'llaniladi.
- Masalan, A = {1, 2, 3} bo'lsa, uning qism to'plamlari: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.
2. Qism to'plamlarning birlashtirmasini aniqlash:
- Qism to'plamlarning birlashtirilgan to'plami A ning o'zini ham o'z ichiga oladi.
- Birlashma to'plami quyidagi formula asosida aniqlash mumkin:
B = ∪{X | X ⊆ A} = A
- Masalan, A = {1, 2, 3} uchun birlashma to'plam B = {1, 2, 3}.
Algoritmning batafsil tushuntirilishi:
1. Berilgan to'plam A uchun qism to'plamlarni aniqlash:
- Qism to'plamlarni aniqlash uchun rekursiv yoki iterativ yondashuv qo'llanilishi mumkin.
- Rekursiv yondashuv: Qism to'plamlarni yig'indisi sifatida aniqlash, ya'ni B = {}, {a1}, {a2}, ..., {a1, a2, ..., an}.
- Iterativ yondashuv: Barcha kombinatsiyalarni hisoblab chiqish, ya'ni B = {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}.
2. Qism to'plamlarning birlashtirmasini aniqlash:
- Birlashma to'plam B = A, ya'ni barcha qism to'plamlar A to'plamini o'z ichiga oladi.
- Birlashma to'plamni aniqlash uchun quyidagi formula qo'llaniladi:
B = ∪{X | X ⊆ A} = A
Bu algoritm to'plamlar nazariyasida keng qo'llaniladi va turli matematik muammolarni yechishda asosiy rol o'ynaydi.
67. Kvadrat teńlemediń korenlerin anıqlaw algoritmi.
Kvadrat tenglamaning ildizlarini (yechimlarini) topish uchun quyidagi algoritmni qo'llash mumkin:
1. Kvadrat tenglamaning umumiy ko'rinishini yozib olamiz:
ax^2 + bx + c = 0, bu yerda a, b, c - koeffitsientlar.
2. Diskriminantni hisoblash:
D = b^2 - 4ac
3. Diskriminantni tahlil qilish:
a) Agar D > 0 bo'lsa, tenglamaning ikkita haqiqiy ildizi bor:
x1 = (-b + √D) / (2a)
x2 = (-b - √D) / (2a)
b) Agar D = 0 bo'lsa, tenglamaning bitta haqiqiy ildizi bor:
x = -b / (2a)
c) Agar D < 0 bo'lsa, tenglamaning ikkita mavjud emas, balki kompleks ildizlari bor:
x1 = (-b + i√(-D)) / (2a)
x2 = (-b - i√(-D)) / (2a)
Algoritm bilan ishlash quyidagicha:
1. Kvadrat tenglamaning koeffitsientlarini (a, b, c) olamiz.
2. Diskriminantni hisoblaymiz: D = b^2 - 4ac.
3. Diskriminantni tahlil qilamiz va mos ravishda ildizlarni hisoblaymiz.
4. Agar ildizlar haqiqiy bo'lsa, natijani chiqaramiz.
5. Agar ildizlar kompleks bo'lsa, natijani kompleks ko'rinishida chiqaramiz.
Misol uchun, a = 1, b = 2, c = 1 bo'lsa:
1. D = b^2 - 4ac = 2^2 - 4*1*1 = 0
2. D = 0, demak, tenglamaning bitta haqiqiy ildizi bor:
x = -b / (2a) = -2 / (2*1) = -1
68. Úsh múyeshliktiń maydanın esaplawdıń Geron formulasın.
Geron formulasi uchburchakning yuzasini hisoblash uchun qo'llaniladigan bir usuldir. Bu formula quyidagi shaklda ifodalanadi:
S = √(p(p-a)(p-b)(p-c))
Bu yerda:
- S - uchburchakning yuzi
- a, b, c - uchburchakning tomonlari
- p - uchburchakning yarim perimetri, ya'ni (a+b+c)/2
Formulaning ishlash tartibi quyidagicha:
1. Uchburchakning tomonlarini (a, b, c) olamiz.
2. Uchburchakning yarim perimetrini (p) hisoblaymiz: p = (a + b + c) / 2
3. Geron formulasini qo'llab, uchburchakning yuzasini (S) hisoblaymiz:
S = √(p(p-a)(p-b)(p-c))
Misol uchun, agar uchburchakning tomonlari a = 3, b = 4, c = 5 bo'lsa, unda:
1. p = (3 + 4 + 5) / 2 = 6
2. S = √(6(6-3)(6-4)(6-5)) = √(6*3*2*1) = √36 = 6
Demak, uchburchakning yuzi 6 kvs.m.
Geron formulasidan foydalanish uchburchakning yuzasini osonlik bilan hisoblash imkonini beradi, faqat uchburchakning tomonlari ma'lum bo'lsa kifoya.
69. Massiv elementlerin tártiplestiriw.
Massiv elementlarini tartiblashtirish uchun turli xil algoritmlar mavjud. Ba'zi eng mashhur algoritmlar quyidagilar:
1. Bubble sort (Pufakcha tartiblash)
2. Insertion sort (Qo'yish tartiblash)
3. Selection sort (Tanlash tartiblash)
4. Merge sort (Birlashtirish tartiblash)
5. Quick sort (Tez tartiblash)
Ular orasida eng ko'p qo'llaniladigan algoritmlar Bubble sort, Insertion sort, Quick sort hisoblanadi.
Bubble sort:
- Massiv elementlarini ketma-ket solishtirib, kattalarini orqaga siljitadi.
- O(n^2) murakkablikka ega.
- Kichik massivlar uchun juda samarali.
Insertion sort:
- Massivni oldindan tartiblanganlardan boshlab, qolganlarini o'rniga qo'yadi.
- O(n^2) murakkablikka ega.
- Kichik massivlar uchun juda samarali.
Quick sort:
- Massivni ikkita qismga bo'ladi, kichik elementlar bir tomonga, kattalar boshqa tomonga.
- O(n*log n) murakkablikka ega.
- Katta massivlar uchun juda samarali.
Har bir algoritmning o'z afzalliklari va kamchiliklari mavjud. Massiv o'lchami kichik bo'lsa, Bubble sort yoki Insertion sort maqsadga muvofiq bo'ladi. Agar massiv katta bo'lsa, Quick sort yoki Merge sort samarali hisoblanadi.
Qo'llaniladigan algoritm tanlovi muammoni yechish uchun eng maqbul echim topishga yordam beradi.
70. Matrica maksimal, minimal elementlerin anıqlaw ushın algoritmler.
Matritsaning maksimal va minimal elementlarini aniqlash uchun quyidagi algoritmlari taklif qilish mumkin;
1. Maksimal elementni aniqlash algoritmi:
Kirish: matritsa A, n - satrlar soni, m - ustunlar soni
Chiqish: maksimal element maks
1. maks = A[0][0]
2. uchun i = 0 dan n-1 gacha qadam 1 bilan
uchun j = 0 dan m-1 gacha qadam 1 bilan
agar A[i][j] > maks esa
maks = A[i][j]
3. maks ni qaytarish
2. Minimal elementni aniqlash algoritmi:
Kirish: matritsa A, n - satrlar soni, m - ustunlar soni
Chiqish: minimal element min
1. min = A[0][0]
2. uchun i = 0 dan n-1 gacha qadam 1 bilan
uchun j = 0 dan m-1 gacha qadam 1 bilan
agar A[i][j] < min esa
min = A[i][j]
3. min ni qaytarish
Bu algoritmlar matritsaning barcha elementlarini takrorlash orqali maksimal va minimal elementlarni topadi. Algoritm vaqt jihatidan O(n*m) murakkablikka ega.
Bundan tashqari, matritsaning maksimal va minimal elementlarini topish uchun quyidagi samarali algoritmlarni ham taklif qilish mumkin:
1. Maksimal elementni topish uchun:
- Har bir qatorning maksimal elementini topish va ularning eng kattasini olib berish.
- Har bir ustunning maksimal elementini topish va ularning eng kattasini olib berish.
2. Minimal elementni topish uchun:
- Har bir qatorning minimal elementini topish va ularning eng kichigini olib berish.
- Har bir ustunning minimal elementini topish va ularning eng kichigini olib berish.
Bu algoritmlar O(n+m) murakkablikda ishlab, matritsa elementlarini faqat bir marta takrorlaydi va samarali hisoblanadi.
71. “Ajrat hám húkimranlıq qıl” principi haqqında
"Ajirat va hukumronlik" prinsipi - bu bir qator boshqaruvchilarning odatiy usullaridan biri hisoblanadi. Bu prinsipda asosiy maqsad - ommani bo'lib, uni kuchsizlantirish va boshqaruvni o'z qo'lida saqlab turish. Bu prinsip quyidagilarni o'z ichiga oladi:
1. Ommani bo'lib tashash:
- Har xil ijtimoiy guruhlar, sinflar va qatlamlarni bir-birlariga qarshi qo'yish;
- Etnik, diniy, siyosiy va boshqa xilma-xil farqlarni kuchaytirish;
- Odamlarning bir-birlariga ishonchsizligini oshirish.
2. Ommani kuchsizlantirish:
- Jamoatchilik manfaatlariga emas, balki shaxsiy manfaatlarga xizmat qilish;
- Ommaning tashabbuskорligini bosmirish, mustaqilligini cheklash;
- Axborotni nazorat qilish, manipulyatsiyalar orqali ommani boshqarish.
3. Hukumronlikni saqlab qolish:
- O'zini xalqdan ustun qo'yish;
- Boshqaruvni markazlashtirib, uni o'z qo'lida saqlash;
- Siyosiy va iqtisodiy resurslarni markazlashtirib, o'z nazorati ostiga olish.
"Ajirat va hukumronlik" prinsipi ko'pincha totalitar va avtoritar tuzumlar, shuningdek, ba'zi demokratik davlatlarda ham qo'llaniladi. U ommani bo'lib tashash, kuchsizlantirish va hukumronlikni mustahkamlash orqali hukmron elitaning manfaatlarini himoya qilishga xizmat qiladi.
Bunday yondashuv jamoatchilik manfaatlariga emas, balki hokimiyatni saqlab qolishga qaratilgan bo'lgani uchun jamoatchilik tomonidan kuchli qoralanadi. Shu sababli, "ajirat va hukumronlik" prinsipi demokratik jamiyatlarda odatda tanqid ostiga olinadi.
72. “Ajrat hám húkimranlıq qıl” principi boyınsha isleytuǵın algoritmlerdi proektlestiriw.
"Ajirat va hukumronlik" prinsipi asosida ishlaydigan algoritmlarni dasturlash uchun quyidagi bosqichlarni amalga oshirish mumkin:
1. Ma'lumotlarni tahlil qilish va guruhlarga ajratish:
- Ijtimoiy, iqtisodiy, siyosiy va boshqa turli ma'lumotlarni to'plash va tahlil qilish;
- Ushbu ma'lumotlarni turli guruhlar (etnik, ijtimoiy, siyosiy va boshqalar) bo'yicha ajratish.
2. Guruhlararo ziddiyatlarni yuzaga keltirish:
- Turli guruhlar o'rtasida mavjud bo'lgan yoki yuzaga keltirilgan ziddiyatlarni kuchaytirish;
- Ularning manfaatlari va qarashlari o'rtasidagi farqlarni oshirish.
3. Ommani boshqarish va manipulyatsiya qilish:
- Ommani yaxlitlashtirishga, uning mustaqilligini susaytirish va nazorat qilishga qaratilgan chora-tadbirlar ishlab chiqish;
- Axborotlar va kontentni nazorat qilish, ommani yuzaki ma'lumotlar bilan cheklash;
- Omma fikrlarini boshqarish uchun ijtimoiy tarmoqlar, media va boshqa vositalardan foydalanish.
4. Markazlashtirilgan boshqaruv tizimini shakllantirish:
- Hokimiyatni markazlashtirib, uni siyosiy va iqtisodiy resurslarga nisbatan monopoliyani o'rnatish;
- Rasmiy va norasmiy, qonuniy va noqonuniy usullar orqali hukumronlikni mustahkamlash.
5. Raqiblarni kuchsizlantirish va yo'qotish:
- Muqobil guruhlar va liderlarni nufuzdan tushirish, ularning faoliyatini cheklash yoki yo'q qilish;
- Ommani muqobil nuqtalar yoki harakat turlaridan chetga surib, ularni yo'q qilish.
Bu algoritmlar maqsadidan kelib chiqib, turli dastur vositalari, modellar, mashhur algoritmlar (masalan, yashirin Markov modellari, tarmoq analizi va h.k.) yordamida amalga oshirilishi mumkin. Lekin bunday yondashuvlar demokratik qiymatlar uchun xavf tug'dirishi mumkin, shu sababli ular tanqid ostiga olinadi.
73. " Ajrat hám húkimranlıq qıl" túsinigi haqqında
Programmalastırıwda, ajırat hám húkimranlıq qil — bul algoritlik principi bolıp, bul principinıń tiykarǵı ideyası algoritlik máselelerdi bas máselege uqsas kishi bólimlerge bolıp tastap, olardı rekursiv sheshiwden ibarat.
Bul principde másele bólimlerge bólingenligi sebepli, bólim máseleler bas máselege qaraǵanda kishilew bolıwı jáne bul bóliniw toqtap qalıwı ushın tiykar jaǵday bolıwı kerek (Rekursiya yadıńızǵa túsip ketmadimi?). Barlıq túrdegi ajırat hám húkimranlıq qil algoritmlerı
3 basqıshdan ibarat boladı :
1. Bolıp taslaw basqıshı. Bunda bas másele tap sol máselege uqsas kishilew máselelerge bolıp shıǵıladı.
2. Húkimranlıq basqıshı. Tiykar jaǵdayımızǵa uyqas kelip qalǵan bólim máseleler tap ol sıyaqlı sheshiledi.
3. Birlestiriw basqıshı. Bul basqıshda sheshilgen kishi bólim máseleler qaytıp birlestirib shıǵıladı jáne bul bas másele sheshimi boladı.
Usınıń sebepinen, ajırat ha'm húkimranlıq eqil principin 3 gáp menen eslep qalıw múmkin: bolıp tasla, húkimranlıq qil, birlestir.
74. " Ajrat hám húkimranlıq qıl " algoritmi
Programmalastırıwda, ajırat hám húkimranlıq qil — bul algoritlik principi bolıp, bul principinıń tiykarǵı ideyası algoritlik máselelerdi bas máselege uqsas kishi bólimlerge bolıp tastap, olardı rekursiv sheshiwden ibarat.
|
