课程简介

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

课程大纲


第一章: 有穷自动机


第二: 正则语言


第三:上下文无关文法


第四:下推自动机


第五: 图灵机


第六:(不)可计算性


第七: 计算复杂性


第八: NP完全理论


课程说明

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


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


参考资料

拓展阅读

其他

主讲教师

刘田   副教授

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

课程助教

  • jingpinmooc

相关课程推荐

  • 正在进行
    软件工程
    本次软件工程MOOC课程是一门导论性课程,在11章、21次课的时间里,我们将全面介绍软件工程所涉及的各方面知识,包括软件过程、软件需求、结构化分析和设计方法、面向对象分析和设计方法、敏捷开发方法、软件测试、软件项目管理、软件开发工具和环境。通过课程讲授,让大家初步了解软件开发和维护的方法学,为进一步深入学习各专题打下基础。
  • 正在进行
    数据分析软件平台----ROOT
    ROOT(下载地址: https://root.cern.ch/ )是科学数据处理的平台。利用它,可将数据(普通数值或C++类)以压缩二进制的办法保存起来并且可以很方便的对其进行挑选、画1维、2维、3维直方图、散点图、拟合等分析工作。利用个人电脑可以登录到远程服务器进行多个文件大批量操作分析数据。ROOT还提供数学及统计工具、并行处理、神经网络及多变量分析软件包,实现多种分布的数据样本产生工具以便于对复杂问题的MC模拟开发,可方便地绘制高质量的图形并存储成pdf等不同格式。对于代码可以不需要编译即可进行解释运行以追求便利也可轻松实现编译运行以追求速度。 该软件现为国际上高能物理数据分析的必备工具,也可用于低能物理、工程、经济、军事等需要处理和分析科学数据及软件开发的领域。通过本培训的学习,学员可以在短时间将数据处理能力快速提高。ROOT系全免费开源软件且可运行在Windows和Linux下,国际上有大量科研人员及科研机构使用,学员掌握该软件后,有助于在参与国际合作和交流的科研活动过程中迅速适应国际科研环境。
  • 正在进行
    解密教育的技术变革史
    互联网并非人类历史上第一次“信息技术”革命。人类历史上一共出现过5种媒介技术:口头语言、手工抄写/羊皮书、印刷技术、广播电视和互联网。 媒介技术提供的记录和传承功能,对人类的群体社会认知,带来了革命性的影响。西方历史上曾经发生的两次文明的大发展,都正好处于媒介技术变革前后。希腊文明处于希腊从口传到手工抄写的媒介技术变革中;近代科学史上的哥白尼革命,又正好处于欧洲从手工抄写到机器印刷的技术转型中;今天,轮到了信息技术…… 吟唱、诗歌、戏曲、绘画、文字书写等,都曾经是一种表达“技术”;《荷马史诗》、《圣经》都曾经充当过识字课本;口头语言、羊皮纸卷、印刷书、广播电视,都是曾经的“教育技术”。 这门课程从重新定义教育和人这两个核心概念开始,带着你从媒介史、知识产业分工配套体系、教学模式和教育组织方式等不同的视角,游历人类一路走来传播生态环境、知识产业、教育教学的发展过程,从中寻找媒介技术影响教育变革的规律,指导学习者迎接未来教育变革的挑战,寻找创新和发展方向!

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

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

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!