课程简介

这是关于计算机算法的入门课程。适合受过高中程度的教育,希望对计算机算法相关话题有比较专业的了解,但还没系统学习的学习者。这里提供的完整内容(包括总共400分钟讲课视频,80道习题和一套包含15个题的试卷),既可以作为大学非计算机专业的选修课材料,也可以用于大学面向学有余力的高中生开设的AP(先修)课程。 课程概述 在概述了算法是什么、算法的描述、算法的分析和算法的类型等四个方面的要点之后,课程选择了10个有代表性的问题进行算法求解的讨论。采用问题导入,算法思路,算法描述和算法分析的基本框架,展现了计算机科学中常用的算法思维内涵。同时,对有些问题,通过强调一题多解的过程,体现了丰富的算法设计思想。 课程目标 通过本课程的学习,预期学习者将获得关于算法世界的一个多维度、有深度的视野,通过熟悉10个典型的问题求解过程,领会丰富多彩的算法思想和算法作为一门学问所关心的要点。学完了本课程,能比较专业地与他人讨论算法问题。

课程大纲

第一讲    开启算法学习之旅

  1.1  什么是算法

  1.2  算法的描述

  1.3  算法的分析

  1.4  算法的类型

第二讲    量水问题  

       2.1量水问题的引入

       2.2 欧几里得算法

       2.3 扩展欧几里得算法

第三讲    二分法

       3.1 二分搜索

       3.2 求奇次方程的一个实根

第四讲    最优编码树

               4.1信息编码

               4.2 哈夫曼编码树

               4.3 哈夫曼编码算法

第五讲    优化互连互通的成本

         5.1 连通图与生成树

         5.2 最小生成树算法

         5.3 算法的正确性

第六讲    斐波那契数的三种解法

               6.1递归法

               6.2 记忆法(动态规划)

               6.3 矩阵解法

第七讲    最大收益的投资组合

         7.1 背景问题

         7.2 最大回报——动态规划法

         7.3 最佳投资组合

第八讲    路径规划

               8.1 图论基础及最短路径问题

               8.2 单源最短路径算法(Dijkstra算法)

               8.3 多源最短路径——动态规划策略

               8.4 多源最短路径算法(Floyd-Warshall算法)

第九讲    物以类聚,人以群分

         9.1 层次聚类法

         9.2 K均值聚类法

         9.3 比较与升华

第十讲    近朱者赤,近墨者黑

               10.1分类问题

               10.2 K近邻分类算法

第十一讲 旅行推销员问题三解

         11.1 蛮力解法

         11.2 遗传算法

         11.3 最小生成树法




课程说明

参考资料

李晓明,王卫红,薛定稷,《信息技术之选修——算法初步》,华东师范大学出版社,20218

陈道蓄,李晓明,《算法漫步——乐在其中的计算思维》,CCF PRESS(机械工业出版社),20218

李晓明,周刚,顾秋辉,白晓琦,《信息技术之选择性必修——数据与数据结构》,华东师范大学出版社,20213



拓展阅读

其他

主讲教师

李晓明 等   

1986年,在美国史蒂文斯理工学院计算机系获得博士学位,后在中国哈尔滨工业大学做博士后、教授。1995-1997在美国锡拉丘茨大学东北并行计算中心(NPAC)做高级访问学者。1997年9月至现在,为北京大学计算机系教授。

王卫红   计算机

毕业于美国科罗拉多州立大学计算机科学系,获硕士学位。现为北京大学信息科学技术学院专职教师,担任计算机网络相关的课程教学工作,参与《网络、群体与市场》教材翻译工作。

相关课程推荐

  • 正在进行
    计算机组成
    本课程的重点在于计算机内部的主要部件以及各部件之间的联系,主要内容包括:冯·诺依曼计算机结构的要点,计算机执行指令的工作过程,当前流行的指令系统的分析对比,高级语言、汇编语言和机器语言之间的关系等。
  • 正在进行
    解密教育的技术变革史
    互联网并非人类历史上第一次“信息技术”革命。人类历史上一共出现过5种媒介技术:口头语言、手工抄写/羊皮书、印刷技术、广播电视和互联网。 媒介技术提供的记录和传承功能,对人类的群体社会认知,带来了革命性的影响。西方历史上曾经发生的两次文明的大发展,都正好处于媒介技术变革前后。希腊文明处于希腊从口传到手工抄写的媒介技术变革中;近代科学史上的哥白尼革命,又正好处于欧洲从手工抄写到机器印刷的技术转型中;今天,轮到了信息技术…… 吟唱、诗歌、戏曲、绘画、文字书写等,都曾经是一种表达“技术”;《荷马史诗》、《圣经》都曾经充当过识字课本;口头语言、羊皮纸卷、印刷书、广播电视,都是曾经的“教育技术”。 这门课程从重新定义教育和人这两个核心概念开始,带着你从媒介史、知识产业分工配套体系、教学模式和教育组织方式等不同的视角,游历人类一路走来传播生态环境、知识产业、教育教学的发展过程,从中寻找媒介技术影响教育变革的规律,指导学习者迎接未来教育变革的挑战,寻找创新和发展方向!
  • 已结课
    推荐系统
    随着信息技术的飞速发展和互联网的全面普及,加快了数据产生和信息传播的速度。这为人们的生活和工作提供了便捷,但同时也带来了困扰:信息超载。为解决这一问题,搜索引擎和推荐系统两种信息过滤系统应运而生。不同于搜索引擎需要“用户主动寻找信息”且反馈结果“千人一面”,推荐系统的目标是“系统主动推送信息”且推荐结果“千人千面”。由于推荐系统能够让用户、平台、商家等多方受益,它已成为互联网(特别是移动互联网)应用和服务的一种标配。 本课程主要介绍推荐系统中的各种常用算法和一些典型应用。通过本课程的学习,学生不仅可以掌握各种常用推荐算法的思想、原理和实现,同时还能熟悉各种推荐算法的应用场景和一些典型的应用案例,并把握推荐系统未来的发展方向。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

1. 试试去广告邮件、垃圾邮件目录看看

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!