計(jì)算機(jī)科學(xué)導(dǎo)論 課件全 沈艷 第1-7章 計(jì)算與計(jì)算機(jī)、邏輯思維-工程思維

第1章計(jì)算與計(jì)算機(jī)本章目錄

計(jì)算機(jī)的概念01計(jì)算與計(jì)算工具02計(jì)算思維（自學(xué)）0301計(jì)算機(jī)的概念計(jì)算機(jī)是20世紀(jì)最先進(jìn)的科學(xué)技術(shù)發(fā)明之一，其應(yīng)用領(lǐng)域從最初的軍事科研應(yīng)用擴(kuò)展到社會(huì)的各個(gè)領(lǐng)域，業(yè)已成為信息社會(huì)中必不可少的工具。一、計(jì)算機(jī)的應(yīng)用01計(jì)算機(jī)的概念Computersareeverywhere！第一節(jié)計(jì)算機(jī)的概念

計(jì)算機(jī)是一種能夠按照事先存儲(chǔ)的程序，自動(dòng)地、高速地、精確地進(jìn)行大量數(shù)值計(jì)算，具有記憶（存儲(chǔ)）能力、邏輯判斷能力以及數(shù)字化信息處理能力的現(xiàn)代化智能電子設(shè)備。二、什么是計(jì)算機(jī)01計(jì)算機(jī)的概念第一節(jié)計(jì)算機(jī)的概念輸入：一個(gè)實(shí)數(shù)C例如：9輸出：例如：3中央處理器CPU存儲(chǔ)器內(nèi)存硬件軟件C=input()B=do_sqrt(C)print(B)軟件描述了用戶的需求，硬件則實(shí)現(xiàn)了用戶的需求01計(jì)算機(jī)的概念操作系統(tǒng)（OS）第一節(jié)計(jì)算機(jī)的概念02計(jì)算與計(jì)算工具一、什么是計(jì)算計(jì)算3+2=5計(jì)算規(guī)則及其簡(jiǎn)化計(jì)算方法，便于人應(yīng)用規(guī)則進(jìn)行計(jì)算，獲得計(jì)算結(jié)果。自動(dòng)計(jì)算要解決的幾個(gè)問(wèn)題:表示-存儲(chǔ)-執(zhí)行“數(shù)據(jù)”的表示“計(jì)算規(guī)則”的表示：程序數(shù)據(jù)與計(jì)算規(guī)則的“自動(dòng)存儲(chǔ)”計(jì)算規(guī)則的“自動(dòng)執(zhí)行”自動(dòng)計(jì)算是指計(jì)算過(guò)程不再依賴人類(lèi)的大腦，而是按照某種步驟和程序機(jī)械地、自動(dòng)地完成計(jì)算，并獲得計(jì)算結(jié)果第一節(jié)計(jì)算機(jī)的概念02計(jì)算與計(jì)算工具二、計(jì)算工具手工計(jì)算工具機(jī)械計(jì)算機(jī)機(jī)電計(jì)算機(jī)電子計(jì)算機(jī)原始計(jì)數(shù)法算籌算盤(pán)第一節(jié)計(jì)算機(jī)的概念02計(jì)算與計(jì)算工具手工計(jì)算工具原始計(jì)數(shù)法結(jié)繩計(jì)數(shù)事大，大其繩；事小，小其繩；結(jié)之多少，隨物眾寡。第一節(jié)計(jì)算機(jī)的概念02計(jì)算與計(jì)算工具算籌算籌始于商周時(shí)代，并在古代軍事中發(fā)揮著巨大的作用《漢書(shū)·張良傳》

“運(yùn)籌策帷幄中，決勝千里之外”手工計(jì)算工具我國(guó)古代數(shù)學(xué)家利用算籌創(chuàng)造了璀璨的數(shù)學(xué)成果祖沖之3.1415926~3.1415927之間比西方早了近一千年圓周率之父秦九韶算法天文歷法第一節(jié)計(jì)算機(jī)的概念02計(jì)算與計(jì)算工具算盤(pán)中國(guó)計(jì)算機(jī)之稱手工計(jì)算工具第二節(jié)數(shù)制及轉(zhuǎn)換01巴貝奇現(xiàn)代計(jì)算機(jī)：一般程序--任意可變的計(jì)算規(guī)則Pascal機(jī)械計(jì)算機(jī):第一臺(tái)機(jī)械計(jì)算機(jī)-能夠自動(dòng)完成計(jì)算Babbage分析機(jī):特定程序--可有限變化的計(jì)算規(guī)則萊布尼茨機(jī)械計(jì)算機(jī):自動(dòng)計(jì)算--固定的計(jì)算規(guī)則1642年1673年1833年計(jì)算與計(jì)算工具第二節(jié)數(shù)制及轉(zhuǎn)換01超大規(guī)模集成電路(VLSI)電子管:可自動(dòng)控制0和1變化的元件集成電路:可自動(dòng)實(shí)現(xiàn)一定變換的元件晶體管：可自動(dòng)控制0和1變化的元件電子管計(jì)算機(jī)ENIAC,1946年,17468只電子管人類(lèi)第一只電子管(真空二極管),1895人類(lèi)第一只晶體管(點(diǎn)接觸晶體管),1947第一臺(tái)晶體管計(jì)算機(jī)TRADIC，1953集成電路的發(fā)明,1959第三代計(jì)算機(jī)IBM360,1964第四代計(jì)算機(jī)—個(gè)人計(jì)算機(jī),1981VLSI出現(xiàn),1974計(jì)算與計(jì)算工具第一節(jié)計(jì)算機(jī)的概念01計(jì)算與計(jì)算工具1958年1959年1960年1964年1965年第一臺(tái)電子計(jì)算機(jī)誕生：八一型數(shù)字電子計(jì)算機(jī)。該機(jī)在738廠小批量生產(chǎn)，改名為103型計(jì)算機(jī)(即DJS-1型)，共生產(chǎn)了38臺(tái)。中國(guó)計(jì)算機(jī)發(fā)展第一臺(tái)大型通用電子計(jì)算機(jī)(104機(jī))的研制完成夏培肅院士領(lǐng)導(dǎo)的科研小組首次自行設(shè)計(jì)并研制成功一臺(tái)小型通用電子計(jì)算機(jī)，即107機(jī)第一臺(tái)自行設(shè)計(jì)的大型通用數(shù)字電子管計(jì)算機(jī)119機(jī)研制成功，平均浮點(diǎn)運(yùn)算速度達(dá)到5萬(wàn)次/秒成功研制了第一臺(tái)大型晶體管計(jì)算機(jī)(109乙機(jī)，共用2萬(wàn)多支晶體管，3萬(wàn)多支二極管)，隨后對(duì)109乙機(jī)加以改進(jìn)，兩年后又推出109丙機(jī)，在我國(guó)兩彈試驗(yàn)中發(fā)揮了重要作用，被用戶譽(yù)為“功勛機(jī)”。第一節(jié)計(jì)算機(jī)的概念02計(jì)算與計(jì)算工具1983年1983年1983年1992年1993年中國(guó)科學(xué)院計(jì)算所完成我國(guó)第一臺(tái)大型向量機(jī)（757機(jī)）計(jì)算速度達(dá)到1000萬(wàn)次/s。國(guó)防科技大學(xué)研制的銀河-Ⅰ億次巨型計(jì)算機(jī)，是我國(guó)高速計(jì)算機(jī)研制的一個(gè)重要里程碑，它標(biāo)志著我國(guó)十年動(dòng)亂時(shí)期與國(guó)外拉大的距離又縮小到7年左右(銀河-Ⅰ的參考機(jī)克雷-Ⅰ于1976年推出)。國(guó)防科技大學(xué)成功研制了銀河-Ⅱ通用并行巨型機(jī)，總體上達(dá)到80年代中后期國(guó)際先進(jìn)水平電子部六所研制成功與IBMPC機(jī)兼容的DJS-0520微機(jī)。國(guó)家智能計(jì)算機(jī)研究開(kāi)發(fā)中心成功研制曙光一號(hào)全對(duì)稱共享存儲(chǔ)多處理機(jī)。第一節(jié)計(jì)算機(jī)的概念02計(jì)算與計(jì)算工具1995年1997-1999年2000年2011年2013年中心又推出了中國(guó)第一臺(tái)具有大規(guī)模并行處理機(jī)(MPP)結(jié)構(gòu)的并行機(jī)曙光1000(含36個(gè)處理機(jī))1997年國(guó)防科技大學(xué)成功研制銀河-Ⅲ百億次并行巨型計(jì)算機(jī)系統(tǒng)，系統(tǒng)綜合技術(shù)指標(biāo)達(dá)到90年代中期國(guó)際先進(jìn)水平。國(guó)家智能計(jì)算機(jī)研究開(kāi)發(fā)中心與曙光公司于1997-1999年先后在市場(chǎng)上推出具有機(jī)群結(jié)構(gòu)的曙光1000A、曙光2000-Ⅰ、曙光2000-Ⅱ超級(jí)服務(wù)器推出浮點(diǎn)運(yùn)算速度為3000億次/秒的曙光3000超級(jí)服務(wù)器推出浮點(diǎn)運(yùn)算速度為1271萬(wàn)億次/秒的曙光6000超級(jí)服務(wù)器。天河二號(hào)第四十一屆世界大型超級(jí)計(jì)算機(jī)TOP500排行榜的第一名第一節(jié)計(jì)算機(jī)的概念03計(jì)算思維我們使用的工具影響著我們的思維方式和思維習(xí)慣，從而也將深刻地影響著我們的思維能力。計(jì)算思維是數(shù)字化計(jì)算時(shí)代的產(chǎn)物，成為這個(gè)時(shí)代每個(gè)人都具備的一種基本能力。艾茲格·迪科斯徹EdsgerWybeDijkstra著名計(jì)算機(jī)科學(xué)家1972年圖靈獎(jiǎng)獲得者計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念求解問(wèn)題、設(shè)計(jì)系統(tǒng)以及理解人類(lèi)行為，它涵蓋計(jì)算機(jī)科學(xué)領(lǐng)域的一系列思維活動(dòng)。周以真本部分自學(xué)！第一節(jié)計(jì)算機(jī)的概念總結(jié)

計(jì)算無(wú)所不在，古有運(yùn)籌帷幄，決勝于千里之外，今有春風(fēng)化雨，潛入千家萬(wàn)戶，計(jì)算文明的發(fā)展，計(jì)算工具的迭代，計(jì)算環(huán)境的演變，計(jì)算機(jī)的發(fā)展業(yè)已成為社會(huì)發(fā)展的標(biāo)志。人類(lèi)運(yùn)用計(jì)算工具不斷影響、改變著人類(lèi)社會(huì)形態(tài)、思維方式。計(jì)算思維的本質(zhì)是抽象和自動(dòng)化，這不僅是數(shù)字化時(shí)代實(shí)施自動(dòng)計(jì)算的產(chǎn)物，也是這個(gè)時(shí)代的人們必備信息素養(yǎng)和能力。謝謝！第2章邏輯思維數(shù)據(jù)表示03數(shù)制及轉(zhuǎn)換01數(shù)據(jù)存儲(chǔ)與運(yùn)算02本章目錄圖靈機(jī)模型0401數(shù)制及轉(zhuǎn)換

數(shù)制是用一組固定的數(shù)碼和一套統(tǒng)一的規(guī)則來(lái)表示數(shù)值的方法。

日常生活中通常用十進(jìn)制來(lái)計(jì)數(shù)。計(jì)算機(jī)內(nèi)部，一切信息的存取、處理和傳輸均采用二進(jìn)制計(jì)數(shù)。

一、為什么選擇二進(jìn)制01數(shù)制及轉(zhuǎn)換實(shí)現(xiàn)簡(jiǎn)單、工作可靠

具有兩種穩(wěn)定狀態(tài)的器件容易找運(yùn)算規(guī)則簡(jiǎn)單。3個(gè)運(yùn)算規(guī)則邏輯操作簡(jiǎn)單

對(duì)象是真和假，兩種狀態(tài)與之對(duì)應(yīng)計(jì)算機(jī)中用二進(jìn)制優(yōu)勢(shì)在計(jì)算機(jī)的世界里，沒(méi)有文字、沒(méi)有電影、沒(méi)有音樂(lè)，只有無(wú)數(shù)個(gè)0和1！01數(shù)制及轉(zhuǎn)換

10100101第二節(jié)數(shù)制及轉(zhuǎn)換二進(jìn)制八進(jìn)制十進(jìn)制十六進(jìn)制數(shù)碼0,10~70~90~9，A~F基數(shù)281016位權(quán)2n8n10n16n進(jìn)位原則逢2進(jìn)1逢8進(jìn)1逢10進(jìn)1逢16進(jìn)1借位原則借1當(dāng)2借1當(dāng)8借1當(dāng)10借1當(dāng)16表示方法(101)2

101B(17)8

17O(45)1045D(1A)16

1AH二、數(shù)制轉(zhuǎn)換D(Decimal)B(Binary)O(Octonary)H(Hexadecimal)01數(shù)制及轉(zhuǎn)換第二節(jié)數(shù)制及轉(zhuǎn)換按權(quán)展開(kāi)式：每位上的數(shù)碼乘以對(duì)應(yīng)位權(quán)之和305.56的按權(quán)展開(kāi)式：

305.56=3×102+0×101+5×100+5×10-1+6×10-201數(shù)制及轉(zhuǎn)換N=an-1×rn-1＋an-2×rn-2＋…＋a0×r0＋a-1×r-1＋…＋a-m×r-mR進(jìn)制數(shù)N展開(kāi)式可表示為：第二節(jié)數(shù)制及轉(zhuǎn)換

101.01B

=1×22+0×21+1×20+0×2-1+1×2-2=5.25D（1）二進(jìn)制/八進(jìn)制/十六進(jìn)制轉(zhuǎn)十進(jìn)制101.01B按權(quán)展開(kāi)式01數(shù)制及轉(zhuǎn)換【例】將101.01B轉(zhuǎn)換為十進(jìn)制數(shù)第二節(jié)數(shù)制及轉(zhuǎn)換整數(shù)部分:除基取余逆排列

小數(shù)部分:乘基取整順排列01數(shù)制及轉(zhuǎn)換(2)十進(jìn)制轉(zhuǎn)二進(jìn)制/八進(jìn)制/十六進(jìn)制【例】將26.25D轉(zhuǎn)換為二進(jìn)制數(shù)第二節(jié)數(shù)制及轉(zhuǎn)換(3)二進(jìn)制與八進(jìn)制、十六進(jìn)制轉(zhuǎn)換01數(shù)制及轉(zhuǎn)換三位一并法（八進(jìn)制），四位一并法（十六進(jìn)制）二進(jìn)制轉(zhuǎn)換為八/十六進(jìn)制：從小數(shù)點(diǎn)開(kāi)始分別向左（整數(shù)）和向右（小數(shù)）劃分?jǐn)?shù)位，每隔3位/4位一組，最后一組若不足3位/4位則補(bǔ)0,再將每組二進(jìn)制數(shù)轉(zhuǎn)換為八/十六進(jìn)制數(shù)。八/十六進(jìn)制轉(zhuǎn)換為二進(jìn)制：將每1位八/十六進(jìn)制數(shù)轉(zhuǎn)換為3位/4位二進(jìn)制數(shù)按次序?qū)懗觥?0110101.10111100010110101.101100（265.54）8（35.BC）16第二節(jié)數(shù)制及轉(zhuǎn)換十進(jìn)制、十六進(jìn)制、八進(jìn)制與二進(jìn)制之間的對(duì)應(yīng)關(guān)系01數(shù)制及轉(zhuǎn)換第二節(jié)數(shù)制及轉(zhuǎn)換各種進(jìn)制之間的轉(zhuǎn)換方法總結(jié)01數(shù)制及轉(zhuǎn)換02數(shù)據(jù)存儲(chǔ)與運(yùn)算位（bit）比特：1或者0，是二進(jìn)制信息組成、處理、存儲(chǔ)、傳輸?shù)淖钚?shù)據(jù)單位。字節(jié)（Byte）：1Byte=8bits，信息存儲(chǔ)的基本單位。字（Word）：計(jì)算機(jī)在同一時(shí)間內(nèi)處理的一組二進(jìn)制數(shù)，字由若干字節(jié)構(gòu)成，字的位數(shù)稱為字長(zhǎng)。如8bits、16bits、32bits、64bits等。字長(zhǎng)是計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理和運(yùn)算的單位。（1）數(shù)據(jù)存儲(chǔ)單位一、數(shù)據(jù)存儲(chǔ)02數(shù)據(jù)存儲(chǔ)與運(yùn)算計(jì)算機(jī)存儲(chǔ)容量的常用表示單位第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示（2）大端和小端存儲(chǔ)內(nèi)存：以字節(jié)Byte為單位，每個(gè)字節(jié)有唯一的地址，就可方便地存取數(shù)據(jù)。數(shù)據(jù)存放：不同的數(shù)據(jù)類(lèi)型占據(jù)的字節(jié)數(shù)不同。02數(shù)據(jù)存儲(chǔ)與運(yùn)算intn=100；//占4個(gè)字節(jié)doublex=3.56；//占8個(gè)字節(jié)第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示02數(shù)據(jù)存儲(chǔ)與運(yùn)算大端存儲(chǔ)小端存儲(chǔ)inta=0x11223344較高的有效字節(jié)存放在較低的存儲(chǔ)器地址，較低的有效字節(jié)存放在較高的存儲(chǔ)器地址，稱為大端存儲(chǔ)較高的有效字節(jié)存放在較高的存儲(chǔ)器地址，較低的有效字節(jié)存放在較低的存儲(chǔ)器地址，稱為大端存儲(chǔ)第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示02數(shù)據(jù)存儲(chǔ)與運(yùn)算二、算術(shù)運(yùn)算第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示02數(shù)據(jù)存儲(chǔ)與運(yùn)算三、邏輯運(yùn)算（1）與運(yùn)算第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示02數(shù)據(jù)存儲(chǔ)與運(yùn)算（2）或運(yùn)算第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示02數(shù)據(jù)存儲(chǔ)與運(yùn)算（3）非運(yùn)算第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示02數(shù)據(jù)存儲(chǔ)與運(yùn)算（4）異或運(yùn)算02性質(zhì)x∨0

=x,x∨1=1,x∧0

=0,x∧1=xx∨?x=1,x∧?x=0

x∧y=y∧x,x∨y=y∨x

(x∧y)∧z=x∧(y

∧z)(x∨y)∨z=x∨(y

∨z)(x∧y)∨z=(x∨z)∧(y∨z)(x∨y)∧z=(x∧z)∨(y∧z)?(x∨y)=?x∧?y?(x∧y)=?x∨?yx→y=?x∨yx⊕y=(?x∧y)∨(x∧?y)(結(jié)合律)(分配律)(DeMorgan律)(0-1律)(交換律)(互補(bǔ)律)數(shù)據(jù)存儲(chǔ)與運(yùn)算02從實(shí)際問(wèn)題到邏輯函數(shù)

舉重比賽時(shí)有A、B、C三個(gè)裁判，在兩名以上或兩名以上裁判判決成功時(shí)，才能最終判決運(yùn)動(dòng)員舉重成功。請(qǐng)分析判決結(jié)果Y與三名裁判A、B、C的判斷的邏輯關(guān)系。解：（1）根據(jù)裁判判決與最終結(jié)果的關(guān)系寫(xiě)出真值表裁判判決成功為1，不成功為0最終結(jié)果成立為1，不成立為0列出真值表數(shù)據(jù)存儲(chǔ)與運(yùn)算02

由真值表寫(xiě)出邏輯函數(shù)表達(dá)式，先選定輸出結(jié)果為1的項(xiàng)，順序?qū)懗鲚斎胱兞浚绻麑?duì)應(yīng)為1則為原變量，對(duì)應(yīng)為0則為反變量。再將這些項(xiàng)相或。

（2）根據(jù)上面的真值表寫(xiě)出函數(shù)表達(dá)式數(shù)據(jù)存儲(chǔ)與運(yùn)算03數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示03數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示一、數(shù)值數(shù)據(jù)的表示符號(hào)位S11101100最高位符號(hào)位，“0”表示正，“1”表示負(fù)數(shù)，其余位為數(shù)值位。-108解決符號(hào)問(wèn)題：?jiǎn)栴}：數(shù)值在計(jì)算機(jī)中二進(jìn)制形式存放，則正負(fù)符號(hào)、小數(shù)點(diǎn)如何表示？03數(shù)據(jù)表示機(jī)器數(shù)是指數(shù)在計(jì)算機(jī)中的表示形式。在計(jì)算機(jī)中只有機(jī)器數(shù)，不存在數(shù)的真值。

兩個(gè)數(shù)N1和N2的真值分別為：N1＝＋1101010N2＝－1011100所對(duì)應(yīng)的機(jī)器數(shù)分別為：N1：01101010N2：11011100第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示03數(shù)據(jù)表示有符號(hào)數(shù)無(wú)符號(hào)數(shù)無(wú)符號(hào)機(jī)器數(shù)的表示范圍：0

X<28，即0~255（00000000）2

（11111111）2

數(shù)的符號(hào)用0和1表達(dá)，0表“+”號(hào)，1表“-”號(hào)（00000000）2

（01111111）2

（10000000）2

（11111111）2

8位機(jī)器字長(zhǎng)無(wú)符號(hào)機(jī)器數(shù)的表示范圍：-27<X<27，即-127~127第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示求：-5+4？問(wèn)題：若符號(hào)位參加運(yùn)算，結(jié)果錯(cuò)；若考慮符號(hào)位，則運(yùn)算變得復(fù)雜；怎么解決？引入數(shù)的編碼二進(jìn)制數(shù)值數(shù)據(jù)在計(jì)算機(jī)中有原碼、反碼和補(bǔ)碼3種表示方法。03數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示

123（10）的原碼表示是：

01111011-123（10）的原碼表示是：

111110110有兩種原碼表示：0000000010000000原碼表示03字長(zhǎng)為8bit一個(gè)正數(shù)的反碼與其原碼相同；一個(gè)負(fù)數(shù)的反碼：對(duì)其原碼的數(shù)值位按位變反（1→0、0→1）。 (123)（反）=(123)（原）=01111011 (-123)（反）=10000100

(11111011→10000100)反碼表示0有兩種反碼表示：00000000111111111數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示9999999里程表補(bǔ)碼表示當(dāng)字長(zhǎng)為8bit，則(123)

10=(01111011)

2要得到(-123)

10,求一個(gè)二進(jìn)制數(shù)c：

c+01111011=0000000這樣的c就是|(-123)

10|的二進(jìn)制表示：

10000101

10000101+）01111011

00000000進(jìn)位被丟棄03再行進(jìn)1公里0

0

0

0

0

0

0當(dāng)限制了數(shù)據(jù)的表示長(zhǎng)度時(shí)，要得到與正數(shù)對(duì)應(yīng)的負(fù)數(shù)表示，可以認(rèn)為：要得到的負(fù)數(shù)加上對(duì)應(yīng)的正數(shù)之后等于0，稱之為求補(bǔ)。數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示負(fù)數(shù)補(bǔ)碼對(duì)其原碼數(shù)值位按位變反后加1原碼表示是：10011010按位變反后：11100101加1后得到補(bǔ)碼：11100110一個(gè)正數(shù)的補(bǔ)碼表示與它的原碼表示相同0只有一種補(bǔ)碼表示：00000000補(bǔ)碼表示

在計(jì)算機(jī)系統(tǒng)中，數(shù)值用補(bǔ)碼來(lái)表示。

03求：-5+4？

11111011+）00000100

11111111補(bǔ)碼再求補(bǔ)即為原碼數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示小結(jié)03數(shù)據(jù)表示正數(shù)負(fù)數(shù)范圍正0負(fù)0原碼0數(shù)值1絕對(duì)值-(２ｎ-１-１）~+(２ｎ-１–

１)0000000010000000反碼0數(shù)值1按位取反-(２ｎ-１-１)~+(２ｎ-１-１)0000000011111111補(bǔ)碼0數(shù)值1按位取反+1-(２ｎ-１)~+(２ｎ-１-１)0000000000000000解決小數(shù)點(diǎn)問(wèn)題：第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示小數(shù)點(diǎn)表示定點(diǎn)浮點(diǎn)03數(shù)據(jù)表示+11110101.0100011110101.01000111101010100小數(shù)點(diǎn)默認(rèn)在此位置(無(wú)需用符號(hào)表示)，機(jī)器中全部是小數(shù)小數(shù)點(diǎn)默認(rèn)在此位置(無(wú)需用符號(hào)表示)，機(jī)器中全部是整數(shù)(+245.25)100111101010100解決小數(shù)點(diǎn)問(wèn)題：第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示小數(shù)點(diǎn)表示定點(diǎn)浮點(diǎn)實(shí)數(shù)可以表示成：一個(gè)純小數(shù)和一個(gè)乘冪之積形式。

(+245.25)10=0.24525×10303數(shù)據(jù)表示小數(shù)點(diǎn)位置變化的數(shù)稱為浮點(diǎn)數(shù)+11110101.0100011110101.010000.111101010100×

2+800.111101010100×

201000N=S.M×2E解決小數(shù)點(diǎn)問(wèn)題：第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示小數(shù)點(diǎn)表示定點(diǎn)浮點(diǎn)實(shí)數(shù)可以表示成：一個(gè)純小數(shù)和一個(gè)乘冪之積形式。

(+245.25)10=0.24525×103數(shù)符S階碼E尾數(shù)M

階碼的位數(shù)決定數(shù)的范圍03數(shù)據(jù)表示小數(shù)點(diǎn)位置變化的數(shù)稱為浮點(diǎn)數(shù)+11110101.0100011110101.010000.111101010100×

2+800.111101010100×

2010000010000111101010100N=S.M×2E尾數(shù)的位數(shù)決定數(shù)的精度第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示03數(shù)據(jù)表示S階碼尾數(shù)8bits23bits1bitS階碼尾數(shù)11bits52bits1bit浮點(diǎn)數(shù)的精度是否還能提高？單精度：32bits雙精度：64bits-0.11101

2-1001

能否去掉指數(shù)的符號(hào)0-127+1270+127+254帶正負(fù)號(hào)的指數(shù)不帶正負(fù)號(hào)的指數(shù)指數(shù)平移：-127~127→0~254，

避免指數(shù)符號(hào)與整個(gè)數(shù)符號(hào)的混淆能否可多表示1尾數(shù)第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示02計(jì)算機(jī)中的數(shù)據(jù)表示浮點(diǎn)數(shù)的精度是否還能提高？-0.11101

2-1001

能否可多表示1尾數(shù)

-1.1101×2-1010

101110101加(27-10)后得到默認(rèn)存在，但不存儲(chǔ)(-127)10-01111111(-0,+0)1000000000(+127)10+01111111+127(0)1000000000(127)1001111111(254)1011111110(-10)10-00001010(117)+01110101S階碼尾數(shù)8bits23bits1bit11010000000000000000000IEEE754標(biāo)準(zhǔn)

于1985建立

之前由每個(gè)計(jì)算機(jī)制造商設(shè)計(jì)自己的規(guī)則

支持所有主流的CPU第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示二、字符表示符號(hào)和英文字母編碼標(biāo)準(zhǔn)：

ASCII碼、Unicode碼等03數(shù)據(jù)表示ASCII碼(AmericanStandardCodeforInformationInterchange，信息交換美國(guó)標(biāo)準(zhǔn)碼)ASCII碼可表示10個(gè)數(shù)字，26個(gè)小寫(xiě)字母，26個(gè)大寫(xiě)字母，以及各種運(yùn)算符號(hào)和標(biāo)點(diǎn)符號(hào)。常規(guī)ASCII碼（8bits）:最高位為0，其他7位表示128種符號(hào)和字母。擴(kuò)展ASCII碼（8bits）:8位表示256種符號(hào)和字母，其中前128種與常規(guī)ASCII碼相同。0b6b5b4b3b2b1b0擴(kuò)展ASCII標(biāo)準(zhǔn)兩個(gè)主要障礙：（1）不足以容納許多亞洲語(yǔ)言和一些東歐語(yǔ)言的字母表。（2）無(wú)法支持包含不同語(yǔ)種的語(yǔ)言文本的文檔。Unicode為每種語(yǔ)言中的每個(gè)字符設(shè)定了統(tǒng)一并且唯一的二進(jìn)制編碼，以滿足跨語(yǔ)言、跨平臺(tái)進(jìn)行文本轉(zhuǎn)換、處理的要求。國(guó)際組織制定的Unicode標(biāo)準(zhǔn)，采用兩個(gè)字節(jié)來(lái)表示一個(gè)數(shù)字、字母、符號(hào)或文字，并為中文、日文等都分配了相應(yīng)的碼段（碼值連續(xù)的區(qū)間），以實(shí)現(xiàn)各種文字的國(guó)際交流。第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示Unicode碼03數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示三、漢字表示03“大”da10110100111101110000001100000000000000110000000000000011000000000000001100000100111111111111111100000011000000000000001100000000000000110000000000000011000000000000001110000000000001100100000000001100001000000001100000110000000100000001100000100000000011101100000000000100計(jì)算機(jī)內(nèi)部由外到內(nèi)由內(nèi)到外2個(gè)字節(jié)表示一個(gè)漢字大漢字內(nèi)碼漢字輸入碼漢字字形碼0011010001110111國(guó)標(biāo)碼1011010011110111機(jī)內(nèi)碼計(jì)算機(jī)內(nèi)部對(duì)漢字進(jìn)行存儲(chǔ)、處理的漢字代碼。用兩個(gè)字節(jié)表示，每個(gè)字節(jié)的最高位都是1國(guó)標(biāo)碼+8080H

=漢字內(nèi)碼數(shù)據(jù)表示數(shù)字碼（區(qū)位碼和電報(bào)碼）音碼（全拼和雙拼）形碼（五筆字型）音形碼（智能ABC）所有字形編碼的集合稱為字庫(kù)點(diǎn)陣:

1代表亮、0代表不亮。

矢量：每個(gè)字形通過(guò)數(shù)學(xué)曲線描述。第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示四、音頻表示用計(jì)算機(jī)對(duì)音頻信息處理，就要將模擬信號(hào)（如語(yǔ)音、音樂(lè)等）轉(zhuǎn)換成數(shù)字信號(hào)。模擬信號(hào)采樣量化編碼數(shù)字信號(hào)時(shí)間離散幅值連續(xù)3.0129623….136731507703數(shù)據(jù)表示每秒鐘存儲(chǔ)聲音容量的公式為：

采樣頻率×采樣精度×聲道數(shù)/8=字節(jié)數(shù)第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示分辨率（行、列）和顏色深度采樣：用多少個(gè)像素點(diǎn)的“列數(shù)×行數(shù)”表示，分辨率越高，圖像越清晰，存儲(chǔ)量也越大。

圖像采樣量化數(shù)字圖像03數(shù)據(jù)表示五、圖形圖像表示指單位長(zhǎng)度內(nèi)包含像素點(diǎn)的數(shù)量；分辨率單位：dpi（點(diǎn)/英寸）等。第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示①黑白圖

圖像的顏色深度為1，則用一個(gè)二進(jìn)制位1和0表示純白、純黑兩種情況；②灰度圖

圖像的顏色深度為8，占一個(gè)字節(jié)，灰度級(jí)別為256級(jí)。通過(guò)調(diào)整黑白兩色的程度（稱顏色灰度）來(lái)有效地顯示單色圖像；③RGB24位真彩色由紅、綠、藍(lán)三基色通過(guò)不同的強(qiáng)度混合而成，當(dāng)強(qiáng)度分成256級(jí)（值為0～255），每個(gè)像素點(diǎn)占3個(gè)字節(jié)24位，就構(gòu)成了224=16777216種顏色的“真彩色”圖像。03數(shù)據(jù)表示量化：量化是在圖像離散化后，將表示圖像色彩濃淡的連續(xù)變化值化為整數(shù)值的過(guò)程。把量化時(shí)所確定的整數(shù)值取值個(gè)數(shù)稱為量化級(jí)數(shù),也稱為顏色深度.第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示03數(shù)據(jù)表示一個(gè)像素的位數(shù)越多，顏色深度越深，表達(dá)的顏色數(shù)目就越多，所占用的存儲(chǔ)空間越大。相反，如果顏色深度太小，圖像讓人覺(jué)得粗糙和很不自然。圖像的分辨率和像素位的顏色深度決定了圖像文件的大小，計(jì)算公式為：

列數(shù)×行數(shù)×顏色深度÷8=圖像字節(jié)數(shù)視頻是將一幅幅獨(dú)立圖像組成的序列按照一定的速率連續(xù)播放，利用視覺(jué)暫留現(xiàn)象在人的眼前呈現(xiàn)出連續(xù)運(yùn)動(dòng)的畫(huà)面。模擬視頻常用兩種標(biāo)準(zhǔn)：NTSC制式(30幀/秒，525行/幀)PAL制式（25幀/秒，625行/幀），我國(guó)采用PAL制式。640×480×3×30×60=1658880000字節(jié)分辨率幀/秒采樣深度時(shí)間第三節(jié)計(jì)算機(jī)中的數(shù)據(jù)表示六、視頻表示容量=列數(shù)×行數(shù)×像素的顏色深度/8×幀/秒=字節(jié)數(shù)真彩色03數(shù)據(jù)表示04圖靈機(jī)模型04圖靈機(jī)模型蘋(píng)果之父：史蒂夫·喬布斯TuringAward一、圖靈及貢獻(xiàn)圖靈是誰(shuí)？他做了什么？為什么要以他的名字命名？模仿游戲了解圖靈的一生04圖靈機(jī)模型1966年開(kāi)始，美國(guó)計(jì)算機(jī)學(xué)會(huì)(AssociationforComputingMachinery—ACM)每年頒發(fā)“圖靈獎(jiǎng)”(TuringAward)給世界上最優(yōu)秀的計(jì)算機(jī)科學(xué)家1912年6月，生于倫敦，中學(xué)期間獲國(guó)王愛(ài)德華六世數(shù)學(xué)金盾獎(jiǎng)?wù)?935年，當(dāng)選劍橋大學(xué)國(guó)王學(xué)院院士1937年，發(fā)表論文-論數(shù)字計(jì)算在決斷難題中的應(yīng)用，提出圖靈機(jī)，1938年，美國(guó)普林斯頓大學(xué)獲博士學(xué)位1938-1945年二戰(zhàn)期間，密碼破譯工作1946年，獲不列顛帝國(guó)勛章1950年，發(fā)表論文-機(jī)器能思考嗎，提出“圖靈測(cè)試”.

(開(kāi)啟了人工智能的研究)1951年，當(dāng)選英國(guó)皇家學(xué)會(huì)會(huì)員(家族中第四位皇家學(xué)會(huì)會(huì)員)1954年，逝世04圖靈機(jī)模型圖靈的貢獻(xiàn)

圖靈機(jī)模型：解決了可計(jì)算問(wèn)題

計(jì)算機(jī)的理論問(wèn)題圖靈測(cè)試：回答什么機(jī)器具有智能人工智能的理論基礎(chǔ)計(jì)算機(jī)科學(xué)之父人工智能之父1937年，圖靈發(fā)表著名論文《論可計(jì)算在判定問(wèn)題中的應(yīng)用》提出理想的計(jì)算機(jī)的數(shù)學(xué)模型---圖靈機(jī)（TuringMachine）1950年，圖靈發(fā)表了論文“計(jì)算機(jī)和智能”(ComputingMachineryandIntelligence)—“圖靈測(cè)試”(TuringTest)。04圖靈機(jī)模型計(jì)算機(jī)中的問(wèn)題

可計(jì)算：不可計(jì)算：如漢諾塔問(wèn)題

設(shè)函數(shù)的定義域?yàn)镈,值域?yàn)镽,如果存在一種算法，對(duì)D中任意給定的x，都能計(jì)算出f(x),則稱函數(shù)f是可計(jì)算的。三、圖靈機(jī)研究思路：為計(jì)算建立一個(gè)數(shù)學(xué)模型，稱之為計(jì)算模型。計(jì)算模型能夠完成的任務(wù)就是可計(jì)算任務(wù)，也就是可計(jì)算問(wèn)題。04圖靈機(jī)模型圖靈機(jī)由圖靈提出的一種抽象計(jì)算模型，即將人們使用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程進(jìn)行抽象，由一個(gè)虛擬的機(jī)器替代人們進(jìn)行數(shù)學(xué)運(yùn)算。

圖靈機(jī)模型是計(jì)算機(jī)科學(xué)最核心的理論之一，它不僅指導(dǎo)了現(xiàn)代電子計(jì)算機(jī)的設(shè)計(jì)，為計(jì)算機(jī)設(shè)計(jì)指明了方向，并且是算法分析和程序語(yǔ)言設(shè)計(jì)的基礎(chǔ)理論。http://.04圖靈機(jī)模型1、圖靈機(jī)的構(gòu)成無(wú)限長(zhǎng)的紙帶（tape，存儲(chǔ)帶）紙帶被劃分為若干小格子，每個(gè)格子存儲(chǔ)一個(gè)數(shù)字或符號(hào)。

讀寫(xiě)頭（head）。讀寫(xiě)頭在紙帶上移動(dòng)，對(duì)所指格子上的符號(hào)或數(shù)字進(jìn)行讀取或修改?？刂瞥绦蛑噶顮顟B(tài)寄存器。記錄圖靈機(jī)的當(dāng)前狀態(tài)，并且有一種特殊狀態(tài)為停機(jī)狀態(tài)。04圖靈機(jī)模型1111111q111Rq1q1b1Rq2q211Rq2q2bbLq3q31bHq3q3bbHq3當(dāng)前狀態(tài)：q1圖靈機(jī)開(kāi)始工作：①讀寫(xiě)頭讀出存儲(chǔ)帶上當(dāng)前方格中的字母/數(shù)字②根據(jù)控制器當(dāng)前狀態(tài)和所讀到的字符，找到相應(yīng)程序語(yǔ)句③根據(jù)相應(yīng)語(yǔ)句，做三個(gè)動(dòng)作2、圖靈機(jī)運(yùn)行機(jī)理04圖靈機(jī)模型1111111q111Rq1q1b1Rq2q211Rq2q2bbLq3q31bHq3q3bbHq3當(dāng)前狀態(tài)：q3圖靈機(jī)做了什么事？圖靈機(jī)停機(jī)意味著什么？停機(jī)表示計(jì)算完畢，表示當(dāng)前存儲(chǔ)帶上保留的是計(jì)算結(jié)果。對(duì)于一個(gè)問(wèn)題的輸入A,問(wèn)：A能否推證出B?如果能找到一個(gè)圖靈機(jī)，得到對(duì)應(yīng)符號(hào)序列B，則A到B是可計(jì)算的，否則問(wèn)題是不可計(jì)算的。04圖靈機(jī)模型圖靈機(jī)為什么受到重視？

簡(jiǎn)單！

強(qiáng)大！

可實(shí)現(xiàn)！3、圖靈機(jī)的意義可計(jì)算性的判定：凡是能用算法解決的問(wèn)題，也一定能用圖靈機(jī)解決；凡是圖靈機(jī)解決不了的問(wèn)題，任何算法也解決不了。給出一個(gè)可實(shí)現(xiàn)的通用計(jì)算模型：思維模型引入通過(guò)“讀寫(xiě)符號(hào)”和“狀態(tài)改變”進(jìn)行運(yùn)算的思想證實(shí)基于簡(jiǎn)單的字母表完成復(fù)雜運(yùn)算的能力引入存儲(chǔ)區(qū)、程序、控制器等概念的原型：本身沒(méi)有帶來(lái)計(jì)算機(jī)的發(fā)明04圖靈機(jī)模型漢諾塔問(wèn)題---現(xiàn)實(shí)中難以計(jì)算的問(wèn)題64個(gè)直徑大小不一的盤(pán)子從下往上按照從大到小的順序放在第一根柱子上，形成一座漢諾塔。并按照以下規(guī)定將第一根柱子上的64個(gè)盤(pán)子借助第二根柱子，全部移到第三根柱子。

①每次只能移動(dòng)一個(gè)盤(pán)子；

②盤(pán)子只能在三根柱子上來(lái)回移動(dòng)，不能放在他處；

③在移動(dòng)過(guò)程中，三根柱子上的盤(pán)子必須始終保持大盤(pán)在下，小盤(pán)在上。04圖靈機(jī)模型搬多少次搬完？一個(gè)盤(pán)子直接將盤(pán)子從A移動(dòng)到C：一次（21-1）04圖靈機(jī)模型搬多少次搬完？二個(gè)盤(pán)子①將盤(pán)子1從A移動(dòng)到B②將盤(pán)子2從A移動(dòng)到C③將盤(pán)子1從B移動(dòng)到C三次（22-1）04圖靈機(jī)模型搬多少次搬完？三個(gè)盤(pán)子23-1=7次64個(gè)盤(pán)子時(shí)，最佳移動(dòng)盤(pán)子次數(shù)為：264-1=18446744073709551615。假設(shè)移動(dòng)一次盤(pán)子需要1秒鐘，不停搬動(dòng)，需要大約5849億年時(shí)間。

理論上可以計(jì)算的問(wèn)題，在實(shí)際中并不一定能行?？捎?jì)算問(wèn)題需要考慮計(jì)算量是否超過(guò)了目前的計(jì)算能力。謝謝第3章數(shù)據(jù)思維

數(shù)據(jù)的組織數(shù)據(jù)的管理02

數(shù)據(jù)的價(jià)值0301本章目錄01數(shù)據(jù)的組織數(shù)據(jù)的組織011、數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的組織012、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)在內(nèi)存中存放有兩種形態(tài)：一是存放數(shù)據(jù)的內(nèi)存單元地址是相鄰的，二是存放數(shù)據(jù)的內(nèi)存單元地址不相鄰。因此，當(dāng)數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元中，其數(shù)據(jù)之間的邏輯關(guān)系和存儲(chǔ)關(guān)系是一致的，這樣的存儲(chǔ)結(jié)構(gòu)稱為順序存儲(chǔ)結(jié)構(gòu)。當(dāng)數(shù)據(jù)元素存放在任意的存儲(chǔ)單元中，這組存儲(chǔ)單元可以是連續(xù)的或不連續(xù)的，數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能反映其邏輯關(guān)系，通常使用地址指針來(lái)表示數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系，這種存儲(chǔ)結(jié)構(gòu)稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。此外，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)還有索引存儲(chǔ)結(jié)構(gòu)和散列（Hash）存儲(chǔ)結(jié)構(gòu)，這兩種存儲(chǔ)結(jié)構(gòu)并不是一種“全新”的存儲(chǔ)結(jié)構(gòu)，而是在前兩種存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上擴(kuò)展定義出的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的組織013、數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)是計(jì)算機(jī)處理符號(hào)的總稱，數(shù)據(jù)是由數(shù)據(jù)元素構(gòu)成的，數(shù)據(jù)元素之間存在關(guān)系，數(shù)據(jù)的存儲(chǔ)需要根據(jù)內(nèi)存的特點(diǎn)選擇適當(dāng)?shù)姆绞竭M(jìn)行存儲(chǔ)，由此，數(shù)據(jù)結(jié)構(gòu)DS可用一個(gè)三元組描述為：DS=（E,R,M）其中，E表示數(shù)據(jù)元素的集合，R表示數(shù)據(jù)元素之間關(guān)系的集合，M表示存儲(chǔ)數(shù)據(jù)元素的存儲(chǔ)單元的集合。數(shù)據(jù)的組織01線性表數(shù)據(jù)的組織01樹(shù)（1）度。一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)稱為此結(jié)點(diǎn)的度，樹(shù)中所有結(jié)點(diǎn)的度的最大值稱為樹(shù)的度。（2）樹(shù)的高度。樹(shù)中的結(jié)點(diǎn)有層次之分，從根結(jié)點(diǎn)開(kāi)始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依次類(lèi)推，樹(shù)中所有結(jié)點(diǎn)的層次的最大值稱為樹(shù)的高度，亦稱深度。（3）葉子結(jié)點(diǎn)和分支結(jié)點(diǎn)。根據(jù)結(jié)點(diǎn)的度，樹(shù)中的結(jié)點(diǎn)可以分為兩類(lèi)，一類(lèi)是度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)；一類(lèi)是度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。（4）雙親結(jié)點(diǎn)、孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。（5）祖先結(jié)點(diǎn)和子孫結(jié)點(diǎn)。從根結(jié)點(diǎn)到某一個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)，以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。樹(shù)是指在n（n≥0）個(gè)結(jié)點(diǎn)構(gòu)成的有限集合T中，當(dāng)n=0時(shí)，稱為空樹(shù)；當(dāng)n>0時(shí)，稱為非空樹(shù)，且滿足如下條件：（1）樹(shù)有一個(gè)稱為根（Root）的結(jié)點(diǎn)，即根結(jié)點(diǎn)，該結(jié)點(diǎn)沒(méi)有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。（2）除根結(jié)點(diǎn)之外的其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m≥0）個(gè)互不相交的有限集T1，T2，T3，...，Tm，其中子集Ti又是一棵樹(shù)，稱為根結(jié)點(diǎn)的子樹(shù)。數(shù)據(jù)的組織01樹(shù)在一棵樹(shù)中，如果各子樹(shù)之間是有先后次序的，則稱為有序樹(shù)，否則稱為無(wú)序樹(shù)。二叉樹(shù)（BinaryTree）是一棵除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)的有序樹(shù)，即結(jié)點(diǎn)的度都不大于2。與此同時(shí)，二叉樹(shù)的這兩棵子樹(shù)有左右之分，其次序不能任意顛倒，位于左邊的子樹(shù)稱為左子樹(shù)，位于右邊的子樹(shù)稱為右子樹(shù)。數(shù)據(jù)的組織01圖圖由頂點(diǎn)和頂點(diǎn)之間的邊的集合組成，設(shè)V為圖G頂點(diǎn)的非空有限集合，圖G中每一條邊的兩個(gè)頂點(diǎn)互為鄰接點(diǎn)，E是圖G邊的有限集合，則圖G可形式化描述為：G=<V，E>若圖中的每條邊沒(méi)有方向，則稱該圖為無(wú)向圖，無(wú)向圖中的邊均為頂點(diǎn)的無(wú)序?qū)?。若圖中的每條邊是有方向的，則稱該圖是有向圖，有向圖中的邊也稱為弧，是由兩個(gè)頂點(diǎn)構(gòu)成的有序?qū)?2數(shù)據(jù)的管理02數(shù)據(jù)的管理一、數(shù)據(jù)庫(kù)系統(tǒng)DBMS管理數(shù)據(jù)庫(kù)的一種系統(tǒng)軟件DBA完成某一功能的應(yīng)用程序1應(yīng)用程序2應(yīng)用程序nDBAP1DBAP2DBAPn相互有關(guān)聯(lián)關(guān)系的表形式數(shù)據(jù)的集合數(shù)據(jù)庫(kù)//DatabaseDBMS如何支持用戶操縱數(shù)據(jù)庫(kù)？數(shù)據(jù)庫(kù)(DB):Database數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS):DatabaseManagementSystem數(shù)據(jù)庫(kù)應(yīng)用(DBAP):DataBaseApplication數(shù)據(jù)庫(kù)管理員(DBA):DataBaseAdministrator計(jì)算機(jī)軟硬件02數(shù)據(jù)的管理二、數(shù)據(jù)模型數(shù)據(jù)模型是一組嚴(yán)格定義的概念集合，是對(duì)現(xiàn)實(shí)世界中的事物特征、聯(lián)系和行為的抽象。數(shù)據(jù)模型精確地描述了系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)完整性約束條件。02數(shù)據(jù)的管理概念數(shù)據(jù)模型簡(jiǎn)稱概念模型，是對(duì)現(xiàn)實(shí)世界的第一層抽象，用戶和數(shù)據(jù)庫(kù)設(shè)計(jì)人員之間進(jìn)行交流的工具。概念模型是整個(gè)數(shù)據(jù)模型的基礎(chǔ)，側(cè)重于對(duì)客觀世界復(fù)雜事物的結(jié)構(gòu)及它們內(nèi)在聯(lián)系的描述，與具體的計(jì)算機(jī)平臺(tái)和數(shù)據(jù)庫(kù)管理系統(tǒng)無(wú)關(guān)的。目前常用概念模型是實(shí)體-聯(lián)系模型（Entity-RelationshipModel，E-R模型）課程學(xué)生選修學(xué)號(hào)姓名年齡性別系別課程號(hào)學(xué)分課程名成績(jī)mn用矩形表示實(shí)體型；用橢圓表示屬性；用菱形表示聯(lián)系，并標(biāo)示出聯(lián)系的類(lèi)型02數(shù)據(jù)的管理邏輯數(shù)據(jù)模型簡(jiǎn)稱邏輯模型，是客觀世界的抽象描述到信息世界的轉(zhuǎn)換。邏輯模型直接與DBMS有關(guān)，概念模型只有在轉(zhuǎn)換成邏輯模型后才能在數(shù)據(jù)庫(kù)中得以表示。目前成熟的邏輯模型有層次模型（HierarchicalModel）、網(wǎng)狀模型（NetworkModel）、關(guān)系模型（RelationalModel）以及面向?qū)ο竽Ｐ停∣bjectOrientedModel）。02數(shù)據(jù)的管理物理數(shù)據(jù)模型簡(jiǎn)稱物理模型，是面向計(jì)算機(jī)物理表示的模型，是信息世界模型在機(jī)器世界的實(shí)現(xiàn)，即將信息世界的實(shí)體及其聯(lián)系抽象為便于計(jì)算機(jī)存儲(chǔ)的二進(jìn)制格式。物理模型給出了數(shù)據(jù)模型在計(jì)算機(jī)上真正的物理結(jié)構(gòu)的表示。02數(shù)據(jù)的管理三、關(guān)系數(shù)據(jù)庫(kù)市場(chǎng)上常見(jiàn)的關(guān)系數(shù)據(jù)庫(kù)產(chǎn)品包括Oracle、SQLServer、MySQL、DB2等關(guān)系數(shù)據(jù)庫(kù)按照結(jié)構(gòu)化的方法存儲(chǔ)數(shù)據(jù)，每個(gè)數(shù)據(jù)表的結(jié)構(gòu)都事先定義好（比如表的名稱、字段名稱、字段類(lèi)型、約束等），然后根據(jù)表的結(jié)構(gòu)，數(shù)據(jù)以行和列的方式進(jìn)行存儲(chǔ)，讀取和查詢都十分方便，可靠性和穩(wěn)定性都比較高02數(shù)據(jù)的管理02數(shù)據(jù)的管理基本動(dòng)作對(duì)基本動(dòng)作的抽象【并】操作

【差】操作

【積】操作

【選擇】操作

【投影】操作

解釋這種組合,并按次序調(diào)用基本動(dòng)作予以執(zhí)行程序執(zhí)行機(jī)構(gòu)程序指令基本動(dòng)作SelectSnameFromStudent,SCWhereStudent.S#=SC.S#andSC.C#=‘001’OrderByScoreDESC;

Sname(student.s#=sc.s#(StudentSC))關(guān)系模型基本運(yùn)算關(guān)系模型基本運(yùn)算的各種組合SQL語(yǔ)言數(shù)據(jù)庫(kù)管理系統(tǒng)復(fù)雜動(dòng)作=基本動(dòng)作的各種方式的組合02數(shù)據(jù)的管理02數(shù)據(jù)的管理關(guān)系數(shù)據(jù)庫(kù)（按行存儲(chǔ)數(shù)據(jù)，按列按類(lèi)型區(qū)分）第一種NoSQL數(shù)據(jù)庫(kù)（按“屬性名：屬性值”對(duì)存儲(chǔ)數(shù)據(jù)，均為字符串?dāng)?shù)據(jù)）第二種NoSQL數(shù)據(jù)庫(kù)（按文檔存儲(chǔ)數(shù)據(jù)，一行是一個(gè)文檔）第二種NoSQL數(shù)據(jù)庫(kù)（按文檔存儲(chǔ)數(shù)據(jù)，一行是一個(gè)文檔，文檔中還可能嵌入文檔）與關(guān)系數(shù)據(jù)庫(kù)相比，最大的優(yōu)點(diǎn)：（1）可擴(kuò)展性—可隨時(shí)增加新屬性列和減少屬性列，而無(wú)須改變以前存儲(chǔ)的數(shù)據(jù)。（2）無(wú)需事先定義模式，可直接操縱數(shù)據(jù)（3）并行/分布處理—可適應(yīng)大規(guī)模并行/分布計(jì)算?！綨oSQL】“不僅是SQL，而不是NO-to-SQL”，不僅能管理結(jié)構(gòu)化數(shù)據(jù)，而且能管理半結(jié)構(gòu)化甚至非結(jié)構(gòu)化數(shù)據(jù)的數(shù)據(jù)庫(kù)。為處理大數(shù)據(jù)，多數(shù)都采用分布式存儲(chǔ)技術(shù)<標(biāo)記>文本</標(biāo)記>“標(biāo)記”:“文本”02數(shù)據(jù)的管理抽象理論設(shè)計(jì)理論支持設(shè)計(jì)：設(shè)計(jì)正確性、完備性判定方法先抽象再設(shè)計(jì)：從管理一個(gè)具體的表，到可管理所有的表抽象：區(qū)分并命名表的每一個(gè)形式要素理論：數(shù)學(xué)化邏輯嚴(yán)密化各種概念；設(shè)計(jì)：語(yǔ)言/實(shí)現(xiàn)/系統(tǒng)理論指導(dǎo)下的抽象：抽象更為嚴(yán)密E.F.Codd,基于對(duì)“表(Table)”的理解:

提出了“關(guān)系”及關(guān)系模型，提出了關(guān)系數(shù)據(jù)庫(kù)理論開(kāi)創(chuàng)了數(shù)據(jù)庫(kù)的時(shí)代，當(dāng)前普遍應(yīng)用的數(shù)據(jù)庫(kù)管理系統(tǒng)的奠基者獲得了計(jì)算機(jī)領(lǐng)域最高獎(jiǎng)“圖靈獎(jiǎng)”03數(shù)據(jù)的價(jià)值03數(shù)據(jù)的價(jià)值1、大數(shù)據(jù)的概念大數(shù)據(jù)由巨型數(shù)據(jù)集組成，這些數(shù)據(jù)集的大小常超出人們?cè)诳山邮軙r(shí)間內(nèi)的收集、應(yīng)用、管理和處理能力。大數(shù)據(jù)具有數(shù)據(jù)量大（Volume）、數(shù)據(jù)類(lèi)型多樣（Variety）、處理速度快（Velocity）和價(jià)值密度低（Value）的特點(diǎn)。03數(shù)據(jù)的價(jià)值2、思維轉(zhuǎn)變由于數(shù)據(jù)已經(jīng)具備了資本的屬性，可以用來(lái)創(chuàng)造經(jīng)濟(jì)價(jià)值，因此，大數(shù)據(jù)時(shí)代思維方式也在發(fā)生轉(zhuǎn)變。維克托·邁爾·舍恩伯格在《大數(shù)據(jù)時(shí)代：生活、工作與思維的大變革》一書(shū)中明確指出，大數(shù)據(jù)時(shí)代最大的轉(zhuǎn)變就是思維方式的3種轉(zhuǎn)變，即全樣而非抽樣、效率而非精確、相關(guān)而非因果。03數(shù)據(jù)的價(jià)值3、大數(shù)據(jù)的應(yīng)用03數(shù)據(jù)的價(jià)值4、數(shù)據(jù)挖掘數(shù)據(jù)挖掘，又稱為數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)，它是一個(gè)從大量數(shù)據(jù)中抽取挖掘出未知的、有價(jià)值的模式或規(guī)律等知識(shí)的復(fù)雜過(guò)程。簡(jiǎn)單地講就是從大量數(shù)據(jù)中挖掘或抽取出知識(shí)。03數(shù)據(jù)的價(jià)值數(shù)據(jù)對(duì)超市經(jīng)營(yíng)有無(wú)幫助呢?客戶購(gòu)買(mǎi)習(xí)慣商品組合方式及策略……營(yíng)銷(xiāo)策略價(jià)格策略貨源組織03數(shù)據(jù)的價(jià)值數(shù)據(jù)挖掘之關(guān)聯(lián)規(guī)則挖掘商品的關(guān)聯(lián)規(guī)則“尿布”?“啤酒”

[支持度=2%，置信度=60%]

“由尿布的購(gòu)買(mǎi)，能夠推斷出啤酒的購(gòu)買(mǎi)”支持度2%意味著所分析事務(wù)的2%同時(shí)購(gòu)買(mǎi)尿布和啤酒置信度60%意味著購(gòu)買(mǎi)尿布的顧客60%也購(gòu)買(mǎi)啤酒。03數(shù)據(jù)的價(jià)值5、數(shù)據(jù)倉(cāng)庫(kù)數(shù)據(jù)倉(cāng)庫(kù)（DataWarehouse）是一個(gè)面向主題的、集成的、相對(duì)穩(wěn)定的、反映歷史變化的數(shù)據(jù)集合，用于支持管理決策。謝謝聆聽(tīng)DATATHINKING第4章算法思維ALGORITHMICTHINKING算法分析03本章目錄01

什么是算法02算法實(shí)現(xiàn)01什么是算法什么是算法01

假設(shè)某商場(chǎng)銷(xiāo)售的某種商品單價(jià)25元，每年可銷(xiāo)售3萬(wàn)件。設(shè)該商品每件提價(jià)1元，則銷(xiāo)售量減少0.1萬(wàn)件。如果要使總銷(xiāo)售收入不少于75萬(wàn)元，求該商品的最高提價(jià)。如何讓你用計(jì)算機(jī)進(jìn)行求解，你怎么做？什么是算法01如何讓你用計(jì)算機(jī)進(jìn)行求解，你怎么做？旅行推銷(xiāo)員問(wèn)題TSP：假設(shè)你計(jì)劃要進(jìn)行一次旅行推銷(xiāo)，有幾個(gè)城市是你要穿越的地方。要求：

——所走路程最短

——每個(gè)城市只能訪問(wèn)一次

——從某城市出發(fā)，最后回到該城市什么是算法011、算法的基本定義程序=算法+數(shù)據(jù)結(jié)構(gòu)1984年圖靈獎(jiǎng)獲得者、Pascal之父及結(jié)構(gòu)化程序設(shè)計(jì)的首創(chuàng)者、瑞士計(jì)算機(jī)科學(xué)家尼克勞斯·沃斯（NicklausWirth）程序：為刻畫(huà)和解決現(xiàn)實(shí)世界的問(wèn)題，在數(shù)據(jù)的某些特定的表示方式和結(jié)構(gòu)的基礎(chǔ)上對(duì)抽象算法的具體表述。---代碼數(shù)據(jù)結(jié)構(gòu)：現(xiàn)實(shí)世界的數(shù)據(jù)模型算法是一個(gè)有窮規(guī)則的集合，它用規(guī)則規(guī)定了解決特定類(lèi)型問(wèn)題的運(yùn)算序列，或者規(guī)定了任務(wù)執(zhí)行或問(wèn)題求解的一系列步驟。01算法特征有窮性（可終止性）確定性輸入輸出能行性算法必須在有限的操作步驟內(nèi)以及合理的時(shí)間內(nèi)執(zhí)行完成。明確的開(kāi)始和結(jié)束算法中的每一個(gè)操作步驟都必須有明確的含義，不允許存在二義性。①算法中每一個(gè)步驟必須能夠?qū)崿F(xiàn)，如不允許分母為0。②算法執(zhí)行結(jié)果要能夠達(dá)到預(yù)期的目的，實(shí)現(xiàn)預(yù)定的功能。算法有0個(gè)或多個(gè)輸入。什么是算法2、算法的特征算法有1個(gè)或多個(gè)輸出。02算法實(shí)現(xiàn)02算法算法策略數(shù)學(xué)建模數(shù)據(jù)結(jié)構(gòu)控制結(jié)構(gòu)程序設(shè)計(jì)算法正確性與復(fù)雜性問(wèn)題問(wèn)題的求解算法實(shí)現(xiàn)02算法實(shí)現(xiàn)一、數(shù)學(xué)建模數(shù)學(xué)建模：用數(shù)學(xué)語(yǔ)言描述實(shí)際現(xiàn)象的過(guò)程，即建立數(shù)學(xué)模型的過(guò)程。數(shù)學(xué)模型：對(duì)實(shí)際問(wèn)題的一種數(shù)學(xué)表述，是關(guān)于部分現(xiàn)實(shí)世界為某種目的的一個(gè)抽象的簡(jiǎn)化的數(shù)學(xué)結(jié)構(gòu)。旅行推銷(xiāo)員問(wèn)題TSP：假設(shè)你計(jì)劃要進(jìn)行一次旅行推銷(xiāo)，有幾個(gè)城市是你要穿越的地方。要求：

——所走路程最短

——每個(gè)城市只能訪問(wèn)一次

——從某城市出發(fā)，最后回到該城市02數(shù)字編號(hào)代替城市名，編號(hào)之間線段長(zhǎng)度用城市之間的距離描述算法實(shí)現(xiàn)路線1：

→

→

→

→

→

→①

路線總距離：1640公里路線2：①→③→④→⑥→⑤→②→①

路線總距離：1550公里

路線3：

→

→

→

→

→

→

路線總距離：1640公里不同路線的結(jié)果02算法實(shí)現(xiàn)

旅行推銷(xiāo)員問(wèn)題是圖論中最著名的問(wèn)題之一，即“已給一個(gè)n個(gè)點(diǎn)的完全圖，每條邊都有一個(gè)長(zhǎng)度，求總長(zhǎng)度最短的經(jīng)過(guò)每個(gè)頂點(diǎn)正好一次的封閉回路”。02算法實(shí)現(xiàn)二、算法策略蠻干/遍歷遍歷算法求解TSP問(wèn)題：列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。所有路徑組合及其長(zhǎng)度蠻干/遍歷策略會(huì)帶來(lái)怎樣的問(wèn)題？組合爆炸路徑組合數(shù)目：(n-1)!20個(gè)城市，遍歷總數(shù)1.216×1017計(jì)算機(jī)以每秒檢索1000萬(wàn)條路線的計(jì)算速度，需386年。2001年解決了德國(guó)15112個(gè)城市的TSP問(wèn)題，使用了美國(guó)Rice大學(xué)和普林斯頓大學(xué)之間互連的、速度為500MHz

的CompaqEV6Alpha處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)算機(jī)花費(fèi)的時(shí)間之和為22.6年。02算法實(shí)現(xiàn)TSP問(wèn)題，有沒(méi)有其他求解算法呢？最優(yōu)解

vs.可行解不同的算法設(shè)計(jì)策略：遍歷、搜索算法分治算法貪心算法動(dòng)態(tài)規(guī)劃算法……算法策略可行解最優(yōu)解TSP問(wèn)題的可行解與最優(yōu)解示意貪心算法是一種算法策略?；舅枷搿敖癯芯平癯怼?一定要做當(dāng)前情況下的最好選擇，否則將來(lái)可能會(huì)后悔，故名“貪心”。從某一個(gè)城市開(kāi)始，每次選擇一個(gè)城市，直到所有城市都被走完。每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過(guò)的路徑總距離最短。02童年時(shí)，大人給小孩講故事：從前有座山，山上有個(gè)廟，廟里有個(gè)老和尚和小和尚，老和尚給小和尚講故事，講的是：從前有座山，山上有個(gè)廟，……。算法實(shí)現(xiàn)遞歸的典型聽(tīng)覺(jué)和視覺(jué)形式---自相似性事物的無(wú)限重復(fù)性構(gòu)造遞歸與迭代02算法實(shí)現(xiàn)遞歸與迭代求n!的算法或程序--用迭代和遞歸方法構(gòu)造有什么不同？02算法實(shí)現(xiàn)longintFact(intn){intcounter；

longproduct=1;forcounter=1tonstep1{product=product*counter；}/*迭代*/returnproduct;} CounterProduct初始值1

Fact(5)的執(zhí)行過(guò)程【示例】求n!的算法或程序--用迭代方法構(gòu)造：循環(huán)-替代-遞推循環(huán)第1次 1 1循環(huán)第2次 2 2循環(huán)第3次 3 6循環(huán)第4次 4 24循環(huán)第5次 5 120退出循環(huán) 6 12002算法實(shí)現(xiàn)longintFact(intn){longintx; If(n>1){x=Fact(n-1);/*遞歸調(diào)用*/returnn*x;}elsereturn1;/*遞歸基礎(chǔ)*/}n>1返回結(jié)果1X=Fact(n-1)NY返回結(jié)果n*X開(kāi)始結(jié)束傳進(jìn)的參數(shù)nFact(n)

【示例】求n!的算法或程序--用遞歸方法構(gòu)造：函數(shù)調(diào)用運(yùn)用遞歸進(jìn)行程序構(gòu)造：函數(shù)結(jié)構(gòu)，自身調(diào)用自身，高階調(diào)用低階02算法實(shí)現(xiàn)n>1返回結(jié)果1X=Fact(n-1)NY返回結(jié)果n*X開(kāi)始結(jié)束傳進(jìn)的參數(shù)nn>1返回結(jié)果1X=Fact(n-1)NY返回結(jié)果n*X開(kāi)始結(jié)束傳進(jìn)的參數(shù)nn>1返回結(jié)果1X=Fact(n-1)NY返回結(jié)果n*X開(kāi)始結(jié)束傳進(jìn)的參數(shù)nn>1返回結(jié)果1X=Fact(n-1)NY返回結(jié)果n*X開(kāi)始結(jié)束傳進(jìn)的參數(shù)nFact(4)4返回4!=24Fact(3)返回3!=624Fact(2)返回2!=2Fact(1)返回1!=13622114

63

22

112602算法實(shí)現(xiàn)h(0)h(n+1)h(0)h(n+1)尋找路徑沿路徑計(jì)算沿一致路徑計(jì)算h(0)h(n+1)可能計(jì)算路徑并不同迭代/遞推遞歸通常，只能由函數(shù)結(jié)構(gòu)實(shí)現(xiàn)在前次結(jié)果基礎(chǔ)上進(jìn)行計(jì)算可采用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)02算法實(shí)現(xiàn)偽代碼表達(dá)算法：Begin

輸入變量x，y；ify=0then輸出錯(cuò)誤提示else

z=x/y輸出zEndif;End自然語(yǔ)言表達(dá)算法：開(kāi)始輸入變量x，y；判斷y是否為0；如果y=0，則輸出錯(cuò)誤提示；否則計(jì)算z=x/y；輸出z。結(jié)束優(yōu)點(diǎn)：簡(jiǎn)單，便于閱讀。缺點(diǎn)：文字冗長(zhǎng)，容易出現(xiàn)歧義。

偽代碼沒(méi)有標(biāo)準(zhǔn)，用類(lèi)似自然語(yǔ)言形式表達(dá)。偽代碼結(jié)構(gòu)清晰、代碼簡(jiǎn)單、可讀性好。算法的表示—控制結(jié)構(gòu)02算法分析03算法思維：復(fù)雜度算法復(fù)雜度：求解問(wèn)題的某一個(gè)算法的復(fù)雜性，反映了一個(gè)算法的效率。通常需要考慮算法執(zhí)行時(shí)所需要的計(jì)算機(jī)資源。時(shí)間復(fù)雜度：衡量算法運(yùn)行速度。空間復(fù)雜度：衡量算法運(yùn)行中所占存儲(chǔ)空間的大小。算法分析03算法分析1、時(shí)間復(fù)雜度的表示問(wèn)題求解算法通常與問(wèn)題規(guī)模n相關(guān)，一個(gè)算法由一些基本步驟組成，則算法基本步驟執(zhí)行的次數(shù)表達(dá)為關(guān)于n的函數(shù)T(n)，稱為時(shí)間復(fù)雜度。時(shí)間復(fù)雜度是衡量算法的運(yùn)行時(shí)間隨著問(wèn)題規(guī)模的增大而增加的趨勢(shì)，而不是具體的運(yùn)行時(shí)間。算法時(shí)間復(fù)雜度常用大O表示（讀為：大圈，Order，big-O）。大O表示法：O(T(n))【例】

求下面算法時(shí)間復(fù)雜度

temp=i;i=j;j=temp;以上語(yǔ)句的頻度均為1，程序執(zhí)行時(shí)間是與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法時(shí)間復(fù)雜度為常數(shù)階時(shí)，記作T(n)=O(1)。如果算法執(zhí)行時(shí)間不隨問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法有上千條語(yǔ)句，其執(zhí)行時(shí)間也是一個(gè)較大的常數(shù)。032、算法時(shí)間復(fù)雜度計(jì)算案例算法分析【例】求下面算法時(shí)間復(fù)雜度

(1)(2)(3)(4)(5)a=0;b=1;for(i=2;i<=n;i++){s=a+b;b=a;a=s;}/*計(jì)算頻度=2次*//*計(jì)算頻度=n次*//*計(jì)算頻度=n-1次*//*計(jì)算頻度=n-1次*//*計(jì)算頻度=n-1次*/03算法時(shí)間復(fù)雜度為：T(n)=2+n+3(n-1)=4n-1=O(n)(1)(2)(3)(4)sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++;/*計(jì)算頻度=1次*//*計(jì)算頻度=n+1次*//*計(jì)算頻度=n（n+1）次*//*計(jì)算頻度=n2次*/算法時(shí)間復(fù)雜度為：T(n)=2n2+2n+2=O(n2)算法分析033、不同量級(jí)復(fù)雜性在計(jì)算時(shí)間方面的差異算法分析03冒泡排序快速排序算法分析03冒泡排序是通過(guò)交換相鄰兩個(gè)元素實(shí)現(xiàn)的思想：比較相鄰2個(gè)元素，如果次序不對(duì)，則將2個(gè)元素位置互換，依次由上往下比較，最終較大（或較?。┑脑叵蛏细∑?，猶如冒泡。算法分析03951426951426951462951642956142965142第一趟：對(duì)6比較算法分析03951426965142965412965421第一趟第二趟第三趟fori=1ton-1forj=1ton-iifA[j]>A[j+1]swap(A[j],A[j+1])冒泡排序的時(shí)間復(fù)雜度？在完全有序的情況下，最好的時(shí)間復(fù)雜度是O(n)，1次冒泡。在極端情況完全逆序，時(shí)間復(fù)雜度為O(n2)(n-1)+(n-2)+…+1=n(n-1)/2算法分析03快速排序的基本思想是：

（1）從列表中取出一個(gè)元素作為“基準(zhǔn)數(shù)”。

（2）比基準(zhǔn)數(shù)大的元素放到它的右邊；

小于基準(zhǔn)數(shù)的元素放到它的左邊；

相同的數(shù)可以放在任一邊。

退出分區(qū)后，基準(zhǔn)數(shù)處于列表中間位置。

（3）利用遞歸算法對(duì)小于基準(zhǔn)數(shù)的元素排序；

然后對(duì)大于基準(zhǔn)數(shù)的元素排序。（4）遞歸結(jié)束條件是列表長(zhǎng)度小于等于1；

當(dāng)列表長(zhǎng)度=0或1時(shí)，排序完成。算法分析03循環(huán)狀態(tài)排序元素列表說(shuō)

明初始狀態(tài)61279345108初始序列，以6為基準(zhǔn)數(shù)第1輪31254697108基準(zhǔn)數(shù)6歸位第2輪31254

以3為基準(zhǔn)數(shù)

21354

基準(zhǔn)數(shù)3歸位第3輪21

以2為基準(zhǔn)數(shù)

12

基準(zhǔn)數(shù)2歸位第4輪1

只有1位，無(wú)需排序第5輪

54

以5為基準(zhǔn)數(shù)

45

基準(zhǔn)數(shù)5歸位第6輪

4

只有1位，無(wú)需排序第7輪

97108以9為基準(zhǔn)數(shù)

87910基準(zhǔn)數(shù)9歸位第8輪

87

8為基準(zhǔn)數(shù)，

78

基準(zhǔn)數(shù)8歸位第9輪

7

7只有1位，無(wú)需排序第10輪

1010只有1位，無(wú)需排序循環(huán)結(jié)束12345678910排序完成算法分析03復(fù)雜度：快速排序624159124659Partition21659最差情況下

——每次Partition都選到最大（?。┑臄?shù)據(jù)——退化為冒泡排序，時(shí)間復(fù)雜度為O(N2)一般情況下——平均時(shí)間復(fù)雜度為O(NlogN)——顯著快于冒泡排序所需時(shí)間快速排序的時(shí)間復(fù)雜度分析：算法分析03多核CPU、集群等：并行化（分布式、大數(shù)據(jù)、云計(jì)算、……）兩種排序算法可以并行執(zhí)行嗎？每個(gè)步驟對(duì)上一步驟存在依賴——冒泡排序算法是不能并行執(zhí)行的算法QuickSort(V,p,q):Ifp<q:m=Partition(V,p,q)QuickSort(V,p,m-1)QuickSort(V,m+1,q)fori=1ton-1forj=1ton-iifA[j]>A[j+1]swap(A[j],A[j+1])——兩個(gè)QuickSort子問(wèn)題之間是相互獨(dú)立的，可以并行——排列順序?qū)artition無(wú)影響，可以并行——快速排序是可以并行執(zhí)行的算法，稱為“可并行性”可并行性是算法計(jì)算復(fù)雜度之上的另一重要考量算法分析謝謝聆聽(tīng)ALGORITHMICTHINKING第5章網(wǎng)絡(luò)思維ALGORITHMICTHINKING

計(jì)算機(jī)網(wǎng)絡(luò)概述

Internet基礎(chǔ)02

網(wǎng)絡(luò)與安全0301本章目錄01計(jì)算機(jī)網(wǎng)絡(luò)概述01計(jì)算機(jī)網(wǎng)絡(luò)概述一、計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展

計(jì)算機(jī)網(wǎng)絡(luò)概述01從市場(chǎng)層面：豐富的網(wǎng)絡(luò)信息資源，尤其是網(wǎng)絡(luò)的交互性，極大地提高人們上網(wǎng)的積極性，網(wǎng)絡(luò)徹底改變?nèi)藗兊纳?、工作方式從技術(shù)層面：個(gè)人電腦（PC）、交換機(jī)和路由器、Web技術(shù)等的誕生和發(fā)展為Internet的興起和發(fā)展提供了技術(shù)保障01計(jì)算機(jī)網(wǎng)絡(luò)概述二、計(jì)算機(jī)網(wǎng)絡(luò)的定義計(jì)算機(jī)網(wǎng)絡(luò)：將地理位置不同的具有獨(dú)立功能的多臺(tái)計(jì)算機(jī)，通過(guò)通信設(shè)備和通信線路連接起來(lái)，在網(wǎng)絡(luò)軟件的管理和協(xié)調(diào)下，實(shí)現(xiàn)資源共享和數(shù)據(jù)通信的計(jì)算機(jī)系統(tǒng)。01計(jì)算機(jī)網(wǎng)絡(luò)概述共享資源：互連計(jì)算機(jī)的目的是為了實(shí)現(xiàn)資源共享，這些資源包括軟件、硬件和數(shù)據(jù)自治系統(tǒng)：能夠獨(dú)立運(yùn)行并提供服務(wù)的系統(tǒng)，連接到計(jì)算機(jī)網(wǎng)絡(luò)中的每個(gè)設(shè)備都應(yīng)該是自治系統(tǒng)。遵守統(tǒng)一的通信標(biāo)準(zhǔn):實(shí)現(xiàn)資源共享就必須相互交換數(shù)據(jù)。相互交換數(shù)據(jù)就必須遵守統(tǒng)一的通信標(biāo)準(zhǔn)三、計(jì)算機(jī)網(wǎng)絡(luò)的特征01計(jì)算機(jī)網(wǎng)絡(luò)概述(a)環(huán)形網(wǎng)絡(luò)(b)星形網(wǎng)絡(luò)(c)總線形網(wǎng)絡(luò)四、網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不同的連接，需要不同的控制規(guī)則-即不同的協(xié)議01計(jì)算機(jī)網(wǎng)絡(luò)概述郵政網(wǎng)絡(luò)Internet發(fā)件人&收件人發(fā)送者&接收者聚集點(diǎn)&發(fā)送點(diǎn)端口號(hào)發(fā)送郵局&接收郵局發(fā)送IP&接收IP郵路發(fā)送或接收站點(diǎn)鏈路層地址,即MAC地址(物理地址)發(fā)件人聚集點(diǎn)郵局發(fā)送站點(diǎn)運(yùn)輸應(yīng)用層傳輸層IP層/網(wǎng)絡(luò)層鏈路層物理生活中的郵政網(wǎng)絡(luò)→計(jì)算機(jī)網(wǎng)絡(luò)01計(jì)算機(jī)網(wǎng)絡(luò)概述五、

網(wǎng)絡(luò)體系結(jié)構(gòu)01計(jì)算機(jī)網(wǎng)絡(luò)概述協(xié)議:為網(wǎng)絡(luò)中各節(jié)點(diǎn)和計(jì)算機(jī)之間的數(shù)據(jù)交換而建立的規(guī)則、標(biāo)準(zhǔn)或約定。事件實(shí)現(xiàn)順序的詳細(xì)說(shuō)明(實(shí)現(xiàn)順序)需要發(fā)出何種控制信息，完成何種動(dòng)作以及作出何種應(yīng)答(如何做)信息交換的結(jié)構(gòu)和格式(做什么)01計(jì)算機(jī)網(wǎng)絡(luò)概述通信子網(wǎng)資源子網(wǎng)各層的任務(wù)處理網(wǎng)絡(luò)應(yīng)用數(shù)據(jù)如何表示主機(jī)間的通信端到端的連接路由尋址介質(zhì)訪問(wèn)接入比特流的傳輸1、OSI參考模型01計(jì)算機(jī)網(wǎng)絡(luò)概述2、TCP/IP協(xié)議傳輸控制協(xié)議（TCP）:提供可靠的數(shù)據(jù)流服務(wù)并進(jìn)行流量控制網(wǎng)際協(xié)議（IP）:為IP數(shù)據(jù)報(bào)(數(shù)據(jù)傳輸?shù)幕締挝?在Internet的發(fā)送、傳輸和接收制定詳細(xì)的規(guī)則簡(jiǎn)潔：較好地平衡了網(wǎng)絡(luò)系統(tǒng)實(shí)現(xiàn)難度和運(yùn)行效率。應(yīng)用層的功能定義更加清晰。開(kāi)放：網(wǎng)絡(luò)接口層為網(wǎng)際層屏蔽了不同類(lèi)型網(wǎng)絡(luò)之間的區(qū)別廣泛應(yīng)用且運(yùn)行穩(wěn)定，是一種既成事實(shí)的工業(yè)標(biāo)準(zhǔn)。實(shí)現(xiàn)網(wǎng)絡(luò)間互連，成為目前操作系統(tǒng)的標(biāo)準(zhǔn)配置。02Internet基礎(chǔ)02Internet基礎(chǔ)

社會(huì)上，每一個(gè)人都有一個(gè)身份證號(hào)碼；互聯(lián)網(wǎng)中，每一臺(tái)電腦都有一個(gè)IP地址Internet：IPv44個(gè)字節(jié)32位Internet2：IPv616個(gè)字節(jié)