[理工] OS+演算法 四個問題

看板Grad-ProbAsk作者 (Transfat)時間7年前 (2017/01/01 17:40), 編輯推噓7(7推 0噓 41→)
留言48則, 8人參與, 最新討論串1/1
[103交大資演 9. (9)(10)] 判斷是P還是NPC (9) Find a maximum independent set in an interval graph Maximum independent set 不是可以從vertex cover reduced 來嗎？所以不是NPC? 答案 給是P, 不過我印象中上課老師說maximum independent set 是NPC problem (10) The 2-CNF satisfiability problem 我看Satisfiable probelm定義是：給定一個CNF, 判斷是否存在一組解使得此CNF為True, 若存在則稱此CNF為Satisfiable. 可是答案給2-CNF is P problem？ [104交大資演 22.(A)] For the two functions f(n) and g(n),either f(n)=O(g(n)) or f(n)=Big omega(g(n)) 答案說這敘述是錯，還有其他種可能？ [104台大電機OS] Interrupt handling need preserve the register contents of the interrupted processes 想問這敘述錯在哪？ [102台大電機資演] The complement graph of a non-empty graph must contain at least one clique 這敘述是對的？ 以上疑問，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483263600.A.861.html
推
01/01 17:44, , 1F
第三題，畫出sin cos的圖出來大概就知道不一定對了
01/01 17:44, 1F
推
01/01 17:47, , 2F
第二題我是用背的2-cnf是p,3-cnf是npc@@
01/01 17:47, 2F
推
01/01 18:11, , 3F
9.在一般graph上是NPC不代表在interval graph上也是NPC
01/01 18:11, 3F
推
01/01 18:19, , 4F
10. 2-SAT是P 可以建成graph 用SCC之類的判斷有無解
01/01 18:19, 4F
→
01/01 18:24, , 5F
印象中沒有規定clique要多少點 所有只要有一個點 就有cli
01/01 18:24, 5F
→
01/01 18:24, , 6F
que
01/01 18:24, 6F
→
01/01 19:17, , 7F
104交大22 三角函數沒辦法決定上下界
01/01 19:17, 7F
→
01/01 20:06, , 8F
第四題感覺在考英文，應該是save register content
01/01 20:06, 8F
→
01/01 20:06, , 9F
而不是preserve，preserve register content好像是在說
01/01 20:06, 9F
→
01/01 20:07, , 10F
把register的內容保留在register內不要動，save則是存
01/01 20:07, 10F
→
01/01 20:07, , 11F
到記憶體裡面
01/01 20:07, 11F
→
01/01 20:07, , 12F
這樣解釋不知道可不可以？自己也覺得毛毛的...
01/01 20:07, 12F
→
01/01 21:51, , 13F
104 台大os 那是dispatch 的工作
01/01 21:51, 13F
→
01/01 21:51, , 14F
最後一題好奇怪，如果我畫一個3-node的complete graph,
01/01 21:51, 14F
→
01/01 21:51, , 15F
Interrupt handling 主要工作是查詢interrupt vector
01/01 21:51, 15F
→
01/01 21:51, , 16F
他的complement不就沒有clique了嗎
01/01 21:51, 16F
→
01/01 21:58, , 17F
102 台大資演 因為題目有說 非空 graph
01/01 21:58, 17F
→
01/01 22:21, , 18F
好>< 謝謝你們
01/01 22:21, 18F
推
01/02 10:02, , 19F
clique是子圖呀 所以我的意思是 非空團的補圖至少會有一
01/02 10:02, 19F
→
01/02 10:02, , 20F
點 而clique印象中沒有說要多少點才算 所以一個點也可以
01/02 10:02, 20F
→
01/02 10:02, , 21F
說是clique(就像是完全圖的補圖 你可以說每個點都是compo
01/02 10:02, 21F
→
01/02 10:02, , 22F
nent)
01/02 10:02, 22F
→
01/02 12:02, , 23F
是我觀念哪裡錯了嗎，完全圖的補圖不就是一個點都沒有了
01/02 12:02, 23F
→
01/02 12:02, , 24F
？他這邊的非空是說G是非空，還是連補圖G' 都要是非空？
01/02 12:02, 24F
→
01/02 12:05, , 25F
補圖G 要非空
01/02 12:05, 25F
→
01/02 12:08, , 26F
你觀念沒錯，但非空為題目多加的條件
01/02 12:08, 26F
→
01/02 12:44, , 27F
完全圖的補圖是只有點沒有邊吧，補圖不影響點
01/02 12:44, 27F
推
01/02 13:03, , 28F
樓上正確 非空圖的補圖至少有大小1的clique 補圖只影響
01/02 13:03, 28F
→
01/02 13:03, , 29F
邊
01/02 13:03, 29F
→
01/02 13:07, , 30F
哦哦了解
01/02 13:07, 30F
→
01/02 13:52, , 31F
哦哦原來如此，補圖就是把原本沒有adjacent的邊連起來,
01/02 13:52, 31F
→
01/02 13:52, , 32F
可是|V|=|V'|,點還是一樣多
01/02 13:52, 32F
推
01/02 14:43, , 33F
y大說的不是preserve而是save那個應該沒錯 之前老師上課
01/02 14:43, 33F
→
01/02 14:43, , 34F
也是這樣講
01/02 14:43, 34F
→
01/02 15:01, , 35F
摁..沒錯，如y大和a大所說，題目只是單純講 它們「ne
01/02 15:01, 35F
→
01/02 15:01, , 36F
ed」是我想的太跳躍了
01/02 15:01, 36F
→
01/02 21:52, , 37F
剛剛剛好翻到恐龍本
01/02 21:52, 37F
→
01/02 21:53, , 38F
01/02 21:53, 38F
→
01/02 21:54, , 39F
它是用preserve來表達將資料保留
01/02 21:54, 39F
→
01/02 22:04, , 40F
哦哦 沒事, address space 和 registered還是有差
01/02 22:04, 40F
→
01/02 22:07, , 41F
坦白講這種題目看到答案可以解釋，考試的時候未必會寫
01/02 22:07, 41F
→
01/02 22:09, , 42F
得出正確答案，成大電通有一題計組在考rather than跟
01/02 22:09, 42F
→
01/02 22:09, , 43F
other than的不同，第一次看到我還真的想很久還寫錯
01/02 22:09, 43F
→
01/02 22:09, , 44F
考試當下 有時間壓力沒看過就只能靠平常的邏輯思考QQ
01/02 22:09, 44F
→
01/02 22:11, , 45F
剛剛還認真去查preserve跟save在英文上的不同，解答是
01/02 22:11, 45F
→
01/02 22:12, , 46F
對native speaker來說這兩個可以交替使用，精確一點來
01/02 22:12, 46F
→
01/02 22:12, , 47F
說，save有避免受到傷害以及救援的意思，preserve則是
01/02 22:12, 47F
→
01/02 22:13, , 48F
保持一個東西的現在狀態，考試的時候真的要靠慧根了XD
01/02 22:13, 48F
‣ 更多 Transfat 的文章
文章代碼(AID): #1OQCvmXX (Grad-ProbAsk)