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

[Transfat (Transfat)]

[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
推 boy00114: 第三題，畫出sin cos的圖出來大概就知道不一定對了
推 boy00114: 第二題我是用背的2-cnf是p,3-cnf是npc@@
推 w181496: 9.在一般graph上是NPC不代表在interval graph上也是NPC
推 w181496: 10. 2-SAT是P 可以建成graph 用SCC之類的判斷有無解
→ aa06697: 印象中沒有規定clique要多少點 所有只要有一個點 就有cli
→ aa06697: que
→ aa06697: 104交大22 三角函數沒辦法決定上下界
→ yupog2003: 第四題感覺在考英文，應該是save register content
→ yupog2003: 而不是preserve，preserve register content好像是在說
→ yupog2003: 把register的內容保留在register內不要動，save則是存
→ yupog2003: 到記憶體裡面
→ yupog2003: 這樣解釋不知道可不可以？自己也覺得毛毛的...
→ ken52011219: 104 台大os 那是dispatch 的工作
→ Transfat: 最後一題好奇怪，如果我畫一個3-node的complete graph,
→ ken52011219: Interrupt handling 主要工作是查詢interrupt vector
→ Transfat: 他的complement不就沒有clique了嗎
→ ken52011219: 102 台大資演 因為題目有說 非空 graph
→ Transfat: 好>< 謝謝你們
推 aa06697: clique是子圖呀 所以我的意思是 非空團的補圖至少會有一
→ aa06697: 點 而clique印象中沒有說要多少點才算 所以一個點也可以
→ aa06697: 說是clique(就像是完全圖的補圖 你可以說每個點都是compo
→ aa06697: nent)
→ Transfat: 是我觀念哪裡錯了嗎，完全圖的補圖不就是一個點都沒有了
→ Transfat: ？他這邊的非空是說G是非空，還是連補圖G' 都要是非空？
→ ken52011219: 補圖G 要非空
→ ken52011219: 你觀念沒錯，但非空為題目多加的條件
→ gary19941208: 完全圖的補圖是只有點沒有邊吧，補圖不影響點
推 w181496: 樓上正確 非空圖的補圖至少有大小1的clique 補圖只影響
→ w181496: 邊
→ ken52011219: 哦哦了解
→ Transfat: 哦哦原來如此，補圖就是把原本沒有adjacent的邊連起來,
→ Transfat: 可是|V|=|V'|,點還是一樣多
推 adplz53: y大說的不是preserve而是save那個應該沒錯 之前老師上課
→ adplz53: 也是這樣講
→ ken52011219: 摁..沒錯，如y大和a大所說，題目只是單純講 它們「ne
→ ken52011219: ed」是我想的太跳躍了
→ ken52011219: 剛剛剛好翻到恐龍本
→ ken52011219: http://i.imgur.com/7p7GK5E.jpg
→ ken52011219: 它是用preserve來表達將資料保留
→ ken52011219: 哦哦 沒事, address space 和 registered還是有差
→ yupog2003: 坦白講這種題目看到答案可以解釋，考試的時候未必會寫
→ yupog2003: 得出正確答案，成大電通有一題計組在考rather than跟
→ yupog2003: other than的不同，第一次看到我還真的想很久還寫錯
→ ken52011219: 考試當下 有時間壓力沒看過就只能靠平常的邏輯思考QQ
→ yupog2003: 剛剛還認真去查preserve跟save在英文上的不同，解答是
→ yupog2003: 對native speaker來說這兩個可以交替使用，精確一點來
→ yupog2003: 說，save有避免受到傷害以及救援的意思，preserve則是
→ yupog2003: 保持一個東西的現在狀態，考試的時候真的要靠慧根了XD