From Nand to Tetris week 10
这次回顾第十章的内容,这一章介绍了编译器的第一部分:语法分析。
课程官网:
https://www.nand2tetris.org/
视频地址:
https://www.coursera.org/learn/build-a-computer
Part 1:课程回顾背景介绍这一章完成了编译器的前半部分:语法分析,输出结果为XML格式,本章重点依然为项目,背景介绍部分从略。
Part 2:项目项目的注意点可以参考PPT的83,110,125页,分为JackTokenizer,CompilationEngine,JackAnalyzer。
JackTokenizerclass JackTokenizer():
Keyword = {'class', 'constructor', 'function', 'method',
'field', 'static', 'var', 'int', 'char',
'boolean', 'void', 'true', 'false', 'null',
...
From Nand to Tetris week 9
这次回顾第九章的内容,这一章介绍了Jack编程语言。
课程官网:
https://www.nand2tetris.org/
视频地址:
https://www.coursera.org/learn/build-a-computer
Part 1:课程回顾背景介绍这章介绍了Jack语言,项目为利用Jack语言写一个app,背景介绍部分从略。
Part 2:项目这部分编写了Breakout游戏,截图如下:
该程序的构成如下:
Ball/** BALL */
class Ball{
// screen location of the ball's center
field int x, y;
// radius of the ball
field int r;
// x direction of the ball, 0 means right, 1 means left
field int directionx;
// y direction of t ...
EE263 Homework 8
课程主页:https://see.stanford.edu/Course/EE263
这次回顾EE263作业8。
13.17(a)$z^{-1}$的作用为延迟算子,所以
A=\left[\begin{array}{cccc}{0} & {\cdots} & {} & {} \\ {1} & {0} & {\cdots} & {} \\ {0} & {1} & {0} & {\cdots} & {} \\ {} & {} & {\ddots} & {} \\ {0} & {\cdots} & {0} & {1} & {0}\end{array}\right], \quad B=\left[\begin{array}{c}{1} \\ {0} \\ {\vdots} \\ {0}\end{array}\right], \quad C=\left[\begin{array}{ccc}{0} & {\cdots} & {0} & {1}\end{array}\right], \quad D=0(b)$A$的特征值全为$0$
(c)
A=
\left[\begin{matrix}{0} & ...
EE263 Lecture 18 SVD Applications
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第十八讲,这一讲介绍了SVD的应用。
线性方程组对于数据误差的敏感度考虑$y=A x$,$A \in \mathbb{R}^{n \times n}$可逆;所以$x=A^{-1} y$
假设$y$有误差或噪声,即$y$变成$y+\delta y$
那么$x$变成$x+\delta x$,其中$\delta x=A^{-1} \delta y$
因此我们有
\|\delta x\|=\left\|A^{-1} \delta y\right\| \le\left\|A^{-1}\right\|\|\delta y\|如果$\left|A^{-1}\right|$很大,
$y$的小误差会产生$x$的大误差
给定$y$,无法求解出很小误差的$x$
因此,在实际中可以认为$A$是奇异的
更精细的分析使用$x,y$的相对误差而不是绝对误差
因为$y=Ax$,我们有$|y| \leq|A||x|$,因此
\frac{\|\delta x\|}{\|x\|} \le
\left\|A^{-1}\ri ...
EE263 Lecture 17 Symmetric matrices, quadratic forms, matrix norm and SVD
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第十七讲,这一讲介绍了SVD。
奇异值分解矩阵增益的完全情形由$A$的SVD给出:
A=U \Sigma V^{T}其中
$A \in \mathbb{R}^{m \times n}, {\operatorname {Rank}}(A)=r$
$U \in \mathbb{R}^{m \times r}, U^{T} U=I$
$V \in \mathbb{R}^{n \times r}, V^{T} V=I$
$\Sigma=\operatorname{diag}\left(\sigma_{1}, \ldots, \sigma_{r}\right)$,其中$\sigma_{1} \geq \cdots \geq \sigma_{r}>0$
记
U=\left[u_{1} \cdots u_{r}\right], V=\left[v_{1} \cdots v_{r}\right]那么
A=U \Sigma V^{T}=\sum_{i=1}^{r} \sigma_{i} u_{ ...
EE261 Lecture 9
课程主页:https://see.stanford.edu/Course/EE261
这次回顾第九讲,这一讲介绍了卷积。
卷积傅里叶变可以解释为时域到频域的变换,给定函数$f(t)$和$g(t)$,我们希望在频域内得到
\mathcal{F} g(s) \mathcal{F} f(s)应该在时域内如何操作呢?这就引入了卷积的概念:
\begin{aligned}
\mathcal{F} g(s) \mathcal{F} f(s)
&=\int_{-\infty}^{\infty} e^{-2 \pi i s t} g(t) d t \int_{-\infty}^{\infty} e^{-2 \pi i s x} f(x) d x \\
&=\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-2 \pi i s t} e^{-2 \pi i s x} g(t) f(x) d t d x \\
&=\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-2 \pi i s(t+x)} ...
EE261 Lecture 7 and Lecture 8
课程主页:https://see.stanford.edu/Course/EE261
这次回顾第七讲和第八讲,这两讲介绍了傅里叶变换的性质。
对偶性注意到
\begin{aligned} \mathcal{F} f(-s) &=\int_{-\infty}^{\infty} e^{-2 \pi i(-s) t} f(t) d t=\int_{-\infty}^{\infty} e^{2 \pi i s t} f(t) d t=\mathcal{F}^{-1} f(s) \\ \mathcal{F}^{-1} f(-t) &=\int_{-\infty}^{\infty} e^{2 \pi i s(-t)} f(s) d s=\int_{-\infty}^{\infty} e^{-2 \pi i s t} f(s) d s=\mathcal{F} f(t) \end{aligned}所以
\begin{aligned} \mathcal{F} f(-s) &=\mathcal{F}^{-1} f(s) \\ \mathcal{F}^{-1} f(-t) &=\mathcal{F} ...
EE263 Homework 7
课程主页:https://see.stanford.edu/Course/EE263
这次回顾EE263作业7。
10.9(a)由行列式展开的特点,构成$s^n$的项为
\prod_{i=1}^n(s-a_{ii})所以$s^n$的系数为$1$。
(b)由行列式展开的特点,构成$s^{n-1}$的项为
\prod_{i=1}^n(s-a_{ii})所以$s^{n-1}$的系数为
-\sum_{i=1}^n a_{ii}=-\operatorname{Tr} A(c)常数项为$s=0$时的多项式的值,即
\mathcal{X}(0)=\operatorname{det}(-A)(d)第一个等式由定义即可,所以
\begin{aligned}
a_{n-1}&=-\sum_{i=1}^{n} \lambda_{i} \\
a_{0}&=\prod_{i=1}^{n}\left(-\lambda_{i}\right)
\end{aligned}10.11由条件可得
A=P^{-1}\Lambda P=\sum_{k=1}^n \lambda_k p_k q_k^T(a)
ran ...
EE263 Lecture 16 Symmetric matrices, quadratic forms, matrix norm and SVD
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第十六讲,这一讲继续介绍了对称矩阵的一些性质。
二次型如下形式的函数$f : \mathbb{R}^{n} \rightarrow \mathbb{R}$
f(x)=x^{T} A x=\sum_{i, j=1}^{n} A_{i j} x_{i} x_{j}被称为二次型。
在二次型中,我们可以假设$A=A^T$,因为
x^{T} A x=x^{T}\left(\left(A+A^{T}\right) / 2\right) x($\left(A+A^{T}\right) / 2$被称为$A$的对称部分)
唯一性:如果对任意$x \in \mathbb{R}^{n}$,$x^{T} A x=x^{T} B x$,并且$A=A^{T}, B=B^{T}$,那么$A=B$
证明:取$x=e_i$可得
\begin{aligned}
e_i^T Ae_i &= a_{ii}\\
e_i^TBe_i &= b_{ii}\\
a_{ii} &= b_{ii}
\end{aligned}取$x=e_ ...
EE261 Lecture 5 and Lecture 6
课程主页:https://see.stanford.edu/Course/EE261
这次回顾第五讲和第六讲,这两讲介绍了傅里叶变换。
傅里叶变换傅里叶变换是上一讲傅里叶序列的推广,可以处理非周期性的函数,其思路为,将非周期函数视为周期为无穷大。
现在考虑函数$f(t)$,假设当$|t| >\frac 1 2$时函数为$0$,将$f(t)$扩张为周期为$T$,其傅里叶系数为
c_{n}=\frac{1}{T} \int_{-T / 2}^{T / 2} e^{-2 \pi i n t / T} f(t) d t=\frac{1}{T} \int_{-1 / 2}^{1 / 2} e^{-2 \pi i n t / T} f(t) d t估计上述系数
\begin{aligned}
\left|c_{n}\right|
&=\frac{1}{T}\left|\int_{-1 / 2}^{1 / 2} e^{-2 \pi i n t / T} f(t) d t\right| \\
& \leq \frac{1}{T} \int_{-1 / 2}^{1 / 2}\left|e^{ ...
EE261 Lecture 4
课程主页:https://see.stanford.edu/Course/EE261
这次回顾第四讲,这一讲讨论傅里叶序列的应用。
热方程考虑热方程(通过变换将系数变为$\frac 12 $)
u_t=\frac{1}{2} u_{x x}假设
u(x+1, t)=u(x, t)将$u(x,t)$展开为傅里叶序列的形式得到
u(x, t)=\sum_{n=-\infty}^{\infty} c_{n}(t) e^{2 \pi i n x}其中
c_{n}(t)=\int_{0}^{1} e^{-2 \pi i n x} u(x, t) d x注意
\begin{aligned}
u_t
&=\sum_{n=-\infty}^{\infty} c_{n}'(t) e^{2 \pi i n x}\\
u_{xx}
&=\sum_{n=-\infty}^{\infty} c_{n}(t) e^{2 \pi i n x}(-4\pi^2 n^2)
\end{aligned}代入热方程得到
\sum_{n=-\infty}^{\infty} c_{n}'(t) e^{2 \pi ...
EE263 Homework 6
课程主页:https://see.stanford.edu/Course/EE263
这次回顾EE263作业6。
9.9(a)
\begin{aligned}
A&=1.2\gamma
\left[\begin{matrix}
0& {0.2} & {0.1} \\
{.05} & {0} & {.05} \\
{0.1} & {\frac 1{30}} & {0}
\end{matrix}\right]\\
b&=0.012\gamma \left[\begin{matrix}
1\\
2\\
3\\
\end{matrix}\right]
\end{aligned}递推
p(t+1)=Ap(t)+b得到
\begin{aligned}
p(t)&=A^tp(0)+\sum_{i=0}^{t-1} A^i b
\end{aligned}所以收敛情形和$A$的特征值有关。
当$\gamma =3$时,特征值的绝对值都小于$1$,所以无条件收敛;当$\gamma= 5$时,有一个特征值的绝对值大于$1$,所以可能会发散。
计算代码如下:
import numpy as np ...