whatyoushouldknow.ppt

What You Should Know 吳晉賢 助理教授 國立台灣科技大學 電子工程系 前言 歡迎研究生加入Embedded Computing and Applications Lab (嵌入式計算暨應用實驗室) 。 下面投影片的內容主要針對本實驗室的研究方向，問題的難度，相關論文研究的工具，以及碩士班畢業的條件。 希望大家可以在這邊學到有用的知識跟學問。 研究方向 下面列的是有興趣的領域: 嵌入式系統 (Embedded Systems) 多核心的軟硬體整合設計 (Multicore Hardware/Software Co-Design) 即時系統 (Real-Time Systems) 普及運算 (Ubiquitous Computing) 快閃記憶體管理 (Flash-Memory Storage Systems) 檔案儲存系統 (File Systems) 畢業要求 (碩士班為主) 有兩種畢業條件，選擇一種即可 做出好的研究論文 至少需完成10頁的2 column格式的英文論文 刊登於有審稿的國際會議或期刊上 做出好的建教合作計劃 若接建教合作計劃，須完成此計劃的目標 寫論文的工具 相關寫論文的工具. WinEdt及MikTex Visio 2002 Gnuplot .tw/aspac/reports/95/95006/ GhostScript GSview 英文論文寫作 “英文科技寫作 – 文法與修辭原則”, 作者是方克濤 問題的難度 請了解P、NP、NP-hard跟NP-Complete的不同。. P是這個問題可以被deterministic polynomial time Turing machines在多項式時間所解決。 NP是這個問題可以被nondeterministic polynomial time Turing machines在多項式時間所解決，且答案正確性可以在多項式時間被驗證。 如果L是NP-Hard，則對任何問題L’屬於NP，都可以將L’ reduce to L。 如果L是NP-Complete，代表L屬於NP-Hard且L是一個NP問題。 Reduction 我們說一個問題L’可以reduce to L，代表L的難度至少跟L’一樣。 我們知道存在很多NP-C的問題，像SAT，TSP，Bin-Packing, Knapsack…等的問題。 因此一個問題如果找不出最解時，可試著證明是否存在一個NP-C的問題可以reduce to你的問題。 若可，則代表你的問題跟NP-C一樣難，則肯定不存在有任何optimal solutions(最佳解法) ，否則P就是NP了。 解決問題的層次(一) Optimal Algorithms 一個問題如果是在P，則最好能證明你的解法是optimal(最佳) ，方法可能是數學歸納法或是反證法或是其它; 反證法通常先假設存在一個比你更好的方法，但最後要導出矛盾，如此就不存在比你更好的方法，因此你的就是最好的方法。 Approximation Algorithms 如果證明問題是一個NP-C，必然沒有optimal的解法，如果可以證明你的方法算出來的值可以離最佳解有特定的範圍時，我們就稱之; 例如2-approximation algorithm代表離最佳解在2倍的範圍。 解決問題的層次(二) On-Line Algorithms 有些問題的input是動態進來的，因此不可能看完所有的input再來運算，而這些問題可能很難或是NP-C的問題，對於解決這些問題的演算法稱為on-line algorithms，跟approximation algorithms一樣，on-line algorithms有時也會離最佳解有特定的範圍。例如，2-competitive代表離最佳解在2倍的範圍。 Heuristics Algorithms 如果我們找不到最佳解或者也沒法證明問題是一個NP-C，因此我們會提出一個可以解的方法，但又不能證明它離最佳解差幾倍。通常這類的方法需要透過實驗來驗證其可行性及優越性。 論文(一) 一般論文會分為會議(conference)論文跟期刊(journal)論文，在電資領域裡，好的論文大多出自於ACM跟IEEE。 一般投稿到會議論文，大概2~3個月內就會公佈結果，而期刊論文則需4個月到1年的期間才