基于连通性的状态压缩

A. 请列举刀片服务器的主要优点

您好,下面我来回答下您提出的问题.
先说说刀片服务器,刀片式服务器是指在标准高度的机架式机箱内可插装多个卡式的服务器单元，实现高可用和高密度。每一块"刀片"实际上就是一块系统主板。它们可以通过"板载"硬盘启动自己的操作系统，如Windows NT/2000、Linux等，类似于一个个独立的服务器，在这种模式下，每一块母板运行自己的系统，服务于指定的不同用户群，相互之间没有关联。不过，管理员可以使用系统软件将这些母板集合成一个服务器集群。在集群模式下，所有的母板可以连接起来提供高速的网络环境，并同时共享资源，为相同的用户群服务。在集群中插入新的 "刀片"，就可以提高整体性能。而由于每块"刀片"都是热插拔的，所以，系统可以轻松地进行替换，并且将维护时间减少到最小。

这些刀片服务器在设计之初都具有低功耗、空间小、单机售价低等特点，同时它还继承发扬了传统服务器的一些技术指标，比如把热插拔和冗余运用到刀片服务器之中，这些设计满足了密集计算环境对服务器性能的需求；有的还通过内置的负载均衡技术，有效地提高了服务器的稳定性和核心网络性能。而从外表看，与传统的机架/塔式服务器相比，刀片服务器能够最大限度地节约服务器的使用空间和费用，并为用户提供灵活、便捷的扩展升级手段。刀片式服务器已经成为高性能计算集群的主流，在全球超级500 强和国内100 强超级计算机中，许多新增的集群系统都采用了刀片架构。由于采用刀片服务器可以极大减少所需外部线缆的数量，可以大大降低由于线缆连接故障带来的隐患，提高系统可靠性。
值得一提的是,惠普公司推出的刀片服务器更具有特色,相比同类服务器具备以下特点
1.经济：与传统IT相比，整合设计有助于降低购买成本，使用户更加轻松地拥有立杆见影的集成冗余特性；与机架安装式基础设施相比，所需线缆和其它组件减少达40％。

2.灵活：惠普虚拟连接和模块化设计有助于顺利进行变更，加快发展速度无需重新布线即可动态添加、更换和恢复资源。

3.节能：惠普智能能耗技术可将电源和散热作为一种资源进行管理，能源效率大幅提升功耗降低高达30％，数据中心内的热气排放量显着减少。

4.省时：惠普洞察管理可有效管理自动化基础设施，节省客户的宝贵时间提高管理员工作效率，简化库存、供应和恢复，加快补丁修复速度。

回答完毕,希望能帮助到您.

B. oier的知识能力体系

数学离散数学集合论 关系 代数系统 数理逻辑 图论
组合数学排列组合 母函数 群论 递推与递归 莫比乌斯反演
数学线性规划 动态 整数
高等数学向量 行列式与矩阵 微积分初步
概率统计
初等数论素数 整数理论 同余与模线性方程
计算几何
数据结构存储结构线性表
（一级结构）静态：数组 栈 队列 广义表 字符串
动态：指针链表 动态数组
树
（二级结构）表示法（静态、动态） 二叉树 森林
图
（三级结构）表示法（矩阵、邻接表、三元组）
特殊结构散列表（HASH表） 并查集 线段树 后缀树 哈夫曼树与哈夫曼编码 地址表Bit图 滚动数组 棋盘图 边顶置换图 二分点图（网络流）
常用方法遍历树 图 前/中/后序优先
转化拓扑排序（三级结构转一级结构） 最小生成树 最小树形图（三级结构转二级结构） 逆遍历
压缩路径树的线索化
压缩存储
查找线性直接 折半Fab
树形二叉查找树 平衡二叉树B+树B-树 线索二叉树索引表
排序插入排序直接排序、折半排序、2-路排序
交换排序冒泡排序 快速排序 归并排序
堆排序
基数排序链式基数排序 桶排序
代码素养代码的编写速度和准确性 误码率
算法实现
算法优化
调试 查错 测试
习惯变量名 注释 缩进 模块化
基本算法数学高精度计算（模拟计算）
表达式处理括号 前/中/后缀表达式 表达式树
排列组合求值 嵌套控制
高斯消元法
快速傅里叶变换（FFT）
筛选素数素数表
分数处理
基本操作实现大量数据赋值与移动Fillchar fillword move等函数
处理实数比较大小 高精度
字符串处理基本函数KMP算法
图论
（显示图搜索）路径问题
（边集）连通性测试传递闭包算法 极大强连通子图 最小点基
最短路问题标号法 第k小路 减半最短路Dijkstra算法floyd算法bellman-ford算法Warshall算法
特殊路径欧拉路及回路 哈密尔顿路及回路
图的中心和重心
生成树Kruskal算法Prim算法
集
（顶点集）覆盖集
独立集
支配集
割顶和块
网络流容量有上下界的网络最大/ 小流
容量有上下界的网络最小费用最大/ 小流
顶容量网络最大流
供求约束可行流
二分图匹配匈牙利算法
关键路径
搜索
（隐式图搜索）深度优先搜索
（回溯法）剪枝优化
预处理
记忆化搜索
可变下界的深度优先搜索
随机化搜索
广度优先搜索双向广搜*多向广搜
启发式搜索（A算法）
分枝定界
多阶段决策贪心算法
背包动态规划
棋盘动态规划
划分动态规划
区间动态规划
树形动态规划
状态压缩型动态规划
其他构造法穷举
模拟

C. 如何正确选择聚类算法

作者 | Josh Thompson

来源 | 数据派THU

Choosing the Right Clustering Algorithm for your Dataset - KDnuggets

聚类算法十分容易上手，但是选择恰当的聚类算法并不是一件容易的事。

数据聚类是搭建一个正确数据模型的重要步骤。数据分析应当根据数据的共同点整理信息。然而主要问题是，什么通用性参数可以给出最佳结果，以及什么才能称为“最佳”。

本文适用于菜鸟数据科学家或想提升聚类算法能力的专家。下文包括最广泛使用的聚类算法及其概况。根据每种方法的特殊性，本文针对其应用提出了建议。

四种基本算法以及如何选择

聚类模型可以分为四种常见的算法类别。尽管零零散散的聚类算法不少于100种，但是其中大部分的流行程度以及应用领域相对有限。

基于整个数据集对象间距离计算的聚类方法，称为基于连通性的聚类（connectivity-based）或层次聚类。根据算法的“方向”，它可以组合或反过来分解信息——聚集和分解的名称正是源于这种方向的区别。最流行和合理的类型是聚集型，你可以从输入所有数据开始，然后将这些数据点组合成越来越大的簇，直到达到极限。

层次聚类的一个典型案例是植物的分类。数据集的“树”从具体物种开始，以一些植物王国结束，每个植物王国都由更小的簇组成（门、类、阶等）。

层次聚类算法将返回树状图数据，该树状图展示了信息的结构，而不是集群上的具体分类。这样的特点既有好处，也有一些问题：算法会变得很复杂，且不适用于几乎没有层次的数据集。这种算法的性能也较差：由于存在大量的迭代，因此整个处理过程浪费了很多不必要的时间。最重要的是，这种分层算法并不能得到精确的结构。

同时，从预设的类别一直分解到所有的数据点，类别的个数不会对最终结果产生实质性影响，也不会影响预设的距离度量，该距离度量粗略测量和近似估计得到的。

根据我的经验，由于简单易操作，基于质心的聚类（Centroid-based）是最常出现的模型。 该模型旨在将数据集的每个对象划分为特定的类别。 簇数（k）是随机选择的，这可能是该方法的最大问题。 由于与k最近邻居（kNN）相似，该k均值算法在机器学习中特别受欢迎。

计算过程包括多个步骤。首先，输入数据集的目标类别数。聚类的中心应当尽可能分散，这有助于提高结果的准确性。

其次，该算法找到数据集的每个对象与每个聚类中心之间的距离。最小坐标距离（若使用图形表示）确定了将对象移动到哪个群集。

之后，将根据类别中所有点的坐标平均值重新计算聚类的中心。重复算法的上一步，但是计算中要使用簇的新中心点。除非达到某些条件，否则此类迭代将继续。例如，当簇的中心距上次迭代没有移动或移动不明显时，聚类将结束。

尽管数学和代码都很简单，但k均值仍有一些缺点，因此我们无法在所有情景中使用它。缺点包括：

相比之下，期望最大化算法可以避免那些复杂情况，同时提供更高的准确性。简而言之，它计算每个数据集点与我们指定的所有聚类的关联概率。用于该聚类模型的主要工具是高斯混合模型（GMM）–假设数据集的点服从高斯分布。

k-means算法可以算是EM原理的简化版本。它们都需要手动输入簇数，这是此类方法要面对的主要问题。除此之外，计算原理（对于GMM或k均值）很简单：簇的近似范围是在每次新迭代中逐渐更新的。

与基于质心的模型不同，EM算法允许对两个或多个聚类的点进行分类-它仅展示每个事件的可能性，你可以使用该事件进行进一步的分析。更重要的是，每个聚类的边界组成了不同度量的椭球体。这与k均值聚类不同，k均值聚类方法用圆形表示。但是，该算法对于不服从高斯分布的数据集根本不起作用。这也是该方法的主要缺点：它更适用于理论问题，而不是实际的测量或观察。

最后，基于数据密度的聚类成为数据科学家心中的最爱。

这个名字已经包括了模型的要点——将数据集划分为聚类，计数器会输入ε参数，即“邻居”距离。因此，如果目标点位于半径为ε的圆（球）内，则它属于该集群。

具有噪声的基于密度的聚类方法（DBSCAN）将逐步检查每个对象，将其状态更改为“已查看”，将其划分到具体的类别或噪声中，直到最终处理整个数据集。用DBSCAN确定的簇可以具有任意形状，因此非常精确。此外，该算法无需人为地设定簇数 —— 算法可以自动决定。

尽管如此，DBSCAN也有一些缺点。如果数据集由可变密度簇组成，则该方法的结果较差；如果对象的位置太近，并且无法轻易估算出ε参数，那么这也不是一个很好的选择。

总而言之，我们并不能说选择了错误的算法，只能说其中有些算法会更适合特定的数据集结构。为了采用最佳的（看起来更恰当的）算法，你需要全面了解它们的优缺点。

例如，如果某些算法不符合数据集规范，则可以从一开始就将其排除在外。为避免繁琐的工作，你可以花一些时间来记住这些信息，而无需反复试验并从自己的错误中学习。

我们希望本文能帮助你在初始阶段选择最好的算法。继续这了不起的工作吧！

D. noip需要准备哪些方面的基础知识。复赛需要做哪些类型的题目（提高组）

Noip算法（小超）
以下用n表示图的点数，m表示边数，k表示一个常数，log均以2为底数，存储边都采用边表。
【模拟】
高精度加、减、乘，除应该不需要
表达式求值（中缀转后缀，栈的操作）

【图论】
图的表示：邻接矩阵，邻接表，边表
单源最短路：dijkstra（O(n2)），bellman（spfa优化，O(km)）
传递闭包和floyd
最小生成树算法：prim（O(n2)），kruskal（O(m log m)）
拓扑排序（O(m)）
欧拉路（边一次）
汉密尔顿回路（点一次）

强连通分量
匹配算法（最大匹配，最小点覆盖，最小路径覆盖，最大独立集）
网络流算法（最大流dinic，最小费用流spfa）
差分约束系统

【树】
树的先序、中序、后序遍历
树中的最长路（两遍bfs）
特殊的树：二叉树
树形动态规划
并查集
字母树

【搜索】
深搜，一般需要剪枝，有可行性剪枝和最优性剪枝两种经常考。还有迭代深搜。
宽搜，双向广搜，估价函数。

【动态规划】
背包问题：01背包，无限背包，多重背包，有依赖的背包，二维费用背包。（参照背包九讲）
树形动态规划
状态压缩的动态规划
最长不下降子序列
最长公共子序列和最长公共子串
动态规划的优化（快速幂，改变状态，优化转移，单调性，四边形不等式）

【贪心】
也有一些经典的模型，如取线段的问题，一般从小规模数据找规律，再适当的有一些证明。

【排序】
选择排序、冒泡排序
快速排序（快排）、堆排序
插入排序
希尔排序
归并排序

【分治】
二分查找
二分答案（这个好像不是分治）

【串】
串的基本操作
Kmp（字串匹配）
Kmp扩展
AC自动机

【数论】
欧几里得算法，最大公约数和最小公倍数
判断质数（sqrt式与筛法求素数）
进制转换

同余定理
中国剩余定理
概率与期望
欧拉函数

【几何】
线段相交
凸包（水平序和极角序）
半平面交

【有序表】
顺序表、链表、块状链表
线段树及其基本操作
树状数组
平衡树（sbt、treap、splay）
后缀数组

【其他】
Hash
随机化算法
矩形切割（与线段树的比较）
Lca（最近公共祖先）与rmq（区间最值）
高斯消元