專題一 計算機科學基礎(chǔ)

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

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

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