專題一 計算機科學基礎

1、專題一專題一計算機科學基礎計算機科學基礎【主要內容主要內容】1基礎知識2可計算性3計算復雜性4求解NP問題的基本思路5進一步理解NP問題一、簡介一、簡介某些問題很難計算，又使另一些問題容易計算？這是復雜性理論的核心問題。值得注意的是，雖然在過去的二十多年里對它進行了深入細致的研究，但是我們仍然不知道它的答案。以后我們將探究這個迷人的問題和它的一些分支。迄今為止，復雜性理論的一個重要成果是，發(fā)現(xiàn)了一個按照計算難度給問題分類的完美體系。它類

2、似按照化學性質給元素分類的周期表。運用這個體系，我們能夠提出一種方法給出某些問題是難計算的證據(jù)，盡管還不能證明它們是難計算的。當你面對一個看來很難計算的問題時，有幾種選擇。首先，搞清楚問題困難的原因，你可能會做某些變動，使問題變的容易解決。其次，你可能會求出問題的不那么完美的的解。在某些情況下，尋找問題的近似解相對容易一些。第三，有些問題僅僅在最壞的情況下是困難的，而在絕大多數(shù)的時候是容易的。就應用而言，一個偶爾運行得很慢、而通常運行得

3、很快的過程是能夠令人滿意的。最后，你可以考慮其他類型的計算，如隨機計算，它能夠加速某些工作。受到復雜性理論直接影響的一個應用領域是密碼技術，這是一個古老的研究領域。在絕大多數(shù)的情況下，容易計算的問題比難計算的問題更可取，因為求解容易的問題的代價要小。密碼技術與眾不同，它特別需要難計算的問題，而不是容易計算的問題。在不知道密鑰或口令時，密碼應該是很難破譯的。復雜性理論給密碼研究人員指出了尋找計算問題的方向，圍繞這些問題已經(jīng)設計出新的革命性