# 决策树 1234567891. SELECT DISTINCT store_id FROM Tx WHERE month = 5;2. SELECT DISTINCT c.name FROM Tx t JOIN Tx_Cakes tc ON t.tx_id = tc.tx_idJOIN Cake c ON tc.cake_id = c.cake_id WHERE t.month = 5;3. SELECT t.month,SUM(t.value) AS total_value,AVG(t.value) AS avg_value,COUNT(tc.cake_id) AS...

# Voronoi 图复杂度的欧拉公式证明 我们希望证明:对于 n>2n > 2n>2 个点的 Voronoi 图 V(P)V(P)V(P),其复杂度是线性的: 顶点数 ≤2n−5\leq 2n - 5≤2n−5 边数 ≤3n−6\leq 3n - 6≤3n−6 # 📐 使用欧拉公式 欧拉公式是平面图中的基本定理: V−E+F=2V - E + F = 2 V−E+F=2 其中: VVV 是顶点数 EEE 是边数 FFF 是面数(Voronoi cell 数量,即原始点数 nnn) # 🔧 添加虚拟点使图封闭 由于...

# Voronoi Diagram 基础讲解 # 什么是 Voronoi Diagram? 给定一个点集 P={p1,p2,…,pn}P = \{p_1, p_2, \dots, p_n\}P={p1​,p2​,…,pn​},Voronoi 图是将平面划分为 nnn 个区域(称为 Voronoi Cells),每个区域对应一个点 pip_ipi​,使得该区域中任意一点 qqq 满足: dist(q,pi)<dist(q,pj)∀j≠i\text{dist}(q, p_i) < \text{dist}(q, p_j)...

# Lecture 9: Streaming and Sketching II - 内容总结 # Part1 引入流式算法以及解决方案 # 🧩 课程引入:流式算法的挑战 数据以流的形式连续到达,不能全部存储。 算法 A 读取前一部分数据后输出结果 21.5 。 结果还没来得及用,更多的数据又到达了。 再运行 A 得到新的结果 18.1 。 关键问题: 如何把两个结果合并成一个整体答案? # 🧠 引入 Sketching 的概念 对每段数据 σ ,算法 A 生成一个摘要: S(σ) ,称为 sketch。 特性: S(σ) 是对数据的压缩表示; 可以从 S(σ)...

# 一、机器学习及分类 # 1.1🔍 机器学习任务分类(Machine Learning Problems) Prediction(预测) 包括分类(Classification)和回归(Regression), 是一种有监督学习 ✅ 例子: 分类问题(Classification): 判断一封邮件是不是垃圾邮件(标签:垃圾 vs 正常) 预测一个肿瘤是良性还是恶性(标签:良性 / 恶性) 回归问题(Regression): 根据房屋面积、地段等预测房价(标签是一个连续数值) Clustering / Segmentation / Association Rules(聚类 /...

# 生日悖论 # 🌟 问题设定 有 m 个人,每个人的生日是等概率地在 1 到 365 天之间。问:至少有两个人生日相同的概率是多少? 我们设: n=365(即一年 365 天) m 是房间里的人数 p (m,n):至少两人生日相同的概率 # 🧮 如何计算这个概率? 我们可以通过 ** 反向思考(补集法)** 来计算。 # 1. 计算 “没有人生日相同” 的概率(记为 q (m,n)) 即,每个人的生日都不重复。 假设第一个人随便选生日(有 365 种选法), 第二个人必须选一个 不一样的(有 364 个选择), 第三个人有 363 个可选…… 直到第 m 个人,有...

# 🧪 一、统计研究类型以及一些概念 # 1. 研究的类型 观察性研究(Observational Study) 被动观察,不控制变量。 只能揭示相关性,不能说明因果。 例子:晒黑设备与皮肤癌、使用电脑时间与血压 简单的观察发生了什么,记录受试者的信息,不对受试者进行任何操作。 实验性研究(Experimental Study) 主动施加处理(treatment),设置对照组。 可以探究因果关系。 例子:限制计算机时间组 vs...

# 1. 线性规划基础 可以根据条件列出一个不等式区间,然后根据目标函数来判断极值位于哪里 比如 lec 中的例题 目标函数:最大化形式 f (x,y)=200,000x+250,000yf (x, y) = 200,000x + 250,000yf (x,y)=200,000x+250,000y。 约束条件来自资源限制(如砖块、门、窗): 10,000x+8,000y≤168,000 4x+2y≤60 5x+10y≤150 x≥0,y≥0 示意图: 这个点通过平移 k=-0.8...

# 一、多边形的三角剖分(Polygon Triangulation) # 1. 算法 1 row123while 多边形 P 尚未被完全三角剖分: 找到一条有效对角线 (x,y) 输出对角线 (x,y) # 📌算法复杂度分析: 算法复杂度从以下三个方面分析: 对角线数量(Number of potential diagonals): 一个多边形有 n 个顶点,每对顶点都有可能构成对角线,所以潜在对角线最多为 O (n2) O (n^2) O (n2)。 检查一条潜在的对角线是否合法(Testing one potential...

首先,这一门课的两个重要方法:反证法和数学归纳法 这两个方法在后续的正确性证明当中使用的相当频繁 然后引入这门课的第一个问题:艺术画廊问题 即 一个艺术画廊中需要放多少个守卫才能监视到整个画廊 每个守卫的视野距离无限,角度 360 度 然后引入上界与下界: 上界我们可以首先松弛一点,即一开始的上界定为 n-2,n 为边数,因为我们可以以最差的角度来考虑,即把整个多边形分成 n-2 个三角形,并且每个三角形都放一个守卫 #...