spContent=算法是数学和信息技术应用的重要组成部分,是计算科学的重要基础。随着现代信息技术的飞速发展,算法在科学技术、社会发展中发挥着越来越大的作用,在信息检索、智能导航、图像处理、语音识别等方面发挥了巨大的作用,可以毫不夸张的说算法是计算的灵魂,算法相关的基础知识是计算机科学的基石。
算法是数学和信息技术应用的重要组成部分,是计算科学的重要基础。随着现代信息技术的飞速发展,算法在科学技术、社会发展中发挥着越来越大的作用,在信息检索、智能导航、图像处理、语音识别等方面发挥了巨大的作用,可以毫不夸张的说算法是计算的灵魂,算法相关的基础知识是计算机科学的基石。
—— 课程团队
课程概述
算法导论作为计算机科学与技术专业的专业主干课程,先修课程是高级语言程序设计、数据结构,主要讲授经典算法,包括递归与分治算法、动态规划算法、贪心算法、回溯算法、分支界限算法的基本原理、实现方法和应用实例,通过该课程的学习,使学生熟悉算法复杂性分析理论和评价算法性能的标准,掌握基本的算法设计方法,能运用一些常用算法去分析和解决实际问题,具有较强的问题抽象和建模的能力,为学生进一步分析和解决计算机科学与技术领域的复杂工程问题奠定良好的基础。
算法导论课程的教学目标有两个:
1)能够针对待解决的具体问题,在满足问题约束条件的前提下,分析多种解决方案在时间、空间复杂度及算法效率上的优劣,选择合理的算法进行解决。
2)能够结合具体应用案例,合理选择经典算法,并能在此基础上设计出复杂算法,使之针对具体应用能够高效地存储和处理数据,并对算法进行有效分析和评价。
授课目标
通过对分治和递归、动态规划、贪心算法、回溯法和分枝限定法等典型算法的学习,使学习者能运用所学算法知识,根据不同问题的特点选择合适的策略去解决,为从事计算机科学理论研究和软件开发奠定扎实的算法知识基础。
成绩 要求
采取百分制,60分-79分可申请合格证书,80分以上可申请优秀证书,成绩达到相应要求即可申请证书。
课程大纲
分治与递归
课时目标:理解递归的概念,掌握设计有效算法的分治策略,通过范例学习分治策略的设计技巧
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.4 合并
2.5 线性时间选择
2.6 大整数的乘法
2.7 最接近点对
2.8 棋盘覆盖
动态规划
课时目标:掌握动态规划算法的基本要素,掌握设计动态规划算法的步骤,通过应用范例学习动态规划算法设计策略。
3.1 动态规划概述
3.2 矩阵连乘
3.3 最长公共子序列
3.4 最大子段和
3.5 凸多边形最优剖分
3.6 流水作业调度
3.7 图像压缩
3.8 0-1背包
3.9 电路布线
3.10 最优二叉搜索树
贪心算法
课时目标:理解并掌握使用贪心策略设计算法的方法
4.1活动安排问题
4.2贪心算法的基本要素
4.3最优装载
4.4哈夫曼编码
4.5哈夫曼编码理论证明
4.6单源最短路径
4.7最小生成树
回溯法
课时目标:理解回溯法的深度优先搜索策略,掌握用回溯法解题的算法框架:子集树算法框架、排列树算法框架,通过应用范例学习回溯法的设计策略
5.1回溯法基本概念
5.2 0-1背包问题
5.3 旅行商问题
5.4 图的着色问题
分支限界法
课时目标:理解分支限界法的剪枝搜索策略,掌握分支限界法的算法框架:队列式(FIFO)分支限界法、优先队列式分支限界法,通过应用范例学习分支限界法的设计策略
6.1 分支限界法概述
6.2 单源最短路径
6.3 装载问题
6.4 最大团问题
展开全部
预备知识
参考资料
1王晓东编,计算机算法设计与分析(第5版),电子工业出版社,2018年
2 Thomas H. Cormen等著,潘金贵等译,算法导论,机械工业出版社
3 R.C.T.Lee等著,王卫东译,算法设计与分析导论,机械工业出版社