课程名称算法设计与分析.docx

课程名称：算法设计与分析授课语言：英文A.课程说明课程代码：学分：2教学时长：64（演讲：32实验：32）先修课程：专业：计算机科学与技术教材：ALGORITHMDESIGN学院:计算机科学与通信工程学院B.教学方法教学和案例。C.课程目标目标1：掌握80X86装配语言编程的基本方法和技能，可以用它来编程应用有一定的难度。目标2：掌握装配语言编程的基本理论，正确运用结构化、模块化编程技术。目标3：使用调试工具，如DEBUG,TD等调试80X86装配语言编程更熟练。目标4：关注相关课程前后的关系。进一步了解主导课程，同时为后续课程奠定基础。目标5：学习装配语言的其他自我特征，除了像往常一样常见的编程语言外，正是底层控制的强大可行性和效率。目标6：提高独立思考、分析问题、解决问题的能力。目标7：培养良好的设计方案风格。目标8：培养分析判断能力和综合调试能力。目标9：培养对计算机软硬件的充分理解和掌握，提高软硬件协调能力。目标10：采用多模块编程方法培养多人联合开发能力。D.课程主题/单位和日期内容计划教学方法教学练习第1章简介：一些代表性问题4教学和案例第2章算法分析基础知识4教学和案例第3章图表68教学和案例第4章贪婪算法68教学和案例第5章分而治之68教学和案例第6章动态编程68教学和案例总结3232E.教科书和所需的工具或补给教科书（必填）：ALGORITHMDESIGN教科书（推荐）：耗材和/或工具：F分级计划评估方法评估要求权重指标点作业和实践根据实践和任务40%2.3(50%)3.2(50%)最终项目根据报告60%2.3(30%)3.2(30%)5.2(40%)G.课程具体组成部分第1章简介：一些代表性问题A.内容Ll第一个问题：稳定匹配1.2五大代表性问题B.目标学习五个具有代表性的问题：了解稳定的匹配。第2章算法分析基础知识A.内容2.1 可选性2.2 渐近增长阶2.3 使用列表和数组实现稳定匹配算法2.4 常见运行时间调查2.5 更复杂的数据结构：优先级队列B.目标学习计算易处理性和优先级队列；了解增长的渐近顺序；掌握功能增长的计算。第3章图表A.内容3.1 基本定义和应用3.2 图连接性和图遍历3.3 使用队列和堆栈实现图遍历3.4 测试双向性：广度优先搜索的应用3.5 有向图的连通性3.6 #向无环图和拓扑排序B.目标学习有向无环图和拓扑排序；了解有向图的连通性；掌握广度优先搜索。第4章贪婪算法A.内容4.1 间隔调度：贪婪算法遥遥领先4.2 计划将延迟最小化：交换论点4.3 最佳缓存：更复杂的交换参数4.4 图中最短路径4.5 最小生成树问题4.6 实现KrUSkal算法：联合查找数据结构4.7 聚类4.8 霍夫曼码与数据压缩问题4.9 *最低成本树状：多阶段贪婪算法B.目标学习集群；了解霍夫曼码和数据压缩问题；掌握图中的最短路径和最小生成树问题。第5章分而治之A.内容5.1 第一次重现：Mergesort算法5.2 进一步的复发关系53计数反转5.4 寻找最接近的点对5.5 整数乘法5.6 卷积和快速傅立叶变换B.目标学习卷积和快速傅立叶变换；了解找到最接近的点对和整数乘法；掌握图中的最短路径和最小生成树问题。第6章动态编程A.内容6.1 加权间隔调度：一个递归过程6.2 动态编程的原理：子问题的记忆或迭代6.3 分段最小二乘：多路选择6.4 子集和和背包：添加变量6.5 RNA二级结构：间隔上的动态编程6.6 序列比对6.7 通过分而治之的线性空间中的序列比对6.8 图中最短路径6.9 最短路径和距离矢量协议6.10 图中的负循环B.目标通过分而治之和RNA二级结构学习线性空间中的最短路径和距离矢量协议以及序列比对；了解分段的最小二乘和子集和与背包；掌握动态编程原理。学习共NP和NP的不对称；了解NP完全问题；掌握有效的认证和NP的定义。