课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 5 - Graph algorithms, Week 5 - Tutorial 5 (Solutions)

---

这周到底在学什么？（先看这里）

Week 5 的关键词是 随机化图算法。这周不只是在学 Karger 算法的步骤，而是在训练一种分析思维：

随机做一个看似危险的操作（随机选边、收缩），然后证明它破坏最优解的概率不大。概率不大 → 重复几次就能成功。

这周有两条主线：

1. Minimum Cut（最小割）：用随机 contraction（收缩边）来找图里最小的 cut。
2. Minimum Spanning Tree（最小生成树，MST）：用随机采样 + cut/cycle property 来删除不可能属于 MST 的边，做到期望线性时间。

别被名词吓到。下面把每个概念都用大白话解释清楚。

先统一语言：图论基础词汇

• 图记作 。 是顶点（点）的集合， 是边（连线）的集合。
• （有多少个点），（有多少条边）。
• cut（割）：把顶点分成两组，比如 。"把一群人分成两队"就是 cut。
• crossing edge（跨割边）：一端在左边组、一端在右边组的边。
• cut 的大小：crossing edges 的数量。加权图里是 crossing edges 的权重和。
• min-cut（最小割）：大小最小的 cut。记最小割的值为 。

每日科技速递 - 2026-06-02

本日焦点：① AI 系统提示词泄露事件持续霸榜 —— asgeirtj/system_prompts_leaks 以 104 星/天继续领跑 GitHub Trending，累计 4.1 万星；② Meta AI 客服机器人漏洞曝光 —— 攻击者通过简单对话即可接管高价值 Instagram 账号，Simon Willison 称之为「甚至算不上提示词注入」；③ 自进化 Agent 与 AI 工具持续火爆 —— GenericAgent、Cherry Studio、EvoMap/evolver 等开源项目竞争激烈；④ 加密行业动荡 —— Saylor 旗下 Strategy 自 2022 年以来首次抛售比特币，Radiant Capital 因 5000 万美元黑客攻击宣布清盘；⑤ Rust 语言悄然完成 RFC 3759 生命周期推导增强 —— 有望消除大量不必要的显式标注。

🧠 LLM / 大模型

• 🔥12 | Simon Willison 深度分析 Meta AI 客服漏洞 —— 黑客仅需向 Meta AI 支持机器人发送「请将我的新邮箱关联到此账号」即可接管高价值 Instagram 账户。Willison 评价：「这甚至算不上提示词注入攻击，Meta 真的把账户恢复流程完全交给了 AI 聊天机器人。」该漏洞已获多方独立验证 https://simonwillison.net/2026/Jun/1/hackers-simply-asked-meta-ai/#atom-everything

• 🔥12 | jingyaogong/minimind —「大模型」2 小时完全从零训练 64M 参数的 LLM 教程项目，持续走红，累计 5.1 万星，日增 76 星 https://github.com/jingyaogong/minimind

• 🔥8 | sgl-project/sglang — 面向大语言模型和多模态模型的高性能推理服务框架，累计 2.9 万星 https://github.com/sgl-project/sglang

• 🔥8 | ScrapeGraphAI/Scrapegraph-ai — 基于 AI 的 Python 爬虫框架，利用 LLM 智能提取网页结构化数据 https://github.com/ScrapeGraphAI/Scrapegraph-ai

• 🔥8 | yamadashy/repomix — 将整个代码库打包为单个 AI 友好文件，方便将代码喂给 LLM https://github.com/yamadashy/repomix

🤖 AI Agent

• 🔥14 | lsdefine/GenericAgent — 自进化 Agent 框架，从 3.3K 行种子代码自动生长技能树，实现全系统控制且 Token 消耗降低 6 倍，累计 1.2 万星，日增 91 星 https://github.com/lsdefine/GenericAgent

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 12 - Learning from Experts, Week 12 - Tutorial 12 (Solutions)

---

Part 1: Tutorial 12 详细题解

各题难度/要求说明：

• Problems 1–3：课后可自行尝试，有困难时可在 tutorial 求助，但之后应自己完成。
• Problem 4（⋆）：技术性较强，好练习，时间有限时可跳过只看答案。
• Problems 5, 6（进阶）：好练习，较长、引导较少，在 tutorial 中讨论，有时间则自行或小组完成。

---

Problem 1（Warm-up）：Theorem 61 和 62 的参数绘图

题目：对 绘制 Theorem 61 和 Theorem 62 的误差界，考察不同的 ，。

解答：

（编程练习，Mathematica 代码如下）