Teaching Assistants (TAs): 王昱傑 顏暐翰 高子豪
Time: 週二 14:00~16:50
Place: 週二 工五館(E6) A207
TA Class: 週二 13:00~13:50 工五館(E6)A207
Sign-In Form (若採線上授課之簽 到單): https://forms.gle/BJjEWro4hF3jG4yb8 (請同學於13:45-14:15進行簽到)
Online Course Link (若採線上授課之課 程鏈結)：https://ncu-edu.webex.com/meet/pr110522039
Offline Video List: Link
請大家先觀看之前的課程介紹影片: https://youtu.be/1muNkALTSr8
*請加選的同學慎思，因為本課程為資工系必修課，課程不及格比率為15%+-5%。修讀本課 程需要繳交midterm project、term project以及每週手寫作業6-10題，任選二題作答；每週線 上程式作業3題，至少完成一題；每週助教課程分組報告一小時，需上傳作業解題投影片。
*建議可以採用先看習題，然後再到影片中學會解決問題技術的方式學習，效果較佳!
Scope:
- Many Classical Algorithms
- Several Machine Learning/Deep Learning Algorithms (2019開始新增)
- Few Quantum Algorithms (2021開始新增)
- 期中考(分析與設計概念)(25%)
- 期末考(分析與設計概念)(30%)
- 期中專題、期末專題、作業、程式設計作業、報告、課程參與度(45%)
- My Book's Manuscript: (輕鬆學演算法 -- 從古典到量子演算法) AlgBook-2023-0325.zip (此教科書勘誤加分由2023年3月 25日 11:45開始，勘誤範圍為0-8章，期中考以此版本為標準答案)；AlgBook(Ch0-7+App1-2)(2023-0213).zip (2023/02/13更新版)(此教科書勘誤加分由2023年2月14日 21:00開始， 勘誤範圍為0-7章。報告勘誤請列出 AlgBook草稿版本日期、錯誤頁碼及錯誤處，並請先確認是否已 有他人列舉過。)(書籍即將出版，版權 所有，草稿僅供修課同學參考，請勿散播流出:)
- 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)
- 第十二屆全國大專院校 AI 智動化設備創作獎: (png)(pdf); AR: (png); AR Paper: (pdf)
- (2/14)(2/21)1. 認識演算法 -- 從食譜到高階程式語言: (AlgSmallTalk.pptx) (Alg-Intro.pptx) (CPSforIndustry4.0.zip) (ACM-ICPC&EPC.ppt)(CPSProject.zip) .1 演算法名稱的由來
.2 什麼是演算法?
.3 演算法的例子
.4 如何表示演算法?
.5 如何實作演算法? (EuclidGCD.c)(EuclidGCD.cpp)(EucidCGDClass1.java)(EucidCGDClass.java)(EuclidGCD.py)
.6 演算法的正確性
Homework1: (for 2/21; Due day: before next class or TA's class on 3/7)
A. 使用虛擬碼(pseudo code)寫一個演算法，輸入一個整數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. 使用虛擬碼(pseudo code)寫一個演算法，輸入一個整數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. 使用虛擬碼 (pseudo code)寫一個演算法，輸入一個整數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. 使用虛擬碼(pseudo code)寫一個演算法，輸入整數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. 使用虛擬碼(pseudo code)寫一個演算法，輸入一個整數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. 使用虛擬碼(pseudo code)寫 一個演算法，輸入一個整數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是快樂數
- 2.
(3/7)演算法複雜度分析範例(以排序演算法為例)(Alg-Analysis.pptx)
.1 演算法的效能
.2 演算法的時間複雜度
.3 大O漸進記號
.4 降低演算法時間複雜度量級
.5 漸進記號(asymptotical notation): Big O, Big Omega, Theta
.6 多項式時間、指數時間及偽多項式時間演算法
.7 氣泡排序(bubble sort)演算法
.8 插入排序(insertion sort)演算法
Homework 2: (2023-ICCE-4-Papers.zip) (Select one problem out of A, B, ..., and H to handwrite its solution, and one of the 4 papers to handwrite a report; Due day: before next TA's class on 3/14)
A. 使用虛擬碼(pseudo code)寫一個時間複雜度為O(sqrt(n))的演算法，輸入一個整數n(n>2)並輸出所有n除了本身以外的正因數 (factor)總和，你必須分析演算法的時間複雜度。
B. 使用虛擬碼(pseudo code)寫一個時間複雜度為O(sqrt(n))的演算法，輸入整數n及m(n>m>2)，輸出所有比n小並大於 m的n的因數 (factor)總和，若無此因數則輸出0，分析演算法的時 間與空間複雜度。
C. 使用虛擬碼(pseudo code)寫一個時間複雜度為O(sqrt(n))的演算法，輸入一個整數(n>2)並判斷n是否為完美數 (perfect number)，你必須分析演算法的最差及最佳時間複雜度。
D. 使用虛擬碼(pseudo code)寫一個演算法，以輸入一個具有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要耗費一小時才可以完 成?
I. (此題僅供參考，不列入手寫作業及實習課口頭報告範圍，也不列入考試範圍)
使 用虛擬碼寫出堆積排序(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/14)
分治(divide-and-conquer)演算法: (Alg-Divide&Conquer.pptx)
若是問題 規模(problem size)夠小， 就直接解決之；反之，若問題規模較大，就將其分割(divide)成兩個或多個子問題(分割階段)，然後將每個子問題遞迴地 (recursively)征 服(conquer)解決之(征服階段)。之後再將每個子 問題的解答合併(merge)，使其成為原問題的解答(合併階段)。Homework 3:
.1 分治演算法簡介
.2 分治缺陷棋盤填滿(tiling a defective chessboard)演算法
.3 合併排序(merge sort)演算法 (屬分治演算法)
.4 快速排序(quick sort)演算法 (屬分治演算法)
A. 在氣泡排序(bubble sort)演算法中，若在某回合中完全沒有任何資料對調，則可推論資料已經排序完成而立即結束演算法執行，這稱為改良氣泡排序(improved bubble sort)演算法。請以虛擬碼描述「改 良氣泡排序演算法」。(請注意:在有些文獻中，所謂 「氣泡排序演算法」其實指的是「改良氣 泡排序演算 法」)
B. 分析改 良氣泡排序演算法最佳、最差與平均時間複雜度
C. 分析合併排序演算法中將兩個元素依序由小而大排列的子陣列L與R合併為元素依序由小而大排列的陣列A的時間 複雜度為O(n)，其中|L|=|R|=n/2, |A|=n。
D. 分析快速排序演算法最佳狀況空間複雜度(best case space complexity)。
E. 分析快速排序演算法最差狀況空間複雜度(worst case space complexity)。
F. 舉出兩個方法讓快速 排序(quick sort)演算法避免產生最壞狀況。
- 4-1. (3/21) 分治演算法(2):
(Alg-Divide&Conquer.pptx後
半段)
(FFT.zip)
.1分治快速傅立葉變換(fast Fourier transform, FFT)演算法
.2分治二維求 秩(2D rank finding)演算法
.3分治二維極大點(2D maxima finding)演算法
.4 分治二 維最近點對(2D closest pair of points)演算法
.5 最大連續子序列和(Maximum Contiguous Subsequence Sum, MCSS)演算法
Homework 4-1:
A. 給定一個序列S=(-2, 1, -3, 4, -1, 2, 1, -5, 4)，仿照merge sort的執行過程畫圖 說明使用分治最大非空連續 子序列和演算法求出最大非空連 續子序列和的過程。
B. 給定一個序列S=(-2, -1, -3, -4, -1, -2, -1, -5)，仿照merge sort的執行過程畫 圖說明使用分治最 大可空連續子序列和演算法求出最大可 空連 續子序列和的過程。
C. 寫一個分治演算法來解決一個給定數值集合 的求秩(rank finding)問題，並進行複雜度分析。
D. 寫一個分治演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)，並進行複雜度 分析。
E. 給定8個二維平面點: (1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 3), (7, 9), (8, 7)，畫圖說明使用分治二維極大點演算法求出所有極大點(maxima)的過程。
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)，畫圖說明使用分治二維最近點對演算法求出最近點對距離的過程。
H. 說明如何使用預先排序(pre-sorting)於分治最近二維點對 (closest pair of 2D points)演算法。
I. 舉例說明一個快速傅立葉變換的應用。 - 4-2. (3/21) 動態規劃(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)
*子集合加總(subset sum)動態規劃演算法
*(複習)多項式及偽多項式時間演算法
*最大連續子序列和(maximum contiguous subsequence sum, MCSS)動態規劃演算法
Homework 4-2:
A. 說明X=ABCBA與Y=BDCA兩個字串藉由動態規 劃演 算法求出最長共同子序列的過程。
B. 設計一個演算法並分析其複雜度，此演算法可以用於產生一個給定集合S的所有可能子集合，其中假定S具有n個不同的元素。
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. 設計最大連續可空子序列和動態規劃演算法。 - 5. (3/28) 機器學習演算法 (Machine Learning algorithms) (ML.pptx)深度學習演算法(DeepLearning.pptx)
(請同學開始觀看Midterm Project投影片及影片，開始準備實作Midterm Project)(Midterm-Project.pptx)
投影片: https://drive.google.com/drive/folders/1OiRiTyf5xMbHxlUEg2LUbXT9Z9GqgLZu?usp=sharing
教學影片:
演算法課程_機 器學習環境安裝之教學影片 - (4/11) Midterm
Exam. (範圍為單元1-4授課內容)
考試時間: 4/11 14:00~16:20 。
考試地點: 工程五館 三間教室
請依照助教安排座位入座參加考試 - (Deadline: 4/18) Midterm Project: Mechanical parts (Bolt, Nut, Washer, Pin) Recognition (佔總分12%)(請 依助教規定方式於4/18中午12:00前線上繳 交)。
- 單元6、7、8(qc-talk.pptx)(qc-talk-full.pptx) (QBookCh1.zip)(QBookCh2.zip)(QBookCh3.zip)(QBookCh4.zip)(QBookCh5.zip)(QBookCh6.zip)(QBookCh7.zip)
- (4/18)
6. 量子演算法1
Homework 6: 練習1.1-1.4；2.1-2.4;3.1-3.5共計13題。每位同學每章任選一題繳交，因此作業共計3題。另外，練習1.5及2.5為加分題，可以 一併寫入本次作業中。本次作業可以製作為電子檔，請依助教規定於4/25中午12:00前線上繳交。
- (4/25) 7. 量子 演算法2
Homework 7: 練習4.1-4.5任選1題；練習5.1-5.4任選1題，因此共 計2題。本次 作業可以製作為電子檔，請依助教規定於5/2中午12:00前線上繳交。
- (5/2) 8.
量子演算法3 (RSA.zip)(FFT.zip)
Homework 8:練習 6.1-6.5任選1題；練習7.1-7.5任選2題，因此共 計2題。本次 作業可以製作為電子檔，請依助教規定於5/9中午12:00前線上繳交。
練習 7.1: 設計量子程式將 5 個量子位元初始狀態設定為 '11011'，先以布洛赫球面顯示量子位元狀態，然後加入量子傅立葉變換線路後，再以布洛赫球面顯示量子位元經過量子傅立葉變換之後的狀態，最後再加入 逆量子傅立葉變換線路，而且同樣以布洛赫球面顯示量子位元狀態。在程式的最後必須顯示整體量子線路，程式可以直接呼叫本章提 供的 qft 及 iqft 函數建構量子傅立葉變換線路及逆量子傅立葉變換線路，並且以量子閘的形式加入量子線路中。請注意，程式無須加入定義 qft 及 iqft函數的細節，但是在呼叫這 2 個函數之前要先執行定義這 2 個函數的程式。
練習 7.2: 設計量子程式透過量子相位估測，以 3 個計數位元的測量結果推導出么正變換T閘本徵值對應的相位。程式必須顯示整體量子線路，計數位元的測量結果直方圖，以及由測量結果推導出的相位。程式可以 直接呼叫本章提供的 iqft 函數建構逆量子傅立葉變換線路，並且以量子閘的形式加入量子線路中。請注意，程式無須加入定義 iqft 函數的細節，但是在呼叫 iqft 函數之前要先執行定義 iqft 函數的程式。
練習 7.3: 設計量子程式透過量子相位估測，以 6 個計數位元的測量結果推導出帶 𝜋 /3 參數么正變換 P 閘本徵值對應的相位。程式只需要顯示計數位元的測量結果直方圖，以及由測量結果推導出的相位。程式可以直接呼叫本章提供的 iqft 函數建構逆量子傅立葉變換線路，並且以量子閘的形式加入量子線路中。請注意，程式無須加入定義 iqft 函數的細節，但是在呼叫 iqft 函數之前要先執行定義 iqft 函數的程式。
練習 7.4: 設計量子程式建構使用 2 個量子計數位元，對應 𝑓(𝑥) = 11𝑥 (mod 15) 的量子相位估測線路，並使用量子電腦模擬器執行量子線路，獲得量子計數位元的測量結果，以求出𝑓(𝑥)的週期。程式可以 直接呼叫本章提供的 qc_mod15 及 iqft 函數建構量子模冪線路及逆量子傅立葉變換線路，並且以量子閘的形式加入量子線路中。程式的最後必須顯示整體量子線路，並顯示量子計數位元的測量結果以及根 據測量結果得到的週期估測值。請注意，程式無須加入定義 qc_mod15 及 iqft 函數的細節，但是在呼叫這 2 個函數之前要先執行定義這 2 個函數的程式。
練習 7.5: 設計量子程式建構使用 4 個量子計數位元，對應𝑓(𝑥) = 7𝑥 (mod 15) 的量子相位估測線路，並使用量子電腦模擬器執行量子線路，獲得量子計數位元的測量結果，以求出𝑓(𝑥) 的週期。程式 可以直接呼叫本章提供的 qc_mod15 及 iqft 函數建構量子模冪線路及逆量子傅立葉變換線路，並且以量子閘的形式加入量子線路中。程式的最後必須顯示整體量子線路，並顯示量子計數位元的測量結果以及根 據測量結果得到的週期估測值。請注意，程式無須加入定義 qc_mod15 及 iqft 函數的細節，但是在呼叫這 2 個函數之前要先執行定義這 2 個函數的程式。
- 9. (5/9)問
題下界與問題分類: P、NP、NP困難與NP完全問題
*一個問題 的下界為任何能解決此問題的演算法至少所需的時間複雜度。(The lower bound of a problem is the least time complexity required for any algorithm which can be used to solve this problem.)
*NP完全問題理論: 若任何一個NP完全問題可在多項式時間被解決，則每一個NP問題皆可在多項式時間獲得解決(也就是P=NP)。 If any one NP-complete 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)
* Solving NP-hard Problems with Quantum Annealing (AWS-Braket-Experience.pptx)
*(NPC 理論測驗及解答)
Homework 9: (A-S任選兩題)
(本次 作業採手寫後拍照上傳方式繳交，請依助教規定於5/10中午12:00前線上繳交。)
(本次實習課報告採用單數或雙數繳交投影片錄影檔案及簡報檔案方式進行，請依助教規定時間及方式線上繳交。)
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問題。證明支配集問題(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
- 10. (5/16)
刪尋(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 10:
(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 年卒) 是戰國末期的
思想家，是中國古代法家思想的代表人物。戰國時期，齊、楚、燕、韓、趙、魏、秦七雄並立。蘇秦曾提出南北合縱六國以抗秦的戰略思
想，使秦國
十五年無法向西出兵攻擊位於其東邊且南北合縱的六國。但是後來張儀以東西連橫的外交策略，遊說各國由合縱抗秦轉變為連橫親秦，而 讓秦國得以遠交近攻，逐漸併吞六國。
韓非在《韓非子·存韓》篇中提到:「諸侯可蠶食而盡」，意思是說秦國可化整 為零，也就是將一個整體合縱抗秦的六國化分成許 多零散部份，然後像蠶吃桑葉那樣，一點一點的逐步侵佔滅亡六國，而達成一統天下的目的。
本單元所介紹的演算法，包括二元搜尋演算法、選取與中位數演算法及限制的一圓心演算法，都採用刪尋解題策略解決問題。這個策略就 是類似「化整為零，蠶食而盡」的概念。刪尋演算法 包含許多的迭代，
每次迭代都嘗試刪除固定比例的輸入資料，而後再遞迴地從剩餘資料中搜尋出解答，若仍然無法找出解答則再刪除固定比例的輸入資料。 這樣經過幾次迭代後，輸入資料的規模將會小到足以讓問題在常數時間內
直接解決，因而得到問題的解答。一般而言，整個刪尋演算法的時間複雜度與每個迭代的時間複雜度具有相同的量級，因此刪尋演算是一 個有效率的演算法。
- 11. (5/23) 貪婪演算法(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)演算法
.6 Dijkstra演算法
Homework 11: (含Homework 12之 B、C、D共10題任選2題)
(A) 一個背包容量為 10，現在有5個物品， 重量分別為4、3、6、2、5，價格分別為10、9、 12、4、8，求背包能夠裝入零碎(fractional)物品的最大價值為何?
(B) 給定 5 個活動，其活動區間分別為 [0,18), [3, 5), [4, 16), [2, 9), [10, 15)，請描述如何以活動選擇演算法找出最多的相容活動總數m(必須寫出m的數值)。
(C) 利用Huffman 編 碼演算法替以下字元編碼A(46%)、 B(7%)、C (28%)、D (19%)。(備註:括號中為字元出現頻率)
(D) 利用Kruskal演算法求出以下的圖(graph)的最小生成樹 (minimum spanning tree, MST)
(E) 利用Prim演算法求出以上的圖(graph)的最小生成樹 (minimum spanning tree, MST)
(F). 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)及其距離(成本)。註: 需要寫出每次迭代每個節點之最 短路徑更新的過程。
(G). 承上題，利用Dijkstra演算法求頂點1到各頂點的最短路徑(shortest path)及其距離(成本)。註: 需要寫出每次迭代每個節點之最 短路徑更新的過程。 -
12. (5/23) 使 用貪婪(greedy)演算法以 及動態規劃(dynamic programming)演算法解決最短路徑問題: (Alg-SP.pptx)
配合教務處創新教學計畫的研究進程，本日之後的所有課程 在 線上以同步課程方式解說之後採用非同 步線上課程方式進行教學，同學可以自行安 排課程學習進度學習，但是必須如期繳交作業。 請同學體驗一下同步與非同步線上教學的優缺點，在6/14舉行線上期末考時回饋給我們參考。)由 加權有向圖(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 12:
A. 使用動態規劃演算法求以下多階圖的最短路徑。
(d->b的加權在圖形與表格中誤植為不一致的值，同學可以將之改為5或6讓圖形與表格一致後解題都算答對。)
C. 求出以下給定圖(graph)的Floyd-Warshall演算法的啟始前節點矩陣(陣列)，並求出最後的前節點矩陣(陣 列)。
D. 針對以下的給定圖，列出Bellman- Ford最短路徑演算 法執行過程， 說明Bellman -Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight cycle)。
- 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 13:
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)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方 向上下左右為其優先順序。 - 14. (6/6) 分支定界(Branch and Bound)演算法 (Branch&Bound.zip)
(Youtube video Part1: https://youtu.be/KUlDxRV6fsU)(Youtube video Part2: https://youtu.be/R91wC81n6Yk)
*分支定界(branch and bound)是一個拜 訪與拓展解 答空間樹的特殊方法，用於找出問題的最佳解。其做法相當於找出一種方法來切割出解答空間的分支(branch)，然後以上界 (upper bound)與下界(lower bound)的概念來加快最佳解的搜尋。
*對於尋找最小成本(minimum cost)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其成本下界(lower bound)，並利用找出可行解來得到問題的成本上界(upper bound)。如果有一個解答的成本下界超過問題成本上界，則這個解不可能是最佳的，因此演算法會中止(terminate)與 這個解相關聯的整個分支的 搜尋。
*而對於尋找最大利益(maximum benefit)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其利益上界(upper bound)，並利用找出可行解來得到問題的利益下界(lower bound)。如果有一個解答的利益上界低於問題利益下界，則這個解不可能是最佳的，因此演算法會中止(terminate)與 這個解相關聯的整個分支的 搜尋。
.1 基本概念
.2 分支定界演算法(配合登山搜尋法)解決多階圖最短路徑問題
.3 分支定界演算法(配合最佳優先搜尋 法)解決旅行推銷員問題
.4 分支定界演算法(配合最佳優先搜尋 法)解決0/1背包問題
.5 一個特殊的分支定界演算法: A*演算法
Homework 14: (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的最段路徑問題。 - 5/30 演講: "AI倫理" by 陳弘軒
教授 (需簽到)
- 6/6 演講: "量子糾纏由哲學，科學，到科技" by 張慶瑞 教授 (需簽到)
- 6/13
Final Examination
14:00-16:30(書面筆試，範圍為期中考之後教授的內容，含量子演算法、問
題下界與問題分類、刪尋演算法、
貪婪演算法、
最短路徑演算法、樹搜尋與回溯演算法、
分支定界演算法)
(30%)
- Term
Project (Deadline 6/20 12:00PM) (12%)
設計量子程式建構使用 c (2 <= c <= 8)個量 子計數位元(counting bits)，對應𝑓(𝑥) = a𝑥 (mod 15) 的量子相位估測線路，並使用量子電腦模擬器執行量子線路，獲得量子計數位元的測量結果，以求出𝑓(𝑥) 的週期。程式可以直接呼叫並納入第七章提供的 qc_mod15 及 iqft 函數建構量子模冪線路及逆量子傅立葉變換線路，並且以量子閘的形式加入量子線路中。程式的輸入為c及a(中間以空白隔開)，輸出結果為針對 counting bits由小而大排序，並分行列出counting bits以 及其對應的週期(中間以空白隔開)。 例如，若碰到test case的輸入為3 13，則輸出為:
000 1
010 4
100 2
110 4
- 15.
匈牙利演算法(Hungarian Algorithm)(HungarianAlg.zip)(Optional)
演算法課程 _0608(匈牙利演算法)影片
Homework 15: 本週只有兩題，因此每個學生都要做這兩題作業，但本週不需繳交影片與簡報。
A. 使用匈牙利演算法(Hungarian algorithm)來解以下的最小成本指派問題(assignment problem)（註: 必須寫出演算法執行過程中的每個中間結果）
B. 說明如何使用匈牙利演算法(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
