1、第2頁第一章 基于計算機的問題求解 第二章 計算機信息數字化基礎 第三章 計算機的工作原理與硬件體系結構第四章 計算機軟件平臺第五章 計算機網絡平臺第六章 數據處理與數據庫第七章 關于計算第八章 算法與程序設計第九章 實用軟件 第十章 計算機科學前沿技術第3頁 1.1 問題描述與抽象 1.2 基于計算機的問題求解方法 1.3 計算機科學學科的知識領域第1章 基于計算機的問題求解實驗1 圖靈機模型與計算機硬件系 統虛擬拆裝實驗第4頁第1章 基于計算機的問題求解人類為什么要發明計算機？ 人的計算速度很低 祖沖之計算至小數點后7位數用了15年 中國第一顆原子彈研制時，數百位科學家在大禮堂打算盤第5頁

2、第1章 基于計算機的問題求解因特網梅森素數大搜索？第6頁第1章 基于計算機的問題求解第7頁1計算思維的本質：抽象和自動化 第1章 基于計算機的問題求解 哥尼斯堡七橋問題 18世紀經典數學問題 在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島以及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發，恰好通過每座橋一次，再回到起點？ 哥尼斯堡七橋問題 哥尼斯堡七橋問題的抽象 第8頁1計算思維的本質：抽象和自動化 第1章 基于計算機的問題求解 自動化：機械地一步一步自動執行，其基礎和前提是抽像 適于計算機的典型算法：枚舉法第9頁2計算思維的特征 是屬于人的思維方式，不是計算機的思維方式 可以由人

3、執行，也可以由計算機執行 是概念化，不是程序化 3計算思維的基本問題 可計算性 計算復雜性 第1章 基于計算機的問題求解第10頁（1）M的狀態：接受狀態、進位狀態。初始時處于進位狀態。（2）從右向左掃描紙帶。 進位狀態：讀到0或空白，則改寫1，進入接受狀態，立即停機； 讀到1，則改寫為0，狀態保住不變，讀寫頭左移。 圖靈機(Turing machine，TM ) 阿蘭圖靈（Alan Mathison Turing ，19121954） 解決問題；什么是計算？什么是可計算性？組成：計算X+1的圖靈機M紙帶 讀寫頭 第1章 基于計算機的問題求解第11頁 圖靈機的能力=高級程序設計語言=現代通用計算

4、機 邱奇-圖靈論題：所有計算或算法都可以由一臺圖靈機來執行。世界上的問題世界上的問題 可計算的：圖靈機可計算的就是可計算的可計算的：圖靈機可計算的就是可計算的 不可計算的不可計算的 圖靈的貢獻圖靈的貢獻 圖靈機模型：解決了可計算問題圖靈機模型：解決了可計算問題 計計算機的理論問題算機的理論問題圖靈測試：回答了什么樣的機器具有智能圖靈測試：回答了什么樣的機器具有智能 人工智能的理論基礎人工智能的理論基礎 美國計算機學會ACM于1966年創立了“圖靈獎” 計算機科學之父 人工智能之父第1章 基于計算機的問題求解第12頁示例 漢諾塔問題 大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上 從下往上

5、按照大小順序摞著64片黃金圓盤。大梵天命令婆羅 門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。 并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次 只能移動一個圓盤。 第1章 基于計算機的問題求解第13頁漢諾塔問題分析 假設有n黃金圓盤，移動次數是f(n) 有f(1)=1，f(2)=3，f(3)=7，f(k+1）=2*f(k)+1 故f(n)=2n-1，時間復雜性記作O(2n) f(64) = 264-1=18446744073709551615 假如每秒鐘移動一次，一年365天，則約需要584942417355年，即5849億年 而地球的壽命才45億年。 假使用計算機進行每秒1億次的

6、移動，也需要5849年。 時間復雜性：O(1) O(logn) O(n) O(nlogn) O(n2）O(n3) O(nk) O(2n) 當n值稍大時，O(2n)的問題就無法計算了 第1章 基于計算機的問題求解第14頁 1.1 問題描述與抽象問題描述與抽象問題描述雞兔同籠建模與求解抽象過程3 5249 4xyxy雞 x兔 y數學模型分析問題和抽象方法不同，求分析問題和抽象方法不同，求解的途徑就不同解的途徑就不同第15頁 1.1 問題描述與抽象問題描述與抽象面向計算機的問題分析1. 面向計算機的問題抽象計算機抽象包括：過程抽象 數據抽象過程抽象是針對對象的行為特征數據抽象就是針對對象的屬性第16

7、頁 1.1 問題描述與抽象問題描述與抽象2. 雞兔同籠問題的計算機求解面向計算機的問題分析 -問題所涉及的參數 -答案要滿足的條件計算機求解過程 雞兔數量為整數；雞兔總數為35；雞兔總腳數為94根據這個流程圖，說明用計算機解決該問題與人的思維解決該問題，有哪些相同與不同之處？圖1-2第17頁 1.1 問題描述與抽象 1.2 基于計算機的問題求解方法 2.3 計算機科學學科的知識領域第1章 基于計算機的問題求解第18頁 1.2 基于計算機的問題求解方法基于計算機的問題求解方法1.2.1 基于計算機軟件的問題求解問題描述軟件名稱問題描述軟件名稱文件與信息下載迅雷下載視頻制作影視屏王文檔瀏覽HedE

8、x Lite壓縮軟件WinRAR圖像瀏覽ACDSee計算機安全使用360殺毒音頻瀏覽酷狗音樂播放器硬盤檢測工具HD Tune Pro視頻瀏覽超級解霸數學建模Mathematica圖像制作美圖秀秀電路設計Protel三維動畫制作3DS max機械制圖AutoCAD，Pro/E第19頁 1.2 基于計算機的問題求解方法基于計算機的問題求解方法1.2.2 基于計算機程序的問題求解程序主要包含如下兩方面的信息：（1）對程序中操作的描述。（2）對程序中數據的描述。計算機程序求解的關鍵問題?可計算，即能夠形式化描述有限步驟，即能自動化執行第20頁 1.2 基于計算機的問題求解方法基于計算機的問題求解方法1

9、.2.2 基于計算機程序的問題求解用程序方法求素數i+1-i開始開始輸入輸入x設設i=2ix?結束結束x能否整除能否整除ix不是素數不是素數x是素數是素數是是是是否否否否第21頁 1.2 基于計算機的問題求解方法基于計算機的問題求解方法以天氣預報系統為例說明基于計算機系統的問題求解方法1.2.3 基于計算機系統的問題求解第22頁 1.1 問題描述與抽象 1.2 基于計算機的問題求解方法 2.3 計算機科學學科的知識領域第1章 基于計算機的問題求解第23頁 1.3 計算機計算機科學科學的的知識領域知識領域1. 計算機科學 計算機及其周圍各種現象和規律的科學，即研究計算機系統結構、程序系統（即軟件

10、）、人工智能以及計算本身的性質和問題的學科。計算機科學是一門包含各種各樣與計算和信息處理相關主題的系統學科，從抽象的算法分析、形式化語法等等，到更具體的主題，如編程語言、程序設計、軟件和硬件等。第24頁 1.3 計算機計算機科學科學的的知識領域知識領域2. 計算機學科 計算機學科就是指計算機科學與技術，是研究計算機的設計，制造和利用進行信息獲取，表示，存儲，處理控制等的理論、原則、方法和技術的學科。計算機學科包括科學和技術兩個方面，計算機科學側重于研究現象揭示規律；計算機技術則側重于研制計算機和研究使用計算機進行處理的方法和技術手段。第25頁 1.3 計算機計算機科學科學的的知識領域知識領域3

11、. 計算機科學與技術專業的知識領域計算機科學與技術學科的知識領域 (IEEE/ACM-CCCS)01. 離散結構 (Discrete Structures-DS)02. 程序設計基礎 (Programming Fundamentals-PF)03. 算法和復雜性 (Algorithms & Complexity-AL)04. 程序設計語言 (Programming Languages-PL)05. 計算機結構與組織 (Architecture & Organization-AR)06. 操作系統 (Operating Systems-OS)07. 人-機交互 (Human-Computer Interaction-HC)08. 圖形學與可視計算 (Graphics & Visual Computing-GR)09. 智能系統 (Intelligent Systems-IS)10. 信息管理 (Informat