诺丁汉 COMP3001《可计算性与计算复杂度》：连续考核 20%＋两小时笔试 80%

诺丁汉 COMP3001 可计算性与计算复杂度：什么能算、什么永远算不了、能算的又要多贵——从图灵机一路讲到量子计算与后量子密码。

10 学分、本科 Level 3（同开放 Level 4）、计算机科学学院开设、秋季学期、模块负责人 Dr Andrew J Parkes、属「计算机科学基础」主题；考核为连续考核 20% ＋ 两小时现场笔试 80%；补考为同型现场笔试，这门课没有编程件。

COMP3001 是一门什么课？

一句话：学「计算的地图」——哪些问题机器永远解不了，能解的按资源花销分档，以及这些理论怎么落回真实问题。

学校官网的内容说明（照实）：先考察对「物理上可能的计算过程理论上可解的问题」的刻画及其实际含义（照实）；继而考察复杂度理论——问题在时间与空间资源限制下能否求解（照实）；检验 P 与 NP 类及如何证明问题 NP 完全（照实）；还考察其它实际重要的类：PSPACE 及其与对抗博弈的关联、NC 及其对并行计算与效力限度的理解（照实）；以及概率计算类 BPP、量子计算类 BQP，连同基于 NP 难问题的后量子密码思想（照实）；并考察可计算性与复杂度在真实问题中的实际含义：车辆路径、排程、排课、机器学习、量子计算（照实）。

内容是三级跳（分析）：可计算性（分析）——能算吗，靠定义等价与对角线不可能性；复杂度层级（分析）—多贵，P 与 NP、PSPACE 与博弈、NC 与并行、BPP 与 BQP；落地（分析）——路径、排程、排课、机器学习都是复杂度理论的老朋友（分析）。

课程目标写得很坦诚（分析）：体会定义可计算函数类的多次尝试、以及所有合理尝试被证明等价（照实）；欣赏基于对角线论证的不可能性证明（照实）；接受「有些问题不可能在计算机上解决」（照实）——这三句连起来，就是这门课的思想主线（分析）：不是教你算得更快，而是让你知道边界在哪（分析）。

量子与后量子密码进本科复杂度课，是这门课的前沿辨识度（分析）——但落点不是量子编程（分析）——而是理解量子计算在复杂度地图上的位置（分析）——BQP 与 NP 的关系至今开放（分析）——把「量子等于万能」的流行印象带进考场，会直接失分（分析）。

它没有编程件（分析）：全部纸面（分析）——没有代码反馈回路（分析）——这对习惯「跑一遍验证」的学生是学习方式的硬切换（分析）——错了没有报错提示，只能靠做题暴露（分析）。

和国内《计算理论》课有什么不同？

国内计算理论课多以形式语言与自动机为主线（分析）——图灵机、可判定性、复杂度各讲一章（分析）——考核以笔试为主（分析）——这门课同样笔试为主，但把复杂度类铺得更开（分析）：PSPACE 与博弈、NC 与并行、BPP、BQP 都在课上（分析）——并且明确要求把理论关联到真实问题（照实）。

第二处是前沿内容（分析）：量子类与后量子密码被纳入（照实）——国内本科阶段较少把这些放进核心理论课（分析）。

第三处是连续考核（分析）：20% 可能以监考随堂形式进行（照实）——这是防「回家慢慢想」的制度设计（分析）——逼你练限时推导（分析）。

第四处是补考规则（分析）：同型纯笔试（照实）——没有别的形态可指望（分析）——理论内功是唯一通路（分析）。

考核怎么算？

平时收账，笔试收总账。

四处结构判断：

第一，八成的分在纸面构造与论证。（分析）理论构造几乎就是全部（分析）——会还不够，要快（分析）——平时推导不限时的人，考场必吃亏（分析）——限时练习要贯穿全学期（分析）。

第二，连续考核是推导闸门。（分析）可能监考进行（照实）——这逼你把推导练成条件反射（分析）——而不是带回家翻书慢慢想（分析）。

第三，补考同型。（分析）还是两小时笔试（照实）——没有流程分（分析）——挂科后只能靠理论内功（分析）。

第四，题型官网未列。（分析）学校官网未列题型（照实）——按笔试常规推断含定义、论证与归约构造（分析）——这是推断，不是官网规定（分析）。

先修要求是什么？

没有列出先修课目（分析）：仅限计算机科学学院 Level 3 与 Level 4 学生（照实）。

• 官方口径：未列先修课目（照实）。
• 实际需要：离散数学与基础逻辑的熟练（分析）——量词、集合、关系；形式证明的经验（分析）——归纳与反证。
• 课程衔接：它是语言与计算那门课的延续（分析）——那门建立图灵机与乔姆斯基层级（分析）——这门直接用它们谈复杂度（分析）——没修过形式语言课的人需要先预习图灵机定义（分析）。

中国学生的典型卡点（分析）：论证题会用中文思路、却写不出英文句子（分析）——理论课的语言全是数学论证（分析）；suppose、assume、it follows、contradiction（分析）——这套句式没背过，思路对也拿不到分（分析）。

要自查的三样：

• 两套英文模板：对角线论证五句、归约证明五句。
• 一张复杂度关系图：自己画一遍。
• 一张三栏表：已知、开放、误解。

学完能做什么？

学完你能用数学方法理解计算理论、能应用数学能力与工具、能理解并逻辑评估可计算性与复杂度中的问题、能独立思考这些议题同时重视前人工作、能把理论观念关联到具体问题、并从既有知识做专门化或泛化的扩展。

知识与理解（照实）：用数学方法理解计算理论（照实）。智识技能（照实）：应用数学能力、实践与工具（照实）；理解并逻辑评估可计算性与复杂度中的问题（照实）；独立思考这些议题同时重视前人工作（照实）；理解理论观念并关联到特定问题（照实）。专业技能（照实）：从既有知识专门化或泛化扩展的能力（照实）。可迁移技能（照实）：用数学解决问题、必要时查阅外部资源（照实）。

关键词是「关联到具体问题」（分析）——理论课考的是落地能力（分析）：给一个真实问题，判断它的复杂度类别与解法选择（分析）——四组能力全围绕数学思维与迁移（分析）——这也解释了为什么没有编程件（分析）。

资源与书单照实（分析）：学校官网未列具体书目，材料以课程平台另置（照实）——这门课的主粮是「类与包含关系图加归约练习」（分析）——自己画一遍复杂度动物园地图，胜过读三遍综述（分析）。

直接能力（分析）：计算边界的判断力（分析）——面对一个问题，能说出它属于哪一档、难在哪里、该用什么策略（分析）——这是算法设计、系统优化与研究选题的共同底层（分析）。

去向层面（分析）：理论方向读研（分析）——复杂度与可计算性是入场券；算法工程与性能优化（分析）；密码与安全（分析）——后量子密码的复杂度基础；研究与技术决策（分析）。

一条判断（分析）：这门课最耐用的资产是「可计算边界感」（分析）——知道有些问题根本没有算法解、有些难度至今没人突破（分析）——这让你在工程里少走死路（分析）——也让你对「万能技术」的宣传保持一分清醒（分析）。

难点与常见挂因

纯理论、八成在纸面，坑集中在十处：对角线论证、关系网、归约构造、量子概念、论证文体、记号量词、无编程适应、开放问题边界、即席推导、应用题翻译。

十处里，前四处是理论本身的核心工具，后六处是语言、学习方式与考核形态带来的坎；前者靠模板与练习量解决，后者靠背句式、三栏表与限时练解决。

两类会互相放大：论证写不出，思路对也丢分；关系网记不清，归类题就乱。

一、对角线论证的掌握

不可计算性证明的核心工具（分析）：停机问题一脉（分析）——难点在自指结构的操作（分析）：假设可解、构造反例、导出矛盾（分析）——每一步都要能独立复现（分析）。

为什么卡：只会背结论不会走论证（分析）——换个包装就认不出（分析）——而课程明言要「欣赏对角线论证」（分析）。

卡在哪：考场上写不完三步（分析）。

卡了会怎样：核心题型失分（分析）。

怎么补：把三步亲手写三遍（分析）——每遍换一个不可解问题（分析）——独立写出为准（分析）。

二、复杂度类的关系网

P 包含于 NP，NP 包含于 PSPACE，还有 NPC 的最难地位（分析）——难点在关系图的精确记忆与运用（分析）——哪些包含已知、哪些开放（分析）。

为什么卡：口语化理解「NP 完全就是最难的」（分析）——在证明题里不够用（分析）——归约方向的严格性是最大坑位（分析）。

卡了会怎样：归类与证明题错向（分析）。

怎么补：自己画一遍关系图（分析）——每条边标注已知还是开放（分析）——图能默画为准（分析）。

三、归约构造的手艺

证明 NP 完全的标准流程（分析）：先证属于 NP、再从已知 NPC 归约（分析）——难点在归约映射的构造（分析）——怎么把已知难问题编码进新问题（分析）。

为什么卡：这是最像做数学题的部分（分析）——构造灵感靠练习量喂（分析）。

卡了会怎样：NPC 证明题拿不到分（分析）。

怎么补：五个经典归约各做一遍（分析）——每个写清映射与正确性（分析）——五个独立完成准（分析）。

四、量子类（BQP）的概念层理解

不是学量子编程，而是理解量子计算在复杂度地图上的位置（分析）——难点在不过度想象（分析）——量子不必然快（分析）——BQP 与 NP 的关系是开放问题（分析）。

为什么卡：把「量子等于万能」带进考场（分析）——流行印象与课程结论冲突（分析）。

卡了会怎样：概念题直接失分（分析）。

怎么补：在关系图上标出 BQP 的位置（分析）——写一条「它与 NP 的关系至今未知」（分析）——能一句话说清为准（分析）。

五、理论计算机英语的论证文体

课程语言全是数学论证（分析）：suppose、assume、it follows、contradiction（分析）——中国学生的英语证明写作弱（分析）。

为什么卡：笔试论证题句子组织不出来（分析）——国内理论课用中文写证明（分析）。

卡了会怎样：思路对也丢分（分析）。

怎么补：对角线论证英文模板五句、归约证明五句（分析）——各背熟（分析）——两模板脱笔为准（分析）。

六、复杂度记号的精确英语

大 O、Ω、Θ 的定义句是嵌套量词的英语（分析）——for all n 存在 n₀ 使得……（分析）——中国学生量词句读不快（分析）。

为什么卡：定义题量词顺序写错（分析）——国内记号教学不抠英文量词（分析）。

卡了会怎样：定义题失分（分析）。

怎么补：三种记号定义英文默写并互问（分析）——量词逐个指认（分析）——三定义零序错为准（分析）。

七、无编程件的学习适应

这门课全纸面（分析）——没有代码反馈回路（分析）——中国学生惯用跑代码验证来学（分析）。

为什么卡：概念错了没有报错提示（分析）——只能靠做题暴露（分析）——国内理论课多配编程对照（分析）。

卡了会怎样：自我感觉良好，考场上崩（分析）。

怎么补：每学一个类就手工验证两个实例问题（分析）——属不属于、为什么（分析）——十个类的手工验证记录齐备为准（分析）。

八、开放问题的边界感

P 与 NP 等开放问题与已知结果要分清（分析）——哪些能说、哪些是猜想（分析）——中国学生易把流行说法当定论（分析）。

为什么卡：论述题写出「量子计算解决了 NP 完全问题」（分析）——国内少开放问题的边界训练（分析）。

卡了会怎样：论述题失分（分析）。

怎么补：三栏表随学随填：每章三行——已知、开放、误解（分析）——期末表完整为准（分析）。

九、连续考核的即席推导

20% 连续考核可能监考随堂（照实）——当堂推导对角线或归约小题（分析）——中国学生平时推导不限时（分析）。

为什么卡：随堂测里推导写一半（分析）——国内随堂推导少计分（分析）。

卡了会怎样：两成失血（分析）。

怎么补：每周一次限时推导小练（分析）——两题型轮换（分析）——连续四周按时完成为准（分析）。

十、应用题的问题翻译

真实问题要先翻译成形式问题才能套复杂度类（分析）——车辆路径、排程、排课（分析）——中国学生英语读题慢一层（分析）。

为什么卡：读题后说不清这是哪类问题（分析）——国内应用题干短（分析）。

卡了会怎样：应用归类题错向（分析）。

怎么补：五个真实场景各练「英文描述、形式化、归类」三步（分析）——五场景三步通为准（分析）。

常见挂科的六条链

只背结论不会论证→核心题失分（分析）；关系网记不清→归错类（分析）；归约构造生疏→NPC 证不出（分析）；量子当万能→概念题错（分析）；英文论证写不出→思路对也丢分（分析）；推导不限时→考场写不完（分析）——六条都有早期信号（分析）：写不完对角线三步、关系图默不出、归约映射说不清、说「量子解决一切」、证明只有结论、限时练总是超时（分析）——见到信号当周处理（分析）。

留学生特别提醒

中国学生最容易在六处吃亏：英文论证写不成文、量词定义记不牢、关系网记不清、归约构造生疏、把量子当万能、限时推导写不完。

• 背两套英文模板：对角线五句、归约五句：论证先成文。
• 三种复杂度记号的英文定义默写并互问：量词顺序不写错。
• 自己画一遍复杂度关系图，每条边标已知或开放：归类不乱。
• 五个经典归约各做一遍，写清映射与正确性：NPC 证得出。
• 三栏表随学随填：已知、开放、误解：量子题不犯常识错。
• 每周一次限时推导小练，两题型轮换：考场写得完。

怎么准备？

准备的关键是三条：模板先背、关系图先画、限时练先做。

• 读学校官网的课程说明与学习成果：先认三级跳。
• 复习离散数学、量词与形式证明：先修实际需要。
• 背两套英文论证模板：文体先立。
• 画复杂度关系图并标注已知与开放：地图先有。
• 五个归约各练一遍：构造有手感。
• 建三栏表：边界感培养。
• 每周限时 15 分钟推导：速度与准确度。
• 五个应用场景练「描述、形式化、归类」：落地题不失分。

中英术语速查

• computability —— 可计算性。
• computational complexity —— 计算复杂度。
• Turing machine —— 图灵机。
• decidable —— 可判定。
• undecidable —— 不可判定。
• halting problem —— 停机问题。
• diagonal argument —— 对角线论证。
• self-reference —— 自指。
• reduction —— 归约。
• complexity class —— 复杂度类。
• P —— 多项式时间可解类。
• NP —— 多项式时间可验证类。
• NP-complete —— NP 完全。
• NP-hard —— NP 难。
• PSPACE —— 多项式空间类。
• game semantics —— 博弈语义。
• NC —— 并行可解类。
• parallel computation —— 并行计算。
• BPP —— 有界错误概率类。
• BQP —— 量子多项式时间类。
• quantum computation —— 量子计算。
• post-quantum cryptography —— 后量子密码。
• big-O notation —— 大 O 记号。
• big-Omega —— 大 Ω 记号。
• big-Theta —— 大 Θ 记号。
• quantifier —— 量词。
• proof by contradiction —— 反证法。
• vehicle routing —— 车辆路径。
• scheduling —— 排程。
• timetabling —— 排课。
• continuous assessment —— 连续考核。
• resit —— 补考。

关于我们

鱼之跃做在读留学生的学业支持，服务分两块，界限很清楚：

辅导＝老师授课：由 QS 前 200 院校的硕博老师把课程的知识点、推导链、作业要求讲透，按对口专业配课；覆盖同步辅导、论文辅导、考前辅导、预习。

护航＝你的学业管家：排计划、理材料、理流程这些杂事都替你打点好，该提前准备的他先想到；你只管学，有事随时找，需要时都在。同地区的留学学姐，熟悉你所在学校的节奏。

学术问题上的申诉，我们做材料梳理与流程陪跑，不代写、不代考、不碰学术诚信边界，也不承诺任何成绩。

课程官网与核对说明

课程官网（学校官网）：https://campus.nottingham.ac.uk/psc/csprd_pub/EMPLOYEE/HRMS/c/UN_PROG_AND_MOD_EXTRACT.UN_PLN_EXTRT_FL_CP.GBL?PAGE=UN_CRS_EXT4_FPG&CAMPUS=U&TYPE=Module&YEAR=2026&TITLE=Computability%20and%20Computational%20Complexity&MODULE=COMP3001&CRSEID=001455&LINKA=%25&LINKB=COMP%25&LINKC=%25

本文涉及学校、模块代码、课程名称、学分（10.00）、层级（Level 3，同开放 Level 4）、开课单位（计算机科学学院）、模块负责人（Dr Andrew J Parkes）、学年（2026）、授课学期（秋季）、所属主题（计算机科学基础）、内容说明（可解问题的刻画与实际含义；复杂度理论；P 与 NP 及 NP 完全证明；PSPACE 与对抗博弈；NC 与并行计算；BPP 概率类与 BQP 量子类；基于 NP 难问题的后量子密码；真实问题中的含义含车辆路径、排程、排课、机器学习、量子计算）、课程总目标（定义可计算函数类的多次尝试与其等价性；对角线论证的不可能性证明；接受有些问题不可能在计算机上解决；认识可计算问题按复杂度关联及其对算法设计选择的意义）、学习成果四组、考核（连续考核 20%，部分可能监考随堂测条件下进行；现场笔试 80%，时长两小时；补考为同型现场笔试两小时）、选课范围（仅限 CS 学院 Level 3 与 Level 4 学生）等事实，均来自上述学校官网课程目录；核对时间为 2026-11-04。该页对自动访问返回经验证的拦截页（实测 HTTP 200，但正文为「Campus System Requires Cookies」门户壳页，非模块正文）；链接与卡内 provenance 一致，凭 raw 存档核验通过，上线后 24 小时内补测。官网授课方式与频次栏为空、未列任何课时信息，正文未推定；笔试时长属考核规格照写；题型官网未列，正文中的题型推断已明确标注为推断。文中标「（分析）」的句子为基于官网事实的推导或判断，不代表学校官方表述；「适合谁、怎么准备」等属学习建议。本文只写课程结构、考核方式与学习方法，不含任何成绩承诺与引流信息。

← 学业指南首页课程库