計算機科學導論 課件全 沈艷 第1-7章 計算與計算機、邏輯思維-工程思維

第1章計算與計算機本章目錄

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

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

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

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

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

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

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

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

對象是真和假，兩種狀態(tài)與之對應計算機中用二進制優(yōu)勢在計算機的世界里，沒有文字、沒有電影、沒有音樂，只有無數(shù)個0和1！01數(shù)制及轉換

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

101B(17)8

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

1AH二、數(shù)制轉換D(Decimal)B(Binary)O(Octonary)H(Hexadecimal)01數(shù)制及轉換第二節(jié)數(shù)制及轉換按權展開式：每位上的數(shù)碼乘以對應位權之和305.56的按權展開式：

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

101.01B

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

小數(shù)部分:乘基取整順排列01數(shù)制及轉換(2)十進制轉二進制/八進制/十六進制【例】將26.25D轉換為二進制數(shù)第二節(jié)數(shù)制及轉換(3)二進制與八進制、十六進制轉換01數(shù)制及轉換三位一并法（八進制），四位一并法（十六進制）二進制轉換為八/十六進制：從小數(shù)點開始分別向左（整數(shù)）和向右（小數(shù)）劃分數(shù)位，每隔3位/4位一組，最后一組若不足3位/4位則補0,再將每組二進制數(shù)轉換為八/十六進制數(shù)。八/十六進制轉換為二進制：將每1位八/十六進制數(shù)轉換為3位/4位二進制數(shù)按次序寫出。00110101.10111100010110101.101100（265.54）8（35.BC）16第二節(jié)數(shù)制及轉換十進制、十六進制、八進制與二進制之間的對應關系01數(shù)制及轉換第二節(jié)數(shù)制及轉換各種進制之間的轉換方法總結01數(shù)制及轉換02數(shù)據(jù)存儲與運算位（bit）比特：1或者0，是二進制信息組成、處理、存儲、傳輸?shù)淖钚?shù)據(jù)單位。字節(jié)（Byte）：1Byte=8bits，信息存儲的基本單位。字（Word）：計算機在同一時間內處理的一組二進制數(shù)，字由若干字節(jié)構成，字的位數(shù)稱為字長。如8bits、16bits、32bits、64bits等。字長是計算機進行數(shù)據(jù)處理和運算的單位。（1）數(shù)據(jù)存儲單位一、數(shù)據(jù)存儲02數(shù)據(jù)存儲與運算計算機存儲容量的常用表示單位第三節(jié)計算機中的數(shù)據(jù)表示（2）大端和小端存儲內存：以字節(jié)Byte為單位，每個字節(jié)有唯一的地址，就可方便地存取數(shù)據(jù)。數(shù)據(jù)存放：不同的數(shù)據(jù)類型占據(jù)的字節(jié)數(shù)不同。02數(shù)據(jù)存儲與運算intn=100；//占4個字節(jié)doublex=3.56；//占8個字節(jié)第三節(jié)計算機中的數(shù)據(jù)表示02數(shù)據(jù)存儲與運算大端存儲小端存儲inta=0x11223344較高的有效字節(jié)存放在較低的存儲器地址，較低的有效字節(jié)存放在較高的存儲器地址，稱為大端存儲較高的有效字節(jié)存放在較高的存儲器地址，較低的有效字節(jié)存放在較低的存儲器地址，稱為大端存儲第三節(jié)計算機中的數(shù)據(jù)表示02數(shù)據(jù)存儲與運算二、算術運算第三節(jié)計算機中的數(shù)據(jù)表示02數(shù)據(jù)存儲與運算三、邏輯運算（1）與運算第三節(jié)計算機中的數(shù)據(jù)表示02數(shù)據(jù)存儲與運算（2）或運算第三節(jié)計算機中的數(shù)據(jù)表示02數(shù)據(jù)存儲與運算（3）非運算第三節(jié)計算機中的數(shù)據(jù)表示02數(shù)據(jù)存儲與運算（4）異或運算02性質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)(結合律)(分配律)(DeMorgan律)(0-1律)(交換律)(互補律)數(shù)據(jù)存儲與運算02從實際問題到邏輯函數(shù)

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

由真值表寫出邏輯函數(shù)表達式，先選定輸出結果為1的項，順序寫出輸入變量，如果對應為1則為原變量，對應為0則為反變量。再將這些項相或。

（2）根據(jù)上面的真值表寫出函數(shù)表達式數(shù)據(jù)存儲與運算03數(shù)據(jù)表示第三節(jié)計算機中的數(shù)據(jù)表示03數(shù)據(jù)表示第三節(jié)計算機中的數(shù)據(jù)表示一、數(shù)值數(shù)據(jù)的表示符號位S11101100最高位符號位，“0”表示正，“1”表示負數(shù)，其余位為數(shù)值位。-108解決符號問題：問題：數(shù)值在計算機中二進制形式存放，則正負符號、小數(shù)點如何表示？03數(shù)據(jù)表示機器數(shù)是指數(shù)在計算機中的表示形式。在計算機中只有機器數(shù)，不存在數(shù)的真值。

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

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

（11111111）2

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

（01111111）2

（10000000）2

（11111111）2

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

123（10）的原碼表示是：

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

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

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

10=(01111011)

2要得到(-123)

10,求一個二進制數(shù)c：

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

10|的二進制表示：

10000101

10000101+）01111011

00000000進位被丟棄03再行進1公里0

0

0

0

0

0

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

在計算機系統(tǒng)中，數(shù)值用補碼來表示。

03求：-5+4？

11111011+）00000100

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

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

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

2+800.111101010100×

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

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

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

2+800.111101010100×

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

2-1001

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

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

2-1001

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

-1.1101×2-1010

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

于1985建立

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

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

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

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

1代表亮、0代表不亮。

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

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

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

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

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

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

(開啟了人工智能的研究)1951年，當選英國皇家學會會員(家族中第四位皇家學會會員)1954年，逝世04圖靈機模型圖靈的貢獻

圖靈機模型：解決了可計算問題

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

可計算：不可計算：如漢諾塔問題

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

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

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

簡單！

強大！

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

①每次只能移動一個盤子；

②盤子只能在三根柱子上來回移動，不能放在他處；

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

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

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

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

【差】操作

【積】操作

【選擇】操作

【投影】操作

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

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

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

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

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

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

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

——所走路程最短

——每個城市只能訪問一次

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

——所走路程最短

——每個城市只能訪問一次

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

→

→

→

→

→

→①

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

路線總距離：1550公里

路線3：

→

→

→

→

→

→

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

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

的CompaqEV6Alpha處理器組成的110臺計算機，所有計算機花費的時間之和為22.6年。02算法實現(xiàn)TSP問題，有沒有其他求解算法呢？最優(yōu)解

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

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

Fact(5)的執(zhí)行過程【示例】求n!的算法或程序--用迭代方法構造：循環(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算法實現(xiàn)longintFact(intn){longintx; If(n>1){x=Fact(n-1);/*遞歸調用*/returnn*x;}elsereturn1;/*遞歸基礎*/}n>1返回結果1X=Fact(n-1)NY返回結果n*X開始結束傳進的參數(shù)nFact(n)

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

63

22

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

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

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

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

求下面算法時間復雜度

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

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

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

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

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

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

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

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

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

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

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

以3為基準數(shù)

21354

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

以2為基準數(shù)

12

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

只有1位，無需排序第5輪

54

以5為基準數(shù)

45

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

4

只有1位，無需排序第7輪

97108以9為基準數(shù)

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

87

8為基準數(shù)，

78

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

7

7只有1位，無需排序第10輪

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

——每次Partition都選到最大（小）的數(shù)據(jù)——退化為冒泡排序，時間復雜度為O(N2)一般情況下——平均時間復雜度為O(NlogN)——顯著快于冒泡排序所需時間快速排序的時間復雜度分析：算法分析03多核CPU、集群等：并行化（分布式、大數(shù)據(jù)、云計算、……）兩種排序算法可以并行執(zhí)行嗎？每個步驟對上一步驟存在依賴——冒泡排序算法是不能并行執(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])——兩個QuickSort子問題之間是相互獨立的，可以并行——排列順序對Partition無影響，可以并行——快速排序是可以并行執(zhí)行的算法，稱為“可并行性”可并行性是算法計算復雜度之上的另一重要考量算法分析謝謝聆聽ALGORITHMICTHINKING第5章網(wǎng)絡思維ALGORITHMICTHINKING

計算機網(wǎng)絡概述

Internet基礎02

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

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

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

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