资源描述：
《第0章 课程概况(0-课程介绍)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、欢迎选修欢迎选修《《算法设计与分析算法设计与分析》》课程课程郑郑婵婵Lucy_zhengchan@hotmail.comLucy_zhengchan@hotmail.com教材：教材：计算机算法设计计算机算法设计与分析（第与分析（第33版）版）王晓东王晓东编著编著电子工业出版社电子工业出版社课程说明：课程说明：基础知识要求：本科数学分析（或高等数学）、离散基础知识要求：本科数学分析（或高等数学）、离散数学和数学和C++C++语言程序设计、数据结构等语言程序设计、数据结构等学时安排：学时安排：4848学时，其中课堂授课学时，其中课堂授课3232学
2、时，上机实践学时，上机实践1616学时，学时，实验从第实验从第55周开始周开始(5~12(5~12周周))考核方式：考试（含考核方式：考试（含70%70%期末成绩期末成绩+30%+30%的实验成绩及的实验成绩及平时作业成绩）平时作业成绩）课程邮箱：课程邮箱：ComputerAlgorithm@163.comComputerAlgorithm@163.compassword:password:scauscauscauscau课程介绍课程介绍程序和算法程序和算法大型软件大型软件==软件工程的原则软件工程的原则＋＋数据结构数据结构＋＋算法算法小型程序
3、小型程序==数据结构数据结构＋＋算法算法Algorithm+DataStructure=Programming区分：区分：什么是数据结构？什么是数据结构？什么是算法？什么是算法？什么是程序？什么是程序？几个实际算法例子几个实际算法例子Hanoi塔问题T(n)=2T(n−1)+1，T(1)=1，解得T(n)=2n−1，64个盘子要多少时间？T(64)=2^64-1=18446744073709551615（1秒移1个，5849亿年）Reve难题：Hanoi塔变种，柱数增加，允许盘子相等.其他变种：奇偶盘号分别放置几个实际算法例子几个实际算
4、法例子搜索问题输入：数组L，x输出：x是否在L中？如果在，输出它的下标排序问题输入：n个数输出：按递增顺序排好的n个数选择问题输入：n个数的集合S，正整数k（1≤k≤n)输出：S中第k小的数现有的算法中哪个算法最好？是否存在更有效的算法？几个实际算法例子几个实际算法例子巡回售货员(货郎担问题)几个实际算法例子几个实际算法例子马的Hamilton周游路线问题棋盘m*n上有只国际象棋马(
5、m-n
6、<=2,且m和n均为大于5的偶数)，恰好走过除起点外任何其他位置各一次，最后回到起点的一条Hamilton周游路线小规模问题，如6*6,6*8,8*8,8*10,
7、10*10,10*12等都可以用回溯法找到大规模问题，m*n(
8、m-n
9、<=2,且m和n均为大于5的偶数)，可采用分治算法，将棋盘进行分割解决N皇后问题N*N的棋盘上放置N个国际象棋皇后，使得皇后们不相互攻击。几个实际算法例子几个实际算法例子背包问题0-1背包问题单机多任务调度多机多任务调度等问题……好的算法提高求解问题的效率节省存储空间需要解决的问题问题→寻找求解算法算法设计技术算法→算法的评价算法分析技术算法类→问题复杂度的评价问题复杂性分析问题类→能够求解的边界计算复杂性理论指数时间的算法：2n,3n,n!,…多项式时间的算法：n,n2,nl
10、ogn,n1/2,…对数多项式时间的算法：logn,log2n,…把现有的问题分成三类：存在多项式时间的有效算法的问题(如排序问题)只有指数时间的无效算法的问题(如旅行商问题、0-1背包问题……)未找到算法的问题(如歌德巴赫猜想)复杂度内容算法复杂度——算法所使用的时间、空间的估计问题复杂度——估计问题的难度术语和概念问题算法算法的时间复杂度函数的阶多项式时间的算法与指数时间的算法问题的复杂度分析课程目的课程目的1.1.理解和掌握算法设计的主要的常用的理解和掌握算法设计的主要的常用的方法；方法；2.2.理解算法复杂性分析原理；理解算法复
11、杂性分析原理；3.3.培养对给定算法的复杂性进行分析的培养对给定算法的复杂性进行分析的能力；能力；4.4.能够独立地设计算法。能够独立地设计算法。授课形式授课形式系统地介绍算法的每一种设计方法和分析技巧系统地介绍算法的每一种设计方法和分析技巧首先介绍一种算法设计的策略的基本思想；首先介绍一种算法设计的策略的基本思想；然后，从应用中出现的实际问题入手，由浅入然后，从应用中出现的实际问题入手，由浅入深的描述几个经典的精巧算法；深的描述几个经典的精巧算法；最后，通常我们要对这些算法所需的时间空间最后，通常我们要对这些算法所需的时间空间复杂度进行分析。复杂度进
12、行分析。主要内容主要内容主要讲解内容和章节主要讲解内容和章节算法引论算法引论递归与分治递归与分
