《计算复杂性理论》课程教学大纲（硕士研究生）

PAGEPAGE2广州大学研究生课程教学大纲课程名称中文计算复杂性理论课程编号0006200121英文ComputationalComplexityTheory开课单位计算机科学与网络工程学院考核方式考查学时16学分1课程类别专业课编制者陈建二适用对象学术型硕士、专业型硕士课程简介(中文)：计算复杂性理论是计算机科学与技术一门重要的专业课。本课程是算法分析、自动机理论和可计算理论的基础上进一步研究计算模型、算法技术和计算复杂性理论。通过对本课程的学习使学生从理论高度理解计算模型、算法技术和计算复杂性理论的重要意义，掌握其相关理论，了解其前沿研究的现状和发展趋势。提高学生计算机理论水平，培养学生应用理论解决实际问题的能力。课程简介(英文)：Computationalcomplexitytheoryisoffundamentalimportanceincomputerscienceandtechnology.Thiscourseisafurtherstudyofcomputingtheoryafterstudentsgainbasicknowledgeofalgorithmanalysis,automatatheory,andcomputabilitytheory.Thecoursediscussescomputationalmodels,algorithmictechniques,andcomputationalcomplexity.Thecoursewillenhancestudents’theoreticalbackground,whichwillhelptheytoapplytheorytosolveproblemsintherealworld.课程目标与基本要求：课程目标：通过对计算复杂性理论的系统学习与研究，培养学生分析问题和解决问题的能力，理解和掌握计算模型、算法技术和计算复杂性的主要理论和方法，提高学生计算机理论水平，培养学生应用理论解决实际问题的能力，为进一步研究计算机科学领域的前沿课题打好坚实的理论基础。基本要求：1.掌握和熟悉各种不同的计算模型：确定计算和非确定计算，并行计算，概率计算。2.掌握NP-完全理论的技术、理论和应用。3.学习并掌握计算问题的时间复杂性、空间复杂性分析技术和理论。4.了解计算复杂性理论的研究前沿。课程内容及学时分配：引论（1学时）课程的学习内容及其意义，了解计算复杂性理论在计算机科学中的重要性。NP-完全理论（8学时）判定问题，确定计算机和非确定计算机，多项式时间规约，NP完全理论及其应用。图灵机模型（2学时）图灵机，基于图灵机的时间复杂性和空间复杂性。概率计算机模型和并行计算机模型（5学时）概率计算机和并行计算机，及其相关的复杂性理论，与传统计算机模型的关系。教材及主要参考书目：教材：1.1ComputationalComplexity:AModernApproach,S.AroraandB.Barak,CambridgeUniversityPress,NewYork,20091.2ComputersandIntractability:AGuidetotheTheoryofNP-Completeness，M.GareyandD.Johnson,W.H.FreemanandCompany,NewYork,1979.预修课程：离散数学、算法分析。教师团队成员：陈建二，王捍贫，陈文彬编制者签名：学科点意见：学科点负责人签名：年月日注：1、课程类别指公共课、专业课。2、适用对象指学术型硕士、专业型硕士、在职专业型硕士、博士等。3、课程内容要强调理论性与应用