|
1. Algoritmlerdi proektlestiriwge kirisiw
|
| bet | 8/11 | | Sana | 09.06.2024 | | Hajmi | 1,23 Mb. | | #261899 |
Bog'liq Algoritmlerdi proektlestiriw JB sorawlarKruskal algoritmı
Algoritm ideyasın ańlatayiq. Aldın terek qırlarınıń kompleksi bos dep daǵaza etiledi. Sonnan keyin múmkin bolǵanǵa shekem keyingi ámel orınlanadı: barlıq qırlardan, olardı bar bolǵan toplamǵa qosılıwı cikl payda bolıwına alıp kelmeytuǵın qırlardan, eń arzan (eń kem ǵárejetli) qırı tańlap alınadı hám bar bolǵan toplamǵa qosıp qoyıladı. Bunday qırlar qalmaǵaninda, algoritm tamamlanadı hám biz dáslepki grafti barlıq ushlarina iye bolǵan graf astın payda etemiz. Bul graf astında cikller bolmawinan, ol eń arzan (eń kem ǵárejetli) terek bolıp, onıń basqasha atı ostov teregi dep júritiledi. Algoritmdı anıq kóz aldimizǵa keltiriwdi mısalda ámelge asıramız hám barlıq processti basqıshpa-basqısh sxematik tárzde ańlatpalaymız. Dáslepki graf 11.1-suwretde keltirilgen.
11.1-súwret
Graftiń hár bir qırı belgili bir salmaqqa iye bolıp, ostov teregin qurıwda biz áyne qırlar salmaǵınan kelip shıǵamız. Onıń ushın qırlardı salmaqları boyınsha tártipleymiz. Eń arzan 5 bahalı qır A B terek kompleksiniń birinshi elementi boladı hám keyngi AG, CD, AC, GF, DE qırlar ma`nisi boyınsha terekke qosıp barıladı
1shi basqısh sızılma AB ni tańlaw
2shi basqısh sızılma AG ni tańlaw
3shi basqısh sızılma CD ni tańlaw
4shi basqısh sızılma AC, GF ti tańlaw
5shi basqısh sızılma DE ni tańlaw
Qalǵan qırlardan qálegenin berilgen terekke qosılıwı cikller payda bolıwına alıp keledi. Demek áyne usi terek izlenıp atırǵan ostov teregi boladı. Bayanlawımız tolıq bolıwı ushın dáslepki grafti sonday suwretleymiz, ostov tereginiń qırları tegis -úzliksiz sızıqlar menen, qalǵan qırlar punktir sızıqlar menen sızılǵan boladı.
11.2-súwret.
D
B
A C
E
F
59. Kesilispeytuǵın toplam astıları hám birlespelerin islew algoritmi.
Kesilispeytuǵın jıynaq astıları hám birlespelerin qıdırıw algoritmi matematika hám informatikada zárúrli temalardan biri bolıp tabıladı. Bul algoritm jıynaqlardı óz-ara kesilispeytuǵın klasslarǵa ajıratıwdı ańlatadı. Endi, bul temanı bir az ishinde kórip shıǵamız :
Jıynaqlardı klasslarǵa ajıratıw :
Jıynaqlardı klasslarǵa ajıratıwda, olardı óz-ara kesilispeytuǵın klasslarǵa ajıratıw kerek. Bul klasslar tómendegi shártlerdi qánaatlantirsa, olar klasslarǵa ajıratılǵan dep ataladı :
Bólim jıynaqlar jupi-jupimenen óz-ara kesilispese: Bul jerde hám belgisi menen kórsetilgen.
Bólim jıynaqlardıń birlespesi jıynaq menen uyqas tusse: Bul jerde hám belgisi menen kórsetilgen.
Klassifikatsiya - bul klass ishinde ob'ektlerdiń uqsaslıǵı hám olardıń basqa klaslardaǵı ob'ektlerden parıq etiwi tiykarında klasslar boyınsha ob'ektlerdi ajıratıw ámeli bolıp tabıladı. Eger joqarıdaǵı shártlerden weń az birewi atqarılmasa, klassifikatsiya nadurıs esaplanadı.
Jıynaqlardı bir, eki hám ush qasiyetke kóre klasslarǵa ajıratıw :
Jıynaqlardı bólim jıynaqlarǵa ajıratıw ushın, olardıń ózgesheliklerin kórsetiw kerek. Jıynaqlardı bir, eki hám ush ózgesheligine kóre klasslarǵa ajıratıw múmkin. Mısal ushın, natural sanlar kompleksin bir neshe usıl menen klasslarǵa ajıratıw múmkin:
Toq hám jup sanlar klası.
Túp hám quramalı sanlar klası.
Bir xanalı, qos belgili, úsh xanalı, …, xanalı sanlar klası.
60. P, NP hám NP tolıq máseleleri.
Eyler diagrammasiuchun P, NP, NP-tolıq hám NP-qattı máseleler kompleksi (tiyisli bolǵan bos til jáne onıń qosımshası bunnan tısqarı ) Plekin joq NPto'liq)
Hújim qılıw P=NP savol, túsinigi NP-tolıqlıq júdá paydalı NP-pıtken máseleler -bul hár birewiniń aldına qóyatuǵın máseleler kompleksidir NP-mashqala polinom waqtında kemeytiriliwi múmkin jáne onıń sheshimi ele da polinom waqtında tastıyıqlanishi múmkin Yaǵnıy, hár qanday NP mashqalanı hár qanday birine aylandırıw múmkin NP-tolıq máseleler Rásmiy bolmaǵan túrde NP-tolıq mashqala NP hesh bolmaǵanda basqa hár qanday mashqala sıyaqlı " qattı" bolǵan mashqala NP-qattı máseleler, hesh bolmaǵanda qıyın bolǵan zatlar NP máseleler, yaǵnıy barlıǵı NP mashqalalardi olarǵa kemeytiw múmkin (polinom waqtında ) NP-qattı máseleler bolıwı shárt emes NP, yaǵnıy olar polinom waqtında tekseriliwi múmkin bolǵan sheshimlerge ıyelewleri shárt emes Mısalı, Logikalıq maqullik mashqalasibu NP tárepinen toldırılǵan Kuk-Levin teoremasi, sol sebeplihar qandaydıń mısalihar qanday mashqala NP mexanik túrde polinom waqtındaǵı logikalıq toyınǵanlıq mashqalasınıń mısalına aylantırılıwı múmkin Logikalıq logikalıq mashqalası áne sonday máselelerden biri bolıp tabıladı NP-tolıq máseleler Eger bar bolsa NP-tolıq mashqala P, keyin buǵan eriw kerek P=NP Biraq, kóplegen zárúrli máseleler kórsetildi NP tolıq hám hesh birewiniń operativ algoritmi málim emes Tek ǵana tariyp tıykarlanıp, bul anıq emes NP-tolıq máseleler ámeldegi; biraq, áhmiyetsiz hám oylap tabılǵan NP-tamamlı máseleni tómendegishe qáliplestiriw múmkin: a xarakteristikası berilgen Turing mashinası polinom waqtında toqtatılıwı kepillik berilgen, polinom úlkenligi barma? qabul qilasizmi? Bul ishinde NP sebebi (kirisiw berilgen) yamasa joq ekenligin tekseriw ańsatMtaqlid qılıw arqalı kirisiwdi qabıl etedim; bul NP-tolıq, sebebi mashqalanıń hár qanday anıq úlgisi ushın tekseriwshi NP polinom-waqıt mashinası retinde múmkin kod bu sheshim kirisiw retinde tekseriliwi kerek Keyin mısal awa yamasa joq ekenligi máselesi haqıyqıy kirisiw bar ekenligi menen belgilenedi Birinshi tábiyiy mashqala NPSAT dep da atalatuǵın logikalıq qaniqish mashqalası tolıq edi Joqarıda aytıp ótilgeni sıyaqlı, bul Kuk-Levin teoremasi; onıń qanaatlanǵan ekenliginiń tastıyıqı NP Komplektda Turing mashinaları haqqındaǵı texnikalıq maǵlıwmatlar ámeldegi, sebebi olar tariypiga tiyisli NP Biraq, bul mashqala
61. NP - tolıq máseleleri. Esaplawda sheshilmeslik jaǵdayları.
Endi biz ushbu masalalarning hisoblash murakkabligidan kelib chiqadigan, NP masalalari sinfiga kiradigan, ba’zi masalalar taqdimotiga murojaat qilamiz.
1. Kvadrat matrisalarning determinantlarini hisoblash. Bu juda shaffof va sodda masalaga o`xshaydi. Keyingi materiallarni yaxshi va oson o`zlashtirish uchun biz ushbu masala haqida batafsil to`xtalamiz.
bo`lganda arifmetik amallarsoni , ya’ni ikkita ko`paytirish va bitta ayirishamallari mavjud. Uchinchi tartibli determinantni birinchi qator elementlari bo`yicha hisoblash qoidasi orqali bajariladi.
Bu yerda Aij -aij elementlarning algebraik to`ldiruvchilari bo`lib, ikkinchi tartibli determinant bo`ladi, ularni har birini hisoblash uchun uchta algebraik amallar bajariladi. Shunday qilib, biz uchinchi tartibli determinantni hisoblash uchun
|
| |
