計(jì)算機(jī)問(wèn)題求解算法在計(jì)算機(jī)科學(xué)中的地位課件

1、計(jì)算機(jī)問(wèn)題求解 論題1-14 - 算法的效率2018年12月18日Part I算法的時(shí)間代價(jià)問(wèn)題1:Hanoi Tower的遞歸算法無(wú)疑是正確的, 但你認(rèn)為它是“可接受的”嗎？需要移動(dòng)多少次圓盤(pán)？相應(yīng)的遞歸方程是：T(n) = 2T(n-1)+1即：T(n) = 2n-1當(dāng)n=64 (據(jù)說(shuō)原始問(wèn)題是這樣的)：其數(shù)量級(jí)大約是 1019，即1000億億！如果每秒移動(dòng)1億個(gè)盤(pán)子，需要大約3200年！問(wèn)題2：現(xiàn)在你是否理解對(duì)一個(gè)問(wèn)題找到一個(gè)正確的算法并不等同于我們“能”解這個(gè)問(wèn)題了呢？TSP: (也許是)世界上最具挑戰(zhàn)性的（算法）問(wèn)題。Rules that give a number of trial

2、s below the number of permutations of the given points are not known!這年頭，我們當(dāng)然使用計(jì)算機(jī)假設(shè)我們使用IBM Roadrunner Cluster (美國(guó)能源部）129,600個(gè)處理器，每秒執(zhí)行1457萬(wàn)億次算數(shù)運(yùn)算價(jià)值1億3千3百萬(wàn)美元2009年高性能計(jì)算機(jī)500強(qiáng)第一名解決33city-TSP耐心等待請(qǐng)勿關(guān)機(jī)We would then need roughly 28 trillion years to solve the 33-city TSP on the Roadrunner, an uncomfortable

3、amount of time, given that the universe is estimated to be only 14 billion years old.問(wèn)題 實(shí)例TSP 挑戰(zhàn)計(jì)算思維能力的極限問(wèn)題3:為什么我們希望了解計(jì)算的“代價(jià)”，而“代價(jià)”的關(guān)鍵就是是什么？問(wèn)題4：為什么我們不能用一個(gè)數(shù)值表示算法的“代價(jià)”？一個(gè)例子 找序列中的最大元素如果我們關(guān)心A的值：顯然：與實(shí)際輸入有關(guān)；最小值：0；最大值：n-1;平均值：?“最壞情況”也不一定容易看出來(lái)For any integer k1, if mn1 and n0By the way:The power of n grows

4、more slowly than any exponential function with base greater than 1nk o(cn) for any c1問(wèn)題7：Big-O 的“Robustness”是什么意思？問(wèn)題8：為什么有時(shí)候Big-O可能誤導(dǎo)人？問(wèn)題9：你能說(shuō)出用Linear Search算法搜索一個(gè)未排序的序列的代價(jià)嗎？它是否是“最優(yōu)”的，為什么？順便問(wèn)一下：書(shū)上講的優(yōu)化方法如何實(shí)現(xiàn)？問(wèn)題10：什么是“Algorithmic Gap”?現(xiàn)在說(shuō)說(shuō)“平均”假設(shè)要在n個(gè)元素的序列中搜索K；假設(shè)K確實(shí)在該序列中的概率是q，則不在其中的概率是1-q。如果在其中，假設(shè)K出現(xiàn)在每一

5、個(gè)位置上的概率是一樣的。對(duì)于特定的位置i (0in-1), 比較次數(shù)為i+1。因此，平均代價(jià)是： 問(wèn)題11：從Linear Search到Binary Search, 收益是什么？需要付出什么代價(jià)？考你一下：Let A be an array of integers and S a target integer. Design an efficient algorithm for determining if there exist a pair of indices i,j such that Ai+Aj=S.如果這里“efficient”是指“線性的”，你的答案滿足要求嗎？a1a2aiiHash(ai)ajIf ai = S-ajHash(S-aj)ASleeping Tigers問(wèn)題12：你是否還記得有什么非排序算法，其主要代價(jià)就是排序的呢？Cons