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

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

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

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

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

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

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

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

→程序?qū)崿F(xiàn)每個(gè)模塊的功能（算法→程序）6S1：頂層設(shè)計(jì)存取款業(yè)務(wù)系統(tǒng)儲(chǔ)戶存取單、存折例0-1：存取款業(yè)務(wù)系統(tǒng)的設(shè)計(jì)存折(存折&存取單)|錢(qián)儲(chǔ)戶驗(yàn)(存折&存取單)(存款|取款)&記賬存折|錢(qián)銀行7S2：一層設(shè)計(jì)儲(chǔ)戶審查分類(lèi)存款處理取款處理帳目文件現(xiàn)金帳存折、存取單存折、存款單存折存折、存款單存折、取款單8S2：二層設(shè)計(jì)9S3：轉(zhuǎn)換成程序結(jié)構(gòu)圖實(shí)現(xiàn)：算法→程序10算法例0-2：求函數(shù)值例0-3：求解多項(xiàng)式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的值開(kāi)始輸入X的值結(jié)束Tk<=6F例0-4：TowerofHonoi幾個(gè)盤(pán)從一柱→另一柱方法：上組盤(pán)→輔助柱最大盤(pán)→目標(biāo)柱輔助柱盤(pán)→目標(biāo)柱例0-5：最短的編碼欲傳送電文：abaccda等長(zhǎng)編碼：abcd各為00、01、10、11等長(zhǎng)碼的電文：00010010101100共14位哈夫曼編碼思想：字符出現(xiàn)頻率越高→編碼越短構(gòu)造哈夫曼樹(shù)：字符出現(xiàn)頻率作權(quán)值、n個(gè)葉子本例字母頻率：abcd各為3、1、2、12112437acbd010011abcd011010111abaccda011001010111014課時(shí)：40（課）+16（機(jī)）上課：中2-3223時(shí)間：上課_課表;上機(jī)_課堂通知

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

各一排左小指：

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

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

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

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

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

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

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

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

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

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

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

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

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

例：文檔操作與格式編排

實(shí)驗(yàn)報(bào)告2．暑名學(xué)號(hào)姓名班級(jí)3．任務(wù)

課堂布置4．實(shí)驗(yàn)條件

計(jì)算機(jī)硬件、軟件配置等5．實(shí)驗(yàn)過(guò)程

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

什么是計(jì)算

計(jì)算、圖靈機(jī)、可計(jì)算性√

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

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

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

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

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

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

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

通過(guò)對(duì)函數(shù)的計(jì)算來(lái)解決問(wèn)題計(jì)算機(jī)科學(xué)的一個(gè)基本問(wèn)題__找到一種技術(shù)，并用之于計(jì)算哪些解決問(wèn)題的函數(shù)，即

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

變量sdelta←計(jì)算sqrt(delta);

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

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

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

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

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

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

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

現(xiàn)狀態(tài)操作新?tīng)顟B(tài)

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

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

A

E

L

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

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

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

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

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

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

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

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

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

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

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