one of those days when i'm too tired to do anything enjoyable. :)
it has been fulfilling, but exhausting as well.
so i wander like many, upon other blogs and what not.
ALGORITHM (CARA SELESAI MASALAH) algorithm ni adalah cara 'jelas' nk selesaikan satu masalah. misalnya, ko nk x leh drive sbb xde lesen. so cara jelas nk dapat lesen ialah S1, S2, S3 dimana .. S1) amik kelas memandu S2) amik ujian teori S3) amik ujian praktikal
POLYNOMIAL TIME (MASA AMIK TUK SELESAI MASALAH) ni rujuk pada masa yg ko PERLU untuk selesaikan masalah. polynomial time ni kira cepat la sbb masa T = X^N dimana N tu constant. maksudnya, masa utk dpt lesen tu x lah amik byk sgt masa sampai ko x mampu nak amik banding masa ko idup kat bumi ni.
ni baik banding dgn exponential time dimana masa T = N^X iaitu masa bertambah dgn mendadak bila X bertambah.
jumlah naik bila X naik tapi mendadak gila. ko tengok daripada 100 ke 1000 ke 10000.
ALGORITHM AND TIME jadi skang ni penting utk pertimbang 1) masa yg amik utk selesai masalah 2) masa yg amik utk periksa / check samada jawapan betul ke tidak.
NP-COMPLETE utk jadi NP complete ada 2 syarat ..
1) NP ni ialah masa utk check samada jawapan yg dapat daripada cara ko selesai masalah tu betul ke tidak. masa check ni perlu cepat ie polynomial time. dalam kes ni, katakanlah ko dah dapat lesen. lama x utk check lesen ko? tak lama kot.. ko tunjuk lesen kat aku, kira dh bukti la masalah dh settle. so masalah ni kira NP.
2) NP HARD ni jenis masalah yg makan masa dan x boleh settle kejap. katakanlah ko dpt lesen dgn cara ko rasuah tempat memandu tu. mungkin aku boleh check samada ko betul atau tidak rasuah kejap je. aku leh tanya ko sendiri. bro, betul ke ko sogok mamat tu?
tapi.. nak buktikan yg ko betul rasuah dan amik tindakan undang-undang terhadap ko kat mahkamah amik masa yg lama. kenapa? sbb susah nk dpt pengakuan drpd ko dan tempat memandu. susah nk buktikan bende yg xde hitam putih ni kat mahkamah.
so NP-COMPLETE ni ialah cara selesai masalah yg.. 1) nk check jawapan betul ke tidak cepat, 2) tapi nak cari jawapan atau penyelesaian sgt lambat.
cam nk check org rasuah ke tak la, mungkin cepat. tapi nak bukti dan dakwa dia kat mahkamah mmg leceh, lambat dan tak tau bila akan settle.
Oooo gitu...instinctively pun maknanya P x kan sama ngn NP la...tp sbb blum ada math proof je la lg. sejuta usd tu hadiah dia huhu (milenium prize) Thanx
ur entry mmg berbunga2.. puas nk fhm aceh. duk pekiak lg.. haha
ReplyDeletelol berbunga, ye ke? intipatinya x ade bunga langsung kot. :)
ReplyDeletepenat tul hari ni.
banyak bende setel, tapi mmg ponat.
x larat nk buat pape, so tgk-tgk blog org je.
u create ayat mcm berbunga2 lau ditukar kpd bm.. pdhl sy ni mmg xpndai nk wt ayat bi2 ni.. haha.. sila tunjuk aja :D
ReplyDeleteSalam
ReplyDeleteaku baca the star ruangan dzof azmi ada mention phrase "NP complete"
Boleh explain kan? Klu buleh mcm ko explainkan incompleteness tempohari
ok, in shaa Allah aku cuba explain step by step
DeleteALGORITHM (CARA SELESAI MASALAH)
algorithm ni adalah cara 'jelas' nk selesaikan satu masalah. misalnya, ko nk x leh drive sbb xde lesen. so cara jelas nk dapat lesen ialah S1, S2, S3 dimana ..
S1) amik kelas memandu
S2) amik ujian teori
S3) amik ujian praktikal
POLYNOMIAL TIME (MASA AMIK TUK SELESAI MASALAH)
ni rujuk pada masa yg ko PERLU untuk selesaikan masalah. polynomial time ni kira cepat la sbb masa T = X^N dimana N tu constant. maksudnya, masa utk dpt lesen tu x lah amik byk sgt masa sampai ko x mampu nak amik banding masa ko idup kat bumi ni.
ni baik banding dgn exponential time dimana masa T = N^X iaitu masa bertambah dgn mendadak bila X bertambah.
contoh?
polynomial time = X^2
10^2, 20^2, 30^2 ...
100, 400, 900
jumlah naik bila X naik tapi tak la mendadak sgt.. sbb naik pun ratus-ratus je.
exponential time = 10^X
10^1, 10^2, 10^3, 10^4
10, 100, 1000, 10000
jumlah naik bila X naik tapi mendadak gila. ko tengok daripada 100 ke 1000 ke 10000.
ALGORITHM AND TIME
jadi skang ni penting utk pertimbang
1) masa yg amik utk selesai masalah
2) masa yg amik utk periksa / check samada jawapan betul ke tidak.
NP-COMPLETE
utk jadi NP complete ada 2 syarat ..
1) NP
ni ialah masa utk check samada jawapan yg dapat daripada cara ko selesai masalah tu betul ke tidak. masa check ni perlu cepat ie polynomial time. dalam kes ni, katakanlah ko dah dapat lesen. lama x utk check lesen ko? tak lama kot.. ko tunjuk lesen kat aku, kira dh bukti la masalah dh settle. so masalah ni kira NP.
2) NP HARD
ni jenis masalah yg makan masa dan x boleh settle kejap. katakanlah ko dpt lesen dgn cara ko rasuah tempat memandu tu. mungkin aku boleh check samada ko betul atau tidak rasuah kejap je. aku leh tanya ko sendiri. bro, betul ke ko sogok mamat tu?
tapi.. nak buktikan yg ko betul rasuah dan amik tindakan undang-undang terhadap ko kat mahkamah amik masa yg lama. kenapa? sbb susah nk dpt pengakuan drpd ko dan tempat memandu. susah nk buktikan bende yg xde hitam putih ni kat mahkamah.
so NP-COMPLETE ni ialah cara selesai masalah yg..
1) nk check jawapan betul ke tidak cepat,
2) tapi nak cari jawapan atau penyelesaian sgt lambat.
cam nk check org rasuah ke tak la, mungkin cepat.
tapi nak bukti dan dakwa dia kat mahkamah mmg leceh, lambat dan tak tau bila akan settle.
Oooo gitu...instinctively pun maknanya P x kan sama ngn NP la...tp sbb blum ada math proof je la lg.
ReplyDeletesejuta usd tu hadiah dia huhu (milenium prize)
Thanx