课程简介

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

课程大纲

国家精品在线开放课程认定评审专家请关注:

由于国外平台访问课程视频较慢,评审专家可在华文慕课平台查看视频等静态内容,在edX查看互动情况,链接:https://www.edx.org/course/li-lun-ji-suan-ji-ke-xue-ji-chu-pekingx-04830260x-0



第一章: 有穷自动机


第二: 正则语言


第三:上下文无关文法


第四:下推自动机


第五: 图灵机


第六:(不)可计算性


第七: 计算复杂性


第八: NP完全理论


课程说明

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


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


参考资料

拓展阅读

其他

主讲教师

刘田   副教授

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

课程助教

  • jingpinmooc

相关课程推荐

  • 正在进行
    程序设计实习
    《程序设计实习》课程是北京大学的本科生主干基础课程。本科生程序设计类基础课程体系包含了四门课,按修课顺序分别为:计算概论、程序设计实习、数据结构与算法、算法分析与设计。
  • 正在进行
    操作系统与虚拟化安全
    操作系统是计算机系统的基础软件,而系统虚拟化已成为云计算平台的核心技术,没有它们提供的安全性,这些计算机系统及其上数据的安全性都将无法保障。本课程将从理论与工程实践相结合的角度,介绍操作系统(Linux)与系统虚拟化(Xen)安全相关理论、技术和方法,包括:安全概念、安全机制、安全模型、安全体系结构、安全开发方法、安全标准与评测方法等,帮助你深入学习和理解该领域的知识体系、实践技术和方法。
  • 正在进行
    需求分析
    需求开发与管理是项目的基础,本课程将对需求定义、需求捕获、需求分析与建模、需求规格化、需求管理提供一套可以实践的解决方案,通过讲解和案例分析指导学员完成一系列练习,使学员对需求分析与需求管理的方法和过程建立较深刻的认识和实际操作的能力。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

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

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!