計算機科學(xué)導(dǎo)論 課件 第2章 邏輯思維

第2章邏輯思維數(shù)據(jù)表示03數(shù)制及轉(zhuǎn)換01數(shù)據(jù)存儲與運算02本章目錄圖靈機模型0401數(shù)制及轉(zhuǎn)換

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

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

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

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

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

10100101第二節(jié)數(shù)制及轉(zhuǎn)換二進制八進制十進制十六進制數(shù)碼0,10~70~90~9，A~F基數(shù)281016位權(quán)2n8n10n16n進位原則逢2進1逢8進1逢10進1逢16進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)展開式：每位上的數(shù)碼乘以對應(yīng)位權(quán)之和305.56的按權(quán)展開式：

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進制數(shù)N展開式可表示為：第二節(jié)數(shù)制及轉(zhuǎn)換

101.01B

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

小數(shù)部分:乘基取整順排列01數(shù)制及轉(zhuǎn)換(2)十進制轉(zhuǎn)二進制/八進制/十六進制【例】將26.25D轉(zhuǎn)換為二進制數(shù)第二節(jié)數(shù)制及轉(zhuǎn)換(3)二進制與八進制、十六進制轉(zhuǎn)換01數(shù)制及轉(zhuǎn)換三位一并法（八進制），四位一并法（十六進制）二進制轉(zhuǎn)換為八/十六進制：從小數(shù)點開始分別向左（整數(shù)）和向右（小數(shù)）劃分數(shù)位，每隔3位/4位一組，最后一組若不足3位/4位則補0,再將每組二進制數(shù)轉(zhuǎn)換為八/十六進制數(shù)。八/十六進制轉(zhuǎn)換為二進制：將每1位八/十六進制數(shù)轉(zhuǎn)換為3位/4位二進制數(shù)按次序?qū)懗觥?0110101.10111100010110101.101100（265.54）8（35.BC）16第二節(jié)數(shù)制及轉(zhuǎn)換十進制、十六進制、八進制與二進制之間的對應(yīng)關(guān)系01數(shù)制及轉(zhuǎn)換第二節(jié)數(shù)制及轉(zhuǎn)換各種進制之間的轉(zhuǎn)換方法總結(jié)01數(shù)制及轉(zhuǎn)換02數(shù)據(jù)存儲與運算位（bit）比特：1或者0，是二進制信息組成、處理、存儲、傳輸?shù)淖钚?shù)據(jù)單位。字節(jié)（Byte）：1Byte=8bits，信息存儲的基本單位。字（Word）：計算機在同一時間內(nèi)處理的一組二進制數(shù)，字由若干字節(jié)構(gòu)成，字的位數(shù)稱為字長。如8bits、16bits、32bits、64bits等。字長是計算機進行數(shù)據(jù)處理和運算的單位。（1）數(shù)據(jù)存儲單位一、數(shù)據(jù)存儲02數(shù)據(jù)存儲與運算計算機存儲容量的常用表示單位第三節(jié)計算機中的數(shù)據(jù)表示（2）大端和小端存儲內(nèi)存：以字節(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ù)存儲與運算二、算術(shù)運算第三節(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性質(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律)(交換律)(互補律)數(shù)據(jù)存儲與運算02從實際問題到邏輯函數(shù)

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

由真值表寫出邏輯函數(shù)表達式，先選定輸出結(jié)果為1的項，順序?qū)懗鲚斎胱兞?，如果對?yīng)為1則為原變量，對應(yīng)為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所對應(yīng)的機器數(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？問題：若符號位參加運算，結(jié)果錯；若考慮符號位，則運算變得復(fù)雜；怎么解決？引入數(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里程表補碼表示當(dāng)字長為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當(dāng)限制了數(shù)據(jù)的表示長度時，要得到與正數(shù)對應(yīng)的負數(shù)表示，可以認為：要得到的負數(shù)加上對應(yīng)的正數(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ù)表示小結(jié)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標(biāo)準

于1985建立

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

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

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

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

1代表亮、0代表不亮。

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

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

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

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

圖像的顏色深度為8，占一個字節(jié)，灰度級別為256級。通過調(diào)整黑白兩色的程度（稱顏色灰度）來有效地顯示單色圖像；③RGB24位真彩色由紅、綠、藍三基色通過不同的強度混合而成，當(dāng)強度分成256級（值為0～255），每個像素點占3個字節(jié)24位，就構(gòu)成了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ù)運動的畫面。模擬視頻常用兩種標(biāo)準：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年開始，美國計算機學(xué)會(AssociationforComputingMachinery—ACM)每年頒發(fā)“圖靈獎”(TuringAward)給世界上最優(yōu)秀的計算機科學(xué)家1912年6月，生于倫敦，中學(xué)期間獲國王愛德華六世數(shù)學(xué)金盾獎?wù)?935年，當(dāng)選劍橋大學(xué)國王學(xué)院院士1937年，發(fā)表論文-論數(shù)字計算在決斷難題中的應(yīng)用，提出圖靈機，1938年，美國普林斯頓大學(xué)獲博士學(xué)位1938-1945年二戰(zhàn)期間，密碼破譯工作1946年，獲不列顛帝國勛章1950年，發(fā)表論文-機器能思考嗎，提出“圖靈測試”.

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

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

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

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

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

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

讀寫頭（head）。讀寫頭在紙帶上移動，對所指格子上的符號或數(shù)字進行讀取或修改?？刂瞥绦蛑噶顮顟B(tài)寄存器。記錄圖靈機的當(dāng)前狀態(tài)，并且有一種特殊狀態(tài)為停機狀態(tài)。04圖靈機模型1111111q111Rq1q1b1Rq2q211Rq2q2bbLq3q31bHq3q3b