高级最优化

先修条件：线性代数，最优化/运筹，基础的概率论，MATLAB使用（如何建模与使用）

优化分类

1，确定性优化：

Linear Optimization线性规划，Second order cone programming 二阶椎优化，Semidefinite programming （SDP半定优化）

背景

大数据背景的几个特点：量大large scale，实时性动态产生数据，结构化/半结构化数据，可信赖程度低（Noise，考虑模型如何更robust），高维度且稀疏的数据集。

这里主要说高维稀疏数据带来的一些问题：

$x=\left(x_{1}, x_{2}, \cdots, x_{p}\right)$, 特征是p维，数据样例有n个，即整个dataset是 n × p ，传统的统计方法适用于一些 n > p 的情况，但是当 n << p的时候，数据量小，但想要求的参数又很多的时候就有困难了。

组合优化问题

问题引入

车辆路径规划问题，n位客户，在不同地点，有需求。在中央仓库有m辆车辆的均质车队。这是一个NP难问题，这类问题中，启发式和元启发式是实践中最常用的VRP解决方案。

启发式算法：模拟退火，遗传算法，蚁群优化算法等。

NP难问题的一些解决方法

1，精确方法（枚举，约束编程，分支定界，分支与剪切）是非多项式的，通常可以处理一定规模的问题实例（如旅行商问题TSP的80000节点）。

树结构

TreeNode结构：

1
2
3
4
5
6

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL) {}
};

CauseInfer的系统概述与工作流

概述

两层因果关系图：将诊断问题公式化为根因推断问题。为了推断服务和系统指标之间的根本原因，我们将运行中的分布式系统映射到两层分层的因果关系图 two layered hierarchical causality graph。 因果关系图中的每个有向边代表直接的“因果关系”关系。“因果关系cause effect”的合理基础是 原因指标cause metric的变化会导致影响指标effect metric的变化。

ABS & Intro

云系统背景

许多组件，复杂交互：cloud-based and cloud-centric systems always consist of a mass of components running in large distributed environments with complicated interactions.

SSH远程

1，在mac上用parallels desktop开启一个Ubuntu16的虚拟机。

注意设置里换源，中国区的快些。

然后进行更新 (sudo apt-get update , 然后sudo apt-get upgrade)

然后安装ssh（sudo apt-get install openssh-server）。

基础

虚拟化技术

Hadoop

hadoop是一个开源框架，允许使用简单的编程模型在跨计算机集群的分布式环境中存储和处理大数据。

HDFS

分布式文件系统，是一个高度容错性的系统（每个数据块都复制到多个节点），可以提供高吞吐量的数据访问（T级别，多个节点同时处理数据）。

文件分块存储，HDFS将一个完整的大文件平均分块存储到不同的计算器上，多主机读取比单主机读取效率更高。代码向数据迁移，尽量地将任务分配到离数据最近的机器上运行。

分治递归思想

为了解决一个给定的问题，算法一次或多次递归的调用自身以解决若干子问题，上层函数调用子函数需要等子函数运行完，这些就是典型的分治法的思想。我们将原问题分解为几个规模较小但类似于原问题的子问题，从而递归的调用自身，最后合并这些子问题的解来建立原问题的解。

关键：1，递：分解原问题为相同结构的子问题。2，解决这些子问题。3，归：合并子问题的解。

链表

用指针来实现线性表，链表是动态的。

1
2
3
4
5

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL) {}
};