DesignandAnalysisofComputerAlgorithms

王宏志計(jì)算機(jī)科學(xué)與工程系課程介紹Instructor:

王宏志Room:D33Office:

綜合樓810房間

Email:

wangzh@Gtalk:

whongzhi@QQ:565063647InformationaboutInstructorHomeworkandExam.Homework:

30%FinalExam(WrittenTest):

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

本文解決了什么問(wèn)題

采用什么思想解決這個(gè)問(wèn)題

基本算法的描述

算法分析的結(jié)論

用一個(gè)例子說(shuō)明相關(guān)算法。2.根據(jù)選擇的論文，調(diào)研相關(guān)領(lǐng)域，寫(xiě)一篇小綜述，包括如下內(nèi)容：

相關(guān)領(lǐng)域的問(wèn)題的分類

每類問(wèn)題解決方法的分類

逐個(gè)簡(jiǎn)介每種方法(每種方法一小段)

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

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

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

1.

IEEETransactionsonComputers2.

IEEETransactionsonSoftwareEngineering3.

IEEETransactionsonDataandKnowledgeEngineering4.

ActaInformatica5.

SIAMJournalonComputing6.

JournalofComputerandSystemSciences7.

CommunicationoftheACM8.

JournaloftheACM9.

BITImportantJournals10.

InformationandControl11.

ACMComputingSurveys12.

MathematicsofComputation13.

InformationProcessingLetters14.

TheoreticalComputerScience15.AlgorithmicaImportantConferences1.AnnualACMSymposiumonTheoryofComputing2.AnnualIEEESymposiumonFoundationsofComputerScience3.ACMAnnualComputerScienceConference4.AnnualSymposiumonComputationalGeometry5.ACMSymposiumonParallelAlgorithmsandArchitectures.OnlineJudgeMOOC入門(mén)篇/learn/HIT-1000002012進(jìn)階