算法设计与分析 课件 0-算法导论

信息工程大学算法设计与分析算法导论国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版问题1：从课程名可以得到的课程信息有什么？算法设计算法分析问题2：可以从哪些方面评价一个应用程序的好坏？安全性用户体验正确性性能……问题3：算法有“好坏”之分吗？算法有政治立场吗？这是一门重要的，和工作生活息息相关的课程，是一门关注于性能的课程，即要能设计好的算法，也要能分析算法的性能。1.课程定位计算机相关专业的核心课程对培养计算思维和求解问题能力起到重要作用为学习其它专业课奠定扎实的基础以算法分析方法和常用的算法设计策略的学习为主2.课程目标从算法角度运用数学工具分析问题和解决问题的基本能力；①能够正确地分析并评价算法，进一步设计出高效算法；配合实践教学，理论联系实际，理论指导实践，规范完成作业，巩固所学知识；②③能力素质3.课程教材规划教材理论实践结合配有微课视频课程思政典型应用详解代码可直接运行注：国家级实验教学示范中心计算机专业组规划教材；教育部高等学校计算机专业教学指导委员会推荐教材。4.网络助学资源2中国大学MOOC国家精品课程《算法设计与分析》1《算法设计与分析》微课4.网络助学资源2中国大学MOOC国家精品课程《算法设计与分析》3麻省理工学院公开课《算法导论》CharlesLeiserson&ErikDemaine1《算法设计与分析》微课4.网络助学资源2中国大学MOOC国家精品课程《算法设计与分析》3麻省理工学院公开课《算法导论》4国内外知名的在线评测系统：POJ、洛谷等1《算法设计与分析》微课最终成绩=平时成绩(30%)+期末笔试(70%)平时成绩=课前预习（5%）+课堂测试

(5%)+编程实践

(20%)5.考核评价加入平时成绩的构成图示■

课前预习5%20%■

编程实践■

课堂测试5%总学时40，理论30+实践10test.ctest_2.ctest_3.c总学时40，理论30+实践10算法分析□算法分析准则□时间复杂度分析方法□最优性定义与证明□NP完全性理论算法设计□递归与分治□动态规划□贪心法□回溯法□分支限界法□概率算法实践环节：算法设计策略的编程实践2.课程重点难点1.每种算法设计策略的适用条件、求解步骤、分析方法和典型应用的求解方法等。算法设计策略典型应用递归与分治策略二分搜索、快速排序、归并排序、棋盘覆盖、大整数相乘、矩阵相乘、最接近点对、…动态规划矩阵连乘、0-1背包、最长公共子序列、最大子段和、最优二叉搜索树、、…贪心活动安排、单源最短路径、哈夫曼编码、背包问题、最小生成树、最优装载、过河问题、…回溯N皇后、0-1背包、旅行售货员、子集和、装载问题、最大团问题、图的m着色、连续邮资问题…分支限界0-1背包、旅行售货员、电路板排列、批处理作业调度、布线问题、装载问题、最大团问题、…分治动态规划贪心动态规划回溯分支限界2.不同算法设计策略之间的联系与区别。1.指导策略提升抽象分析能力看懂直白题目厘清问题本质转变提升3种能力，完成3个转变1.指导策略提升抽象分析能力看懂直白题目厘清问题本质转变提升3种能力，完成3个转变问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？1.指导策略提升抽象分析能力看懂直白题目厘清问题本质转变提升3种能力，完成3个转变问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？等价为：斐波那契数列1.指导策略提升抽象分析能力拓展计算思维能力直观单一思路多种算法策略转变看懂直白题目厘清问题本质转变提升3种能力，完成3个转变十个药瓶，装有相同数量的药，但其中有1瓶每一片药都轻1毫克，给你一把秤，你需要用几次秤，才能找到药片轻一点的药瓶？只能使用1次秤，你还能找到吗？有问题的药不确定有哪几瓶，依然只能使用1次秤，你能一次全找到吗？1.指导策略转变只求可行方法择优选择方法提升抽象分析能力拓展计算思维能力增强算法评价能力直观单一思路多种算法策略转变看懂直白题目厘清问题本质转变提升3种能力，完成3个转变2.具体做法---上下结合，内外延伸自主学习（课下xh）要点讲解（课上60m）随堂研讨（课上25m）随堂测试（课上5m）编程实践（课下xh）提前给出学习内容，课前反馈学习情况（集中反馈）：课前1天随堂测试主要对自主学习内容掌握情况进行评估，成绩计入平时成绩编程实践主要完成课后作业及课堂实践针对实践题目组织研讨交流编程实现完成解题报告2.具体做法---怎么练在线评测系统和本地编程相结合569112471013812131415数字华容道：用尽量少的步数，尽量短的时间，将棋盘上的数字方块，按照从左到右、从上到下的顺序重新排列整齐。解题过程使用的方法是什么？设有n个城市，已知任意两城市间距离不等，现有一情报员想从郑州出发巡回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。1.(2分)关于算法特征描述正确的有？A：

确定性B：

可行性C：

无穷性D：

有输入E：

有输出F: 有穷性2.(2分)分析算法的指标有哪些？A：

正确性