Informações sobre o curso
3.5
92 classificações
32 avaliações

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Nível intermediário

Aprox. 40 horas para completar

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

Inglês

Legendas: Inglês

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Nível intermediário

Aprox. 40 horas para completar

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

Inglês

Legendas: Inglês

Programa - O que você aprenderá com este curso

Semana
1
5 horas para concluir

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 vídeos (total de (Total 27 mín.) min), 3 testes
2 videos
Sets, Relations, Functions10min
1 exercício prático
Sets, relations, and functions30min
Semana
2
4 horas para concluir

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 vídeos (total de (Total 28 mín.) min), 2 testes
2 videos
Mirsky's and Dilworth's Theorem14min
1 exercício prático
Partial orders, maximal and minimal elements, chains, antichainss
Semana
3
5 horas para concluir

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 vídeos (total de (Total 35 mín.) min), 2 testes
3 videos
Evaluating Simple Sums8min
Pascal's Triangle14min
1 exercício prático
Counting Basic Objectss
Semana
4
4 horas para concluir

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 vídeos (total de (Total 55 mín.) min), 3 testes
3 videos
Estimating the Binomial Coefficient22min
Excursion to Discrete Probability: Computing the Expected Minimum of k Random Elements from {1,...,n}18min
1 exercício prático
An Eagle's View of Pascal's Triangle8min
Semana
5
5 horas para concluir

Asymptotics and the O-Notation

...
1 vídeo (total de (Total 14 mín.) min), 3 testes
1 exercício prático
The Big-O-Notation18min
Semana
6
5 horas para concluir

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 vídeos (total de (Total 41 mín.) min), 3 testes
3 videos
Graph Isomorphism, Degree, Graph Score13min
Graph Score Theorem16min
1 exercício prático
Graphs, isomorphisms, and the sliding tile puzzle30min
Semana
7
5 horas para concluir

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 vídeos (total de (Total 36 mín.) min), 3 testes
3 videos
Cycles and Trees15min
An Efficient Algorithm for Isomorphism of Trees12min
1 exercício prático
Cycles and Trees30min
Semana
8
3 horas para concluir

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 vídeos (total de (Total 27 mín.) min), 2 testes
2 videos
Hamilton Cycles - Ore's and Dirac's Theorem16min
1 exercício prático
Hamiltonian Cycles and Pathss
Semana
9
5 horas para concluir

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 vídeos (total de (Total 29 mín.) min), 3 testes
2 videos
The Number of Trees on n Vertices15min
1 exercício prático
Spanning Trees40min
Semana
10
3 horas para concluir

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 vídeos (total de (Total 29 mín.) min), 2 testes
2 videos
Flow Networks: The Maxflow - Mincut Theorem15min
1 exercício prático
Network flow8min
Semana
11
3 horas para concluir

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 vídeos (total de (Total 46 mín.) min), 1 teste
3 videos
Matchings in Bipartite Graphs: Hall's and König's Theorem16min
Partial Orders: Dilworth's Theorem on Chains and Antichains15min
3.5
32 avaliaçõesChevron Right

Melhores avaliações

por NPOct 23rd 2017

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

por AGDec 5th 2018

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

Instrutores

Avatar

Dominik Scheder

Assistant Professor
The Department of Computer Science and Engineering

Sobre Universidade de Shanghai Jiao Tong

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

Perguntas Frequentes – FAQ

  • Ao se inscrever para um Certificado, você terá acesso a todos os vídeos, testes e tarefas de programação (se aplicável). Tarefas avaliadas pelos colegas apenas podem ser enviadas e avaliadas após o início da sessão. Caso escolha explorar o curso sem adquiri-lo, talvez você não consiga acessar certas tarefas.

  • Quando você adquire o Certificado, ganha acesso a todo o material do curso, incluindo avaliações com nota atribuída. Após concluir o curso, seu Certificado eletrônico será adicionado à sua página de Participações e você poderá imprimi-lo ou adicioná-lo ao seu perfil no LinkedIn. Se quiser apenas ler e assistir o conteúdo do curso, você poderá frequentá-lo como ouvinte sem custo.

Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.