序言｜Preface

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

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

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

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

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

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

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

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

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

陸　宏

2018年10月