CMU 15251 | 理論計算機科學:介紹

2021-02-20 計算與經濟學
15251 理論計算機科學先修

首先，你應該學習了計算機科學的入門課程，包括編程和算法思維，比如 15122/15150。

其次，你應該有抽象的推理經驗，知道如何書寫證明，比如 15151。

資源

這門課沒有教材，如果想參考涵蓋部分課程內容的書籍，可以使用

Michael Sipser，計算理論導引（Introduction to the Theory of Computation）Cristopher Moore & Stephan Mertens，計算本質（The Nature of Computation）Boaz Barak，理論計算機科學概論（Introduction to Theoretical Computer Science）Scott Aaronson，從德謨克裡特到量子計算（Quantum Computing Since Democritus）計算機科學

這門課的主題就是

Computer Science is no more about computers than astronomy is about telescopes.

計算機科學與計算機無關，正如天文學與望遠鏡無關。

這句話常被誤傳為是 Dijkstra 說的，但其實是 Michael Fellows 說的。

計算機科學是研究計算的科學

雖然我們已經使用了幾千年算法了，但是算法的數學化是在 20 世紀才完成的事情。

希爾伯特提出了兩個問題

這兩個問題的答案都是 NO

1936，丘奇發明了 Lambda 演算，聲稱這應該是算法的定義1936，哥德爾和 Emil Leon Post 指出丘奇的聲稱是不合理的1936，圖靈描述了一個用於計算的新模型，現在被稱作圖靈機（TM）哥德爾，Kleene，丘奇後來說，圖靈解決了這個問題，算法被定義了1937，圖靈證明了圖靈機和 Lambda 演算是等價的丘奇-圖靈假設：「可計算」指可以被圖靈機的一個函數計算1970，Matiyasevich-Robinson-Davis-Putnam 證明了，沒有算法能解決希爾伯特第十問題

理論計算機科學的主要問題

內容 note#titlechap#1字符串，語言，編碼，問題12DFA23圖靈機，可判定性34不可判定性55時間複雜度66圖 187圖 298布爾電路，NP 和 NP-完全10，129近似算法1310隨機算法 11411隨機算法 2，模算術1512群，域和多項式
13量子計算
14密碼學和交互證明
15哥德爾不完備性定理
Note1 字符串，語言，編碼，問題字符串

計算是對數據/信息的操作，我們在數學上如何表示數據？

在英語裡，我們用 apple, car, happy, three 等單詞來表示數據，我們用一個字母表

我們把

字符串也可以這樣定義

我們把

語言

定義

我們定義

編碼

如果

例如，

問題

一個問題（計算問題）是一個函數

其中

在 TCS 中，

注意：問題的定義是

判定問題是這樣的問題

很多計算問題都可以轉換成判定問題，比如輸入一個自然數 N，輸出它的質因數分解，就可以轉換成輸入兩個自然數 N 和 k，輸出 N 是否存在 1 到 k 之間的因數。

判定問題和語言之間存在一一對應關係，如下圖，被


這門課會更關注語言，討論這些問題

Note2 DFA

一個決定性有窮狀態機

如果

為了方便，我們可以直接寫一個函數

所有被

相反，對於一個語言

那麼自然就有兩個問題：

所有語言都是 Regular 的嗎？

不是的。

例如

就一定不是 regular 的。

用反證法證明

證明一個語言不是 regular 的一般思路就是這樣的

找一個字符串

並且 1 元的語言也可以是非 regular 的

我們知道一個語言是和一個判別問題對應的，存在非 regular 的語言其實就告訴我們，DFA 並不能解決所有的判別問題。

怎麼判斷一個語言是不是 regular 的？

那麼我們就要討論一些 regular 的語言的性質。

首先，如果

並且取其逆反命題，如果

我們還知道，如果

同理我們還知道

基於此我們可以定義 regular 表達式

Note3 圖靈機

一個圖靈機是一個 7 元組

對一個語言

那我們說

對一個函數

可判定性

通過編碼，我們可以把一個圖靈機

我們可以定義四個新的語言

可以證明這四個語言都是可判定的。

不可判定性

任何一個語言

必然不是，因為所有的

而每一個圖靈機都是用有限長的字符串編碼的，所以所有圖靈機的集合是一個可數集（和

所以一定存在不可判定的語言。

並且大部分語言都是不可判定的，比如 。

圖靈停機問題

圖靈在 1936 年證明了這個語言是不可判定的

我們用反證法，假設存在一個圖靈機

也就是說我們構造了一個圖靈機

這就構造了矛盾：

Reduction

我們可以用停機問題的不可判定性證明其他語言的不可判定性，比如

如果存在一個圖靈機

如果沒有接受，就把

而停機問題是不可判定的，所以

我們用

我們實際上證明了

More Reductions

再介紹幾個語言

我們有

同理我們還有

最後，我們給出

More More Reductions

甚至我們可以說 的難度是相等的。

對於 t = 1 to Infinity，對長度至多為 t 的字符串執行

另外，

另外，不可判定語言的難度層次（就像上面說的一樣）是無窮深的，儘管語言的集合是可數的。

其他不可判定問題

元胞自動機（CA）是否會循環也是一個不可判定問題。

Post's correspondence problem 也是一個不可判定問題，因為它比 ACCEPT 難。

Wang Tiles 也是一個不可判定問題。

給定一個代數規則，然後判斷從一個數能否到達另一個數，例如著名的 3n+1 問題，也是不可判定的（Börger, 1989）。

給定一個有理數集合，判斷使用加減乘除、正弦、自然指數、絕對值、

給定兩個 21*21 的矩陣，判斷它們的乘積有沒有可能是 0 矩陣，也是不可判定的（Halava, Harju, Hirvensalo, 2007）。

希爾伯特第十問題，給定任意多項式的係數，判斷是否存在整數根，也是不可判定的（Matiyasevich, Robinson, Davis, Putnam, 1970）。

但是否存在實數根是可判定的（Tarski, 1951），尚不確定是否存在有理數根是不是可判定的。

Note4 時間複雜度

下面我們討論回文問題。

1993 年，喜劇演員 Demetri Martin 在耶魯上了一門數學課《分形幾何》，他的期末項目是，寫了一首 225 個詞的迴文詩。

迴文詩和分形有什麼關係，不知道，他們是個文科學校。

這首詩的全文：

Dammit I'm mad Evil is a deed as I live. God, am I reviled? I rise, my bed on a sun, I melt. To be not one man emanating is sad. I piss. Alas it is so late. Who stops to help? Man, it is hot. I'm in it. I tell. I am not a devil. I level "Mad Dog". Ah, say burning is as a deified gulp in my halo of a mired rum tin. I erase many men. Oh, to be man, a sin. Is evil in a clam? In a trap? No. It is open. On it I was stuck. Rats peed on hope. Elsewhere dips a web. Be still if I fill its ebb. Ew, a spider ... eh? We sleep. Oh no! Deep, stark cuts saw it in one position. Part animal, can I live? Sin is a name. Both, one ... my names are in it. Murder? I'm a fool. A hymn I plug, Deified as a sign in ruby ash - a goddam level I lived at. On mail let it in. I'm it. Oh, sit in ample hot spots. Oh, wet! A loss it is alas (sip). I'd assign it a name. Name not one bottle minus an ode by me: "Sir, I deliver. I'm a dog." Evil is a deed as I live. Dammit I'm mad.

但這其實不算什麼，在 1986 年，Lawrence Levine 寫了一部回文的小說，大約 10 萬詞。

今天我們的任務就是證明：回文問題的複雜度是

首先我們知道這個問題是可解的，因為對語言


這個算法是

但是如果我們用另一個模型

def TwoFingersPalindromeTest(S,n):
    # ACCEPT iff string S[1]...S[n] is a palindrome
    lo = 1
    hi = n
    while (lo<hi):
        if S[lo] != S[hi]:
            return False
        lo = lo + 1
        hi = hi - 1
    return True
這個算法又是 
但是 S[lo] != S[hi]，比較兩個在內存上距離很遠的數，真的可以用 
先不管這件事，這個算法會不會有比 
我們在小學學了 
再比如是否存在哈密頓迴路，暴力算法是 
再比如是否存在歐拉迴路，歐拉定理指出解決這個問題的算法一定是 
現在回過頭來看計算模型的問題
TwoFingersPalindromeTest 算法說回文問題是 
到底哪個更合理呢？
圖靈機模型是不合理的，因為圖靈機沒有 RAM，但是現實裡的計算機都有而 x==x[::-1] 也是不合理的，其實它的運行時間和 x 是有關的，就像 
IsPalindrome(x)             // x in Σ*
    lo = 1
    hi = n                  // n is the length of x
    loop while (lo<hi)      // basic flow-control things
        if S[lo] != S[hi]   // access any memory cell in 1 step
            return False
        lo = lo + 1         // in 1 step
        hi = hi - 1
    end loop
    return True
我們真的可以用 1 步完成加一運算嗎？
當然可以，每一個 x86 處理器的計算機都有一個把兩個寄存器加起來的指令但是同時，如果一個數字有 10^6 位，它就不能保存到一個 64 位的寄存器裡了所以我們把整數分成兩類，小整數可以用 1 步完成加一，但是大整數不可以大整數在計算機中以字符串的形式存儲，大整數加法應該是一個字符串算法加法
Add(x,y)
    /* Assume x,y encoded as base-10 strings with 
       array indices 0...n-1. We freely convert
       between digit characters and BoundedInts. */
    carry = 0
    for i from 0 to n-1 do
        columnSum = x[i] + y[i] + carry
        z[i] = columnSum mod 10
        carry = (columnSum-z[i]) / 10
    z[n] = carry
    return z
這個算法是 
乘法
對於乘法，我們要做兩步，先按位乘，再把結果相加。
按位乘是 
for i = 0...n-1
 for j = 0...n-1
  table[i][j] = x[j]*y[i]
把結果相加，我們有 n 列，每列的加法都是 Θ(n) 的，所以一共也是 Θ(n^2) 的。
所以乘法是 Θ(n^2) 的。
但是乘法的 intrinsic 複雜度是平方的嗎？有沒有可能存在線性的乘法算法？
Andrey Kolmogorov 在 1960 年猜想乘法的複雜度就是平方的。
如果你用 Python 做實驗的話，會發現 Python 的乘法是 
回過頭來看乘法的計算過程
6421 * 5213
= (6*10^3 + 4*10^2 + 2*10^1 + 1*10^0) * (5*10^3 + 2*10^2 + 1*10^1 + 3*10^0)
= (6*3)*10^(3+0) + (4*3)*10^(2+0) + (2*3)*10^(1+0) + (1*3)*10^(0+0)
+ (6*1)*10^(3+1) + (4*1)*10^(2+1) + (2*1)*10^(1+1) + (1*1)*10^(0+1)
+ (6*2)*10^(3+2) + (4*2)*10^(2+2) + (2*2)*10^(1+2) + (1*2)*10^(0+2)
+ (6*5)*10^(3+3) + (4*5)*10^(2+3) + (2*5)*10^(1+3) + (1*5)*10^(0+3)
= ...
Anatoly Karatsuba 在 1960 年提出用分治來計算
6421 * 5213
= (64*10^2 + 21) * (52*10^2 + 13)
= (64*52)*10^4 + (64*13 + 21*52)*10^3 + (21*13)
= ...
但是如果分成四份遞歸，計算還是 n^2 的，Karatsuba 提出這樣做
(64 - 21)*(52 - 13)
= 64*52 - 64*13 - 21*52 + 21*13
這樣我就把四份變成了三份，遞歸是
這個遞歸是 
Anatoly Karatsuba 是第一個把複雜度降低到 2 以下的，後來 Toom Cook 算法（1963）推廣了他的想法，後來 Arnold Schönhage 和 Volker Strassen 利用快速傅立葉變換發明了 
Schönhage 和 Strassen 的論文裡猜想，最好的算法應該是

相關焦點

  • CMU出品,計算機圖形學秋季課程已上線,B站同步字幕視頻
    有關計算機圖形學方面的課程 ciqian 也介紹過一些，如太極（Taichi）作者胡淵鳴於今年 6 月 1 日開設的線上課程《高級物理引擎實戰指南 2020》，這門 10 節的課程主要講授了基於物理的動畫的基礎和前沿知識。國外有關該領域的課程不在少數。
  • 計算機科學與技術專業介紹
    、表示、存儲、處理、控制等的理論、原理、方法和技術的學科。本專業學生主要學習和掌握計算機科學與技術專業領域的基本理論知識，接受從事計算機和嵌入式系統相關的研究與應用的專業訓練，具有研究、開發、應用和集成計算機系統與嵌入式系統的基本能力。二、專業學什麼1、自動化專業屬於工學門類、計算機類下面的專業，本科學制4年，畢業獲得工學學士學位。
  • 美國計算機科學專業學校介紹
    數據科學家和軟體工程師等計算機領域的工作在未來七年中增長潛力最大，同時，醫療保健等職業是另一個主要增長領域。今天就給大家介紹一些美國留學的計算機專業。Systems, and Software Engineering 程式語言、形式系統和軟體工程 　　Scientific Computing 科學計算 　　在申請要求上，對於先行課的要求是如果本科不是學CS的學生必須有充足的背景基礎：計算機編程、算法和資料庫結構、計算機組織和計算理論(相當於Illinois的計算機科學入門、資料庫結構、離散結構、計算機結構)。
  • 為什麼 Ray Kurzweil 的垃圾科學理論能夠騙人?
    既然原文作者和中文小編硬要和人工智慧扯上關係，我就只好幫大家科普一下Ray Kurzweil的其人其事，順便介紹一下為什麼這些人的垃圾科學(Junk Science)理論可以在美國和中國蠱惑人心。Ray Kurzweil是誰？
  • 攜Science封面，CMU大神Noam博士畢業，論文已公開
    機器之心對該論文的核心內容進行了簡要介紹，感興趣的讀者可以閱讀原論文。論文地址：http://www.cs.cmu.edu/~noamb/thesis.pdfSlides 地址：http://www.cs.cmu.edu/~noamb/thesis_slides.pdf
  • 攜Science封面,CMU大神Noam博士畢業,論文已公開
    機器之心對該論文的核心內容進行了簡要介紹，感興趣的讀者可以閱讀原論文。論文地址：http://www.cs.cmu.edu/~noamb/thesis.pdfSlides 地址：http://www.cs.cmu.edu/~noamb/thesis_slides.pdf博士論文簡介這篇博士論文詳述了大型對抗性不完美信息博弈中均衡計算的一系列進展。
  • 計算機科學、經濟學交叉的時代,不懂計算經濟學理論談何應用?| CCF...
    計算經濟學（Computational economics）就是這樣一門涉及計算機科學、經濟學、數學、博弈論、社會科學等領域的交叉學科。近年來，學術界在該領域裡取得了長足的進步，例如美國卡內基—梅隆大學教授西蒙提出有限理性理論，斯卡夫提出可計算一般均衡理論等，計算模型也在不斷發展，出現了人工神經網絡模型、ACE模型等。只有夯實理論基石，才能在應用中更加得心應手。
  • 朱平——江南大學——代數理論、理論計算機科學、生物計算等
    1962-09 所在院校： 江南大學       所在院系： 理學院 職稱： 教授       招生專業： 計算數學 研究領域： 代數理論
  • CMU大佬分享三類優質數據集:綜合、CV和NLP
    主要包括了綜合性數據集、CV計算機視覺數據集和NLP自然語言處理數據集。 PS：以前我們也分享過一些數據集的資源，感興趣的可以在公眾號歷史文章中搜索查看，數據集系列也會持續更新。 一、綜合性機器學習數據集 1.
  • 量子計算機科學與計算機交叉學科的原理是什麼
    至於分類，你可以把他們分為「信息科學」和「量子生物學」。量子信息科學與計算機科學交叉學科，囊括了計算機和信息科學。目前歸在計算機學院，但研究內容較計算機科學內容更加廣泛。量子科學包括量子通信。量子信息科學包括量子通信。量子計算機科學與計算機交叉學科。
  • 關注科技,關注首屆國際理論計算機聯合大會!
    理論計算機不僅是計算機科學的基礎，同時也是當前各門類學科發展的關鍵基礎之一。計算機技術的快速發展，使得「計算」一詞不僅從經典數學理論中獨立出來，也正在通過計算的視角促進其他學科的發展，形成了本世紀重要的學科交叉融合熱點。
  • 「我也要成為一名理論計算機科學家！」——訪南京大學教授尹一通
    您的研究方向是理論計算機科學，能否首先簡單介紹一下您的具體研究領域？尹一通：我非常榮幸獲得「CCF-IEEE CS青年科學家獎」這個重要的獎項，十分感謝本領域的前輩們對我的支持與認可。很榮幸接受CCCF的採訪。我的研究方向是理論計算機科學。
  • 美國熱門專業——計算機科學專業深度解析
    計算機科學專業是什麼？英文名稱是 Computer Science，簡稱CS。計算機科學簡單來說就是研究計算機系統、軟體設計，以及將相關理論進行領域應用的。如果你打算學習這個專業，那麼你將會學習很多抽象化的概念。同時，因為計算機溝通要求精確性，所以你還必須學會使用很多精確的程序語言。
  • 計算機科學與技術專業就業面面觀
    考生和家長眼中的計算機專業，實際往往包含高等教育計算機類的各個專業，如計算機科學與技術、軟體工程、網絡工程等。其中，最核心、最基礎的專業是計算機科學與技術。總體而言，計算機科學與技術專業強調硬體與軟體相結合、面向系統、側重應用。各高校在實際學科建設中各有特點。
  • 彭實戈獲得2020未來科學大獎「數學與計算機科學獎」
    中國青年報客戶端北京9月6日電（中青報·中青網記者原春琳）2020未來科學大獎今天在北京揭曉。山東大學教授彭實戈因為「在倒向隨機微分方程理論，非線性Feynman-Kac公式和非線性數學期望理論中的開創性貢獻」，而獲得「數學與計算機科學獎」。
  • 彭實戈獲得2020未來科學大獎「數學與計算機科學獎」
    中國青年報客戶端北京9月6日電（中青報·中青網記者原春琳）2020未來科學大獎今天在北京揭曉。山東大學教授彭實戈因為「在倒向隨機微分方程理論，非線性Feynman-Kac公式和非線性數學期望理論中的開創性貢獻」，而獲得「數學與計算機科學獎」。
  • 讓人「雲裡霧裡」的計算機科普——計算機科學普及的現狀與思考
    在新形勢下，弘揚科學精神，傳播科學方法以提升科學素養更是一個長期過程，這對研究人員產生了新的、對科普能力的要求，自然也提出了新問題：作為科研人員又該如何科普？對比物理知識科普，分析計算機科學普及的現狀，或許能引發一些思考。
  • US News全美人工智慧研究生院排名:CMU第一,MIT第二
    3月20日，US News發布2019美國最佳研究生院排名，本文重點介紹該排名的計算機科學部門，以及其中「人工智慧」這一分支的排名。新智元報導來源：US NewsUS News 的大學排行榜是全球最具影響力的大學排行榜之一，一直有著非常大的影響力。
  • AP計算機科學A&AP計算機原理,哪一個更適合?
    2016-2017學年新增的一門AP計算機原理，旨在鼓勵更多的學生學習計算機科學與STEM(科學、技術、工程、數學)相關知識，是以計算機原理和基礎知識為主，含編程方面的知識。報考要求：1.考生所在的AP學校必須獲得授權可以開設該課程；2.考生必須在AP學校學習過該課程。
  • 2020未來科學大獎周:2020數學與計算機科學獎獲獎者學術報告會
    鳳凰網科技訊 12月30日消息，彭實戈教授因在倒向隨機微分方程理論，非線性Feynman-Kac公式和非線性數學期望理論中的開創性貢獻，榮獲2020未來科學大獎-數學與計算機科學獎。由未來科學大獎聯合山東大學共同舉辦的「概率與概率的不確定性——2020未來科學大獎-數學與計算機科學獎獲獎者學術報告會」今日首播，山東大學校長樊麗明，未來科學大獎科學委員會-數學與計算機科學獎獎項委員會2020輪值主席、美國西北大學Pancoe講席教授夏志宏做開場致辭。