序言｜Preface

本教材的編寫基于在南京大學(xué)的教學(xué)經(jīng)驗積累.2002年起由南京大學(xué)數(shù)學(xué)系面向全校開設(shè)本課程，同時這也是信息與計算科學(xué)專業(yè)、應(yīng)用數(shù)學(xué)專業(yè)基礎(chǔ)課程.我們知道當(dāng)前世界是一個信息大爆發(fā)的時代，我們需要每天在生活中、工作中恰當(dāng)?shù)靥幚怼⑦\用各種各樣的信息.本書從獲取信息、編碼、計算的角度出發(fā)，力圖讓包括數(shù)學(xué)系學(xué)生在內(nèi)的各專業(yè)學(xué)生對信息的方方面面做一個全局性的認識和了解，盡可能讓學(xué)生認識到信息的每個環(huán)節(jié)其實質(zhì)都與編碼有關(guān)，在信息傳輸之前要先將信息進行編碼，即要了解或掌握任一個事物，我們必須找到該事物的種種特征，把握其種種信息，因此我們建立模型，總結(jié)其信息，將可計算的信息編入數(shù)學(xué)公式中.信息傳輸時也是如此.編碼必定是可計算的，可計算的必定能在機器上計算，這就要有算法.所以這是一本介紹信息、算法和編碼的書，講述如何建立模型來研究、挖掘信息，如何編碼、如何找到算法.不同于常見的信息論教材，我們從數(shù)理邏輯、可計算分析、算法信息三門課程入手，循序漸進地把數(shù)學(xué)中處理信息的豐富思想揭示出來.數(shù)理邏輯是數(shù)學(xué)的基礎(chǔ).信息與數(shù)理邏輯，這兩者間表面上看似乎毫無聯(lián)系，但它們均屬于信息科學(xué)，我們通過對數(shù)理邏輯、可計算分析、算法信息的研究，試圖闡述信息的傳遞和編碼的實質(zhì)，講述如何進行信息的傳遞和編碼，如何計算，從而為傳統(tǒng)信息論的研究，提供更多的數(shù)學(xué)工具和方法.

我們還講解了傳統(tǒng)的關(guān)于通信的香農(nóng)信息論.在這部分內(nèi)容的講解過程中，我們嘗試用數(shù)學(xué)思想、信息思想進行解讀.而常見的信息論教材，要么數(shù)學(xué)內(nèi)容對于數(shù)學(xué)系學(xué)生來講比較單薄，要么物理背景比較強，所以不太適合數(shù)學(xué)系學(xué)生.因此為了適應(yīng)信息科學(xué)發(fā)展的需要，本書側(cè)重于講授信息、算法和編碼的理論方法，講授信息處理的思想，力圖形象直觀，我們會在講解中根據(jù)實際需要和專業(yè)背景對一些重要的概念和定理等做一些必要的解讀注釋.

本書共分四個部分.第一部分我們處理離散無窮函數(shù)的信息、算法和編碼問題，講述數(shù)理邏輯這門學(xué)科中的可計算性理論，這部分主要處理的是從自然數(shù)集?到?上的離散函數(shù).從第一章到第四章，我們介紹什么樣的離散函數(shù)f：?→?是計算機可計算的，什么是算法，如何將算法編碼，這部分主要講述的著名數(shù)理邏輯學(xué)大家G?del的編碼思想，使得每個可計算的函數(shù)都對應(yīng)一個編碼，從而建立了函數(shù)、編碼、圖靈機（或URM機器等等等價計算機模型）三者間的等價關(guān)系.注意這并不是將函數(shù)的每個函數(shù)值的信息進行傳遞，而是將函數(shù)的編碼進行傳遞，從而實現(xiàn)其可計算性.在第四章及第五章，我們講解丘奇論題，簡單介紹了G?del不完備性定理、P與NP及部分復(fù)雜性知識.我們著重介紹了何為“好”的編碼，給出了評估標準，這不僅適用于計算機領(lǐng)域也可適用于通信領(lǐng)域，既有理論價值又有實用價值.在第六章，我們講述了在計算機世界中還存在很多不可計算的函數(shù)以及如何判定不可計算的方法.在第七章，我們講解什么是遞歸集（或可計算集），實際上在傳統(tǒng)信息論中能編碼的都是可計算集.在第八章，我們講解帶外部信息元（oracle）的圖靈機，講述了規(guī)約方法，這是衡量信息強弱、計算難度的最主要的利器（由此可以發(fā)展出可計算性理論中最難的一門學(xué)科——度論）.

第二部分我們處理連續(xù)函數(shù)的信息、算法和編碼問題，講述了可計算分析理論——把可計算性理論應(yīng)用于數(shù)學(xué)分析的一門新興學(xué)科，講述如何在計算機上計算非離散的實函數(shù)f：?→?.要實現(xiàn)無窮實數(shù)之間的計算，我們不僅要引入2-圖靈機，還要引入名、表示等概念，并建立命名系統(tǒng)上的可計算體系.這不僅需要編碼，還要選擇適當(dāng)?shù)谋硎痉椒ǎ詫崿F(xiàn)可計算函數(shù)在圖靈機上的可計算性.這是一門比較煩瑣的復(fù)雜的但又很實用的處理連續(xù)信息的編碼理論，我們做了大量的解讀工作，以方便讀者閱讀并迅速理解名、表示體現(xiàn)了函數(shù)的計算程序的信息、編碼，也蘊涵了每個輸入的信息、編碼一方面要挖掘出信息，另一方面要將信息進行合適的編碼，兩者缺一不可，關(guān)鍵在于如何在計算機上協(xié)調(diào)好并進行“好”的計算.

第三部分，我們從算法的角度來處理離散的有窮函數(shù)的信息、算法和編碼問題，講述算法信息熵是如何定義的.不同于前面處理離散函數(shù)、連續(xù)函數(shù)的兩個部分，這里考察有窮字符串是如何處理、計算信息的，介紹了Kolmogorov復(fù)雜性、前綴復(fù)雜性的定義.最后還講解了算法熵是不可計算的.

第四部分我們處理離散的有窮函數(shù)的信息、算法和編碼問題在通信領(lǐng)域的具體應(yīng)用，講述的是傳統(tǒng)的香農(nóng)信息論.它共分十章，分別介紹信息論的基本概念——各種熵、互信息、信道容量等的定義，給出了信源編碼的方法，介紹了信道編碼的原理，講解了多種信道編碼——分組碼、循環(huán)碼、卷積碼、漢明碼、BCH碼……及這些編碼所需的相關(guān)的代數(shù)知識.關(guān)于有限域知識，我們幾乎對每個定義、每個定理都做了解讀，主要是從信息的角度去挖掘數(shù)學(xué)概念背后隱藏的本質(zhì)的結(jié)構(gòu)信息.希望部分讀者不再懼怕數(shù)學(xué)，能夠明白數(shù)學(xué)其實是有操作性的，每個數(shù)學(xué)概念、定理后面都有一條主線，抓住它，您就會喜歡上數(shù)學(xué).

這部教材在醞釀過程中，得到多位老師的幫助和指點，在此我向丁德成老師、喻良老師等等表示衷心感謝.這部教材的出版更離不開系領(lǐng)導(dǎo)班子在課程設(shè)置和出版資金上的大力支持，尤其離不開朱曉勝老師、鄧衛(wèi)兵老師的鼎力支持，在此表示衷心的感謝.編者特別感謝南京大學(xué)出版社楊博、王南雁等編輯和工作人員對本書出版所付出的辛勤勞動.

本教材參考了不少中外著名圖書，例如[NC][KW]［fj］[zxl]……在此一并謝過.另外參考文獻均按照作者名、年代、著作名或文章名、出版社或雜志社、文章頁碼設(shè)置特定的縮略詞，以方便讀者查找.

本書力圖能建立信息、算法、編碼三者間的聯(lián)系并加以闡述，本人的愿望就是希望本書能起一個拋磚引玉的作用.但本人水平有限，還望各位專家、讀者批評指正.

陸　宏

2018年10月