課程名稱:演算法

英文名稱:Algorithms

學年、學期、學分數/時數:第三學年、第二學期、3學分/3小時

先修課程:程式設計() 程式設計()資料結構

後續延修課程:

教學目標:1. 了解演算法複雜度等級的概念(知識)

2. 熟習常用的演算法設計技巧(知識)

3. 了解NP-Complete理論(知識)

培育(實務)能力:能學會演算法設計技巧於程式設計的應用。

達成本系教育目標:

培養具資訊工程之實務能力的人才(目標1)

培養具資訊工程之專業知能與資訊倫理兼備的人才(目標2)

達成本系學生核心能力:

培養學生具備紮實的理論基礎能力(能力1)

培養學生具備專精的實作能力(能力2)

教材大綱

單元主題

內容綱要

備註

一、課程簡介

1.1課程目的、進度、評分方式

1.2演算法效能及分析

1.3時間及空間複雜度

1.4複雜度等級

作業1

二、計算複雜度

2.1排序問題

2.2搜尋問題

作業2

三、演算法設計

3.1Divide-and-Conquer

3.2Dynamic Programming

3.3Greedy Approach

3.4Backtracking

作業3

四、計算複雜度及棘手問題

4.1P vs. NP

4.2NP-Complete理論

4.3NP-Complete問題

作業4