第2章認識計算學科教學要求掌握計算學科的基本概念；熟悉計算學科的知識體系、學科特性以及中國計算機科學與技術學科概況；了解計算學科的根本問題、學科形態和計算學科的典型問題.問題引出從原始的計算工具到現代的電子計算機，已發展成為一門新興學科——計算學科。那么，作為一門新興的綜合性學科，它是怎樣形成的？其根本問題是什么？具有哪些基本特性？計算學科包括哪些知識領域和研究范疇？這就是本章所要討論的問題.

教學重點本章主要討論計算學科的形成、計算學科的根本問題、主要特點、計算學科的3個形態；中國計算機科學與技術學科的專業設置、課程體系；計算學科中的經典問題等。

§2.1計算學科的基本概念

§2.4計算機軟件系統

§2.2計算學科的知識體系認識計算學科

§2.3計算機科學與技術學科本章教學內容§2.1計算學科的基本概念

1、什么是計算學科

《辭海》對學科的定義是：“①學術的分類。指一定科學領域或一門科學的分支，如自然科學中的物理學、生物學等，社會科學中的史學、教育學等；②教學的科目。指學校教學內容的基本單位，如中、小學的政治、語文、數學、外語等。”

2、計算學科的定義1985年春美國計算機學會（AssociationforComputingMachinery，ACM）和國際電子電氣工程師協會計算機學會（InstituteofElectricalandElectronicsEngineers-ComputerSociety，IEEE-CS）聯合組成攻關組，開始了對“計算作為一門學科”的存在性證明。通過4年的研究，1989年提出了報告。2.1.1計算作為一門學科

(1)計算作為一門學科的存在性證明：在這份報告中，第一次對計算學科及其核心問題給出了定義：計算學科是對信息描述和變換的算法過程（包括對其理論分析、設計、效率分析、實現和應用等）進行的系統研究。美國計算科學鑒定委員會（CSAB）發布的報告摘錄中強調了計算學科的廣泛性：“計算學科的研究，包括了從算法與可計算性的研究以及可計算硬件和軟件的實際實現問題的研究。這樣，計算學科不但包括從總體上對算法和信息處理過程進行研究的內容，也包括滿足給定規格要求的有效而可靠的軟硬件設計，包括所有科目的理論、研究、實驗方法和工程設計。”2.1.1計算作為一門學科

(2)整個學科核心課程詳細設計：報告《計算作為一門學科》勾畫出了計算學科的知識框架，給出了計算學科中二維定義矩陣的定義及其相關研究內容,從而將學科的主題領域與學科的3個學科形態（抽象、理論和設計）有機地聯系在一起。它通過主題領域劃分的方式為計算學科課程體系建設提供了基礎的指導思想，從而為科學制訂教學計劃奠定了基礎，避免了教學計劃設計中的隨意性。

(3)強調整個學科綜述性引導課程的構建：提出并解決了未來計算學科教育必須解決的整個學科核心課程問題以及整個學科綜述性引導(導論)課程的構建問題。使人們對整個學科認知科學化、系統化和邏輯化，有力促進對計算學科方法論的研究，推動計算學科的快速發展。

2.1.1計算作為一門學科

3、計算學科教程

《計算作為一門學科》報告對計算學科的發展起到了極大的推動作用。1991年，在該報告的基礎上，提交了關于計算學科的計算教程(ComputingCurricula1991,CC1991)報告。隨后相繼發表了CC2001、CC2004、CC2005等，形成了不同時期的“計算教程”。CC2004在原有的4個專業方向：

計算機科學、計算機工程、軟件工程、信息系統的基礎上，添加了信息技術專業方向。其中，CC2001提出了許多新的概念和主題領域新的劃分，為新學科教程的形成起到了承前啟后的重要作用。計算學科的二維定義矩陣如表2-1所示。2.1.1計算作為一門學科表2-1計算學科的二維定義矩陣三個過程學科主領域抽象理論設計1.離散結構（DS）集合論；數理邏輯；近世代數；圖論；組合數學等2.程序設計基礎（PF）程序設計結構；算法和問題求解；數據結構等3.算法與復雜性（AL）算法設計策略；算法分析；并行算法；分布式算法等。可計算性理論；計算復雜性理論；并行計算理論；密碼學等。算法及組合問題啟發式算法的選擇、實現和測試；密碼協議等4.體系結構（AR）布爾代數模型；電路模型；有限狀態機；硬件可靠性等。布爾代數；開關理論；編碼理論；有限自動機理論等。硬件單元；指令集的實現；差錯處理；故障診斷；機器實現等5.操作系統（OS）用戶可察覺對象與、內部計算機結構的綁定；子問題模型；安全計算模型等。并發理論；調度理論；程序行為和存儲管理的理論；性能模型化與分析等。分時系統；自動存儲分配；多級濕度；內存管理；文件管理；構建OS技術等。6.網絡計算（NC）分布式計算模型；組網;協議；網絡安全模型等。數據通信理論；排隊理論；密碼學；協議的形式化驗證等。排隊網絡建模；系統性能評估；網絡體系結構；協議技術等。7.程序設計語言（PL）基于各種標準的語言分類；語義模型；編譯器組件等。形式語言與自動機；圖靈機；形式語義學；近世代數等。特定程序設計語言；程序設計環境；翻譯技術；統計處理等。8.人機交互（HC）人的表現模型；原型化；交互對象的描述；人機通信等認知心理學；人機工程學；社會交互科學；人機界面等交互設備；圖形專用語言；交互技術；用戶接口；評價標準等。9.圖形學與可視化計算(GV)顯示圖像算法；實體對象的計算機表示；圖像處理方法等。二維和多維幾何；顏色理論；認知心理學；傅立葉分析等。圖形算法的實現；圖形庫和圖形包；圖像增強系統等。10.智能系統（IS）知識表示；推理與學習模型；自然語言理解；自動學習等。邏輯；概念依賴性；認知心理學；相關支持領域等。邏輯程序設計語言；定理證明；專家系統；弈棋程序；機器人等。11.信息管理（IM）數據模型；文件表示；數據庫查詢語言；超媒體模型等.關系代數；關系演算；數據依賴理論；并發理論；統計推理等。數據庫設計；數據庫安全；磁盤映射；人機接口等。12.軟件工程（SE）歸約方法；方法學；軟件工具與環境；系統評價；生命周期等程序驗證與證明；時態邏輯；可靠性理論；認知心理學等歸約語言；配置管理；軟件開發方法；工程管理；軟件工具等13.社會和職業問題（SP）價值觀；道德觀；知識產權；美學問題等。14.科學計算（CN）數學模型；有限元模型；連續問題的離散化技術等。數論；線性代數；數值分析；其他支持領域等有限元算法映射到特定結構的方法；標準程序庫和軟件包等。表2-1計算學科的二維定義矩陣2.1.2計算學科的三個形態1、抽象形態抽象是指在思維中對同類事物去除其現象的、次要的方面,抽取其共同的、主要的方面，從而做到從個別中把握一般，從現象中把握本質的認知過程和思維方法。抽象形態表明，基于計算學科的實驗科學方法，廣泛采用實驗物理學的研究方法。抽象的結果是概念、符號、模型。按照對客觀現象和規律的實驗研究過程包括以下4個步驟：①對研究對象的概念抽象(定義)；②假設對象的基本性質和對象之間可能存在的關系；③確定這些性質和關系是否正確(證明)；④解釋結果(與計算機系統或研究對象形成對應)。抽象形態的基本特征是其研究內容的構造性數學特征，是區別于更廣泛的數學科學學科形態的典型特征。2.1.2計算學科的三個形態2、理論形態科學認識由感性階段上升為理性階段就形成了科學理論。理論形態表明，基于計算科學的數學基礎和計算科學理論，廣泛采用數學的研究方法。按照統一、合理的理論發展過程，包含以下4個步驟：①表述研究對象的特征(定義和公理)；②假設對象之間的基本性質和對象之間可能存在的關系；③確定這些性質和關系是否正確(證明)；④分析結果(與計算機系統或研究對象形成對應)。這個形態主要出現在計算科學中與硬件設計和實驗有關的研究之中。當計算科學理論比較深奧，理解較為困難時，不少科研人員在大致了解理論、方法和技術的情況下，基于經驗和技能常以這種學科形態方式開展工作。2.1.2計算學科的三個形態3、設計形態設計用來開發求解給定問題的系統和設備，主要要素為：需求說明、規格說明、設計和實現方法、測試和分析。設計形態表明，基于計算學科的工程設計，廣泛采用工程科學的研究方法。按照為解決某個問題構造系統或裝置的過程，包含以下4個步驟：①進行需求分析；②給定技術條件，建立規格說明；③設計并實現該系統或裝置；④對系統進行測試分析、修改完善。這個形態廣泛出現在計算科學中與硬件、軟件、應用有關的設計和實現之中。2.1.3計算學科的根本問題計算學科的根本問題是討論“計算過程的能行性”，而凡是與“能行性”有關的討論，都是處理離散對象，因為非離散對象，即連續對象是很難進行“能行性”處理的。因此“能行性”決定了計算機本身的結構和它處理對象的離散特性，決定了以離散數學為代表的應用數學是描述計算學科的理論、方法和技術的主要工具。

1、計算過程的能行性對計算學科根本問題的認識與對計算過程的認識是緊密聯系在一起的。遠古時期我國學者就認為，對于一個數學問題，只有當確定了可用算盤求解的規則時，例如“三下五去二”、“四下五去一”等)，這個問題才是可解的，這就是最初的“算法化”思想，它蕰涵了中國古代對計算根本問題——“能行性”的理解。2.1.3計算學科的根本問題

20世紀30年代，圖靈用形式化的方法成功地表述了計算過程的本質，證明了某些數學問題不能用任何機械過程來解決，深刻地揭示了計算所具有的“能行過程”的本質特征：

一個計算過程是能行的，當且僅當它能夠被圖靈機實現。

2、計算的本質

計算的本質問題是可計算性。可計算性決定了計算機的體系結構和計算機所處理的對象都只能是離散型的，因為連續對象(即非離散對象)）是很難進行計算處理的，必須在轉化為離散型問題以后才能被計算機處理。例如，計算定積分就是把它變成離散量，再用分段求解的方法來處理的。盡管計算學科已成為一個極為寬廣的學科，但計算學科所有分支領域的根本任務就是進行計算，其實質就是符號的變換。

1嚴謹：計算機硬件系統的設計和軟件的開發都必須十分嚴謹，尤其是軟件開發，嚴謹的邏輯思維能力是相當重要的。2學科知識體系龐大：該學科從算法與可計算性研究到根據可計算硬件和軟件實現問題的研究，其知識體系龐大。3抽象：是計算學科的三個基本學科形態(抽象、理論、設計)之一。例如計算機中的文件管理、設備管理等都歸為操作系統。

4實踐性強：計算學科是在數學和電子學基礎上發展起來的，它不僅是一門理論性很強的學科,而且是一門實踐性很強的學科。5與其它學科關聯緊密：如邏輯學、微電子科學、光電子科學、遺傳學和神經生理學、物理和化學科學中的精細材料科學等。2.1.4計算學科的主要特點

1計算機科學：程序設計、離散結構、算法、數據結構、組成原理計算機網絡、操作系統、數據庫、編譯、軟件工程等15門.2計算機工程：程序設計、離散結構、算法、數據結構、組成原理網絡、操作系統、數據庫、編譯、軟件工程、數字邏輯等16門。3軟件工程：程序設計、離散結構、算法、數據結構、組成原理、網絡、操作系統、數據庫、編譯、軟件工程、軟件測試等24門。4信息技術：信息技術導論、數據結構與算法、數據庫與信息管理計算機系統平臺、應用集成、互聯網絡、信息工程等15門。§2.2

計算學科的知識體系2.2.1計算學科的知識領域5信息系統：關系數據庫、數據查詢、數據模型、信息系統、信息存儲、多媒體信息、事務處理、超文本和超媒體等15門。

1計算機離散數學：研究數理邏輯、集合論、近世代數和圖論等,計算機所處理的對象是離散型的，它是計算機科學的理論基礎.2算法分析理論：研究算法設計和分析中的數學方法與理論，如組合數學、概率論、數理統計等。3形式語言與自動機理論：研究程序設計語言及自然語言的形式化定義、分類、結構,研究識別各類語言的自動機模型及相互關系.4程序設計方法學：研究編制高質量程序的各種程序設計規范化方法，程序正確性證明理論等。5程序設計語言理論：運用數學和計算機科學理論研究程序設計語言的基本規律。如代數語義、公理語義、操縱語義等。2.2.2計算學科的研究范疇1、計算機理論的研究內容

1元器件與存儲介質：研究構成計算機硬件的各類電子的、磁性的、機械的、超導的元器件和存儲介質。2微電子技術：研究構成計算機硬件的各類集成電路、大規模集成電路、超大規模集成電路芯片的結構和制造技術等。3計算機組成原理：研究通用計算機的硬件組成結構以及運算器、控制器、存儲器、輸入/輸出設備等各部件的構成和工作原理。4微型計算機技術：研究使用最廣泛的微型計算機的組成原理、結構、芯片、接口電路及其應用技術。5計算機體系結構：研究計算機軟硬件的總體結構、各種新型體系結構以及進一步提高計算機性能的各種新技術。2.2.2計算學科的研究范疇2、計算機硬件的研究內容

1程序設計語言：研究數據類型、操作、控制結構、引進新類型和操作機制。根據實際需求選擇合適、新穎的程序設計語言。2算法設計：研究計算機領域及其它相關領域中的常用算法的設計方法并分析其時間復雜度和空間復雜度，以評價算法的優劣。3數據結構：研究數據在計算機中的表示和存儲方法、抽象的邏輯結構及其定義的各種基本操作。4編譯原理：研究程序設計語言中的詞法分析、語法分析、中間代碼優化、目標代碼生成和編譯程序開發。2.2.2計算學科的研究范疇3、計算機軟件的研究內容

數據庫管理系統：研究數據庫基礎理論、數據庫安全保護、數據庫模型、數據設計與應用和數據庫標準語言等。6軟件工程學：研究軟件過程、軟件需求與規格說明、軟件設計、軟件驗證、軟件演化、軟件項目管理、軟件開發工具與環境、形式化方法、軟件可靠性、專用系統開發。7可視化技術：研究如何用圖形和圖像來直觀地表征數據，它不僅要求計算結果的可視化，而且要求計算過程的可視化。2.2.2計算學科的研究范疇操作系統：研究操作系統的邏輯結構、并發處理、資源分配與調度、存儲管理、設備管理、文件系統等。85

1網絡組成：研究局域網、廣域網、Internet、Intranet等各種類型網絡的拓撲結構、構成方法和接入方式。2數據通信：研究連接在網絡上的計算機進行數據通信的介質、傳輸原理、調制與編碼技術、數據交換技術和差錯控制技術等。3體系結構：研究網絡通信雙方必須共同遵守的協議和網絡系統中各層的功能、結構、技術和方法等。4網絡安全：研究計算機網絡的設備安全、軟件安全、信息安全以及病毒防治等技術，以提高計算機網絡的可靠性和安全性。5網絡服務：研究如何為計算機網絡的用戶提供方便的遠程登錄、文件傳輸、電子郵件、信息瀏覽等服務。2.2.2計算學科的研究范疇4、計算機網絡的研究內容

1軟件開發工具：研究軟件開發工具的有關技術,如程序調試技術、代碼優化技術、代碼重用技術等。2完善現有的應用系統：根據新的技術平臺和實際情況對已有的應用系統進行升級、改造，使其功能更強大，更加便于使用。3開拓新的應用領域：研究如何打破計算機傳統的應用領域，擴大計算機在國民經濟以及社會生活中的應用范疇。4人一機交互：研究人與計算機的交互和協同技術，如圖形用戶接口設計、多媒體系統的人機接口等，為用戶提供更加友好界面。2.2.2計算學科的研究范疇5、計算機應用的研究內容在這些研究領域中，有些方面已研究得比較透徹并取得了許多成果，也有些方面還不夠成熟和完備，需要進一步去探索、研究、完善和發展。

1信息、管理與決策系統：涵蓋數據庫設計與數據管理技術、數據表示與存儲、多媒體技術、數據與信息檢索、管理信息系統、計算機輔助系統、數字仿真、決策系統等方向。3計算可視化：涵蓋科學計算、計算機圖形學、計算幾何、模式識別與圖形圖像處理等方向。4人工智能應用與系統：涵蓋人工智能、機器人、神經元計算、知識工程、自然語言處理與機器翻譯、自動推理等方向。2.2.3計算學科的知識結構

計算學科經過了半個多世紀的迅猛發展，已經成為一個相對比較完備的學科體系，衍生了許多相對獨立的方向和分支。從學科體系的角度，可將計算學科的內容劃分為3個層面。1、應用層

1軟件開發方法學：涵蓋順序、并行與分布式軟件開發方法學，如軟件工程技術、軟件開發工具和環境等方向。2計算機網絡與通信技術：涵蓋計算機網絡、網絡互聯技術、數據通信技術以及信息保密與安全技術等方向。3程序設計科學：涵蓋數據結構、數值與符號計算、算法設計與分析、程序設計語言、程序設計方法學、程序理論等方向。4計算機系統基礎：涵蓋電路基礎、數字邏輯技術、計算機組成原理、計算機體系結構、操作系統、編譯技術、數據庫系統實現技術、容錯技術、故障診斷與器件測試技術等方向。2、專業基礎層2.2.3計算學科的知識結構

1計算理論：涵蓋了可計算性（遞歸論）與計算復雜性理論、形式語言與自動機理論、形式語義學、Petri網理論等方向。2高等邏輯：涵蓋模型論、各種非經典邏輯與公理集合論等方向。3、專業理論基礎層

上述三個層面的劃分，有利于不同類型人才的培養。在人才培養規格上，可分劃為三種類型。

●科學型人才：強調基礎理論知識的掌握和創新能力的培養，要求掌握計算機科學理論和應用知識，具備較強的創新能力和實踐能力。

●工程型人才：強調解決實際工程問題能力的培養，要求掌握計算機理論和應用知識，具備較強的工程實踐能力。

●應用型人才：強調應用知識的掌握和組織協調能力的培養，要求掌握計算機科學及計算機應用知識，具備較強的實踐能力和動手能力。2.2.3計算學科的知識結構2.2.4計算學科與其它學科的關系1、計算學科與數學方法計算學科對數學具有很大的依賴性，數學不僅是計算機系統設計、算法設計的基礎，而且為計算學科提了最重要的學科思想和學科的方法論基礎。2、計算學科與電子學計算機硬件的發展與電子技術的發展緊密相關，每當電子技術有突破性的進展，就會導致計算機的一次重大變革。未來計算機的發展，將會與微電子學和光電子學密切相關。

3、計算學科與新興技術計算學科的發展正在更多地依賴新興技術的發展。對計算學科能產生重大影響的學科有：光學、材料科學、科學哲學、生物化學、腦科學與神經生理學、構造性數學、行為科學等。§2.3

中國計算機與技術學科2.3.1CCC2002與專業規范

1、中國計算機教程2002我國的計算機專業本科教育始于1956年哈爾濱工業大學等學校開設的“計算裝置與儀器”專業，后經歷了多種名稱變化，于1998年教育部進行本科專業目錄調整，計算機類專業名稱統一為計算機科學與技術專業。從2001年開始，增設了軟件工程專業和網絡工程專業。為了與國外先進課程體系接軌，2001年3月成立了《中國計算機科學與技術學科教程2002》（ChinaComputingCurricula2002，CCC2002）項目研究組，希望通過對CC2001的跟蹤、分析和研究，并結合我國計算學科的發展狀況，提出一個適應我國本科教學要求的教學計劃，2002年4月提交了研究報告，并通過了教育部組織的專家評審，且于同年9月出版發行。2.3.1CCC2002與專業規范

2、中國計算機專業規范

2006年6月24日，教育部頒布了計算機科學與技術專業發展規范，主要內容為：①在計算機科學與技術專業名稱下，鼓勵不同的學校根據社會需求和自身實際情況，為學生提供不同人才培養類型的教學計劃和培養方案。②將人才培養的規格歸納為三種類型、4個專業方向：科學型(計算機科學專業方向)、工程型(計算機工程專業方向、軟件工程專業方向)、應用型(信息技術專業方向)。③給出了4個專業方向的專業規范,，并將CC2004中的“信息系統(InformationSystem,IS）”專業方向劃歸管理科學，因此在《研究報告暨專業規范》中沒有該專業方向的內容。2.3.2計算機科學與技術學科的專業設置

1、計算機科學與技術學科體系

20世紀90年代我國對計算機科學與技術學科與專業設置做了重大改革，本科專業按一級學科培養，統一為計算機科學與技術專業；研究生按二級學科培養，統一為計算機軟件與理論、計算機系統結構和計算機應用技術3個專業,如圖2-2所示。圖2-2計算機科學與技術學科結構三個二級學科計算機系統結構計算機軟件與理論計算機應用技術一個一級學科計算機科學與技術2.3.2計算機科學與技術學科的專業設置

2、計算機科學與技術學科結構

(1)計算機系統結構學科：是計算機科學與技術的支柱學科和基礎學科,它研究計算機硬件與軟件的功能分配、軟硬件界面的劃分、硬件結構、組成與實現的方法與技術。

(2)計算機軟件與理論學科：是計算機科學與技術的核心與靈魂,它研究系統軟件、軟件自動化、程序設計語言、數據庫系統、軟件工程與軟件復用技術、并行處理與高性能計算、智能軟件、理論計算機科學、人工智能、計算機科學基礎理論等。

(3)計算機應用技術學科：是計算機科學與技術學科服務于國民經濟、國防建設、社會生活的鑰匙與紐帶,它研究計算機各類應用中具有共性的理論、技術和方法,以及各種前沿性、創新性、跨學科、跨領域的計算機新應用，包括科學問題的計算、數據的自動處理、各種對象的過程控制等。2.3.3計算機科學與技術學科的知識體系

1、離散結構8、人機交互

2、程序設計基礎9、圖形學與可視化計算3、算法與復雜性10、信息管理

4、體系結構與組織11、信息管理

5、操作系統12、軟件工程

6、網絡及其計算13、計算科學與數字方法

7、程序設計語言14、社會與職業問題

在上述核心課程中，計算機科學導論是學習計算機科學技術的入門課程、是計算機專業完整的知識體系概論，是計算機科學與技術專業課程體系中的通識課程。該課程在整個知識體系中，起到承前啟后的作用，并對整個學習過程起導航作用。在人類進行科學探索與科學研究的過程中，曾經提出過許多對科學發展具有重要影響和深遠意義的科學問題，如哥德巴赫猜想、四色定理、哥尼斯堡七橋等著名問題。這些經典問題的提出，對計算學科及其分支領域的形成與發展起了重要推進作用。了解這些經典問題，不僅有助于我們深刻理解計算學科中一些關鍵問題的本質，而且對學科的深入研究具有十分重要的促進作用。為了便于討論，我們將其歸類為：圖論問題、算法復雜性問題、機器智能問題、并發訪問控制問題。

通過對這些經典問題的介紹，希望能激發出同學們的學習熱情和研究興趣，為計算機科學與技術的研究和進步做出貢獻。§2.4

計算學科的經典問題2.4.1圖論問題

1、哥尼斯堡18世紀中葉,俄羅斯有一座哥尼斯堡城，城中有一條貫穿全市的流河,河中央有座島，河的兩條支流環繞其旁，并將整個城市分成北區、東區、南區和島區4個區域，由７座橋將４個城區連起來，如圖2-3所示。圖2-3哥尼斯堡七橋問題人們常通過這７座橋到各城區游玩，于是產生了一個有趣的問題:一個人怎樣不重復地走完7座橋，最后回到出發地點？這就是著名的“哥尼斯堡七橋問題”。為了解決哥尼斯堡七橋問題，歐拉用4個字母A、B、C、D代表4個城區，并用7條邊表示7座橋，如圖2-4所示。歐拉不僅給出了哥尼斯堡七橋問題的證明，還將問題進行了一般化處理，即對給定的任意一個河流圖與任意多座橋，判定是否存在每座橋恰好走過一次的路徑(不一定回到原出發點),并用數學方法給出了三條判定規則,人們將其規則圖稱為歐拉圖。圖2-４哥尼斯堡問題七橋抽象圖2.4.1圖論問題

2、哈密爾頓回路問題1857年愛爾蘭物理學家和數學家威廉·哈密爾頓提出的一個數學問題，也有人將它稱為周游世界的數學游戲。游戲的規則是：設有一個如圖2-7所示的正十二面體，它有20個頂點，把每個頂點看作一個城市,把正十二面體的30條邊看成連接這些城市的路。找一條從某城市出發,經過每個城市恰好一次,并且最后回到出發點的路徑,人們把這種路徑稱為哈密頓回路。把正十二面體投影到平面上，如圖2-8所示。圖中標出了一種走法,且從城市1出發，經過2、3、…、20，最后回到1。

2.4.1圖論問題2.4.1圖論問題圖2-7正十二面體圖2-8周游世界游戲示意圖

對一個圖是否存在“歐拉回路”前面已給出充分必要條件，而對一個圖是否存在哈密頓回路至今仍未找到充分必要條件。

3、中國郵路問題我國數學家管梅谷教授1960年也提出了一個有重要理論意義和廣泛應用背景的問題，當時稱為“最短投遞路線問題”，國際上稱為中國郵路問題：一個郵遞員應如何選擇一條路線，使他能夠從郵局出發，走遍他負責送信的所有街道，最后回到郵局，并且所走的路程最短。該問題歸結為圖論問題，對問題的求解是：給定一個連通無向圖(沒有孤立頂點)，每條邊都有非負的確定長度,求該圖的一條經過每條邊至少一次的最短回路。對于有歐拉回路的歐拉圖，找到一條歐拉回路即可。對于不存在歐拉回路的非歐拉圖，才是中國郵路問題的重點。管梅谷教授及國內外學者給出了一些解決該問題及推廣與變形問題的算法，研究成果除用于郵政部門外，還用于掃雪車路線、灑水車路線、警車巡邏路線的最優設計等。2.4.1圖論問題

4、旅行商問題旅行商問題（TravelingSalesmanProblem，TSP）是哈密頓和英國數學家柯克曼于19世紀初提出的一個數學問題。其基本含義是，有若干個城市，任何兩個城市之間的距離都是確定的，現要求一旅行商從某城市出發，必須經過每一個城市且只能在每個城市停留一次，最后回到原出發城市。要解決的問題是：如何事先確定好一條路程最短的旅行路徑呢？人們思考解決這個問題時首先想到的基本方法是：對給定的城市進行排列組合，列出每一條可供選擇的路徑，然后計算出每條路徑的總里程，最后從所有可能的路徑中選出一條路程最短的路徑。假設給定有4個城市，分別為C1、C2、C3和C4，各城市之間的距離是確定的值，城市間的交通如圖2-9所示。2.4.1圖論問題2.4.1圖論問題圖2-9城市交通問題示意圖圖2-10組合路徑圖從圖中可以看到，從城市Cl出發，最后再回到Cl城市，可供選擇的路徑共有6條，括號中為路徑長度，如圖2-10所示。

Cl→C2→C3→C4→C1（20），Cl→C2→C4→C3→C1（29）Cl→C3→C2→C4→C1（23），Cl→C3→C4→C2→C1（29）Cl→C4→C3→C2→C1（20），Cl→C4→C2→C3→C1（23）從中很快可以選出一條總路程最短的路徑

Cl→C2→C3→C4→C1或Cl→C4→C3→C2→C1若設城市的數目為n時，則組合路徑數為（n-1）!。顯然，當城市數目不多時，要找到最短距離的路徑并不難，但隨著城市數目的不斷增多，組合路徑數將呈指數規律急劇增長，以至達到無法計算的地步，這就是所謂的“組合爆炸問題”。假設城市的數目為20，組合路徑數則為(20-1)!≈1.216×1017，如此巨大的組合數目，若計算機每秒能計算出1000萬條路徑的速度計算，計算完所有路徑的需要386年的時間,這樣的算法是沒有實際意義的。2.4.1圖論問題據報導，1998年，科學家們成功地解決了美國13509個城市之間的TSP問題，2001年又解決了德國15112個城市之間的TSP問題，但這一工程代價也是巨大的。據報道，解決15112個城市之間的TSP問題，共使用了美國賴斯大學和普林斯頓大學之間網絡互聯的、由速度為500MHz的CompaqEV6Alpha處理器組成的110臺計算機，所有計算機花費的實踐總和為22.6年。TSP是最有代表性的優化組合問題之一，它的應用已逐漸滲透到各個技術領域和我們的日常生活中。在大規模生產過程中，尋找最短路徑能有效地減低成本。事實上，這類問題的解決還可以延伸到其它行業領域中。由于TSP會產生組合爆炸問題，為此人們提出了一些求近似解的算法，即找出的路徑不一定是最短路徑，而是比較短的路徑，但求解問題的時間復雜度大大降低了，因而是可行的實用算法，包括最近鄰算法、抄近路算法等。2.4.1圖論問題所謂“計算復雜性”，就是利用計算機求解問題的難易程度。它包括兩個方面：一是計算所需的步數或指令條數，稱為時間復雜度（TimeComplexity）；二是計算所需的存儲單元數量，稱為空間復雜度（SpaceComplexity）。下面列舉算法復雜性的4個著名實例。

1、Hanoi（漢諾塔）問題Hanoi問題源于印度神話傳說。傳說古代教的天神在創造世界時，建造了一座稱作為貝拿勒斯的神廟，神廟里安放了一個黃銅座，座上豎有三根寶石柱子。在第一根寶石柱上按照從小到大、自上而下的順序放有64個直徑大小不一的金盤子形成一座金塔，如圖2-11所示。

2.4.2算法復雜性問題天神讓廟里的僧侶們將第一根柱子上的64個盤子借助第二根柱子全部移到第三根柱子上，同時定下三條規則：①每次只能移動一個盤子；③盤子只能在三根柱子上來回移動，而不能放在它處；③在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。2.4.2算法復雜性問題

ABC圖2-11漢諾塔問題示意圖64個盤子天神說,當這64個盤子全部移到第三根柱子上后,世界末日就要到了。事實上，如果每秒移動一次，一年有31536000秒,僧侶們一刻不停地來回搬動,也需要花費大約5849億年的時間。假定計算機以每秒10000萬個盤子的速度進行搬遷,則需要花費大約58490年的時間。通過這一例子我們可以了解到，理論上可以計算的問題，實際上并不一定能實現。Hanoi塔是一個典型的只有用遞歸方法才能解決的問題。所謂遞歸，就是將一個較大的問題規約為一個或多個相對簡單的子問題的求解方法。而這些子問題比原問題簡單，且在結構上與原問題相同。

Hanoi塔是一個看似簡單，而實際處理卻很復雜，這一類問題稱為難解性問題，它包括時間的復雜性和空間的復雜性。2.4.2算法復雜性問題

2、NP問題

在采用圖靈機作為標準的計算工具的情況下，可以非形式化地定義如下幾類計算問題。(1)NP類問題：就是在算法的時間復雜性分析和研究中，將所有可以在多項式(如T(n2))時間內驗證的問題稱為多項式復雜程度的非確定性類問題。NP問題是至今沒有找到多項式時間算法解的一類問題，因此，NP類問題采用的是非確定性算法。

(2)NP完全問題：在NP類問題中某些問題的復雜性與整個類的復雜性有關，如果這些問題中的任意一個能在多項式的時間內求解，則所有NP類問題都能在多項式時間內求解，這些NP類問題稱為NP完全問題或NP難問題。求總路程小于B的路徑的旅行商問題是NP完全問題，求哈密頓回路也是NP完全問題。2.4.2算法復雜性問題2.4.2算法復雜性問題

3、36軍官問題36軍官問題是18世紀由歐拉作為一個數學游戲提出來的。設有分別來自6個軍團共有6種不同軍銜的36名軍官他們能否排成6行6列的編隊使得每行每列都有各種軍銜的軍官1名，并且每行和每列上的不同軍銜的6名軍官還分別來自不同的軍團？如果將一個軍官用一個序偶(i，j)表示，其中i表示該軍官的軍銜(i＝1,2,…,6)，而j表示他所在的軍團(j＝1,2,…,6)。于是這個問題又可以變成：36個序偶(i，j)(i＝1,2,…,6；j＝1,2,…,6)能否排成6×6陣列，使得在每行和每列這6個整數1,2,…,6都能以某種順序出現在序偶第一個元素的位置上，并以某種順序出現在序偶第二個元素的位置上？2.4.2算法復雜性問題36軍官問題提出后的很長一段時間沒有得到解決，直到20世紀初才被證明這樣的方隊是排不起來的。將36軍官問題中的軍團數和軍階數推廣到一般的n的情況,相應的滿足條件的方隊被稱為n階歐拉方。經過多次嘗試，歐拉猜測：對任何非負整數k,n＝4k＋2階歐拉方都是不存在的。1901年,法國數學家塔里(G.Tarry，1843～1913)用窮舉法證明了歐拉猜想對于n＝6是成立的；大約在1960年,三位統計學家R.C.Bose、E.T.Parke和S.S.Shrikhande）成功地證明了歐拉猜想對于所有的n＞6都是不成立的，也就是說，n＝4k＋2(k≥2)階歐拉方是不存在的。2.4.2算法復雜性問題

4、四色問題四色問題又稱為四色猜想或四色定理，1852年首先由英國的一位大學生古思里(F.Guthrie)提出來的。古思里在給一幅英國地圖著色時發現，只要4種顏色就可以使任何相鄰的兩個郡不同色。他推斷任何地圖的著色也只需要4種顏色就夠了，但他未能給出證明。1878年，英國數學家凱利(A.Cayley，1821～1895)對此問題進行了認真分析，認為這是一個不可忽視的問題，他正式向倫敦數學學會提出這個問題，于是四色猜想成了世界數學界關注的問題，世界上許多一流的數學家都紛紛參加了四色猜想的大會戰。1879年，英國律師兼數學家肯普(1849～1922)發表了證明四色猜想的論文，宣布證明了四色定理。11年后，即1890年，年輕的數學家赫伍德(1861～1955)以自己的精確計算指出肯普的證明有誤。2.4.2算法復雜性問題赫伍德一生堅持研究四色問題，但始終未能證明這一定理。但赫伍德在肯普的方法的基礎上證明了用5種顏色對任何地圖著色都是足夠的，即“地圖五色定理”是成立的。進入20世紀以后，科學家們對四色猜想的證明基本上是按照肯普的想法進行的。有些數學家對平面圖形的可約性進行了深入分析。1969年德國數學家希斯第一次提出了一種具有可行的尋找不可避免可約圖的算法，開創了研究的新思路。1970年，美國伊利諾伊大學的數學教授哈肯與阿佩爾合作從事這一問題研究。1976年6月哈肯和阿佩爾終于獲得成功：一組不可避免的可約圖終于找到了，這組圖一共有2000多個，即證明了任意平面地圖都能夠用4種顏色著色。他們的證明需要在計算機上計算1200小時，程序先后修改了500多次。2.4.3計算機智能問題計算機智能是20世紀中葉興起的一個新的科學技術領域，是目前計算機領域的熱點研究問題，也是計算機的一個重要發展趨勢。下面是計算機智能問題中的3個著名實例。

1、圖靈測試在計算機科學誕生后，為解決人工智能中一些激烈爭論的問題，圖靈和西爾勒分別提出了能夠反映人工智能本質特征的兩個著名的哲學問題，即圖靈測試和西爾勒的中文小屋。經過多年的研究，人們在人工智能領域取得了長足的進展。圖靈在1950年英國《Mind》雜志上發表了題為《計算機器和智能》的論文。論文中提出了“機器能思維嗎?”這一問題，在定義了“智能”和“思維”的術語之后，最終他得出的結論是我們能夠創造出可以思考的計算機。2.4.3計算機智能問題同時，他還提出了另一個問題：“如何才知道何時是成功了呢？并給出了一個判斷機器是否具有智能功能的方法，這就是被后人稱之為圖靈測試的模擬游戲，測試方法和過程如下：該游戲由一個男人(A)、一個女人(B)和一個性別不限的提問者(C)來完成。提問者(C)待在與兩個回答者相隔離的房間里，如圖2-12所示。圖2-12圖靈測試示意圖回答者B回答者A提問者2.4.3計算機智能問題游戲的目標是讓提問者通過對兩個回答者的提問來鑒別其中哪個是男人，哪個是女人。為了避免提問者通過回答者的聲音、語調輕易地做出判斷，在提問者和回答者之間通過計算機鍵盤。提問者只被告知兩個人的代號為X和Y，游戲的最后提問者要做出“X是A，Y是B”或“X是B，Y是A”的判斷。現在，把上面這個游戲中的男人(A)換成一部機器來扮演，如果提問者在與機器、女人的游戲中做出的錯誤判斷與在男人、女人之間的游戲中做出錯誤判斷的次數是相同或更多，那么就可以判定這部機器是能夠思維的。這時機器在提問者的提問上所體現出的智能(思維能力)與人沒有什么區別。根據圖靈當時的預測，到2000年，能有機器通過這樣的測試。有人認為，在1997年戰勝國際象棋大師卡斯帕羅夫的“深藍”計算機就可以看作通過了圖靈測試。2.4.3計算機智能問題

2、西爾勒中文小屋與人工智能有關的另一個著名的實驗是“中文小屋”。1980年美國哲學家西爾勒在雜志上發表了“心、腦和程序”的論文，文中他以自己為主角設計了一個假想實驗：假設西爾勒被關在一個小屋中，屋子里有序地堆放著足夠的中文字符，而他對中文一竅不通。這時屋外的人遞進一串中文字符，同時還附有一本用英文編寫的處理中文字符的規則（作為美國人，西爾勒對英語是熟悉的），這些規則將遞進來的字符和小屋中的字符之間的轉換作了形式化的規定，西爾勒按照規則對這些字符進行處理后，將一串新的中文字符送出屋外。事實上，他根本不知道送進來的字符串就是屋外人提出的“問題”，也不知道送出去的字符串就是所提出問題的“答案”。2.4.3計算機智能問題又假設西爾勒很擅長按照規則熟練地處理一些中文字符，而程序員（編寫規則的人）又擅長編寫程序（規則），那么，西爾勒“給出”的答案將會與一個熟悉中文的中國人給出的答案沒有什么不同。但是，能說西爾勒真的懂中文嗎？真的理解以中文字符串表示的屋外人遞進來的“問題”和自己給出的“答案”嗎？西爾勒借用語言學的術語非常形象地揭示了“中文小屋”的深刻含義：形式化的計算機僅有語法，沒有語義，只是按規則辦事，并不理解規則的含義及自己在做什么。圖靈認為，不要求機器與人腦在構造上一樣，只要與人腦有相同的功能就認為機器有思維。西爾勒認為，機器沒有什么智能，只是按照人們編寫好的形式化的程序來完成一項任務，機器本身未必清楚自己在做什么。這種對同一問題的不同認識代表了目前人們在計算機智能或人工智能上的爭議。2.4.3計算機智能問題

3、博弈問題人們把諸如下棋、打牌、戰爭等一類競爭性的智能活動稱為博弈。人工智能研究博弈的目的并不是為了讓計算機與人進行下棋、打牌之類的游戲，而是通過對博弈的研究來檢驗某些人工智能技術是否能達到對人類智能的模擬，因為博弈是一種智能性很強的競爭活動。另外，通過對博弈過程的模擬可以促進人工智能技術更深一步的研究。IBM研制的超級計算機“深藍”于1997年5月，與當時蟬聯12年世界冠軍的國際象棋大師—白俄羅斯的卡斯帕羅夫對弈，最終“深藍”以3.5比2.5的總比分獲勝，從而引起了世人的極大關注。2001年德國的“更弗里茨”國際象棋軟件擊敗了當