斯坦福算法专项课程Course1 week2算法实现
这次回顾第二周的算法。
课程地址: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):
...
斯坦福算法专项课程Course1 week1算法实现
这个系列的课程之前学过一遍,但是笔记没有整理完,最近在复习,准备把内容再学习一遍,这次准备实现每周所介绍的全部算法,这里是第一周的内容。
课程地址: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 // ...
EE263 Homework 9
课程主页: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 ...
Analysis of Algorithms Week 1
最近开始学习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} ...
EE364A Homework 2
课程主页: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 ...
EE364A Homework 1
课程主页: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}} ...
EE261 Problem Set 9
课程主页: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} ...
EE261 Problem Set 8
课程主页: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)) \\
...
EE261 Problem Set 7
课程主页: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 ...
EE364A Lecture 1 and Lecture 2
课程主页:https://see.stanford.edu/Course/EE364A
最近开始学习凸优化,公开课为斯坦福的凸优化公开课,主页如下。这次回顾凸优化第一第二讲,这部分介绍了凸集的概念。
Lecture 1 Introduction主要介绍凸优化的历史和应用,这里从略。
Lecture 2 Convex sets仿射集穿过$x_1,x_2$的直线可以表示为
x=\theta x_{1}+(1-\theta) x_{2} \quad(\theta \in \mathbf{R})仿射集:包含过集合中任意两点的直线的集合。
例子:
\{x | A x=b\}凸集过$x_1, x_2$的线段可以表示为
x=\theta x_{1}+(1-\theta) x_{2}其中$0\le \theta \le 1$
凸集:包含过集合中任意两点的线段的集合,即
x_{1}, x_{2} \in C, \quad 0 \leq \theta \leq 1 \quad \Longrightarrow \quad \theta x_{1}+(1-\theta) x_{2} \in C凸组合 ...
EE261 Lecture 30
课程主页:https://see.stanford.edu/Course/EE261
这次回顾第三十讲,这一讲介绍了二维傅里叶变换的应用以及拉东变换。
I=I_{0} \exp \left(-\int_{L} \mu\left(x_{1}, x_{2}\right) d s\right)考虑X光的问题,公式如上。$I_0$为初始强度,$I$为测量强度,$L$为线段,现在的任务是已知$I$,如何恢复$\mu(x_1, x_2)$,从上式中可以看出,实际我们的任务是已知如下线积分,然后恢复原函数。
\int_{L} \mu\left(x_{1}, x_{2}\right) d s拉东变换由于要计算线积分,这里首先讨论直线的表示方法,如下图所示,直线可以由角度$\phi$以及有向距离$\rho$表示。
当$\phi $固定,$\rho $变动时表示的是一族平行线;当$\rho $固定,$\phi$变动时表示的过原点的切线。
该坐标系和直角坐标系的变换关系为:
\rho=\mathrm{x} \cdot \mathrm{n}=\left(x_{1}, x_{2}\right) \cd ...
EE263 Lecture 20 Observability and state estimation
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第十九讲,这一讲结束了可控性和状态转移,介绍了可观测性和状态观测。
无限时间的最小能量矩阵
P=\lim _{t \rightarrow \infty}\left(\int_{0}^{t} e^{\tau A} B B^{T} e^{\tau A^{T}} d \tau\right)^{-1}总存在,并且给出了到达$x_{\mathrm{des}}$所需最小能量(对$t$没有约束的情形下)
\min \left\{\int_{0}^{t}\|u(\tau)\|^{2} d \tau | x(0)=0, x(t)=x_{\mathrm{des}}\right\}=x_{\mathrm{des}}^{T} P x_{\mathrm{des}}
如果$A$稳定,那么$P>0$(即,无法免费到达任何地方)
如果$A$不稳定,那么$P$可能有非平凡零空间
$Pz=0,z\neq 0$说明可以用能量为任意小的$u$到达$z$
一般的状态转移考虑将将$x\left(t_{i}\right)$转 ...