中正大學課程大綱
課程名稱(中文)： 近似演算法與網路應用 開課單位： 資訊工程研究所(Graduate Institute of Computer Science and Information Engineering)
課程名稱(英文) Approximation Algorithms and Applications to Networks 課程代碼 4105329_01
授課教師： 郭建志 學分數 3
必/選修 選修 開課年級 碩博合開
先修科目或先備能力：
Discrete Mathematics, Algorithms
課程概述：
Many discrete optimization problems in networks are NP-hard and we cannot obtain the optimal solution for these problems in polynomial time unless P=NP. Therefore, we employ approximation algorithms to come as close as possible to the optimum value in polynomial time, rather than guarantee the best solution. The area has developed many deep and beautiful mathematical results over the years, and it is inherently interesting to study these. In this course, we will study how to obtain a near optimal solution for these problems and their applications in networks.
學習目標：
1. Learn to design approximation algorithms
2. Learn to analyze performance of approximation ratios
3. Learn to improve the design based on the analysis
4. Algorithm implementation and application study (optional)
教科書：
The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge

課程大綱 分配時數 核心能力 備註
單元主題 內容綱要 講授 示範 隨堂作業 其他
Introduction to approximation algorithm 12345678
Greedy algorithm and local search 12345678
Rounding data and dynamic programming 12345678
Deterministic/randomized rounding of linear programming 12345678
Primal-dual method 12345678
Group Presentation 12345678

教育目標
1.具獨立從事學術研究或產品創新研發之人才
2.具團隊合作精神及科技整合能力，並在團隊中扮演領導、規劃、管理之角色
3.具自我挑戰與終身學習能力之人才
4.具有學術倫理、工程倫理、國際觀之人才

核心能力
1.具有資訊工程與科學領域之專業知識(Competence in computer science and computer engineering.)
2.具有創新思考、問題解決、獨立研究之能力(Be creative and be able to solve problems and to perform independent research.)
3.具有撰寫中英文專業論文及簡報之能力(Demonstrate good written, oral, and communication skills, in both Chinese and English.)
4.具策劃及執行專題研究之能力(Be able to plan and execute projects.)
5.具有溝通、協調、整合及進行跨領域團隊合作之能力(Have communication, coordination, integration skills and teamwork in multi-disciplinary settings.)
6.具有終身學習與因應資訊科技快速變遷之能力(Recognize the need for, and have the ability to engage in independent and life-long learning.)
7.認識並遵循學術與工程倫理(Understand and commit to academic and professional ethics.)
8.具國際觀及科技前瞻視野(Have international view and vision of future technology.)

請尊重智慧財產權，不得非法影印教師指定之教科書籍

教學要點概述：
1. 教材編選(可複選)：自編簡報(ppt)教科書作者提供
2. 教學方法(可複選)：講述板書講述
3. 評量工具(可複選)：上課點名 0%, 隨堂測驗0%, 隨堂作業0%, 程式實作0%, 實習報告0%,
                       專案報告0%, 期中考0%, 期末考0%, 期末報告0.00%, 其他0.00%,
4. 教學資源：課程網站 教材電子檔供下載 實習網站
5. 教學相關配合事項：

課程目標與教育核心能力相關性        
請勾選：12345678
1 具有資訊工程與科學領域之專業知識(Competence in computer science and computer engineering.)
為何有關：
達成指標：
評量工具(可複選)：
2 具有創新思考、問題解決、獨立研究之能力(Be creative and be able to solve problems and to perform independent research.)
為何有關：
達成指標：
評量工具(可複選)：