802.16 IP Telephony Lab會議紀錄 時間:105年01月28日14:15 地點:國立暨南國際大學科三館113教室 主講人:楊凱博 紀錄:林嘉緯 出席者:吳坤熹老師、楊國呈、陳冠筑、王詠瑜、江俊杰 會議主題: Introduction to NP-complete . The relationship between Tai-yi schedule and Memory management . 摘要: Motivation Classification problem NP Relationship between Tai-yi schedule and Memory management Conclusion 問題: Q1 : 為什麼數獨是NP-Complete,圍棋不是?(老師) ans : 是從過程著手。 Q2 : 如何判斷這個問題是NP-Complete或是NP Hard?(老師) ans : P的定義是存在Polynomial time可以解決他;NP是表示所有的問題都可以reduce給NP-Complete;若有一個問題不確定是不是能reduce成NP-Complete,稱為NP-Hard。所以圍棋應該什麼都不算是。(老師) Q3 : 用Virtual memory 有什麼好處?是怎樣的Share方式(老師) ans : 假設每份Process A,B,C都是3K,輪流使用,這樣就是每份3K而不是總共9K。 ans : 當記憶體不夠的時候,若B要使用,就先將A空出來寫進硬碟,然後LOAD B,所以這時記憶體和硬碟都會很忙。因此當記憶體不足時、硬碟也一直在閃,要解決這個問題增加記憶體就好了(老師),用軟體的方式解決問題。 Q4 : Reference bit and Modify bit問題 - B、C同時寫進A時,應該保留誰? ans : 應該要留B,因為寫進比較早 其實事實不會這樣處理。應該是有一個記憶體模組,看你要多少就給你多少,不是讓你自己在那邊搶,就像餐廳會有Waiter帶位一樣。這個模組可以想像成Function。(老師) Q5 : p.12頁的First-in-first-out是如何?(國呈) ans : 不是queue,也不是LRU(0剛被用過不應該被擠掉,才是LRU),是circular。為什麼不用Linked list?因為overhead太大了。當我們在電腦上的時候沒感覺記憶體不夠,但若是embaded system就有這樣的問題,用array就可以完成就不要用pointer指來指去。 Q6 : 為什麼用First-in-first-out而不是用LRU和OPT?(俊杰) ans : 因為台一是First-in-first-out的精神,所以才選他。 因為農業不可能像記憶體管理這樣做,要避開Virtual Memory。 Q7 : p.7 A應該不能reduce到B吧?這張圖是否有錯(詠瑜) ans : 所有的問題都可以reduce。這張圖沒錯 Q8 : p.7 NP-Complete的敘述是要表達什麼?(冠筑) ans : 所有NP的問題都可以被reduce成任意一個NP-Complete,可以在Polynomial time被解決。 NP-Complete是證明這個問題很難被解決(老師) 建議: 1.英文定冠詞是描述"特定"的名詞,這是常犯的錯誤。(老師) 2.舉生活化的例子很好,但舉錯例子就達到不好的效果。(老師) 3.連在電腦裡面都不知道怎麼運作的話就舉農業的實際例子的話是有問題的,要先讓大家讓知道如何在電腦裡面運作。(老師) 4.CPU time-sharing是一個CPU能一次做很多事情的假象,其實一次只能做一件事情。 5.Lab Meeting是每個星期大家有學東西覺得很精彩,想要來分享讓別人可以聽懂或是至少聽懂是什麼問題,希望在Lab Meeting的時候可以練習如何表達給別人聽。(老師) 6.PowerCam 的用法其實是在Meeting前可以先錄起來讓自己聽聽看,不是報告完作後才聽。(老師) 7.必須用對方熟悉的語言來描述概念,才能幫助對方了解、對他有幫助,這就是所謂的"圓融" : 將問題用對方熟悉的語言講給對方聽。(老師) 8.為了不要只低頭寫程式、跟印度人一樣,要培養實作、創新、表達能力。 9.學到一個新的東西,問完what之後,弄懂後要想why?why not?可以幫助自己學得更好。(老師) 10.農業上的問題不能用Virtual Memory。(老師) 11.NP-Complete有它有趣的地方,但簡報中並沒有顯示出來,若單一主題分開講可能大家收穫會比較多,有的時候少就是多。