計算機問題求解算法在計算機科學中的地位課件

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

2、s below the number of permutations of the given points are not known!這年頭，我們當然使用計算機假設(shè)我們使用IBM Roadrunner Cluster (美國能源部）129,600個處理器，每秒執(zhí)行1457萬億次算數(shù)運算價值1億3千3百萬美元2009年高性能計算機500強第一名解決33city-TSP耐心等待請勿關(guān)機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.問題 實例TSP 挑戰(zhàn)計算思維能力的極限問題3:為什么我們希望了解計算的“代價”，而“代價”的關(guān)鍵就是是什么？問題4：為什么我們不能用一個數(shù)值表示算法的“代價”？一個例子 找序列中的最大元素如果我們關(guān)心A的值：顯然：與實際輸入有關(guān)；最小值：0；最大值：n-1;平均值：?“最壞情況”也不一定容易看出來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問題7：Big-O 的“Robustness”是什么意思？問題8：為什么有時候Big-O可能誤導人？問題9：你能說出用Linear Search算法搜索一個未排序的序列的代價嗎？它是否是“最優(yōu)”的，為什么？順便問一下：書上講的優(yōu)化方法如何實現(xiàn)？問題10：什么是“Algorithmic Gap”?現(xiàn)在說說“平均”假設(shè)要在n個元素的序列中搜索K；假設(shè)K確實在該序列中的概率是q，則不在其中的概率是1-q。如果在其中，假設(shè)K出現(xiàn)在每一

5、個位置上的概率是一樣的。對于特定的位置i (0in-1), 比較次數(shù)為i+1。因此，平均代價是： 問題11：從Linear Search到Binary Search, 收益是什么？需要付出什么代價？考你一下：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問題12：你是否還記得有什么非排序算法，其主要代價就是排序的呢？Cons