课程简介

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

课程大纲


第一章: 有穷自动机


第二: 正则语言


第三:上下文无关文法


第四:下推自动机


第五: 图灵机


第六:(不)可计算性


第七: 计算复杂性


第八: NP完全理论


课程说明

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


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


参考资料

拓展阅读

其他

主讲教师

刘田   副教授

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

课程助教

  • jingpinmooc

相关课程推荐

  • 正在进行
    程序设计实习
    《程序设计实习》课程是北京大学的本科生主干基础课程。本科生程序设计类基础课程体系包含了四门课,按修课顺序分别为:计算概论、程序设计实习、数据结构与算法、算法分析与设计。
  • 正在进行
    设计模式
    本课程介绍什么是设计模式,设计模式的分类及每种设计模式的具体结构类图、角色和java实例,还包括每种设计模式的优缺点和使用场景。
  • 正在进行
    大数据分析中的算法
    大数据给数据分析和处理带来了前所未有的机遇和挑战。本课程介绍大数据分析中一些算法:数据的稀疏和低秩表达,稀疏和低秩矩阵优化,社交网络计算中的图与网络流问题,机器学习和数据挖掘的最优化算法,随机优化算法,强化学习等等。通过本课程学习,掌握最优化的基本概念,典型的几类最优化建模方法,相关优化问题的基本计算方法,并能熟练调用基于MATLAB或Python等语言的典型优化软件程序求解一些标准的优化问题,灵活运用所讲授的算法和理论求解一些非标准的优化问题。达到锻炼将实际问题建立合适最优化模型的能力,选择合适的现有软件包和算法的能力,遇到没有现成算法自己实现简单算法的能力。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

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

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!