大學(xué)計(jì)算機(jī)第一章概述

1、第2頁(yè)第一章 基于計(jì)算機(jī)的問(wèn)題求解 第二章 計(jì)算機(jī)信息數(shù)字化基礎(chǔ) 第三章 計(jì)算機(jī)的工作原理與硬件體系結(jié)構(gòu)第四章 計(jì)算機(jī)軟件平臺(tái)第五章 計(jì)算機(jī)網(wǎng)絡(luò)平臺(tái)第六章 數(shù)據(jù)處理與數(shù)據(jù)庫(kù)第七章 關(guān)于計(jì)算第八章 算法與程序設(shè)計(jì)第九章 實(shí)用軟件 第十章 計(jì)算機(jī)科學(xué)前沿技術(shù)第3頁(yè) 1.1 問(wèn)題描述與抽象 1.2 基于計(jì)算機(jī)的問(wèn)題求解方法 1.3 計(jì)算機(jī)科學(xué)學(xué)科的知識(shí)領(lǐng)域第1章 基于計(jì)算機(jī)的問(wèn)題求解實(shí)驗(yàn)1 圖靈機(jī)模型與計(jì)算機(jī)硬件系 統(tǒng)虛擬拆裝實(shí)驗(yàn)第4頁(yè)第1章 基于計(jì)算機(jī)的問(wèn)題求解人類為什么要發(fā)明計(jì)算機(jī)？ 人的計(jì)算速度很低 祖沖之計(jì)算至小數(shù)點(diǎn)后7位數(shù)用了15年 中國(guó)第一顆原子彈研制時(shí)，數(shù)百位科學(xué)家在大禮堂打算盤第5頁(yè)

2、第1章 基于計(jì)算機(jī)的問(wèn)題求解因特網(wǎng)梅森素?cái)?shù)大搜索？第6頁(yè)第1章 基于計(jì)算機(jī)的問(wèn)題求解第7頁(yè)1計(jì)算思維的本質(zhì)：抽象和自動(dòng)化 第1章 基于計(jì)算機(jī)的問(wèn)題求解 哥尼斯堡七橋問(wèn)題 18世紀(jì)經(jīng)典數(shù)學(xué)問(wèn)題 在哥尼斯堡的一個(gè)公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€(gè)島以及島與河岸連接起來(lái)。問(wèn)是否可能從這四塊陸地中任一塊出發(fā)，恰好通過(guò)每座橋一次，再回到起點(diǎn)？ 哥尼斯堡七橋問(wèn)題 哥尼斯堡七橋問(wèn)題的抽象 第8頁(yè)1計(jì)算思維的本質(zhì)：抽象和自動(dòng)化 第1章 基于計(jì)算機(jī)的問(wèn)題求解 自動(dòng)化：機(jī)械地一步一步自動(dòng)執(zhí)行，其基礎(chǔ)和前提是抽像 適于計(jì)算機(jī)的典型算法：枚舉法第9頁(yè)2計(jì)算思維的特征 是屬于人的思維方式，不是計(jì)算機(jī)的思維方式 可以由人

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

4、機(jī) 邱奇-圖靈論題：所有計(jì)算或算法都可以由一臺(tái)圖靈機(jī)來(lái)執(zhí)行。世界上的問(wèn)題世界上的問(wèn)題 可計(jì)算的：圖靈機(jī)可計(jì)算的就是可計(jì)算的可計(jì)算的：圖靈機(jī)可計(jì)算的就是可計(jì)算的 不可計(jì)算的不可計(jì)算的 圖靈的貢獻(xiàn)圖靈的貢獻(xiàn) 圖靈機(jī)模型：解決了可計(jì)算問(wèn)題圖靈機(jī)模型：解決了可計(jì)算問(wèn)題 計(jì)計(jì)算機(jī)的理論問(wèn)題算機(jī)的理論問(wèn)題圖靈測(cè)試：回答了什么樣的機(jī)器具有智能圖靈測(cè)試：回答了什么樣的機(jī)器具有智能 人工智能的理論基礎(chǔ)人工智能的理論基礎(chǔ) 美國(guó)計(jì)算機(jī)學(xué)會(huì)ACM于1966年創(chuàng)立了“圖靈獎(jiǎng)” 計(jì)算機(jī)科學(xué)之父 人工智能之父第1章 基于計(jì)算機(jī)的問(wèn)題求解第12頁(yè)示例 漢諾塔問(wèn)題 大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上 從下往上

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

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

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

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

9、.2.2 基于計(jì)算機(jī)程序的問(wèn)題求解用程序方法求素?cái)?shù)i+1-i開(kāi)始開(kāi)始輸入輸入x設(shè)設(shè)i=2ix?結(jié)束結(jié)束x能否整除能否整除ix不是素?cái)?shù)不是素?cái)?shù)x是素?cái)?shù)是素?cái)?shù)是是是是否否否否第21頁(yè) 1.2 基于計(jì)算機(jī)的問(wèn)題求解方法基于計(jì)算機(jī)的問(wèn)題求解方法以天氣預(yù)報(bào)系統(tǒng)為例說(shuō)明基于計(jì)算機(jī)系統(tǒng)的問(wèn)題求解方法1.2.3 基于計(jì)算機(jī)系統(tǒng)的問(wèn)題求解第22頁(yè) 1.1 問(wèn)題描述與抽象 1.2 基于計(jì)算機(jī)的問(wèn)題求解方法 2.3 計(jì)算機(jī)科學(xué)學(xué)科的知識(shí)領(lǐng)域第1章 基于計(jì)算機(jī)的問(wèn)題求解第23頁(yè) 1.3 計(jì)算機(jī)計(jì)算機(jī)科學(xué)科學(xué)的的知識(shí)領(lǐng)域知識(shí)領(lǐng)域1. 計(jì)算機(jī)科學(xué) 計(jì)算機(jī)及其周圍各種現(xiàn)象和規(guī)律的科學(xué)，即研究計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、程序系統(tǒng)（即軟件

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

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