資訊工程研究所(Graduate Institute of Computer Science and Information Engineering)
課程名稱(英文)
Computer Algorithms
課程代碼
4105310_01
授課教師：
黃耀廷
學分數
3
必/選修
必修
開課年級
研究所
先修科目或先備能力：
Computer programming for at least two years. Data structure and algorithms in undergraduate levels.
課程概述：
This course will introduce conventional algorithms for solving optimization problems. Specifically, deterministic, randomized, and relaxation methods for proving NP-hard problems will be presented. Applications of these problems and algorithms will be introduced in relevant topics.
學習目標：
1. Design and analysis of algorithms for P and NP-hard problems
2. Strategies for solving NP-hard problems
教科書：
Introduction to Algorithms, Cormen Online resources at https://ecourse2.ccu.edu.tw/
(請尊重智慧財產權，不得非法影印教師指定之教科書籍)
課程大綱
分配時數
核心能力
備註
單元主題
內容綱要
講授
示範
隨堂作業
其他
Review of divide and conquer
Dynamic programming, string index, graph problems
9
12345678
P, NP, and NP-completeness
Defines class P, class NP, NP-hard and NP-complete, and presents proofs using SAT, clique and subset sum problems as examples
9
12345678
Approximation algorithms
Introduce basic approximate algorithms and analysis techniques for solving NP-hard problems.
9
12345678
Randomized algorithms
Introduce randomized approximation algorithm and analysis techniques.
6
12345678
Relaxation strategies
Introduce linear- and semidefinite-programming relaxation with randomized rounding
9
12345678
Inapproximability and intractibility
Introduce lower bounds of approximation algorithms and the tractability of problems.
6
12345678
Polynomial-time approximation scheme
Defines PTAS and FPTAS by giving examples such as subset sum.
6
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.)
具有資訊工程與科學領域之專業知識(Competence in computer science and computer engineering.)
為何有關：
This course introduce the algorithms for solving NP-hard problems in computer science.
達成指標：
The students will be evaluated by quiz, homework assignmetns, midterms, and final exams.
評量工具(可複選)：
Evaluation is based on in-class quizzes, homework assignments, and midterm and final examinations. The grading levels are defined as follows:
Level 5: Has submitted at least 80 % of all homework assignments, or projects a semester grade of 80 or above, or has achieved a report grade of 80 or above.
Level 4: Has submitted at least 60 % of all homework assignments, or projects a semester grade of 70 or above, or has achieved a report grade of 70 or above.
Level 3: Has submitted at least 40 % of all homework assignments, or projects a semester grade of 60 or above, or has achieved a report grade of 60 or above.
Level 2: Has submitted at least 20 % of all homework assignments, or projects a semester grade of 50 or above, or has achieved a report grade of 50 or above.
Level 1: Has submitted no homework assignments, or projects a semester grade below 50, or has achieved a report grade below 50.