Intro

此系列为 18.06-Linear Algebra 2005 的学习总结
原视频地址 B站翻译版

概述

线性+代数,线性代数这门课成最直观的理解就是解线性方程.本节的核心就是从Row Picture和Column Picture 两个角度解方程.

线性方程组的集合解释

例如现在有如下方程组,两个未知数,两个方程式. 下面将从行与列两个视角给出方程式的集合解释

行图像

首先按行将方程式写成用矩阵形式:$
\left[
\begin{matrix}
2&-1\\
-1&2
\end{matrix}
\right]
\left[
\begin{matrix}
x\\
y
\end{matrix}
\right]
=
\left[
\begin{matrix}
0\\
3
\end{matrix}
\right]
$
等式左侧,左侧矩阵对应未知数的系数称为系数矩阵, x, y 对应未知数称为未知向量,等式右侧为线性变换的结果.亦可简写作$A\vec{x}=\vec{b}$的形式.其中:

系数矩阵(A):将方程组系数按行提取出来,构造完成的一个矩阵.
未知向量($\vec{x}$):将方程组的未知数提取出来,按列构成一个向量.
向量($\vec{b}$): 将等号右侧结果按列提取,构成一个向量.

和中学时代学过的东西一样,两个直线方程,观察它们交点的情况.在此个例中,两条直线交于一点,意味着此方程式有唯一解.

列图像

还是这个方程$
\bigg\{
\begin{aligned}
2x-y=0 \\
-x+2y=3
\end{aligned}
$
竖着观察矩阵,有如下等式.意味求使两向量的线性组合等于等式右侧向量的 x 和 y (在下图中记做了a和b).

滑动a,b不难发现,此例中的两向量可以构成任意方向的向量,布满整个二维空间.

集合解释的高维推广

以三维为例,有如下方程组

矩阵如下

行图像

如果绘制行图像,很明显这是一个三个平面相交得到一点,想直接看出这个点的性质并不容易.
可行的思路是先联立其中两个平面,使其相交于一条直线,再研究这条直线与平面相交于哪个点,最后得到点坐标即为方程的解.
这个求解过程对于三维来说或许还算合理,那四维呢?五维甚至更高维数呢?直观上很难直接绘制更高维数的图像,这种行图像受到的限制也越来越多.

列图像

使用列图像的思路进行计算,那矩阵形式就变为：
左侧是线性组合,右侧是合适的线性组合组成的结果,这样一来思路就清晰多了,”寻找线性组合”成为了解题关键.
不难看出,只需要取 x = 0, y = 0, z = 1 就可使线性组合成立,这在行图像之中并不明显.
当然,之所以推荐使用列图像求解方程, 是因为这是一种更系统的求解方法,即寻找线性组合,而不用绘制每个行方程的图像之后寻找那个很难看出来的点.

矩阵乘法

有矩阵$A_{m*n}$ 和 $B_{n*l}$, 则矩阵乘法$AB$的结果为一个$C_{m*l}$的矩阵.
矩阵C中的每一个元素可以视作矩阵A的某一行和B的某一列的点积(dot product),$C_{ij}=\text{ith row of A} · \text{jth column of B}$.
还有一种视角,可以将C中的每一列视作矩阵B中每个列向量和A的线性组合的结果.

Title

视频地址有B站机翻字幕和YouTube ,
课程地址在此:MIT 6.824: Distributed Systems (Spring 2020)

Windows 10下的Lab环境构建

Linux环境下的构建课程地址中就有详细介绍, 本节详细介绍构建Windows下的Linux环境(Windows Subsystem for Linux).
本节基本摘抄自此页, 有问题可以去获取更多信息.

开启 Windows Subsystem for Linux

以管理员权限运行PowerShell,执行下面的代码.

1

dism.exe /online /enable-feature /featurename:Microsoft-Windows-Subsystem-Linux /all /norestart

检查CPU架构及版本号

1
2
3
4
5

# 架构
systeminfo | find "System Type"
# 版本
[System.Environment]::OSVersion.Version

1
2
3
4
5
6
7
8
9

PS C:\WINDOWS\system32> [System.Environment]::OSVersion.Version

Major  Minor  Build  Revision
-----  -----  -----  --------
10     0      18362  0

PS C:\WINDOWS\system32> systeminfo | find "System Type"
System Type:               x64-based PC
PS C:\WINDOWS\system32>

对于x64架构: build版号18362或更高.
对于ARM64架构: build版号19041或更高.
版号18362以下的不支持WSL 2,请升级Windows或使用WSL 1.

使用WSL 1的可直接重启电脑后在微软商店下载distribution开始使用.

开启虚拟机特性

以管理员权限运行PowerShell,执行下面的代码. 执行后重启电脑.

1

dism.exe /online /enable-feature /featurename:VirtualMachinePlatform /all /norestart

下载并安装Linux内核更新包

x64
arm64

将WSL 2设置为默认

1

wsl --set-default-version 2

下载Linux CLI

打开微软商店,找个喜欢的Linux发行版装上,我装的是ubuntu. 安装后打开设置好用户名密码,就可以开始Lab之旅了. 别的发行版不知道,我下载的ubuntu没有gcc和make, 手动整上.

1
2

apt install gcc
apt install make

原文在此: How to Read a Paper

摘要

研究者们花费大量时间阅读研究文献,但很少被教导如何阅读,浪费了很多精力.
本文概述了一种实用而有效的三遍法并概述如何用该方法进行文献调查

引论

典型的研究人员每年可能要花费数百小时阅读论文。研究人员必须阅读论文有以下几个原因：

• 评审
• 跟上在其所在领域的步伐
• 探索新领域

高效阅读论文是至关重要但很少被传授的技能。因此，初学者必须在自学中反复尝试,艰苦付出却收效甚微并因此感到沮丧.

多年来我一直用三遍法来使自己免于细节的桎梏并保持对整体的掌握它可以让我估计审阅一组论文所需的时间。此外，我还可以根据自己的需要和时间调整阅读的深度。本文介绍了
方法及其在进行文献调查中的应用。

三遍法

核心思想是,你应该读三遍而非一遍从头读到尾.每一遍在前一遍的基础上达成一些特定的目的.第一遍你要领会论文的整体思想.第二遍你要掌握论文的关键内容而非细节.第三遍深度理解.

第一遍

第一遍是一次掌握文章脉络的速读.掌握文章脉络后你可以决定要不要继续细读.第一遍阅读大约花5-10分钟并包含如下步骤:

1. 仔细阅读标题,摘要,引论
2. 阅读每个大小章节的第一段并忽略其他内容
3. 浏览一下数学内容（如果有的话）以确定底层的理论基础
4. 读结论
5. 浏览参考文献并留意你阅读过的文章

在第一遍之后,你应该可以回答一下5个问题(5Cs):

1. 分类 Category: 这是一遍什么类型的论文? 实验报告? 对现有系统的分析? 对研究原形(research prototype)的阐述?
2. 关联性 Context: 它与哪些其他论文相关? 哪些基础理论应用在了这篇文章中?
3. 正确性 Correctness: 假设看上去正确么?
4. 贡献 Contributions: 论文的主要贡献是什么?
5. 整洁性 Clarity: 文章水平如何?

基于以上信息,你也许会决定不再深读(也不会把它打印出来,还省纸).原因可能是因为你不感兴趣,或者你没有足够知识储备去理解文章,亦或者文章基于的假设看上去不靠谱.对于不是你研究领域但某一天可能会是的文章,读一遍就够了.

顺便一说,在你写文章时,你也会料到大多读者(或评审)只会读一遍你的文章.小心选择连贯的大小章节标题，以及编写简洁而全面的摘要。如果评审在读完一遍之后无法理解你文章的梗概,大概率你的文章会被打回.如果读者在五分钟后仍无法理解论文的要点，那你的论文很可能会永远不会被阅读。一个精心编写的”图形摘要”会是一个不错的做法,你也可以在科学期刊中越来越多这么做的文章.

第二遍

在第二遍中,仔细阅读,但忽略诸如证明的细节.记下关键点或在边角处留下注解也会有帮助.奥格斯堡大学的Dominik Grusemann 建议记录下不明的或想向作者提问的点.如果您是一名评审,写下这些也有助于你写述评,并在评审会时也会帮到你.

1. 仔细阅读各类图表.X,Y轴有没有正确的记述?有没有误差线(error bar)使得结论具有统计意义?这些常见的错误会使得文章水平高下立判.
2. 记下还没有阅读的相关参考以便将来阅读(这是个学习更多相关背景知识的好办法).

对于有经验的读者,第二遍会花大约一个小时.读完第二遍后,你应该已经掌握论文内容,并且可以像他人概述论文的主要推论以及支持推论的证据.对于你感兴趣但并非你专业领域的文章,这样的掌握度已经足够.

有时,你读完了两遍也没有理解文章.可能是因为文章主题对你来说你全新的,里面有各种你不熟悉的术语和缩写.又或者作者在证明或实验中使用了你不知道的技巧,以至于文章通篇都难以理解.文章也可能水平不佳,使用了没有根据的断言,大量的使用了参考文献.又又又或者仅仅是因为夜深了你累了.这时候你可以:(a) 把文章丢到一遍并祈祷它不会成为你成功路上的阻碍. (b) 读些参考文献及背景知识. (c) 坚持不懈地开始第三遍.

第三遍

想要完全理解文章,尤其是对于评审来说,第三遍是必要的.第三遍的核心就是再写一遍本文:基于和作者相同的假设,再做一遍作者做过的工作.通过对比你的重做与文章,你可以清楚地发现文章的创新之处,并找到潜在的失败与假设.

这一遍尤其关注细节.你要认出并挑战每句话中的假设.此外,你还应该考虑自己如何能提出特定的想法.这种对比会为你提供敏锐的洞察力,有助于你理解证明以及论述过程.你应该将它加入自己的方法库中.这一遍中,你还应该记下你产生的各种想法以便后续的工作.

这一遍对于初学者会花费大量时间,即使是经验者也会花一到两个小时.在这边之后,你将有能力从记忆中重构整篇文章的框架并指出它的优缺点.尤其是,你可以指出其中隐含的假设,缺省的相关引文,以及在实验和分析中的潜在问题.

文献查阅

读论文是需要练习的技巧,它需要你读大量论文,甚至是在不熟悉的领域.三遍法可以帮助你找到需要读的论文.

首先,在某一领域,使用 Google Scholar 或 CiteSeer 之类的学术搜索引擎找到三至五篇近期高引用的文章.每篇文章都粗读一遍并理解大意,然后阅读其相关章节内容.您会发一些最近的研究内容的简略摘要,运气好的话你会找到关于近期调查文章(译注:recent survey paper,应该是对某一领域的整体调查报告之类的概述性文章).找的话就祝自己好运吧,读它就完了.

否则,在第二步中,在参考中找到相同的引用文献和重复的作者.这些是该领域的关键论文和研究人员.下载重要论文放在一边.然后去搜索关键研究人员,看看他们最近在哪里发表.这将帮助您确定该领域的顶级学会,因为最好的研究人员通常会在顶级学会上发表论文.

第三步,访问这些顶级学会的网站,并浏览它们最近的会议记录.快速浏览通常会确定近期的高质量相关工作.这些论文以及你先前保留的论文构成了调查的第一版.读两遍这些文章.如果他们都引用了一篇你之前没发现的关键文献,获取并阅读它,必要时多读几遍.

相关工作

如果你正在进行论文评审,则还应阅读Timothy Roscoe 的文章Writing reviews for systems conferences[3] .如果你打算撰写技术论文,你应参考 Henning Schulzrinne 的综合网站 [4] 和George Whitesides 的 excellent overview of the process[5].最后, Simon Peyton Jones 有一个涵盖整个研究技能的网站 [2].

来自 McLean of Psychology, Inc. 的 Iain H 整理了一个可下载的 “评审矩阵”, 它使用三遍法简化了实验心理学论文评审的工作 [1]. 经过一些细小的修改,它也许可以应用于其他领域的文章.

致谢

该文档的第一版由我的学生们起草:Hossein Falaki, Earl Oliver, and Sumair Ur Rahman. 在此向他们致谢. Christophe Diot 的知性评论与 Nicole Keshav 的 eagle-eyed copyediting 也使我受益良多.

我希望此文档长期有效,当我收到评论时会对其进行更新.请花一点时间给我发邮件提出任何改进意见或建议.感谢长期以来来自多方的反馈与鼓励.

参考

1. I.H. McLean, “Literature Review Matrix,”
2. S. Peyton Jones, “Research Skills,”
3. T. Roscoe, “Writing Reviews for Systems Conferences,”
4. H. Schulzrinne, “Writing Technical Articles,”
5. G.M. Whitesides, “Whitesides’ Group: Writing a Paper,”

题目

原题在此
Suppose you have n integers from 1 to n. We define a beautiful arrangement as an array that is constructed by these n numbers successfully if one of the following is true for the ith position (1 <= i <= n) in this array:

• The number at the ith position is divisible by i.
• i is divisible by the number at the ith position.
  Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Example 2:
Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 15

解析

暴力搜索的情况,需要遍历所有可能的排列(permutation),此时复杂度为$O(N)$.
改进的思路也简单,在全排列的过程中,如果一个分支出现了不满足题意的情况,则该分支下的所有排列都不可能是”Beautiful Arrangement”.
用一个bool数组来记录每个数字的使用情况,然后从位置1开始尝试放入1-N的每个数字,此时:

• 若该数字还没有被使用且符合题目要求,尝试下一个位置.
• 若该数字不符合要求,继续看下一个数字是否能放在当前位置.
• 都放完了的时候即是一个”Beautiful Arrangement”, count 加一.

此时时间复杂度为$O(k)$, k为有效排列的个数.空间复杂度为$O(N)$,使用了一个长度为$n$的数组.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int used[16] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int count = 0;
    int countArrangement(int n) {
        dfs(1, n);
        return count;
    }
    
    void dfs(int pos, int n) {
        if(pos > n) {
            count++;
            return;
        }
        for(int i = 1; i <= n; ++i) {
            if(!used[i] && (!(i % pos) || !(pos % i))) {
                used[i] = 1;
                dfs(pos + 1, n);
                used[i] = 0;
            }            
        }
    }
};

Chapter 1 Introduction to Vectors

Vectors and Linear Combinations

1. A vector $v$ in two-dimensional space has two components $v_1$ and $v_2$.
2. $v + w = ( v_1 + w_1, v_2 + w_2)$ and $cv = ( cv_1, cv_2)$ are found a component at a time.
3. A linear combination of three vectors $u$ and $v$ and $w$ is $cu+ dv + ew$.
4. Take all linear combinations of $u$, or $u$ and $v$, or $u$, $v$, $w$. In three dimensions,
   those combinations typically fill a line, then a plane, then the whole space $R^3$.

Lengths and Dot Products

1. The dot product $v • w$ multiplies each component $v_i$ by $w_i$ and adds all $v_i w_i$.
2. The length $||v||$ is the square root of $v · v$. Then $u = \frac{v}{||v||}$ is a unit vector : length 1.
3. The dot product is v · w = 0 when vectors v and w are perpendicular.
4. The cosine of $\theta$ ( the angle between any nonzero v and w) never exceeds 1:
   Cosine $cos\theta=\frac{v · w}{||v||||w||}$, Schwarz inequality $|v · w|\leqq||v||||w||$.

Matrices

1. Matrix times vector: $Ax$ = combination of the columns of $A$.
2. The solution to $Ax = b$ is $x = A - lb$, when $A$ is an invertible matrix.
3. The cyclic matrix $C$ has no inverse. Its three columns lie in the same plane.
   Those dependent columns add to the zero vector. $Cx = 0$ has many solutions.
4. This section is looking ahead to key ideas, not fully explained yet.

Chapter 2 Solving Linear Equations

Vectors and Linear Equations

1. The basic operations on vectors are multiplication cv and vector addition v + w.
2. Together those operations give linear combinations cv + dw.
3. Matrix-vector multiplication Ax can be computed by dot products, a row at a time.
   But Ax must be understood as a combination of the columns of A.
4. Column picture: Ax = b asks for a combination of columns to produce b.
5. Row picture: Each equation in Ax = b gives a line (n = 2) or a plane (n = 3)
   or a “hyperplane” (n > 3). They intersect at the solution or solutions, if any.

什么是NoSQL

NoSQL，是指Not Only SQL而非“没有SQL”。SQL指代传统关系型数据库（RDBMS），NoSQL泛指非关系型数据库。

DFA

定义: 有穷自动机是一个5元组 $(Q, Σ, δ, q_0, F)$ , 其中
1) $Q$是一个有穷集合, 叫做状态集.
2) $Σ$是一个有穷集合, 叫做字母表.
3) $δ: Q×Σ→Q$ 是转移函数.
4) $q_0∈Q$是起始状态.
5) $F \subseteq Q$是接受状态集

在算数中,基本对象是数,工具是处理数的运算,如加减乘除. 在计算理论中,对象是语言,工具包括为处理语言所设计的运算.设$A$是机器$M$接受的全部字符串集, 称$A$是机器$M$的语言,记做$L(M)=A$.定义如下三种运算,称作正则运算.

定义:设$A和B$是两个语言

• 并: $A \cup B=\{ x| x \in A \text{ 或 } x \in{B}\}$
• 连结: $A \circ B=\{ xy | x \in{A} \text{ 且 } y\in{B}\}$
• 闭包: $A \text{*}= \{ x_1x_2\dotsb x_k|k \geq 0 \text{ 且 } \forall{x_i}\in A\} $

并运算把$A和B$中的所有字符串合并在一个语言中.
连结运算以所有可能的方式,把$A$中的一个字符串接在$B$中的一个字符串前面,得到新的语言中的全部字符串.
闭包运算是一个一元运算,他把$A$中任意个字符串连结在一起得到新语言中的一个字符串.以为任意个包括0个,所以空串 $\epsilon$总是$A \text{*}$的一个成员.

$\epsilon$-NFA

非确定型有穷自动机是一个5元组 $(Q, Σ, δ, q_0, F)$ , 其中
1) $Q$是一个有穷集合, 叫做状态集.
2) $Σ$是一个有穷集合, 叫做字母表.
3) $δ: Q×(Σ\cup\{\epsilon\})→2^Q$ 是转移函数.
4) $q_0∈Q$是起始状态.
5) $F \subseteq Q$是接受状态集

与DFA不同之处在于
1) 状态转移的结果为状态集合的幂集. (定义:一个集合$Q$的所有子集所组成的集合称作集合$Q$的幂集记做$2^Q$,其中包括全集和空集.)
2) 允许空串状态转移($\epsilon\text{-move}$)

前端小白刚刚涉足前端开发，面对琳琅满目的框架，不知该如何挑选，不可免俗的落入了货比三家的尴尬场面。在看过尤雨溪在JSconf的演讲后，对 _React_, _Vue_, _Angular_ 三大框架有了一些基础认识。
视频中，尤通过Scope和Render Mechanism两个角度对比了三大框架。

Scope (范围)

范围意为框架试图为用户解决多少问题。小的框架专注于原始的概念，依靠活跃的生态系统，像集市一样自下而上的发展。大的框架试图提供常见问题的全套解决方案，也因此会像教堂一样自上而下的发展。

Small Scope

_React_ 在官网中自称是JS的UI库，可见其范围之小
Pros

• 更少概念 -> 更快开始
• 更多用户自由度 -> 活跃的生态系统
• 更少维护范围 -> 更多力气用来创新

Cons

• 解决复杂问题时需要更多的抽象(基建)工作
• 重复的抽象工作渐渐产生模式，模式渐渐变成了成熟的第三方解决方案，第三方解决方案变成了某种程度上的必备知识却不一定有完备的文档可供学习。
• 生态系统的碎片化

Large Scope

_Angular_ 特性丰富，功能繁多，是大型框架的代表
Pros

• 大多常见问题可在框架内找到解决方案，不用为选择何种第三方方案而烦恼
• 稳定一致的生态系统

Cons

• 需要更多的前置技能
• 在内置解决方案不适配你的问题时体现出的不灵活
• 由于框架开发团队要负责框架的全部维护工作，在保证整体协作性的引入新的特性会变得代价昂贵

渐进式Scope

视频中，尤称 _Vue_ 落在了 _React_ 和 _Angular_ 的中间， 同时享有Small Scope和Big Scope的优缺点
Pros

• 引用一个 “Vue.js” 就可以开始编码，上手简单
• 必要时可以引入官方提供的部件(e.g. Router, Vuex)，它们有完备的文档。当然你也可以实现自己的需求

Cons

• 框架开发团队需要维护更多的东西。对比有钱有人的Google和Facebook，更暴露出更新缓慢的问题

Render Mechanism (渲染机制)

渲染机制意为框架下的UI构造的表达方式以及框架如何渲染这些东西。在这一节，尤以 _React_ 和 _Angular_ 为例做出了对比。

JSX / Virtual Dom

Pros

• JSX 拥有高度的表达能力与自由
• Virtual Dom 将试图抽象为数据，可以渲染在DOM之外的地方(e.g. _React Native_)

Cons

• 更多自由度意味着更多的不确定性，会给调优带来困难
• scheduling在感官上提高了性能其实有更多开销

Template

Pros

• 更直接的渲染方式也意味着更好的性能表现
• 更固定的表达方式意味着更多优化的可能
• 适当优化可带来更轻量的初次加载

Cons

• 受模板语法所限
• 运行时或构建阶段的编译开销
• 优化带来更冗余的template

VDom + Tepmlate

Vue 同时支持VDOM和template，也同时享有两方的优点。至于缺点，尤提到了两点。

1. 不会比原生JS快和template
2. render()和template该用哪个的选择问题

感觉都没说到点子上，所以又去查了查，参考如下
vue.js有哪些设计缺陷？

个人思考

作为一个初学者，40分钟的视频边查各种词汇边看花了一个下午，对各个框架的底层设计并没有很好的理解。还是不要纠结孰优孰劣得好，不如抓起一个就学，充分了解各个框架的设计思路与底层实现，得出自己的结论。

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