课程信息
13,692 次近期查看

100% 在线

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

可灵活调整截止日期

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

中级

完成时间大约为40 小时

建议:11 weeks of study, 3-5 hours per week....

英语(English)

字幕:英语(English)

100% 在线

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

可灵活调整截止日期

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

中级

完成时间大约为40 小时

建议:11 weeks of study, 3-5 hours per week....

英语(English)

字幕:英语(English)

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

1
完成时间为 5 小时

Introduction - Basic Objects in Discrete Mathematics

This module gives the learner a first impression of what discrete mathematics is about, and in which ways its "flavor" differs from other fields of mathematics. It introduces basic objects like sets, relations, functions, which form the foundation of discrete mathematics....
2 个视频 (总计 27 分钟), 3 个测验
2 个视频
Sets, Relations, Functions10分钟
1 个练习
Sets, relations, and functions30分钟
2
完成时间为 4 小时

Partial Orders

Even without knowing, the learner has seen some orderings in the past. Numbers are ordered by <=. Integers can be partially ordered by the "divisible by" relation. In genealogy, people are ordered by the "A is an ancestor of B" relation. This module formally introduces partial orders and proves some fundamental and non-trivial facts about them....
2 个视频 (总计 28 分钟), 2 个测验
2 个视频
Mirsky's and Dilworth's Theorem14分钟
1 个练习
Partial orders, maximal and minimal elements, chains, antichains
3
完成时间为 5 小时

Enumerative Combinatorics

A big part of discrete mathematics is about counting things. A classic example asks how many different words can be obtained by re-ordering the letters in the word Mississippi. Counting problems of this flavor abound in discrete mathematics discrete probability and also in the analysis of algorithms....
3 个视频 (总计 35 分钟), 2 个测验
3 个视频
Evaluating Simple Sums8分钟
Pascal's Triangle14分钟
1 个练习
Counting Basic Objects
4
完成时间为 4 小时

The Binomial Coefficient

The binomial coefficient (n choose k) counts the number of ways to select k elements from a set of size n. It appears all the time in enumerative combinatorics. A good understanding of (n choose k) is also extremely helpful for analysis of algorithms....
3 个视频 (总计 55 分钟), 3 个测验
3 个视频
Estimating the Binomial Coefficient22分钟
Excursion to Discrete Probability: Computing the Expected Minimum of k Random Elements from {1,...,n}18分钟
1 个练习
An Eagle's View of Pascal's Triangle8分钟
5
完成时间为 5 小时

Asymptotics and the O-Notation

...
1 个视频 (总计 14 分钟), 3 个测验
1 个视频
1 个练习
The Big-O-Notation18分钟
6
完成时间为 5 小时

Introduction to Graph Theory

Graphs are arguably the most important object in discrete mathematics. A huge number of problems from computer science and combinatorics can be modelled in the language of graphs. This module introduces the basic notions of graph theory - graphs, cycles, paths, degree, isomorphism....
3 个视频 (总计 41 分钟), 3 个测验
3 个视频
Graph Isomorphism, Degree, Graph Score13分钟
Graph Score Theorem16分钟
1 个练习
Graphs, isomorphisms, and the sliding tile puzzle30分钟
7
完成时间为 5 小时

Connectivity, Trees, Cycles

We continue with graph theory basics. In this module, we introduce trees, an important class of graphs, and several equivalent characterizations of trees. Finally, we present an efficient algorithm for detecting whether two trees are isomorphic....
3 个视频 (总计 36 分钟), 3 个测验
3 个视频
Cycles and Trees15分钟
An Efficient Algorithm for Isomorphism of Trees12分钟
1 个练习
Cycles and Trees30分钟
8
完成时间为 3 小时

Eulerian and Hamiltonian Cycles

Starting with the well-known "Bridges of Königsberg" riddle, we prove the well-known characterization of Eulerian graphs. We discuss Hamiltonian paths and give sufficient criteria for their existence with Dirac's and Ore's theorem....
2 个视频 (总计 27 分钟), 2 个测验
2 个视频
Hamilton Cycles - Ore's and Dirac's Theorem16分钟
1 个练习
Hamiltonian Cycles and Paths
9
完成时间为 5 小时

Spanning Trees

We discuss spanning trees of graphs. In particular we present Kruskal's algorithm for finding the minimum spanning tree of a graph with edge costs. We prove Cayley's formula, stating that the complete graph on n vertices has n^(n-2) spanning trees....
2 个视频 (总计 29 分钟), 3 个测验
2 个视频
The Number of Trees on n Vertices15分钟
1 个练习
Spanning Trees40分钟
10
完成时间为 3 小时

Maximum flow and minimum cut

This module is about flow networks and has a distinctively algorithmic flavor. We prove the maximum flow minimum cut duality theorem....
2 个视频 (总计 29 分钟), 2 个测验
2 个视频
Flow Networks: The Maxflow - Mincut Theorem15分钟
1 个练习
Network flow8分钟
11
完成时间为 3 小时

Matchings in Bipartite Graphs

We prove Hall's Theorem and Kőnig's Theorem, two important results on matchings in bipartite graphs. With the machinery from flow networks, both have quite direct proofs. Finally, partial orderings have their comeback with Dilworth's Theorem, which has a surprising proof using Kőnig's Theorem....
3 个视频 (总计 46 分钟), 1 个测验
3 个视频
Matchings in Bipartite Graphs: Hall's and König's Theorem16分钟
Partial Orders: Dilworth's Theorem on Chains and Antichains15分钟
3.6
31 个审阅Chevron Right

热门审阅

创建者 NPOct 23rd 2017

Fantastic course. Fascinating material, presented at a reasonably fast pace, and some really challenging assignments.

创建者 AGDec 5th 2018

This course is good to comprehend relation, function and combinations.

讲师

Avatar

Dominik Scheder

Assistant Professor
The Department of Computer Science and Engineering

关于 上海交通大学

Shanghai Jiao Tong University, a leading research university located in Shanghai, China, has been regarded as the fastest developing university in the country for the last decade. With special strengths in engineering, science, medicine and business, it now offers a comprehensive range of disciplines in 27 schools with more than 41,000 enrolled students from more than one hundred countries....

常见问题

  • 注册以便获得证书后,您将有权访问所有视频、测验和编程作业(如果适用)。只有在您的班次开课之后,才可以提交和审阅同学互评作业。如果您选择在不购买的情况下浏览课程,可能无法访问某些作业。

  • 您购买证书后,将有权访问所有课程材料,包括评分作业。完成课程后,您的电子课程证书将添加到您的成就页中,您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容,可以免费旁听课程。

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