理论计算机科学基础

Course Details

立即报名 4340 已报名

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

教师团队

课程助教

第一章：有穷自动机

第二章：正则语言

第三章：上下文无关文法

第四章：下推自动机

第五章：图灵机

第六章：（不）可计算性

第七章：计算复杂性

第八章： NP完全理论

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

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

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