UCL COMP0005《算法》：大一就要手写证明的算法课

UCL 计算机系 COMP0005《算法》是本科一年级 Term 2 的核心必修课：期末笔试占 80%、小组活动占 20%，重点是大 O 分析、正确性证明与图算法。

课程官网（学校官网）：https://www.ucl.ac.uk/module-catalogue/modules/algorithms-COMP0005

COMP0005 是一门什么课？

一句话：这门课不只教你怎么写算法，更教你怎么用数学说明它「跑得多快」和「为什么一定对」。

这是伦敦大学学院（University College London，UCL）工程科学学院计算机系的本科课程，课程代码 COMP0005，英文名 Algorithms，中文就是「算法」。

在计算机科学里，「算法」指解决某类问题的一套有限步骤的方法——就像菜谱，输入食材、按步骤操作、输出菜肴。这门课系统教授设计和分析这类「菜谱」的方法论。

学校官网给出的 Indicative content（示意内容）包括六块：Analysis of algorithms（算法分析）、Abstract Data Types（抽象数据类型）、Sorting Algorithms（排序算法）、Searching Algorithms（查找算法）、Graphs Algorithms（图算法）、String-processing Algorithms（字符串处理算法）。展开看，实际要学的是：

• 算法复杂度分析：用大 O 符号（Big-O notation，描述算法随输入规模增长时运行时间的上界）衡量时间效率和空间效率，区分最坏、最好、平均情况。
• 基础排序算法：插入排序、归并排序、快速排序、堆排序，重点理解各自的时间复杂度和适用场景。
• 基础数据结构：链表、栈、队列、二叉树、堆、哈希表——这些是组织和存储数据的方式。
• 图算法：广度优先搜索（BFS）、深度优先搜索（DFS）以及最短路径算法（如 Dijkstra's algorithm）；图在这里是「节点 + 边」的网络结构，不是统计图表。
• 算法设计范式：分治法（把大问题拆成小问题分别解决再合并）、贪心算法（每步取局部最优）、动态规划（存储子问题结果避免重复计算）的入门介绍。
• 算法正确性证明：用循环不变式（loop invariant）和数学归纳法说明一个算法为什么对所有输入都给出正确结果。

学校官网写明，本模块是本科一年级（FHEQ Level 4）模块，在第二学期（Term 2）授课，学分 15 credits，是计算机科学专业的核心基础课之一。

核心能力是「分析」而不是「记忆」：不只是会写排序代码，而是能推导出它的时间复杂度，并证明它是对的。算法分析使用的数学语言（渐进符号、递归关系式）是贯穿后续所有进阶课程的基础符号体系，学好它等于给后两三年打地基。图算法部分是本模块最实用的出口——网络路由、社交关系、地图导航背后都跑着类似的逻辑。

和国内数据结构与算法课有什么不同？

最大的差别是：国内课侧重「实现」，这门课侧重「分析与证明」；代码写得出来只是起点，讲清为什么对、为什么快才是核心。

• 国内「数据结构与算法」课（大多数院校大二开设）侧重数据结构的实现——写链表、写树的代码占较大比例；UCL COMP0005 侧重算法分析与正确性证明，代码实现退居其次，数学论证是核心考查内容。
• 国内课程通常不要求学生用形式化语言写算法正确性证明；UCL 从一年级就引入循环不变式和数学归纳法证明，学生需要具备用英文写出严格论证的能力。
• 教材选用上，UCL 同类模块常用 CLRS（《算法导论》，Cormen et al.）作为参考，该书证明密度极高，与国内普遍使用的教材（如严蔚敏版《数据结构》）风格差异很大，需要主动适应。
• 考核形式不同：国内通常是期末机考或笔试写代码；UCL 笔试要求在纸上写伪代码、推导复杂度并写出证明，「写算法 = 推理 + 证明 + 伪代码」的综合考法需要专门练习。
• 开课时间为一年级（国内通常大二）：UCL 将该模块放在入学第一年，意味着教学节奏设计上假设学生从零开始，但同时要求在一年内达到能做正式证明的水平，跨越速度比国内快。
• 总体而言，UCL 这门课的「理论深度」高于国内大多数同名课程，但「实现广度」（覆盖的数据结构种类、编程练习量）低于国内；擅长数学的学生反而可能比国内大学学得更顺。

考核怎么算？

期末笔试占 80%，Group activity（小组活动，2 次评估）占 20%；评分方式为 Numeric Marks（数字分）。

学校官网的 Methods of assessment 写的是：80% Exam；20% Group activity。Mark scheme 为 Numeric Marks。

具体拆开看：

• 期末笔试占 80%，考查算法分析推导、伪代码书写和证明；学校官网只给了权重，没有给考试时长与形式，闭卷与否属于经验推断，比例本身以 80% / 20% 为准。
• Group activity 占 20%，学校官网用词是 Group activity，不是 coursework（课程作业）；对应 2 次评估。
• 学校官网没有在考核表里给出更多细节；具体题型、考试安排以当学期课程信息为准。

这个结构意味着：笔试是绝对大头，而笔试考的是「推理 + 证明 + 伪代码」，不是背结论。小组活动占 20%，是分数缓冲，但不能指望它拉分；如果笔试的推导和证明没练熟，20% 的小组活动救不了 80%。

先修要求是什么？

学校官网没有列出具体先修课程编号，但明确了选课资格、编程基础和数学起点。

学校官网 Requisites 写的是：要能选这门模块，学生必须注册在「该模块正式开放」的 programme 与年级。Restrictions 进一步写明，本模块仅向以下专业的本科一年级（FHEQ Level 4）学生开放：

• BSc Computer Science；
• MEng Computer Science；
• MEng Mathematical Computation；
• BA Philosophy and Computer Science。

学校官网的 Additional note 还写：学生应具备 Python 基础编程经验；校方会在开课前提供自学资源和 Programming Tutor 支持。

从课程内容看，数学上高中级别的集合、函数、数列、简单归纳法足以起步；这门课不需要线性代数或概率论。真正的门槛不在「学过哪门课」，而在能不能接受「从做题到证明」的思维跳跃。

适合谁：CS 一年级核心必修生——这门课是后续几乎所有技术模块（操作系统、数据库、机器学习、系统设计）的工具箱；想打牢理论基础再做工程的学生；哲学与计算机科学方向的学生——算法的形式化证明与哲学逻辑训练有天然的思维相通之处；有意参加 ACM、LeetCode 竞赛或实习刷题的学生——这门课覆盖的算法类型和复杂度分析方法，是系统性入门竞赛编程的起点。不适合「只想学编程不想学数学」的学生：这门课的核心产出是推导和证明，不是代码量。

学完能做什么？

核心是五件事：估算算法代价、选对数据结构、读懂算法论文、手工模拟图算法、为后续课程打形式化基础。

具体包括：

• 能对任意算法估算时间/空间代价——在工作和面试中，能快速判断「这个方案在 n=10⁶ 时跑不跑得动」，而不是靠直觉猜；
• 能选对数据结构——知道什么场景用哈希表（O(1) 查找）、什么场景用堆（O(log n) 取最小值），而不是无脑用数组；
• 具备阅读算法论文的基础语言——大 O 符号、伪代码书写规范、正确性证明框架，是读研后阅读任何算法类论文的共同语言；
• 能手工模拟和调试图上的搜索/最短路过程——BFS/DFS/Dijkstra 是网络工程、游戏 AI、路径规划的底层逻辑；
• 为大三算法进阶课和系统类课程打下形式化基础——很多高年级模块直接沿用本模块的复杂度语言。

以上是基于课程内容与考核方式的梳理，帮你把「学完能做什么」落到具体场景。

难点与常见挂因

这门课难在「从做题到证明」的跳跃：概念入口不高，但要求你从第一天起就用形式化语言推理。

为什么中国学生容易在这里卡？

• 国内算法课偏实现，这里偏论证。 国内「数据结构与算法」课常以写链表、写树为主，考试考代码填空；UCL 一年级就要求用英文写出完整数学论证，语言和思路同时承压，审题失误率高。
• 竞赛背景两极分化。 参加过信息学奥赛的学生会觉得太简单；没有接触过算法竞赛、仅靠高考进入 CS 专业的学生，第一次接触大 O 分析和形式化证明时落差极大。两类学生的起点差距在开学头几周就会显现。
• 数学证明写作是陌生技能。 国内课程通常不要求形式化证明；这里要用循环不变式、数学归纳法写出严格论证，语言精确、逻辑严密，和「写代码跑一跑看对不对」的工程习惯完全不同。
• 英文专业词汇密度高。 amortized analysis（均摊分析，把多次操作的总代价平摊到每次操作上）、invariant（不变式）、recurrence（递归关系式）这些词在讲义里密集出现，不提前建立词汇表，听课时会反应滞后。
• 笔试是手写伪代码加现场证明。 国内习惯机考或选择题的学生，第一次面对「用笔写算法 + 当场证明」会很不适应；时间有限，思路一卡就写不完。

卡住之后会发生什么？

• 大 O 的严格定义没弄清，后面的复杂度推导会全部含糊；考试只写结论拿不到步骤分。
• 递归关系式不会解，分治、归并排序、主定理相关的题会连续失分。
• 循环不变式写不出来，证明题只能空着；而证明题是这门课的核心题型之一。
• 图算法不练手工模拟，考试时队列、优先队列的状态一乱，步骤分大量丢失。
• 前几周的概念一旦模糊，后面所有推导都会出错；拖到期末再补，时间根本不够建立推理速度。

具体难在哪：五处高频卡点

1. 渐进分析的抽象性。 大 O 符号描述的是「增长趋势」而不是精确运行时间，初学者常困惑「为什么 O(n²) 在 n=10 时比 O(n³) 慢」；需要大量习题建立直觉。
2. 递归思维的建立。 递归算法的正确性证明和复杂度分析（用主定理求解递归式）是一道认知门槛，不练透很容易停留在「看懂了但写不出来」。
3. 算法正确性证明。 循环不变式是一种形式化的数学论证，要求语言精确、逻辑严密；大多数学生需要专门训练，不能靠「代码跑通」代替。
4. 图算法的状态追踪。 手动模拟 BFS/DFS/Dijkstra 在较复杂图上的执行过程时，容易丢失节点状态；考试中若不建立清晰的追踪表格习惯，步骤分会大量丢失。
5. 数据结构与算法的配合。 为什么用堆实现优先队列能让 Dijkstra 跑得更快？这类「结构选择影响复杂度」的推理链条，学生往往在学完之后才能回头想通。

常见挂因与对应动作

• 只背结论不推导。 死记「快排平均 O(n log n)」，但不会从递归式导出；考试题要求写推导过程，只写结论得不到步骤分。怎么补：每学一个算法，强制自己用主定理或替换法推一遍，不看答案推到底。
• 跳过证明题只练代码。 认为「会实现就够了」，但笔试核心题型是「证明该算法在所有情况下正确」或「分析最坏情况复杂度」。怎么补：每周固定时间专门练写证明，从最简单的插入排序循环不变式开始。
• 图算法没练手工模拟。 BFS/Dijkstra 在考试中要求手工追踪每一步的队列/优先队列状态。怎么补：用纸笔在几个节点的小图上完整模拟几遍，直到机械化。
• 期末突击复习。 本模块考查的是能力（推理 + 证明），不是知识点背诵；考前两周才开始看讲义，时间根本不够建立推理速度。怎么补：从第一周就做每周的 problem set，保持训练节奏。
• 不去答疑，卡点不清。 前几周的概念一旦模糊，后续所有推导都会出错。怎么补：每周至少去一次 office hours，把不确定的地方当场问清。

留学生特别提醒

中国学生最容易在四处吃亏：证明写作、英文术语、笔试形式，以及「不好意思问」。

• 数学证明写作要专门练。 国内课通常不要求形式化证明；这里要用英文写循环不变式、归纳法论证，语言和逻辑同时练。建议从最简单的排序算法开始，每周写一段完整证明，请助教看逻辑是否严密。
• 英文术语提前建表。 amortized analysis、invariant、recurrence、pseudocode 这些词会密集出现；提前整理中英对照，听课和读题都会顺很多。
• 竞赛党别轻敌，零基础别慌。 参加过竞赛的同学，容易把「会写代码」当成「会证明」；零基础的同学，也不要因为别人快而乱节奏。这门课最后考的是论证能力，起点不同，练法可以不同。
• 手写伪代码和证明要模拟。 笔试要求在有限时间内写伪代码、推导复杂度并给出论证；平时练习就用纸笔限时写，别只在电脑上跑代码。
• 办公室答疑要主动去。 UCL 教授/助教有固定答疑时间，主动去问是被鼓励的；许多中国学生因为觉得「问太基础的问题丢脸」而放弃，导致小错误积累成知识漏洞。
• 别把小组活动当「水分」。 Group activity 占 20%，但它同样考表达和协作；把它当成「用英文讲清算法思路」的练习，对笔试也有帮助。

怎么准备？

准备的关键是三条：把大 O 和递归式练成直觉；把证明当日常写作练；把图算法的手工模拟练到机械化。

• 先补数学语言。 集合、函数、数列、简单归纳法过一遍；大 O 的严格定义和常见函数增长阶要能脱口而出。
• 每个算法自己推一遍。 排序、查找、图算法，学完就推复杂度；合上材料能写出推导，才算真的会。
• 证明从最简单的开始。 插入排序的循环不变式写熟，再练归并排序、快速排序；每周写一段完整英文证明。
• 图算法用纸笔模拟。 BFS/DFS/Dijkstra 在几个节点的小图上完整走几遍，画出队列表格，直到不丢状态。
• 用纸笔限时练。 笔试是手写伪代码加证明，平时就按考试形式练，别只在电脑上写代码。
• 每周做 problem set。 这门课考能力，不考背诵；保持每周训练节奏，比期末突击有用。
• 主动去 office hours。 带着具体问题去问，把「哪里不懂」讲清楚；小问题当周解决，别攒。
• 用 CLRS 当参考，不要硬啃。 教材证明密度高，先跟课程讲义搭框架，再用 CLRS 补细节；看不懂的证明可以先跳过，回头再看。

中英术语速查

• algorithm —— 算法：解决某类问题的一套有限步骤。
• complexity analysis —— 复杂度分析：衡量算法随输入规模增长的时间与空间代价。
• Big-O notation —— 大 O 符号：描述算法运行时间上界的方式。
• abstract data type (ADT) —— 抽象数据类型：只定义操作、不暴露实现的数据类型。
• sorting algorithms —— 排序算法：插入、归并、快速、堆排序等。
• searching algorithms —— 查找算法：在数据中找目标元素的方法。
• graph algorithms —— 图算法：在「节点 + 边」结构上做搜索与最短路径。
• BFS / DFS —— 广度优先搜索 / 深度优先搜索：两种图遍历方式。
• Dijkstra's algorithm —— 最短路径算法：求单源最短路径的经典方法。
• divide and conquer —— 分治法：把大问题拆成小问题分别解决再合并。
• greedy algorithm —— 贪心算法：每步取局部最优。
• dynamic programming —— 动态规划：存储子问题结果，避免重复计算。
• loop invariant —— 循环不变式：证明循环正确性的形式化工具。
• mathematical induction —— 数学归纳法：证明与自然数有关命题的方法。
• recurrence relation —— 递归关系式：描述递归算法代价的方程。
• Master Theorem —— 主定理：求解一类递归式的常用工具。
• amortized analysis —— 均摊分析：把多次操作的总代价平摊到每次操作。
• pseudocode —— 伪代码：用接近代码的方式描述算法步骤。

关于我们

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

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

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

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

课程官网与核对说明

课程官网（学校官网）：https://www.ucl.ac.uk/module-catalogue/modules/algorithms-COMP0005

本文涉及学校、课程代码、学分、课程内容、考核比例、选课资格与教学安排的事实，均来自上述学校官网课程页；核对时间为 2026-10-29。文中「与国内课程差异、先修判断、难点、适合谁、怎么准备、学完能力」等属于基于课程内容的分析与学习建议，不代表学校官方要求。

← 学业指南首页课程库