計算方法之實務應用

Practical/Real-Life Applications of Computational Algorithms

學期

109-2

學分

3 學分

當期課號

5274

永久課號

IOC5215

開課單位

資訊科學與工程研究所

授課教師

吳凱強

校區

光復

類別

選修

上課時間表

節	週一
N 12:20–13:10	計算方法之實務應用 ED302 3 節連堂
5 13:20–14:10
6 14:20–15:10

* 根據陽明交大上課時間表所列

概述

這門課將會介紹一些計算方法及其實務上的應用,包括在1970年代第一個被證明為NP-complete問題的Boolean satisfiability (SAT),解決這個問題的方法在1990年代開始有突破性的發展,也因此近年來,有很多被認為是很複雜的問題,例如數獨、著色問題、邏輯驗證,在轉成SAT問題後迎刃而解;然後是著名的Viterbi演算法,它被用於一些通訊及訊號處理的應用上;也會介紹被廣泛使用在機器學習領域的決策樹(decision tree)及其衍生的決策圖(decision diagram),這是2007年Turing Award得主Edmund Clarke用來解決symbolic model checking的最主要方法;另外會介紹如何系統化地對數位電路做pipelining及retiming以達到效能的最佳化,這個問題可以完美地轉成最短路徑問題,進而有效地解決;生物科技領域裡很重要的DNA比對也會介紹到,其中將包括精準比對(exact matching)和非精準比對(inexact matching)兩類;最後,一些常用於不同領域的最佳化技巧如蟻群最佳化、蜂群最佳化、粒子群移動最佳化,都會涵蓋於這門課中。

先修科目

Programming in C/C++ (required) Data Structures and Algorithms (preferred but not required)

教學方式

http://e3new.nctu.edu.tw/

評分方式

Homework: 30% (~4 programming assignments) Project: 30% (2+1 milestones) Exam: 30% (1 final exam) Participation: 10%

週次計畫

週次	主題
第 1 週	Introduction and syllabus
第 2 週	Review of computational algorithms/backtracking
第 3 週	Review of computational algorithms (Boolean satisfiability, dynamic programming, graph traversal, etc)
第 4 週	Boolean satisfiability - historical review
第 5 週	Boolean satisfiability - state of the art
第 6 週	Decision tree/diagram
第 7 週	Introduction to Python & PyEDA
第 8 週	FSM verification based on reachability analysis
第 9 週	Midterm for Project X
第 10 週	Google's PageRank algorithm and Markov chain
第 11 週	Viterbi algorithm and hidden Markov model
第 12 週	Pipelining and retiming
第 13 週	Bioinformatics (suffix tree for exact matching)
第 14 週	Bioinformatics (dynamic programming for inexact matching)
第 15 週	Simulated annealing and genetic algorithm
第 16 週	Ant/bee colony and particle swarm optimization
第 17 週	Project X presentation
第 18 週	Project X presentation

教科書

No required textbook

Office Hours

地點: EC530
時間: Monday after class (3:10pm ~ 4:10am) and by appointment
聯絡方式: Tel: 54734 (校內分機) E-mail: kcw@cs.nctu.edu.tw