|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/discrete-mathematics
课程评论：没有评论
课程名称：离散数学 课程概述：离散数学是计算机和信息科学的数学基础，同时也是一门极具趣味性的学科。学习者将熟悉一系列在计算机科学中无处不在的数学对象，如集合、函数、关系和图论。此外，更重要的是，学习者将达到一定的数学成熟度，能够理解形式语句及其证明，自行给出严谨证明，并得出有趣的结果。 本课程旨在保持严谨性而不至于过于正式。对于每个引入的概念，至少展示一个有趣的非平凡结果，并提供完整的证明，但会尽量减少形式符号的使用，更多地利用例子和图形。 课程主要涵盖以下主题：（1）集合、函数、关系；（2）枚举组合数学；（3）图论；（4）网络流与匹配。课程不涉及模算术、代数和逻辑等内容，因为这些主题略有不同，并且在Coursera上已经有其它专门的课程。 课程大纲： 1. **引言 - 离散数学中的基本对象**：介绍离散数学的基本对象，如集合、关系和函数，帮助学习者初步了解离散数学的独特性质。 2. **部分序**：正式介绍部分序，探讨关于它们的一些基本而深刻的事实。 3. **枚举组合数学**：探讨离散数学中的计数问题，如字母重排如何组合形成不同单词。 4. **二项式系数**：讨论二项式系数(n choose k)的计算及其在枚举组合数学中的重要性。 5. **渐近分析与O符号**：涉及渐近分析和常用的算法复杂度表示法。 6. **图论简介**：介绍图论的基本概念，图、循环、路径以及同构等。 7. **连通性、树与循环**：介绍树的基本特性以及如何检测树的同构性。 8. **欧拉与哈密尔顿循环**：讨论“耶路撒冷桥”的经典问题，给出欧拉图的特征及哈密尔顿路径的存在条件。 9. **生成树**：讨论图的生成树及其最小生成树的寻找算法。 10. **最大流与最小切**：探讨流网络，证明最大流最小切的对偶定理。 11. **二分图的匹配**：证明Hall定理和Kőnig定理，讨论与流网络的关系。 本课程将帮助学习者在理解和应用离散数学中获得扎实的基础。
Part: 1
Title:Introduction - Basic Objects in Discrete Mathematics
Description: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.
Part: 2
Title:Partial Orders
Description: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.
Part: 3
Title:Enumerative Combinatorics
Description: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.
Part: 4
Title:The Binomial Coefficient
Description: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.
Part: 5
Title:Asymptotics and the O-Notation
Description:
Part: 6
Title:Introduction to Graph Theory
Description: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.
Part: 7
Title:Connectivity, Trees, Cycles
Description: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.
Part: 8
Title:Eulerian and Hamiltonian Cycles
Description: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.
Part: 9
Title:Spanning Trees
Description: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.
Part: 10
Title:Maximum flow and minimum cut
Description:This module is about flow networks and has a distinctively algorithmic flavor. We prove the maximum flow minimum cut duality theorem.
Part: 11
Title:Matchings in Bipartite Graphs
Description: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.
Discrete mathematics forms the mathematical foundation of computer and information science. It is also a fascinating subject in itself. Learners will become familiar with a broad range of mathematical objects like sets, functions, relations, graphs, that are omnipresent in computer science. Perhaps more importantly, they will reach a certain level of mathematical maturity - being able to understand formal statements and their proofs; coming up with rigorous proofs themselves; and coming up with interesting results. This course attempts to be rigorous without being overly formal. This means, for every concept we introduce we will show at least one interesting and non-trivial result and give a full proof. However, we will do so without too much formal notation, employing examples and figures whenever possible. The main topics of this course are (1) sets, functions, relations, (2) enumerative combinatorics, (3) graph theory, (4) network flow and matchings. It does not cover modular arithmetic, algebra, and logic, since these topics have a slightly different flavor and because there are already several courses on Coursera specifically on these topics.
