前 言 当学生时没学懂的地方，教这门课时学懂了；看书时忽略的细节，备课时注意到了；备课时自信能讲好一个定理的证明，上课时挂板了；上课时高调阐述一个得意的观点，回答学生提问时心虚了。十年后，当准备为这门课写自己的教材时，终于知道，关于这门课，知道得太少了。为写教材，花了一年多时间查阅文献，才发现，有个别地方，过去十年一直在误导学生。 解惑之道，是一条往返于细节与真理之间的路。这条路，教师多走几遍，学生就多获益几许。要做到在讲堂上从心所欲，教师须经历读书、教书、写书的全过程。编写本书，有几层考虑。其一，我非常想进一步提高“计算复杂性理论”这门课的课堂教学水平。2020 年秋季学期，当第十几次给高年级本科生和研究生讲授这门课时，我已没了以往的激情，这不是个好兆头。为求改变，我边讲课，边把课上所讲内容写下来。2021 年春季学期，我讲授“计算复杂性理论高等议题”这门课。我对这部分内容远不如我对秋季学期讲的那部分内容熟悉，我还是认真做了讲课笔记。之后的一年，我对这些笔记改头换面，补充了所有课上没讲的证明，增加了不少这门课以前没有涉及的内容，在结构上做了变动，直至最后，对这本书的定位也做了些许调整。在本书完稿之前，我已确信我能把这门课讲授得更好。考虑之二，中国的计算机专业教育急需一本系统介绍计算复杂性理论的中文教材。中国的计算机专业教育是全球最大的专业教育，如果它的学生还要为教材发愁，如果它的学生使用的大多数教材都是国外学者撰写的，我们有什么理由说我们的计算机专业教育是好的。出版社的编辑告诉我，百分之九十五以上的中国学生更愿意使用中文教材。我认为他们有绝对的权利要求好的中文教材，任何一本能解决中国计算机专业教育燃眉之急的教材都值得马上写。考虑之三，教育部高等学校计算机类专业教学指导委员会于2019 年5 月启动了“计算机专业教育丛书”系列，作为该丛书的编委会主任，我有幸与国内计算机专业领域的一些著名学者探讨过撰写中文专业教材的问题，他们中的一些接受了我的邀请，加入了撰写本丛书教材的队伍。受他们的鼓舞，我决定也写一本教材。我觉得，如果我不这样做的话，一定会被认为有点虚伪。曾经犹豫，因为国内有一批教授能写一本比这本更好的计算复杂性理论教材；不再犹豫，因为有一本将被超越的教材总比没有好。当然，还有一些其他考虑。在高校教书近三十年，能有一本自己的教材，既多了一份对所选择的终身职业的敬意，也多了一个与同行交流的话题。 本书的主要读者群是高年级本科生、硕士生、博士生，以及希望了解（更多）计算复杂性理论的教师和科技工作者。我希望这本书包含足够多的细节，学生在积极参与了课堂学习之后能通过阅读本书的相关章节完全理解有关的定义、定理、证明。我希望这本书自圆其说，读者无须参考任何其他资料就可理解本书的全部内容。这些努力是否成功得由读者裁定。 本书可作为以下课程的主参考书： （1） 面向高年级本科生、研究生的“计算复杂性理论导论”课程，内容涵盖前3章，可略去第1.6节（但要讲线性加速定理）、第1.20节、第2.10节、第3.6节。若对前3 章内容做了较大删减，第4章的前几节内容也可被涵盖。 （2） 面向研究生的“计算复杂性理论高等议题”课程，内容涵盖第4章（“计算复杂性理论导论”课程讲过的除外）、第5章、第6章。 （3） 面向高年级本科生、研究生的“算法理论”课程，涵盖第4章、第6章中有关随机算法和去随机、近似算法和不可近似性的内容。 （4） 面向高年级本科生、研究生的“计算理论”课程，以第1章的内容为核心，并根据学分多少和授课对象不同做适当补充。 作者在上海交通大学讲授“计算复杂性理论导论”和“计算复杂性理论高等议题”课程多年，也在其他学校讲授过“计算复杂性理论导论”课程。感谢选修这些课的学生，他们的问题总会让我去探究计算复杂性理论的更多细节。特别感谢所有的助教，他们为提高这两门课的教学质量做出了贡献。这两门课的所有电子演示文稿可供读者随意使用，无须征得作者同意。 我希望本书能让读者收获人类智慧，我也期待着收获读者的批评和建议。 傅育熙 二零二三年二月八日 上海交通大学徐汇校区

• 暂无课件
• 样章下载
• 暂无网络资源

扫描二维码
下载APP了解更多

版权图片链接