計算機科學(xué)中的算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)的離散性解析

高塔

?

計算機科學(xué)中的算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)的離散性解析

高塔

河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 保定 071000

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

計算機科學(xué)；算法設(shè)計；數(shù)據(jù)結(jié)構(gòu)；離散性；二進制

引言

計算機科學(xué)是一門包含多種與計算、信息處理相關(guān)的主題的系統(tǒng)科學(xué)，其由理論計算機科學(xué)、實驗計算機科學(xué)組成[1]。在計算機科學(xué)中，計算機算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)是重要的基礎(chǔ)知識，是計算機科學(xué)計算與模擬實驗得以實現(xiàn)的工具，因此深入研究計算機算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)對計算機科學(xué)的發(fā)展具有重要意義。本文主要解析計算機科學(xué)中算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)的離散性問題。

1 算法設(shè)計的離散性

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

1.1 遞推法

遞推法是一種常用于序列計算機中的算法，其核心內(nèi)容是重復(fù)復(fù)雜計算過程到簡單計算過程的轉(zhuǎn)化。

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

1.2 遞歸法

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

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

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

1.3 算法設(shè)計的原則

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

2 數(shù)據(jù)結(jié)構(gòu)的離散性

數(shù)據(jù)結(jié)構(gòu)是對數(shù)據(jù)元素與數(shù)據(jù)元素的結(jié)構(gòu)關(guān)系進行研究。數(shù)據(jù)結(jié)構(gòu)一般按元素關(guān)系的特性分為網(wǎng)狀、樹形、線性和集合四種基本結(jié)構(gòu)（見圖1），表明數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素具有離散性[5]。

圖1 數(shù)據(jù)結(jié)構(gòu)基本類型

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

另外，在計算機中，通過應(yīng)用離散數(shù)學(xué)的一些理論知識，解決了一些高難度的問題或?qū)崿F(xiàn)了解決方法的優(yōu)化，比如Huffman樹，其常用來實現(xiàn)壓縮解碼。

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

3 計算機中的離散性問題

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

3.1 二進制

3.2 二進制的離散性

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

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

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

總之，在計算機中，計算機處理問題因二進制的運用而表現(xiàn)出離散性特征，且前文談及的算法設(shè)計、數(shù)據(jù)結(jié)構(gòu)皆可利用二進制來進行離散性解釋。

4 結(jié)語

自人類進入21世紀(jì)以來，計算機科學(xué)實現(xiàn)了飛速發(fā)展，且其實際需求量與日俱增，從而激發(fā)了相關(guān)領(lǐng)域?qū)τ嬎銠C離散性的重視。在本文，筆者主要探討了如何利用離散數(shù)學(xué)來解決計算機的離散性問題。首先，介紹了計算機科學(xué)中算法設(shè)計的常用方法，即遞推法和遞歸法，并舉例探討了兩種方法的離散性體現(xiàn)；其次，介紹了計算機科學(xué)中的數(shù)據(jù)結(jié)構(gòu)與其離散性體現(xiàn)；最后，提出了計算機離散性問題以二進制的運用最為關(guān)鍵。

總之，為了適應(yīng)計算機科學(xué)深入發(fā)展的需要，要求深化對計算機科學(xué)中算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)的離散性問題的研究。

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

[2]向裕良，彭佳紅. 關(guān)于計算機科學(xué)中數(shù)據(jù)結(jié)構(gòu)算法探究[J]. 計算機光盤軟件與應(yīng)用，2013（19）：154-155.

[3]朱雅莉，李肯立. DNA計算機中堆棧數(shù)據(jù)結(jié)構(gòu)的設(shè)計[J]. 計算機工程與科學(xué)，2008（4）：121-123，127.

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

[5]肖文磊，劉亞醉，Oleksandr Zavalnyi，等.T-SPLINE開源內(nèi)核的三層數(shù)據(jù)結(jié)構(gòu)及算法原理[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報，2017（11）：2023-2036.

[6]趙景昌，高菲，劉光偉，等. 基于散列函數(shù)與半邊數(shù)據(jù)結(jié)構(gòu)的TIN拓?fù)渲貥?gòu)算法[J]. 計算機應(yīng)用研究，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