Xinhecuican's Blog

结构 引脚名称 引脚功能 I/$O_0$ - I/$O_7$ 数据输入输出 CLE 命令锁存使能 ALE 地址锁存使能 $\overset{-}{CE}$ 芯片使能 $\overset{-}{RE}$ 读使能 $\overset{-}{WE}$ 写使能 $\overset{-}{WP}$ 写保护 $R/\bar{B}$ 就绪/忙输出信号 $V_{cc}$ 电源 $V_{ss}$ 池 NC 不接 K9F1208U0M容量64mb，每一页的大小是512字节，并且每一页上还有额外的字节。也就是说总共有$2^{18}$个字节 读写nand的过程： 发出命令字 发出地址 读写数据 命令字及操作方法 命令 第一个周期 第二个周期 第三个周期 Read1(读) 00h/01h - - Read2(读) 50h - - Read ID(读芯片ID) 90h - - Page Program(写页) 80h 10h - Block Erase(擦除块) 60h D0h - Read Status(读状态 ...

概念k-means算法属于非监督学习，也就是事先不知道给的数据属于那一类，需要自己去分类。它的基本思想是把数据点密集的一群分成一类。 具体过程： 随机选择k个类的初始中心 在c次迭代中，对任意一个样本，求到各中心点之间的距离，将该样本归类到最近中心的那个类 使用均值等方法更新中心点。 如果两次更新匪类相同也结束 例如划分三个点(1, 1) (2, 3) (4, 6)是一类，那么新的中心点是((1+2+4)/3, (1+3+6)/3),不一定要在原有点上 实现import numpy as np# Function: K Means# -------------# K-Means is an algorithm that takes in a dataset and a constant# k and returns k centroids (which define clusters of data in the# dataset which are similar to one another).def kmeans(X, k, maxIt): # maxIt是初始化次数 ...

缘起B树属于动态查找树，二叉树，平衡二叉树，红黑树都是动态查找树。关于查找的基础内容可看。他们的查找效率都可以达到$log_2^n$，其中n是树的深度。 虽然他们的查找效率和遍历相比已经有很大提升了，但是和哈希相比又大大不如。QMap（红黑树为数据结构）在n=10之后效率就比不过QHash(哈希为数据结构)，越到后面差距越大。但是在数据库中却是使用B树作为数据结构。因为数据库除了考虑速度还要考虑空间，而hash对空间要求大。因此日常对空间不敏感的程序尽量使用hash。 前面已经说了，决定查找次数的是树的深度。假如有65535个数据，那么树的深度为16，那么平均查找深度为 (1 + 2 2 + 3 4 + 4 8 + 5 16 + …. + 16 * 32768) / 65535 = 14.如果14个数据块位于2个不同的磁盘块上（因为是指针不是连续存储），那么就需要2次磁盘读取，所需时间便在毫秒以上。他和直接查找也显现不出太多优势。 因此减少树高就是非常必要的了。一种解决思路就是由二叉树变为多叉树，每一层容纳的数量变多了，树高自然就减少了。此外，各个分支如果树高大致相同毫无疑问平 ...

8数码问题8数码问题是在一个九宫格上有8个数，初始中间一个空缺，外围随机排布，最终要8个数按顺序排列初始3281 4567中间的格子可以利用，也就是说可以328 14567最终1238 4765可以使用广度优先搜索进行遍历，那么第一层有四种情况（将上下左右4个移动到中间)，然后第二层有8种第二层的一个例子328 14567第一种 28314567或者328514 67 然后就这样不断遍历，直到找到最终结果 但是这样的复杂度明显太高，我们可以定义一个函数预先判断走那条路可能得到更好的结果。 定义f(n) = g(n) + h(n). 其中g(n)表示现在是第几层的搜索，h(n)表示现在和最终结果还有多少不同 拿上面的例子假设现在到了 28314567则g(n) = 2他和最终结果1238 4765有2个相同，因此h(n) = 6然后根据上面的这个式子，每次选取最小的进行搜索，这样相比于盲目的搜索更快 A*算法通过上面的例子，我们对A算法有了初步的了解。A算法的关键就是定义 f(n) = g(n) + h(n) g(n): 表示当前已经花费的代价。也可以说是距起点的代价 h(n): 预计 ...

语法分析基础编译的第一步是词法分析，第二步是语法分析。词法分析产生的结果是标识符，第二步是判断源程序文法是否合法。例如if{...}就是不合法的文法，但是他产生的标识符都是正确的。 工作原理： 通过上下文无关文法产生的文法式，识别输入字符串是否是一个句子。从左至右每次读入一个字符进行规则匹配。 问题及解决左递归例如 规则为P->Pa字符串为a起始非终结符为P读入a后将栈中的P展开为Pa,然后因为是从左往右匹配因此读入P，展开为Paa,如此递归，得到死循环 消除递归的方法： 消除直接左递归 经过这样的转换之后产生的语言没有改变，但是消除了直接的左递归 再将它一般化得： \begin{aligned} A &\to A \alpha_1 | A\alpha_2 | \dots | A \alpha_m | \beta_1 | \beta_2 | \dots | \beta_n\\ 则可以改写为\\ A &\to \beta_1 A^{'} | \beta_2 A^{'} | \dots | \beta_n A^{'}\\ A &\to \alpha_1 A ...

字符串匹配是在一个长度为s的t串中找到和长度为m的p串相同的部分。t串是匹配串，p串是模式串 Pabin-Karp算法它的基本思想是哈希。即将匹配串中每一个长度为m的子串进行哈希并与p串的哈希值进行比较。 假设模式串p[1…m]，得到哈希值的算法为 p = （p[m] + 10(p[m-1] + 10(p[m-2] + … + 10(p[2] + 10(p[1]))…)） % q — 霍纳法则 q是为了防止超范围的，10是基数，可以变成其他值 对于t串（匹配串），它的处理方法与p串相同，但是还需要进行移动，移动的方法为 t_2 = 10(t_1 - 10^{m-1}T[s+1]) + T[s+m+1]其中T[s+m+1]是原来字符串的高一位，T[s+1]就是原来字符串的最低位。也就是减去最低位然后将字符串左移一位再加上最高位。 $10^{m-1}$可以使用快速幂的方法在O(lgm)时间计算完。 在计算完所有子串之后就可以对每一个哈希值进行比较了。如果p串哈希值和子串哈希值相同并不能说明二者一定相同，还可能产生哈希冲突。因此还需要对每一个字符进行匹配。 bool match(stri ...

支配 支配集： 挑选出一些顶点组成支配集，使得所有其他的点都和这个集合中的点相连。 极小支配集： 支配集删去任意顶点之后不是支配集 最小支配集： 支配集中顶点数量最小的 只配速： 最小支配集中点的个数 例如图中两个都是极小支配集，其中第一个是最小支配集。 定理： 无向图无孤立点，$V_1^$是极小支配集，则存在$V_2^$也是极小支配集，且$V_1^ \cap V_2^ = \oslash$ 证明： $V_1^$是支配集，那么$V - V_1^$也是支配集反证： 如果不是支配集，那么存在$\exists u \in V_1^ , \forall v \in V - V_1^ , (u, v) \notin E$, 因为u不是孤立点，那么$V_1^ - {u}$还是支配集。所以$V - V_1^$是极小支配集 $V - V_1^*$是支配集，那么它的子集中必定存在极小支配集 求最小支配集 例如求上图的最小支配集 \begin{aligned} \Psi (v_1 , v_2 , v_3 , v_4 , v_5 , v_6 ) &= (v_1 + v_2 + v_3 + v_4 ...

多路复用和多路分解多路分解： 多路分解指的是将报文段中的数据提交到正确的套接字 1 1. 应用程序接受信息的接口 ↩ 多路复用：从主机不同套接字上收集数据，并为每个数据块加上首部信息（如源端口号和目的端口号等）形成报文段，然后传到网络层。 多路复用也就是从传输层到网络层的过程，而多路分解是从传输层到应用层的过程 要想提交到正确的套接字，其实也就是提交到正确的端口。在计算机中端口范围在 0-65535 中，其中 0-1023 是周知端口号，有特殊用途，而其他就是分配给应用程序使用的了。 UDP 的多路复用和多路分解 UDP 的运输层报文段包括应用程序数据，源端口号，目的端口号和其他两个值。通过目的端口号可以标识要送到目的的具体位置，而源端口号则是为了送回数据时使用的。 TCP 的多路复用和多路分解 TCP 和 UDP 区别是 TCP 套接字是一个四元组 (源 IP 地址， 源端口号， 目的 IP 地址， 目的端口号）来标识的。因此他还可以让两个到同一个端口号的 TCP 连接互不干扰（因为有了源 IP 地址，所以可以分辨出这个数据时从哪发出的） UDPUDP 是一种不可靠运 ...

概念很多词语在不同语境下有不同含义，我们需要确定在某种语境下具体的含义。 语义消岐（WSD)定义： 确定一个歧义词在某种语境下应该使用哪种语义 消岐面临的三个问题： 判断一个词是否是多义词 对不同多义词的含义进行区分 确定在不同语境下应该使用哪种语义 基于贝叶斯的消岐假设一个词有多个意象$s_1 s_2 .. s_n$，上下文（句子）C$w_1 w_2 … w_n$需要确定在该语境下使用哪种语义，即： P(s_i | C ) = \frac{P(C | s_i ) P(s_i )}{P(C)} P(C | s_i ) = P(\{w_j | w_j \in C \} | s_i ) = \prod_{w_j \in C}\frac{Count(w_j , s_i )}{Count(s_i )} 其中$P(s_i)$是这个词义出现的概率 基于互信息互信息是使用另一个信息来表示当前信息。例如想知道当前词的语义信息，我们可以根据上一个词的时态或者是语态。 设一个中文词在英语中有若干译词$t_1 t_2 … t_n$,并且这个中文词有若干含义$v_1 v_2 … v_n$。 算法过程 ...

HTTP协议基础HTTP由两个程序组成：客户程序和服务器程序。客户程序就是我们电脑上的程序 一个Web页面是由若干对象组成的，对象指的是一个文件，例如HTML文件，JPEG图像，Java小程序等。 多数Web页面包含一个HTML基本文件和几个引用对象。首先获得基本文件，基本文件之中又有链接到其他文件的URL,然后通过这些URL又获得其他文件。 例如有时我们直接从浏览器下网页文件打开后发现这个网页既没有排版也没有字体颜色，也没有图像。这里我们下载的文件就是HTML基本文件，如index.html.如果我们想要获得完整的页面就需要根据基本文件中的url再去获得其他文件然后通过浏览器合并到一起。 HTTP使用TCP作为传输层协议。TCP大致是首先发起一个与服务器的TCP连接，在链接成立之后就可以进行稳定的传输了。 非持续连接和持续连接非持续连接指的是所有请求都通过单独的TCP连接发送，持续连接时所有请求都通过同一个连接发送。 HTTP的非持续连接假设我们请求一个HTML基本文件和若干图形。并且这些对象位于同一台服务器上，那么非持续连接请求的大致过程是： HTTP客户进程在端口号80发起一个 ...