演算法在繞線問題的實務應用
The applications of algorithms on routing problems
| 節 | 週一 |
|---|---|
3 10:10–11:00 | 演算法在繞線問題的實務應用 ED301 2 節連堂 |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
課程概述與目標： The goal of this course is to help undergraduate students to learn how to apply the knowledge of algorithms to resolve the problems of various topics. The shortest path problem is a fundamental and well-known problem for CS students. Its variants belong to NP problems and can be found in many fields, including network, robotic mouse, auto-pilot, and chip design, generally named as routing problems. The curriculum design involves case study of different routing problems, by which you can learn to employ proper algorithms for tackling different routing problems imposed by specific constraints and objectives. The case studies are designed for senior undergraduate students, where students can learn the model establishment for tackling optimization problems and the selection of suitable algorithms. The practice of three programming assignments can help students to accumulate more experience of designing algorithms to explore optimized solutions and debugging programs with a large set of benchmarks. 本課程主要在幫助大學生從具備演算法知識進而初窺最佳化研究中各種演算法如何適當地加以應用以解決問題。路徑搜尋問題是資訊領域新生就熟知的問題，在各個領域中存在著許多不同屬於NP問題的變種路徑搜尋問題，也被稱為繞線問題，例如網路、機器鼠、自動導航到晶片設計最佳化與自動化領域。課程的設計是由基礎的最短路徑問題到衍生為各領域的特定繞線問題，透過不同問題案例的研讀，可以進一步了解不同演算法適用於解決具有某些特徵的問題與限制。 問題案例的選擇以適合大三大四大學部學生為主，目標是讓大學部學生透過問題案例研讀了解最佳化問題的模型建立與選擇適合的演算法。透過三個佐以真實世界複雜測資的程式專案，讓同學初步體驗以後研究工作跟大學以課程學習為主的差異、增加不同類型最佳化演算法的設計經驗，以及學習大型測資下的程式優化與除錯。
Data structure, algorithm
handouts
3 programming projects: 75%. Note: You can use any AI-assisted tools, such as LLMs or vibe coding utilities. Final exam: 25%
| 週次 | 主題 |
|---|---|
| 第 1 週 | 1. Algorithm review. 2. Introduction to the routing problem. 3. Background knowledge for the course. 4. Channel routing - left-edge and greedy algorithms. |
| 第 2 週 | 1. Channel routing - left-edge and greedy algorithms - continue. 2. Channel routing - graph algorithms. 3. Project 1 - greedy channel routing. |
| 第 3 週 | 1. Channel routing - graph algorithms - continue. 2. River routing - heuristic algorithms. |
| 第 4 週 | 1. River routing - heuristic algorithms. 2. Maze routing on a weighted map - variant BFS. |
| 第 5 週 | 1. Global routing - multi-level/hierarchical optimization algorithms, Integer linear programming, dynamic programming. |
| 第 6 週 | 1. Global routing: multi-level/hierarchical optimization algorithms, Integer linear programming, dynamic programming - continue. 2. Project 2 - DP based global routing. |
| 第 7 週 | 1. Track routing - graph algorithm 2. Detailed routing - simulated annealing algorithm, simulated evolution algorithm. |
| 第 8 週 | 1. Detailed routing: simulated annealing algorithm, simulated evolution algorithm - continue. 2. Multi-Layer Obstacle-Avoiding Rectilinear Steiner Tree: Local search algorithm. |
| 第 9 週 | 1. Multi-Layer Obstacle-Avoiding Rectilinear Steiner Tree - Local search algorithm - continue. 2. Cell routing - concurrent algorithms with Satisfiability (SAT)/Max SAT and Integer linear programming. |
| 第 10 週 | 1. Cell routing - concurrent algorithms with Satisfiability (SAT)/Max SAT and Integer linear programming - continue. |
| 第 11 週 | 1. PCB/Escape routing - concurrent algorithms with Satisfiability(SAT)/Max SAT, network flow, and integer linear programming. 2. Project 3 - Concurrent routing using SAT, network flow, or integer linear programming. |
| 第 12 週 | 1. Package routing - network flow algorithm. |
| 第 13 週 | 1. Length-matching routing: Lagragian relaxation optimization. |
| 第 14 週 | 1. Robotic mouse mazing: Dijkstra algorithm and flood fill algorithm. 2. Automatic navigation beyond Google map - Traffic jam prediction: Variant Dijkstra Algorithm. |
| 第 15 週 | 1. Course review. |
| 第 16 週 | Final exam. |
| 第 17 週 | |
| 第 18 週 |
Main: IEEE/ACM conference proceeding: https://ieeexplore-ieee-org.ezproxy.lib.nctu.edu.tw/Xplore/home.jsp Reference: 1. Introduction to algorithms by Thomas H. Cormen et al. 2. Approximation algorithms by Vijay V. Vazirani 3. Graph Theory and Its Applications by Jonathan L. Gross and Jay Yellen 4. VLSI Physical Design Automation by Sadiq M. Sait and Habib Youssef
- 地點
- EBIII 441
- 時間
- Mon 5,6 or appointment by emails
- 聯絡方式
- ylli@cs.nctu.edu.tw 5131364