Yarrow Blog

Dijkstra’s algorithm算法图示：Bilibili《最短路径查找—Dijkstra算法》 Dijkstra’s algorithm（迪杰斯特拉算法）是一种用于求解单源最短路径问题的经典算法。该算法可以计算从单个起始节点到图中所有其他节点的最短路径。Dijkstra’s algorithm适用于没有负权边的有向或无向带权图。 算法的基本思想是从起始节点开始，不断扩展当前已知的最短路径，直到到达目标节点或处理完所有节点。该算法使用一个辅助数组（通常称为距离数组）来保存从起始节点到每个节点的最短路径长度。算法的步骤如下： 初始化：将起始节点的距离设置为0，其他节点的距离设置为无穷大（表示尚未计算出最短路径）。 遍历：从起始节点开始，依次选择当前距离数组中距离最小的节点，记为当前节点。 更新：对于当前节点的所有邻居节点，计算通过当前节点到达它们的路径长度，并与距离数组中的当前最短路径进行比较，如果计算出的路径更短，则更新距离数组。 标记：将当前节点标记为已处理，继续遍历未被标记的节点，重复步骤2和步骤3，直到所有节点都被处理。 完成：当所有节点都被标记后，距离数组中的最短路径 ...

贪心算法贪心算法（Greedy Algorithm）是一种常见的优化算法，用于解决一类最优化问题。在每一步选择中，贪心算法总是选择当前看起来最优的选择，而不考虑该选择会不会影响未来的选择。这种贪心选择的策略通常是局部最优的，但不一定是全局最优的。 贪心算法适用于一些特定类型的问题，特别是那些具有贪心选择性质和最优子结构性质的问题。贪心选择性质是指每一步的局部最优选择最终能够导致全局最优解。最优子结构性质是指问题的最优解包含子问题的最优解。 贪心算法的基本思想如下： 首先定义问题的优化目标，明确要求找到最大值或最小值。 从问题的所有可选解中，选择一个局部最优解，作为当前的选择。 接着，检查该局部最优解是否满足问题的约束条件和要求。 如果满足约束条件和要求，则将该局部最优解加入到最终解集合中。 否则，舍弃该局部最优解，并回到第2步，继续选择下一个局部最优解。 最终得到的解集合就是整个问题的全局最优解。 需要注意的是，贪心算法并不适用于所有类型的问题。在某些问题中，贪心算法可能会得到次优解或者不正确的结果。因此，在应用贪心算法时，必须要确保问题具有贪心选择性质和最优子结构性质，并进行充分 ...

Arithmetic Progression Graphs算术级数图（Arithmetic Progression Graphs, APG），也称为等差数列图，是等差数列的可视化表示。等差数列是一组数字，其中任意两个连续项之间的差值总是相同的。这个常数差值被称为算术级数的公差。 APG的顶点权重依序成等差数列，与某一顶点相连的所有边的权重之和等于顶点权重，例如下图所示： APG一些已知特性 判断APG给定一副图，并确定图的所有顶点值（已知图的顶点值成等差数列），这幅图是否能够称为APG？ 问题的本质主要是确定是否存在满足条件的边的权重序列，确保与顶点相连的边的权重值之和等于顶点权重值

Perrin numbers佩林数（Perrin numbers）是一个整数数列，以P(n)表示，其中 n 为非负整数。佩林数列的定义如下： P(0) = 3P(1) = 0P(2) = 2 对于 n ≥ 3 的情况，佩林数列的每一项都由以下递推公式获得： P(n) = P(n-2) + P(n-3)，其中 n ≥ 3 因此，佩林数列开始为：3、0、2、3、2、5、5、7、10、12、17、… 佩林数由法国数学家Alfred J. Perrin于1899年引入的，以他的名字命名。这个数列在组合数学和计算机科学中有一些应用。 佩林数列的前几项为：3、0、2、3、2、5、5、7、10、12、17、…，以此类推。 123n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14P(n) = 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51div? = n, n, y, y, n, y, n, y, n, n, n, y, n, y, n 佩林数具有很多特殊的性质，观察上面 ...

FOCUS OF THIS LECTURE Identify access control requirements Know access control elements Understand access control systems 授权（AUTHORISATION）向系统实体授予权利或权限以提供对特定资源的访问的过程，也称访问控制（Access Control） 访问控制要求（ACCESS CONTROL REQUIREMENTS） 可靠的输入（Reliable inputs） 经过身份认证的实体，例如使用UPI或密码登录 真实的资料，例如学生或教职工成员 最小特权（Least privilege） 最小特权原则表示授予完成某项工作的最低访问权限集，例如，访问单个课程与所有课程 管理职责（Administrative duties） 只有特殊实体才能管理访问权限，例如，管理员授予、撤销或更新访问权限 访问控制组件（AC ELEMENTS） 主体（Subject） 可以访问对象的实体，它可以是用户也可以是用户授权的进程 对象（Object） 需要被保护的 ...

FOCUS OF THIS LECTURE Understand identification and authentication Learn how passwords are protected 身份识别和认证身份识别（IDENTIFICATION）系统实体提供其声明的身份的过程，例如UPI（统一支付接口） 认证（Authentication）验证系统实体声明的身份的过程，例如PIN码或秘密 密码漏洞（PASSWORD VULNERABILITIES）Offline dictionary attack 离线字典攻击离线字典攻击就是攻击者获取到口令文件（字典），有了离线字典文件后,针对口令文件攻击者直接查表，一旦哈希值匹配成功了，那么就可以得到口令明文。 应对策略： 防止未经授权访问密码文件 识别入侵的入侵检测措施 快速重新发布密码 Specific account attack 特定账户攻击攻击者针对某些特定账户进行攻击，不断猜测并提交密码直到成功 应对策略： 尝试失败一定次数后锁定机制 另一种方法是逐渐延迟每次后续尝试 Popular password attack ...

DPD“Data Protection Directive”，欧盟隐私和人权法的组成部分，DPD 负责个人数据的保护和处理，它不保护欧盟以外的欧盟公民的个人数据 GDPRGDPR (General Data Protection Regulation) 是欧盟关于数据保护的法规，它协调了整个欧盟的数据隐私法，保护并增强了欧盟公民的数据隐私，重塑了欧盟处理数据隐私的方式。 为什么选择GDPR GDPR 取代了 DPD GDPR 依法保护欧盟境外欧盟公民的个人数据 GDPR 扩展了个人数据的定义 照片、音频、视频、金融交易、社交媒体帖子等。 设备标识符（IP 地址、IMEI 号码） 浏览记录 遗传信息 数据Data Personal data：与已识别或可识别人员相关的任何信息，例如电子邮件ID De-identified data：去识别化数据，没有任何个人标识的个人数据（Personal data），例如匿名帖子 Anonymised data：匿名数据，没有任何个人标识的个人数据，无法进行重新识别，例如首次购房者的平均年龄 常用术语Data subject 数据主体数据主体是 ...

参考：经典算法问题——稳定匹配（Stable Matching） Gale-Shapley Algorithms简称“GS 算法”，也称为延迟接受算法。是 Gale 和 Shapley 为了寻找一个稳定匹配而设计出的市场机制。运行时间在算法输入的大小上是线性的。根据其使用方式，它可以找到对匹配一侧的参与者或另一侧的参与者最佳的解决方案。 问题描述给出一个 $n$ 个男性的集合 $M$，和 $n$ 个女性的集合 $W$，其中： 每位男性根据对所有女性的心仪程度从高至低进行排名； 每位女性根据对所有男性的心仪程度从高至低进行排名。 根据以上条件，我们需要找到一个“稳定匹配”。 基本概念匹配 Matching匹配 $S$ 是一个包含有序数对 $m-w$ 的集合，其中 $m \in M$ 且$w \in W$，其中： 每个男性最多出现在一个数对中； 每个女性最多出现在一个数对中。 完美匹配 Perfect matching如果 $\left| S \right|=\left| M \right|=\left| W \right|=n$ 则匹配$S$是完美匹配，也就是说，男女数量相等且都 ...

Lectrue 3 Understand computer security Understand human aspect of security Understand network security Next, we can build on these three to understand cyber security OSI 安全架构OSI 安全架构分为三大类，即安全攻击、安全机制和安全服务。 安全攻击（Security attack）安全攻击是指个人或实体企图获得未经授权的访问以破坏或损害系统、网络或设备的安全性。 被动攻击（Passive attack）：试图从系统中学习或利用信息，但不影响系统资源。 窃听（Release of message content / disclosure）：攻击者在两方不知情的情况下拦截和收听他们之间的通信。 流量分析（Traffic analysis）：攻击者分析网络流量模式和元数据以收集有关系统、网络或设备的信息。入侵者无法读取消息，只能了解加密的模式和长度。可以使用多种技术执行流量分析，例如网络流量分析或协议分析。 主动攻 ...