專題一 計(jì)算機(jī)科學(xué)基礎(chǔ)

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

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

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