Hexo

无限小求椭圆切线

并行计算 两学分的水课… [课程主页]:Parallel computing - structures, algorithms, programming 并行计算结构将并行计算结构抽象为图，节点为计算节点，不同的结构有着不同的通信复杂度。 一维线性阵列：对剖宽度为2（对剖宽度是将一个并行结构拆分为两个大小接近的部分所切断最小的链路；sparest...

谱图论引言笔者在大二上学期学习了图论与算法的相关内容，并且有一定的离散数学基础，不过谱图论作为单纯使用线性代数手法分析图的邻接矩阵等性质的一门学科，笔者从未接触过。 拉普拉斯矩阵

KMP 算法 在线性的时间和空间复杂度中查询字串s在文本t 中出现的次数，linux中grep命令实现 [前缀函数与 KMP 算法 - OI Wiki]:

K近邻算法算法解决的是：给定训练数据集，每一个数据已经贴好标签，对于新引入的测试数据，算法如何根据已有的训练集正确分类，因此该算法是一个懒惰学习的分类算法。 采用的策略也是多数表决法，即确定k值后，在训练数据中选出k个度量距离最近的数据，选择多数的数据类别给测试数据贴上标签。 度量距离推荐采用普遍性更强的Lp范数。 KD树的构造构造二叉平衡树，采用分治法，在一次递归中，对数据进行某一维度上的排序（一般选取方差最大的一个维度），后选取中点作为pivot划分。 K近邻搜索在二叉搜索的基础上加入了回溯算法，避免最优解在未搜索的子树。 python代码实现 笔者本打算使用c++手搓后放弃转python 1234567891011121314151617181920from sklearn import datasetsfrom sklearn.neighbors import KNeighborsClassifierimport numpy as npiris = datasets.load_iris()iris_x = iris.datairis_y =...

密码学原理 南京大学2025-2026秋季课程 参考教材：现代密码学：原理和协议 (乔纳森·卡茨 (Jonathan Katz) etc.) 第一章 古典密码学概述密码学形式化定义的一些概念如密钥空间，明文空间，密文空间，密钥生成函数等，古典密码如凯撒密码的密钥空间极小，部分变种有极大的密钥空间，但是破译方案仍然存在，书中作者认为古典密码学建立在“设计方案，破解方案”的无聊循环中。 第二章 完善保密加密定义：（来自克劳德.香农）$$Pr(M=m|C=c)=Pr(M=m)$$作为敌方截获密文之后并不能获得任何与明文的概率分布相关的信息， 换句话说：你看到了密文，但是你不能根据密文进一步缩小它对应的明文空间！ 等价定义：$$Pr(C=c|M=m)=Pr(C=c)$$完美不可区分性：$$Pr(C=c|M=m_{0})=Pr(C=c|M=m_{1})$$ 一次一密对称密钥密码学3.1...

数据库第二章 关系数据模型实体-联系模型，实体是对数据的抽象，属性是实体的特征，联系是实体之间的联系。 实体与实体之间的联系本质上是函数，可以为单射，双射函数。 第三章 关系数据库系统关系数据库系统是有着业界统一标准，统一语言SQL，以及广泛为业界所使用的。 1.依靠一一对应的函数能够唯一访问，查找数据表中的原子数据 2.原子数据可以赋空值的能力 关系代数这种数据模型更像哈希表，有（多个）key和value，通过一张表构建关系数据模型。 二维表有n列则被称为n元表，一列有m行，一行是由n个属性值组成的元组。 表中的每一列称为关系的域（可以理解为定义域）,所有域的笛卡尔积组成了一切可能的组合， 而关系数据表是这个笛卡尔积的子集（真实存在有意义的数据）。 将关系数据库中的关系理解为集合，那么关系的删除，修改，增加也就可以看作集合上的操作了， 下面介绍关系数据库中查询的操作，这需要引入新的运算。 投影运算： ,则 选择运算：的形式，表示中满足性质的元组，是一个逻辑表达式。 通过投影运算和选择运算就能够选择关系数据库中的所有关系元组 关系代数中的扩充运算：

高级算法 在大二下学期学习了yyt老师主讲的概率论与数理统计，作为拔尖班课程，yyt老师掺杂了很多有关随机算法，组合数学的私货，于是在大三上学期继续修读由yyt老师开设的高级算法。 课程网站：TCS Wiki Min-cut一个非常经典的图论模型与算法，笔者在大二上学习了最大流最小割定理，之后学习了解决该问题的随机算法Karger's Algorithm，原理十分简单，只需要有基本的图论与条件概率的知识即可。 这里是一篇讲义，读者可自行参考CS161Lecture16.pdf。 当我们找到了图G的最小割时，图的节点被分为两个互不相交的集合S和T，其中一条边若连接着分别属于这两个集合的顶点，那么这条边就属于当前划分的割。Karger算法将集合S,T视为两个super node。集合内部的边均可收缩，因为对最小割的寻找没有影响。 算法过程123for (int i=1;i<=n-2;i++)...

形式语言与自动机 南京大学2025-2026秋季学期课程 [Formal Languages and Automata]:课程主页 引言1.自动机可以理解为检测一种形式化语言的工具，通过用节点表示状态，用边表示状态的迁移，最简单的是确定性有穷状态机，状态有限，根据输入的内容确定性进行状态迁移。 “最终”和”接受“两个状态：自动机接受一个语言的字符串，如果最终停止的状态节点是被接受的，那么这个状态是终止状态，终止状态是可以有出边的，因为可能有没读完的字符串。 有穷状态机非确定性有穷自动机...

数据结构与算法 笔者从2023年入学以来便饱受数据结构与算法的摧残， 建议大家直接转[OI Wiki - OI Wiki]:笔者会不定期更新一些有意思的内容 字典树 本学期的形式语言与自动机课程有着十分坐牢的编程作业，于是笔者决定简单了解下这方面所需的编程基础，首先就是字典树，直接转[字典树 (Trie) - OI Wiki]: