南台課程大綱
學年度 104學年第一學期 系所 電子系
課程名稱 圖形理論 班級 博研電子一甲,碩研電子一甲,碩研通訊一甲,海研電子一甲
授課教師 黎靖 點 閱 次 數 79
選修
選修
課程概述
本課程是圖形理論導論課程,目的為使同學了解圖形理論的基本原理及應用。本課程將教授圖形理論之基本定義、定理,並輔以期末專題研究,以強化學生分析、推理及解決問題之能力。
課程目標
本課程的目標在培養下列核心能力:
1.專業技能(50%): 具備圖形理論的基礎,知道如何使用圖形定義工程問題。
2.資訊能力(30%): 撰寫圖形問題的相關程式。
3.終身學習(10%): 採用英文教科書,訓練學生專業英文研讀能力。學生能搜尋演算法之相關期刊及網路資源。
4.報告溝通(5%): 藉由撰寫期末報告,訓練學生撰寫學術報告及發表的能力。
5.智財產權(5%): 了解演算法也可以申請專利,並認知與尊重智財權。
課程大綱
第1章 圖的性質與類型
1.1 專有名詞
1.2 相鄰矩陣表示法
1.3 相鄰串列表示法
1.4 樹
1.5 二元樹
1.6 有向圖
1.7 路徑
第2章 圖的搜尋
2.1深先搜尋
2.2深先搜尋演算法
2.3 廣先搜尋
2.4 一般化的圖形搜尋第
3章 有向圖與DAG
3.1專有名詞
3.2以深先搜尋剖析有向圖
3.3 Warshall演算法
3.4 DAG
3.5 拓普排序
3.6 有向圖的強連通單元
3.7 Tarjan演算法
3.8 Gabow演算法
第4章 最小展開樹
4.1表示法
4.2 MST演算法的深層原理
4.3 Prim演算法
4.4 Kruskal演算法
第5章 最短路徑
5.1 網路
5.2 最短路徑問題
5.3 Dijkstra演算法
5.4 任兩點間最短路徑
英文大綱
Chapter 1 Graph properties and types
1.1 Glossary
1.2 Adjacency-matrix graph representation
1.3 Adjacency-lists graph representation
1.4 Trees
1.5 Binary tree
1.6 Digraph representations
1.7 Simple, Euler, and Hamilton Paths
Chapter 2 Graph Search
2.1 Depth-First Search
2.2 DFS Algorithms
2.3 Breadth-First Search
2.4 Generalized Graph Search
Chapter 3 Digraphs and DAGs
3.1 Glossary
3.2 Anatomy of DFS in Digraphs
3.3 Warshall’s algorithm
3.4 DAGs
3.5 Topological Sorting
3.6 Strong components in digraphs
3.7 Tarjan’s algorithm
3.8 Gabow’s algorithm
Chapter 4 Minimum Spanning Trees
4.1 Representations
4.2 Underlying principles of MST algorithms
4.3 Prim’s Algorithm and Priority-First Search
4.4 Kruskal’s Algorithm
Chapter 5 Shortest Paths
5.1 Network and representations
5.2 Shortest Path Problems
5.3 Dijkstra’s Algorithm
5.4 All-Pairs Shortest Paths
下載
Doc Pdf
連結(一) 連結(二)

上一頁