《计算机网络》笔记 - 概述

ALOHA IP LAN TCP WAN 接口 网络 蓝牙 路由 多路复用 操作系统 电话网络

顾名思义,计算机网络是指计算机连接而成的网络。但我们首先还是需要区分一下计算机网络分布式系统

  • 分布式系统 对于用户是一个统一的整体,只有一个模型或泛型,由操作系统之上的中间件负责实现。 eg. 万维网(world wide web)
  • 计算机网络 大量独立的计算机互相连接起来共同完成计算任务。

算法导论笔记 - 图算法

Dijkstra 排序 算法 队列 最小生成树 单源最短路径 广度优先搜索 深度优先搜索

基本的图算法

图的表示

图 G=(V,E) 可以用两种标准表示方法表示。

  1. 邻接链表:由一个包含 |V| 条链表的数组 Adj 构成,每个结点有一条链表。

    权重图:直接将边 (u,v) 的权重值 w(u,v) 存放在 u 的邻接链表里。 邻接链表表示 稀疏图(边的条数|E|远小于$|V|^2$)时非常紧凑。

  2. 邻接矩阵:由$|V|\times |V|$的矩阵 $A=(a_{ij})$ 表示: $a_{ij}= \begin{cases} 1,~if~(i,j)\in E\
    0,~other \end{cases} $

    邻接矩阵更适合表示 稠密图、需要快速判断任意两个点是否相连的图。

算法导论笔记 - 高级数据结构

B树 指针 磁盘 算法 红黑树

B树

  • B树类似于红黑树。他们在降低磁盘I/O操作数方面更好一些。因为B树的分支因子可以非常大,所以其高度要比红黑树小得多。
  • B树是以一种自然的方式推广了的二叉搜索树。

B树的定义

我们假定,任何与 关键字相联系的 卫星数据将与关键字一样存放在同一结点中,并随着关键字一起移动。一棵B树T是具有以下性质的有根树(根为T.root):

B+树是B树的变种。

  1. 每个结点x有如下属性: a. x.n,表示结点x中的关键字个数 b. x.n个关键字以非降序排列 c. x.leaf,表示x是否为叶结点
  2. 每个内部结点包含 x.n+1 个指针指向孩子们 c[i]
  3. x 中的关键字 x.key[i] 对子树中的关键字 k[i] 进行分割,n个关键字,n+1个子树
  4. 每个叶结点有相同的深度,即树的高度h
  5. 每个结点的关键字数由 最小度数(minimum degree)t>=2控制: a. 除根节点外,每个结点至少含 t-1 个关键字 b. 每个结点至多含 2t-1 个关键字

如果 n>=1,那么对任意一棵包含n个关键字、高度为h、最小度数t>=2 的B树T,有 $h\leq \log_t \frac{n+1}{2}$

算法导论笔记 - 高级设计和分析技术

分治 常量 排序 数组 算法 贪心 队列 二叉树 动态规划 字符编码 矩阵连乘 哈夫曼编码 最优二叉搜索树 最长公共子序列

动态规划

动态规划方法通常用来求解 最优化问题(optimization problem),通常有四个步骤:

  1. 刻画一个最优解的特征
  2. 递归地定义最优解的值
  3. 计算最优解的值
  4. 利用计算出的信息构造一个最优解

动态规划(dynamic programming)与分治方法相似,都是通过组合子问题的解来求解原问题。区别在于分治法的子问题互不相交,而动态规划应用于子问题重叠的情况。

导航: 上一页 下一页

加载中...

🔝