课程简介

通过这门课程的学习,学生将了解计算理论的基础知识,掌握有效计算的概念。本课程的教学内容包括:形式语言与自动机理论、可计算性理论、计算复杂性理论等三个部分。这些内容分别回答下列问题:(1)有哪些计算装置?它们的能力如何?(2)什么是计算?哪些问题是(不)可计算的?(3)什么是有效计算?哪些问题是(不)可有效计算的?通过这门课程的学习,学生将了解计算理论的基础知识,掌握有效计算的概念。

课程大纲


第一章: 有穷自动机


第二: 正则语言


第三:上下文无关文法


第四:下推自动机


第五: 图灵机


第六:(不)可计算性


第七: 计算复杂性


第八: NP完全理论


课程说明

本课程的教学方式包括教学录像片段(每段录像8-20分钟,内含1-2个测验问题),教学录像之外的书面作业,以及(必须参加的)期末考试。


本课程课程的总长度为8周,每周教学录像长度大约120分钟。需要的预备知识是离散数学(集合论、数理逻辑、图论等)的基本概念


参考资料

拓展阅读

其他

主讲教师

刘田   副教授

北京大学信息学院计算机系副教授,主要研究方向为算法分析与计算复杂性理论。主持过两项国家自然科学基金项目以及多项其他研究课题,发表了多篇论文和译著。长期主讲“集合论与图论”、“理论计算机科学基础”等课程,2006年和2013年先后两次获得了北京大学教学优秀奖。

课程助教

  • jingpinmooc

相关课程推荐

  • 正在进行
    计算机组成
    本课程的重点在于计算机内部的主要部件以及各部件之间的联系,主要内容包括:冯·诺依曼计算机结构的要点,计算机执行指令的工作过程,当前流行的指令系统的分析对比,高级语言、汇编语言和机器语言之间的关系等。
  • 正在进行
    计算概论PartB
    理解“结构化程序设计的基本思想”,掌握“C程序设计的基本技巧”,养成“良好的编程习惯和编程风格”,编写出“真正具有生命力的计算机程序”。完成这门课的学习,你将能解释C程序设计语言的基本概念与知识,并且使用C语言编写计算机程序解决生活工作中的实际问题。
  • 正在进行
    算法设计与分析
    本课程的内容分成两大部分:算法的基础知识、通用算法设计技术与分析方法。 第一部分是算法基础知识,约占20%,主要介绍算法相关的基本概念和数学基础。比如,什么是算法的伪码描述?什么是算法最坏情况下和平均情况下的时间复杂度?算法时间复杂度函数的主要性质,算法复杂度估计中常用的数学方法,如序列求和及递推方程求解。 第二部分是通用的算法设计技术与分析方法,主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径,并给出一些重要的应用。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

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

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!