作者w831231 (tsai)
看板Grad-ProbAsk
標題[理工] 中央106資演
時間Thu Feb 8 07:24:11 2018
感覺第五題等等會考
但是該怎麼証呢 拜託大家了@@
https://i.imgur.com/sfoIjSa.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.59.25
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1518045853.A.706.html
※ 編輯: w831231 (42.72.59.25), 02/08/2018 07:24:36
1F：推 leoone: 證Y不屬於NP但是是NP complete 02/08 08:02
2F：→ w831231: 可講的詳細點嗎 謝謝 02/08 08:39
3F：推 TMDTMD2487: 就把你證明的方法跟理論基礎講出來呀 02/08 08:40
4F：推 pinchieh1996: 搜105 中央 有一篇在對答案 02/08 08:41
5F：→ pinchieh1996: 一模一樣的題目 02/08 08:41
6F：→ TMDTMD2487: 她問你要怎麼證明y是hp hard你就把證法講一下就好 02/08 08:42
7F：→ w831231: 謝謝大大門 02/08 08:42
8F：→ TMDTMD2487: 理論基礎像是np hard定義是所有np都可以reduce到它 02/08 08:42
9F：→ TMDTMD2487: 而np complete的定義是既是np又是np hard 02/08 08:43
11F：→ TMDTMD2487: 所以只要把x reduce到y就代表你可以吧所有的np reduce 02/08 08:44
12F：→ TMDTMD2487: 到y 如此得證y是np hard 02/08 08:44
13F：→ w831231: 感謝T大 02/08 08:44
14F：→ TMDTMD2487: 這沒考reduce考觀念而已算基本的 02/08 08:44
16F：→ w831231: 感謝感謝 02/08 08:46
17F：推 TMDTMD2487: 把p, np, np complete, np hard定義搞清楚就沒這麼難 02/08 08:46
18F：→ TMDTMD2487: 了 02/08 08:46
19F：推 leoone: 中央很愛考 這四年考了3年 真的不會就背起來吧 02/08 08:58
20F：推 gR7P4zXH: 好 02/08 09:07
21F：推 agag5123: 幹 考完馬上發現腦殘了，最後最短路徑演算法是小於 02/08 11:16
22F：推 moneylon: 你是說20.21題嗎 02/08 11:18
23F：推 TMDTMD2487: 最後是我才學術淺嗎 02/08 11:19
24F：→ TMDTMD2487: 我不知道大於要怎麼做 02/08 11:19
25F：→ TMDTMD2487: 不對應該是我他的選項大小於跟我想的相反 02/08 11:19
26F：推 gR7P4zXH: 先知 02/08 11:20
27F：推 moneylon: 對 我也是 我覺得是大於 可是選項沒有... 02/08 11:20
28F：→ devilkool: 我也想半天想不出哪個選項能選 求解 02/08 11:21
29F：推 TMDTMD2487: 然後我抓到他heap sort那個建heap他寫錯應該是i-- 02/08 11:21
30F：推 moneylon: 對 02/08 11:22
31F：→ TMDTMD2487: 我當作題目大於小於寫反了在答 02/08 11:22
32F：→ moneylon: 不然他一直加加 判斷大於0就會一直跑 02/08 11:22
33F：推 tcc080206: 還有quicksort A[i]應該找>pivot，A[j]應該是<pivot的 02/08 11:22
34F：→ tcc080206: 吧。然後用adjust調整heap，後面不是應該是i--嗎？ 02/08 11:22
35F：→ TMDTMD2487: 整體而言不難 話說河內塔是39嗎我找不到更短的 02/08 11:23
36F：推 tcc080206: 39+1 02/08 11:24
37F：推 agag5123: 我也是39 02/08 11:24
38F：推 age01282005: 1+7+31=39 02/08 11:25
39F：推 havewind: 河內塔也算39 02/08 11:26
40F：推 TMDTMD2487: 他選想給不好 有給40的話我會不小心選到ww 02/08 11:26
41F：推 wei5280: 那個i++怎麼算啊 這樣是送分嗎 02/08 11:28
42F：推 shownlin: 最後一題bellman ford是不是怪怪的 02/08 11:28
43F：推 agag5123: 除3的那個sort複雜度是多少啊？ 02/08 11:28
44F：推 TMDTMD2487: 做後一題不是floyd warshall嗎 02/08 11:30
45F：→ TMDTMD2487: tn=3t(2n/3) 我印象中時間遞迴漲這樣 02/08 11:31
46F：推 microchianag: 先知 02/08 11:32
47F：推 moneylon: logn 3/2的3. 我寫這樣 02/08 11:32
48F：→ TMDTMD2487: 我覺得建立heap不會送不過最後幾題就不知道了 02/08 11:32
49F：推 agag5123: 謝謝 我也是選那項 02/08 11:32
50F：→ moneylon: 說錯 是 n的log3/2 3 02/08 11:32
51F：→ TMDTMD2487: 空間是n嗎 02/08 11:33
52F：→ moneylon: 所以T大的i寫 i=n/2嗎 02/08 11:33
53F：→ TMDTMD2487: 對啊雖然+1跟沒加執行結果應該是一樣的 02/08 11:34
54F：推 HungDa: 額外空間有需要n？ 02/08 11:35
55F：推 TMDTMD2487: 我算了stack用的空間 02/08 11:35
56F：→ TMDTMD2487: 想說到底是多少不過現在想想應該小於n 02/08 11:36
57F：→ TMDTMD2487: 要應該也是log的等級 02/08 11:36
58F：→ TMDTMD2487: 應該是logn現在想了一下 02/08 11:37
59F：推 lion83395: 我寫Logn 不過不是很確定 02/08 11:37
60F：→ TMDTMD2487: 我那時不小心連array也存到stack就變n了QQ 02/08 11:38
61F：推 king8313: 我也在猶豫遞迴用的空間要不要算 02/08 11:38
62F：推 leoone: 我怎麼覺得我中央有點爆炸 第一題寫log2 3QQ 02/08 11:39
63F：推 Xunion: 你不可以有台大了就這樣讓分r 02/08 11:41
64F：推 TMDTMD2487: 有台大就很囂張QQ 02/08 11:42
65F：推 leoone: 別說台大惹 想到就傷心 02/08 11:44
66F：推 jimmy45689: 想問一下np那幾題答案多少 我有連續兩題寫abce 因為 02/08 11:45
67F：→ jimmy45689: 當初有點想放沒讀很熟 02/08 11:46
68F：推 moneylon: leo大台大電機比80%的人多10分 2^10000 02/08 11:46
69F：推 ReanoX: Stack的空間不用算嗎？我選n呢QQ 02/08 11:47
70F：推 leoone: 可4馬跟asymmetric錯惹 -15 02/08 11:48
71F：推 djmez: 至少有兩題程式碼有問題 只是連考卷都收走了讓你也沒辦法 02/08 11:48
72F：推 ReanoX: 而且那題Heap看到i ++我直接選I=0不要進for XD 02/08 11:49
73F：推 TMDTMD2487: 你不能跟教授打錯字過不去啊XD 02/08 11:50
74F：→ djmez: 河內塔根本懶的算 直接放了 02/08 11:51
75F：推 HungDa: 中央教授好爽電腦閱卷都不用改,而且自己應該沒對過考卷 02/08 11:54
76F：推 TMDTMD2487: 不錯了 跟昨天的電機丙比... 02/08 11:55
77F：推 moneylon: 別提那四隻馬了 02/08 11:56
78F：→ gR7P4zXH: ???? 02/08 11:57
79F：推 harryboy23: 河內塔好像是把12345疊在B後 6移到C 7回合 再移動1234 02/08 12:05
80F：→ harryboy23: 5就好 所以是7+2^5-1=38 ？？ 02/08 12:05
81F：推 shownlin: 對 floyd-warshall 打錯XD 02/08 12:11
82F：推 HungDa: 話說我看到有人帶整本演算法來看整個眼神死 02/08 12:17
83F：推 agag5123: 123放在45上就要7步了。另外heap那題我直接背誒，印象中 02/08 12:17
84F：→ agag5123: 是從最後一個父點作adjust 02/08 12:17
85F：→ djmez: 可是他一直加加還>0 不給結束了 02/08 12:21
86F：推 Dora5566: 應該是i--打錯成i++ 02/08 12:22
87F：推 MOUOREO: 123放到45 要7步 然後6放到最右邊一步 02/08 16:22
88F：→ MOUOREO: 再加31 共39步？ 02/08 16:23
89F：推 jacky804024: Leo大 有台大了 中央就亂考 02/08 18:07
90F：推 leoone: 到底是誰說我有台大QQ 我自己怎都不知道 02/09 00:14