計算機二級公共基礎知識(全)

1.1 算法 考點1 算法的基本概念 計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。 算法(algorithm)是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的，同時是明確的；此順序將在有限的次數后終止。算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。 1算法的基本特征 (1)可行性(effectiveness)：針對實際問題而設計的算法，執行后能夠得到滿意的結果。 (2)確定性(definiteness)：算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性。 (3)有窮性(finiteness)：算法必需在有限時間內做完，即算法必需能在執行有限個步驟之后終止。 (4)擁有足夠的情報：要使算法有效必需為算法提供足夠的情報當算法擁有足夠的情報時，此算法才最有效的；而當提供的情報不夠時，算法可能無效。 2算法的基本要素 (1)算法中對數據的運算和操作：每個算法實際上是按解題要求從環境能進行的所有操作中選擇合適的操作所組成的一組指令序列。 計算機可以執行的基本操作是以指令的形式描述的。一個計算機系統能執行的所有指令的集合，稱為該計算機系統的指令系統。計算機程序就是按解題要求從計算機指令系統中選擇合適的指令所組成的指令序列在一般的計算機系統中，基本的運算和操作有以下4類： ①算術運算：主要包括加、減、乘、除等運算； ②邏輯運算：主要包括“與”、“或”、“非”等運算； ③關系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算； ④數據傳輸：主要包括賦值、輸入、輸出等操作。 (2)算法的控制結構：一個算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執行順序有關。算法中各操作之間的執行順序稱為算法的控制結構。 算法的控制結構給出了算法的基本框架，它不僅決定了算法中各操作的執行順序，而且也直接反映了算法的設計是否符合結構化原則。描述算法的工具通常有傳統流程圖、N-S結構化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環3種基本控制結構組合而成。 (3)算法設計的基本方法 計算機算法不同于人工處理的方法，下面是工程上常用的幾種算法設計，在實際應用時，各種方法之間往往存在著一定的聯系。 (1)列舉法 列舉法是計算機算法中的一個基礎算法。列舉法的基本思想是，根據提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。 列舉法的特點是算法比較簡單。但當列舉的可能情況較多時，執行列舉算法的工作量將會很大。因此，在用列舉法設計算法時，使方案優化，盡量減少運算工作量，是應該重點注意的。 (2)歸納法 歸納法的基本思想是，通過列舉少量的特殊情況，經過分析，最后找出一般的關系。從本質上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結出一般性的結論。 (3)遞推 遞推是指從已知的初始條件出發，逐次推出所要求的各中間結果和最后結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡而確定。遞推本質上也屬于歸納法，工程上許多遞推關系式實際上是通過對實際問題的分析與歸納而得到的，因此，遞推關系式往往是歸納的結果。對于數值型的遞推算法必須要注意數值計算的穩定性問題。 (4)遞歸 人們在解決一些復雜問題時，為了降低問題的復雜程度(如問題的規模等)，一般總是將問題逐層分解，最后歸結為一些最簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問題進行求解，而只是當解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的基本思想。 遞歸分為直接遞歸與間接遞歸兩種。 (5)減半遞推技術 實際問題的復雜程度往往與問題的規模有著密切的聯系。因此，利用分治法解決這類實際問題是有效的。工程上常用的分治法是減半遞推技術。 所謂“減半”，是指將問題的規模減半，而問題的性質不變；所謂“遞推”，是指重復“減半”的過程。 (6)回溯法 在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進行無限的列舉。對于這類問題，一種有效的方法是“試”。通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再逐步試探。 4算法設計的要求 通常一個好的算法應達到如下目標： (l)正確性(correctness) 正確性大體可以分為以下4個層次： ①程序不含語法錯誤； ②程序對于幾組輸入數據能夠得出滿足規格說明要求的結果； ③程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數據能夠得出滿足規格說明要求的結果； ④程序對于一切合法的輸入數據都能產生滿足規格說明要求的結果。 (2)可讀性(readability) 算法主要是為了方便入的閱讀與交流，其次才是其執行。可讀性好有助于用戶對算法的理解；晦澀難懂的程序易于隱藏較多錯誤，難以調試和修改。 (3)健壯性(robustness) 當輸入數據非法時，算法也能適當地做出反應或進行處理，而不會產生莫名其妙的輸出結果。 (4)效率與低存儲量需求 效率指的是程序執行時，對于同一個問題如果有多個算法可以解決，執行時間短的算法效率高；存儲量需求指算法執行過程中所需要的最大存儲空間 考點2 算法的復雜度 1算法的時間復雜度 算法的時間復雜度，是指執行算法所需要的計算工作量。同一個算法用不同的語言實現，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。撇開這些與計算機硬件、軟件有關的因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規模(通常用整數n表示)，它是問題的規模函數。即 算法的工作量=f(n) 例如，在N×N矩陣相乘的算法中，整個算法的執行時間與該基本操作(乘法)重復執行的次數n3成正比，也就是時間復雜度為n3，即 f(n)=O(n3) 在有的情況下，算法中的基本操作重復執行的次數還隨問題的輸入數據集不同而不同。例如在起泡排序的算法中，當要排序的數組a初始序列為自小至大有序時，基本操作的執行次數為氏當初始序列為自大至小有序時，基本操作的執行次數為n(n- 1)/2。對這類算法的分析，可以采用以下兩種方法來分析

總結

以上是生活随笔為你收集整理的计算机二级基础知识 文库,计算机二级公共基础知识(全)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。