大學計算機基礎緒論

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

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

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

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

嚴整的戰(zhàn)略規(guī)劃?精細的戰(zhàn)術實施

如：結構化設計——

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

→程序實現(xiàn)每個模塊的功能（算法→程序）6S1：頂層設計存取款業(yè)務系統(tǒng)儲戶存取單、存折例0-1：存取款業(yè)務系統(tǒng)的設計存折(存折&存取單)|錢儲戶驗(存折&存取單)(存款|取款)&記賬存折|錢銀行7S2：一層設計儲戶審查分類存款處理取款處理帳目文件現(xiàn)金帳存折、存取單存折、存款單存折存折、存款單存折、取款單8S2：二層設計9S3：轉換成程序結構圖實現(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的值結束Tk<=6F例0-4：TowerofHonoi幾個盤從一柱→另一柱方法：上組盤→輔助柱最大盤→目標柱輔助柱盤→目標柱例0-5：最短的編碼欲傳送電文：abaccda等長編碼：abcd各為00、01、10、11等長碼的電文：00010010101100共14位哈夫曼編碼思想：字符出現(xiàn)頻率越高→編碼越短構造哈夫曼樹：字符出現(xiàn)頻率作權值、n個葉子本例字母頻率：abcd各為3、1、2、12112437acbd010011abcd011010111abaccda011001010111014課時：40（課）+16（機）上課：中2-3223時間：上課_課表;上機_課堂通知

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

各一排左小指：

左側其余右小指：

右側其余右大指：

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

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

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

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

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

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

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

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

繪圖工具條、微調、組合、環(huán)繞方式等7．數(shù)學公式

上標、下標、插入公式、插入域8．圖文混排

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

例：文檔操作與格式編排

實驗報告2．暑名學號姓名班級3．任務

課堂布置4．實驗條件

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

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

什么是計算

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

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

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

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

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

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

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

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

通過對函數(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ù)越復雜，需要的技術支持越強結論：問題：任意復雜的函數(shù)，總能找到系統(tǒng)來計算它嗎？姚普選201131函數(shù)的可計算與不可計算可計算：如果一個函數(shù)可依據(jù)輸入值和一定的計算步驟來確定輸出值，則稱其為可計算的（computable）不可計算：如果根據(jù)輸入找不到定義好的、一步一步的過程來確定輸出值，這樣的函數(shù)稱為不可計算的(uncomputable)如果一個問題是可計算的，不管它有多復雜，總能制造出一種機器對其進行求解而如果問題是不可計算的，意味著它超出了機器的能力范圍姚普選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

否則，轉到⑷⑶i←計算i+1

轉到⑵⑷輸出變量mul的值⑸算法結束34計算設備模型——圖靈機

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

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

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

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

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

A

E

L

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

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

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

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

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

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

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

如當m＞2時任意圖的m-可著色問題

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

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

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