离散数学
分享
课程详情
课程评价
spContent=为什么“麻花辫”古今中外都只有一种编法儿?许多有趣的数学问题/游戏/魔术,背后的原理又是什么?让我们来共同拿起离散数学的柳叶刀,剖析、鉴赏、玩味。体会到思考和解决是生活的快乐之本、幸福之源!作为计算机科学和软件科学的基础,本课程讲解详尽、练习丰富,讨论区无零回复——有问必答!
—— 课程团队
课程概述

“离散数学”是面向所有专业的本科生、专科生和社会公众开放的基础课程。
“离散数学”研究不同离散量的各自结构、规律及相互关系的一门学科。它在程序设计语言、数据结构、操作系统、软件工程、数据库原理、计算机网络、人工智能、软件设计形式化等方面都有广泛的应用,具有研究性、实践性、创新性强的特点,不仅强调对知识的理解和掌握,还强调方法论的学习。

本课程共8讲,学生学习全部课程内容并完成测验、作业大约共计8周;每讲之后学生需要完成单元测试及作业;还要参加期末考试。

课程大纲

第1讲  基础知识

1.2  数论基础

1.1  集合与序列

1.4  布尔矩阵及其运算

1.3  计数基础

第1讲单元作业

第1讲单元测试

第2讲  命题逻辑

扩展内容——新裙子的颜色

2.3  命题逻辑的等值演算

扩展内容——说谎人与妖魔戒指

扩展内容——从一个竞赛题目说起

扩展内容——早餐吃的什么

2.5  命题逻辑的推理

扩展内容——对偶

扩展内容——逻辑联接词的完备集

2.4  范式

2.1  命题逻辑的基本概念

2.2  命题公式及其分类

第2讲单元作业

第2讲单元测试

课程介绍

课程介绍

第3讲  谓词逻辑

3.5  前束范式

3.6 谓词逻辑的推理

3.2  谓词公式及分类

3.4  谓词逻辑的等值演算

扩展内容——Prolog语言

3.1  谓词与量词

3.3  自然语句形式化

第3讲单元测试

第3讲单元作业

第4讲  二元关系

4.2  关系的运算

4.3  关系的性质

4.1  关系及其表示

4.5  等价关系和集合的划分

4.4  关系的闭包

第4讲单元测试(2)

第4讲单元测试(1)

第4讲单元作业

第5讲  函数

5.4  逆函数

扩展内容——集合的势

5.3  函数的复合

5.2  函数的性质

扩展内容——置换

5.5  计算机科学中的常用函数

5.1  函数的定义

第5讲单元作业

第5讲单元测试

作业讲解

第2讲单元作业讲解

第4讲单元作业讲解

第3讲单元作业讲解

第7讲单元作业讲解

第5讲单元作业讲解

第1讲单元作业讲解

第6讲单元作业讲解

第8讲单元作业讲解

第6讲  偏序关系

扩展内容——信息流的安全格模型

扩展内容——Chomp游戏

6.1  偏序关系和偏序集

6.2  偏序集中的特殊元素

6.3  格

第6讲单元测试

第6讲单元作业

第7讲  图论

7.1 图的基本概念

7.3 哈密尔顿图

7.6 图的着色

7.2 欧拉图

扩展内容——中国邮路问题

扩展内容——抱子甘蓝游戏(Brussels sprouts)

7.4 平面图

扩展内容——顿时错乱游戏

7.5 顶点支配、独立与覆盖

扩展内容——抽芽游戏(Sprouts)

第7讲单元测试

第7讲单元作业

第8讲  树及其应用

8.4 根树

8.6 最优二叉树与霍夫曼编码

第8讲单元作业

第8讲单元测试

8.3 最短道路树

8.5 二叉树的遍历

8.1 无向树

8.2 支撑树及其应用

可自学章节——有限语言与自动机

正则文法和有限状态自动机

巴科斯-诺尔范式和语法图

有限状态自动机

正则表达式

扩展内容——林登麦伊尔系统

形式语言

字母表与串

文法

文法的分类

非确定性有限状态自动机

可自学章节——代数结构

代数结构

扩展内容——麻花辫

扩展内容——魔方

环与域

扩展内容——伯恩赛德引理与波利亚定理

专题

汉诺塔专题

正多面体

格路问题专题

裴蜀等式专题

“德·布鲁因”专题

格雷码专题

鸽巢原理的纸牌魔术

谢尔宾斯基三角形

证书要求

需完成课程的全部学习任务。总成绩组成:各讲测验总得分占20%,各讲作业总得分占40%,期末考试得分占40%。总成绩为60分至84分,可获得合格证书,总成绩为85分至100分,可获得优秀证书。

参考资料

指定教材:《离散数学及应用(第2版)》

作者:刘铎

出版社:清华大学出版社

ISBN:9787302496632


亚马逊有售

常见问题

Q :  课程难么?
A :  如果套用常见的回答就是“学就不难,不学就难”。而就我在学校授课的真实感受而言,很多学生反映“就跟着刘老师走,离散课玩儿着似的就学下来了”、“期末要考试了但是不知道复习什么,因为感觉没什么难的”。

Q : 需要什么预备知识么? 
A :  其实”离散数学“对于预备知识的要求比较少,只要具有高中阶段知识储备就可以接受几乎所有教学内容。与”知识“相比,这门课程其实更加看重”思维“,而且通过这门课程的学习,可以使你的逻辑分析能力更加傲人!

Q : 学会这门课能干吗? 
A :   这个问题真的很难回答,我始终记得我大一时侯张贤科教授反问我们”8+5=13有什么用?你怎么就一定是买了5个橘子又买了8个橘子呢?你就不能先买6个橘子再买7个橘子?“
基础和底蕴也许不能让人迈开最大的第一步,也不能给人立刻增加上闪亮的光环和丰富的谈资,但它却可以最终决定人能走多高、走多远。而“离散数学 ”就是这样一门课程。

 
Q :  视频和教材完全匹配么?
A :  严格地讲——不完全匹配。由于课时限制,本开放课程视频只是教材内容的真子集。但:1、逻辑脉络是一致的;2、全书内容本人都录制了视频,如果大家需要可以在讨论区留言,本人将在课程最后作为附录给出大家感兴趣的部分。

Q :  教材可有习题解答?
A :  暂时还没有编写出版,未来有所考虑。不过如果学员自己做了习题而不知正确与否可以在讨论区留言、贴图,本人将解答讲评。

Q :  有没有更多的有趣案例?
A :  本人在知乎还在持续建设专栏”Liu言杂记“,其中有(但不仅限于)大量”离散数学“相关小文,大家有兴趣的话可以关注,^ ^ 。

Liu言杂记