算法1_算法求解基础_大校
算法设计与分析,张怡婷Email:zytnjupt.edu.cnPhone:13951927531,课前简介,课程学时：48学时(40+8)平时成绩考核办法：点名作业实验报告考试时间、方式19周（之前），闭卷答疑时间、地点周五上午第2小节，教2-316,学习要求：预习动手实现上课认真听讲，在书上作适当的标记和注释课后复习,随堂提问课堂练习学习报告,算法与数据结构的关系,算法是数据结构的灵魂：不了解施加于数据上的算法就无法决定如何构造数据。反之，数据结构又是算法的基础：算法的结构和选择又常常在很大程度上依赖于数据结构。,算法+数据结构=程序,学习算法不外乎两个目的：一是了解各种算法，在遇到问题时能灵活的应用所掌握的方法技巧；二是研究算法设计技术，当没有现成可用的算法时，能够创造出问题的求解方法。,算法怎么学？,前者很实际，后者很重要。,课程学习目标,Learning to solve real problems that arise frequently in computer application学习计算机应用中求解实际问题的有效算法Learning the basic principles and techniques used for answering the question: “How good, or, how bad is the algorithm”学习评价算法好/坏的基本原理和技巧Getting to know a group of “very difficult problems” categorized as “NP-Complete”学习NP-Complete问题的相关理论和算法,课程主要章节内容：Ch1 算法问题求解基础Ch2 算法分析基础（算法复杂度概念）算法设计策略、算法分析和证明Ch5 分治法Ch6 贪心法Ch7 动态规划法Ch8 回溯法Ch9 分枝限界法Ch10 NP完全问题Ch13 密码算法,课程内容,课程参考书,ClassicsDonald E.Knuth. The Art of Computer ProgrammingVol.1 Fundamental Algorithms基本算法Vol.2 Seminumerical Algorithms半数字化算法Vol.3 Sorting and Searching排序与搜索Popular textbooksThomas H.Cormen, etc. Introduction to AlgorithmsAlfred V.Aho,John E.Hopcroft,Jeffrey D.Ullman. The Design and Analysis of Computer AlgorithmsUdi Manber. Introduction to Algorithms-A Creative ApproachRobert Sedgewick. Algorithms in C/C+/Java(with different versions using different programming languages)Advanced mathematical techniquesGraham, Knuth, etc. Concrete Mathematics: A Foundation for Computer Science具体数学（连续数学+离散数学）,其他参考书1 王晓东.计算机算法设计与分析.电子工业出版社，2001.2 Jon Bentley著，黄倩,钱丽艳译，编程珠玑（第2版）.人民邮电出版社，2008. 3 卢开澄，计算机算法导引设计与分析.清华大学出版社，1996.4 Jon Kleinberg, Eva Tardos著，张立昂，屈婉玲 译，算法设计.清华大学出版社，2007.网上学习资料MIT OpenCourseWare | Electrical Engineering and Computer Science（MIT开放式课件 | 电气工程与计算机科学）http:/www.core.org.cn/OcwWeb/Electrical-Engineering-and-Computer-Science/index.htm课件资料下载 http:/class.njupt.edu.cn,上机安排,上机时间和地点分治策略第7周周五（4月 4日） 第1大节（ 8:00- 9:35）动态规划法第11周周五（5 月 2 日） 第1大节（ 8:00- 9:35）回溯法第13周周五（5月 16日） 第1大节（ 8:00- 9:35）密码算法第14周周五（5月 23 日） 第1大节（ 8:00- 9:35）地点：教2-316（软件与信息安全实验室）先修课程： 高级语言程序设计、面向对象程序设计、数据结构,第1章 算法问题求解基础,学习要点：理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。章节内容：1.1 算法概述1.3 算法设计与分析,An Arabian mathematician AbAbud Allh Muhammad ibn Ms al-Khwrizm (c.780-c.850?) wrote the famous “Persian text-book” titled Kitb al-jabr wal-muqbala”,Algebra,Algorism,Algorithm,Algorithm的由来,Arithmetic,1.1 算法概述,An algorithm is a precise description of the process of solving a problem, consisting of finite number of instructions which can be executed mechanically and produce a deterministic result.算法是对某个问题求解方案的完整而明确的描述，是指令的有限序列。Five important features（五个重要特征）:Finiteness有穷性（算法必须总能在执行有限步之后终止）Definiteness确定性（组成算法的每一条指令都是清晰，无歧义的）Input输入（算法有零个或多个外部提供的输入量）Output输出（算法至少产生一个输出量）Effectiveness可行性（算法的每一条指令必须足够基本，能够通过已经实现的基本运算执行有限次来实现）,算法与程序,程序(Program)是算法用某种程序设计语言的具体实现。算法必须可终止，程序却没有这一限制。即：程序可以不满足算法的性质(5)“有穷性”。例如：操作系统是一个在无限循环中执行的程序，却不是算法。因此操作系统是使用计算机语言描述的一个计算过程，而不是一个算法。,算法描述,描述一个算法可以用自然语言、流程图、伪代码和程序设计语言。,经典算法举例,欧几里德算法（辗转相除法）：求两整数m和n的最大公约数(0m<n),欧几里德算法,m,n,r, 输入m 和n； 求n除以m的余数r； 若r等于0，则m为最大公约数，算法结束； 否则执行第步； 将m的值放在n中，将r的值放在m中； 重新执行第步。,自然语言描述：,流程图描述：,伪代码描述：,1. r = n % m; 2. 循环直到 r 等于0 2.1 n = m; 2.2 m = r; 2.3 r = n % m; 3. 输出 m ;,程序设计语言描述（递归）：,int RGcd(int m,int n) /欧几里德递归算法if (m=0) return n; /终止条件return RGcd(n%m,m);,尾递归,int Gcd(int m,int n)if (m>n) Swap(m,n);return RGcd(m,n);,程序1-1 欧几里德算法（递归）void Swap(int ,程序1-2 欧几里德算法（迭代）void Swap(int ,程序设计语言描述（迭代）：,可见：一个问题可以设计不同的算法来求解。同一个算法可采用不同的形式来表示。,程序1-3 连续整数检测int Gcd(int m,int n)if (m=0) return n;if (n=0) return m;int t=m>n?n:m;while (m%t|n%t) t-;return t;,程序设计语言描述（连续整数检测）：,小思考,若不事先比较m和n的大小，如何实现欧几里德算法？,int Gcd(int m,int n) while (m!=0 ,程序是否一定会在有限步之内终止？,小思考,m*n /Gcd(m,n),如何求最小公倍数？,算法的重要性（ Algorithm Everywhere ）,ApplicationsHuman Genome Project: identifying 100000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis. （卡普Karp ->华盛顿）Internet service: e.g. routing the dataElectronic commerce: public-key cryptography and digital signaturesSystemsHardwareOperating systemsCompilers（克努特Knuth-LR(k)文法）,假设某一负责人交给你一个很难的任务，几天后询问你问题解决了没有。可能会发生如下图这样的情况：,问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，没能完成任务。”,问：“交给你的问题，解决方案设计出来了吗？”答： “我找不到一个有效的算法来解决它，因为这样的算法是不存在的。”,不过，要证明一个问题不存在有效算法，往往跟寻找有效算法一样难。,问：“交给你的问题，解决方案设计出来了吗？”答： “我找不到一个有效的算法来解决它，但不是我不行，因为所有这些名人也都找不到解决它的有效算法。”,Philosophy of Problem Solving,To distinguish between the two classes, we use our wit.,算法与图灵奖超过1/3的Turing奖获奖者其成果与算法有关,1974 - Donald Knuth(Stanford): “The Art of Computer Programming”1976 - Michael Rabin(Hebrew) & Dana Scott(Oxford): Nondeterministic Finite State Automata (NDFSA)1982 - Stephen Cook(Toronto): Satisfiability of Proposition Calculus is NP-complete1985 - Richard Karp(UC Berkley): Branch-and-Bound Method1986 - John Hopcroft(Cornell) & Robert Tarjan (Princeton): Graph algorithms,
