攜提客

運算思維(二)

演算法

Computer Algorithm

資工系丁德榮(指導教授是曾憲雄)

• 什麼是Algorithm ?

日常生活中，做事的方法，有固定的rule，有限的步驟，明確的定義，很有效率地解決一個問題。有沒有更有效率的方法？（詳見第八章）

Finiteness（有限個steps）
Definiteness（每一個step做的事確定）
Effectiveness（不只確定還要足夠的快能做完）

有input/output (O.S.永不terminate只能稱是computational procedure)

• Algorithm is everywhere

李家同是演算屆的泰斗，

資源有限下，充分利用資源，做最好的排程，實施方式可以是軟體、硬體或韌體

任何一領域都要用Algorithm去解決該領域所發生的問題

線上課程請務必看到chpter1~7

交作業可用任何程式語言，需有source code +執行結果的截圖

NP-complete problem

n：需要2的n次方時間

找近似最佳解（Approximating）

旅行推銷員問題(Traveling Salesman Problem，TSP)：最短路徑

TSP  http://www.math.uwaterloo.ca/tsp/index.html

平面圖著色定理：相鄰國家的顏色必不相同

四色定理：在1975年，數學家利用三台當時最先進的大型電腦，總共花了一千兩百小時的計算，分析驗證了1482種基本圖之後，終於證明成功，而使『四色猜想』正式成為『四色定理』！

---------------------------------------------------

QuickSort

Divide approach & recursive algorithm

------------------------------------------------

時間複雜度Time complexity classes

O(1) < O(log n) < O(n) <  O(n log n) <  O(n2)<  O(n3)< O(2n)<  O(n!) <  O(nn)

指數Exponential algorithm: O(2n)
多項式polynomial algorithm: e.g. O(n2), O(nlogn), …

0/1 Knapsack problem 0/1背包問題，限重15kg，怎麼偷最划算

Partition problem：分財產的問題

Art gallery problem：畫廊設監視器或警衛的問題

Minimum spanning tree

Convex hull凸多邊形

One-center problem

Lower Bound下界

Knockout sort 淘汰排序法：用空間換取時間

Heap Sort 堆積排序法

-----------------------------------------

Matrix multiplication 短陣相乘

Let A, B and C be n * n matrices

requires O(n3) time

Strassen’s matrix multiplication

原本要乘8次，改良後為乘7次 ,requires  O(n^2.81) time