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.信息科技复习资料(包括算法部分)信息的特征:根据实例判断体现的特征 1.2信息与数字化 一、数制的转换(学案02) 1、把要处理的信息用二进制代码来表示,这就是信息的数字化,或者说信息的编码 2、计算机内部采用二进制,因为它符合电路中的二态性,便于实现 3、计数数制:用一组固定的符号和规则来表示数的方法 http://www.360doc.com/document/17/0715/20/45444085_671594305.shtml
2.五大基础算法——枚举,算法数据结构枚举法资源下面是一个枚举算法的实例: 问题:分数拆分(Fractions Again?!) 输入:一个正整数k 输出:所有的正整数x>=y,使得1/k=1/x+1/y 解决思路:由给出的式子和x>=y,可知,k<y<=2k,通过枚举y,求出满足式子的x即可。 代码如下: ```cpp #include <iostream> #include <cstdio> #include <string> #include <https://download.csdn.net/download/qq_40464803/85090015
3.详细实例说明+典型案例实现对枚举法进行全面分析C++第五章 枚举法 目录 第五章 枚举法 ●前言 1.简要介绍 2.代码及结果示例(简单理解) 3.生活实例 ●二、枚举法的典型案例——鸡兔同笼&质数求解 1.鸡兔同笼 2.质数求解(枚举法) ●总结 前言 简单的来说,算法就是用计算机程序代码来实现数学思想的一种方法。学习算法就是为了了解它们在计算机中如何演算,以https://blog.51cto.com/zhangzhichaoya/6021768
4.枚举算法举例枚举算法举例 小明是一个数学迷,昨天他约了几个同学一起到会议室里举行一个联谊会,可是粗心的小明去总务处拿了一串钥匙回来准备开门时,却忘记了到底哪一把才是会议室的钥匙。假设这串钥匙一共有10把。怎样才能找到正确的钥匙来开门 找钥匙的过程 1.拿出第一把钥匙,试验第一把钥匙能否开门;2.拿出第二把钥匙https://wenku.baidu.com/view/7afb1f995b1b6bd97f192279168884868762b8f3.html
5.“枚举算法”教学实践的几点反思从课后的反馈看,全体学生已掌握了枚举法这一知识点,一半以上学生已经能够灵活运用枚举法解题,本次教学效果良好,同行也对课堂表示了肯定。我就以下几个方面对“枚举算法”教学实践进行反思。 1、情景创设,引出主题 在课题引入时,我列举了几个生活实例,请了一位学生找出能开启这间教室大门的所有钥匙,并请他https://www.qpshs.sh.cn/site/73ee013c-6b37-41a3-b0e1-71a0871ff706/detail/3a59efd3-f778-4616-9d9e-6e9053421306_222a947a-688e-46e2-925e-00b84ff8fd4e.html
6.算法分析与设计期末答案2023秋6.动态规划算法的特点()A:子问题独立 B:自顶向下计算 C:子问题重叠 D:自底向上计算 答案:子问题重叠###自底向上计算 7.时间复杂度为O(nlogn)的排序算法有A:堆排序 B:计数排序 C:快速排序 D:合并排序 答案:合并排序###堆排序 8.枚举算法的优化方法有A:优化数学模型 B:优化数据结构 C:减少枚举变量 https://www.wkebb.com/c/776b56604264529595bfd59c2f472142.html
7.算法与程序的区别关系算法与程序设计知识点总结算法实例 1. 枚举算法。 (1) 描述枚举算法的基本概念:列举每一种可能,并检验是否成立,也称穷举法 (2) 列举枚举算法的基本特征:先列举,后检验(用分支结构实现检验) (3)描述枚举算法的基本实现方法:循环中嵌套分支 2. 解析算法。 (1) 描述解析算法的基本概念:用代公式的方法来计算结果的算法 https://m.elecfans.com/article/610437.html
8.循环语句枚举算法 核心:通过已知条件缩小可能的范围,逐一检查每个可能值 步骤: 1.找到对象 2.确定范围 3.设定条件 4.检验结果 实例:士兵报数问题 算法1:假定范围为5000 int x; for ( x = 1; x < 5000; x++){//5000无依据 if ( x% 5==1 && x % 6== 5 && x % 7 == 4 && x % 11 == 10){https://www.jianshu.com/p/65322b14ec2b
9.小学奥数,加法原理,分类枚举,找规律,例1【例 1】有一个电子表的表面用2个数码显示“小时”,另用2个数码显示“分”。例如“21:32”表示21时32分,那么这个手表从“10:00”至“11:30”之间共有多少分钟表面上显示有数码“2”. 【解析】 显示小时的数码不会出现2,只有分钟会出现。 10点https://mp.weixin.qq.com/s?__biz=MzU0MDg4OTY2NA==&mid=2247513392&idx=1&sn=6ca79dc6ec2edd4319c4ece5c363b952&chksm=faaf4d578604991dadc223fcd1352d94e1e362d3f0c296a854b6f1f4f8da032124639dda8e87&scene=27
10.LRULFUTinyLFU缓存算法实例详解Golang这篇文章主要为大家介绍了LRU LFU TinyLFU缓存算法实例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪简介 前置知识 知道什么是缓存 听完本节公开课,你可以收获 掌握朴素LRU、LFU算法的思想以及源码 掌握一种流式计数的算法 Count-Min Sketch 手撕TinyLFU算法、分析Window-TinyLFU源码 https://m.jb51.net/article/262101.htm
11.枚举算法(精选六篇)并行枚举(m,n)-选择算法的基本思想是:将待查找数据进行分组,由p个处理机并发地调用串行枚举(m,n)-选择算法对各分组进行(m,n)-选择,再将各分组选出的m个最小数据重新组成待查找数据,递归地进行并行枚举(m,n)-选择,当待查找数据元素的个数足够小(分组数为1)时,直接进行串行(m.n)-枚举选择。算法描述如下https://www.360wenmi.com/f/cnkey6jhs3mx.html
12.生化通用人工智能——通用人工智能的哲学原理及算法实例其它类型依据相似原理,在此不一一枚举。 3.4.4. 抽象自感的生化算法实例 对于通用人工智能实体或多个实体在一定时空中按照各种自感模型进行心感生化更新的同时,产生十三感反射并生成新的心感,属于一种新的自感,本文称之为抽象自感。该实体或多个实体通过后文的实体心感理解模式进行理解时,所有被确认或新增的自感https://www.hanspub.org/journal/PaperInformation.aspx?paperID=57573
13.《算法与程序设计》课堂教学教材组织方案算法的三种不同执行模式 变量和变量的用途 算法的执行流程 1 4 活动 枚举算法 什么是枚举算法 枚举算法举例 2 5 活动 解析算法 什么是解析算法 解析算法举例 2 6 活动 排序算法 什么是排序 冒泡排序 选择排序算法 2 7 活动 什么是查找 1 查找算法 顺序查找 对分查找 8 活动 算法实例综合活动 第二章“本章https://doc.mbalib.com/view/076091718f8ad96a60434cc3a43481f7.html
14.枚举算法公开课经管文库(原现金交易版)经管枚举算法的程序实现 HSSZ 邓彰超 教学目标 重点 难点 1.了解枚举算法求解问题的基本过程,理解其基本https://bbs.pinggu.org/thread-13132398-1-1.html
15.案例程序教学法11篇(全文)1、在前面的教学中,学生已经理解了算法的特点,学习了算法的三种表示方式,理解了顺序、选择、循环三种基本结构,并通过参与活动手册中的实践,对程序有了初步的认识。 2、通过枚举算法两课时的学习,重点深化了流程图,基本上会设计流程图,并根据流程图写出相应的代码并通过自己编制程序上机实践来体验。那么在课堂分析过程https://www.99xueshu.com/w/ikeyleh882cj.html