作者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/cn.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