本课程是 Introduction to Discrete Mathematics for Computer Science 专项课程专项课程的一部分

4.7
星
358 个评分

Alexander S. Kulikov

19,162 人已注册

提供方

Introduction to Discrete Mathematics for Computer Science 专项课程University of California San Diego

课程信息

3,297 次近期查看

In this online course we’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem. The goal in this problem is to visit all the given places as quickly as possible. How to find an optimal solution to this problem quickly? We still don’t have provably efficient algorithms for this difficult computational problem and this is the essence of the P versus NP problem, the most important open question in Computer Science. Still, we’ll implement several solutions for real world instances of the travelling salesman problem.
While designing these solutions, we will rely heavily on the material learned in the courses of the specialization: proof techniques, combinatorics, probability, graph theory. We’ll see several examples of using discrete mathematics ideas to get more and more efficient solutions.

可灵活调整截止日期

根据您的日程表重置截止日期。

可分享的证书

完成后获得证书

100% 在线

立即开始，按照自己的计划学习。

第 5 门课程（共 5 门）

Introduction to Discrete Mathematics for Computer Science 专项课程

初级

完成时间大约为13 小时

英语（English）

可灵活调整截止日期

根据您的日程表重置截止日期。

可分享的证书

完成后获得证书

100% 在线

立即开始，按照自己的计划学习。

第 5 门课程（共 5 门）

Introduction to Discrete Mathematics for Computer Science 专项课程

初级

完成时间大约为13 小时

英语（English）

授课教师

授课教师评分

4.65/5 （24 个评分）

Alexander S. Kulikov

Professor

Department of Mathematics and Computer Science

699,016 个学生

13 门课程

提供方

University of California San Diego

授课大纲 - 您将从这门课程中学到什么

周

周 1

完成时间为 5 小时

Traveling Salesman Problem

We start this module with the definition of mathematical model of the delivery problem — the classical traveling salesman problem (usually abbreviated as TSP). We'll then review just a few of its many applications: from straightforward ones (delivering goods, planning a trip) to less obvious ones (data storage and compression, genome assembly). After that, we will together take the first steps in implementing programs for TSP.

完成时间为 5 小时

4 个视频（总计 43 分钟）, 1 个阅读材料, 5 个测验

周

周 2

完成时间为 4 小时

Exact Algorithms

We'll see two general techniques applied to the traveling salesman problem. The first one, branch and bound, is a classical approach in combinatorial optimization that is used for various problems. It can be seen as an improvement of the brute force search: we try to construct a permutation piece by piece, but at each step we check whether it still makes sense to continue constructing the permutation (if it doesn't, we just cut off the current branch). The second one, dynamic programming, is arguably the most popular algorithmic technique. It solves a problem by going through a collection of smaller subproblems.

完成时间为 4 小时

4 个视频（总计 49 分钟）

周

周 3

完成时间为 4 小时

Approximation Algorithms

As we've seen in the previous modules, solving the traveling salesman problem exactly is hard. In fact, we don't even expect an efficient solution in the nearest future. For this reason, it makes sense to ask: is it possible to find efficiently a solution that is probably suboptimal, but at the same time is close to optimal? It turns out that the answer is yes! We'll learn two algorithms. The first one guarantees to find quickly a solution which is at most twice longer than the optimal one. The second algorithms does not have such guarantees, but it is known to work pretty well in practice.

完成时间为 4 小时

2 个视频（总计 20 分钟）

审阅

4.7

48 条评论

5 stars
76.53%
4 stars
18.15%
3 stars
2.79%
2 stars
2.23%
1 star
0.27%

来自DELIVERY PROBLEM的热门评论

由 DS 提供Sep 19, 2020

Amazing course with lots of intuitive examples and puzzles

由 NL 提供Mar 21, 2021

This series is great. I am confident to tutor my son in CS now.

Thanks UCSD and HSE

由 LF 提供Jan 13, 2020

This is a very nice course. I feel that a further explanation in the coding problems would be useful since sometimes you are not sure what one should return from the function.

由 AG 提供Jun 27, 2020

Well structured introductory course into transportation problems. The code in examples is well written and clean. It was a pleasure to study this course.

查看所有评论

关于 Introduction to Discrete Mathematics for Computer Science 专项课程

Discrete Mathematics is the language of Computer Science. One needs to be fluent in it to work in many fields including data science, machine learning, and software engineering (it is not a coincidence that math puzzles are often used for interviews). We introduce you to this language through a fun try-this-before-we-explain-everything approach: first you solve many interactive puzzles that are carefully designed specifically for this online specialization, and then we explain how to solve the puzzles, and introduce important ideas along the way. We believe that this way, you will get a deeper understanding and will better appreciate the beauty of the underlying ideas (not to mention the self confidence that you gain if you invent these ideas on your own!). To bring your experience closer to IT-applications, we incorporate programming examples, problems, and projects in the specialization.

常见问题

我什么时候能够访问课程视频和作业？
讲座和作业的访问权限取决于您的注册类型。如果您以旁听模式参加课程，则可以免费查看大多数课程资料。要访问评分作业并获得证书，您需要在旁听期间或之后购买证书体验。如果看不到旁听选项：
课程可能不提供旁听选项。您可以尝试免费试用，也可以申请助学金。
课程可能会改为提供'完整课程，没有证书'。通过此选项，您可以查看所有课程材料、提交所要求的作业，以及获得最终成绩。这也意味着您将无法购买证书体验。
我购买证书后会得到什么？
您购买证书后，将有权访问所有课程材料，包括评分作业。完成课程后，您的电子课程证书将添加到您的成就页中，您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容，可以免费旁听课程。
有助学金吗？
是的。如果您负担不起学习计划的注册费，则可以在选择学习计划时申请助学金或奖学金。如果您选择的学习计划提供助学金或奖学金，则您将在描述页面上看到一个申请链接。

还有其他问题吗？请访问学生帮助中心。

Delivery Problem

课程信息