课程简介

本课程面向非计算机软件专业本科生及相关IT行业从业人士,介绍计算机科学和信息技术理论基础的概念和思想方法。

课程大纲


第一章:数理逻辑


1.1 命题演算:命题与联结词、重言式、范式、命题演算形式系统PC


1.2 谓词演算:个体谓词和量词、一阶谓词公式、谓词演算形式系统FC,自然推理系统ND




第二章:集合论


2.1 集合基本概念:集合定义、集合基本运算、归纳定义和归纳法证明


2.2 关系:关系基本概念、基本性质、等价关系、序关系


2.3 函数:函数定义、函数合成、基本函数类、逆函数




第三章:图论


3.1 图论基本概念:图定义、图的同构、路径回路、可达性和连通性、图的矩阵表示


3.2 特殊图:欧拉图、哈密顿图、二分图、平面图、树




第四章:抽象代数


4.1 代数结构的定义


4.2 代数结构中特殊元素


4.3 代数结构的同态与同构




第五章:形式语言与自动机


5.1 形式语言基本概念:形式语言定义、Chomsky分类体系、短语结构语法、语法和语言表示


5.2 有限状态自动机:定义和状态图、泵引理、机器同余和商机器、机器化简、有限状态机实现计算


5.3 图灵机和可计算理论:图灵机、哥德尔编码、通用图灵机、停机问题和哥德尔不完全性定理


课程说明

离散数学是计算机科学的基础理论,离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功,离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。


本课程介绍计算机科学和信息技术理论基础的概念和思想方法,介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念,介绍离散数学基本概念和空间信息技术之间的联系与结合,培养学生理解和掌握离散数学基本概念,采用形式化方法分析问题,并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。


参考资料

1.[O158/75]计算机科学中的离散结构,王元元, 张桂芸编著,机械工业出版社 2004


2.[O158/60]离散数学导论,王元元, 张桂芸编著,科学出版社 2002


3.[O158/36]离散数学,王元元,李尚奋编著,科学出版社 1994


以上三本书实际上内容基本相同,选择其中一本即可,如果找不到,其它离散数学教材也没有问题。


拓展阅读

其他

先修知识

先修过《高等数学》《计算概论》《数据结构与算法》等理科基础课程最好,但这些先修课并不是必须的,有基本数理概念也可以选修本课程。


授课形式

本课程授课视频一般每段为6-9分钟左右,每段视频会有1-2个随堂测试,每周将安排1次作业,结课采用考试形式。


常见问题

Q:这是一门数学课么?

A:离散数学跟你在中学里学过的代数、几何,或者大学里学过的高等数学、线性代数都不一样,它研究推理过程如何变成公式演算,分立对象之间的关系以及把它们放在一起构成更复杂的系统。


Q:学了这门课会有什么收获?

A:离散数学是计算机科学的理论基础,所以对理科学生进一步学习程序设计、操作系统、数据库等等计算机类课程有很大帮助,你以后会在这些课程里反复用到离散数学的基本概念。如果你已经开始了IT行业的职业生涯,离散数学对提升你对工作的高度,拓宽行业视野也会有很大的帮助。


Q:课程介绍特别提了本课程面向“非”计算机软件专业,这意味着什么?

A:计算机软件专业对于离散数学教学的内容更为细致,要求更高,通常还会分成几门课程来讲述。本课程属于概论性质,主要是对基本概念的理解和掌握,综合性更强。


Q:课程介绍视频里还提到理解科幻作品?

A:在信息技术飞速发展的今天,人和机器的关系越来越被人们所重视,越来越多的小说、电影通过科幻的形式讨论未来技术发展对人类社会的影响。通过本课程的学习,你可以认识到机器的本质,理解科学知识体系的根基与边界。再看这些作品,你会有不同的眼界和体验。


主讲教师

陈斌   计算机软件、地理信息系统

博士,北京大学地球与空间科学学院副教授,硕士生导师。1995、1998、2002年在北京大学计算机科学与技术系软件专业分别获得学士、硕士和博士学位;2002年进入北京大学遥感所博士后流动站,2004年出站后留校从事教学科研工作至今。在攻读硕士期间开始进入GIS研究领域,主要研究兴趣在虚拟地理环境、空间信息分布式计算领域,主持和参加过十余项国家级科研项目,包括自然科学基金重大项目、863计划课题、国家科技支撑计划、科技基础性工作专项资金项目等,受聘担任科技部国家遥感中心主持的国产GIS/RS软件测评专家委员会委员。获校级奖励4项,省部级奖励2项。发表论文40余篇,已培养研究生12人,获授权专利3项,受理2项,获软件著作权8项。

课程助教

  • yichaopku

  • tomato8965

  • jingpinmooc

  • 陈旭

相关课程推荐

  • 正在进行
    医学统计学与SPSS软件(基础篇)
    本课程适用于医学各专业的学生以及医疗卫生工作者。 课程包括基础统计学方法及SPSS软件应用:绪论、统计描述、t检验、方差分析、卡方检验、直线回归与相关、秩和检验。通过本课程的学习,学生能掌握医学统计学的基本方法及SPSS软件的应用技能,培养统计思维能力,并在医学科研工作中能灵活地、正确地运用统计学。
  • 正在进行
    变分学
    变分学是数学分析的一个重要组成部分,是一门与其他数学分支密切联系、并有广泛应用的数学学科。近几十年来,变分学不论是在理论上还是在应用中都有了很大发展,与数学其他分支的联系也更加紧密,已经成为大学数学教育不可缺少的部分。
  • 正在进行
    科学研究方法-年轻生物医学研究者的生存技巧
    This is a brief introduction of the Workshops on “Scientific Methods: Survival Skills for Young Biomedical Investigators,” that I gave in 2012 and 2018 at the School of Life Sciences Peking University. I have a long-standing friendship and collaboration with Professors Zhai Zhonghe and Ding Mingxiao (former Dean of the School of Life Sciences) to study intermediate filaments and membrane specialization. Professor Ding did two sabbaticals in my lab in NYU School of Medicine, which were productive, fun and memorable. Three of us co-supervised a graduate student, Feng-Xia Liang, who is now a Professor and Director of the Microscopy Core Laboratory at NYU School of Medicine. Professor Deng Hongkui, after making a ground-breaking discovery at NYU of the T cell receptor of AIDS virus, returned to PKU in 2002 and also became a wonderful friend.

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

1. 试试去广告邮件、垃圾邮件目录看看

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!