À propos de ce cours
14,453 consultations récentes

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Niveau intermédiaire

Approx. 40 heures pour terminer

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

Anglais

Sous-titres : Anglais

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Niveau intermédiaire

Approx. 40 heures pour terminer

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

Anglais

Sous-titres : Anglais

Programme du cours : ce que vous apprendrez dans ce cours

Semaine
1
5 heures pour terminer

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 vidéos (Total 27 min), 3 quiz
2 vidéos
Sets, Relations, Functions10 min
1 exercice pour s'entraîner
Sets, relations, and functions1h 30min
Semaine
2
4 heures pour terminer

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 vidéos (Total 28 min), 2 quiz
2 vidéos
Mirsky's and Dilworth's Theorem14 min
1 exercice pour s'entraîner
Partial orders, maximal and minimal elements, chains, antichains2 h
Semaine
3
5 heures pour terminer

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 vidéos (Total 35 min), 2 quiz
3 vidéos
Evaluating Simple Sums8 min
Pascal's Triangle14 min
1 exercice pour s'entraîner
Counting Basic Objects2 h
Semaine
4
4 heures pour terminer

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 vidéos (Total 55 min), 3 quiz
3 vidéos
Estimating the Binomial Coefficient22 min
Excursion to Discrete Probability: Computing the Expected Minimum of k Random Elements from {1,...,n}18 min
1 exercice pour s'entraîner
An Eagle's View of Pascal's Triangle8 min
Semaine
5
5 heures pour terminer

Asymptotics and the O-Notation

...
1 vidéo (Total 14 min), 3 quiz
1 exercice pour s'entraîner
The Big-O-Notation18 min
Semaine
6
5 heures pour terminer

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 vidéos (Total 41 min), 3 quiz
3 vidéos
Graph Isomorphism, Degree, Graph Score13 min
Graph Score Theorem16 min
1 exercice pour s'entraîner
Graphs, isomorphisms, and the sliding tile puzzle30 min
Semaine
7
5 heures pour terminer

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 vidéos (Total 36 min), 3 quiz
3 vidéos
Cycles and Trees15 min
An Efficient Algorithm for Isomorphism of Trees12 min
1 exercice pour s'entraîner
Cycles and Trees30 min
Semaine
8
3 heures pour terminer

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 vidéos (Total 27 min), 2 quiz
2 vidéos
Hamilton Cycles - Ore's and Dirac's Theorem16 min
1 exercice pour s'entraîner
Hamiltonian Cycles and Paths1 h
Semaine
9
5 heures pour terminer

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 vidéos (Total 29 min), 3 quiz
2 vidéos
The Number of Trees on n Vertices15 min
1 exercice pour s'entraîner
Spanning Trees40 min
Semaine
10
3 heures pour terminer

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 vidéos (Total 29 min), 2 quiz
2 vidéos
Flow Networks: The Maxflow - Mincut Theorem15 min
1 exercice pour s'entraîner
Network flow8 min
Semaine
11
3 heures pour terminer

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 vidéos (Total 46 min), 1 quiz
3 vidéos
Matchings in Bipartite Graphs: Hall's and König's Theorem16 min
Partial Orders: Dilworth's Theorem on Chains and Antichains15 min
3.5
32 avisChevron Right

Principaux examens pour Mathématiques discrètes

par NPOct 23rd 2017

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

par AGDec 5th 2018

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

Enseignant

Avatar

Dominik Scheder

Assistant Professor
The Department of Computer Science and Engineering

À propos de Université Jiao-tong de Shanghai

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

Foire Aux Questions

  • Une fois que vous êtes inscrit(e) pour un Certificat, vous pouvez accéder à toutes les vidéos de cours, et à tous les quiz et exercices de programmation (le cas échéant). Vous pouvez soumettre des devoirs à examiner par vos pairs et en examiner vous-même uniquement après le début de votre session. Si vous préférez explorer le cours sans l'acheter, vous ne serez peut-être pas en mesure d'accéder à certains devoirs.

  • Lorsque vous achetez un Certificat, vous bénéficiez d'un accès à tout le contenu du cours, y compris les devoirs notés. Lorsque vous avez terminé et réussi le cours, votre Certificat électronique est ajouté à votre page Accomplissements. À partir de cette page, vous pouvez imprimer votre Certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez seulement lire et visualiser le contenu du cours, vous pouvez accéder gratuitement au cours en tant qu'auditeur libre.

D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.