lecture 1introduction

《lecture 1introduction》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lecture1IntroductionLecturer:HanLinSomethingaboutme…1999.9～2003.7中山大学计算机科学与技术专业本科2003.9～2005.7中山大学计算机软件与理论专业硕士生（硕博连读）2005.9～2008.7中山大学计算机软件与理论专业博士导师：苏开乐教授2008.7～中山大学计算机科学系讲师Somethingaboutme…姓名：林瀚Homepage:http://www.cs.sysu.edu.cn/~lh/Email:linhan095@gmail.comSomething

2、aboutthiscourseCoursePage:http://www.cs.sysu.edu.cn/~lh/algorithms.htmlBBS:http://bbs.sysu.edu.cn/bbsdoc?board=ACMICPCOfficeHours:每周一下午3：00～5：00，信息学院楼616E其它时间可邮件预约Somethingaboutthiscourse1.平时作业：书面作业+编程练习2.研究型的小Project：选一个问题，编程实现解决这一问题的若干种算法，在不同规模的测试数据上，比较各种算法的性能3.期末考试

3、：ACM方式,自动测评FAQQ:这门课是为了培养参加ACM比赛的队员而专门开设的吗？A:No.SomeimportanttopicsnotincludedinACMICPC•AdvancedAlgorithmAnalysisTechniques•NP-CompletenessProofs•RandomizedandApproximationAlgorithms•QuantumAlgorithms推荐书籍教材推荐书籍特点：有较多源代码，适合学习算法的同时提高编程能力高深秘笈DonaldKnuthTuringAward(1974)开课

4、第一问•什么是算法？Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.－－《算法导论》KnuthSaid…Knuth(1968,1973)hasgivenalistoffivepropertiesthatarewidelyacceptedasrequirementsforanalgorithm:

5、Finiteness:"Analgorithmmustalwaysterminateafterafinitenumberofsteps...averyfinitenumber,areasonablenumber"Definiteness:"Eachstepofanalgorithmmustbepreciselydefined;theactionstobecarriedoutmustberigorouslyandunambiguouslyspecifiedforeachcase"Input:"...quantitieswhichar

6、egiventoitinitiallybeforethealgorithmbegins.Theseinputsaretakenfromspecifiedsetsofobjects"Output:"...quantitieswhichhaveaspecifiedrelationtotheinputs"Effectiveness:"...alloftheoperationstobeperformedinthealgorithmmustbesufficientlybasicthattheycaninprinciplebedoneexac

7、tlyandinafinitelengthoftimebyamanusingpaperandpencil"Finally…Thewordalgorithmdoesnothaveagenerallyaccepteddefinition.FromwikipediaSo,nextquestion.为什么学习算法？原因之一：广泛的应用•HumanGenomeProject•Internet•Electroniccommercesecurity•Othermanufacturingandcommercialsetting•Etc.为什么学习

8、算法？原因之二：强大的力量为什么学习算法？原因之三：Justforfun!一个简单例子：插入排序问题：对于一个算法，我们要提出什么问题？问题一为什么这个算法是正确的？利用循环不变式来证明算法的正确性，其一般步骤如下：插入排序的正确性证明见课本p18