高塔

?

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

高塔

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

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

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

引言

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

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

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

1.1 遞推法

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

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

1.2 遞歸法

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

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

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

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

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

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

數(shù)據(jù)結(jié)構(gòu)是對(duì)數(shù)據(jù)元素與數(shù)據(jù)元素的結(jié)構(gòu)關(guān)系進(jì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)均由一些獨(dú)立存在的數(shù)據(jù)元素組成，表明數(shù)據(jù)元素與數(shù)據(jù)元素的關(guān)系具有離散性和不連續(xù)性。離散數(shù)學(xué)是一種未涉及連續(xù)變化量的數(shù)學(xué)，主要用于研究以離散空間為基礎(chǔ)的數(shù)學(xué)結(jié)構(gòu)。對(duì)于數(shù)據(jù)結(jié)構(gòu)，離散數(shù)學(xué)與其存在非常緊密的關(guān)系，比如圖論，其研究了數(shù)據(jù)元素與數(shù)據(jù)元素的復(fù)雜關(guān)系。

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

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

3 計(jì)算機(jī)中的離散性問題

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

3.1 二進(jìn)制

3.2 二進(jìn)制的離散性

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

圖2 計(jì)算機(jī)離散化處理音頻信息

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

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

4 結(jié)語

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

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

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

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

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

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

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

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