計算機科學中的算法設計與數據結構的離散性解析

高塔

?

計算機科學中的算法設計與數據結構的離散性解析

高塔

河北農業大學信息科學與技術學院，河北 保定 071000

主要探討了計算機科學中算法設計與數據結構的離散性，用以對計算機問題的抽象解決進行具體化的解釋，從而建立一種“連續性—離散性”的思維模式。

計算機科學；算法設計；數據結構；離散性；二進制

引言

計算機科學是一門包含多種與計算、信息處理相關的主題的系統科學，其由理論計算機科學、實驗計算機科學組成[1]。在計算機科學中，計算機算法設計與數據結構是重要的基礎知識，是計算機科學計算與模擬實驗得以實現的工具，因此深入研究計算機算法設計與數據結構對計算機科學的發展具有重要意義。本文主要解析計算機科學中算法設計與數據結構的離散性問題。

1 算法設計的離散性

算法是對問題的解決的具體性完整性的方案描述，其代表了運用系統的方法對解決問題加以描述的策略機制。算法設計體現了計算機科學的離散性，其常用方法包括遞推法和遞歸法。筆者主要探討算法設計方法的離散性。

1.1 遞推法

遞推法是一種常用于序列計算機中的算法，其核心內容是重復復雜計算過程到簡單計算過程的轉化。

按照遞推法的定義，計算機采用了一種笨辦法來實現復雜的運算，比如求最大值的算法。根據求最大值的算法，計算機會反復比較最大的已知數字和數組中的下一數字，直至結束。與此相比，人類采用了完全不同的方式進行數值大小的比較，即當數字較多時，先確定數字的位數，再選定位數最高的數字；若該類數字的個數較多，則需逐一比較。這種思維模式是人類慣用的連續性思維。對此，計算機很難運用這種連續性思維，而需設計復雜的算法來“模擬”這一連續性思維。另外，可能存在下列可能性：人類的大腦較為高級及其算法非常復雜，因此具備連續性的思維[2]。

1.2 遞歸法

遞歸法是指一個函數或過程在說明或定義中間接或直接調用自身編程技巧的方法，其一般會層層轉化復雜的大型問題，使其變成小型問題，然后再求解問題[3]。

在一些情況下，遞歸法能夠簡化算法，比如求最大公約數的算法。遞歸法求最大公約數可描述為“自己調用自己”，其離散性的表現有下列兩種：一種與求最大值的算法類似；另一種則是指程序運行的離散性，即計算機在棧中實現程序的運行，而棧具有“后進先出”的特點。

該種遞歸算法在運行中，通過返回“自己”可獲得相應的返回值，直至返回獲得確定值后，再逐層返回。綜上，在遞歸算法中，計算機每完成一次遞歸計算，便向內存Push一次，直至計算結束，然后再逐一Pop出。對此，其體現出了計算的離散性，而不是連續性思維模式[4]。

1.3 算法設計的原則

為了保證計算機的運行處理效果，要求算法設計遵循下列幾點原則：首先，算法的正確性，算法必須正確無誤，要求按需選擇科學的算法編寫程序，注意算法的結果應具有唯一性；其次，算法的可讀性，即保證程序的運算更快、更好；再次，算法的穩定性，即避免計算機的輸出曲線出現波動異常；最后，算法的高效低耗性能，即在“節能環保”理念的指導下，實現計算機運行的快速性、低噪聲和低能耗。

2 數據結構的離散性

數據結構是對數據元素與數據元素的結構關系進行研究。數據結構一般按元素關系的特性分為網狀、樹形、線性和集合四種基本結構（見圖1），表明數據結構中的數據元素具有離散性[5]。

圖1 數據結構基本類型

從圖1可知，集合結構是由一些離散的數據元素組成的；線性結構具有非常明顯的離散性；樹形、圖形結構均由一些獨立存在的數據元素組成，表明數據元素與數據元素的關系具有離散性和不連續性。離散數學是一種未涉及連續變化量的數學，主要用于研究以離散空間為基礎的數學結構。對于數據結構，離散數學與其存在非常緊密的關系，比如圖論，其研究了數據元素與數據元素的復雜關系。

另外，在計算機中，通過應用離散數學的一些理論知識，解決了一些高難度的問題或實現了解決方法的優化，比如Huffman樹，其常用來實現壓縮解碼。

數字電子是與計算機學科交叉的一門學科，其離散性可采用數字信號進行解釋。其中，數字信號是一組數值與時間皆為離散的信號，其對應于模擬信號而且是一組數值與時間皆為連續的信號。數學上認為“連續性”意味著該類信號具有微積分意義，說明離散的信號沒有意義[6]。

3 計算機中的離散性問題

在計算機中，二進制的運用賦予了計算機處理問題的離散性特征，而且計算機科學中的算法設計與數據結構兩者均可以用二進制闡述其離散性特征。據此，對于計算機中的離散性問題，筆者主要從二進制的角度展開論述。

3.1 二進制

3.2 二進制的離散性

對于音頻、視頻及圖片等信息，人類非常容易理解，但計算機卻因只認識“0”和“1”，而無法直接理解該類信息，因此計算機需利用離散的數據認識整個世界。其中，離散的數據可從本質上理解為僅包含“0”和“1”的二進制數據。據此，計算機的處理對象皆為離散的數據。例如，在處理音頻時，只有先對連續改變的聲音進行二進制處理，才能實現計算機對該類數據的處理。計算機離散化處理音頻信息的方法如圖2所示。

圖2 計算機離散化處理音頻信息

如圖2所示，計算機對音頻信息的離散化處理越“細”，則聲音更能還原其原貌。

總之，在計算機中，計算機處理問題因二進制的運用而表現出離散性特征，且前文談及的算法設計、數據結構皆可利用二進制來進行離散性解釋。

4 結語

自人類進入21世紀以來，計算機科學實現了飛速發展，且其實際需求量與日俱增，從而激發了相關領域對計算機離散性的重視。在本文，筆者主要探討了如何利用離散數學來解決計算機的離散性問題。首先，介紹了計算機科學中算法設計的常用方法，即遞推法和遞歸法，并舉例探討了兩種方法的離散性體現；其次，介紹了計算機科學中的數據結構與其離散性體現；最后，提出了計算機離散性問題以二進制的運用最為關鍵。

總之，為了適應計算機科學深入發展的需要，要求深化對計算機科學中算法設計與數據結構的離散性問題的研究。

[1]孔娟華，鄭江濱. 一種三維離散點數據生成非結構四面體算法[J]. 計算機工程與科學，2009（1）：35-37.

[2]向裕良，彭佳紅. 關于計算機科學中數據結構算法探究[J]. 計算機光盤軟件與應用，2013（19）：154-155.

[3]朱雅莉，李肯立. DNA計算機中堆棧數據結構的設計[J]. 計算機工程與科學，2008（4）：121-123，127.

[4]張海燕，張立毅，孫云山. 基于離散剪切波正則化的低劑量CT圖像統計重建算法[J]. 計算機工程與科學，2018（1）：86-92.

[5]肖文磊，劉亞醉，Oleksandr Zavalnyi，等.T-SPLINE開源內核的三層數據結構及算法原理[J]. 計算機輔助設計與圖形學學報，2017（11）：2023-2036.

[6]趙景昌，高菲，劉光偉，等. 基于散列函數與半邊數據結構的TIN拓撲重構算法[J]. 計算機應用研究，2017（12）：3689-3692，3700.

Algorithm Design and Discrete Analysis of Data Structure in Computer Science

Gao Ta

College of Information Science and Technology, Hebei Agricultural University, Hebei Baoding 071000

The paper mainly discusses the discreteness of algorithm design and data structure in computer science. It is used to interpret the abstract solution of computer problems and establish a “continuity→discreteness” thinking mode.

computer science; algorithm design; data structure; discreteness; binary

TP301.6；TP311.1

A