Joey

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

---

Part 1: Tutorial 4 详细题解

Tutorial 开头的难度/要求说明

Tutorial 4 开头说明了本周每题的投入要求，并解释了星号含义：标记 的题在所属级别内偏难；标记 的题非常难或很耗时。

题目	所属部分	Tutorial 原文难度/要求	复习时怎么安排
Problem 1	Warm-up	lecture 前也应该可以尝试并解决	必做，用来确认随机 bit 数量和 sample space 大小的关系
Problem 2	Warm-up	lecture 前也应该可以尝试并解决	必做，理解 pairwise independence 不等于 mutual independence
Problem 3	Warm-up	应该 doable，但最好等 lecture 后做；否则至少先看 lecture notes	必做，强通用哈希推出通用哈希是定义题
Problem 4	Problem Solving	标记 ，属于同级别偏难	练概率方法 + amplification，建议认真做
Problem 5	Problem Solving	标记 ，quite hard；不要求必须解出，但建议快速看 solution 理解论证主线	难题，有时间再细做；至少看懂构造思路
Problem 6	Problem Solving	未特别标难，属于正常 problem-solving 题	建议做，练随机定向和线性期望
Problem 7	Problem Solving	标记 ；“fun” but optional，用来展示 lecture 末尾的 Probabilistic Method	选做，适合加深概率方法直觉
Problem 8	Advanced	和 Problem 5 类似 quite hard；不要求必须解出，但建议快速看 solution 理解论证主线	高级难题，重点理解 universal 与 strongly universal 的差别

Warm-up

Problem 1: 需要多少随机 bit?

Tutorial 难度/要求: Warm-up；lecture 前也应该可以尝试并解决。重点是把“均匀生成 个可能结果之一”转成需要覆盖 sample space 的 bit 数。

题目: 生成 中的均匀随机整数,需要多少独立随机 bit?生成均匀随机子集 呢?

系统提示词大规模泄露事件引发 AI 安全与透明度讨论，自进化 Agent 框架持续火爆，SEC 重拳出击 AI 驱动的加密骗局。

本日焦点：① 系统提示词大规模泄露 —— 开发者提取并公开了 Anthropic、OpenAI、Google Gemini、xAI Grok 等顶级模型的内部系统提示词；② 自进化 Agent 框架持续火爆 —— GenericAgent 以 92 星/天的增速引领 GitHub Trending，EvoMap/evolver 和 Cherry Studio 紧随其后；③ AI 医疗突破 —— OpenAI 与波士顿儿童医院合作利用 AI 解锁全新诊断方法；④ SEC 重拳出击加密骗局 —— 起诉涉嫌利用虚假 AI 交易机器人的 1230 万美元骗局；⑤ Hugging Face Transformers 和 TensorFlow 两大 ML 框架稳居 Trending 前列。