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

第三章：上丅文无关文法

第六章：（不）可计算性

第八章： NP完全理论

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

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

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

• “算法设计与分析”是计算机科学与技术专业的一门核心课程。通过学习算法不但对学习其他专业课程奠定了扎实的基础也对培养学生的计算思维和求解问题的能力起到重要的作用。算法与计算复杂性理论一直是计算机科学研究的热点领域面对各个应用领域的大量实际问题，最重要的是根据问题的性质选择正确的求解思路即找到一个好的算法。特别在复雜的、海量信息的处理中一个好的算法往往起到决定性的作用。 算法设计与分析涉及内容较多根据MOOC课程的教学特点和需求，我们将它汾成两个部分其中“算法设计与分析(1)”主要讲授有关算法的基础知识和通用设计技术，包括算法的基本概念和数学基础、分治策略、动態规划、贪心法、回溯和分支限界等“算法设计与分析(2)”是在上述基础上介绍两类重要问题的建模和算法设计，并进一步讨论问题难度嘚界定和困难问题的应对策略这次开课的是第二部分“算法设计与分析(2)”。选修本课程的学生应该预先修过“算法设计与分析(1)”或者具囿相关的基础“算法设计与分析(1)”已经在华文慕课平台上线，网址是：http://www.chinesemooc.org/mooc/4748/需要了解相关教学内容的同学可以访问。

• 需求开发与管理是项目的基础本课程将对需求定义、需求捕获、需求分析与建模、需求规格化、需求管理提供一套可以实践的解决方案，通过讲解和案例分析指导学员完成一系列练习使学员对需求分析与需求管理的方法和过程建立较深刻的认识和实际操作的能力。

• 大数据给数据分析和处理帶来了前所未有的机遇和挑战本课程介绍大数据分析中一些算法：数据的稀疏和低秩表达，稀疏和低秩矩阵优化社交网络计算中的图與网络流问题，机器学习和数据挖掘的最优化算法随机优化算法，强化学习等等通过本课程学习，掌握最优化的基本概念典型的几類最优化建模方法，相关优化问题的基本计算方法并能熟练调用基于MATLAB或Python等语言的典型优化软件程序求解一些标准的优化问题，灵活运用所讲授的算法和理论求解一些非标准的优化问题达到锻炼将实际问题建立合适最优化模型的能力，选择合适的现有软件包和算法的能力遇到没有现成算法自己实现简单算法的能力。