第1章基基礎(chǔ)知識識1.1計算機軟軟件概述述1.2操作系統(tǒng)統(tǒng)的基本本概念1.3算法法1.1計算機軟軟件概述述1.1..1計算機軟軟件及其其分類計算機系系統(tǒng)由計計算機硬硬件系統(tǒng)統(tǒng)和計算算機軟件件系統(tǒng)組組成。計算機硬硬件系統(tǒng)統(tǒng)是指實實際的物物理設(shè)備備，包括括計算機機的主機機和外圍圍設(shè)備。。計算機軟軟件系統(tǒng)統(tǒng)，是指指能指揮揮計算機機工作的的程序、、程序運運行時所所需要的的數(shù)據(jù)以以及與這這些程序序和數(shù)據(jù)據(jù)有關(guān)的的文字說說明和圖圖表資料料。其中文字字說明和和圖表資資料又稱稱為文檔檔。1．系統(tǒng)軟軟件系統(tǒng)軟件件是指管管理、監(jiān)監(jiān)控和維維護計算算機資源源(包括硬件件和軟件件)，并提供供用戶與與計算機機之間界界面等工工具的軟軟件。（1）操作系系統(tǒng)（2）程序設(shè)設(shè)計語言言與語言言處理程程序（3）工具軟軟件2．應(yīng)用軟軟件常見的應(yīng)應(yīng)用軟件件有以下下幾種:①各種信息息管理軟軟件。②辦公公自動化化系統(tǒng)。。③各種種文字處處理軟件件。④各種種輔助設(shè)設(shè)計軟件件以及輔輔助教學(xué)學(xué)軟件。。⑤各種種軟件包包，如數(shù)數(shù)值計算算程序庫庫、圖形形軟件包包等。1.1..2程序設(shè)計計語言及及其語言言處理程程序程序設(shè)計計語言一一般分為為機器語語言、匯匯編語言言和高級級語言三三類。1．機器語語言機器語言言是最底底層的計計算機語語言。用用機器語語言編寫寫的程序序，計算算機硬件件可以直直接識別別。2．匯編語語言匯編語言言與機器器語言一一般是一一一對應(yīng)應(yīng)的，用用匯編語語言編寫寫的程序序也比機機器語言言程序易易讀、易易檢查、、易修改改。將匯編語語言源程程序翻譯譯成機器器語言程程序的程程序稱為為匯編程程序。3．高級語語言機器語言言和匯編編語言都都是面向向機器的的語言，，一般稱稱為低級級語言。。面向問題題的程序序設(shè)計語語言，稱稱為高級級語言。。高級語言言與具體體的計算算機硬件件無關(guān)，，其表達達方式接接近于被被描述的的問題，，易為人人們接受受和掌握握。1.2操作系統(tǒng)統(tǒng)的基本本概念1.2..1操作系統(tǒng)統(tǒng)的功能能與任務(wù)務(wù)操作系統(tǒng)統(tǒng)是最基基本的和和核心的的系統(tǒng)軟軟件。。操作系統(tǒng)統(tǒng)實際上上是由一一些程序序模塊組組成的，，它們是是系統(tǒng)軟軟件中最最基本的的部分，，其主要要作用有有以下幾幾個方面面：①管理系統(tǒng)統(tǒng)資源。。②為用用戶提供供資源共共享的條條件和環(huán)環(huán)境，并并對資源源的使用用進行合合理調(diào)度度。③提供供輸入/輸出的方方便環(huán)境境，簡化化用戶的的輸入/輸出工作作，提供供良好的的用戶界界面。④規(guī)定定用戶的的接口，，發(fā)現(xiàn)、、處理或或報告計計算機操操作過程程中所發(fā)發(fā)生的各各種錯誤誤。操作系統(tǒng)統(tǒng)的功能能和任務(wù)務(wù)主要有有以下五五個方面面。1．處理機機管理處理機管管理的主主要任務(wù)務(wù)是：充充分發(fā)揮揮處理機機的作用用，提高高它的使使用效率率。2．存儲器器管理存儲器管管理的主主要任務(wù)務(wù)是：對對有限的的內(nèi)存儲儲器進行行合理的的分配，，以滿足足多個用用戶程序序運行的的需要。。3．設(shè)備管管理設(shè)備管理理的主要要任務(wù)是是：有效效地管理理各種外外部設(shè)備備，使這這些設(shè)備備充分發(fā)發(fā)揮效率率；并且且還要給給用戶提提供簡單單而易于于使用的的接口，，以便在在用戶不不了解設(shè)設(shè)備性能能的情況況下，也也能很方方便地使使用它們們。4．文件管管理文件管理理的主要要任務(wù)是是：實現(xiàn)現(xiàn)惟一地地標識計計算機系系統(tǒng)中的的每一組組信息，，以便能能夠?qū)λ鼈冞M行行合理地地訪問和和控制；；以及有有條理地地組織這這些信息息，使用用戶能夠夠方便且且安全地地使用它它們。5．作業(yè)管管理它的主要要任務(wù)是是：對所所有的用用戶作業(yè)業(yè)進行分分類，并并且根據(jù)據(jù)某種原原則，源源源不斷斷地選取取一些作作業(yè)交給給計算機機去處理理。1.2..2操作系統(tǒng)統(tǒng)的發(fā)展展過程1．手工操操作階段段2．成批處處理系統(tǒng)統(tǒng)3．執(zhí)行程程序系統(tǒng)統(tǒng)4．多道程程序系統(tǒng)統(tǒng)的引入入1.2..3操作系統(tǒng)統(tǒng)的分類類1．多道批批處理操操作系統(tǒng)統(tǒng)多道批處處理操作作系統(tǒng)包包含“多多道”和和“批處處理”兩兩層意思思?！岸嗟馈薄笔侵冈谠谟嬎銠C機內(nèi)存中中存入多多個用戶戶作業(yè)。。“批處理””是指這這樣一種種操作方方式，在在外存中中存入大大量的后后備作業(yè)業(yè)，作業(yè)業(yè)的運行行完全由由系統(tǒng)控控制，用用戶與其其作業(yè)之之間沒有有交互作作用，用用戶不能能直接控控制其作作業(yè)的運運行，通通常稱這這種方式式為批操操作或脫脫機操作作。2．分時操操作系統(tǒng)統(tǒng)在分時操操作系統(tǒng)統(tǒng)中，多多個用戶戶分享使使用同一一臺計算算機，即即在一臺臺計算機機上聯(lián)接接若干臺臺終端，，每個用用戶可以以獨占一一臺終端端。分時操作作系統(tǒng)具具有以下下幾方面面的特點點：①同時時性。②獨立立性。③及時時性。④交互互性。3．實時操操作系統(tǒng)統(tǒng)所謂實時時，是指指對隨機機發(fā)生的的外部事事件作出出及時的的響應(yīng)并并對其進進行處理理。具有實時時要求的的系統(tǒng)稱稱之為實實時系統(tǒng)統(tǒng)。4．通用操操作系統(tǒng)統(tǒng)5．優(yōu)良的的操作環(huán)環(huán)境——多窗口系系統(tǒng)所謂多窗窗口，就就是把計計算機的的顯示屏屏幕劃分分出多個個區(qū)域，，每個區(qū)區(qū)域稱為為一個窗窗口，每每個窗口口負責(zé)處處理和顯顯示某一一類信息息。向用戶提提供友好好界面是是多窗口口系統(tǒng)主主要體現(xiàn)現(xiàn)在以下下幾方面面：（1）靈活、、方便的的窗口操操作（2）彈出式式菜單（3）命令對對話框1.3算法法1.3..1算法的基基本概念念算法是指指解題方方案的準準確而完完整的描描述。通常，算算法又分分為數(shù)值值型算法法與非數(shù)數(shù)值型算算法。非數(shù)值型型算法又又稱為符符號處理理。1．算法的的基本特特征（1）可行性性①算法法中的每每一個步步驟必須須能夠?qū)崒崿F(xiàn)。②算法法執(zhí)行的的結(jié)果要要能夠達達到預(yù)期期的目的的。（2）確定性性算法的確確定性（（Definiteness），是指指算法中中的每一一個步驟驟都必須須是有明明確定義義的。。（3）有窮性性算法的有有窮性（（Finiteness），是指指算法必必須能在在有限的的時間內(nèi)內(nèi)做完，，即算法法必須能能在執(zhí)行行有限個個步驟之之后終止止。（4）擁有足足夠的情情報2．算法的的基本要要素一個算法法通常由由兩種基基本要素素組成：：一是對對數(shù)據(jù)對對象的運運算和操操作，二二是算法法的控制制結(jié)構(gòu)。。（1）算法中中對數(shù)據(jù)據(jù)的運算算和操作作（2）算法的的控制結(jié)結(jié)構(gòu)1.3..2算法描述述語言1．符號與與表達式式符號是以以字母開開頭的字字母和數(shù)數(shù)字的有有限串，，主要用用以表示示變量名名、數(shù)組組名等，，必要時時也用來來表示語語句標號號。在語句標標號后應(yīng)應(yīng)跟隨一一個冒號號，然后后是語句句。例如如：loop：i=i++1在算法中中，算術(shù)術(shù)運算符符沿用數(shù)數(shù)學(xué)中的的表示法法。關(guān)系運算算符用=、≠、＜＜、＞、、≤、≥≥等表示示。邏輯運算算符用and（與）、、or（或）、、not（非）來來表示。。2．賦值語語句賦值語句句的形式式為：a=e3．控制轉(zhuǎn)轉(zhuǎn)移語句句無條件轉(zhuǎn)轉(zhuǎn)移語句句的形式式為：GOTO標號4．循環(huán)語語句循環(huán)語句句有兩種種形式：：一是WHILE語句，二二是FOR語句。WHILE語句的形形式為：：WHILECDOSFOR語句的形形式為：：FORi==initTOlimitBYstepDOS5．其他語語句1.3..3算法設(shè)計計基本方方法1．列舉法法列舉法的的基本思思想是，，根據(jù)提提出的問問題，列列舉所有有可能的的情況，，并用問問題中給給定的條條件檢驗驗?zāi)男┦鞘切枰牡?，哪些些是不需需要的?！?．枚舉歸歸納法枚舉歸納納法的基基本思想想是，通通過列舉舉足夠多多（但不不是全部部）的特特殊情況況，發(fā)現(xiàn)現(xiàn)其中的的一些規(guī)規(guī)律，經(jīng)經(jīng)過分析析，最后后找出一一般的關(guān)關(guān)系。3．遞推遞推是指指從已知知的初始始條件出出發(fā)，逐逐次推出出所要求求的各中中間結(jié)果果和最后后結(jié)果。。4．遞歸這種將問問題逐層層分解的的過程，，實際上上并沒有有對問題題進行求求解，而而只是當當解決了了最后那那些最簡簡單的問問題后，，再沿著著原來分分解的逆逆過程逐逐步進行行綜合，，這就是是遞歸的的基本思思想。由此可以以看出，，遞歸的的基礎(chǔ)也也是歸納納。遞歸分為為直接遞遞歸與間間接遞歸歸兩種。。如果一一個算法法P直接調(diào)用用自己則則稱為直直接遞歸歸。如果算法法P調(diào)用另一一個算法法Q，而算法法Q又調(diào)用算算法P，則稱為為間接遞遞歸調(diào)用用。5．減半遞遞推技術(shù)術(shù)“減半””是指將將問題的的規(guī)模減減半，而而問題的的性質(zhì)不不變。“遞推””是指重重復(fù)“減減半”的的過程。。6．回溯法法1.3..4算法的復(fù)復(fù)雜度分分析算法的復(fù)復(fù)雜度主主要包括括時間復(fù)復(fù)雜度和和空間復(fù)復(fù)雜度。。1．算法的的時間復(fù)復(fù)雜度算法的時時間復(fù)雜雜度，是是指執(zhí)行行算法所所需要的的計算工工作量。。（1）平均性性態(tài)分析析