第一章算法问题求解基础.ppt

算法分析与设计主讲:徐晓蓉计算机科学与技术学院学****算法的必要性及目的学****算法的必要性及目的算法是计算机科学的基础,更是程序的基石,为了成为训练有素的软件人才,必须有良好的算法基础。哈雷尔在他的<算法学—计算的灵魂>一书中说:”算法不仅是计算机学科的一个分支,它更是计算机科学的核心,而且可以毫不夸张地说,它和绝大多数科学、商业和技术都是相关的”简单的说,学****算法,就是为了掌握并灵活运用已有的算法策略解决实际问题,并设计新的更有效的新算法。教材、参考书与课时安排教材、参考书与课时安排教材算法设计与分析--C++ 语言描述陈慧南电子工业出版社参考书?苏德富主编,《计算机算法设计与分析》,电子工业出版社,2000 年6月; ?王晓东主编,《计算机算法设计与分析》(第2版),电子工业出版社, 2004 年7月; ?卢开澄主编清华大学出版社出版的《计算机指导引论-设计与分析》? Sartaj Sahni 著(美) ,汪诗林等译, 《数据结构、算法与应用》,***出版社, 1999 ?课时安排?授课:48学时实验:10学时课程的教学任务和目标课程的教学任务和目标学****并掌握各种基本的算法设计策略。学****算法分析的基本方法。学****用基本的算法设计策略解决实际问题的方法. 通过对常用的、有代表性的算法的学****研究,让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力,锻炼其逻辑思维能力和想象力,并使之了解算法理论的发展。使学生掌握算法设计过程与方法,并学会用所学知识解决实际问题,培养他们的独立科研的能力和理论联系实践的能力。主要教学内容主要教学内容第一章算法问题求解基础第二章算法分析基础第五章分治法第六章贪心法第七章动态规划法第八章回溯法第九章分枝限界法第十章 NP 完全问题课程的基本要求课程的基本要求课前做好充分的预****保持课堂安静,头脑清醒,思维活跃重视上机实践,有效利用宝贵的上机时间,做到上机前事先对实验题目进行预****分析并写出代码. 课后认真、独立、=学****态度+课堂考勤+平时作业第一章第一章算法问题求解基础算法问题求解基础算法概述问题求解方法算法设计与分析递归和归纳第一讲算法概述及算法设计与分析?教学目的: ?1、理解算法、递归定义及递归的概念; ?2、理解问题求解的方法; ?3、理解用算法求解问题的过程。?4、理解并掌握使用递归的思想求解问题的方法; ?教学内容: ?算法的概念,问题求解的过程和方法、用算法求解问题的过程,递归的概念,递归定义中的两个要素,递归算法举例,递归算法正确性的归纳证明. ?教学重点: ?算法的概念、算法求解问题的过程、递归的思想,递归算法的设计?拟教课时: ?3(理论) ?教学过程: 算法概述?算法的概念: ?是对特定问题求解步骤的一种描述,是指令的有限序列。?算法的特征: ?输入: 有零个或多个外部量作为算法的输入。?输出: 算法产生至少一个量作为输出。?确定性: 算法的每个步骤必须有明确的意义,对每种可能的情况,算法都要给出确定的操作. ?能行性: 算法的每一条指令必须能够实现,算法执行结果要达到预期的目的; ?有限性: 算法必须在执行有穷个指令后终止,并且每条指令都在执行有限时间后结束。?算法的三个要素: ?1). 数据:运算序列中作为运算对象和结果的数据. ?2). 运算:运算序列中的各种运算:赋值,算术和逻辑运算?3). 控制和转移: 算法概述?算法的分类: ?从解法上?从处理方式上?从解的精确程度上?算法的描述方法: ?自然语言描述(但不够严谨) ?流程图(早期)和 N-S 图(对于复杂算法,难于建图和理解) ?伪代码(比自然语言精确,比程序设计语言简洁) ?高级程序设计语言(描述精确,但一般细节较多)—程序数值型算法:算法中的基本运算为算术运算. 非数值型算法:算法中的基本运算为逻辑运算. 串行算法:串行计算机上执行的算法. 并行算法:并行计算机上执行的算法. 精确算法:能够得到问题的精确解的算法. 近似算法:只能得到问题的近似解的算法.