節(jié)計算學科中核心概念

第4章

計算學科中的核心概念

認知學科終究是通過概念來實現(xiàn)的，掌握和應用學科中的核心概念是成熟的計算機科學家和工程師的標志之一。本章首先介紹計算學科中一個最具方法論性質(zhì)的核心概念——算法，包括算法的歷史、定義、表示方法，以及算法的分析等內(nèi)容。然后，介紹數(shù)據(jù)結(jié)構(gòu)、程序、軟件、硬件，以及計算機中的數(shù)據(jù)（含進位制數(shù)及其相互轉(zhuǎn)換，原碼、反碼和補碼及其轉(zhuǎn)換，字符、字符串和漢字，圖像數(shù)據(jù)的表示，聲音數(shù)據(jù)的表示）等內(nèi)容。最后，給出CC1991提取的12個核心概念，即綁定、大問題的復雜性、概念模型和形式模型、一致性和完備性、效率、演化、抽象層次、按空間排序、按時間排序、重用、安全性、折衷與結(jié)論。4.1引言

學科中的核心概念是學科中最關(guān)鍵、最重要的概念，它涉及學科研究的內(nèi)涵、對象、本質(zhì)、核心要素等內(nèi)容，其基本特征有以下4點：（1）在學科中多處出現(xiàn)；（2）在各分支領域及抽象、理論和設計的各個層面上都有很多示例；（3）在技術(shù)上有高度的獨立性；（4）一般都在數(shù)學、科學和工程中出現(xiàn)。在計算學科的一般文獻中，學科中的核心概念指的是CC1991報告提取的學科中反復出現(xiàn)的12個核心概念。為便于教學，本書將學科中最具方法論性質(zhì)的概念——算法，以及數(shù)據(jù)結(jié)構(gòu)、程序、軟件、硬件、計算機中的數(shù)據(jù)等與CC1991報告提取的12個核心概念一起統(tǒng)稱為學科中的核心概念。4.2算法

算法是計算學科中最具方法論性質(zhì)的核心概念，也被譽為計算學科的靈魂。算法設計的優(yōu)劣決定著軟件系統(tǒng)的性能，對算法進行研究能使我們深刻地理解問題的本質(zhì)以及可能的求解技術(shù)4.2.1算法的歷史簡介

公元825年，阿拉伯數(shù)學家阿科瓦里茨米（AlKhowarizmi）撰寫了著名的《波斯教科書》（PersianTextbook），書中概括了進行四則算術(shù)運算的法則?！八惴ǎˋlgorithm）”一詞就來源于這位數(shù)學家的名字。后來，《韋氏新世界詞典》（WebstersNewWorldDictionary）將其定義為“解某種問題的任何專門的方法”。而據(jù)考古學家發(fā)現(xiàn)，古巴比倫人在求解代數(shù)方程時，就已經(jīng)采用了“算法”的思想。在算法的研究中，人們不可避免的要提到丟番圖方程，希爾伯特著名的23個數(shù)學問題中的第十個問題就是關(guān)于“丟番圖方程的可解性問題”。古希臘數(shù)學家丟番圖（Diophantus）對代數(shù)學的發(fā)展有極其重要的貢獻，并被后人稱之為“代數(shù)學之父”。 他在《算術(shù)》（Arithmetica）一書中提出了有關(guān)兩個或多個變量整數(shù)系數(shù)方程的有理數(shù)解問題。對于具有整數(shù)系數(shù)的不定方程，若只考慮其整數(shù)解，這類方程就叫丟番圖方程?！皝G番圖方程可解性問題”的實質(zhì)為：能否寫出一個可以判定任意丟番圖方程是否可解的算法？本書僅討論線性丟番圖方程，至于非線性丟番圖方程，本書不再討論。對于只有一個未知數(shù)的線性丟番圖方程而言，求解很簡單，如ax=b，只要a能整除b，就可判定其有整數(shù)解，該整數(shù)解即b/a。對于有兩個未知數(shù)的線性丟番圖方程判定其是否有解的方法也很簡單，如ax+by=c，先求出a和b的最大公因子d，若d能整除c，則該方程有（整數(shù)解）。

例4.1問：方程13x+26y=52有無整數(shù)解？ 答：13和26的最大公因子是13，13又可整除52，故該方程有整數(shù)解（如x=2，y=1即方程的解）。 例4.2問：方程2x+4y=15有無整數(shù)解？ 答：2和4的最大公因子是2，2不能整除15，故該方程無整數(shù)解。 因此可以看出，對于兩個未知數(shù)的線性丟番圖方程來說，求解的關(guān)鍵就是求最大公因子。公元前300年左右，歐幾里德在其著作《幾何原本》（Elements）第七卷中闡述了關(guān)于求解兩個數(shù)最大公因子的過程，這就是著名的歐幾里德算法：給定兩個正整數(shù)m和n，求它們的最大公因子，即能同時整除m和n的最大正整數(shù)。

算法如下：（1）以n除m，并令所得余數(shù)為r（r必小于n）；（2）若r=0，算法結(jié)束，輸出結(jié)果n；否則，繼續(xù)步驟（3）；（3）將n置換為m，r置換為n，并返回步驟（1）繼續(xù)進行。例4.3設m=56，n=32，求m、n的最大公因子。算法的執(zhí)行過程如下：（1）32除56余數(shù)為24；（2）24除32余數(shù)為8；（3）8除24余數(shù)為0，算法結(jié)束，輸出結(jié)果8。答：m、n的最大公因子為8。 歐幾里德算法既表述了一個數(shù)的求解過程，同時，它又表述了一個判定過程，該過程可以判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公因子）這個命題的真假。4.2.2算法的定義和特征

有關(guān)算法的定義不少，其內(nèi)涵基本上是一致的，其中最為著名的是計算機科學家克努特在其經(jīng)典巨著—《計算機程序設計的藝術(shù)》（TheArtofComputerProgramming）第一卷中對算法的定義和特性所作的有關(guān)描述。 1．算法的非形式化定義 一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型問題的運算序列。 2．算法的重要特性 （1）有窮性：一個算法在執(zhí)行有窮步之后必須結(jié)束。也就是說，一個算法，它所包含的計算步驟是有限的。如在歐幾里德算法中，由于m和n均為正整數(shù)，在步驟（1）之后，r必小于n，若r≠0，下一次進行步驟（1）時，n的值已經(jīng)減小，而正整數(shù)的遞降序列最后必然要終止。因此，無論給定m和n的原始值有多大，步驟（1）的執(zhí)行都是有窮次。

（2）確定性：算法的每一個步驟必須要確切地定義。即算法中所有有待執(zhí)行的動作必須嚴格而不含混地進行規(guī)定，不能有歧義性。如歐幾里德算法中，步驟（1）中明確規(guī)定“以n除m”，而不能有類似“以n除m或以m除n”這類有兩種可能做法的規(guī)定。 （3）輸入：算法有零個或多個的輸入，即在算法開始之前，對算法最初給出的量。如歐幾里德算法中，有兩個輸入，即m和n。 （4）輸出：算法有一個或多個的輸出，即與輸入有某個特定關(guān)系的量，簡單地說就是算法的最終結(jié)果。如在歐幾里德算法中只有一個輸出，即步驟（2）中的n。

（5）能行性：算法中有待執(zhí)行的運算和操作必須是相當基本的，換言之，它們都是能夠精確地進行的，算法執(zhí)行者甚至不需要掌握算法的含義即可根據(jù)該算法的每一步驟要求進行操作，并最終得出正確的結(jié)果。

3．算法的形式化定義 算法的形式化定義：算法是一個四元組，即（Q，I，Ω，F(xiàn)）。 其中： （1）Q是一個包含子集I和Ω的集合，它表示計算的狀態(tài)； （2）I表示計算的輸入集合； （3）Ω表示計算的輸出集合； （4）F表示計算的規(guī)則，它是一個由Q到它自身的函數(shù)，且具有自反性，即對于任何一個元素q∈Q，有F(q)=q。 一個算法是對于所有的輸入元素x，都在有窮步驟內(nèi)終止的一個計算方法。在算法的形式化定義中，對于任何一個元素x∈I，x均滿足以下性質(zhì)：x0=x，xk+1=F(xk)，(k≥0) 該性質(zhì)表示任何一個輸入元素x均為一個計算序列，即x0，x1，x2，…，xk。對任何輸入元素x，該序列表示算法在第k步結(jié)束。4.2.3算法實例 下面，再介紹幾個簡單的算法實例，以加深讀者對算法思想的理解。 例4.4求1+2+3+…+100 設變量X表示加數(shù)，Y表示被加數(shù)，用自然語言將算法描述如下： （1）將1賦值給X； （2）將2賦值給Y； （3）將X與Y相加，結(jié)果存放在X中； （4）將Y加1，結(jié)果存放在Y中； （5）若Y小于或等于100，轉(zhuǎn)到步驟（3）繼續(xù)執(zhí)行；否則，算法結(jié)束，結(jié)果為X。 例4.5求解調(diào)和級數(shù)Hn。

Hn=1/1+1/2+1/3+…+1/n

…調(diào)和級數(shù)在算法分析中有重要作用。直覺上，當n很大時，Hn也未必會得到很大的值。其實不然，只要n充分大，則Hn就能得到我們所需要的不論多大的數(shù)。這個例子與梵天塔問題一樣清晰地表明：在算法的研究中，不能依靠人的直覺，而只能依靠嚴密的數(shù)學方法。 下面，給出求解調(diào)和級數(shù)的算法。 設變量X表示累加和，變量I表示循環(huán)的次數(shù)，自然語言描述算法如下： （1）將0賦值給X； （2）將1賦值給I； （3）將X與1/I相加，然后把結(jié)果存入X； （4）將I加1；（5）若I大于等于N，算法結(jié)束，結(jié)果為X；否則轉(zhuǎn)到步驟（3）繼續(xù)執(zhí)行。

例4.6求解斐波那契數(shù)。 0，1，1，2，3，5，8，13，21，34，…（1） 數(shù)列（1）即著名的斐波那契數(shù)列，它來源于1202年意大利數(shù)學家斐波那契（L.P.Fibonacci）在其《珠算之書》（LiberAbaci）中提出的一個“兔子問題”： 假設一對剛出生的兔子一個月后就能長大，再過一個月就能生下一對兔子，并且此后每個月都能生一對兔子，且新生的兔子在第二個月后也是每個月生一對兔子。問：一對兔子一年內(nèi)可繁殖成多少對兔子？ 在序列（1）中，每個數(shù)都是它的前兩個數(shù)之和，F(xiàn)n表示這個序列的第個數(shù)，該序列可以形式化的定義為： F0=0，F(xiàn)1=1，F(xiàn)n+2=Fn+1+Fn，n≥0 斐波那契數(shù)列不僅包含著一個有趣的“兔子問題”，而且還是一個關(guān)于加法算法的典型實例。下面，給出求解前個斐波那契數(shù)的算法。 設變量X表示前一個數(shù)的值，即定義中的Fn，變量Y表示當前數(shù)的值，即定義中的Fn+1，變量Z表示后一個數(shù)的值，即定義中的Fn+2。那么求解問題的自然語言描述如下：（1）如果n=0，那么將0賦值給Y，并輸出Y，轉(zhuǎn)步驟（11）繼續(xù)執(zhí)行；（2）將0賦給X，將1賦值給Y；（3）輸出X、Y；（4）將1賦值給I；（5）如果I大于-1，則轉(zhuǎn)到步驟（11），否則繼續(xù)執(zhí)行；（6）將X和Y的和賦值給Z；（7）將Y賦值給X；（8）將Z賦值給Y；（9）將Y輸出；（10）將I加1，轉(zhuǎn)步驟（5）繼續(xù)執(zhí)行；（11）算法結(jié)束。4.2.4算法的表示方法

算法是對解題過程的精確描述，這種描述是建立在語言基礎之上的，表示算法的語言主要有自然語言、流程圖、偽代碼、計算機程序設計語言等。1．自然語言前面關(guān)于歐幾里德算法以及算法實例的描述使用的都是自然語言，自然語言是人們?nèi)粘Ｋ玫恼Z言，如漢語、英語、德語等。使用這些語言不用專門訓練，所描述的算法也通俗易懂。然而，其缺點也是明顯的：（1）由于自然語言的歧義性，容易導致算法執(zhí)行的不確定性；（2）自然語言的語句一般太長，從而導致了用自然語言描述的算法太長；（3）由于自然語言表示的串行性，因此，當一個算法中循環(huán)和分支較多時就很難清晰地表示出來；（4）自然語言表示的算法不便翻譯成計算機程序設計語言理解的語言。

2．流程圖流程圖是描述算法的常用工具，它采用美國國家標準化協(xié)會ANSI（AmericanNationalStandardInstitute）規(guī)定的一組圖形符號來表示算法。流程圖可以很方便地表示順序、選擇和循環(huán)結(jié)構(gòu)，而任何程序的邏輯結(jié)構(gòu)都可以用順序、選擇和循環(huán)結(jié)構(gòu)來表示，因此，流程圖可以表示任何程序的邏輯結(jié)構(gòu)。另外，用流程圖表示的算法不依賴于任何具體的計算機和計算機程序設計語言，從而有利于不同環(huán)境的程序設計。就算法的描述而言，流程圖優(yōu)于其他描述算法的語言。下面，分別給出求解例4.4、例4.5和例4.6的流程圖算法描述。圖4.1例4.4算法流程圖（2）求解例4.4的算法流程圖，如圖4.1所示。（2）求解例4.5的算法流程圖，如圖4.2所示。圖4.2例4.5算法流程圖（3）求解例4.6的算法流程圖，如圖4.3所示。圖4.3例4.6算法流程圖

3．偽代碼 偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法的工具。它不用圖形符號，因此，寫方便，格式緊湊，易于理解，便于向計算機程序設計語言算法（程序）過渡。下面，分別給出求解例4.4、例4.5和例4.6的偽代碼算法描述。 （1）求解例4.4的偽代碼算法描述： BEGIN(算法開始) 1=>X 2=>Y while（Y<=100） { X+Y=>X Y+1=>Y}{ X+1/I=>X I+1=>I }while(I>=n) END（算法結(jié)束）（3）例4.6的偽代碼算法描述： BEGIN（算法開始） ifn==0 { 0=>Y PrintY } else{ 0=>X 1=>Y PrintX，Y for(i=1;i<=n-1;i++) { X+Y=>Z Y=>X Z=>Y PrintY } }END（算法結(jié)束）4．計算機程序設計語言 計算機不能識別自然語言、流程圖和偽代碼等算法描述的語言。因此，用自然語言、流程圖和偽代碼等語言描述的算法最終還必須轉(zhuǎn)換為具體的計算機程序設計語言描述的算法，即轉(zhuǎn)換為具體的程序。一般而言，計算機程序設計語言描述的算法（程序）是清晰的、簡明的，最終也能由計算機處理的。然而，就使用計算機程序設計語言描述算法而言，它還存在以下幾個缺點：（1）算法的基本邏輯流程難于遵循。與自然語言一樣，程序設計語言也是基于串行的，當算法的邏輯流程較為復雜時，這個問題就變得更加嚴重；（2）用特定程序設計語言編寫的算法限制了與他人的交流，不利于問題的解決；

（3）要花費大量的時間去熟悉和掌握某種特定的程序設計語言；（4）要求描述計算步驟的細節(jié)，而忽視算法的本質(zhì)。下面，分別給出求解例4.4、例4.5和例4.6的計算機程序設計語言（C語言）的算法描述。（1）求解例4.4的計算機程序設計語言（C語言）的算法描述：main(){intX,Y;X=1;Y=2;while<=100){X=X+Y;Y=Y+1;};printf("%d",X);}（2）求解例4.5的計算機程序設計語言（C語言）的算法描述：main(){intn;floatX,I;printf("Pleaseinputn:");scanf("%d",&n);X=0;I=1;do{X=X+1/I;I=I+1;}while(I<=n);printf("\n%f",X);}（3）求解例4.6的計算機程序設計語言（C語言）的算法描述：main(){intX,Y,Z,I,j,n;printf("pleaseinputn:");scanf("%d",&n);printf("\n");if(n==0){Y=0;printf("%d",Y);}

else{X=0;Y=1;printf("%d%d",X,Y);for(I=1;I<=n-1;I++){ Z=X+Y; X=Y; Y=Z; printf("%d",Y);}}}4.2.5算法分析

解一個問題，往往有若干不同的算法，這些算法決定著根據(jù)該算法編寫的程序性能的好壞。那么，在保證算法正確性的前提下，如何確定算法的優(yōu)劣就是一個值得研究的課題。在算法的分析中，一般應考慮以下3個問題：（1）算法的時間復雜度；（2）算法的空間復雜度；（3）算法是否便于閱讀、修改和測試。算法時間復雜度是指算法中有關(guān)操作次數(shù)的多少，它用T(n)表示，T為英文單詞Time的第一個字母，T(n)中的n表示問題規(guī)模的大小。如在累加求和中，n表示待加數(shù)的個數(shù)；在矩陣相加問題中，n表示矩陣的階數(shù)；在圖中，n表示頂點數(shù)等。

在算法的復雜度分析中，經(jīng)常使用一個記號（讀作“大”），該記號是保羅·巴克曼（P.Bachmann）于1892年在《解析數(shù)論》（AnalytischeZahlentheorie）一書引進的，它為Order（數(shù)量級）的第一個字母，它允許使用“=”代替“≈”。如n2+n+1=(n2)，該表達式表示，當n足夠大時表達式左邊約等于n2。設f(n)是一個關(guān)于正整數(shù)n的函數(shù)，若存在一個正整數(shù)n0和一個常數(shù)C，當n≥n0時，∣T(n)∣≤∣Cf(n)∣均成立，則稱f(n)為T(n)的同數(shù)量級的函數(shù)。于是，算法時間復雜度T(n)可表示為：

T(n)=

(f(n))

常見的大表示形式有：(1)稱為常數(shù)級；(logn)稱為對數(shù)級；(n)稱為線性級；(nc)稱為多項式級；(cn)稱為指數(shù)級；(n!)稱為階乘級。 用以上表示方法，在第2章的梵天塔問題中，需要移動的盤子次數(shù)為h(n)=2n-1，則該問題的算法時間復雜度表示為(2n)；例4.4的算法時間復雜度表示為(1)；例4.5的算法時間復雜度表示為(n)；例4.6的算法時間復雜度表示為(n)等等。 一般而言，對于較復雜的算法，應將它分成容易估算的幾個部分，然后用的求解原則計算整個算法的時間復雜度，最好不要采用指數(shù)級和階乘級的算法，而應盡可能選用多項式級或線性級等時間復雜度較小的算法。另外，還要在算法最好、平均和最壞的情況下區(qū)別執(zhí)行效率的不同。

在階乘級的算法中，如果問題規(guī)模n為10，則算法時間復雜度為10！（3628800）。若要檢驗10！種情況，設每種情況需要1毫秒的計算時間，則整個計算將需1小時左右。一般來說，如果選用了階乘級的算法，則當問題規(guī)模等于或者大于10時，就要認真考慮算法的適用性問題。 算法的空間復雜度是指算法在執(zhí)行過程中所占存儲空間的大小，它用S(n)表示，S為英文單詞Space的第一個字母。與算法的時間復雜度相同，算法的空間復雜度S(n)也可表示為：S(n)=

(g(n))。4.3數(shù)據(jù)結(jié)構(gòu)

數(shù)學模型有定量模型和定性模型兩類之分。定量模型指的是可以用數(shù)值方程表示的一類模型，而定性模型則是指非數(shù)值性的數(shù)據(jù)結(jié)構(gòu)（如表、樹和圖等）及其運算。 在計算領域中，數(shù)據(jù)結(jié)構(gòu)（DataStructure）指的是一類定性數(shù)學模型，它是計算機算法設計的基礎，它在計算科學中占有十分重要的地位。本節(jié)將介紹數(shù)據(jù)結(jié)構(gòu)的基本概念和常用的幾種數(shù)據(jù)結(jié)構(gòu)，如線性表、數(shù)組、樹和二叉樹以及圖等。4.3.1數(shù)據(jù)結(jié)構(gòu)的基本概念1．數(shù)據(jù)結(jié)構(gòu)的組成數(shù)據(jù)結(jié)構(gòu)是一類定性的數(shù)學模型，它由數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)（或稱物理結(jié)構(gòu)）及其運算3部分組成。2．數(shù)據(jù)邏輯結(jié)構(gòu)的形式化定義DS=<D，R>其中：D表示數(shù)據(jù)的集合；R表示數(shù)據(jù)D上關(guān)系的集合。3．數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是指在反映數(shù)據(jù)邏輯關(guān)系的原則下，數(shù)據(jù)在存儲器中的存儲方式。數(shù)據(jù)存儲結(jié)構(gòu)的基本組織方式有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。（1）順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素的邏輯關(guān)系。（2）鏈式存儲結(jié)構(gòu)：借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常在數(shù)據(jù)元素上增加一個或多個指針類型的屬性來實現(xiàn)這種表示方式。4．數(shù)據(jù)結(jié)構(gòu)的基本運算內(nèi)容（1）建立數(shù)據(jù)結(jié)構(gòu)；（2）清除數(shù)據(jù)結(jié)構(gòu)；（3）插入數(shù)據(jù)元素；（4）刪除數(shù)據(jù)元素；（5）更新數(shù)據(jù)元素；（6）查找數(shù)據(jù)元素；（7）按序重新排列；（8）判定某個數(shù)據(jù)結(jié)構(gòu)是否為空，或是否已達到最大允許的容量；（9）統(tǒng)計數(shù)據(jù)元素的個數(shù)。4.3.2常用的幾種數(shù)據(jù)結(jié)構(gòu)

1．線性表 線性表是n個數(shù)據(jù)元素的有限序列，即（X[1]，X[2]，X[3]，…，X[i]，…，X[n]）。插入、刪除和存取數(shù)據(jù)元素是所有數(shù)據(jù)結(jié)構(gòu)的基本操作，若對線性表的這些基本操作加一定的限制，則形成下面幾種特殊的線性表： （1）后進先出（LastInFirstOut，簡稱LIFO）的線性表。它的所有插入、刪除和存取都是在線性表的表尾進行的； （2）先進先出（FirstInFirstOut，簡稱FIFO）的線性表。它的所有插入都是在線性表的一端進行的，而所有的刪除和存取又都在線性表的另一端進行； （3）限定所有插入、刪除和存取都在表的兩端進行的線性表。 2．數(shù)組 數(shù)組是線性表的推廣形式之一。如在一個mn的二維數(shù)組中，每個元素A[i,j]都分別屬于兩個線性表，即（A[i,1]，A[i,2]，…，A[i,n]）和（A[1,j]，A[2,j]，…，A[m,j]）。3．樹和二叉樹樹和二叉樹是一種具有層次關(guān)系的非線性結(jié)構(gòu)，在計算機領域中有廣泛的應用，尤其以二叉樹最為常用。（1）樹樹（Tree）是由n（n≥0）個結(jié)點組成的有限集合。若n=0，則稱為空樹，任何一個非空樹均滿足以下兩個條件：①僅有一個稱為根的結(jié)點；②當n>0時，其余結(jié)點可分為m（m≥0）個互不相交的有限集合，其中每個集合又是一棵樹，并稱為根的子樹。例如，圖4.4所示的樹中有12個結(jié)點，A是根結(jié)點，該樹又可再分為若干不相交的子樹，如T1={B，E，F(xiàn)，K}，T2={C，G}，T3={D，H，I，J，L}等。圖4.4樹（2）二叉樹 二叉樹是n（n≥0）個結(jié)點組成的有限集合，它或者是空集（n0），或者由一個結(jié)點及兩棵互不相交的子樹組成，且這兩個子樹有左、右之分，其次序不能任意顛倒。

4．圖 圖是由結(jié)點和連接這些結(jié)點的邊所組成的集合。在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。 圖的形式化定義為：G=<V，E> 其中： V是一個非空結(jié)點的集合； E是連結(jié)結(jié)點的邊的集合。 例G=<V，E> 其中V={A，B，C，D}，E={(A,B)，(A，C)，(B，D)，(B，C)，(D，C)，(A，D)}。 該圖也可以用圖4.5來表示。圖4.5圖的表示4.4程序

“程序”一詞，從廣義上講可以認為是一種行動方案或工作步驟。在日常生活中，我們經(jīng)常會碰到這樣的程序：某個會議的日程安排、一條旅游路線的設計、手工小制作的說明書等，這些程序表示的都是我們在做一件事務時按時間的順序應先做什么后做什么。本書所指的程序特指計算機的程序，也是一種處理事務的時間順序和處理步驟。由于組成計算機程序的基本單位是指令，因此，計算機程序就是按照工作步驟事先編排好的、具有特殊功能的指令序列。一個程序具有一個單一的、不可分的結(jié)構(gòu)，它規(guī)定了某個數(shù)據(jù)結(jié)構(gòu)上的一個算法。瑞士著名計算機科學家尼可萊·沃思（NikiklausWirth）在1976年曾提出這樣一個公式： 算法+數(shù)據(jù)結(jié)構(gòu)=程序

由此看來，我們前面提到的算法和數(shù)據(jù)結(jié)構(gòu)是計算機程序的兩個最基本的概念。算法是程序的核心，它在程序編制、軟件開發(fā)，乃至在整個計算機科學中都占據(jù)重要地位。數(shù)據(jù)結(jié)構(gòu)是加工的對象，一個程序要進行計算或處理總是以某些數(shù)據(jù)為對象的，而要設計一個好的程序就需將這些松散的數(shù)據(jù)按某種要求組成一種數(shù)據(jù)結(jié)構(gòu)。然而，隨著計算機科學的發(fā)展，人們現(xiàn)在已經(jīng)意識到程序除了以上兩個主要要素外，還應包括程序的設計方法以及相應的語言工具和計算環(huán)境等內(nèi)容。4.5軟件

軟件是與程序密切相關(guān)的一個概念，在計算機發(fā)展的初期，硬件設計和生產(chǎn)是主要問題，那時的軟件就是程序。后來，隨著計算技術(shù)的發(fā)展，傳統(tǒng)軟件的生產(chǎn)方式已不適應發(fā)展的需要，于是人們將工程學的基本原理和方法引入軟件設計和生產(chǎn)中。現(xiàn)在計算機軟件一般指計算機系統(tǒng)中的程序及其文檔，也可以指在研究、開發(fā)、維護，以及使用上述含義下的軟件所涉及的理論、方法、技術(shù)所構(gòu)成的分支學科。軟件一般分為系統(tǒng)軟件、支撐軟件、應用軟件3類。 （1）系統(tǒng)軟件是計算機系統(tǒng)中最靠近硬件層次的軟件。如操作系統(tǒng)、編譯程序等。 （2）支撐軟件是支撐其他軟件的開發(fā)與維護的軟件。如數(shù)據(jù)庫管理系統(tǒng)、網(wǎng)絡軟件、各種接口軟件和開發(fā)工具等。 （3）應用軟件是特定應用領域的專用軟件。如商業(yè)會計軟件、教學軟件等。4.6硬件

計算機硬件是構(gòu)成計算機系統(tǒng)的所有物理器件、部件、設備，以及相應的工作原理與設計、制造、檢測等技術(shù)的總稱。廣義的硬件包含硬件本身及其工程技術(shù)兩部分。其中： 計算機系統(tǒng)的物理元器件包括：集成電路、印制電路板，以及其他磁性元件、電子元件等。 計算機系統(tǒng)的部件和設備包括：控制器、運算器、存儲器、輸入輸出設備、電源等。 硬件工程技術(shù)包括：印制電路板制造、高密度組裝、抗環(huán)境干擾、抗惡劣環(huán)境破壞等技術(shù)，以及在設計和制造過程中為提高計算機性能所采取的措施等。 計算機就是由計算機硬件和計算機軟件組成的。硬件是計算機的“軀體”，軟件是計算機的“靈魂”。4.7數(shù)據(jù)存儲和表示

計算機用位的形式來表示數(shù)據(jù)。位（binarydigit，二進制數(shù)字，縮寫為bit）是存儲在計算機中的最小數(shù)據(jù)單位，位表示二進制數(shù)字的0或1，8位表示1個字節(jié)（byte）。存儲一個位需要用一個有兩種狀態(tài)的設備。例如，電子開關(guān)就能表示并存儲位，通常用“開”（合上）狀態(tài)表示“1”，用“關(guān)”（斷開）表示“0”?，F(xiàn)代計算機使用各種各祥的兩態(tài)設備來存儲數(shù)據(jù)。在計算機中，數(shù)據(jù)和指令都是用二進制代碼來表示的。二進制數(shù)的每一位只能是數(shù)字0或1，它只有形式的意義，對于不同的應用，可以附給它不同的含義。因此，可以用它來表示數(shù)值、字符、圖像甚至聲音，對這些數(shù)據(jù)，需要進行相應的編碼。在需要呈現(xiàn)給用戶時，再對它們進行解碼。下面分別介紹進位制數(shù)及其相互轉(zhuǎn)換，原碼、反碼和補碼及其轉(zhuǎn)換，以及字符、字符串和漢字，圖像和聲音等數(shù)據(jù)的表示。4.7.1進位制數(shù)及其相互轉(zhuǎn)換

在計算機中，只能存二進制數(shù)，因此，要保存一個十進制（Decimal）的數(shù)，也就是要保存一個對應的二進制數(shù)。由于計算機很難確定在內(nèi)存中一個值的結(jié)束位置和另一個值的起始位置，因此，大多數(shù)計算機和程序都采用固定的寬度來避免這個問題，即每一個數(shù)都用相同的位數(shù)來表示。常用的有16位、32位和64位。 在一個16位的計算機中，若一個十進制數(shù)轉(zhuǎn)換為二進制數(shù)后，不夠16位，則在這個二進制數(shù)前加0，直到滿16位為止。比如，十進制數(shù)2，其二進制數(shù)為10，在10前加14個0，即為：0000000000000010。 在實際的程序中，由于二進制數(shù)不直觀。因此，在程序的輸入和輸出中，一般仍采用十進制數(shù)，而在分析計算機內(nèi)部工作時，常用十六進制（Hexadecimal）數(shù)，這樣，就要進行相應的轉(zhuǎn)換。下面，分別介紹十進制與二進制，以及二進制與八進制（Octal），二進制與十六進制等幾種常用的進位制數(shù)的表示及其相互轉(zhuǎn)換。

1.十進制數(shù)與二進制數(shù)之間的轉(zhuǎn)換 我們知道在表示十進制數(shù)的時候，從右邊起的第1個數(shù)字是1（100=1），第2個數(shù)字是10（101=10），第3個數(shù)字是100（102=100），第4個數(shù)字是1000（103=1000），以此類推。如果我們要把十進制整數(shù)3254展開，我們很容易知道存在如下的關(guān)系，3254=3*103+2*102+5*101+4*100

。 這樣的關(guān)系同樣存在二進制數(shù)中，只是這里的基數(shù)不是10，而變成了2。這時，從右邊起的第1個數(shù)字就是1（20=1），第2個數(shù)字就是2（21=2），第3個數(shù)字是4（22=4），第4個數(shù)字就是8（23=8）了。從這一點出發(fā)，我們很容易找到十進制和二進制轉(zhuǎn)換的方法。 （1）十進制數(shù)轉(zhuǎn)換為二進制數(shù)

若R表示十進制整數(shù)，Kn-1

，Kn-2

，Kn-3…K1

，K0

表示二進制數(shù)的各位數(shù)，最低（右）端一位為K0，最高（左）端一位為Kn-1。為了區(qū)分十進制數(shù)和二進制數(shù)，我們分別給十進制數(shù)和二進制數(shù)加上下標10和2，即有如下形式 （R)10=（Kn-1Kn-2Kn-3…K1K0)２① 與上文提到的十進制的展開類似，我們可以將上式寫為 （Kn-1Kn-2Kn-3…K1K0)２

=Kn-1*2n-1+Kn-2*2n-2+Kn-3*2n-3+…+K1*21+K0*20② 顯然，從等式右邊看，除最后一項K0以外，其余每項都包含有２的因子，它們都能２除盡。故R除以2，它們的余數(shù)即為K0，商變?yōu)镵n-1*2n-2+Kn-2*2n-3+Kn-3*2n-4+K1*20，將得到的商再除以2，余數(shù)即為K1

，商變?yōu)镵n-1*2n-3+Kn-2*2n-4+Kn-3*2n-5+…+K2*20

，這樣依次下去，分別得到K2

，K3

，K4…Kn，最終得到二進制數(shù)的各位數(shù)。十進制數(shù)126的轉(zhuǎn)換如下圖所示。根據(jù)上圖，十進制數(shù)126可以用二進制數(shù)1111110表示（這里只討論數(shù)之間的轉(zhuǎn)換，沒有涉及標準格式的存儲，為了方便，如無特殊說明，不用0去補足計算機的實際位數(shù)）。 （126）10=（1111110）2（2）二進制數(shù)轉(zhuǎn)換為十進制數(shù)二進制數(shù)轉(zhuǎn)換為十進制數(shù)比較簡單，由①式和②式我們很容易得到

(R)10=Kn-1*2n-1+Kn-2*2n-2+Kn-3*2n-3+…+K1*21+K0*20 我們只要簡單地將每一位與其對應為的2的冪次方相乘，然后求和。比如

(1111110)2=1*26+1*25+1*24+1*23+1*22+1*21+0*20 =64+32+16+8+4+2+0=(126)10

。 這樣，就完成了從二進制數(shù)向十進制數(shù)的轉(zhuǎn)換。以下是幾個計算機中常用的二進制數(shù)和十進制數(shù)轉(zhuǎn)換的例子。

2.八進制數(shù)與二進制數(shù)之間的轉(zhuǎn)換因為23=8，所以1位八進制數(shù)相當于3位二進制數(shù)。利用這一點，我們可以將每位八進制數(shù)用3位對應的二進制數(shù)來表示，完成八進制數(shù)向二進制數(shù)的轉(zhuǎn)換；將二進制數(shù)每3位表示成1位八進制數(shù)，完成二進制數(shù)向八進制數(shù)的轉(zhuǎn)換。下面，通過兩個例子說明八進制和二進制之間的轉(zhuǎn)換。 （1）八進制數(shù)轉(zhuǎn)換為二進制數(shù)

例如，八進制數(shù)（254）8

要轉(zhuǎn)換為二進制數(shù)，則將2，5，4分別用3位二進制表示。 （2）二進制數(shù)轉(zhuǎn)換為八進制數(shù)例如，二進制數(shù)（11010010110)2

要轉(zhuǎn)換為八進制數(shù)，則將11010010110從最低端開始每3位寫成一組，最高端不足3位的用0補足。再將每一組3位二進制數(shù)表示成八進制即：（245）8=（010100101）2即：（11010010110）2=（3226）8

3.十六進制數(shù)與二進制數(shù)之間的轉(zhuǎn)換根據(jù)八進制數(shù)與二進制數(shù)轉(zhuǎn)換的原理，由于24=16，所以1位十六進制數(shù)相當于4位二進制數(shù)。（1）十六進制數(shù)轉(zhuǎn)換為二進制數(shù)例如，（5AC8）16

可轉(zhuǎn)換為即（5AC8）16=（0101101011001000）2

（2）二進制數(shù)轉(zhuǎn)換為十六進制數(shù) 同樣的道理，例如（100101000111001）2

可轉(zhuǎn)換為即（100101000111001）2=（4A39）16 計算機中的數(shù)據(jù)是以二進制數(shù)表示的，二進制數(shù)的每1位只能為0或1，而人要處理一長串的0和1是非常乏味且容易出錯的。而采用十六進制可以有效的幫助我們，借助這種方法，一個16位的二進制數(shù)0100101000111001可以用更簡單的十六進制數(shù)4A39來表示。即（100101000111001）2=（4A39）164.7.2原碼、反碼、補碼及其轉(zhuǎn)換

前面，介紹了進制數(shù)及其轉(zhuǎn)換?，F(xiàn)在，介紹帶符號的編碼表示方法。帶符號的編碼與數(shù)字計算機最基本的一個運算，即“加法”有關(guān)。而數(shù)字計算機中的“減法”，則是通過下面的“補數(shù)”法，簡化為“加法”實現(xiàn)的。 1.原碼 原碼是一種最簡單而又直觀的編碼方法。數(shù)的符號用一位數(shù)碼表示，0表示正號，1表示負號，其余的數(shù)位與數(shù)值本身相同。例如 N1=+1001101N2=-1001101 其原碼為： [N1]原=01001101[N2]原=11001101

需要指出的是數(shù)值0如何表示。由于機器數(shù)受位數(shù)的限制，當計算中出現(xiàn)太小的數(shù)時（即下溢出），機器作為0處理，于是有正0與負0之分，即+0.00…0，-0.00…0。若要表示為原碼，則有： [+0]原=0.00…0[-0]原=1.00…0 原碼表示簡單，與真值間的轉(zhuǎn)換很容易。但是由于只是簡單地將符號數(shù)值化，而沒有與數(shù)值統(tǒng)一編碼，作加減運算時很不方便。例如兩符號相反的數(shù)相加：1011+0010，（-3+2），表面上是做加法，事實上由于兩數(shù)異號，故做減法，即原碼表示的數(shù)在做加法運算時，不僅要根據(jù)指令規(guī)定的操作性質(zhì)（加或減），還要根據(jù)兩數(shù)的符號，才能決定實際操作是加還是減。這些操作使控制線路復雜化，運算速度降低。

2.反碼 反碼是機器數(shù)的另一種編碼表示法。它是一種正數(shù)與原碼相同，負數(shù)將原碼除符號位外其余各位求反的表示法。求反就是0變1，1變0的操作。例 [2]原=00000010 [2]反=00000010 [-2]原=10000010 [-2]原=11111101 由于0的原碼存在兩個，且反碼由原碼得到，所以0的反碼也存在兩個 [+0]原=0.00…0[-0]原=1.11…1 計算機中得到反碼非常方便，因為計算機中將一個二進制數(shù)變反是很容易的。通常只需要完成一個按位加的操作便可。比如0110101求反

但是反碼和原碼一樣，計算比較麻煩，因此實際使用不多，通常只是將反碼作為求補碼過程的中間形式。 3.補碼 為了彌補原碼和反碼計算能力的不足，在計算機中引入了補碼的概念。我們先來看兩個例子。第一個例子是兩個十進制數(shù)之間的運算 8-3=58+7=15=10+5 如果運算器只能計算1位十進制數(shù)，那么在做加法8+7時，結(jié)果中的10超出該運算器的表示范圍時，將會被自動舍去。運算器只能表示出結(jié)果為5。在做減法8-3時，若用加法8+7代替，同樣可以得到結(jié)果5。 在介紹補碼中，另一個經(jīng)典的例子就是調(diào)整時鐘。如果現(xiàn)在時鐘的時間是9點，要把時鐘調(diào)到2點，我們很容易想到兩種方法。一種方法是從9點開始逆時針回撥7小時到2點，即減去7；另一種方法是從9點開始順時針前撥5小時到2點，即加上5。兩種方法都能將時鐘調(diào)到4點。 上面的兩個例子，10是第一個例子的模，12是第二個例子的模。我們稱7是以10為模的-3的補數(shù)，5是以12為模的-7的補數(shù)。通過模和補數(shù)的概念，我們就可以將減法變成加法，將負數(shù)變成正數(shù)，這正是引入補碼的目的所在。 由上面兩個例子，我們可以歸納出求補數(shù)的方法[-3]補

=（-3+10）=7[-7]補

=（-7+12）=5 即[-X]補

=（-X+MOD） 補數(shù)的概念來自數(shù)學的“同余”概念。為免敘述上的混淆，采用“補碼”這個名稱。所謂補碼，是指在計算機中用補數(shù)碼表示數(shù)值。對于正數(shù)，補碼即原碼本身；而對于負數(shù)，補碼是原碼對模數(shù)的補數(shù)。換句話說，對負數(shù)而言，可以用負數(shù)加模的方法得到其補碼。 在計算機中二進制數(shù)的補碼是如何表示的？ 我們知道，計算機中數(shù)的表示受計算機字長的限制，其運算都是有模運算。模在機器中是表示不出來的，各運算結(jié)果超出能表示的數(shù)值范圍，則會自動舍去溢出量（模），只保留小于模的部分。 設字長為n+1位，對定點小數(shù)x0.x1x2…xn

，其溢出量為 即2，則以2為模。對定點整數(shù)x0x1x2…xn，其溢出量為，即2n+1

，則以2n+1為模。在知道了二進制數(shù)的模后，根據(jù)我們上面的公式[-X]補

=（-X+MOD），我們可以求出二進制數(shù)的補碼了。

在知道了二進制數(shù)的模后，根據(jù)我們上面的公式[-X]補

=（-X+MOD），我們可以求出二進制數(shù)的補碼了。 以定點小數(shù)說明。設有如下兩個數(shù) [+0.1011]原

=0.1011[-0.1011]原

=1.1011 正數(shù)的補碼就是它本身．即正數(shù)的補碼與原碼相同 [+0.1011]原

=0.1011 [+0.1011]補

=0.1011 下面，我們求負數(shù)的補碼 [-0.1011]原

=1.1011 [-0.1011]補

=-0.1011+10=1.0101

4.原碼、反碼和補碼的轉(zhuǎn)換 這里介紹一種二進制負數(shù)求補碼的更簡單的方法：對于一個機器數(shù)原碼來說，如果為正數(shù)，則其補碼與原碼相同，如果為負數(shù)，則除符號為不變外，其余各位按位求反，并在最低位上加１即得其補碼。 還是用剛才的二進制數(shù)-0.1011，它的原碼為1.1011，我們對其除符號位外求反得1.0100，再加上1就得到了-0.1011的補碼1.0101。

一個補碼又如何變回原碼以得到真值呢?對于正數(shù)，補碼就是原碼，不必變換。而對于負數(shù)，則是再次“取反加1”，我們求上例補碼的原碼，只需 我們看到，得到的原碼與上例中的原碼是相同的。我們做如下歸納，對正數(shù)而言，原碼、反碼和補碼的表示形式是相同的；對負數(shù)而言，原碼與反碼的互換，只需“除符號位不變外，按位求反”，原碼與補碼的互換，只需“除符號位不變外，按位求反再加1”。4.7.3字符、字符串和漢字

在計算機中，除了能處理數(shù)值數(shù)據(jù)信息外，還能處理大量的如字符、圖像及漢字等的信息，這些信息在計算機中也必須用二進制代碼形式表示。要想用計算機對這些信息進行處理，首先遇到的一個問題是如何用二進制數(shù)表示字符，即如何對字符編碼。 1.字符目前被廣泛采用的字符編碼是由美國國家標準局（AmericanNationalStandards）制定的美國標準信息交換碼——（AmericaStandardCodeforInformationInterchange，ASCII），該編碼被國際標準化組織（ISO）定為國際標準，稱為ISO646標準。ASCII碼用8位二進制碼來表示英文中的大小寫字母、標點符號、數(shù)字0到9以及一些控制數(shù)據(jù)（如換行、回車和制表符等），最高位為0。若將最高位設為1，還可以將標準的ASCII進行適當?shù)臄U展（可增加128個字符）。下面，給出常用的ASCII碼對照表（表4.1）。表4.1常用的的ASCII碼對照表查ASCII碼對照表，可知A的ASCII碼是01000001，a的ASCII碼是01100001，字符就是用這樣的二進制數(shù)表示的。2.字符串 字符串又是怎么表示的呢？字符串是由字符序列所組成的，字符串可以表示成一系列字節(jié)，每個字節(jié)對應ASCII碼中的一個特定字符。例如，字符串“hello”可以表示成

3.漢字 盡管八位ASCII碼完全可以表示任何英文字符，但對中文來說，256個字符是遠遠不夠的，那中文怎么表示呢？在ASCII碼的基礎上，可以對其進行擴展，使其區(qū)分不同漢字。 漢字機內(nèi)碼是計算機內(nèi)部存儲和處理漢字的編碼。常用兩個字節(jié)表示，每個字節(jié)的最高位都設置為1。 內(nèi)碼是以漢字拼音的順序排序的，第一個漢字是“啊”，它的內(nèi)碼是B0A1，即第一個八位字節(jié)為10110000，后一個八位字節(jié)為10100001。 利用內(nèi)碼，可以找到相對應的漢字字形信息，然后，再將它送到輸出設備中。在屏幕上，可以用32個字節(jié)的字形碼表示1616的漢字點陣信息。二進制的0表示點陣上的白色，1表示黑色。 圖4.6是“啊”的點陣圖，每一行用兩個字節(jié)表示，第一行的二進制代碼是0000000000000100，第二行的二進制代碼是0010111101111110，第三行是1111100100000100，以此類推。最終用16行，共32個字節(jié)的字形碼表示一個1616的漢字點陣信息。圖4.6“啊”的點陣圖 通常，把所有字形碼的集合稱為字庫，先把它存在計算機中(如以文件形式存放在硬盤中)，在漢字輸出時，根據(jù)漢字內(nèi)碼找到相應的字形碼，然后，再由字形碼的1，0，控制輸出設備的黑白輸出顯示漢字。

日文、韓文、阿拉伯文、臺灣繁體（BIG-5）……都使用類似的方法來擴展本地字符集的定義。但是這個方法是有缺陷的，在上網(wǎng)時，可能會遇到這樣的問題，在訪問日文、韓文、或繁體網(wǎng)站時，出現(xiàn)亂碼。這是因為一個系統(tǒng)中只能有一種內(nèi)碼，因此，必須進行相應的字符內(nèi)碼轉(zhuǎn)換。為了支持不同國家的語言字符集，ASCII碼正在被Unicode碼所代替，Unicode是一個16位的編碼系統(tǒng)。它用16位二進制來表示每一個符號，這樣Unicode就有216（65536）種不同的二進制編碼。足以將日語、韓語和中文等的常用字都表示出來。為了簡化ASCII與Unicode之間的轉(zhuǎn)換，Unicode的設計者還使其向后兼容ASCII碼。原來用ASCII碼能表示的字符，其Unicode碼只是在原來的ASCII碼前加上8個0。比如，a的ASCII碼是01100001，而它的Unicode碼是00000001100001。4.7.4圖像

在計算機中表示圖像的技術(shù)兩種：位圖和矢量圖。1.位圖在位圖技術(shù)中，圖像被看作是點的集合，每一個點叫做一個像素。對黑白圖像來說，每一個像素點用1位表示就足夠了，1表示黑色，0表示白色。這與上面介紹的漢字的字型碼表示是一樣的。 在表示彩色圖像時，每個像素用1位表示就不夠了。最普遍的系統(tǒng)是將每個像素用24位來表示。為什么呢？這里引入一個術(shù)語RGB，它說的是像素的顏色可以由紅色（Red）、綠色（Green）、藍色（Blue）這三原色根據(jù)不同的強度疊加而成。我們將強度的范圍規(guī)定在0~255之間（從小到大顏色的強度值遞增），因此紅、綠、藍每種顏色的強度用8位表示，那么一個像素就是用24位來表示了。表4.2是常用顏色RGB值的對照表。

顏色（R,G,B）顏色（R,G,B）Red（紅）（255,0,0）Green（綠）（0,128,0）Darkred（暗紅）（139,0,0）Darkgreen（深綠）（0,100,0）Crimson（深紅）（220,20,60）Lightgreen（淺綠）（144,238,144）Pink（粉紅）（255,192,203）Brown（褐）（165,42,42）Violet（紫羅蘭）（255,130,238）White（白）（255,255,255）Orange（橙色）（255,165,0）Blue（藍）（0,0,255）Purple（紫）（128,0,128）Darkblue（深藍）（0,0,139）Black（黑）（255,255,255）Lightblut（淡藍）（173,219,230）表4.2常用顏色RGB值對照表

例如一個像素點的顏色是橙色，從上表，可以得到它的RGB值為（255，165，0），表示成二進制便是111111111010010100000000。一個像素點用24位存儲，這就意味著，用位圖技術(shù)存儲一張10241024的圖片就需要3兆字節(jié)的存儲空間。 2.矢量圖 與位圖不同，矢量圖是以指令來描述圖像的。它用指令來描述直線，曲線，矩形，圓形的形狀、大小、材質(zhì)等等。它不需要向位圖技術(shù)那樣，記錄每個像素點的信息，而只需要記錄描述圖形的幾個關(guān)鍵信息，然后用指令描述這幾個關(guān)鍵信息傳送給最終產(chǎn)生圖形的設備，將實現(xiàn)的細節(jié)留給這些設備去解決。

比如用矢量技術(shù)表示一個圓，計算機所需的信息只有兩個——圓心的坐標和半徑。然后再利用圖形設備上相應的函數(shù)畫出圖形。 由于矢量技術(shù)不需要存儲每一個像素量化的值，所以存儲空間大大減小。但是由于矢量技術(shù)是用指令來描述圖像的，如果涉及的圖像十分復雜，那么指令數(shù)目將會很大，調(diào)用函數(shù)的次數(shù)也隨之增大，因此對于復雜的圖像，矢量技術(shù)比位圖耗時要大。4.7.5聲音

聲源體發(fā)生振動，引起四周空氣振蕩便形成了聲波。聲波借助空氣向四面八方傳播，我們便聽到了聲音。聲波由振蕩產(chǎn)生，所以聲波是連續(xù)的，聽到的聲音是連續(xù)的。我們把這種連續(xù)的信號稱為模擬信號。 但是，計算機所能處理的只能是數(shù)字信號，用計算機如何存儲和處理是模擬信號的聲音呢？ 很容易想到的方法是“轉(zhuǎn)換”——將連續(xù)的模擬波形轉(zhuǎn)換為一系列離散的數(shù)值。這一轉(zhuǎn)換的過程包括“采樣”和“量化”。采樣就是等時間間隔地讀取波形的幅值，量化是把讀取聲波的幅值表示為數(shù)字值（圖4.7）。即（100101000111001）2=（4A39）16

采樣的時間間隔取多少好呢？我們給出一個概念——采樣頻率，它是指在將模擬信號數(shù)字化時，每秒鐘采樣的次數(shù)。在今天的CD中，為了得到高質(zhì)量的聲音，通常采用的是44.1kz的采樣頻率，即每秒要采樣44100次。如果每次采樣所得到的幅值用32位來表示的話，1分鐘CD文件的大小就是10兆多。為了減少數(shù)字聲音文件的大小，通常的方法是濾掉高于人類聽力范圍的聲音，或者識別到一種聲音將淹沒另一種聲音的時候，濾掉較弱的聲音。現(xiàn)在流行的MP3格式的聲音文件，它利用MPEGAudioLayer3的壓縮技術(shù)，把文件壓縮為只有原來的1/10甚至更小，而音質(zhì)卻能和CD差不多。4.8CC1991報告提取的核心概念

學科中的核心概念是CC1991報告首次提出的，具有普遍性、持久性的重要思想、原則和方法。報告認為，熟練掌握和應用這些核心概念是一個成熟的計算機科學家和工程師的標志之一。 1．綁定（Binding） 綁定指的是通過將一個對象（或事物）與其某種屬性相聯(lián)系，從而使抽象的概念具體化的過程。例如，將一個程序的執(zhí)行過程與一個處理機聯(lián)系起來；一個變量與其類型或值聯(lián)系起來。 2．大問題的復雜性（ComplexityofLargeProblems） 大問題的復雜性是指隨著問題規(guī)模的增長而使問題的復雜性呈非線性增加的效應。這種非線性增加的效應是區(qū)分和選擇各種現(xiàn)有方法和技術(shù)的重要因素。例如，在軟件工程中，隨著問題規(guī)模的增大，系統(tǒng)的復雜性也在增大。每個新的信息項、功能或限制都可能影響整個系統(tǒng)的其他元素。因此，隨著問題復雜性的增加，系統(tǒng)分析的任務將呈幾何級數(shù)增長。在研制一個大系統(tǒng)時，顯然，控制和降低系統(tǒng)的復雜性便成為區(qū)分和選擇現(xiàn)有方法和技術(shù)的重要因素。

3．概念模型和形式模型（ConceptualandFormatModels） 概念模型和形式模型是對一個想法或問題進行形式化、特征化、可視化思維的方法。抽象數(shù)據(jù)類型、語義數(shù)據(jù)類型以及指定系統(tǒng)的圖形語言，如數(shù)據(jù)流圖和E-R圖等都屬于概念模型。而邏輯、開關(guān)理論和計算理論中的模型大都屬于形式模型。概念模型和形式模型以及 形式證明是將計算學科各分支統(tǒng)一起來的重要核心概念。 4．一致性和完備性（ConsistencyandCompleteness） 一致性包括用于形式說明的一組公理的一致性、事實和理論的一致性，以及一種語言或接口設計的內(nèi)部一致性。完備性包括給出的一組公理，使其能獲得預期行為的充分性、軟件和硬件系統(tǒng)功能的充分性，以及系統(tǒng)處于出錯和非預期情況下保持正常行為的能力等

在計算機系統(tǒng)設計中，正確性、健壯性和可靠性就是一致性和完備性的具體體現(xiàn)。 5．效率