MOOC丨算法设计与问题求解大学慕课

本课程以计算机经典问题求解为导向,通用算法思维和编码能力培养为目标,引入ACM国际大学生程序设计竞赛的有益元素,精心安排课程的理论教学和编程实践。本课程学习将帮助学员提高计算思维和程序设计能力,帮助学员应对IT公司的算法笔试/面试或者研究生入学考试的机考/面试。

——课程团队

开课学校:北京交通大学

开课教授:李清勇、张英俊、李公仆、赵宏智、李强、刘铭

课程概述

“软件=算法+数据结构”,算法是软件的灵魂。在信息时代,计算思维是分析复杂工程问题的重要思维方式,计算机则是求解问题的重要工具。本课程以计算机经典问题求解为导向,通用算法思维和编码能力培养为目标,引入ACM国际大学生程序设计竞赛的有益元素,精心安排课程的理论教学和编程实践。

本课程主要讲授计算机问题求解的经典算法设计方法和算法复杂度分析方法,主要内容包括算法复杂度分析,枚举算法,递归与分治策略,动态规划,贪心算法和通用搜索技术。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂问题时,既能“想到”还能“做到”。

授课目标

课程大纲

第二章枚举算法(大道至简)

2.1基本原理

2.2模糊数字问题

2.3百钱百鸡问题

2.4数组配对问题

2.5绳子切割问题

2.6石头移动问题

2.7小结

枚举算法作业

第三章递归与分治(庖丁解牛)-1

3.1递归基本思想

3.2递归实例

3.3分治基本原理

3.4Master定理

3.5合并排序

递归算法实践

第三章递归与分治(庖丁解牛)-2

3.6逆序对问题

3.7快速排序

3.8最接近点对

3.9乘方运算

3.11小结

矩阵搜索问题

第四章.动态规划(跬步千里)-1

4.1基本原理

4.2矩阵连乘-问题分析

4.3矩阵连乘-算法与实现

4.4矩阵连乘-备忘录方法

4.5多段图最短路径-问题分析

4.6多段图最短路径-算法与实现

编辑距离问题

第四章.动态规划(跬步千里)-2

4.7最长公共子序列-问题分析

4.8最长公共子序列-算法与实现

4.90-1背包-问题分析

4.100-1背包-算法与实现

4.110-1背包-优化方法

4.12最大上升子序列-问题分析

4.13最大上升子序列-算法与实现

4.14小结

收集控的决策问题

第五章.贪心算法(局部寻优)-1

5.1基本原理

5.2活动安排问题-算法与实现

5.3活动安排问题-正确性证明

5.4小数背包问题

5.5哈夫曼编码-算法与实现

5.6哈夫曼编码-正确性证明

5.7单源最短路径-Dijkstra与实现

5.8单源最短路径-正确性证明

数字删除问题

第五章.贪心算法(局部寻优)-2

5.9最小生成树-问题分析

5.10最小生成树-Prim算法与实现

5.11最小生成树-Prim证明

5.12并查集基础

5.13最小生成树-Kruskal算法与实现

5.14最小生成树-Kruskal证明

5.15小结

贪心算法实践

第六章.搜索技术(按图索骥)-1

6.1状态空间图

6.2深度优先搜索

6.3广度优先搜索

6.4回溯算法-原理

6.5回溯算法-实例

搜索算法实践

第六章.搜索技术(按图索骥)-2

6.6分支限界法-原理

6.7分支限界法-实例

6.8启发式搜索-原理

6.9A*算法-原理

6.10启发式搜索-实例

6.11小结

预备知识

参考资料

李清勇.算法设计与问题求解-计算思维培养(第2版),电子工业出版社,2020.

Cormen,T.H.等著,潘金贵等译.算法导论,机械工业出版社,2006.

课程心得

老师讲得十分透彻,将经典算法的核心思想整理出来了并教给学生如何思考、解决问题,真的非常棒!将算法书上的重点深入浅出的讲解了出来,非常适合本科生学习。对于业余爱好来说,本课程也成了难度没那么高,值得一学的课程!

THE END
1.理解递归算法的原理腾讯云开发者社区当然这只是一个段子,不过也从侧面反映出递归算法不容易理解的事实。这个我自己也深有体会,就拿排序算法里面的快排和归并排序来说吧,这两种算法采用的都是分治思想来处理排序问题,所以递归在这里就出现了,如果你不理解递归算法,就去学习这两种排序算法,可能理解起来就非常费事,尽管你知道这两种排序的算法原理和它的https://cloud.tencent.com/developer/article/1356049
2.算法之美:解读递归算法原理和效率常见递归算法 下面总结一下常见的递归问题和实现算法。 斐波那契数列 斐波那契数列的排列是:0,1,1,2,3,5,8,13,21,34,55,89,144……依次类推下去,你会发现,它后一个数等于前面两个数的和。在这个数列中的数字,就被称为斐波那契数。 递归思想:一个数等于前两个数的和。 http://www.360doc.com/content/19/1227/22/27863154_882621949.shtml
3.递归算法与递归套路编程编程递归算法原理 递归算法的核心思想是将一个问题划分为一个或多个规模较小但类似于原问题的子问题,并通过递归调用解决这些子问题,最终将子问题的解合并得到原问题的解。递归算法通常包含两个要素: 递归基(Base Case):定义递归的终止条件,即最简单的情况下直接给出解答。 https://download.csdn.net/blog/column/12409590/132877647
4.C++递归与分治算法原理示例详解C语言这篇文章主要为大家介绍了C++递归与分治算法的策略原理示例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪+ 目录 GPT4.0+Midjourney绘画+国内大模型 会员永久免费使用!【 如果你想靠AI翻身,你先需要一个靠谱的工具!】 1. 汉诺塔问题 递归算法,分为 3 步:将 n 个 a 上的盘子https://www.jb51.net/article/226989.htm
5.怎么绘制递归算法流程图?教你简单的制作方法递归流程图是一种描述递归算法执行过程的图形化工具,它可以帮助理解递归算法的实现原理,展示递归函数调用的过程和递归函数在不同层次上的执行情况。那么要怎么绘制递归算法流程图呢?接下来就让我们一起来看看。https://www.liuchengtu.com/tutorial/diguiliuchengtu.html
6.python3open指定编码mob64ca1402a190的技术博客递归体。解答:什么时候需要调用自身方法。 ##使用递归计算n的阶乘 def factorial(n): if n==1: return n else: return (n*factorial(n-1)) print(factorial(5)) 1. 2. 3. 4. 5. 6. 7. 8. 15.递归算法原理——目录树结构展示 ##递归打印所有的目录和文件 https://blog.51cto.com/u_16213626/11467185
7.编译原理第四章:语法分析消除左递归算法 提取左公因子 对于一个文法,通过改写产生式来推迟决定,等获得足够多的输入信息再做正确的决定。 例:文法: 可以改写为: 三、LL1文法 预测分析法的工作过程 从文法的开始符号S开始,每一步推导根据当前句型的最左非终结符A和当前输入符号α,选择正确的A-产生式。为保证分析的确定性,选出的候选式https://www.jianshu.com/p/47dd1b4791f7
8.腾讯算法岗武功秘籍(上)2.2.4 手写算法代码 ● 定义函数实现一下softmax(不要用numpy) ,数值太大溢出怎么办? 2.2.5 激活函数类 ● DNN中如果把中间层的激活函数去掉会怎样?去掉激活函数的DNN与逻辑回归有什么区别? 2.3 深度学习:RNN递归神经网络方面 2.3.1 讲解相关原理 ● RNN的梯度爆炸怎么解决? ● LSTM对于RNN的改进地方在哪?https://www.flyai.com/article/930
9.90%的算法都基于这六个算法思想计算机科学中存在多种常见的算法思想,它们在解决问题时具有独特的特点和适用场景。本文将深入探究递归算法、贪心算法、回溯算法、分治算法、动态规划和枚举算法,并提供每个算法思想的示例问题,以帮助读者更好地理解其原理、应用和优缺点。 递归算法 递归算法是一种自我调用的算法思想,通过将问题分解为基本情况和更小规模https://m.w3cschool.cn/article/96194468.html
10.北航软件学院招收2024年硕士研究生自命题考试大纲(991包括但不限于内排序的基本概念、各类算法实现原理和应用,主要内容有:排序的基本概念,各种内排序方法的基本原理和特点;插入排序法(含折半插入排序法);选择排序法;泡排序法;谢尔排序法;快速排序法;堆排序法;二路归并排序法。 七、递归分析技术 包括但不限于递归分析技术的基本概念和操作,主要内容有:掌握递归算法的分https://soft.buaa.edu.cn/news_nry.jsp?urltype=news.NewsContentUrl&wbtreeid=1325&wbnewsid=10683
11.递归算法(图文详解)递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。 二、算法实质 递归算法就是将原问题不断分解为规模缩小的子问题,然后递归调用方法来表示 问题的解。(用同一个方法去解决规模不同的问题) 三、算法思想 递归算法,顾名思义就是有两个大的阶段:递和归,即就是有去(递去)有https://www.coonote.com/algorithm-note/explanation-of-recursive-algorithms.html
12.浅谈递归算法优缺点这与递归算法的原理是一致的,递归算法的核心思想是简化复杂性。对于一个复杂的问题,将原始问题分解为几个相对简单的子问题,直到子问题简单到可以直接解决,即递归的出口,使原始问题有递归解决方案。 2.用有限的句子定义对象的无限集合; 这似乎不容易理解,但结合实际例子,我们的理解可以大大加深。举一个最经典的例子,https://www.tulingxueyuan.cn/tlzx/jsp/1251.html
13.科学网—经典的算法回顾1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。 2.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重https://blog.sciencenet.cn/blog-315535-665392.html
14.递归算法实验报告.docx递归算法实验报告篇一:递归算法的设计和实现的实验报告 班级学号 姓名 实验组别 试验日期 室温 报告日期成绩 报告内容:(目的和要求、原理、步骤、数据、计算、小结等) 实验名称:递归算法的设计和应用 实验目的: 1. 掌握递归算法的实现。 2. 实现递归算法的应用。 实验环境(硬/软件要求): Windows XX, Visual C++https://max.book118.com/html/2018/1018/8105025065001127.shtm
15.2021年度市级以上公安机关面向社会招录警务信息侦控网络安全4.数据结构和算法 (3)链表、队列、树等常见数据结构 (4)递归、排序、查找等常见算法 (十八)大数据基础知识 1.大数据的特点、分布式存储、分布式计算的概念 2.Zookeeper原理和架构,应用场景 3.HDFS的特点,常用操作 4.MapReduce 原理和架构 5.YARN原理和架构 http://www.gxjcxy.com/zsjy/zpxx/content_3331