可計(jì)算性問題

1、可計(jì)算性問題Tel: 31984767Email: 1計(jì)算復(fù)雜度假設(shè)有N個數(shù)據(jù)形成的一個鏈表。查找x是否在此列表中，采取順序比較方式。如果x在此列表中，且位置處于i,則需要比較i次。則平均比較次數(shù)為如果x不在此列表中，則需要比較N次。因此該查找算法的平均查找復(fù)雜度為(N+1)/2，最大復(fù)雜度為N2大O分析為了簡化數(shù)量級的分析，往往采用大O分析，選取最重要的部分，即使用隨著問題的大小增長得最快的項(xiàng)表示計(jì)算時間（復(fù)雜度）。例如f(N)=N4+100N2+10N+50, O(f(N)=O(N4)f(n)=(N+1)/2, O(f(n)=O(N)3常見的數(shù)量級4可滿足性問題對于有N個變量的布爾表達(dá)式（

2、僅僅包含AND， OR，NOT操作），可否存在一組變量使得該布爾表達(dá)式的值為15可計(jì)算問題的淵源1928年德國著名數(shù)學(xué)家希爾伯特(Hilbert)提出一個問題：可否有一個算法能對所有的數(shù)學(xué)原理自動給予證明1931年，奧地利數(shù)學(xué)家哥德爾證明了：對于一個相容的形式系統(tǒng)，存在一個算術(shù)命題，它在該系統(tǒng)中可以既未被證明，也未被證否。6圖靈機(jī)用準(zhǔn)確的數(shù)學(xué)形式來描述什么是“計(jì)算”圖靈機(jī)包含了一條無限長的紙帶和一個控制器?？刂破骺梢裕簭募垘献x出一個符號；向紙帶寫入一個符號；使帶子可以向左邊移動一個位置，或向右移動一個位置停機(jī)Church-Turing理論：任何能直觀計(jì)算的問題都內(nèi)被圖靈機(jī)計(jì)算。如果證明了某個

3、問題使用圖靈機(jī)是不可解決的，那么這個問題就是不可解決的。7停機(jī)定理給定任意一個圖靈機(jī)程序P和任意一組輸入數(shù)據(jù)I，不存在一個圖靈機(jī)程序，它能在有限多步后停機(jī)，并告訴我們P是否會結(jié)束輸入數(shù)據(jù)I的處理。8P和NP問題P (Polynomially)類問題：算法能在多項(xiàng)式時間內(nèi)完成的問題。NP (Nondeterministic Polynomially)問題：可以用多項(xiàng)式時間來驗(yàn)證一個解是否正確。已經(jīng)可以證明：需要證明：PNP，或者P是NP的一個真子集9NP完全問題(NP-Complete Problems)NP問題中有一組問題，如果其中有一個問題具有多項(xiàng)式的算法可以完成，則這一組問題都可以使用多項(xiàng)

4、式時間完成。NP完全問題的例子：可滿足問題；貨擔(dān)郎問題：在一個圖中，可否找到一個路徑滿足：所有的節(jié)點(diǎn)經(jīng)過且僅經(jīng)過一次，而且最后可以回到起點(diǎn)；裝箱問題：有有限多個容量為1的箱子，以及N個貨物（每個貨物的重量均小于1），需要最少的箱子把所有的N個貨物完全裝完。背包問題：背包的容量為C，有N個物體，體積分別為s1,sn以及價值分別為p1,pn，尋找一個最大價值的裝背包的方案。10計(jì)算復(fù)雜度假設(shè)有N個數(shù)據(jù)形成的一個鏈表。查找x是否在此列表中，采取順序比較方式。如果x在此列表中，且位置處于i,則需要比較i次。則平均比較次數(shù)為如果x不在此列表中，則需要比較N次。因此該查找算法的平均查找復(fù)雜度為(N+1)/

5、2，最大復(fù)雜度為N11大O分析為了簡化數(shù)量級的分析，往往采用大O分析，選取最重要的部分，即使用隨著問題的大小增長得最快的項(xiàng)表示計(jì)算時間（復(fù)雜度）。例如f(N)=N4+100N2+10N+50, O(f(N)=O(N4)f(n)=(N+1)/2, O(f(n)=O(N)12常見的數(shù)量級13圖靈機(jī)用準(zhǔn)確的數(shù)學(xué)形式來描述什么是“計(jì)算”圖靈機(jī)包含了一條無限長的紙帶和一個控制器。控制器可以：從紙帶上讀出一個符號；向紙帶寫入一個符號；使帶子可以向左邊移動一個位置，或向右移動一個位置停機(jī)Church-Turing理論：任何能直觀計(jì)算的問題都內(nèi)被圖靈機(jī)計(jì)算。如果證明了某個問題使用圖靈機(jī)是不可解決的，那么這個問題就是不可解決的。14P和NP問題P (Polynomially)類問題：算法能在多項(xiàng)式時間內(nèi)完成的問題。NP (Nondeterministic Polynomially)問題：可以用多項(xiàng)式時間來驗(yàn)證一個解是否正