课程简介

本课程面向非计算机软件专业本科生及相关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

相关课程推荐

  • 正在进行
    数据结构与算法(下)
    计算机是现代社会中用于解决问题的重要工具。利用计算机解决实际问题需要将问题抽象,并对数据进行操作,最后通过计算机程序求解问题。而本门课程主要内容就是对以上内容进行研究。 该课程并未正式开课,报名后仅提供前三周课程视频预览,开课信息敬请持续关注。
  • 正在进行
    自然地理学概论(下)
    地理学以地球表层的人地关系作为研究的核心,强调整体性和个体性,而“自然地理学”是地理学的重要分支之一,它是研究地球表层的自然景观及其组成要素和自然现象在空间上相互依存与相互作用机理的一门综合性很强的学科。 本门课程是《自然地理学概论》的下篇——地质过程与生物循环。具体讲授的内容包括:(1)地球表层系统内物质循环过程中的固体地球物质循环和地球化学生物循环过程;各个循环过程的主要驱动力及特点。(2)地球表层系统的整体特征,包括地球表层系统的圈层结构、时间结构、地域结构和时空尺度;地球表层系统的功能,分为圈层之间的相互作用和人与环境的相互作用;地球表层系统的概念模型,分为地球表层系统的驱动力量和控制过程。 与本门课程同时开放的《自然地理学概论》上篇——太阳辐射与气候形成,主要介绍太阳能在大气、陆地和海洋之间的传输转化过程,以及由其引起的大气和海洋运动、地球表层气候形成等,欢迎同学们选择学习!
  • 正在进行
    自然地理学概论(上)
    地理学以地球表层的人地关系作为研究的核心,强调整体性和个体性,而“自然地理学”是地理学的重要分支之一,它是研究地球表层的自然景观及其组成要素和自然现象在空间上相互依存与相互作用机理的一门综合性很强的学科。 本门课程是《自然地理学概论》的上篇——太阳辐射与气候形成。具体讲授的内容包括:(1)自然地理学的学科体系和当代自然地理学所面临的重要科学问题;一般系统论的基本概念和原理,并利用系统论的观点阐释地球表层系统的基本性质。(2)地球表层系统最主要的能量来源——太阳能——进入系统并在大气、陆地和海洋之间传输与转化的过程。不同纬度地面能量收支的不均衡分布产生了大气环流;海洋上空的大气运动推动着表层海水运动,形成表层大洋环流;海水密度的差异驱动深层海水运动,形成深层大洋环流。大气环流和大洋环流在全球尺度上调整着地表能量收支的不平衡分布状况。(3)地球表层系统内的物质循环过程与机理,并具体介绍三种物质循环过程中的水分循环部分。 与本门课程同时开放的《自然地理学概论》下篇——地质过程与生物循环,主要介绍地球表层物质循环的固体地球物质循环和生物地球化学循环过程,以及地球表层系统的整体性特征,欢迎同学们选择学习!

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

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

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!