About this Course
13,944

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 videos (Total 27 min), 3 quizzes
2개의 동영상
Sets, Relations, Functions10m
1개 연습문제
Sets, relations, and functions30m
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 videos (Total 28 min), 2 quizzes
2개의 동영상
Mirsky's and Dilworth's Theorem14m
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 videos (Total 35 min), 2 quizzes
3개의 동영상
Evaluating Simple Sums8m
Pascal's Triangle14m
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 videos (Total 55 min), 3 quizzes
3개의 동영상
Estimating the Binomial Coefficient22m
Excursion to Discrete Probability: Computing the Expected Minimum of k Random Elements from {1,...,n}18m
1개 연습문제
An Eagle's View of Pascal's Triangle8m
5
완료하는 데 5시간 필요

Asymptotics and the O-Notation

...
1 video (Total 14 min), 3 quizzes
1개의 동영상
1개 연습문제
The Big-O-Notation18m
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 videos (Total 41 min), 3 quizzes
3개의 동영상
Graph Isomorphism, Degree, Graph Score13m
Graph Score Theorem16m
1개 연습문제
Graphs, isomorphisms, and the sliding tile puzzle30m
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 videos (Total 36 min), 3 quizzes
3개의 동영상
Cycles and Trees15m
An Efficient Algorithm for Isomorphism of Trees12m
1개 연습문제
Cycles and Trees30m
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 videos (Total 27 min), 2 quizzes
2개의 동영상
Hamilton Cycles - Ore's and Dirac's Theorem16m
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 videos (Total 29 min), 3 quizzes
2개의 동영상
The Number of Trees on n Vertices15m
1개 연습문제
Spanning Trees40m
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 videos (Total 29 min), 2 quizzes
2개의 동영상
Flow Networks: The Maxflow - Mincut Theorem15m
1개 연습문제
Network flow8m
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 videos (Total 46 min), 1 quiz
3개의 동영상
Matchings in Bipartite Graphs: Hall's and König's Theorem16m
Partial Orders: Dilworth's Theorem on Chains and Antichains15m
3.5
32개의 리뷰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....

자주 묻는 질문

  • 강좌에 등록하면 바로 모든 비디오, 테스트 및 프로그래밍 과제(해당하는 경우)에 접근할 수 있습니다. 상호 첨삭 과제는 이 세션이 시작된 경우에만 제출하고 검토할 수 있습니다. 강좌를 구매하지 않고 살펴보기만 하면 특정 과제에 접근하지 못할 수 있습니다.

  • 수료증을 구매하면 성적 평가 과제를 포함한 모든 강좌 자료에 접근할 수 있습니다. 강좌를 완료하면 전자 수료증이 성취도 페이지에 추가되며, 해당 페이지에서 수료증을 인쇄하거나 LinkedIn 프로필에 수료증을 추가할 수 있습니다. 강좌 콘텐츠만 읽고 살펴보려면 해당 강좌를 무료로 청강할 수 있습니다.

궁금한 점이 더 있으신가요? 학습자 도움말 센터를 방문해 보세요.