Teaching Assistants (TAs): 李俊賢 房子豪 林橋毅
Time: 週二 14:00~16:50
Place: 週二 工五館(E6) A207
TA Class: 週二 13:00~13:50 工五館(E6) A207
請大家先觀看之前的課程介紹影片: https://youtu.be/1muNkALTSr8
*請加選的同學慎思，因為本課程為資工系必修課，課程不及格比率為15%+-5%。修讀本課 程需要繳交midterm project、term project以及每週手寫作業6-10題，任選二題作答；每週線 上程式作業3題，至少完成一題；每週助教課程分組報告一小時，需上傳作業解題投影片。
*建議可以採用先看習題，然後再聽課或到課程影片中學會解決問題技術的方式學習，效果較佳!
EEClass: (CE3005B)
Scope:
- Designs and Analysis of Many Classical Algorithms
Introduction to Several Machine Learning/Deep Learning Algorithms (2019開始新增)
- Introduction to Gate-based Quantum Algorithms and Quantum
Annealing Algorithms (2021開始新增) for Midterm and Final Projects
- 期中考(分析與設計概念)(
25%25%)
- 期末考(分析與設計概念)(
30%25%) - 期中專題(
10%10%) - 期末專題(
10%10%) - 作業、程式設計作業、報告、課程參與度(
25%30%)
- My Book's Manuscript: (演算法精要：設計與分析) AlgBook(Ch1-8).zip (書籍即將出版，版權 所有，草稿僅供修課同學參考，請勿散播流出:)
- My Another Book: (輕鬆學量子程
式設計 -- 從量子位元到量子演算法)
- R.C.T. Lee et. al., Introduction to the Design and Analysis of Algorithms -- A Strategic Approach (2/e), McGraw Hill, 2005.
- Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction to Algorithms (3/e), MIT Press, 2009.
- 張元翔, 量子電腦與量子計算, 碁峰, 2020.
- 陳建宏(譯), 量子計算實戰, 碁峰, 2020.
- 林大貴, TensorFlow + Keras 深度學習人工智慧實務應用, 博碩文化, 2017.
- 齊藤康毅, Deep Learning -- 用Python進行深度學習的基礎理論實作, O'REILLY, (吳嘉芳
譯, 碁峰資訊出版), 2017.
- Algorithm Design: Foundations, Analysis, and Internet
Examples, Michael T. Goodrich, Roberto Tamassia, Wiley, 2002.
(有中譯本)
- Computer Algorithms, Ellis Horowitz et. al., Silicon Press, 2008.
- 中文Java程式設計 (第三版) SIM-908A , 江振瑞 著, 儒林出版社, 2006.
- 物件導向資料結構 — 使用Java語言, 江振瑞 著, 松崗圖書公司, 2005.
- Algorithms, S. Dasgupta, C. Papadimitriou and U. Vazirani,
McGraw Hill, 2008.
- Programming Challenges, Steven S. Skiena and Miguel Revilla, Elsevier, 2003.
- The Algorithm Design Manual, Steven S. Skiena, Elsevier.
2 安裝MinGW C++ Compiler (G++): http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download
3 安裝最新Python 3 Interpreter: https://www.anaconda.com/
4 安裝Jeep7(Java editor for every programmers v7.0) (下載: Jeep7Setup&SourceCode.exe) (防毒軟體會誤判為不安全軟體，但保證安全，請安心使用。)
5 設定路徑參數: 注意，這會因為你安裝上列不同軟體的不同版本而不同，也會因為你安裝的作業系統版本不同而不同。以下為針對Windows作業系統的設定:
選擇 [控制台][系統及安全性][系統][進階系統設定][環境變數]，找出[path]變數並按下[編輯]，並在其變數值末端加入以下內容:
;JDK安裝目 錄\bin;MinGW安裝目錄\ bin;Python安裝目錄;Jeep7安裝目錄
(例如: ;C:\Program Files\Java\jdk-9.0.4\bin;C:\MinGW\bin;C:\Users\yourname\Anaconda3;C:\Jeep7)
6 下載範例程式(Sample.c)(Sample.cpp)(Sample.java)(Sample.py)儲 存於C:\Jeep7目錄中，按下桌面Jeep7圖示執行Jeep7軟體，並使用 [開舊檔]選項載入範例程式進行[編譯][執行]。
- The
Universidad
de Valladolid (UVa) judge: http://online-judge.uva.es
Example: http://online-judge.uva.es/p/v100/10041.html (Vito's Family) (Vito.java) (Vito1.java) (Vito.cpp)
Exercise: http://online-judge.uva.es/p/v102/10258.html (Contest Scoreboard)
Exercise: http://online-judge.uva.es/p/v5/531.html (Compromise)
- (2/18)0. 演算法課程介紹 (AlgSmallTalk.pptx)
- (2/25)1. 認識演算法 -- 從食譜到高階程式語言: (Alg-Intro.pptx) (ACM-ICPC&EPC.ppt) .1 演算法名稱的由來
.2 什麼是演算法?
.3 演算法的例子
.4 如何表示演算法?
.5 如何實作演算法? (EuclidGCD.c)(EuclidGCD.cpp)(EucidCGDClass1.java)(EucidCGDClass.java)(EuclidGCD.py)
.6 演算法的正確性
Homework1: (For 2/25. Select two problems out of A, B, ..., and G and handwrite their solutions. Due day: before noon of next class on 3/4)
A. 使用虛擬碼(pseudocode)寫一個演算法，輸入一個整數n(n>2)並並判斷n是否為質數(prime)(Write an algorithm using the pseudo code to input an integer n and output (decide) if n is a prime.)
B. 使用虛擬碼(pseudocode)寫一個演算法，輸入一個整數n(n>2)並輸出小於n的最大因數 (factor) (Write an algorithm using the pseudo code to input an integer n and output the n's largest factor that is less than n.)
C. 使用虛擬碼 (pseudocode)寫一個演算法，輸入一個整數n(n>2)並輸出所有n除了本身以外的正因數(factor)總和 (Write an algorithm using the pseudo code to input an integer n and output the total summation of all n's factors except n.)
D. 使用虛擬碼(pseudocode)寫一個演算法，輸入整數n及m(n>m>2)，輸出所有比n小並大於m的n的因數(factor)總和， 若無 此因數則輸出0 (Write an algorithm using the pseudo code to input integers n and m, and output all n's factors larger than m and less than n.)
E. 使用虛擬碼(pseudocode)寫一個演算法，輸入一個整數n(n>2)並判斷n是否為完美數(perfect number)。一個完美數是一個正整數，它所有的真因數(即除了自身以外的因數)的和，恰好等於它本身。 (Write an algorithm using the pseudo code to input an integer n and output (decide) if n is a perfect number. Note that a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself.)
F. 使用虛擬碼(pseudocode)寫 一個演算法，輸入一個整數n(n>0)並判斷n是否為快樂數(happy number) (Write an algorithm to input an integer n and output (decide) if n is a happy number.)
註: 快樂數有以下的特性：在給定的進位制下，該數字所有數位(digits)的平方和，得到的新數再次求所有數位的平方和，如此重複進 行，最終結果必為1。例 如，以十進位為例：
28 → 22+82= 68 → 62+82=100 → 12+02+02=1，因此28是快樂數
G. 使用虛擬碼 (pseudocode) 寫一個演算法，輸入一個整數 n (n > 2)，並判斷 n 是否為阿姆斯壯數 (Armstrong number)(Write an algorithm using the pseudo code to input an integer n and decide if n is an Armstrong number.)
註: 阿姆斯壯數 (Armstrong number) 是指一個 d 位數字，其每個數字的 d 次方總和等於該數本身。例如：
153 = 13 + 53 + 33 = 153
9474 = 94 + 44 + 74 + 44 = 9474
- 2.
(3/4)演算法複雜度分析範例(以排序演算法為例)(Alg-Analysis.pptx) (期中專題與期末專題相關介紹:2025-qc-talk.zip)
.1 演算法的效能
.2 演算法的時間複雜度
.3 大O漸進記號
.4 降低演算法時間複雜度量級
.5 漸進記號(asymptotical notation): Big O, Big Omega, Theta
.6 多項式時間、指數時間及偽多項式時間演算法
.7 氣泡排序(bubble sort)演算法
.8 插入排序(insertion sort)演算法
Homework 2: (Select two problems out of A, B, ..., and H and handwrite their solutions. Due day: before noon of next class on 3/11)
A. 使用虛擬碼(pseudocode)寫一個時間複雜度為O(sqrt(n))的演算法，輸入一個整數n(n>2)並輸出所有n除了本身以外的正因數 (factor)總和，你必須分析演算法的時間複雜度。
B. 使用虛擬碼(pseudocode)寫一個時間複雜度為O(sqrt(n))的演算法，輸入整數n及m(n>m>2)，輸出所有比n小並大於 m的n的因數 (factor)總和，若無此因數則輸出0，分析演算法的時 間與空間複雜度。
C. 使用虛擬碼(pseudocode)寫一個時間複雜度為O(sqrt(n))的演算法，輸入一 個整數(n>2)並判斷n是否為完美數 (perfect number)，你必須分析演算法的最差及最佳時間複雜度。
D. 使用虛擬碼(pseudocode)寫一個演算法，以輸入一個具有n個元素的集合S並輸出S的 幂集(power set)，你必須分析演算法的時間複雜度。 (Write an algorithm to input a set S of n elements and output the power set of S. You must analyze the time complexity of your algorithm.)
E. 分析費伯納西數列演算法與遞迴費伯納西數列演算法之空間 複雜度
F. 畫出n log n、n log2 n、n2及n3圖 形(for n=2, 4, 8, ..., 128)並比較之。
G. 若一演算法A的時間複雜度為6 x 2n=O(2n)可以在n=10的時候耗費一小時解決問題 X，而另一個解決問題X的演算法B的時間複雜度為5 x n3 = O(n3)， 則請問當n=10時演 算法B要耗費多少時間完成?
H. 若一演算法A的時間複雜 度為6 x 2n=O(2n)可 以在n=10的時候耗費一小時解決問題X，而另一個解決問 題X的演算法B的時間 複雜度為5 x n3 =O(n3)，則請問當n為 何值時演算法B要耗費一小時才可以完 成?
使 用虛擬碼寫出堆積排序(heap sort)演算法，分析其時間與空間複雜度。
J.
以binary heap實現priority queue的operations，包括 insert(p): Inserts a new element with priority p; extractMax(): Extracts an element with maximum priority; remove(i): Removes an element pointed by an iterator i; changePriority(i, p): Changes the priority of an element pointed by i to p; 以上操作都具有O(log n)的time complexity；而getMax(): Returns an element with maximum priority; 則具有O(1) time complexity。
- 3. (3/11)
分治(divide-and-conquer)演算法: (Alg-Divide&Conquer.pptx)
若是問題 規模(problem size)夠小， 就直接解決之；反之，若問題規模較大，就將其分割(divide)成兩個或多個子問題(分割階段)，然後將每個子問題遞迴地 (recursively)征 服(conquer)解決之(征服階段)。之後再將每個子 問題的解答合併(merge)，使其成為原問題的解答(合併階段)。
.1 分治演算法簡介
.2 分治缺陷棋盤填滿(tiling a defective chessboard)演算法
.3 合併排序(merge sort)演算法 (屬分治演算法)
.4 快速排序(quick sort)演算法 (屬分治演算法)
.5 最大連續子序列和(Maximum Contiguous Subsequence Sum, MCSS)演算法
.6 分治二維求秩(2D rank finding)演算法
.7 分治二維極大點(2D maxima finding)演算法
.8 分治二 維最近點對(2D closest pair of points)演算法
Homework 3: (Due day: before noon of next class on 3/18)
A. 分析合併排序演算法中將兩個元素依序由小而大排列的子陣列L與R合併為元素依序由小而大排列的陣列A的 時間 複雜度為O(n)，其中|L|=|R|=n/2, |A|=n。
B. 舉 出兩個方法讓快速 排序(quick sort)演算法避免產生最壞狀況。
C. 給定一 個序列S=(-2, 1, -3, 4, -1, 2, 1, -5, 4)，仿照merge sort的執行過程畫圖 說明使用分治最大非空連續 子序列和演算法求出最大非空連續子序列和的過程。
D. 給定一個序列S=(-2, -1, -3, -4, -1, -2, -1, -5)，仿照merge sort的執行過程畫 圖說明使用分治最 大可空連續子序列和演算法求出最大可空連續子序列和的過程。
F. 給定8個二維平面點: (1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 3), (7, 9), (8, 7)，畫圖說明使用分治二維求秩演算法求出每個點的秩(rank)的過程。
G. 給定8個二維 平面點: (1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 3), (7, 9), (8, 7)，畫圖說明使用分治二維最近點對演算法求出最近點對距離的過程。
- 4. (3/18) 動態規劃(dynamic programming)演算法: (Alg-DP.pptx)
動態規劃 (dynamic programming)演算法籍由將原問題分解成一系列子問題 (subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問 題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，與其重新計算其 解答，演算法會取而代之地 從表格中直接取出其解答以節省計算時間，是一個「以空間換取時間」的演算法。一個動態規劃演算法會先從最簡單的子問題先解起，並 以一定的程序持續運行直至 求出原問題解答為止。最佳解原則(Principle of optimality): 假設為了解決一個問題，我們必須作出一系列的決策 D1, D2, …, Dn。若這一系列的決策是最佳解，則針對於前n-k個(或最後n-k個)決策所產生的狀態(子問題)而言，最後的k個(或前k個)決 策(1<= k<=n)必定也是最佳的。
*最長共同子序列(longest common subsequence, LCS or LCSS)演算法
*0/1背包動態規劃演算法(0/1 knapsack dynamic programming algorithm)
*矩陣鏈乘積(matrix-chain product)動態規劃演算法
*子集合加總(subset sum)動態規劃演算法
*(複習)多項式及偽多項式時間演算法
*最大連續子序列和(maximum contiguous subsequence sum, MCSS)動態規劃演算法
Homework 4:
A. 說明X=ABCBA與Y=BDCA兩個字串藉由動態規 劃演算法求出最長共同子序列的過程。
C. 設計一個演算法並 分析其複雜度，此演算法可 以輸入長度為m的序列X及長 度為n的序列Y，輸出 true或是false，分別 代表X是或不是Y的子序列。
D. 給定一個0/1背包問題如下；背包荷重W=12，且4個物品其重量各為6、4、5、3，其價值各為20、30、40、10，說明藉由動態規劃演 算法 解決此0/1背包問題的過程。
E. 以子集合加總動態規劃演算法解決以下子集合加總問題: 給定整數集合S={1, 2, 4, 7}及整數c=10。
F. 修改子集合加總動態規劃演算法使其傳回加總值為c的子集合若此子集合存在；否則傳回空集合。
G. 令S = (-2, 1, -3, 4, -1, 2, 1, -5, 4), 使用動態規劃演算法求出最大連續非 空子 序列和。
H. 設計最大連續可空子序列和動態規劃演算法。
I. 藉由動態規劃演算法來替一矩陣鏈(其維度序列為 <5, 20, 10, 12> )加上括號來最佳化矩陣相乘次數。
- 5. (3/25)
刪尋(prune-and-search)演算法: (Alg-Prune&Search.pptx)
刪尋(prune-and-search)演算法包含多次迭代 (iteration)，在每一次的迭代中，均刪除(prune)輸入資料的一部分(假設為f部份, 0<f<1)，而後再遞迴地(recursively)以相同的演算法在剩餘的資料中搜尋(search)出解答。 在經過一定次數的迭代後， 輸入資料的規模將會變得相當小，而能在常數時間內直接找出解答。
假設一個刪除-搜尋演算法的時間複雜度為T(n)，並且每次迭 代所需的時間 為O(nk)(k為大於0的常數)，則T(n)=T((1-f)n)+O(nk)。由於 1-f<1，我們可得T(n)=O(nk)。
.1 刪尋(prune-and-search)演算法概念介紹
.2 二元搜尋(binary search)演算法
.3 選取(selection)與中位數(median)演算法
.4 限制的一圓心 (constrained 1-center)演算法
.5 凸包(Convex Hull)演算法: (ConvexHull.zip)
Homework 5: (任選1題)
(A) 舉一個8個元素的陣列為例說明二元搜尋演算法執行情形，分別說明最佳狀況時間複雜度找到目 標元素、最壞狀況時間複雜度找到目標元素及最壞狀況時間複雜度找不到目標元素。
(B) 在選取刪尋演算法中，若每個分割子集改為3個元素，則其最壞狀況時間複雜度是否依然為 O(n)，為什麼?
(C) 在選取刪尋演算法中，將每個分割子集改為6個元素後重新分析其時間複雜度。
(D) 有一個刪尋演算法其時間複雜度為 T(n)=T((7/8)n)+cn2， 詳細分析其時間複雜度並以大O記號表示。
(E) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(2,0)，圓心在y=0上。(可 以精確繪圖說明即可)
(F) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(4,0)，圓心在y=3上。(可 以精確繪圖說明即可)
- 韓非 (約西元前 281 生，西元
前 233 年卒) 是戰國末期的
思想家，是中國古代法家思想的代表人物。戰國時期，齊、楚、燕、韓、趙、魏、秦七雄並立。蘇秦曾提出南北合縱六國以抗秦的戰略思
想，使秦國
十五年無法向西出兵攻擊位於其東邊且南北合縱的六國。但是後來張儀以東西連橫的外交策略，遊說各國由合縱抗秦轉變為連橫親秦，而 讓秦國得以遠交近攻，逐漸併吞六國。
韓非在《韓非子·存韓》篇中提到:「諸侯可蠶食而盡」，意思是說秦國可化整 為零，也就是將一個整體合縱抗秦的六國化分成許 多零散部份，然後像蠶吃桑葉那樣，一點一點的逐步侵佔滅亡六國，而達成一統天下的目的。
本單元所介紹的演算法，包括二元搜尋演算法、選取與中位數演算法及限制的一圓心演算法，都採用刪尋解題策略解決問題。這個策略就 是類似「化整為零，蠶食而盡」的概念。刪尋演算法 包含許多的迭代，
每次迭代都嘗試刪除固定比例的輸入資料，而後再遞迴地從剩餘資料中搜尋出解答，若仍然無法找出解答則再刪除固定比例的輸入資料。 這樣經過幾次迭代後，輸入資料的規模將會小到足以讓問題在常數時間內
直接解決，因而得到問題的解答。一般而言，整個刪尋演算法的時間複雜度與每個迭代的時間複雜度具有相同的量級，因此刪尋演算是一 個有效率的演算法。
- 6. (3/25) 貪婪演算法(greedy
algorithm): (Alg-Greedy.pptx)
貪婪演算法(greedy algorithm)一步步地建構出一個問題的完整解答。其每一步都藉由貪婪解題策略(greed strategy)增加一部份的解答到完整解答中。所謂貪婪解題策略為: 每一次都選擇當下最好的部份解答加入完整解答中。
.1 背包演算法(knapsack algorithm) (帶出0/1背包問題後可以在之後講授NP-hard問題)
.2 活動選擇(activity selection)演算法
.3 Huffman編碼(Huffman coding)演算法
.4 Kruskal最小生成樹(minimum spanning tree, MST)演算法
.5 Prim最小生成樹(minimum spanning tree, MST)演算法
.6Dijkstra演算法
Homework 5: (任選1 題)
(F) 一個背包容量為 10，現在有5個物品， 重量分別為4、3、6、2、5，價格分別為10、9、 12、4、8，求背包能夠裝入零碎(fractional)物品的最大價值為何?
(G) 利用Huffman 編 碼演算法替以下字元編碼A(46%)、 B(7%)、C (28%)、D (19%)。(備註:括號中為字元出現頻率)
(H) 利用Kruskal演算法求出以下的圖(graph)的最小生成樹 (minimum spanning tree, MST)
(I) 利用Prim演算法求出以上的圖(graph)的最小生成樹 (minimum spanning tree, MST)
(J) 給定 5 個活動，其活動區間分別為 [0,18), [3, 5), [4, 16), [2, 9), [10, 15)，請描述如何以活動選擇演算法找出最多的相容活動總數m(必須寫出m的數值)。
7. (4/1)問 題下界與問題分類: P、NP、NP困難與NP完全問題
- *一個問題的下界(PLB)為任何能解決此問題的演算法至少所需的時間複雜度。(The lower bound
of a problem is the least time complexity required for
any algorithm which can be used to solve this problem.)
*NP完全(NPC)問題理論: 若任何一個NP完全(NPC)問題可在多項式時間被解決，則每一個NP問題皆可在多項式時間獲得解決(也就是P=NP)。 If any one NP-complete (NPC) problem can be solved in polynomial time, then every problem in NP can also be solved in polynomial time (i.e., P=NP). (ProblemLB.zip)(Recipe, Cook, Carp, and Bernstein)(NPC.zip) (教科書新增PLB-NPC一章)
*(NPC 理論測驗及解答)
Homework 6: (A-S任選兩題)
A. 以下的敘述是對還是錯，並解釋對或錯的原因:
若我們能證明任何一個 NPC問題的最壞狀況問題下界(worst case problem lower bound)是指數函數量級，則我們已經證明 NP不等於P。
B. 以下的敘述是對還是錯，並解釋對或錯的原因:
若我們能證明任何一個 NPC問題的最壞狀況問題下界(worst case problem lower bound)是多項式函數量級，則我們已經證明 NP等於P。
C. 以下的敘述是對還是錯，並解釋對或錯的原因:
若我們能直找到一個確定性演算法，在最差狀況下以多項式時間複雜度解決一個NPC問題，則我們已經證明NP等於P。
D. 以下的敘述是對還是錯，並解釋對或錯的原因:
人們已經證明: 沒有任何確定演算法(deterministic algorithm)可以在最差狀況(worst case)下，以多項式時間複雜度解決NPC問題。
E. 以下的敘述是對還是錯，並解釋對或錯的原因:
人們已經證明: 沒有任何確定演算法(deterministic algorithm)可以在最差狀況(worst case)下，以多項式時間複雜度解決NP-hard問題。
F. 以下的敘述是對還是錯，並解釋對或錯的原因:
任何NPC問題可以polynomially reduces to另一個NPC問題。
G. 證明支配集問題(dominating set problem)為NP問題。
H. 證明點覆蓋問題(vertex cover problem)為NP問題。
I. 證明集團問題(clique problem)為NP問題。
J. 證明著色問題(chromatic coloring problem)為NP問題。
K. 證明0/1 背包問題(0/1 knapsack problem)為NP問題。
L. 證明3-滿足問題(3-SAT problem)為NP問題。
M. 證明最大割問題(Max cut problem)為NP問題。
N. 證明史坦惹樹問題(Steiner tree problem)為NP問題。
O. 證明劃分問題(partition problem)為NP問題。
P. 證明擊中集合問題(hitting set problem)為NP問題。
Q. 證明三維匹配問題(3-dimensional matching problem)為NP問題。
R. 證明Convex Hull問題的問題下界為Omega(n log n)
S. 畫出merge sort演算法的三個元素(1,2,3)的decision tree - 8. (4/8) Solving NP-hard
Problems with Quantum Annealing (AWS-Braket-Experience.pptx) (期中專題與期末專題相關介紹:2025-April-QC-talk.zip)上機教學文件:(2025-0408-annealing-midterm-project.ipynb)
(自行上傳到自己的Google Drive中才可以使用)
參考論文:
- Jehn-Ruey Jiang, and Chun-Wei Chu, "Classifying and Benchmarking Quantum Annealing Algorithms Based on Quadratic Unconstrained Binary Optimization for Solving NP-hard Problems," IEEE Access, vol. 11, pp. 104165-104178, 2023. (DOI: 10.1109/ACCESS.2023.3318206)(SCI)(IF: 3.745)Computer Science (miscellaneous)(Q1); Engineering (miscellaneous)(Q1).
- Jehn-Ruey Jiang, Yu-Chen Shu, and Qiao-Yi Lin, "Benchmarks and Recommendations for Quantum, Digital, and GPU Annealers in Combinatorial Optimization," IEEE Access, vol. 12, pp. 125014-125031, 2024. (DOI: 10.1109/ACCESS.2024.3455436)(SCI)(IF: 3.745)Computer Science (miscellaneous)(Q1); Engineering (miscellaneous)(Q1).
- (4/15) Midterm
Exam. (範圍為單元1-7授課內容)(25%)
考試時間: 4/15 14:00~16:20 。
考試地點: 工程五館 教室
請依照助教安排座位入座參加考試 - (Deadline: 4/21) Midterm Project: Quantum Annealing Programming (佔總分10%)(請 依助教規定方式於4/21 23:59前繳交)。
-
9. (4/22) 使 用貪婪(greedy)演算法以 及動態規劃(dynamic programming)演算法解決最短路徑問題: (Alg-SP.pptx) (教科書新增一章ShortestPath)
由 加權有向圖(weighted digraph)中的某個頂點或節點 (vertex or node)v到圖中的另一節點u，若v到u之間存在一條路徑(path)，則路徑中所經過的邊(edge)的權值(weight)總合稱為路徑的成本 (cost)或距離(distance)，而所有路徑中具有最小成本或距離的路徑則稱為最短路徑(shortest path)。
(0) 本次課程概要說明(含貪婪演算法及動態規劃演算法之比較說明)(影片網址:https://youtu.be/YYg8iLf1ej4)
(1) 多階圖最短路徑演算法(使用動態規劃解題策略)(影片網址:https://youtu.be/GQ4xKH4MpYI)
(2) Dijkstra演算法(使用貪婪解題策略)(上週同步課程中已解說，因此不包含在此次課程影片中)
(3) Bellman-Ford演算法(使用動態規劃解題策略)(影片網址:https://youtu.be/jc-NLpcV6vY)
(4) Floyd-Warshall演算法(使用動態規劃解題策略)(影片網址:https://youtu.be/UdTjmFy7J_E)
Homework 7:
A. 使用動態規劃演算法求以下多階圖的最短路徑。
B. 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)及其距離(成本)。註: 需要寫出每次迭代每個節點之最 短路徑更新的過程。
C. 承上題，利用Dijkstra演算法求頂點1到各頂點的最短路徑(shortest path)及其距離(成本)。註: 需要寫出每次迭代每個節點之最 短路徑更新的過程。
(d->b的加權在圖形與表格中誤植為不一致的值，同學可以將之改為5或6讓圖形與表格一致後解題都算答對。)
E. 求出以下給定圖(graph)的Floyd-Warshall演算法的啟始前節點矩陣(陣列)，並求出最後的前節點矩陣(陣 列)。
F. 針對以下的給定圖，列出Bellman- Ford最短路徑演算 法執行過程， 說明Bellman -Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight cycle)。
G. 分析多階圖最短路徑動態規劃演算 法時間複雜度。
- Slides and Videos: (Alg4-1203(NoMark).pptx)
(更正: 投影片第36和37頁 樹第三層右邊的三個節點由左而右依序為"2' "4' "5")
Youtube video:https://youtu.be/mM93FheJEGQ)
*許多問題的尋找解答過程可以使用樹 (tree)來表達，這類問題也都可以建構 出解答空間樹(solution space tree)。因此要找到這些問題的解答，不管是可行解(feasible solution)或是最佳解(optimal solution)，就轉變成一個樹搜尋(tree search)問題。
*有許多方法可以拜訪(visit)與拓展(expand)一個解答空間樹，包括深度優先搜尋(depth- first search, DFS)、廣度優先搜尋 (breadth- first search, BFS)、登山搜尋(hill climbing search, HCS)以及最佳優先搜尋(best-first search)等演算法。
* 廣度優先搜尋(breadth-first search, BFS)演算法
* 深度優先搜尋(depth-first search, DFS)演算法
* 登山搜尋法(hill climbing search, HCS)演算法
* 最佳優先搜尋法(best-first search)演算法
* 回溯(backtracking)演算法
Homework 8:
A. 給定一集合S={7, 4, 1, 2, 11}以及一加總值10，利用深度優先搜尋法來解子集合加總問題，你必須畫出解出問題的解 答空間樹(solution space tree)。
B. 以深度優先搜尋演算法找出以下圖 (graph)的漢米爾頓迴路 (Hamiltonian circuit)，你必須畫出解出問題 的解 答空間樹(solution space tree)。
C. 以廣度優先搜尋演算法找出上圖的漢米爾頓 迴路，你必須畫出解出問題 的解答空間樹(solution space tree)。
D. 以空單 格的移動方向為上下左右的次序，以廣度優先搜 尋演 算法下解決以下 的八拼圖(8- puzzle)問題。
起 始狀態:
目標狀態:2
3184765
E. 以空單 格的移動方向為上下左右的次序，以深度優先搜 尋演 算法解決D題中 的八拼圖(8- puzzle)問題。1238
47
65
F. 以空單格的移動方向為上下左右的次序，以登山搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為 方塊錯置的數目，若有相同的 情形，則以空單格移動方向上下左右為其優先順序。
G. 以空單格的移動方向為上下左右的次序，以最佳優先搜 尋演算法解決D題中的八拼圖 (8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方 向上下左右為其優先順序。
H. 列出4-Queen問題的所有解答
- 11. (5/6) 分支定界(Branch and Bound)演算法 (Branch&Bound.zip) (AlgBookB&B.zip)(Youtube
video Part1: https://youtu.be/KUlDxRV6fsU)(Youtube video Part2: https://youtu.be/R91wC81n6Yk)
*分支定界(branch and bound)是一個拜訪(visit)與拓展(expand)解 答空間樹的特殊方法，用於找出問題的最佳解。其做法相當於找出一種方法來切割出解答空間的分支(branch)，然後以上界(upper bound)與下界(lower bound)的概念來加快最佳解的搜尋。
*對於尋找最小值(minimum)解答的最小化(minimization)問題而言，分支定界演算法會針對每一分支預測其解 答的下界(lower bound)，並利用找出可行解(feasible solution)來得到目前最佳解答的上界(upper bound)。如果有一個分支的解答下界超過或等於目前最佳解答的上界，則這個分支不可能找到最佳解或比目前最佳解更好的解答，因此演算法會中止 (terminate)在這個分支上的搜尋。
*而對於尋找最大值(maximum)解答的最大化(maximization)問題而言，分支定界演算法會針對每一分支預測其 解答的上界(upper bound)，並利用找出可行解(feasible solution)來得到目前最佳解答的下界(lower bound)。如果有一個分支的解答上界低於或等於目前最佳解答的下界，則這個分支不可能找到最佳解或比目前最佳解更好的解答，因此演算法會中止 (terminate)在這個分支上的搜尋。
.1 基本概念
.2 分支定界演算法(配合登山搜尋法)解決多階圖最短路徑問題
.3 分支定界演算法(配合最佳優先搜尋 法)解決旅行推銷員問題
.4 分支定界演算法(配合最佳優先搜尋 法)解決0/1背包問題
.5 一個特殊的分支定界演算法: A*演算法
Homework 9: (A- G選2題)
A. 以分支定界演算法解決以下多階圖最短路徑問題。
B. 給定一0/1背包問題，其背包可載重C=10,且有三物品的重量分別為10, 3, 5，而其利潤分別為40, 20, 30，求出可以放入背包中物品利潤的負值的最小化，使用分支定界演算法來解此0/1背包問題。 （註: 必須畫出搜尋樹）(此題使用負的目標函數值，因此feasible solution是求出upper bound，而且我們不斷 地嘗試降低upper bound)
C. 同上 題，但目標改為求 出可以放入背 包中物品利潤的最大化，使用分支定界演算法來解此0/1背包問 題。 （註: 必須畫出搜尋樹）(此題使用正的目標函數值，因此feasible solution是求出lower bound，而且我們不斷地嘗試提高lower bound)
D. 使用A*演算法來解以下之多階圖最短路徑問題。（註: 必須畫出搜尋樹）
E. 將A題的S與T對調，箭頭反向解題。
F. 將B題所有成本乘以2減3解題。
G. 將C題的物品重量改為20, 5, 6解題。
H. 將D題的V0與V8對調，箭頭反向解由V8到V0的最段路徑問題。 - 12. (5/13) 近似演算法 (Approximation
algorithms) (ApproximationAlgorithm.zip)
歐拉旅途演算法 (Eulerian Tour Algorithm) (EulerianTour.zip)
From Wiki: URL: https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98
定理一
*連通的無向圖G有歐拉路徑的充要條件是： G中奇頂點（連接的邊數量為奇數的頂點）的數目等於0或者2。
*連通的無向圖G是歐拉環（存在歐拉迴路）的充要條件是： G中每個頂點的度都是偶數。
定理二
*一個連通的有向圖可以表示為一條從頂點 u到 v的（不閉合的）歐拉路徑的充要條件是： u的出度（從這個頂點發出的有向邊的數量）比入度（指向這個頂點的有向邊的數量）多1， v的出度比入度少1，而其它頂點的出度和入度都相等。
*一個連通的有向圖是歐拉環（存在歐拉迴路）的充要條件是：每個頂點的出度和入度都相等。
Howework 10:
A. 使用2-近似演算法(2-approximation algorithm)來解決以下圖的頂點覆蓋問題 (vertex cover problem)。（註: 須描述在執行演算法過程的每個中間結果。）
B. 使用歐拉旅途演算法來找出以下圖的歐拉旅途。（註: 須描述在執行演算法過程的每個中間結果。）
C. 將以自然語言撰寫的「無向圖歐拉旅途/路徑演算法」改為以虛擬碼撰寫
D. 以虛擬碼撰寫「有向圖歐拉旅途/路徑演算法」
E. 以自然語言撰寫「有向圖歐拉旅途/路徑演算法」(應考慮「入度(in-degree)」與「出度(out-degree)」的相差值)
F. 分析「無向圖歐拉旅途/路徑演算法」以及「有向圖歐拉旅途/路徑演算法」的 時間複雜度 -
13. (5/13) 匈牙利演算法(Hungarian
Algorithm)(HungarianAlg.zip)
演算法課程 _0608(匈牙利演算法)影片
Homework 10:
G. 使用匈牙利演算法(Hungarian algorithm)來解以下的最小成本指派問題(assignment problem)（註: 必須寫出演算法執行過程中的每個中間結果）
H. 說明如何使用匈牙利演算法(Hungarian algorithm)解決最小歐氏平面權重配對(Minimum Euclidean Weighted Matching)問題。所謂最小歐氏平面權重 配對問題描述如下: 給定n個點(n為偶數)，如何將此n個點匹配形成n/2個點對，讓每個點對形成一條線段，而此n/2條線段具有最小的長度總和。
Task A
Task B
Task C
Tim
$1
$2
$3
Bob
$2
$3
$2
Alex
$2
$2
$3
- 單元14、15(qc-talk.pptx)(qc-talk-full.pptx) (QBookCh1.zip)(QBookCh2.zip)(QBookCh3.zip)(QBookCh4.zip)(QBookCh5.zip)(QBookCh6.zip)(QBookCh7.zip)
- (5/20)
14. 量子演算法1
Homework 11: 練習1.1-1.4；2.1-2.4;3.1-3.5共計13題。每位同學每章任選一題繳交，因此作業共計3題。
- (5/27) 15. 量子演算法2
Homework 12: 練習4.1-4.5任選1題；練習6.1-6.4任選1題，共計2題。 - 6/3
Final Examination 14:00-16:30(書面筆試，範圍為期中考之後教授的內容，含最
短路徑演算法、樹搜尋與回溯演算法、
分支定界演算法、A*演算法、近似演算法、歐拉旅途演算法、匈牙利演算法)
(
25%28%)
- Term
Project (Deadline 6/24 12:00PM) (up to 14%)(任選一題完成最高得7%，兩題都完成最高可得14%)
(7%) 1. 以分支定界演算法解決旅行銷售員問題(Traveling Salesperson Problem, TSP)(Online Judge以及書面報告)
(7%) 2. 設計量子程式使用格羅佛演算法 (Grover's algorithm)解決頂點覆蓋問題(Vertex Cover Problem, VCP)(題目: 2025TermProject.pptx) (繳交書面報告)(參考論文及投影片: Grover-VCP-ppt.zip)
