0%

为专业课复习用

🌿分布式系统概念

🌿概念

一个分布式系统是若干个独立的计算机的集合,通过通信网络互相连接,实现资源共享和协同工作,但是对该系统的用户来说,感觉该系统就像一台计算机一样。

硬件方面:每台计算机都是独立、自主的

软件方面:用户感觉在独占系统

🌰应用举例

  • 万维网
  • 移动计算
  • 连锁店
  • 云计算

🌿从集中式系统到分布式系统的原因

  • 高性能微型计算机的普及
  • 高速计算机网络(LAN、WAN)的普及

🌿分布式系统的特点

优点

与集中式系统相比较

  1. 经济性

    微型处理机提供了比大型主机更好的性能价格比
  2. 性能

    分布式系统总的计算能力比单个大型主机更强
  3. 固有的分布性能

    一些应用涉及空间上分散的机器
  4. 可靠性

    多工系统的容错能力:如果一个机器崩溃,整个系统还可以运转
  5. 渐增(可扩充性强)

    计算能力可以逐渐有所增加

与独立PC机比较

  1. 支持数据共享
    • 文件
    • 数据库
  2. 支持设备共享
    • 高档打印机
    • 海量磁盘
  3. 增强人与人之间的沟通
    • Email
    • bbs
  4. 灵活性
    • 负载分配(在其他的机器上执行任务) |

存在的问题

  1. 缺乏充分的软件产品和应用经验

    操作系统、中间件、编程语言、工具
  2. 网络性能的限制

    QoS(带宽、速度)
  3. 安全性

    黑客、泄密、盗用、破坏

硬件概念

Flynn分类

按照指令流、数据流的个数

  • SISD
    • 单指令流、单数据流
    • PC机
  • SIMD
    • 单指令流、多数据流
    • 矩阵计算机
  • MISD
    • 多指令流、单数据流
    • 无🌰
  • MIMD
    • 多指令流、多数据流
    • 分布式系统

MIMD分类

存储器使用

  • 共享式 --- 多处理器系统
  • 私有式 --- 多计算机系统

连接方式

  • 总线式
  • 交换式

MIMD系统分类

  1. 总线型多处理机
  2. 交换型多处理机

    交叉开关线:n^2个交叉开关点
  3. 总线型多计算机
  4. 交换型多计算机

软件概念

分类

  • 紧耦合式
  • 松耦合式

系统

  • DOS 分布式操作系统
  • NOS 网络操作系统
  • Middleware中间件系统
    • 是一种独立的系统软件或服务程序,分布式应用软件借助这种软件在 不同的技术之间共享资源
    • 中间件位于操作系统之上,管理计算资 源和网络通信。

🌿分布式系统的结构模型

客户-服务器模型

分布式系统设计问题/目标

  1. 透明性(Transparency) :访问透明性、位置透明性等
  2. 开放性:系统能不能进行扩展和重新实现
  3. 可扩展性:规模、地域、管理可扩展性
  4. 可靠性:可用性、安全性、容错性

简介

动态规划,Dynamic Programming,简称DP。

特点

  • 最优子结构
  • 重叠子问题

解题一般思路

  1. 分解子问题:子问题与原问题相同/相似,只是缩小了规模,“大而化小,小而化了”。
  2. 确定状态:子问题各变量的一组取值
  3. 确定边界:初始状态,或者边界条件的取值
  4. 确定状态转移方程:递推的公式

关键是确定状态转移方程,在什么条件下进行什么状态的转换。

DP vs. 递归

  • 递归:自上而下,就会有重复的子问题
  • DP:自下而上,用空间换时间

🌰

  • 最长公共子序列LCS
  • 最长上升子序列

题目

首先从最简单的开始,通过斐波那契数列来感受重叠子问题

斐波那契数列

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N,计算 F(N)

显然,这个问题用递归求解很简单。

1
2
3
4
5
int fib(int N) {
if (N == 0) return 0;
if (N == 1) return 1;
return fib(N - 1) + fib(N - 2);
}

附上力扣的题目链接https://leetcode-cn.com/problems/fibonacci-number/

假设N=6,画出递归树,可以发现有很多重复的子问题,也就是在求解的过程中进行了重复计算,增加了时间的开销。

N为6的递归树
N为6的递归树

我们把重复计算的地方存下来,“用空间换时间”,避免重复的计算。

1
2
3
4
5
6
7
8
9
10
int fib(int n) {
int f[101];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; ++i) {
f[i] = f[i - 1] + f[i - 2];
f[i] = f[i] % (1000000007);
}
return f[n];
}

附上力扣题目链接https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

70. 爬楼梯

到达第n阶楼梯的方法数量 = 到达第n-1阶楼梯的方法总数 + 到达第n-2阶楼梯的方法总数 解释:最后一步可能走一个阶梯,也可能走两个阶梯 其实是一个斐波那契数列

  • 状态

d[i]表示达到第i阶的方法总数

  • 边界:

    d[0] = 1 实际上无这种情况,为递推定义的 d[1] = 1 n>=2时,进行状态转移

  • 状态转移方程:

d[n] = d[n - 1] + d[n - 2]

解题代码:

1
2
3
4
5
6
7
8
9
int climbStairs(int n){
int d[101];
d[0] = 1;
d[1] = 1;
for(int i = 2; i <= n; i++){
d[i] = d[i - 1] + d[i - 2];
}
return d[n];
}

746. 使用最小花费爬楼梯

  • 分析过程

对于每个阶梯,都有选和不选,两种情况。

假设求d[9],选择第9个阶梯,那么有两种情况:一是选择第7个阶梯,二是选择第8个阶梯。

...依次做下去。

使用最小花费爬楼梯的分析
使用最小花费爬楼梯的分析
  • 状态

d[i]代表到达i阶的最小花费,i=0i=1的情况下特别处理

  • 边界

    n<2的时候,取min(cost[0], cost[1]); d[0] = cost[0]; d[1] = cost[1];

  • 结果

求的是到达n的前1阶或前2阶的最小值,即min(d[costSize - 2], d[costSize - 1]);

  • 状态方程
1
d[i] = min(d[i - 2] + cost[i], d[i - 1] + cost[i]); // 当 i >=2 时
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//
// Created by Christy on 2020/7/25.
//
int min(int a, int b) {
return a < b ? a : b;
}

int minCostClimbingStairs(int *cost, int costSize) {
int *d = (int *) malloc(sizeof(int) * costSize);

if (costSize < 2) {
return min(cost[0], cost[1]);
}

d[0] = cost[0];
d[1] = cost[1]; // 这里不能写min(min(cost[0], cost[1]);

for (int i = 2; i < costSize; ++i) {
d[i] = min(d[i - 2] + cost[i], d[i - 1] + cost[i]);
}
return min(d[costSize - 2], d[costSize - 1]);
}

经典问题的状态转移方程

动态规划问题 - 经典模型的状态转移方程

力扣上的一个关于DP的总结

https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns#Decision-Making

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment