算法設計與分析 ch0a 學習課件

DesignandAnalysisofComputerAlgorithms

王宏志計算機科學與工程系課程介紹Instructor:

王宏志Room:D33Office:

綜合樓810房間

Email:

wangzh@Gtalk:

whongzhi@QQ:565063647InformationaboutInstructorHomeworkandExam.Homework:

30%FinalExam(WrittenTest):

70%QQ群：？？InformationaboutClass作業(yè)1.在相關期刊或者會議今年(2016)的論文中找到自己感興趣的算法類論文，讀懂，寫一篇論文概述，包括以下內容：

本文解決了什么問題

采用什么思想解決這個問題

基本算法的描述

算法分析的結論

用一個例子說明相關算法。2.根據(jù)選擇的論文，調研相關領域，寫一篇小綜述，包括如下內容：

相關領域的問題的分類

每類問題解決方法的分類

逐個簡介每種方法(每種方法一小段)

比較解決每種問題的解決方法3.描述已有算法的不足(包括已有算法的問題，可以改進的地方，不適用的情況)4.針對當前算法的不足，提出新算法解決之并進行分析和論述討論為何能夠有效的解決當前算法的不足。2016年的:STOC,FOCS,SODA,VLDB,SIGMOD,KDD,ICDE,JACM,TCSOutlineofthecourse1.緒論（2學時）算法的概念、算法設計與分析的目的、意義和一般過程。2.數(shù)學基礎（2學時）算法復雜性函數(shù)的階、和式的估計與極限，遞歸方程的建立及其基本求解方法。3.排序與分治算法（4學時）排序問題與基本排序算法的分析，分治技術和基于分治技術的排序算法，基于比較的排序算法的時間復雜度下界。4.動態(tài)規(guī)劃技術（4學時）動態(tài)規(guī)劃技術的基本原理，矩陣鏈乘法、序列比對、0-1背包等問題的動態(tài)規(guī)劃算法。5.貪心算法（4學時）貪心算法的基本原理，單位時間活動安排問題、Huffman編碼問題、最小生成樹問題。6.搜索算法（4學時）Best-first算法、爬山法、分支界限算法、A*算法的基本概念及實例。7.圖論算法（4學時）最短路徑算法；二分圖匹配算法。8.字符串匹配算法（4學時）字符串匹配問題及經典的字符串匹配算法；關鍵字樹和后綴樹的概念、構建算法及其應用。References1.

ThomasH.Cormen,CharlesE.Leiserson,andRonaldL.Rivest.IntroductiontoAlgorithms,

TheMITPress,第三版,2012.2.王曉東，計算機算法設計與分析，電子工業(yè)出版社，2001。

1.

IEEETransactionsonComputers2.

IEEETransactionsonSoftwareEngineering3.

IEEETransactionsonDataandKnowledgeEngineering4.

ActaInformatica5.

SIAMJournalonComputing6.

JournalofComputerandSystemSciences7.

CommunicationoftheACM8.

JournaloftheACM9.

BITImportantJournals10.

InformationandControl11.

ACMComputingSurveys12.

MathematicsofComputation13.

InformationProcessingLetters14.

TheoreticalComputerScience15.AlgorithmicaImportantConferences1.AnnualACMSymposiumonTheoryofComputing2.AnnualIEEESymposiumonFoundationsofComputerScience3.ACMAnnualComputerScienceConference4.AnnualSymposiumonComputationalGeometry5.ACMSymposiumonParallelAlgorithmsandArchitectures.OnlineJudgeMOOC入門篇/learn/HIT-1000002012進階