Doraemonzzz

这次回顾第三周的算法。 课程地址：https://www.coursera.org/specializations/algorithms Quick Sortimport numpy as np def Exchange(A, i, j): #交换元素的值 p = A[i] A[i] = A[j] A[j] = p def Partion(A, l, r): p = A[l] i = l + 1 for j in range(l + 1, r + 1): if (A[j] < p): Exchange(A, i, j) i += 1 Exchange(A, l, i - 1) return i - 1 def Quick_Sort(A, l, r): n = r - l + 1 if (n <= 1): return #返回pivot的位置 i = Parti ...

课程主页：https://see.stanford.edu/Course/EE364A 这次回顾凸优化第七，第八讲，这部分介绍了凸优化问题以及对偶性。 Lecture 7 Convex optimization problems广义不等式约束考虑广义不等式约束下的凸问题： \begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \preceq_{K_{i} } 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array} f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}为凸函数；$f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}^{k_{i} }$关于正规锥$K_i$凸 锥形式问题：目标函数和约束为仿射函数的特殊情形 \begin{array}{cl}{\operatorname{minimize} } & {c^{T} ...

课程主页：https://see.stanford.edu/Course/EE364A 这次回顾凸优化第五，第六讲，这部分介绍了凸优化问题。 Lecture 5 and Lecture 6 Convex optimization problems优化问题的标准形式 \begin{array}{cl}{ {\operatorname{minimize} } } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=0, \quad i=1, \ldots, p}\end{array} $x \in \mathbf{R}^{n}$为优化变量 $f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$为目标或损失函数 $f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}, i=1, \dots, m$，为不等式约束 $h_{i} : \mathbf{R}^{n} \rig ...

这次回顾第二周的算法。 课程地址：https://www.coursera.org/specializations/algorithms Closest Pairimport numpy as np import functools import time #生成测试数据 def generate(n): return np.random.randn(n, 2) #比较函数 def cmp1(a, b): return a[0] - b[0] def cmp2(a, b): return a[1] - b[1] #距离函数 def dist(a, b): return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 #直接解法 def Closest_Pair_bf(data): n = len(data) d_min = 1e9 p = [] q = [] for i in range(n): for j in range(i + 1, n): ...

这个系列的课程之前学过一遍，但是笔记没有整理完，最近在复习，准备把内容再学习一遍，这次准备实现每周所介绍的全部算法，这里是第一周的内容。 课程地址：https://www.coursera.org/specializations/algorithms Karatsuba Mulplicationimport numpy as np def Karatsuba_Mulplication(x, y): ''' 输入x, y为字符串，首先补0，使得数字长度一样 ''' #预处理，使得长度一样 n1 = len(x) n2 = len(y) n = max(n1, n2) if (n1 < n2): x = "0" * (n2 - n1) + x else: y = "0" * (n1 - n2) + y #个位数 if (n == 1): return int(x) * int(y) else: k = n // ...

课程主页：https://see.stanford.edu/Course/EE263 这次回顾EE263作业9。 14.16(a)注意到 (A^TA)_{ii}= \sum_{k=1}^n A_{ki}^2所以 \begin{aligned} \operatorname{Tr} A^{T} A &= \sum_{i=1}^n \sum_{k=1}^n A_{ki}^2\\ &=\sum_{i, j}\left|A_{i j}\right|^{2} \end{aligned}因此 \|A\|_{\mathrm{F}}=\left(\sum_{i, j}\left|A_{i j}\right|^{2}\right)^{1 / 2}(b) \begin{aligned} \operatorname{Tr} \left((UA)^{T} (UA) \right) &=\operatorname{Tr} \left(A^T U^T UA \right)\\ &=\operatorname{Tr} \left(A^TA \right)\\ \operatorname{Tr} \lef ...

最近开始学习Coursera上普林斯顿的算法分析课程，后续会记录下学习过程，这次是第一周的内容。 课程主页：https://www.coursera.org/learn/analysis-of-algorithms Exercise1.14Follow through the steps given for quicksort to solve the recurrence: A_{N}=1+\frac{2}{N} \sum_{1 \leq j \leq N} A_{j-1} \quad \text { for } \quad N>0解：两边乘以$N$可得 \begin{aligned} N A_N &=N +2 \sum_{1 \leq j \leq N} A_{j-1}\\ (N-1) A_{N-1} & =N-1 +2 \sum_{1 \leq j \leq N -1} A_{j-1} \end{aligned}相减可得 \begin{aligned} N A_N- (N-1) A_{N-1} &= 1 +2 A_{N-1}\\ NA_N -(N+1) A_{N-1} ...

课程主页：https://see.stanford.edu/Course/EE364A 这次回顾凸优化Homework 2。 2.28利用顺序主子式即可。 一阶： x_1 \ge 0二阶： \begin{aligned} x_1 &\ge 0 \\ x_1 x_3 &\ge x_2^2 \end{aligned}三阶： \begin{aligned} x_1 &\ge 0\\ x_1 x_4 &\ge x_2^2 \\ x_1 x_4x_6 + 2x_2 x_3 x_5&\ge x_1x_5^2 +x_6x_2^2+x_4x_3^2 \end{aligned}2.33(a)凸： $\forall x^{(1)}, x^{(2)}\in K_{\mathrm{m}+}, \theta\in [0, 1]$，对于$i > j$，我们有 \begin{aligned} \left(\theta x^{(1)} + (1-\theta)x^{(2)}\right)_i &= \theta x^{(1)}_i+(1-\theta)x^{(2)}_i\\ &\ge \theta ...

课程主页：https://see.stanford.edu/Course/EE364A 这次回顾凸优化Homework 1。 2.1关于$k$做数学归纳法，$k=2$时结论显然。假设$k=n$时结论成立，下证$k=n+1$时候结论成立。 此时的条件为 \sum_{i=1}^{n+1}\theta_i =1总能找到$\theta_i \neq 1$，不妨设为$\theta_{i+1}$，那么 \begin{aligned} \sum_{i=1}^{n}\theta_i &=1 -\theta_{n+1} \\ \sum_{i=1}^{n}\frac{\theta_i}{1-\theta_{n+1}} &=1 \end{aligned}所以 \begin{aligned} \sum_{i=1}^{n+1} \theta_i x_i &= \sum_{i=1}^{n} \theta_i x_i + \theta_{n+1} x_{n+1}\\ &= (1-\theta_{n+1}) \left(\sum_{i=1}^{n}\frac{\theta_i}{1-\theta_{n+1}} ...

课程主页：https://see.stanford.edu/Course/EE261 这次回顾Problem Set 9。 Problem 1 \begin{aligned} \mathcal F g(x,y) &=\mathcal F \left(\Pi(x) \Pi(y) \right) \mathcal F \left(\Pi(x) \Pi(y) \right)\\ &= \mathcal F^2 (\Pi(x))\mathcal F^2 (\Pi(y))\\ &=\text{sinc}^2(\xi)\text{ sinc}^2(\eta)\\ &=\mathcal F(\Lambda(x)\Lambda(y)) \end{aligned}取逆变换可得 g(x,y) = \Lambda(x)\Lambda(y)Problem 2注意汉高变换为 G(\rho)=2 \pi \int_{0}^{\infty} g(r) J_{0}(2 \pi r \rho) r d r考虑$g(ar)$的汉高变换 \begin{aligned} 2 \pi \int_{0}^{\infty} ...

课程主页：https://see.stanford.edu/Course/EE261 这次回顾Problem Set 8。 Problem 1根据对称性，虚部应该为$0$。 Problem 2后续记线性系统为$L$ (a) \begin{aligned} L(\alpha v(t) +\beta u (t)) &= (\alpha v(t) +\beta u (t))\cos(\omega t) \\ &=\alpha v(t)\cos(\omega t) +\beta u(t)\cos(\omega t) \\ &=\alpha L (v(t))+\beta L(u(t))\\ L(v(t-\tau))&= v(t-\tau) \cos(\omega t) \\ &\neq v(t-\tau) \cos(\omega (t-\tau)) \end{aligned}所以该系统是线性系统，但不是时不变的。 (b) \begin{aligned} L(\alpha v(t) +\beta u (t)) &= \sin (\alpha v(t) +\beta u (t)) \\ ...

课程主页：https://see.stanford.edu/Course/EE261 这次回顾Problem Set 7。 Problem 1(a) \begin{aligned} \underline{\mathcal{F} }\left(\tau_{p} \mathrm{f}\right)[m] &= \sum_{k=0}^{N-1} \tau_{p} \mathrm{f}[k] w^{-k m}\\ &= \sum_{k=0}^{N-1} \mathrm{f}[k-p]w^{-k m}\\ &=w^{-pm} \sum_{k=0}^{N-1} \mathrm{f}[k-p]w^{-(k-p) m}\\ &= w^{-pm} \underline{\mathcal{F} } \mathrm{f}[m]\\ &= (\underline{\omega}^{-p} \underline{\mathcal{F} } \mathrm{f})[m] \end{aligned}所以 \underline{\mathcal{F} }\left(\tau_{p} \mathrm{f}\rig ...