このコースについて
14,053

100%オンライン

自分のスケジュールですぐに学習を始めてください。

柔軟性のある期限

スケジュールに従って期限をリセットします。

中級レベル

約40時間で修了

推奨:11 weeks of study, 3-5 hours per week....

英語

字幕:英語

100%オンライン

自分のスケジュールですぐに学習を始めてください。

柔軟性のある期限

スケジュールに従って期限をリセットします。

中級レベル

約40時間で修了

推奨:11 weeks of study, 3-5 hours per week....

英語

字幕:英語

シラバス - 本コースの学習内容

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 quizzes
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 quizzes
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 quizzes
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 quizzes
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 quizzes
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 quizzes
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 quizzes
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 quizzes
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 quizzes
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 quizzes
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 quiz
3件のビデオ
Matchings in Bipartite Graphs: Hall's and König's Theorem16 分
Partial Orders: Dilworth's Theorem on Chains and Antichains15 分
3.5
32件のレビューChevron Right

人気のレビュー

by NPOct 23rd 2017

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

by 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)について

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....

よくある質問

  • 修了証に登録すると、すべてのビデオ、テスト、およびプログラミング課題(該当する場合)にアクセスできます。ピアレビュー課題は、セッションが開始してからのみ、提出およびレビューできます。購入せずにコースを検討することを選択する場合、特定の課題にアクセスすることはできません。

  • 修了証を購入する際、コースのすべての教材(採点課題を含む)にアクセスできます。コースを完了すると、電子修了証が成果のページに追加されます。そこから修了証を印刷したり、LinkedInのプロフィールに追加したりできます。コースの内容の閲覧のみを希望する場合は、無料でコースを聴講できます。

さらに質問がある場合は、受講者向けヘルプセンターにアクセスしてください。