計算思維與信息表示

1、 計算思維計算思維與計算機中的信息表示與計算機中的信息表示計算思維計算機中的信息表示 2006年3月，美國卡內(nèi)基梅隆大學(xué)計算機科學(xué)系主任周以真（Jeannette M. Wing）教授在美國計算機權(quán)威期刊Communications of the ACM雜志上給出，并定義的計算思維（Computational Thinking）。周教授認(rèn)為： 計算思維計算思維是運用計算機科學(xué)的基礎(chǔ)概念進行問題求解、系問題求解、系統(tǒng)設(shè)計統(tǒng)設(shè)計、以及人類行為理解人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動。 21世紀(jì)每個人都應(yīng)該具備的能力。計算思維計算思維計算思維是人類應(yīng)具備的第三種思維理論思維理論思維：對

2、事物的感性認(rèn)識資料，經(jīng)過抽象抽象、概括概括，形成描述事物本質(zhì)的概念，主要以推理推理和演繹演繹的方法，探尋概念之間相互聯(lián)系的一種思維活動。實驗思維實驗思維：通過觀察觀察和實驗實驗的手段，揭示自然規(guī)律法則的一種思維方法。特征是觀察、整理、歸納、對比和驗證特征是觀察、整理、歸納、對比和驗證。計算思維計算思維：構(gòu)造思維，是指從具體的算法設(shè)計設(shè)計規(guī)范入手，通過算法過程的構(gòu)造構(gòu)造與實施，來解決給定問題的一種思維方法。在當(dāng)前環(huán)境下，理論與實驗手段面臨大規(guī)模數(shù)據(jù)的情況下，不可避免的要用計算手段來輔助進行。計算機能干什么計算機能干什么 多記憶一些數(shù)據(jù)，多接收一些信息，算的快一些，交流方便些。 以億次的計算，求解

3、繁復(fù)的微分方程和方程組，描繪超乎想象的圖像，模擬無法實現(xiàn)或耗資巨大的過程等等。計算機不能干什么計算機不能干什么 不能替人拿主意、定方案 人機分界面恰在思考二字，即把計算機所不具備的直覺、綜合、機敏，甚至藝術(shù)家的靈感留給人，由人來創(chuàng)造性的開發(fā)各種所需的算法、模型、方法。計算思維的關(guān)鍵計算思維的關(guān)鍵：用計算機模擬現(xiàn)實世界計算思維的本質(zhì)計算思維的本質(zhì): 抽象和自動化 計算思維中的抽象完全超越物理的時空觀，并完全用符號來表示。自動化是機械地一步一步自動執(zhí)行，其基礎(chǔ)和前提是抽象。 案例：18世紀(jì)著名的古典數(shù)學(xué)問題哥尼斯堡七橋問題。哥尼斯堡七橋問題哥尼斯堡七橋問題哥尼斯堡地處東普魯士，位于普雷格爾河的兩岸

4、及河中心的兩個島上，城市各部分由七座橋與兩岸連結(jié)起來。多年來，當(dāng)?shù)氐木用窨傆幸粋€愿望：從家里出去散步，能否通過沒每座橋恰好一次，再返回家中？但是任何人也沒有找到這樣一條理想的路徑。1976年，瑞士數(shù)學(xué)家歐拉(Euler)解決問題的辦法是把陸地抽陸地抽象為一個點象為一個點，用連接兩個點的線段表示橋梁用連接兩個點的線段表示橋梁，將該問題抽象成點與線連接圖的數(shù)學(xué)問題。把一個實際問題抽象成合適的“數(shù)學(xué)模型”，這就是計算思維中的抽象。計算思維品質(zhì)對人的能力影響作用計算思維品質(zhì)對人的能力影響作用問題抽象層次的能力是衡量人的思維品質(zhì)的重要方面。問題抽象層次的能力是衡量人的思維品質(zhì)的重要方面。 根據(jù)求解問題的

5、需要，在分析問題的過程中，人們可以對問題進行多層次的抽象，將注意力集中在感興趣的抽象層次或關(guān)系相對密切的上下層，拋棄那些不感興趣的(不重要的)層次或細(xì)節(jié)，使問題分析相對簡單，以控制問題解決的復(fù)雜性。抽象的概念是由具體概念依其“共性”而產(chǎn)生的，把具體概念的諸多個性排出，集中描述其共性，就會產(chǎn)生一個抽象性的概念。 人的大腦思維方法和思維品質(zhì)的差異決定著： 同一問題解決辦法和處理方式各不相同。其付出的代價與取得效果甚至可能天壤之別。 計算思維的應(yīng)用領(lǐng)域計算思維的應(yīng)用領(lǐng)域 計算思維是每個人應(yīng)當(dāng)具備的基本技能，也是創(chuàng)新人才的基本要求和專業(yè)素質(zhì)，每個人都應(yīng)當(dāng)學(xué)習(xí)和應(yīng)用計算思維。正如印刷出版促進了閱讀、寫作

6、和算術(shù)的傳播一樣，計算和計算機也促進著計算思維的傳播。迄今為止，計算思維不僅滲透到每個人的生活，而且對生物信息學(xué)、生物計算、專家系統(tǒng)、經(jīng)濟學(xué)等學(xué)科領(lǐng)域產(chǎn)生了重大影響，在科技創(chuàng)新與教育教學(xué)中起著非常重要的作用。 計算思維領(lǐng)域提出的新思想、新方法不斷地促進自然科學(xué)、工程技術(shù)和社會經(jīng)濟等領(lǐng)域產(chǎn)生革命性的發(fā)展。1.2 101.2.1數(shù)制概念及數(shù)制間的轉(zhuǎn)化1.2.2計算機中數(shù)據(jù)的表示方法1.2.3 常用信息編碼1.2.4 計算機中信息單位1.數(shù)制 即計數(shù)制，用一組固定的符號和統(tǒng)一的規(guī)則來表示 數(shù)值的方法 。計算機領(lǐng)域中涉及的數(shù)制有4種：十進制、二進制二進制、八進制、十六進制。例如：36D、1010lB、

7、76O、5AH分別標(biāo)識十進制數(shù)36、二進制數(shù)1010、八進制數(shù)76、十六進制數(shù)5A。 1.2.11.2.1數(shù)制概念及數(shù)制間的轉(zhuǎn)化數(shù)制概念及數(shù)制間的轉(zhuǎn)化進制表示符號B 二進制O八進制D十進制H十六進制 在計算機內(nèi)部，數(shù)據(jù)的存儲和處理都是采用二進制數(shù)，主要原因是：（1）二進制數(shù)在物理上最容易實現(xiàn)。（2）二進制數(shù)的運算規(guī)則簡單，這將使計算機的硬件結(jié)構(gòu)大大簡化。（3）二進制數(shù)的兩個數(shù)字符號“1”和“0”正好與邏輯命題的兩個值“真”和“假”相對應(yīng)，為計算機實現(xiàn)邏輯運算提供了便利的條件。 但二進制數(shù)書寫冗長，所以為書寫方便，一般用十六進制數(shù)或八進制數(shù)作為二進制數(shù)的簡化表示。 位權(quán)例如14十六進制數(shù)1十進制

8、數(shù)轉(zhuǎn)化為二進制數(shù)、八進制數(shù)、十六進制數(shù)整數(shù)：除以基值取余法，直到商為零時為止 ，逆讀 小數(shù)：乘以基值取整法，直到積中的小數(shù)部分為零，或者達(dá)到所要求的精度為止，順讀2二進制、八進制、十六進制轉(zhuǎn)化為十進制-按權(quán)展開，相加求和按權(quán)展開，相加求和(110101)2=125+124+023+122+021+120 = 32+ 16+ 0+ 4+ 0+1 =(53)103.二進制轉(zhuǎn)化成八進制和十六進制轉(zhuǎn)化成八進制： 以小數(shù)點為中心向兩邊分組,每三位一組.整數(shù)部分不足位數(shù)左補0，小數(shù)部分不足位數(shù)右補轉(zhuǎn)化成十六進制：以小數(shù)點為中心向兩邊分組,每四位一組.整數(shù)部分不足位數(shù)左補0，小數(shù)部分不足位數(shù)右補0 4.八進

9、制和十六進制轉(zhuǎn)化成二進制八進制轉(zhuǎn)化成二進制： 一位八進制數(shù)對應(yīng)三位二進制數(shù)十六進制轉(zhuǎn)化成二進制：一位十六進制數(shù)對應(yīng)四位二進制數(shù)144(O)=001 100 100(B)64(H)=0110 0100(B) 6 4 二進制、八進制、十六進制數(shù)間的關(guān)系 八進制 對應(yīng)二進制 十六進制對應(yīng)二進制十六進制 對應(yīng)二進制0000000008100010011000191001201020010A1010301130011B1011410040100C1100510150101D1101611060110E1110711170111F11113位對應(yīng)位對應(yīng)1位位4位對應(yīng)位對應(yīng)1位位八進制八進制二進制二進制十六

10、進制十六進制1位對應(yīng)位對應(yīng)3位位1位對應(yīng)位對應(yīng)4位位二進制二進制十進制十進制八進制八進制十六進制十六進制基數(shù)乘除法按權(quán)展開求和1.2.21.2.2計算機中數(shù)據(jù)的表示方法計算機中數(shù)據(jù)的表示方法 例如，在機器中用8位二進制表示一個數(shù)90，其格式為：01011010符號位符號位 0表示正表示正在計算機中數(shù)據(jù)都是采用二進制表示，對于數(shù)的符號，也用“0”或“1”表示，“0”表示正，“1”表示負(fù)；數(shù)的最高位為符號位。 在機器內(nèi)存放的正負(fù)號符號化的數(shù)稱為機器數(shù)機器數(shù)，把機器外存放的由正負(fù)號表示的數(shù)稱作真值真值。例：-0101100 真值 -76 機器數(shù)10101100 機器數(shù)在運算時必須考慮符號位的處理。為

11、了便于運算，在機器中有三種表示數(shù)的方法： 1、原碼原碼的最高位為符號位，數(shù)值部分為原數(shù)的絕對值。 +105原=01101001 -105原=11101001 2、反碼正數(shù)的反碼與其原碼相同。而負(fù)數(shù)的反碼等于其絕對值各位求反。+105反=01101001 -105反=10010110 3、補碼正數(shù)的補碼與其原碼相同。負(fù)數(shù)的補碼是把其原碼除符號位外的各位先求其反碼，然后在最低位加1。+105補=01101001 -105補=10010111 0100000010000011定點小數(shù)：定點小數(shù)：小數(shù)點固定在數(shù)值部分最高位的左邊小數(shù)點固定在數(shù)值部分最高位的左邊定點整數(shù)：定點整數(shù)：小數(shù)點固定在數(shù)值部分最

12、低位的左邊小數(shù)點固定在數(shù)值部分最低位的左邊定定點點數(shù)數(shù)符號位符號位隱含小數(shù)位（隱含小數(shù)位（+0.5)符號位符號位隱含小數(shù)位（隱含小數(shù)位（-3)31 30 24 23 22 31 30 24 23 22 0 0浮浮點點數(shù)數(shù)階符階符 階碼階碼 數(shù)符數(shù)符 尾數(shù)尾數(shù) 階碼部分階碼部分 尾數(shù)部分尾數(shù)部分 小數(shù)點浮動-科學(xué)計數(shù)法 123.456=0.123456103浮點數(shù)分為階碼階碼( (指數(shù)指數(shù)) )和尾數(shù)尾數(shù)兩部分例：二進制數(shù)0.110111*26 在計算機中以浮點格式存放1.2.3 1.2.3 常用信息編碼常用信息編碼 ACSII碼碼(American Standard Code for Info

13、rmation Interchange) 128個常用字符，個常用字符，用用7位二進制編碼位二進制編碼，從，從0到到127 控制字符：控制字符：032，127；普通字符：；普通字符：94個。個。 例如：例如：“a”字符的編碼為字符的編碼為1100001，對應(yīng)的十進制數(shù)是，對應(yīng)的十進制數(shù)是97； 換行換行 0AH 10 回車回車 0DH 13 空格空格 20H 32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 97122漢字編碼漢字編碼 輸入碼 國標(biāo)碼 字形碼 機內(nèi)碼 地址碼 漢字輸出 漢字輸入 (1) 漢字輸入碼 音碼類 全拼、雙拼、微軟拼音、智能ABC等

14、形碼類 五筆字型法、鄭碼輸入法等 。(2) 漢字國標(biāo)碼(GB231280)：每個漢字占兩個字節(jié)。 一級漢字：3755個；二級漢字：3008個。 漢字分區(qū)，每個區(qū)94個漢字。(3)機內(nèi)碼漢字在設(shè)備或信息處理系統(tǒng)內(nèi)部最基本的表達(dá)形式。漢字 國標(biāo)碼 漢字內(nèi)碼中 8680(01010110 01010000)B (11010110 11010000)B 華 5942(00111011 00101010)B (10111011 10101010)B 漢字漢字（4）字形碼點陣：漢字字形點陣的代碼 矢量：存儲的是描述漢字字形的輪廓特征 1.1.2 2.4 .4 計算機中信息單位計算機中信息單位位（Bit）：

15、二進制數(shù)的最小單位，通常用“b”表示。字節(jié)（Byte）：以8位二進制數(shù)組成1個字節(jié)，通常用“B”表示。最常用的基本單位K 字節(jié)1K = 1024 byteM（兆）字節(jié) 1M = 1024 KG（吉） 字節(jié) 1G = 1024 M T（太）字節(jié)1T = 1024 G字（ word ）：由若干個字節(jié)組成，通常我們把計算機一次所能處理的數(shù)據(jù)的最大位數(shù)稱為該機器的字長。 著名計算機科學(xué)家沃思(Nikiklaus Wirth)提出一個公式： 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序數(shù)據(jù)結(jié)構(gòu):對數(shù)據(jù)的描述。在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式算法:對操作的描述。即要求計算機進行操作的步驟1.3

16、 一個程序除了算法和數(shù)據(jù)結(jié)構(gòu)這主要要素外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計方法進行程序設(shè)計，并且用某一種計算機語言表示 算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計方法和語言工具是一個程序設(shè)計人員應(yīng)具備的知識 廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法” 計算機算法可分為兩大類別：數(shù)值運算算法：求數(shù)值解非數(shù)值運算算法：事務(wù)管理領(lǐng)域例：圖書檢索，人事管理等例： 求12345 可以用最原始的方法進行：步驟1：先求1*2，得到結(jié)果2。步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這就是最后的結(jié)果。例：例： 求求12345 1000太繁瑣太繁瑣 改

17、進的算法：設(shè)變量t為被乘數(shù)變量i為乘數(shù)用循環(huán)算法求結(jié)果 S1：使t=1，或?qū)懗?=t S2：使i=2，或?qū)懗? = i S3：使t與i相乘，乘積仍放在變量t中，可表示為：t*i =t S4：使i的值加1，即i+1 = i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結(jié)束 最后得到t的值就是 5!的值若是若是1000？ S1：使t=1，或?qū)懗?=t S2：使i=2，或?qū)懗? = i S3：使t與i相乘，乘積仍放在變量t中，可表示為：t*i = t S4：使i的值加1，即i+1 = i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結(jié)束 最后得到t的值就是 5!的值若求若求1357911

18、33221111相當(dāng)于相當(dāng)于i 11 一個有效算法應(yīng)該具有以下特點：(1) 有窮性。一個算法應(yīng)包含有限的操作步驟，而不能是無限的。(2) 確定性。算法中的每一個步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。 一個有效算法應(yīng)該具有以下特點：(3) 有零個或多個輸入。所謂輸入是指在執(zhí)行算法時需要從外界取得必要的信息。(4) 有一個或多個輸出。算法的目的是為了求解，“解” 就是輸出。沒有輸出的算法是沒有意義的。(5) 有效性。算法中的每一個步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。 常用的方法有：自然語言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖偽代碼 用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)歧義性 用自然語言

19、描述包含分支和循環(huán)的算法，不很方便 除了很簡單的問題外，一般不用自然語言 流程圖是用一些圖框來表示各種操作 用圖形表示算法，直觀形象，易于理解起止框起止框輸入輸出框輸入輸出框處理框處理框判斷框判斷框流程線流程線連接點連接點x0YN一個入口一個入口兩個出口兩個出口 流程圖是用一些圖框來表示各種操作 用圖形表示算法，直觀形象，易于理解起止框起止框輸入輸出框輸入輸出框判斷框判斷框流程線流程線連接點連接點位置不夠位置不夠 例：求5！的算法用流程圖表示。 求123451 = t輸出輸出ti5開始開始2 = it*i = ti+1 = i結(jié)束結(jié)束NY1.傳統(tǒng)流程圖的弊端 傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴(yán)格限制 使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使人難以理解算法的邏輯2.三種基本結(jié)構(gòu)(1) 順序結(jié)構(gòu)AB2.三種基本結(jié)構(gòu)(2) 選擇結(jié)構(gòu)ABYpNAYpN2.三種基本結(jié)構(gòu)(3)