课程简介

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

课程大纲


第一章: 有穷自动机


第二: 正则语言


第三:上下文无关文法


第四:下推自动机


第五: 图灵机


第六:(不)可计算性


第七: 计算复杂性


第八: NP完全理论


课程说明

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


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


参考资料

拓展阅读

其他

主讲教师

刘田   副教授

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

课程助教

  • jingpinmooc

相关课程推荐

  • 正在进行
    操作系统原理
    《操作系统原理》是针对计算机科学技术专业三年级本科生开设的一门专业基础课程。本课程着重学生系统观的培养,通过重点讲述操作系统的内部结构、工作原理及典型技术的实现,使学生建立起对操作系统的整体及各个功能模块的认识,从而系统掌握计算机的专业知识,进一步提升学生的软件开发能力乃至系统软件开发能力。
  • 正在进行
    生物统计
    得益于现代科学技术的快速发展,目前生物科学家可以在短时间内产生大量的数据。这些生物技术的普及使得生物大数据的分析已经变成了生物学研究及应用的关键。在此课程中,我们将主要讲授在生物数据分析中特别是近年来高通量生物数据分析中常用的统计方法,并基于软件R介绍利用这些方法进行生物数据分析的具体实例。本课程无指定教材,但可参考所列参考资料。本课的视频和文字内容仅用于课程学习,仅允许登陆本慕课的同学观看,未经任课教师本人授权,禁止课程之外的下载和传播。
  • 即将开始
    推荐系统
    随着信息技术的飞速发展和互联网的全面普及,加快了数据产生和信息传播的速度。这为人们的生活和工作提供了便捷,但同时也带来了困扰:信息超载。为解决这一问题,搜索引擎和推荐系统两种信息过滤系统应运而生。不同于搜索引擎需要“用户主动寻找信息”且反馈结果“千人一面”,推荐系统的目标是“系统主动推送信息”且推荐结果“千人千面”。由于推荐系统能够让用户、平台、商家等多方受益,它已成功应用于各行各业的各种平台和应用,并已成为互联网(特别是移动互联网)应用和服务的一种标配。 本课程主要介绍推荐系统中的各种常用算法和一些典型应用。通过本课程的学习,学生不仅可以掌握各种常用推荐算法的思想、原理和实现,同时还能熟悉各种推荐算法的应用场景和一些典型的应用案例,并把握推荐系统未来的发展方向。 本课程适合计算机科学与技术、软件工程、数据科学、人工智能等专业的高年级本科生和研究生选修,也适合于期望从事推荐系统、搜索引擎、数据挖掘等研发工作的相关人员学习。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

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

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!