大學(xué)計算機基礎(chǔ)緒論

第1章緒論姚普選計算機教學(xué)實驗中心課程內(nèi)容網(wǎng)絡(luò)通信|計算機Internet局域網(wǎng)生活、工作數(shù)據(jù)倉庫聯(lián)機分析處理數(shù)據(jù)挖掘信息利用管理決策計算機工作原理軟件硬件數(shù)據(jù)管理數(shù)據(jù)庫數(shù)據(jù)庫DBMS數(shù)據(jù)結(jié)構(gòu)線性表、樹、圖數(shù)據(jù)__數(shù)字、文字等的表示、存儲、壓縮程序設(shè)計__語言、算法網(wǎng)絡(luò)局域網(wǎng)、Internet通信技術(shù)、設(shè)備數(shù)據(jù)倉庫

OLAP數(shù)據(jù)挖掘軟件文本、數(shù)據(jù)、講稿、圖處理聲音、動畫、視頻播放操作系統(tǒng)數(shù)據(jù)__二進(jìn)制數(shù)、ASCII碼、漢字內(nèi)碼、圖聲視頻數(shù)字化知識和技能硬件CPU、內(nèi)存、外存、I/O設(shè)備數(shù)字電路；邏輯設(shè)計、制造工作原理__馮諾依曼計算機數(shù)據(jù)庫數(shù)據(jù)庫DBMS自動控制自控系統(tǒng)自控原理智能模擬專家系統(tǒng)推理、機器學(xué)習(xí)、模式識別Page4學(xué)習(xí)方法課堂VS課外

學(xué)時少，需看書、網(wǎng)上查詢知識VS技能

如，OS_知原理可推知操作方法經(jīng)驗VS訓(xùn)練常用并不能自然成為高手統(tǒng)觀VS局部認(rèn)知：局部重要性—整體可行性廣博VS精深相輔：方向正確—解決現(xiàn)實問題Page5學(xué)習(xí)方法_續(xù)現(xiàn)狀VS將來如,Excel→數(shù)據(jù)處理→數(shù)據(jù)庫Access→SQLServer|MySQL→數(shù)據(jù)倉庫|OLAP|數(shù)據(jù)挖掘戰(zhàn)略VS戰(zhàn)術(shù)

嚴(yán)整的戰(zhàn)略規(guī)劃?精細(xì)的戰(zhàn)術(shù)實施

如：結(jié)構(gòu)化設(shè)計——

數(shù)據(jù)流圖→系統(tǒng)結(jié)構(gòu)圖（多個模塊的層次結(jié)構(gòu)）

→程序?qū)崿F(xiàn)每個模塊的功能（算法→程序）6S1：頂層設(shè)計存取款業(yè)務(wù)系統(tǒng)儲戶存取單、存折例0-1：存取款業(yè)務(wù)系統(tǒng)的設(shè)計存折(存折&存取單)|錢儲戶驗(存折&存取單)(存款|取款)&記賬存折|錢銀行7S2：一層設(shè)計儲戶審查分類存款處理取款處理帳目文件現(xiàn)金帳存折、存取單存折、存款單存折存折、存款單存折、取款單8S2：二層設(shè)計9S3：轉(zhuǎn)換成程序結(jié)構(gòu)圖實現(xiàn)：算法→程序10算法例0-2：求函數(shù)值例0-3：求解多項式y(tǒng)=9x5+10x4-5x3+8x2+3x-1數(shù)組p[1]~p[6]：-1,3,8,-5,10,9迭代式：y=p[k]+x?yy=-1+x(3+x(8+x(-5+x(10+x(9)y=0y=9+x?yy=10+x?yy=-5+x?yy=8+x?yy=3+x?yy=-1+x?yy=p[k]+x*yp[1]~p[6]←

1,3,8,-5,10,9y=0k←1輸出y的值開始輸入X的值結(jié)束Tk<=6F例0-4：TowerofHonoi幾個盤從一柱→另一柱方法：上組盤→輔助柱最大盤→目標(biāo)柱輔助柱盤→目標(biāo)柱例0-5：最短的編碼欲傳送電文：abaccda等長編碼：abcd各為00、01、10、11等長碼的電文：00010010101100共14位哈夫曼編碼思想：字符出現(xiàn)頻率越高→編碼越短構(gòu)造哈夫曼樹：字符出現(xiàn)頻率作權(quán)值、n個葉子本例字母頻率：abcd各為3、1、2、12112437acbd010011abcd011010111abaccda011001010111014課時：40（課）+16（機）上課：中2-3223時間：上課_課表;上機_課堂通知

上機：計算機教學(xué)實驗中心作業(yè)：學(xué)校統(tǒng)一制作的作業(yè)本——教材科購買實驗報告：上傳到_39用戶名、密碼——學(xué)號教材：《大學(xué)計算機基礎(chǔ)》《大學(xué)計算機基礎(chǔ)實驗指導(dǎo)》清華大學(xué)出版社、2011年9月鍵盤功能鍵字母鍵光標(biāo)鍵數(shù)字鍵計算機鍵盤定位：FJ基準(zhǔn)鍵：ASDFJKL；食指：各兩排中、無名指：

各一排左小指：

左側(cè)其余右小指：

右側(cè)其余右大指：

空格鍵Page17預(yù)備知識與技能1．操作系統(tǒng)的功能2．Windows系統(tǒng)的用戶界面3．文件操作4．設(shè)置5．附件§1Windows操作系統(tǒng)Page181.Windows操作系統(tǒng)的功能計算機硬件：物質(zhì)基礎(chǔ)軟件：管理計算機；為用戶提供服務(wù)；擴充計算機系統(tǒng)的功能軟件分類：系統(tǒng)軟件（如Word）、應(yīng)用軟件操作系統(tǒng)：最重要的系統(tǒng)軟件操作系統(tǒng)的功能：管理計算機的硬件、軟件和數(shù)據(jù)資源；安排計算機工作流程，使各部件協(xié)同工作；提供用戶與計算機之間的接口；常用操作系統(tǒng)：Unix、Linux、Windows、DOSPage192．Windows系統(tǒng)的用戶界面桌面：開始菜單、圖標(biāo)、任務(wù)欄開始菜單：程序、設(shè)置、搜索、幫助、關(guān)機等桌面上的圖標(biāo)：

文件夾圖標(biāo)：我的電腦、網(wǎng)上鄰居、我的文檔等；文件；快捷方式任務(wù)欄：按鈕、指示器等文件夾窗口：我的電腦、網(wǎng)上鄰居、資源管理器等剪貼板：剪_Ctrl+X、復(fù)制_Ctrl+C、粘貼_Ctrl+V拖放操作：移動、復(fù)制_按住Ctrl鍵3.文件操作Page204.設(shè)置開始｜設(shè)置｜控制面板｜顯示

→“顯示屬性”對話框開始｜設(shè)置｜控制面板｜管理工具｜計算機管理→“計算機管理”對話框開始｜設(shè)置｜打印機

→“打印機”對話框｜添加打印機５.附件開始｜程序｜附件｜寫字板開始｜程序｜附件｜畫圖開始｜程序｜附件｜娛樂｜錄音機Page21§2Word內(nèi)容1.Office用戶界面

主窗口、文檔窗口：菜單、工具欄、定制；2．文檔操作

打開、創(chuàng)建、保存、關(guān)閉3．錄入輸入法工具條、插入符號、自動圖文集、自動更正4．格式編排

字樣、段落、頁面、分欄、頁眉、頁腳、模板、樣式（標(biāo)題等）Page225．表格制作

插入表格、表格與邊框工具欄、文字與表格轉(zhuǎn)換、自動套用格式6．作圖

繪圖工具條、微調(diào)、組合、環(huán)繞方式等7．?dāng)?shù)學(xué)公式

上標(biāo)、下標(biāo)、插入公式、插入域8．圖文混排

插入圖片、圖片格式、圖片工具欄、裁剪縮放Word內(nèi)容_續(xù)Page23實驗報告格式1．題目

例：文檔操作與格式編排

實驗報告2．暑名學(xué)號姓名班級3．任務(wù)

課堂布置4．實驗條件

計算機硬件、軟件配置等5．實驗過程

詳細(xì)說明操作步驟及解決問題的過程6．總結(jié)第一次實驗24微機總線結(jié)構(gòu)CPU和內(nèi)存外存儲器總線和I／O設(shè)備軟件分類與功能計算機的應(yīng)用上網(wǎng)查詢、編輯Word文檔并上傳：第一章緒論√

什么是計算

計算、圖靈機、可計算性√

計算工具的發(fā)展和電子計算機算籌、算盤、機械計算機、計算尺、電子數(shù)字計算機√

計算科學(xué)學(xué)科形態(tài)、基本概念√

計算科學(xué)的應(yīng)用例：人工智能；云計算、網(wǎng)格計算、普適計算26本章內(nèi)容什么是計算—執(zhí)行算法哪些問題是可計算的？ 哪些是不可計算的？如何衡量問題的復(fù)雜性？歷史上的計算工具與 計算機有哪些共同的思想?計算科學(xué)的根本問題是什么？

算法、可計算性、軟硬件實現(xiàn)了解計算科學(xué)的應(yīng)用范圍

數(shù)值計算、數(shù)據(jù)處理、實時控制、 智能模擬；CAD（計算機輔助設(shè)計）姚普選271.1什么是計算思考：求解x2+2x-3=0？求解ax2+bx+c=0？有4個嫌疑人：a說："我不是小偷。"b說："c是小偷。"c說："小偷肯定是d。"d說："c冤枉人！"4人中3人說的是真話，問到底誰是小偷？總結(jié)：什么是計算？281.1.1計算計算_

computation：算法的執(zhí)行，從包含算法和輸入數(shù)據(jù)的初始狀態(tài)開始，經(jīng)過一系列中間狀態(tài)直到最終的目標(biāo)狀態(tài)的過程算法_algorithm：若干條指令組成的有窮序列姚普選29計算

VS產(chǎn)品的加工/生產(chǎn)過程，可比之處？函數(shù)_function：一組可能的輸入值和一組可能的輸出值之間的映射關(guān)系函數(shù)為每個可能的輸入賦予單一的輸出函數(shù)的計算：對于一個給定的輸入，確定其具體輸出的值的過程

通過對函數(shù)的計算來解決問題計算機科學(xué)的一個基本問題__找到一種技術(shù)，并用之于計算哪些解決問題的函數(shù)，即

y=f(x)能否確定，如何確定加工過程，如何實現(xiàn)加工過程?30思考：實現(xiàn)下列函數(shù)的計算，有什么特點和問題？去年每天的平均氣溫投資額P，利率r，投資n年后的金額=P(1+r)n計算sin(x)的值計算22，23，24，210，2100函數(shù)越復(fù)雜，需要的技術(shù)支持越強結(jié)論：問題：任意復(fù)雜的函數(shù)，總能找到系統(tǒng)來計算它嗎？姚普選201131函數(shù)的可計算與不可計算可計算：如果一個函數(shù)可依據(jù)輸入值和一定的計算步驟來確定輸出值，則稱其為可計算的（computable）不可計算：如果根據(jù)輸入找不到定義好的、一步一步的過程來確定輸出值，這樣的函數(shù)稱為不可計算的(uncomputable)如果一個問題是可計算的，不管它有多復(fù)雜，總能制造出一種機器對其進(jìn)行求解而如果問題是不可計算的，意味著它超出了機器的能力范圍姚普選201132（計算機解題）例1：求解ax2+bx+c=0⑴變量a、b、c←輸入各次項系數(shù)⑵變量delta←計算b*b-4*a*c⑶判斷（delta>=0？）,是則

變量sdelta←計算sqrt(delta);

否則，變量sdelta←計算sqrt(-delta)⑷變量real←計算-b/(2*a);

變量imag←計算sdelta/(2*a)⑸判斷（delta>=0？），是則x1←real+imag; x2←real-imag否則， x1←real+jimag; x2←real-jimag⑹輸出變量x1和x2的值姚普選201133（計算機解題）例2：求n!⑴變量n←終值10變量mul←初值1

變量I←初值1⑵判斷（i<=10？）,是則mul←計算mul*i

否則，轉(zhuǎn)到⑷⑶i←計算i+1

轉(zhuǎn)到⑵⑷輸出變量mul的值⑸算法結(jié)束34計算設(shè)備模型——圖靈機

依程序命令及內(nèi)部狀態(tài)移動、讀寫閱讀35圖靈機組成紙帶，兩端無限長，劃為一個個格子_存儲單元讀寫頭_大盒子，可左/右移，讀/改寫當(dāng)前格符號狀態(tài)寄存器_盒子上的方塊0、1、8、9等，保存有限個狀態(tài)（可能的內(nèi)部狀態(tài)、初始狀態(tài)、停機狀態(tài)）控制規(guī)則_程序，按當(dāng)前機器狀態(tài)及格子上符號確定讀寫頭下一步動作，改變狀態(tài)寄存器值，令機器進(jìn)入新狀態(tài)圖靈機計算：

預(yù)存的程序依據(jù)機器當(dāng)前狀態(tài)和當(dāng)前格內(nèi)容確定控制單元動作，控制單元一步步執(zhí)行每一步：觀察當(dāng)前格的符號，必要時寫入符號、左移/右移一格，然后改變狀態(tài)閱讀36例：本步操作

現(xiàn)狀態(tài)操作新狀態(tài)

當(dāng)前狀態(tài)為q4，A

改寫為E左移一格，進(jìn)入q3狀態(tài)指令：q4

A

E

L

q3工作方式讀寫頭_讀出當(dāng)前格符號依據(jù)_當(dāng)前狀態(tài)及讀取的符號查表(一連串指令)確定_是否改寫符號、如何移動讀寫頭、是否停機機器_進(jìn)入程序指定的新狀態(tài)閱讀37圖靈機：輸入信息變換→輸出信息最簡信息形式、運算：0、1、布爾運算_與或非構(gòu)造圖靈機：信息可0、1編碼；變換可分解為0、1編碼的變換；0、1編碼的運算可分解為_與/或/非

→布爾電路可組成任意圖靈機閱讀姚普選201138預(yù)先輸入指令閱讀姚普選201139圖靈可計算：將二進(jìn)制形式輸入值放在紙帶上，運行機器直至停止，即可從帶上讀取輸出值。由圖靈機這樣計算的函數(shù)稱為圖靈可計算的。即，存在一個圖靈機，給它一個空紙帶，可打印出任意逼近該函數(shù)的結(jié)果

丘奇—圖靈論題（圖靈猜想）：圖靈可計算函數(shù)與可計算函數(shù)是一樣的，即，圖靈機的計算能力囊括了任何算法系統(tǒng)的能力還可以說，圖靈機概念提供了一個環(huán)境，在此環(huán)境下，所有可計算函數(shù)的解都可表示出來圖靈猜想的意義：可將圖靈機的能力作為一種標(biāo)準(zhǔn)，若一個計算系統(tǒng)能夠計算所有的圖靈可計算函數(shù)，即可認(rèn)為其能力相當(dāng)于任何計算系統(tǒng)的能力閱讀40元胞自動機_馮諾依曼研究可自我復(fù)制的自動機時提出空間分成元胞（方、?、六邊形等離散的格子）。元胞處于若干可能狀態(tài)之一、可隨時間演化且其演化受臨近元胞狀態(tài)影響。傳統(tǒng)元胞自動機中，每個元胞的變化都同時進(jìn)行例:J.H.Conway_生命游戲二維空間劃為方格_元胞，元胞僅死/活二態(tài)，記為0/1，姚普選2011馮諾依曼鄰居Moore鄰居鄰居，可考慮上下左右，或四周，或其他類型整個空間初始狀態(tài)可人為設(shè)計，也可隨機設(shè)定。隨時間推移，每個元胞或死或生，然而空間整體卻出現(xiàn)了非常復(fù)雜的狀態(tài)演化閱讀41生命游戲J.H.Conway_60年代末設(shè)計，單人玩計算機游戲

產(chǎn)生動態(tài)圖案和動態(tài)結(jié)構(gòu)能力的元胞自動機模型給定初始狀態(tài)分布。經(jīng)若干步運算：有的圖案很快消失有的圖案固定不動，有的周而復(fù)始重復(fù)兩個或幾個圖案有的婉蜒而行有的保持圖案定向移動，形似閱兵陣……等價于通用圖靈機，選擇不同初始條件，可完成一切計算機可完成的算法演算/complex/models/gameoflife.htm姚普選2011閱讀42生命游戲的構(gòu)成及規(guī)則(1)元胞分布在規(guī)則劃分的網(wǎng)格上；(2)元胞具有0，1兩種狀態(tài)，0代表“死”，l代表“生”；(3)元胞以相鄰8個元胞為鄰居。即Moore鄰居形式；(4)一個元胞的生死由該時刻本身生死狀態(tài)和周圍8個鄰居的狀態(tài)(確切講是狀態(tài)的和)決定:當(dāng)前時刻，若一元胞狀態(tài)為“生”，且8個相鄰元胞中有2或3個的狀態(tài)為“生”，則下一時刻該元胞繼續(xù)保持“生”，否則“死”；當(dāng)前時刻，若一元胞為“死”。且8個相鄰元胞中正好有3個為“生”。則該元胞下一時刻“復(fù)活”。否則保持為“死”演示閱讀姚普選2011431.1.2可計算性自終止（self-terminating）

：若程序中所有變量都用程序自身的編碼形式進(jìn)行初始化，且該程序的執(zhí)行可導(dǎo)致一個終止的過程，則該程序是自終止的x=0;whilexnot0dox=x+1;endwhilestop一個自終止的程序閱讀44假設(shè)：停機函數(shù)是可計算的，→可找到一個程序，其輸入是程序，若輸入的程序是自終止的，則結(jié)果為x=1，若輸入的程序不是自終止的，則結(jié)果為x=0。設(shè)該程序為“停機函數(shù)判定程序”。問題：所有函數(shù)都是可計算的嗎？答案是否定的函數(shù)值為1輸入的程序是自終止的0輸入的程序不是自終止的例：停機函數(shù)：其輸入為一個程序問：停機函數(shù)是可計算的嗎？閱讀45構(gòu)造另一個新程序“停機函數(shù)判定擴展程序”：假設(shè)：新程序是自終止的，則“停機函數(shù)判定程序”的結(jié)果是x=1，由于x不等于0，導(dǎo)致x不停地加1，而且永遠(yuǎn)不會為0，從而程序不終止，矛盾；假設(shè)：新程序不是自終止的，則“停機函數(shù)判定程序”的結(jié)果為x=0，由于x=0，while的循環(huán)不會執(zhí)行而使程序停止，仍矛盾→停機函數(shù)在圖靈機模型下是不可計算的以新程序作為新程序自身的輸入“停機函數(shù)判定程序”whilexnot0dox=x+1;endwhile閱讀461.1.3問題的復(fù)雜性求解兩個問題將{5,2,8,1,6,3,10,7,4,9}從小到大排序計算3.1x2+6.2x+8.9=0的根哪個簡單？（求解同一個問題可找到多種不同的算法）如果要排序的不是數(shù)字，而是裝在相同容器中的不同重量的物質(zhì)47時間復(fù)雜性：

計算機求解所花的時間——問題求解關(guān)鍵算法的時間復(fù)雜度：主要看算法中需要的主要運算的次數(shù)和問題規(guī)模的關(guān)系同一個問題可以有不同的算法，用其中時間復(fù)雜度最小的作為問題的時間復(fù)雜性若算法在最壞情況下的時間復(fù)雜度是O(nk)，其中n為問題的規(guī)模，k為一確定常數(shù)，則稱該算法的時間復(fù)雜性為多項式時間一般地，將可由多項式時間算法求解的問題看作易處理的問題，稱為P問題

超出多項式時間才能求解的問題看做難處理問題48例如，n個人的群體，列出所有可能的小組組合：2n-1時間復(fù)雜度至少O(2n-1)_指數(shù)時間復(fù)雜性問題有一類問題，已有時間復(fù)雜性為指數(shù)階的算法，且已證明不存在多項式階算法，如梵塔問題__稱之為頑型問題另一類問題，目前已有的算法的時間復(fù)雜性為指數(shù)階，但不能肯定它有或沒有多項式階算法，

如當(dāng)m＞2時任意圖的m-可著色問題

__稱之為NP（NondeterministicPolynomial）問題，即“非確定的多項式”問題西安交通大學(xué)計算機教學(xué)實驗中心201149空間復(fù)雜性計算機內(nèi)存資源有限，問題較大時需考慮節(jié)省內(nèi)存的算法通過度量程序所需的存儲空間來衡量復(fù)雜性稱為空間復(fù)雜性空間復(fù)雜性也是用問題規(guī)模的數(shù)量級來表示的空間復(fù)雜性和時間復(fù)雜性可能常常是矛盾的，在設(shè)計算法時需要做出折中501.2計算工具發(fā)展__電子計算機誕生1.手工計算工具算籌記數(shù)加法線性方程組51算盤、計算尺、手搖計算機523.電子計算機的誕生電子數(shù)值積分機和計算機（ElectronicNumericalIntegratorandComputer）,簡稱ENIAC1945年，馮?諾依曼“EDVAC報告的第一份草案”

，確定新機器有五個構(gòu)成部分：運算器、控制器、存儲器、輸入和輸出裝置這一結(jié)構(gòu)被稱為馮?諾依曼結(jié)構(gòu)，有此結(jié)構(gòu)的計算機統(tǒng)稱為馮?諾依曼計算機EDVAC的方案有兩個重大改進(jìn)：發(fā)揮電子元件高速度而采用了二進(jìn)制；實現(xiàn)了存儲程序,可自動從一個指令進(jìn)入下一指令,作業(yè)順序可通過“條件轉(zhuǎn)移”指令而自動完成53馮.諾依曼結(jié)構(gòu)西安交通大學(xué)計算機教學(xué)實驗中心201154計算機的發(fā)展隨著組成邏輯電路的電子元件的發(fā)展，將電子計算機的發(fā)展劃分為：第一代電子管時代，第二代晶體管時代，第三代集成電路時代，第四代超大規(guī)模集成電路時代。如今，計算機從體積上趨于小型化，性能上趨于巨型化，功能上趨于網(wǎng)絡(luò)化、智能化和綜合化西安交通大學(xué)計算機教學(xué)實驗中心2011551.3計算科學(xué)1985年，ACM（美國計算機協(xié)會）和IEEE－CS（國際電子電氣工程師學(xué)會計算機分會）組成聯(lián)合攻關(guān)小組，開始了對“計算作為一門學(xué)科”的存在性證明1989年1月，該小組提交了《計算作為一門學(xué)科》（Computingasadiscipline）的報告第一次給出了計算學(xué)科一個透徹的定義，回答了計算學(xué)科中長期以來一直爭論的一些問題，完成了計算學(xué)科的“存在性”證明561.3.1計算學(xué)科計算學(xué)科(thedisciplineofcomputing）是對描述和變換信息的算法過程，包括對其理論、分析、設(shè)計、效率、實現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究它來源于對算法理論、數(shù)理邏輯、計算模型和自動計算機器的研究并與存儲式電子計算機的發(fā)明一起形成于20世紀(jì)40年代初期計算學(xué)科，即計算機科學(xué)與工程及計算機科學(xué)技術(shù)計算學(xué)科的研究：從算法與可計算性的研究到硬件和軟件實現(xiàn)問題的研究計算學(xué)科，總體上對算法和信息處理過程進(jìn)行研究的內(nèi)容，滿足給定規(guī)格要求的有效而可靠的軟硬件設(shè)計——它包括所有科目的理論研究、實驗方法和工程設(shè)計西安交通大學(xué)計算機教學(xué)實驗中心201157報告認(rèn)為，計算的根本問題是：什么能被（有效地）自動化，討論能行性的有關(guān)內(nèi)容包括：什么是（實際）可計算的、什么是（實際）不可計算的、如何保證計算的自動性、有效性及正確性等1.3.2計算科學(xué)的三個學(xué)科形態(tài)理論、抽象和設(shè)計581.理論

理論源于數(shù)學(xué)，其主要要素：定義、公理、定理、證明和結(jié)果用定義和公理來表達(dá)所研究對象的特征；用定理來假設(shè)對象之間的基本性質(zhì)和對象之間可能存在