算法与复杂性-CS2308

参考资料来源：
http://basics.sjtu.edu.cn/~chen/teaching/ALGO23/
https://chat.openai.com/chat

前言：

独自理解英文非常痛苦，在很多方面请求了茶老师的帮助。
茶老师虽然经常犯错和道歉，但是知识还是比我渊博得多（）
不过，也难免在我的记录中保留了一些茶老师的错（这样你才知道我问的是茶老师）（故意地）。在笔记中，一般来说，中文的段落由我和茶老师总结，英文则来源于陈老师的PPT。

陈老师的ppt和课程安排非常完善，茶老师也在此基础上帮上了我很多，真的非常非常感谢。

Slides01

Basic arithmetic

decimal representation / binary representation
- shares complexity of computing

Slides02

Modular arithmetic

original Euclid’s algorithm

将两个输入的非负整数记为a和b，其中a大于等于b。
用b除以a，得到商q和余数r。即，b = aq + r。
如果余数r为0，则a是最大公约数，算法结束。
如果余数r不为0，则用原来的除数a替换被除数b，用余数r替换除数a。然后重复步骤2。
这个过程一直持续到余数为0为止。最终，最后一次非零余数即为最大公约数。

gcd(a,b) (greatest common divisor)

based on gcd(a,b) == gcd(a,a - b)

extended Euclid’s algorithm

除了计算最大公约数外，它还可以找到满足贝祖等式（Bézout’s identity）的两个整数x和y。贝祖等式是一个方程，形式为ax + by = gcd(a, b)

输入两个整数a和b，其中a大于等于b。
用原始欧几里得算法计算a和b的最大公约数gcd(a, b)。
在计算的过程中，记录每一步的商和余数。
从最后一步开始，用递归的方式向上计算x和y的值。
- 基本情况：最后一步的余数为0，此时x = 1，y = 0。
- 递归情况：根据贝祖等式，使用下一步的x和y计算当前步的x和y，直到回到第一步。
返回x和y作为结果。

Modular division theorem For any a mod N, a has a multiplicative inverse modulo N if and only if it is relatively prime to N (i.e., gcd(a; N) = 1).
When this inverse exists, it can be found in time O(n3) by running the extended Euclid algorithm.

Example
We wish to compute 11-1 mod 25:
Using the extended Euclid algorithm,
we find 15 · 25 - 34 · 11 = 1, thus -34 · 11 ≡ 1 mod 25 and -34 ≡ 16 mod 25.
This resolves the issue of modular division: when working modulo N, we can divide by numbers relatively prime to N. And to actually carry out the division, we multiply by the inverse.

Modular inverse

We say x is the multiplicative inverse of a modulo N if ax ≡ 1 mod N.

Slides03

Primality Test

Fermat’s little theorem

If p is prime, them for every $1\le a<p$
$a^{p-1} \equiv 1(\bmod p)$

RSA

encryption() & decryption() （信息的加密和解密）

Private-key scheme

one-time pad

内容

- 约定一串等长字符
- 按位异或
- e(e(x)) = (x ⊕ r) ⊕ r = x ⊕ (r ⊕ r) = x ⊕ 0 = x

Attention

random R
- costly
reused insecure
- x ⊕ z

The Rivest-Shamir-Adelman (RSA) cryptosystem

RSA是一种公钥密码系统，RSA算法基于数学上的大质数分解问题和模幂运算的原理。
为了确保RSA的安全性，公钥 (Public Key, PK) 和私钥 (Secret Key, SK) 必须使用足够长的密钥长度，通常为2048位或更长。

在RSA中，每个用户都有一对密钥，即公钥(N,e)和私钥(N,d)。公钥是公开的。
加密：A使用B的公钥来加密消息以发送给B
解密：B使用自己的私钥来解密加密的消息

主要数学原理

选择两个大质数p和q，取N = p * q。
根据欧拉函数 φ(N) = (p-1) (q-1) 计算与φ(N)*互质的整数e，e称为公钥。
(e常常取3，有较高的计算效率)
用扩展欧几里得算法计算 私钥d ，使得 d * e ≡ 1 (mod φ(N))。(也就是求逆元d)
将N和e组成公钥，将N和d组成私钥。
对于要加密的明文M，使用公钥进行加密，即计算出密文C = M^e (mod N)。
对于接收到的密文C，使用私钥进行解密，即计算出明文M = C^d (mod N)。

RSA算法的安全性基于质因数分解问题。因为要破解RSA加密算法，需要对N进行质因数分解，即找出p和q。
但对于足够长的p和q，质因数分解是非常困难的。目前最好的算法也需要耗费大量的时间和计算资源。因此，使用足够长的密钥长度可以保证RSA算法的安全性。

关于算法

扩展欧几里得算法
*扩展欧几里得算法可以求出两个整数a和b的最大公约数gcd(a, b)，以及它们的一组整数解x和y，满足ax + by = gcd(a, b)。求得一组整数解x和y后，x即为a关于模n的逆元a^-1。
模幂算法
- 在RSA解密过程中，模幂运算是非常重要的一步。解密过程中需要计算密文C的d次方模N的结果，即计算 $C^d \bmod N$。
- 通常使用快速幂算法（也称为模重复平方法）来计算模幂。
- 快速幂算法的基本思想是将指数d表示为二进制形式，然后按位计算幂的乘积，遇到1就将底数乘到当前的幂中，遇到0则将幂平方。

一个简单例子

A想要制作一对钥匙！他选择了5和11。

在RSA中，选取p=5和q=11，那么N=p*q=55，φ(N)=(p-1)*(q-1)=40。
选取e=3，即gcd(e, φ(N))=1。3与40互质，e=3是合法的选择。

接下来计算私钥d，即试满足d*e ≡ 1 (mod φ(N))。
根据扩展欧几里得算法，可以得到一组整数解x和y，使得xe + yφ(N) = gcd(e, φ(N))。
将e=3和φ(N)=40代入上式，可以得到x_3 + y_40 = gcd(3, 40) = 1。

通过扩展欧几里得算法求解x和y的过程，可以得到x=-13，y=1。
由于xe + yφ(N) = 1，所以x*e ≡ 1 (mod φ(N))。
因此，私钥d=-13 mod 40 = 27。
所以，公钥为(N, e)=(55, 3)，私钥为(N, d)=(55, 27)。

B想要给A发送信息！他想发送9。

假设B要向A发送数字9。首先，B需要使用A的公钥对数字9进行加密。具体步骤如下：

将数字9转换成二进制形式，得到1001。

使用A的公钥(N, e)=(55, 3)进行加密，计算出密文C=9^3 mod 55=34。

将密文34发送给A。

A接收到了B的信息准备解密

A使用自己的私钥对密文进行解密。

使用A的私钥(N, d)=(55, 27)进行解密，计算出明文$M=14^{27}\bmod 55=9$。

将解密得到的明文9转换成十进制形式，得到原始的数字9。

（乐得，茶老师竟然觉得模运算算出来结果是34，我指出来它就疯狂道歉（（（茶老师啊——

Divide-and-Conquer Algorithms

分而治之

Multiplication

Karatsuba

// Input: positive integers x and y, in binary
// Output: their product

n = max(size of x, size of y) rounded as a power of 2.

if n = 1 then return xy.

xL; xR = leftmost n=2, rightmost n=2 bits of x

yL; yR = leftmost n=2, rightmost n=2 bits of y

P1 = multiply(xL; yL)

P2 = multiply(xR; yR)

P3 = multiply(xL + xR; yL + yR)

return P1 × 2n + (P3 - P1 - P2) × 2n=2 + P2.

茶老师的翻译如下：

计算输入数字 x 和 y 的长度，并选择最大长度 n，使其成为2的幂。

如果 n=1，则直接返回 xy。

将 x 和 y 分别分成两个长度为 n/2 的数字 xL,xR 和 yL,yR。

递归地计算 P1 = xL × yL，P2 = xR × yR 和 P3 = (xL + xR) × (yL + yR)。

将 P1 × 2n + (P3 − P1 − P2) × 2n/2 + P2 作为结果返回。

步骤3-4是递归的核心部分，将原问题分解成较小的子问题。
步骤5是组合的关键，将子问题的解组合成整个问题的解。

整个算法的时间复杂度为 $O(n log n)$ ，比传统的乘法算法的时间复杂度 $O(n^2)$ 更为优秀。然而，由于 Karatsuba 算法的常数较大，当 n 较小时，传统的乘法算法可能更快。

具体分析该算法的时间效能？

$T(n) = 3T(n=2) + O(n)$
The algorithm’s recursive calls form a tree structure (The height of the tree is log2 n) .

At the very top level, when $k = 0$, we need $O(n)$.
At the bottom, when $k = log_2(n)$, it is $O(3^{log_2(n)}) = O(n^{log_2(3)}) \approx O(n^{1.59})$

Recurrence relations

主定理（Master Theorem）是计算分治算法时间复杂度的一种常用方法，通常用于解决具有递归形式的算法问题。

主定理给出了递归式 $T(n)=aT(n/b)+f(n)$ 的渐近解，其中 $a\geq1$，$b>1$，$f(n)$ 是一个渐进正的函数，$T(n)$ 表示问题规模为 $n$ 时算法的时间复杂度。

主定理的一般形式如下：
若 $f(n)=O(n^{\log_b a-\epsilon})$，其中 $\epsilon>0$，则 $T(n)=\Theta(n^{\log_b a})$。
若 $f(n)=\Theta(n^{\log_b a})$，则 $T(n)=\Theta(n^{\log_b a}\log n)$。
若 $f(n)=\Omega(n^{\log_b a+\epsilon})$，其中 $\epsilon>0$，且对某个常数 $c<1$，有 $af(n/b)\leq cf(n)$，则 $T(n)=\Theta(f(n))$。

Slides 10

最小覆盖

This is the set cover problem. For each town x, let Sx be the set of towns within 30 miles of it. A school at x will essentially “cover” these other towns. How many sets Sx must be picked in order to cover all the towns in the county?

Input: A set of elements B, sets S1, . . . , Sm ⊆ B
Output: A selection of the S- whose union is B.
Cost: Number of sets picked.

A greedy solution

Repeat until all elements of B are covered: Pick the set S- with the largest number of uncovered elements.

-> optimal = $k$, greedy <= $klnn$
proof:
$n_{t+1}<=n_t-n_t/k$
$n_t<=n_t(1-1/k)^t$

Dynamic programming

Directed acyclic graphs

可线性化图

Solution

initialize all dist(·) values to ∞
dist(s) = 0 for each v ∈ V \ {s}, in linearized order do
dist(v) = min(u,v)∈E {dist(u) + (u, v)}

This algorithm is solving a collection of subproblems, {dist(u) | u ∈ V}

先修课排课

Longest increasing subsequences

for j = 1 to n do
L(j) = 1 + max {L(i) | (i, j) ∈ E}
return max L(j)

L(j) is the length of the longest path – the longest increasing subsequence – ending at j plus 1.

Any path to node j must pass through one of its predecessors, and therefore L(j) is 1 plus the maximum L(·) value of these predecessors.

If there are no edges into j, we take the maximum over the empty set, i.e., zero.
The final answer is the largest L(j), since any ending position is allowed.

核心为问题分解

Edit distance

字符串最小差

for - = 0 to m 
	E(i, 0) = - 
for j = 1 to n 
	E(0, j) = j 
for - = 1 to m 
	for j = 1 to n 
		 E(i, j) = min(1 + E(- − 1, j), 1 + E(i, j − 1), diff(i, j) + E(- − 1, j − 1) )
return E(m, n)

The over running time is O(m · n).

Slides11

Linear programming

LP function

Interger linear programming!
-> an important but very hard problem

variants of lp

turn max to min -> $\times -1$
turn inequality to equation -> $…+s = b, s >= 0$
turn equality to inequality -> $ax = b$ -> $ax <= b$ and $ax >= b$
x is unrestricted -> x+, x- >= 0, replace x by x+-x-

standartd form

We can reduce any LP (maximization or minimization, with both inequalities and equations, and with both nonnegative and unrestricted variables) into an

the variables are all nonnegative,
the constraints are all equations,
the objective function is to be minimized

Flows in networks

Capture the flow-increasing chances in:

$c{uv} - f{uv}, \,if (u,v) \in E\,and\,f{uv} < c{uv}$
$f{vu}, \,if (v,u) \in E\,and\,f{uv} > 0$
It proceeds in iterations, each time explicitly constructing $G_f$, finding a suitable s-t path in $G_f$ by using, say, a linear-time breadth-first search, and halting if there is no longer any such path along which flow can be increased.

就实现而言，相当于每次操作为：

找到一条s-t路径
取该路径的最大流量f
对该路径的每条边，更新管道流量为c-f，并为该边的反向边+f（如果不存在，则创建）
直到出现可划分含s点的部分没有指向另一部分的边

Bipartite matching

This matchmaking game can be reduced to the maximum-flow problem, and thereby to linear programming!

Create a new source node s with outgoing edges to all the boys;
a new sink node t with incoming edges from all the girls;
and direct all the edges in the original bipartite graph from boy to girl.
Finally, give every edge a capacity of 1

Duality

Zero-sum games

$\max {\mathrm{x}} \min {\mathrm{y}} \sum{i, j} G{i j} x{i} y{j}=\min {\mathbf{y}} \max {\mathrm{x}} \sum{i, j} G{i j} x{i} y{j}$

The best each player can do is to play completely randomly, with an expected payoff of zero.

if both play optimally, then it doesn’t hurt a player to announce his or her strategy in advance

Slides12

Simplex algorithm

基本思想：在不同的相邻交点间移动
（线性规划的顶点定理：最值在交点和线段上取得）

从一个基本可行解开始，通过交替移动基变量和非基变量来逐步逼近最优解。每次移动的过程被称为一次迭代。
在每次迭代中，选择一个非基变量作为入基变量，同时选择一个基变量作为出基变量。

通过一系列计算，得到一个新的基本可行解。

时间复杂度：At most (m+n)Cn ，其中n指n维向量空间，m指m个不等式约束

Postscript: circuit evaluation

利用LP快速计算逻辑网

Slide 13

NP-Complete problems

We will show that for some problems efficient algorithms are unlikely to exist
Algorithms will be used to transform one problem to another （==reductions==）.

Search problems

The quest for efficient algorithms is about finding clever ways to bypass exhaustive search.