编译原理第四章笔记

编译原理第三章笔记

首先查阅相关的资料，比较谱聚类算法与传统的聚类算法K-mean的区别。 K-mean实现： 确定 K 值，随机选取 K 个点 以这 K 个点为中心质点，对原始数据集中中的每个点分别计算离哪个中心点更近 计算结束就将原始数据集分为 K 个类，对 K 个类重新计算中心质点（平均值法） 若全部 K 类新计算出的中心质点与该类上一个中心质点的距离小于一个阈值，则认为聚类操作已经收敛了，聚类结束 否则重复步骤 2-4 K-mean的优缺点主要如下： 优点： 原理简单，易于理解 聚类效果不错 缺点： 需要提前确定K值（划分种类数） 个别噪点对于总体效果影响较大 谱聚类实现： 邻接矩阵 W ε 近邻法 只取距离小于ε的边 K 近邻法 两点互为 K 近邻 其一为 K 近邻 全连接法 常采用，但是需要但不好确定参数σ 度矩阵 D 拉普拉斯矩阵矩阵 L L= D - W 正规化 $D^{-1/2}LD^{-1/2}$ 计算 K 个最小特征值对应的特征向量$h_i$,特征向量组成矩阵$H^{n*k}$ 无论是 Ncut 还是 Radioc....

文章借鉴 内存寻址之分页机制 与 内存分页、寻址方式那些事 写在前面 分页与分段机制 分段机制是Intel CPU一直保持的机制,而分页机制在80x86的计算机中是一种可选的机制,但只有在保护模式下才存在这种机制,也就是说保护模式下才存在分页寻址的机制,但保护模式不一定开启分页寻址机制. 内存碎片化问题: 进程A进来，向os申请了200的内存空间，于是os把0~199分配给A 进程B进来，向os申请了5的内存空间，os把200~204分配给它 进程C进来，向os申请了100的内存空间，os把205~304分配给它 这个时候进程B运行完了，把200-204还给os但是很长时间以后，只要系统中的出现的进程的大小>5的话,200-204这段空间都不会被分配出去（只要A和C不退出）。过了一段更长的时间，内存中就会出现许许多多200-204这样不能被利用的碎片 分页的原因 解决内存碎片化问题,分页机制将虚拟内存空间和物理内存空间划分为同样大小的单位-页面,并以页面作为最小分配单位,然后将内存按照页为单位进行内存分配,这样一段内存空间就可以属于很多进程.内存在虚拟中为连续的,物理中离散....

引入问题 首先来看这样一个问题 现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数 N（≤1000）和候选道路数目 M（≤3N）；随后的 M 行对应 M 条道路，每行给出 3 个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从 1 到 N 编号。 输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出 −1，表示需要建设更多公路。 根据题目的描述，我们可以得知这是一道图论的题目，图为带权无向图，边上的权值即为题中描述的道路修建成本。 现在需要我们根据已有的图，求该图的最小（权值和最小）生成树。 这时候就需要引入解决问题的最小生成树算法了。 Prim 算法思路 首先读入所有的边，边的数据结构是一个结构体，主要包括：起点、终点、权值。 读入边之后按照边的权值由小到大排序。初始化一个数组记录边加入生成树的状态，初始时全部边为未加入。再初始化一个数组记录结点加入生成树的情况。 将某一个结点加入生成树（改变状态标志），因为所....

编译原理第二章笔记

这是由BBfat推荐给我的一道经典面试题

编译原理第一章的笔记

题目： 给定一个长度为 n 的整形数组 nums，求从数组索引 l 至 索引 r 的整数序列中，连续序列和的最大值为多少。 思路： 本题的主要思路，可分为两种 使用遍历的思想，遍历出序列的每种情况，逐一求和，计算最大值 但这种思路及其耗费时间,不可取。 使用动态规划的思想，使用一个数组 dp 记录，从索引 l 起包含位置 k 连续序列和的最大值 （l<=k<=r），最大值可由下面的公式推导。 dp[k] = max{ num[k] , num[k] + dp[k-1] } 公式解释： 这个公式的意思很明了，即某个位置之前的序列和若为正，那么包含之前的序列，肯定会使包含当前位置的序列和增大。 这个公式不好理解之处在于，若一个位置的值为负还要包括他吗？举个例子来说明： 若位置 i 处值为负，之前序列和为正，那么虽然包括了他使到这个位置为止的序列和减小，但是起到了连接 i+1 位置的作用，若 i+1 位置的值很大，那么包含 i 位置使序列和减小的损失就可以忽略了，因为到 i+1 处的序列和是增大的了。 若之前序列和为负，那么包含之前序列就没有任何意义，到 i ....

该文章已经加密。