Об этом курсе
3.6
Оценки: 89
Рецензии: 31

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 тестов
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
Рецензии: 31Chevron 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. Просто ознакомиться с содержанием курса можно бесплатно.

Остались вопросы? Посетите Центр поддержки учащихся.