|
課程名稱 |
學士班專題研究二
Special Project for Undergraduate (Ⅱ) |
|
開課學期 |
114-2 |
|
授課對象 |
數學系 |
|
授課教師 |
沈俊嚴 |
|
課號 |
MATH3003 |
|
課程識別碼 |
201 45170 |
|
班次 |
05 |
|
學分 |
2.0 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
|
|
上課地點 |
|
|
備註 |
初選不開放。
總人數上限：5人 |
|
|
|
|
課程簡介影片 |
|
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
The content follows the textbook with possible revision if necessary. It includes at least first six chapters of the following contents.
1. Introduction to Domination in Graphs
2. Design and Analysis of Algorithms
3. Trees
4. Chordal Graphs
5. Interval Graphs
6. Strongly Chordal Graphs
7. Cocomparability Graphs and Asteroidal Triple-Free Graphs
8. Permutation Graphs
9. Distance-Hereditary Graphs |
|
課程目標 |
The purpose of this course is to introduce domination and its variations in graphs from an algorithmic point of view. In the process of achieving this, we discuss the structures of various graph classes, including trees, chordal graphs, strongly chordal graphs, interval graphs, cocomparability graphs, permutation graphs, distance-hereditary graphs and generalizations of these graphs. These structure properties provide concepts for designing the algorithms.
While there are many algorithms on variations of domination, the attempt of this course is not to discuss all of them. On the other hand, we make a systematic introduction to the main methods used, including the labeling approach, the dynamic programming approach and the primal-dual approach. |
|
課程要求 |
|
|
預期每週課前或/與課後學習時數 |
|
|
Office Hours |
另約時間 備註： 預約時間 (email: gjchang@math.ntu.edu.tw)。 |
|
指定閱讀 |
G. J. Chang, Algorithmic Aspects of Domination in Graphs, World Scientific Publishing, Singapore, 2026. |
|
參考書目 |
請到數學系圖書館課程參考區參考
1. G. J. Chang, Algorithmic Aspects of Domination in Graphs, World Scientific Publishing, Singapore, 2026.
2. D. B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, Upper Saddle River, NJ, 2001.
3. 張鎮華、蔡牧村，演算法觀點的圖論，修訂版，台大出版中心，台北，2020。
4. M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
5. T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1998.
6. T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
7. T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Domination in Graphs: Core Concepts, Springer Nature Switzerland AG, Cham, Switzerland, 2023. |
|
評量方式
(僅供參考) |
- 本校尚無訂定 A+ 比例上限。
- 本校採用等第制評定成績，學生成績評量辦法中的百分制分數區間與單科成績對照表僅供參考，授課教師可依等第定義調整分數區間。詳見學習評量專區 (連結)。
|
|
針對學生困難提供學生調整方式 |
|
上課形式 |
提供學生彈性出席課程方式 |
|
作業繳交方式 |
書面報告取代口頭報告 |
|
考試形式 |
|
|
其他 |
由師生雙方議定 |
|
|
週次 |
日期 |
單元主題 |
|
第0週 |
說明 |
上課時間：週一 13:00 ~ 16:00。
上課地點：天文數學館 302 室。
以下進度為初步設定，將視實際上課情況適當調整。實際授課進度請看課程內容。 |
|
第1週 |
2026-02-23 |
1. Introduction to Domination in Graphs
|
|
第2週 |
2026-03-02 |
2. Design and Analysis of Algorithms
|
|
第3週 |
2026-03-09 |
3. Trees
|
|
第4週 |
2026-03-16 |
3. Trees |
|
第5週 |
2026-03-23 |
4. Chordal Graphs
|
|
第6週 |
2026-03-30 |
4. Chordal Graphs |
|
第7週 |
2026-04-06 |
5. Interval Graphs
|
|
第8週 |
2026-04-13 |
5. Interval Graphs |
|
第9週 |
2026-04-20 |
6. Strongly Chordal Graphs
|
|
第10週 |
2026-04-27 |
6. Strongly Chordal Graphs |
|
第11週 |
2026-05-04 |
7. Cocomparability Graphs and Asteroidal Triple-Free Graphs
|
|
第12週 |
2026-05-11 |
7. Cocomparability Graphs and Asteroidal Triple-Free Graphs |
|
第13週 |
2026-05-18 |
8. Permutation Graphs
|
|
第14週 |
2026-05-25 |
8. Permutation Graphs |
|
第15週 |
2026-06-01 |
9. Distance-Hereditary Graphs |
|
第16週 |
2026-06-08 |
9. Distance-Hereditary Graphs |
|