算法在計(jì)算機(jī)科學(xué)中的角色

算法是計(jì)算機(jī)科學(xué)的主題
解決一個(gè)計(jì)算問題的過程：
可計(jì)算否---》能行可計(jì)算否---》算法設(shè)計(jì)與分析---》用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)算法---》軟件系統(tǒng)
可計(jì)算理論
--計(jì)算模型
--可計(jì)算問題、不可計(jì)算問題
--計(jì)算模型的等價(jià)性--圖靈/church命題
計(jì)算復(fù)雜性理論
--在給定計(jì)算模型下研究問題的復(fù)雜性
*固有復(fù)雜性
*上界
*下界
*平均
*復(fù)雜性問題分類
*抽象復(fù)雜性研究

算法的概念

算法的定義

• 計(jì)算：可有一個(gè)給定計(jì)算模型機(jī)械地執(zhí)行規(guī)則或計(jì)算步驟序列成為該計(jì)算模型的一個(gè)計(jì)算。
  一個(gè)計(jì)算機(jī)程序是一個(gè)計(jì)算（計(jì)算模型是計(jì)算機(jī)）
  計(jì)算可能永遠(yuǎn)不停止——不是算法
• 算法：滿足
  有窮性：有限步內(nèi)必須停止
  確定性：每一步都是嚴(yán)格定義和確定的動(dòng)作
  能行性：每一個(gè)動(dòng)作都能夠被精確地機(jī)械執(zhí)行
  輸入：有一個(gè)滿足給定約束條件的輸入
  輸出：滿足給定約束條件的結(jié)果
• 問題：是算法的目的。定義了輸入集合和輸出集合的映射關(guān)系。
• 問題實(shí)例：一個(gè)算法面向一個(gè)問題，而不是僅求解一個(gè)問題的一個(gè)或幾個(gè)實(shí)例。

算法的分析

算法的正確性分析

• 算法正確性：算法對(duì)于每一個(gè)輸入都最終停止，而且產(chǎn)生正確輸出。
  不正確算法：不停止（在某個(gè)輸入上）。對(duì)所有輸入都停止，但對(duì)某輸入產(chǎn)生不正確結(jié)果
  近似算法：對(duì)所有輸入都停止。產(chǎn)生近似正確的解或產(chǎn)生不多不正確解。
• 算法正確性證明：證明算法對(duì)所有輸入都停止，證明對(duì)每個(gè)輸入都產(chǎn)生正確結(jié)果。
  調(diào)試程序不等于程序正確性證明。調(diào)試程序只能證明程序有錯(cuò)，不能證明程序無(wú)錯(cuò)。
• 循環(huán)不變量方法——證明主要結(jié)構(gòu)是循環(huán)結(jié)構(gòu)的算法正確性。
  循環(huán)不變量：數(shù)據(jù)或數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵性質(zhì)，依賴具體算法和算法的特點(diǎn)。
  初始：循環(huán)開始前循環(huán)不變量成立。
  循環(huán)步驟：循環(huán)體每執(zhí)行一次，循環(huán)不變量成立。
  終止：算法結(jié)束后，循環(huán)不變量保證算法正確。

算法的復(fù)雜性分析

• 目的：預(yù)測(cè)算法對(duì)不同輸入所需的資源量
• 復(fù)雜性測(cè)度：時(shí)間，空間，I/O等，是輸入大小的函數(shù)。
  *其他概念：輸入大小，時(shí)間復(fù)雜度性，空間復(fù)雜性，最壞復(fù)雜性，最小復(fù)雜性，平均復(fù)雜性。