#AsuultSambar :

ASUULT.NET - МОНГОЛ УЛС МАНДАН БАДРАГ!
It is currently Nov.22.19 8:45 am

All times are UTC+09:00




Post new topic  Reply to topic  [ 43 posts ]  Go to page Previous 1 2
Author Message
 Post subject: Re: P=NP?
PostPosted: Aug.18.10 12:18 pm 
Offline
• Moderator
<b><font color=#000099>• Moderator</font></b>
User avatar

Joined: Mar.06.09 11:45 am
Posts: 13614
Location: God did not create man, man created god.
Хүний зовлонгоор жаргал хийхээ болиорой, гэхдээ энэ чинь бүхэл тоон олонлог, натурал тоон олонлог 2-г илэрхийлж байгаа мөн үү?

_________________
Science, bitсh!


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.18.10 1:04 pm 
Offline
¤ Expert
User avatar

Joined: Apr.13.02 9:20 pm
Posts: 6224
Location: Henti aimgiin Galshar sumiin uyach Bazarwaaniin gert
bish

_________________
http://t8m8r.wordpress.com


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.18.10 1:37 pm 
Offline
• Moderator
<b><font color=#000099>• Moderator</font></b>
User avatar

Joined: Mar.06.09 11:45 am
Posts: 13614
Location: God did not create man, man created god.
Хаха за би чимээгүй хараа л сууж байя...

_________________
Science, bitсh!


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.18.10 2:07 pm 
Offline
¤ Expert
User avatar

Joined: Apr.13.02 9:20 pm
Posts: 6224
Location: Henti aimgiin Galshar sumiin uyach Bazarwaaniin gert
chi hen be yagaad arhi uugaad bn

_________________
http://t8m8r.wordpress.com


Top
   
 Post subject: Yu
PostPosted: Aug.19.10 12:02 am 
Offline
Asuult Precious Member
User avatar

Joined: Apr.12.02 10:54 pm
Posts: 3716
Location: Insulin shock therapy
tentsuu gedeg ni batlagdchuul hend ashigtai? batlagdahgui bol hend ashigtai?


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.19.10 1:26 am 
Offline
¤ Expert
User avatar

Joined: Apr.13.02 9:20 pm
Posts: 6224
Location: Henti aimgiin Galshar sumiin uyach Bazarwaaniin gert
chi ali ih mungu ugsniih ni tald orj batlah nuu

_________________
http://t8m8r.wordpress.com


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.23.10 8:29 pm 
Offline
• Moderator
<b><font color=#000099>• Moderator</font></b>
User avatar

Joined: Mar.06.09 11:45 am
Posts: 13614
Location: God did not create man, man created god.
Ти Жи ямар учиртайг нь мэдэхгүй над мэтэд тайлбарлахгүй юм уу?

_________________
Science, bitсh!


Top
   
 Post subject: Re: Yu
PostPosted: Aug.25.10 12:39 pm 
Offline
Өвөг Дээдсийн Сахиус Гишvvн
Өвөг Дээдсийн Сахиус Гишvvн
User avatar

Joined: Dec.30.02 10:46 pm
Posts: 744
Quote:
tentsuu gedeg ni batlagdchuul hend ashigtai? batlagdahgui bol hend ashigtai?
Tootson bodoh tohooromj olon yanz baigaa. Jishee ni: Tsag agaar uridchilan tootsoh super computer, Intel processor-tai jiriin desktop, toonii mashin. Mash olon architecture-tai tootson bodoh tohooromj baidag bolovch ene bugd daraah neg eronhii ontslogtoi:
yamar negen bodlogo T avch uzie. T-iin engiin jishee gevel s gesen temdegt mor (string) oroltoor orj irehed, s -d 'a' gesen useg baigaa esehiig medeh yavdal baij bolno. Geh met yamar ch baij bolno. n gedeg toogoor oroltiin urtiig temdegley (manai jisheegeer bol n=|s|). Hervee yamar negen tootson bodoh tohooromj T bodlogyg bodohod O(n^k) gesen hugatsaand bodoj chadaj baival oor yamar ch tootson bodoh tohooromj O(n^k') gesen hugatsaand bodoj chadna (k, k' togtmol too, ooroor helbel n ih bolohod oorchlogdohgui. Tsaashdaa O(n^k) -g polynomial gej nerley). Angliar helvel: every computational device is closed under polynomial time.

Iimees ene olon architecture-tai computer dundaas duraaraa negiig ni songoj avch sudalya. Hamgiin engiineer ni Turing Machine (tuuzaar ajilladag mashin, gehdee uunii dotood buttsiis, herhen ajilladag ni chuhal bish tsaashdaa. iluu ihiig unshihiig husvel wiki-ees Church-Turing thesis gej haij uzeerei) gesen tootson bodoh tohooromjiig model bolgon songoj avya.
Gol asuult yu ve? Yamar bodlogo O(n^2) zeregt bodogdoh vee gesen asuult utgagui yum, uchir ni ene ni bidnii songoj avsan architecture-aas shaltgaalna. Yamar bodlogo polynomial hugatsaand bodogdoh ve gesen asuult tavij bolno. Ene ni bidnii songoj avsan architecture-aas hamaaralgui bolno. Hervee bodlogo polynomial hugatsaand bodogdoj baival P gesen angilald oruulya.

Zarim tohioldold bodlogyn shiidiig oloh ni hetsuu baij bolno. Jishee ni tanid neg hun graph ogood, buh oroig yag neg dairah zam ol gevel tun hetsuu baih bolno. harin buh oroig yag neg dairah zam tanid ogood taniig shalga gevel amarhan shuu dee (ene bodlogo hamilton cycle gedeg bodlog). Uun shig, zarim bodlogiin shiidiig olohod hetsuu bolovch, hervee olchihson tohioldold zov esehiig shalgahad amarhan baidag. hervee zov esehiig ni shalgahad polynomial gesen hugatsaand oldoj baival NP bodlogyn torold oruulya. Medeej P torliin bodlogo NP torliin bodlogo bolno. Harin NP torliin bodlogo yamar ch bodlog polynomial hugatsaand bodogdoj chadah uu? gesen asuult suuliin 30,40 jil computer scientist, matyematikchid hariulj chadahgui baigaa yum.

Hamgiin sonirholtoi ni NP torold ih sonin bodloguud baidag. Jishee 3-SAT, Hamiltonian Path, TSP geh met (NP-Complete problems). Edgeer bodlogiin zovhon negiig ni polynomial hugatsaand bodoj chadval NP -d baih alivaa bodlogiig mon polynomial hugatsaand bodoj chadna. (ene bol Cook-Levin theorem gej baigaa)

Iimees P=NP gej batlaval ihenh hetsuu gesen bodloguud amarhan bolno doo, computer-aar humuus mash olon yumiig mash hurdan hugatsaand hiij chaddag bolno. Gevch burhan bid nart tiim ch amarhan amidral hairlaagui bailgui dee. Iimees ihenh erdemted P NP tentsuu bish gedegt itgedeg.

P!=NP gesen asuultand hariulaad bid nar yund hureh yum bee. Uuniig hariulahiin tuld tootson bodoh tohooromj gej yuu vee gedgiig mash sain oilgoh baih daa. Yavj yavj hun torolhton chn ertontsiin unen gej yuu ve gej oilgohiin tuld orshin togtnoj baigaa shuu dee.

_________________
Work hard, play hard!


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.25.10 1:37 pm 
Offline
¤ Expert
User avatar

Joined: Apr.13.02 9:20 pm
Posts: 6224
Location: Henti aimgiin Galshar sumiin uyach Bazarwaaniin gert
goyo heljee

ter P-g oruulj irj bga ni jaahan sonin sanagdlaa. jishee ni neg bodlogo bailaa gehed tuuniig O(n^2) hugatsaand shiidej boloh uu gedeg bol chuhal asuult shuu dee. tuhailbal NxN matrix-iin urvuug O(n^2) hugatsaand olj boloh uu geed hetsuu bodlogo bn. P-g avch uzdeg ni zugeer mash olon bodlogiig zereg avch uzeh (u.h. mash yurunhii onol bii bolgoh) bolomj olgodog bolohoor tegj bga yum bish uu?

_________________
http://t8m8r.wordpress.com


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.25.10 2:51 pm 
Offline
Өвөг Дээдсийн Сахиус Гишvvн
Өвөг Дээдсийн Сахиус Гишvvн
User avatar

Joined: Dec.30.02 10:46 pm
Posts: 744
Quote:
goyo heljee

ter P-g oruulj irj bga ni jaahan sonin sanagdlaa. jishee ni neg bodlogo bailaa gehed tuuniig O(n^2) hugatsaand shiidej boloh uu gedeg bol chuhal asuult shuu dee. tuhailbal NxN matrix-iin urvuug O(n^2) hugatsaand olj boloh uu geed hetsuu bodlogo bn. P-g avch uzdeg ni zugeer mash olon bodlogiig zereg avch uzeh (u.h. mash yurunhii onol bii bolgoh) bolomj olgodog bolohoor tegj bga yum bish uu?
zov hellee!! "utgagui asuult" gesen ugee tegvel butsaj avya. minii heleh gesen sanaa bol yamar tohooromj songoj avsnaasaa shaltgaalaad O(n^k) -iin ter togtmol too k ni oor oor baina gesen yum. nXn matrix-iin urvuug zugeer ram model deer O(n^3) hiij chadah bolovch, harin Turing machine deer bol O(n^7) (7-g zugeer ayulguin uudnees songoloo. magadgui n^5-d hiij magadgui, gehdee hamaagui l dee) hiij chadah bolovch, harin O(n^3) hiij chadah ni todorhoi bish (lav l nadad todorhoi bish)

tiimee ali boloh eronhii onol bii bologohiin tuld P-g gargasan baih.

_________________
Work hard, play hard!


Top
   
 Post subject: Yu
PostPosted: Aug.25.10 3:11 pm 
Offline
Asuult Precious Member
User avatar

Joined: Apr.12.02 10:54 pm
Posts: 3716
Location: Insulin shock therapy
ih hetsuu yumiig engiineer tailbarlajee. oilgohuu baisnaa oilgochloo. bayarlalaa


Top
   
 Post subject: Re: Yu
PostPosted: Aug.25.10 3:26 pm 
Offline
Өвөг Дээдсийн Сахиус Гишvvн
Өвөг Дээдсийн Сахиус Гишvvн
User avatar

Joined: Dec.30.02 10:46 pm
Posts: 744
Quote:
ih hetsuu yumiig engiineer tailbarlajee. oilgohuu baisnaa oilgochloo. bayarlalaa
okay tegvel bodlogoo oilgoson bol odoo batla daa!!

_________________
Work hard, play hard!


Top
   
 Post subject: Yu
PostPosted: Aug.25.10 3:32 pm 
Offline
Asuult Precious Member
User avatar

Joined: Apr.12.02 10:54 pm
Posts: 3716
Location: Insulin shock therapy
batalchuul say $ avchih geed baigaa biz?


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.25.10 10:46 pm 
Offline
¤ Expert
User avatar

Joined: Apr.13.02 9:20 pm
Posts: 6224
Location: Henti aimgiin Galshar sumiin uyach Bazarwaaniin gert
$-aas aidag hun neg shirheg bn aa end

_________________
http://t8m8r.wordpress.com


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.25.10 10:55 pm 
Offline
¤ Expert
User avatar

Joined: Apr.13.02 9:20 pm
Posts: 6224
Location: Henti aimgiin Galshar sumiin uyach Bazarwaaniin gert
Quote:
zov hellee!! "utgagui asuult" gesen ugee tegvel butsaj avya. minii heleh gesen sanaa bol yamar tohooromj songoj avsnaasaa shaltgaalaad O(n^k) -iin ter togtmol too k ni oor oor baina gesen yum. nXn matrix-iin urvuug zugeer ram model deer O(n^3) hiij chadah bolovch, harin Turing machine deer bol O(n^7) (7-g zugeer ayulguin uudnees songoloo. magadgui n^5-d hiij magadgui, gehdee hamaagui l dee) hiij chadah bolovch, harin O(n^3) hiij chadah ni todorhoi bish (lav l nadad todorhoi bish)

tiimee ali boloh eronhii onol bii bologohiin tuld P-g gargasan baih.
aan Turing mashin dee k ni uur boldog gedgiig medeegui yum bn. odoo bodohod bol oilgomjtoi bn. minii helsen matrixiin urvuug oldog bodlogo O(n^2) gedeg taamaglal ni real number model (ene chinii heleed bga ram modeltai adilhan bj magadgui) deer yarij bga bh. 2 matrixiig O(n^2)-s urjuulj chadval ene bas shiidegdene. O(n^3)-ees onoliin huvid hurdan algorithmuud gevel Strassenii O(n^2.81), Coppersmith-Winogradiin O(n^2.34) geed bga. sayahan microsoft-iin heden nuhud ene bodlogiig bulgiin onoliin bodlogond huvirgasan.

_________________
http://t8m8r.wordpress.com


Top
   
 Post subject: Yu
PostPosted: Sep.10.10 6:03 pm 
Offline
Asuult Precious Member
User avatar

Joined: Apr.12.02 10:54 pm
Posts: 3716
Location: Insulin shock therapy


Top
   
 Post subject: Re: P=NP?
PostPosted: Aug.06.19 6:07 pm 
Offline
Ноёлон Ноёрхогч Гишvvн
Ноёлон Ноёрхогч Гишvvн

Joined: Sep.25.15 10:11 pm
Posts: 1053
Location: Хавтгай дэлхий
Энийгээ сайн тайлбарлаж өгнө үү.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 43 posts ]  Go to page Previous 1 2

All times are UTC+09:00


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Copyright Asuult.NET © 2000-2015.
Administrative Contact: Khundaga Khurelbaatar [hundaga@hotmail.com]
Tel: 1-888-303-4927, Fax: 1-888-406-2264.
Powered by phpBB © 2000-2015 phpBB Group. Powered by phpBB® Forum Software © phpBB Limited