课程简介

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

课程大纲


第一章: 有穷自动机


第二: 正则语言


第三:上下文无关文法


第四:下推自动机


第五: 图灵机


第六:(不)可计算性


第七: 计算复杂性


第八: NP完全理论


课程说明

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


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


参考资料

拓展阅读

其他

主讲教师

刘田   副教授

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

课程助教

  • jingpinmooc

相关课程推荐

  • 正在进行
    算法设计与分析(高级)
    “算法设计与分析”是计算机科学与技术专业的一门核心课程。通过学习算法不但对学习其他专业课程奠定了扎实的基础,也对培养学生的计算思维和求解问题的能力起到重要的作用。算法与计算复杂性理论一直是计算机科学研究的热点领域。面对各个应用领域的大量实际问题,最重要的是根据问题的性质选择正确的求解思路,即找到一个好的算法。特别在复杂的、海量信息的处理中,一个好的算法往往起到决定性的作用。 算法设计与分析涉及内容较多,根据MOOC课程的教学特点和需求,我们将它分成两个部分。其中“算法设计与分析(1)”主要讲授有关算法的基础知识和通用设计技术,包括算法的基本概念和数学基础、分治策略、动态规划、贪心法、回溯和分支限界等。“算法设计与分析(2)”是在上述基础上介绍两类重要问题的建模和算法设计,并进一步讨论问题难度的界定和困难问题的应对策略。这次开课的是第二部分“算法设计与分析(2)”。选修本课程的学生应该预先修过“算法设计与分析(1)”或者具有相关的基础。“算法设计与分析(1)”已经在华文慕课平台上线,网址是:http://www.chinesemooc.org/mooc/4748/,需要了解相关教学内容的同学可以访问。
  • 正在进行
    架构设计
    本课程介绍软件架构分析和设计过程和步骤、视图和文档、软件架构应用与常用的架构模式/策略/原则等诸多架构实际问题,透视软件架构是如何设计和实现的整个流程, 并且介绍应该如何应用系统架构设计为后期的详细设计和应用开发提供指导
  • 正在进行
    工程管理定量分析方法
    本课程的目标是针对工程管理的各种问题,采用定量分析的方法,通过把问题抽象成数学问题、建立模型、利用计算机软件求解等步骤,解决工程管理中的问题。课程培养学生进行理性思维和逻辑思维、运用方法和工具解决工程管理中实际问题的能力。课程采用课堂教学与案例教学相结合的授课方法。 课程作为工程管理硕士必修课,已经在北京大学校内开设多年。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

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

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!