算法分析与设计介绍.pptxVIP

算法分析与设计 董强 电子科大计算机学院 自我介绍 董强，2010年12月于重庆大学计算机专业博士毕业。科研兴趣包括图论互连网络、故障诊断和异常检测等。承担了2011年肖鸣宇副教授主讲的《算法分析与设计》课程的助教和实验教学工作。 Cell:Email: qdong1984@ 2009, Niagara Falls 欢迎! 你是否在思考这些问题吗? 我们为什么要学习算法课程? 在这门课程中我们能够学到什么? 这个老师怎么样? 考试是否容易通过? 我不擅长数学. 我基础不好 我英语很差 没问题　 上课要求 关掉手机铃声 不准在课堂上打电话 缺课影响平时成绩 按时提交作业 雷同作业成绩零分 课程基本信息 课程性质及学时:专业核心课程，讲授40学时，实验8学时 上课时间及地点:时间: 星期三3-4节 （单周）  星期五1-2节 （每周）地点: 清水河校区A313 成绩计算:平时成绩 10% 期中考试 10% 实验10% 期末考试 70% 课程主页: /dongqiang/ 课程基本信息 2011年信息安全专业肖鸣宇老师《算法》课程:选修人数: 100参加期末考试人数: 100不及格人数:20左右 最高分: 90+ 建议:1. 如果你不喜欢数学、分析、逻辑，那么你可能要多花点时间才能把这门课程学好。2. 上课认真听讲，不懂就问，这远比你课下自己看书效率高得多。3. 尤其要注意课堂上重点讲述的内容，这些将是考试的重点。 教材及参考书目 教材： 王晓东，计算机算法设计与分析，电子工业出版社出版，2008 参考书： 张德富 ，算法设计与分析 ，国防工业出版社 J. Kleinberg， E. Tardos, Algorithm design，Addison Wesley， 2005 Cormen，Leiserson，Rivest，Stein，算法导论（第二版 影印版），高等教育出版社，2007 课程简介 课程主要介绍计算机算法分析、算法设计及复杂性理论的基本概念、基本的算法分析方法和常用的算法设计方法。 课程目标： 掌握计算机算法分析的基本方法及常见算法设计方法 训练逻辑思维 利用常见的算法设计方法解决科学研究和软件开发中的实际问题 先修课程： 离散数学、数据结构、高级程序设计语言。 课时安排 介绍 (2学时) 算法分析基础 (2学时) 分而治之算法 (8学时) 动态规划算法 (8学时) 贪心算法 (6学时) 回溯法、分支限界法 (6学时) 算法复杂度入门 (4学时) 期中考试 (2学时) 作业评讲 (1学时) 期末复习 (1学时) 算法是计算机科学基础的重要主题 70年代前 计算机科学基础的主题没有被清楚地认清。 70年代 Knuth出版了《The Art of Computer Programming》 以算法研究为主线 确立了算法为计算机科学基础的重要主题 1974年获得图灵奖。 70年代后 算法作为计算机科学核心推动了计算机科学技术飞速发展 11 计算机问题 计算机问题：A task to be performed by computers （需要计算机解决的任务） Problems  Mathematical function from inputs to matching outputs. （输入到对应输出的一个数学功能） A particular input must always result in the same output every time the function is computed （每次同样的输入计算机给出同样的输出） Problem definition should include constraints on the resources that may be consumed by any acceptable solution（问题定义时需要给出对计算机解决问题时所能用的资源的规定，比如说运行时间、内存等） 计算机问题求解步骤 理解问题 精确解或近似解 选择数据结构 算法设计策略 设计算法 13 三种不同的计算机问题 Decision Problem (判断问题，回答yes或者no) 比如：输入的数是否大于60 Optimal Problem （优化问题，求最优解） 比如：从A到B的最短路径是什么？ Numerical Calculation （数值计算） 比如说用计算机求方程或积分等，这些问题都属于数值计算中 14 Algorithms（算法） 1. a method or a process followed to solve a problem u