stealed foreword

The first laboratory session was devoted to finding out that developer feels slippery and that fixer smells awful.

试试 mdbook

github pages 好像静态网页都能托管。

呼呼呼

学习，学个屁。真如漏勺兜水，前面学后面忘。

行逆水行舟之事挫人心志，左看右看不知深处，浑浑厄厄不知岁月，转头一看什么也没有留下。

哗啦哗啦

• mdbook 默认的公式是 mathjax。这个 blog 感觉尽量不要把数学的东西丢进来，但等下还是看看 preprocess，把 mathjax 换成 katex，以及
• markdown 看看有没有 CICD 支持的 lint。
• racket 语法高亮。

TLS

One cannot build a beautiful and functional bridge without a knowledge of steel and dirt and considerable mathematical technique for using this knowledge to compute the properties of structures.

开始研习 the little schemer，记录学习过程中的想法

据 preface 所言，此书旨在 teaching reader thinking recursively，为了达成这一目的，作者才选择了 scheme 作为教具。

此书的写作目的并非让读者熟练掌握 scheme 本身，作者明确指出书中只用到了 scheme 的一个小子集。

在 guideline 中，作者建议 Read carefully，并且 Do not read the book in fewer than three sittings。前面章节的理解会影响后面的阅读，请读者保证顺序理解所述内容。

若在读书过程中设立一个明确的目标，大概就是理解并自行推导出 y-combinator，理解其思想。

Racket

racket 是 lisp 的一种方言，是 scheme 的一个 descendant。

没了解过 scheme，不太清楚具体区别。不过据说 racket 能直接用来看 TLS，使用 DrRacket，并选择 racket 原生语言即可：

#lang racket

cons and list

atom

序言中定义了 atom?:

(define atom?
    (lambda (x)
        (and (not (pair? x)) (not (null? x)))))

即，不是 pair，也不是 null 的东西就叫 atom

> (atom? null)
#f
> (atom? '(1 2 3))
#f

> (atom? #f)
#t
> (atom? 1)
#t
> (atom? "abc")
#t

怀疑这是不是书中自造的概念，我在 The Racket Guide 里没看到这个说法

pair, list 和 s-expression

reference 中提到：

In general, the result of cons is a pair. The more traditional name for the cons? function is pair?, and we’ll use the traditional name from now on.

也就是说 cons 是 pair 的构造子，(cons a b) 表示把 a 和 b 连在一起，构成一个 pair。

这一点与书中不一样。TLS 中并没有 pair 这一回事，而是只有 list，并将 cons 视为 list 的构造子，其第二个参数必须也是一个 list。

我这里还是采用 racket 实际的情况。

对此，书中提到一笔：

In practice, (cons a b) works for all values a and b, and

(car (cons a b)) = a, (cdr (cons a b)} = b

利用 cons，我们构造出 list 和 s-expression，按我理解，二者是递归定义的，以 CFG 写出来大概像这样:

S-expression = 
    atom |
    list

list = 
    null |
    (cons S-expression list)

list

1. 要么是 null
2. 要么是一个特殊的 pair。特殊在于该 pair 的第二个部分一定是一个 list。由此可知，list 必有类似以下的结构：

(cons a (cons b (cons c (cons d null))))

一个例子是

> (cons null null)
'(())

racket 中，null 也可以写作 '()。单引号是一个函数 quote 的简写

值得注意，(cons a b) 直接将 a, b 组成一个 pair，这不等于 (list a b)：

> (cons 1 2)
'(1 . 2)
> (cons 1 '(2))
'(1 2)
> (list 1 2)
'(1 2)

> (list? (cons 1 2))
#f
> (pair? (cons 1 2))
#t
> (pair? (list 1 2))
# t

'(a b) 表示一个 list，而 '(a . b) 表示一个 pair。应该将前者看作后者的一种简写，'(a b) 写全了应该是 '(a . (b . ()))

quote

还需理解 datum。quote 是否与其数据引用有关。

'a = (quote a)
'(a b c) = (list 'a 'b 'c)

在 REPL 里测试一下：

> '#t
#t
> '1
1
> '"abc"
"abc"

> '()
'()
> (list)
'()
> 'fdasfs
'fdasfs

一个层层展开的例子：

''(1)
-> (quote '(1))
-> (quote (quote (list 1)))

> (car ''(1))
'quote
> (cdr ''(1))
'((1))

分析一下，首先，要理解 (car ''(1)) 得到 'quote ，只需要理解 (quote (quote (list 1))) 是一个 list，它的左侧就是 quote

然后为了得到 (cdr ''(1))，这里把 list 看成 pair，即：

• (quote (quote (list 1))) 看作
• (quote . ((quote (list 1))))

再例如：

> (car '(define a 1))
'define
> (car '(+ 1 2))
'+

这里有个关于 null 的，有点特别的例子：

> null
'()
> '()
'()
> 'null
'null
> ''()
''()
> ''null
''null

null

书中指出，(quote ()) 是 null 的一种记号。

Lisp: Also () and '().

Scheme: Also '()

实验一下:

> (quote ())
'()
> (null? (quote ()))
#t

嗯... () 能单独出现在 (quote ()) 里，这是否说明解释器以某种规则进行了特判。

> null
'()
> '()
'()
> (eq? null '())
#t
> (eq? 'null ''())
#f

有点神秘

stars

直到 *-functions 这一章，作者用上了他定义的所有东西。其迭代的对象有

1. (cons atom list)
2. (cons number list)
3. (cons s-expression list)

从这时起，每次 l 上的迭代都将判断三块地方

1. (null? l)，其为边界条件
2. (atom? (car l))，若 #t，则在 (car l) 上递归
3. else，在 (cdr l) 上递归

例如 occur*

(define (occur* a l)
  (cond
    ((null? l) 0)
    ((atom? (car l))
     (cond
       ((eq? a (car l)) (add1 (occur* a (cdr l))))
       (else (occur* a (cdr l)))))
    (else (+ (occur* a (car l)) (occur* a (cdr l))))))

关于 leftmost

(define (leftmost l)
  (cond
    ((null? l) null)
    ((atom? (car l)) (car l))
    (else
     (cond
       ((null? (leftmost (car l)))
        (leftmost (cdr l)))
       (else (leftmost (car l)))))))

实际上不需要去问 (cdr l)，因为此处左侧要么存在一个 atom，要么为 null，因而只需要考虑 (car l)

(define (leftmost1 l)
  (cond
    ((null? l) null)
    ((atom? (car l)) (car l))
    (else (leftmost1 (car l)))))

书上给的答案是

(define (leftmost2 l)
  (cond
    ((atom? (car l)) (car l))
    (else (leftmost2 (car l)))))

其假设 l 的左侧非 null

不清楚实际写代码，如果出了 null 怎么办。是 lisp 不容易出现这种问题吗？

eqlist?

首先，写了一个判断两个 list 是否相等的判定函数 eqlist?

(define (eqlist? l r)
  (cond
    ((and (null? l) (null? r)) #t)
    ((or (null? l) (null? r)) #f)
    (else
     (cond
       ((and (atom? (car l)) (atom? (car r)))
        (and (eq? (car l) (car r))
             (eqlist? (cdr l) (cdr r))))
       ((or (atom? (car l)) (atom? (car r))) #f)
       (else (and (eqlist? (car l) (car r))
                  (eqlist? (cdr l) (cdr r))))))))

然后，利用这个函数来写一个判定 s-expression 是否相等的函数 equal?

(define (equal l r)
  (cond
    ((and (atom? l) (atom? r)) (eq? l r))
    ((or (atom? l) (atom? r)) #f)
    (else (eqlist? l r))))

最后，用 equal? 倒回来替换掉 eqlist? 中 s-expression 的比较：

; modified `eqlist?`
(define (eqlist? l r)
  (cond
    ((and (null? l) (null? r)) #t)
    ((or (null? l) (null? r)) #f)
    (else (and (equal? (car l) (car r))
               (eqlist? (cdr l) (cdr r))))))

; use this `equal?`
(define (equal? l r)
  (cond
    ((and (atom? l) (atom? r)) (eq? l r))
    ((or (atom? l) (atom? r)) #f)
    (else (eqlist? l r))))

这形成了一个相互递归调用，它的收敛性我不好说

只能勉强看出来，每次调用的过程中，参数都在变，而且应该是作为 list 变短了。这很符合书中所述的某一条 Commandment

shadow

这章没太看懂跟 shadow 有什么关系。

前面写了两个不同形式的算术表达式 parser，后面用另一种方式定义了自然数。

估计是想跟柏拉图的地穴寓言一样表达一下认知论的东西。

friends and relations

set

实现了一些集合操作，没什么好说的

pair

书中的 pair 定义为长为 2 的 list，与实际上不同。

fun

从函数映射的角度看这种...类似 map 的结构

定义 fun? 来判定映射, fullfun? 来判定双射。这不该是满射吗

应该说 map 天然就是满射，所以他这里只判断了单射，于是满射。

这章最后用两种办法判定双射，一种是直接看陪域有没有重复，也就是是不是单射。

问有没有另一种实现，给出的答案是判定其逆映射是不是映射。

嗯...

abstract and continuation

这章还没深入讲 lambda，只是将其作为抽象工具

continuation

Wiki:

In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements (reifies) the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on.

简单理解的话，感觉是把一个连续过程分解成从节点到节点，并且把节点以具体数据结构表示出来方便后续操作。有点像 linux 的文件系统，有点像流

multirember&co

我不好说，这部分有点烧脑

(define multirember&co
  (lambda (a lat col)
    (cond
      ((null? lat)
       (col '() '()))
      ((eq? a (car lat))
       (multirember&co a (cdr lat)
                       (lambda (newlat seen)
                         (col newlat (cons (car lat) seen)))))
      (else
       (multirember&co a (cdr lat)
                       (lambda (newlat seen)
                         (col (cons (car lat) newlat) seen)))))))

还是直接来个例子展开：

(define a-friend
    (lambda (x y) (null? y)))

(multirember&co 2 '(1 2 3) a-friend)

=> (multirember&co 2 '(2 3)
                   (lambda (newlat seen)
                     (a-friend (cons 1 newlat) seen)))

=> (multirember&co 2 '(3)
                   (lambda (newlat' seen')
                     (lambda (newlat seen)
                       (a-friend (cons 1 newlat) seen))
                     newlat'
                     (cons 2 seen')))

=> (multirember&co 2 '()
                   (lambda (newlat'' seen'')
                     (lambda (newlat' seen')
                       (lambda (newlat seen)
                         (a-friend (cons 1 newlat) seen))
                       newlat'
                       (cons 2 seen'))
                     (cons 3 newlat'')
                     seen''))

=> ((lambda (newlat'' seen'')
      (lambda (newlat' seen')
        (lambda (newlat seen)
          (a-friend (cons 1 newlat) seen))
          newlat'
          (cons 2 seen'))
        (cons 3 newlat'')
        seen'')
      '()
      '())

=> ((lambda (newlat' seen')
      (lambda (newlat seen)
        (a-friend (cons 1 newlat) seen))
        newlat'
        (cons 2 seen'))
      (cons 3 '()) 
      '()))

=> ((lambda (newlat seen)
      (a-friend (cons 1 newlat) seen))
    (cons 3 '())
    (cons 2 '()))

=> (a-friend (cons 1 (cons 3 '()) (cons 2 '())))

=> #f
     

我不好说。

从这个展开来看，该函数会将 l 分成两个 list，前者是去掉 a 的 l，后者是所有的 a。

恕我直言，这个例子举得不是很好。一来这个函数的意义并不显然，二来难度曲线太大，手动模拟起来有些繁琐

已经解包

我觉得一个简单点的例子也许看的更清楚

写个函数 remove-a&co x l col 处理数字的 list，去掉 l 中的 x 并统计其个数

(define (remove-a&co x l col)
  (cond
    ((null? l) (col '() 0))
    ((= x (car l))
     (remove-a&co x (cdr l)
                  (lambda (newl cnt)
                    (col newl (add1 cnt)))))
    (else (remove-a&co x (cdr l)
           (lambda (newl cnt)
             (col (cons (car l) newl) cnt))))))

; (remove-a&co 1 '(2 1 3 5 4 1)
;              (lambda (l cnt) (list l cnt)))

; 直接用 `list` 替代这个 `lambda`
(remove-a&co 1 '(2 1 3 5 4 1) list)

; output: 
;   '((2 3 5 4) 2)

用一个简单点的例子写一下展开过程：

(remove-a&co 1 '(2 1 3) list)

->
(remove-a&co 1 '(1 3)
    (lambda (newl cnt)
        (list (cons 2 newl) cnt)))

->
(remove-a&co 1 '(3)
    (lambda (newl' cnt')
        (lambda (newl cnt)
            (list (cons 2 newl) cnt))
          newl'
          (add1 cnt')))

->
(remove-a&co 1 '()
    (lambda (newl'' cnt'')
        (lamdba (newl' cnt')
            (lambda (newl cnt)
                (list (cons 2 newl) cnt))
            newl'
            (add1 cnt'))
        (cons 3 newl'')
        cnt''))

->
((lambda (newl'' cnt'')
    (lamdba (newl' cnt')
        (lambda (newl cnt)
            (list (cons 2 newl) cnt))
        newl'
        (add1 cnt'))
    (cons 3 newl'')
    cnt'')
    '()
    0)

->
((lambda (newl' cnt')
    (lambda (newl cnt)
        (list (cons 2 newl) cnt))
        newl'
        (add1 cnt'))
    (cons 3 '())
    0)

->
((lambda (newl cnt)
    (list (cons 2 newl) cnt))
    (cons 3 '())
    1)

->
(list (cons 2 (cons 3 '())) 1)

; which is
;   '((2 3) 1)

lambda 嵌套 lambda，本该在过程式语言中最里侧的参数，在这里却是从最外侧传进去

数据传递以参数的形式进行，而没有解包的过程

evens-only*

该函数过滤掉 list 中的奇数，并统计去掉奇数的个数。

此习题与之前的差不多，不过要求从 list 的左右两边同时递归，并整合两边递归的结果。

(define (evens-only*&co l col)
  (cond
    ((null? l) (col '() 0))
    ((atom? (car l))
     (cond
       ((even? (car l))
        (evens-only*&co (cdr l)
                     (lambda (newl cnt)
                       (col (cons (car l) newl) cnt))))
       (else (evens-only*&co (cdr l)
                          (lambda (newl cnt)
                            (col newl (add1 cnt)))))))
    (else (evens-only*&co (cdr l)
                       (lambda (newld cntd)
                         (evens-only*&co (car l)
                                         (lambda (newla cnta)
                                           (col (cons newla newld)
                                                (+ cnta cntd)))))))))

(evens-only*&co '((9 1 2 8) 3 10 ((9 9) 7 6) 2) list)

; '(((2 8) 10 (() 6) 2) 6)

这个整合两侧的 lambda 很不好想。

之所以能写出这个 collector，我想是因为二叉树可以拉直成一条链

从回调函数的角度来理解，当 (lambda (newl cnt) ...) 定义出来时，就该假设其函数体定义里已经得到了 newl, cnt 的值，并且能够自由使用

嗯...

callback 可能是个不错的角度

halt

A's arguments, like shuffie's and looking's, do not necessarily decrease for the recursion.

第九章从几个函数出发简单介绍了一下停机和死循环。

它将最终会停机的函数称为 total，否则称为 partial。

以映射角度看函数，其居然有值无法到达陪域，因而称为 partial function

停机

这里给的证明是若函数 will-stop? 是 total 的，则：

(will-stop? (lambda (x)
    (and (will-stop? last-try)
        (eternity x))))

会得到矛盾的值。

《计算理论导引》那书上的停机问题好像是归约到图灵机 $A_{TM}$ 不可判定上去

$\lambda$ 递归

(lambda (x) (x x))

这个例子相当引人入胜，用 $\lambda$ 构造出 length 来计算 list 的长度：

尝试

(((lambda (mk-length)
   (mk-length mk-length))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1
              (length (cdr l)))))))) 
 '())

这个仅能计算一层，展开的话是：

->
(((lambda (length)
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1
            (length (cdr l)))))))
  (lambda (length)
    (lambda (l)
      (cond
      ((null? l) 0)
       (else (add1
             (length (cdr l))))))))
  '())

->
((lambda (l)
    (cond
    ((null? l) 0)
    (else (add1
        ((lambda (length)
           (lambda (l)
            (cond
              ((null? l) 0)
              (else (add1
                (length (cdr l)))))))
           (cdr l))))))                 ; 本应传递一个 `length` 得到内部的 lambda，但传递了一个 `list`
  '())

->
0

可以看出来尚不足以进行长度大于 0 的递归，因为到后面 length 没有正确的参数传进去。

修复

; 一步步改进
(((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1
              ((mk-length eternity)
               (cdr l))))))))
 '(1))

这里放了个 eternity 虚位以待，然而并不能改变它算不了非空 list 的事实：

->
(lambda (l)
  (cond
  ((null? l) 0)
  (else (add1
    ((lambda (mk-length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 
                  (mk-length (cdr l)))))))
      eternity                      ; 充其量
      (cdr l))))))

->
(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1
      ((lambda (l')
          (cond
            ((null? l') 0)
            (else (add1 
                    (eternity (cdr l))))))
        (cdr l))))))

可以看出仅能递归两层。

接下来的任务是要用一个无穷递归来替换 eternity

无穷

为了让递归更明显，多写几层，无穷递归部分仍以 eternity 暂时代替

(lambda (l)
(cond
((null? l) 0)
(else (add1
  (
    (lambda (l)
    (cond
    ((null? l) 0)
    (else (add1
      (
        (lambda (l)
        (cond
        ((null? l) 0)
        (else (add1
          (
            (lambda (l)
            (cond
            ((null? l) 0)
            (else (add1
              (
                (lambda (l)
                (cond
                ((null? l) 0)
                (else (add1
                  (
                    (lambda (l)
                    (cond
                    ((null? l) 0)
                    (else (add1
                      (
                        (lambda (l)
                        (cond
                        ((null? l) 0)
                        (else (add1
                          (
                            (lambda (l)
                            (cond
                            ((null? l) 0)
                            (else (add1
                              (
                                (lambda (l)
                                (cond
                                ((null? l) 0)
                                (else (add1
                                  (
                                    (lambda (l)
                                    (cond
                                    ((null? l) 0)
                                    (else (add1
                                      (
                                        (lambda (l)
                                        (cond
                                        ((null? l) 0)
                                        (else (add1
                                          (
                                            (lambda (l)
                                            (cond
                                            ((null? l) 0)
                                            (else (add1
                                              (
                                                eternity
                                            (cdr l))))))
                                        (cdr l))))))
                                    (cdr l))))))
                                (cdr l))))))
                            (cdr l))))))
                        (cdr l))))))
                    (cdr l))))))
                (cdr l))))))
            (cdr l))))))
        (cdr l))))))
    (cdr l))))))
(cdr l))))))

回过头看用 eternity 作为占位符的定义：

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1
              ((mk-length eternity)
               (cdr l))))))))

最后真正想要得到的是这一部分：

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1
            ((mk-length eternity)
             (cdr l))))))

并且想要用这一个整体自身来替换 (mk-length eternity)

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1
            ((lambda (l)
              (cond
                ((null? l) 0)
                (else (add1
                        ((mk-length eternity)
                        (cdr l)))))))
             (cdr l))))))

换言之，我需要找到一个 eternity 满足

(mk-length eternity) 

=

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1
            ((mk-length eternity)
             (cdr l))))))

然而答案一开始就给出来了：

mk-length = 
(lambda (mk-length)
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1
              ((mk-length eternity)
              (cdr l))))))))

(mk-length mk-length) = 
(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1
            ((mk-length eternity)
            (cdr l))))))))

于是只需要取 eternity 在这里等于 mk-length 即可

y(WIP)

TLS 里最终抽象出来的 Y 组合子长这样：

(define Y
    (lambda (le)
        ((lambda (f) (f f))
         (lambda (f) 
            (le (lambda (x) ((f f) x)))))))

里边稍微 apply 一层就跟经典的长得一样了：

(define Y
    (lambda (le)
        ((lambda (f)
            (le (lambda (x) ((f f) x))))
         (lambda (f)
            (le (lambda (x) ((f f) x)))))))

注意 (lambda (x) ((f f) x)) 其实就是 (f f)，这里为了惰性求值包了一层。

(define Y
    (lambda (le)
        ((lambda (f)
            (le (f f)))
         (lambda (f)
            (le (f f))))))

(define fact
  (Y (lambda (fact1)
       (lambda (n)
         (cond
           ((= n 1) 1)
           (else (* n (fact1 (sub1 n)))))))))

(fact 1)
(fact 2)
(fact 3)
(fact 5)

上述写法会无穷递归

type(WIP)

找找有没有办法查看表达式的类型。

或者说有没有官方支持的类型。

lazy(WIP)

在提取 length 里面 (mk-length mk-length) 的时候，利用 lambda 包一层实现了惰性，问：

(a a)

(lambda (x)
    ((a a) x))

有什么区别

在正常求值的时候应该看不出来区别，然而在作为参数传递的时候区别很大：

(define (do-x f x)
    (f x))

(do-x (a a) 1)
；先求值 (a a)，再代入

(do-x (lambda (x)
        ((a a) x)) 1)
->
((lambda (x) ((a a) x)) 1)
->
((a a) 1)

questions

1. explain

> null
'()
> '()
'()
> (eq? null '())
#t
> (eq? 'null ''())
#f

2. why not same

> (eq? (quote 1) 1)
#t
> (eq? (quote a) a)
#f
> a
'()
> (define y a)
> (eq? (quote a) y)
#f

3. litteral?

能否写一个函数 car l，使其返回 l 的第一个字符？

不同于 car '(+ 2 3) 会得到 '+，能否有 car1 (+ 2 3) 得到 '+？

感觉不行，默认是按值传递的。

reverse list

翻转代数类型的链表还挺复杂的

(cons c (cons a (cons t null)))

=>

(cons t (cons a (cons c null)))

这个完全翻转的过程很容易让人联想到利用 lambda 来把参数调用顺序翻过来的过程：

(define (rev&f l f)
  (cond
    ((null? l) (f null))
    (else (rev&f (cdr l) (lambda (new-l)
                           (cons (car l) (f new-l)))))))

(define (rev l) (rev&f l (lambda (l) null)))

想象一下，最后反过来调用的过程应该长这样：

(lambda (new-l3)
    (cons t
        ((lambda (new-l2)
            (cons a 
                ((lambda (new-l1)
                    (cons c
                        (f 
                        new-l1)))
                new-l2)))
        new-l3))) 
null

可以看到 null 从 new-l3 传到 new-l2，再到 new-l1，一层层地被传递到最里面

那么有没有办法不通过函数调用，而是直接传到最里面呢？毕竟大伙都知道最里面肯定是个 null

emmm...

(define (rev&f l f)
  (cond
    ((null? l) (f))
    (else (rev&f (cdr l) (lambda ()
                           (cons (car l) (f)))))))

(define (rev l) (rev&f l (lambda () null)))

...silly of me

...

想复杂了好像

(define (rev-helper l new-l)
  (cond
    ((null? l) new-l)
    (else (rev-helper (cdr l) (cons (car l) new-l)))))

(define (rev1 l) (rev-helper l null))

cs144

体验，学习，顺便考研

Spring 2023

官网

每年都用一个 url，不知道将来还能不能找到这一年的存档

我的作业 repo

rust

本来是想用 rust 做的，课程要求的 cpp 风格很严格，不能有 new/delete，不能有裸指针，要积极加 const qualifier，不能 c 风格 cast，感觉不如直接用 rust

但底层代码以及，尤其是大量的测试代码，都是内嵌 cpp，一时让人不太想重写

还是先用 cpp 做完一遍再看看自己实现吧

peek

lab0 的第一部分是模仿 telnet 的操作，用它给的 socket 实现去进行一个 http 的 GET 请求

每个 socket 都在 write 对面和 read 自己，这与后面实现的 StreamBytes 类不同

ByteStream

第二部分

按照要求，这是一个单线程读写 Stream

也就是说，同时只有一个 writer 和一个 reader，而且 reader 读的还都是这个 writer 写的东西

这部分的主要问题在于 peek 函数

class Reader : public ByteStream
{
public:
  std::string_view peek() const; // Peek at the next bytes in the buffer

函数是 const 的，说明没有副作用

返回值类型是 string_view，这是一个引用，相当于 slice

这说明该函数应该返回自己内部数据的一个引用类型

然而 string_view 要求引用的数据是 contiguous 的，也就是说在内存里要挨着

如果我来定义这个 peek 我估计会返回一个迭代器

总之这样就只能用 vector 了，并且用它模拟一个环

然而新问题在于 peek 需要能返回多长的内容

如果返回迭代器就没有这个问题，但返回 string_view 代表返回的内容长度需要我来决定

额

既然用 vector 模拟环了，那么能返回的长度上限就不是 capacity，而是从 head 到 vector.end() 之间，这样会导致 peek 不能保证 peek 到全部内容

...

然而这么写的话，测试都过了

不好说

在不 pop 的情况下，明显会出现有一部分内容永远无法 peek 到的情况

这应该不是一个好的定义

vector 模拟环

我计算下标的时候直接储存了单调递增的 head 和 tail，虽然是 uint64 类型，但终究是有限数

...

不好说，感觉问题很大

send and receive

此时才意识到这个 cs144 的 lab 其实没有那么底层，它的 send 实现甚至是让人填空 maybe_send()，然后外部轮询

有点琐碎，细枝末节太多，感觉一个月后什么也不记得。

fp

But what about creative composition? In order to be creative one must first gain control of the medium. One can not even begin to think about organizing a great photograph without having the skills to make it happen. In engineering, as in other creative arts, we must learn to do analysis to support our efforts in synthesis. One cannot build a beautiful and functional bridge without a knowledge of steel and dirt and considerable mathematical technique for using this knowledge to compute the properties of structures. Similarly, one cannot build a beautiful computer system without a deep understanding of how to "previsualize" the process generated by the procedures one writes.

当真不论哪个分叉都洋洋兮若江河，看不见顶摸不着底。

又是 lambda (WIP)

时隔良久，又忙里偷闲捡起来这东西。

看了这个博客，感觉是很好的补充，又把没理解的东西捡起来试图理解一下。（也是在翻了这作者的博文之后，让我起了好好记录 blog 的念头。

解方程

对于阶乘函数 fact

fact :: Int -> Int
fact n = case n of 
  1 -> 1
  n -> n * fact (n-1)

有一个问题是如何只用 lambda 演算来实现 fact。具体一点来说，需要在 fact 内部不能调用 fact 自身。

一定程度上来说，这个要求是很直观的，因为在函数内部调用 fact 时，fact 自身还没定义完，怎么能够调用它呢？

在上面提到的博文当中，该文作者视函数定义为一个方程（可能也确实是），fact n 后的等号 =，就是数学意义上的等号，等号两侧完全等价。

如果能够利用这个方程，直接解出 fact 的定义，那么也就得到了 fact 的定义，绕过了先有鸡还是先有蛋的问题。

不动点

中学数学里其实很直接少见到递归的概念，偶尔出现也只是出于数列题目，浮光掠影。

然而哪怕只是很少出现，也有人已经把不动点的概念引入到各种高中教辅书里，配上标题：『不动点法求通项公式』，配图往往有两种，一种是一个螺旋状，另一种是折线。（折线的大概长这样）：

       ▲
       │
       │
       │
       │
       │                                                 xx
       │                                                xx               lll
       │                                              xx         lllllllll
       │                                           xxx     llllll
       │                                        xxx lllllll
       │                                     llllllll
       │                               lll▲─►l
       │                         lllll┌───┘x
       │                     lllll    ▲xxx
       │                 lll┌────────►┘x
       │             lllll  ▲      xxx
       │         lllll      │    xx
       │     lllll          │  xx
       lllllll▲─────────────►xx
lllllll│      │            xx
l      │      │         xxx
       │      │       xxx
       │      │     xxx
       │      │    xx         y=x
       │      │  xx
       │      │xx
       │     x│x
       │    xx│
       │  xx  │
───────┘xx────┴───────────────────────────────────────────────────────────────►
      xx
    xx │
   x   │
 xx    │

基本意思就是不动点随着数列趋于极限，将逐步收敛到一个“稳定”的定值。或者干脆就等于这个值，同时因为这个点很“稳定”，于是它不再往外跑，从而得到了一个解。

那时候的理解很粗糙，没能真正弄懂极限与无穷。但是从利用这个工具解题的过程中还是获得了一点认知：谁掌握了不动点，谁就掌握了整个复杂过程的解。

方程例子

上面提到的 blog 里，作者引用的是函数定义上的不动点，即若 f(x)=x，则 x 是 f 的一个不动点。但我觉得数列的例子可能更像一个算法，于是多写了几笔。

言归正传。先从阶乘的例子来看 $Y$ 组合子怎么用。$Y$ 组合子有这样的性质：

Y f = f Y f

也就是说 $Y$ 组合子是这样一个高阶函数：对于任意函数 $f$，$(Yf)$ 都是 $f$ 的一个不动点

f (Y f) = (Y f) ; 函数作用是右结合的

定义对于阶乘函数 fact，定义一个 mk-fact:

(define (mk-fact fact')
  (lambda (n)
    (cond
      ((= n 1) 1)
      (else (* n (fact' (sub1 n)))))))

我擦，看起来好麻烦，我换个随意点的写法：

mk-fact fact' =
  if n = 1  => 1
  else      => n * (fact' (n-1)) ; 意思到了就行

然后直接将 mk-fact 给 $Y$ 组合子：

Y mk-fact = mk-fact (Y mk-fact)

接着传递 n 的时候，神奇的事情发生了:

(Y mk-fact) n 

->
(mk-fact (Y mk-fact)) n

->
if n = 1  => 1
else      => n * ((Y mk-fact) (n-1))

如果记 fact = Y mk-fact，则：

fact n =
  if n = 1  => 1
  else      => n * (fact (n-1))

就此得到了阶乘函数 fact 家人们

Y-combinator

$$\lambda f.(\lambda x.fxx)(\lambda x.fxx)$$

这就是 $Y$ 组合子

随便带入一个 $f$：

$$\begin{array}{rlr}& \lambda f.(\lambda x.fxx)(\lambda x.fxx)f& \\ \to & (\lambda x.fxx)(\lambda x.fxx)& \text{which is exactly }(Yf)\\ \to & f(\lambda x.fxx)(\lambda x.fxx)& (fYf)\\ \to & ff(\lambda x.fxx)(\lambda x.fxx)& (ffYf)\\ \to & ...& \end{array}$$

在 apply 一个具体 f 之后，$Y$ 组合子变成了类似 $\Omega$ 组合子 $(\lambda x.xx)(\lambda x.xx)$ 的东西

此式永远能继续规约，不能规约到一个 normal form，因而说它是发散的（diverge)

如果 $Y$ 作用于自身，直接代入即有 $(\lambda f.Yf)Y=(\lambda f.fYf)Y=YY=YYY$

回过头来

我们总结一下寻找 fact 的过程：

首先，先把 fact 写出来

fact = lambda n.
  if n = 1 => 1
  else => n * (fact (n-1))

抽象一下，就是写一个函数体里有 fact 递归调用的函数

fact = ... fact ...     (1)

然后我们假设 fact 是某个函数 g 的不动点，即 g fact = fact

于是 fact = g fact (2)

于是 g fact = ... fact ... (3)，将 (2) 代回 (1) 即得

现在又已知 Y 组合子能求出任意函数的不动点，Y g = g Y g (4)

于是设 Y g = h，则 g h = h (5)，带入 (4) 即得

于是 g h = ... h ... (6)，将 h 作为 fact 代入 (3) 即得

于是 h = ... h ... 将 (5) 代回 (6)

于是解出了阶乘函数（递归函数）h

简直是魔术

Algorithm

算法精深，不可不学

minimum cut maximum flow

jyy老师的图解画的真好

罗列定义

网络流

a flow network is a directed graph $G=(V,E)$ without multiple arcs, where each edge has a non-negative capacity function $c$ and each edge receives a flow.

if 2 nodes are distinguished -- one as the source $s$, and the other as the sink $t$, then $(G,c,s,t)$ is called a network flow.

流

$f:V\times V\to \mathbb{R}$，$f(u,v)$ 表示从 $u$ 到 $v$ 的流。其应该满足

1. Skew symmetric constraint. $f(u,v)=-f(v,u)$，符号表示方向。这说明以邻接矩阵表示该图，则该矩阵斜对称
2. Capacity constraint. An arc's flow cannot exceed its capacity. that is $f(u,v)\le c(u,v)$

以上两条定义了 pseudo-flow（不知道中文叫什么，伪流吗？）

再加上第三条约束则定义了 feasible flow, or just a flow:

3. Flow conservation constraint, 流量守恒，除了 $s,t$ 之外，其余节点都应满足输入等于输出

割

a Cut $C=(S,T)$ is the set $\{(u,v)\in E|u\in S,v\in T\}$

也就是割只关心从 $S$ 到 $T$ 的边，反方向的边是不关注的。

the capacity of an s-t cut is defined as the sum of the capacity of each edge in the cut-set.

残量网络

添加一个流之后网络剩下的容量视为一个新网络. $c_f(u,v)=c(u,v)-f(u,v)$

增广路径

即找一条从 $s$ 到 $t$ 的路径。

注意流函数 $f$ 可以为负数，$f(u,v)<0$ 说明 $f(v,u)>0$，从 $f(u,v)=-f(v,u)$ 和 $0\le f(v,u)\le c(v,u)$ 的约束中可以得到 $$-c(v,u)\le f(u,v)\le 0$$

这描述了 $f(u,v)$ 的合法范围，这个流可以看作在容量为 $[-c(v,u),0]$ 的管道中流动

每一条新的流量为 $k$ 的增广路径 $P$ 都不过是在 $P$ 上每一条边加上一点流量 $k$。只要 $k+f(u,v)\le 0$，这条路径就是合法的。

Ford-Fulkerson 增广

我记得之前看的资料都把这个算法描述为增广的同时添加一条反向边

jyy 老师的讲解中增加了一个图解：

如果把流经一个割两侧的流量之和称为这个割的流量，那么对每一个割来说，每一次增广都一定会增大这个割的流量

• 问: 一个网络流的任意的割都有相同流量吗？

• 答: 是的。这是显然的，因为一个割把网络流图分割为两部分，而所有从 $s$ 出发的流一定会流到 $t$，因此任意的割的流量都是相等的

虽然割的流量都是相等的，但是割的容量不一定是相等的，它取决于这个割有哪些边

每次增广后，都考虑残差网络的割

• 问: 若一个网络所有割的容量都大于 $0$，则一定可以增广吗？
• 答: 是的。这个过程很好想象，画图如下：

这个过程中有一个小细节：每一次连接割中两个点 $u,v$，$u$ 并不总是上一次连接进去的点

然而，可以归纳地保证，每一次新连进去的点 $v$，必有一条从 $s$ 到 $v$ 的增广路径

因而每一次新取的割中 $S$ 里的每一个点都能从 $s$ 出发走到

因此，在增广过程的最后连接 $t$，这保证了有一条从 $s$ 到 $t$ 的路径

最大流最小割定理

上面说明了若一个网络所有割的容量都大于 $0$，则一定可以增广

因此，通过不断的增广，最终会使得残差网络中的所有割当中，至少有一个割，容量为 $0$

显然，按此割来分割原网络流：

不可能有更大的流了，因而得到了最大流

同时，显然不可能有比它容量更小的割

总结

这么看下来好像也没有特别难以理解的地方，可能还是没有做题，检验不出来

如果能很自然地接受负数流，进而理解增广路径的过程，那么接下来就一路平坦了

tarjan

理解 tarjan 和缩点

写了个证明在知乎：Tarjan scc 证明

tarjan 求强连通分量

理解这个过程的关键在于以 dfs 搜索树和搜索栈的视角来看待图遍历

众所周知 dfs 一个图的过程可以看作一棵树

• 问：如果树的一个节点 $a$ 可以延申一条边到 $b$，$b$ 是 $a$ 的祖先，说明什么
• 答：说明 $7$ 和 $3$ 位于同一个强连通分量

• 问：如果 $b$ 不是 $a$ 的祖先，说明什么
• 答：看情况，$11$ 能连 $7$ 说明 $7$ 和 $11$ 在同一个强连通分量，而 $9$ 能连 $5$ 什么也说明不了

• 问：是什么造成了这种差异
• 答：因为 $7$ 与 $3$ 强连通，$3$ 是 $11$ 的祖先

• 问：强连通说明什么
• 答：$a$ 和 $b$ 强连通，从某种意义上可以将 $a$ 与 $b$ 看作同一个点

• 问：然后呢
• 答：所以 $7$ 实际上可以看作就是 $11$ 的祖先

• 问：有个问题，如果 dfs 的过程中，先发现 $11$ 能连接 $7$，然后才发现 $7$ 能连 $3$，可怎么办
• 答：这种情况不会出现

• 问：为什么
• 答：因为如果 $11$ 和 $3$ 在同一个强连通分量，那么当 $11$ 还在搜索栈里的时候，一定有办法碰到 $3$

• 问：也就是说不可能出现 $11$ 没发现 $3$ 跟自己在同一个强连通分量里，反而要通过后续的 $7$ 来间接发现的情况
• 答：对

• 问：所以当看到 $9$ 能碰到 $5$ 的时候直接无视就好了
• 答：对。因为如果 $9$ 能碰到 $5$，但 $5$ 又不在 $9$ 的子树里，这说明 $5$ 已经遍历完了。 这也说明 $9$ 不在 $5$ 的子树里。所以假如 $5$ 能与 $9$ 强连通，那么唯一的可能是他们都至少与 $2$ 强连通，$2$ 是他们的公共祖先

• 问：所以即使 $a$ 和 $b$ 强连通，他们也有可能不在对方的子树里
• 答：对。可以想象这样一种情况：$a$ 和 $b$ 强连通，但他们之间仅仅由一个节点 $c$ 连接，没有其他互相到达的路径。如果此时 dfs 不巧以 $c$ 作为二者的祖先来遍历，那么由于每个节点都只在 dfs 中出现一次，$a$ 和 $b$ 不能通过 $c$ 来互相抵达

• 问：是搜索剪枝导致它这样的
• 答：是的

• 问：那假如 $5$ 和 $9$ 强连通，则他们一定都与 $2$ 强连通吗？我的意思是，他们有没有可能通过其他节点来连接起来
• 答：可以分情况解答：
  1. 若 $9$ 和他们其他的公共祖先，比如 $1$ 强连通，那么 $9$ 一定和 $2$ 也强连通，这很显然
  2. 若 $9$ 和 $5$ 通过 $4$ 强连通起来，那么在 dfs 的过程里，$4$ 应该是 $5$ 和 $9$ 的公共祖先，这与现在的情况矛盾

• 问：我再想想 #沉淀
• 答：如果从结果倒推，当 dfs 接触到一坨强连通分量时，碰到的第一个节点 $a$ 就应该是该强连通分量里其他所有节点的祖先。这很自然，因为从 $a$ 一定能到达其余所有节点

• 问：也就是说，从直观上来看，一个强连通分量在 dfs 树上一定也是连通的
• 答：是的，只要 dfs 搜索树长成了这样，并且 $2$ 和 $1$ 不连通，那么就算 $5$ 跟 $1,3,7$ 连出了花，他们也一定不连通

• 问：因为如果 $5$ 和 $1$ 连通，那么他们一定都和 $2$ 连通。同样如果 $5$ 和 $3$ 连通，则他们要么一方在另一方的子树里，要么有连通的公共祖先
• 答：对

• 问：是不是如果 $a$ 和 $b$ 在不同的子树，但他们连通，则他们一定有且仅有唯一的公共祖先
• 答：并不，比如他们可以和最小公共祖先的父节点也连通

单调性

先看问题，再来总结

单调栈

leetcode.P84

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

这题关键在于分析这个图：

假如枚举以每个矩形为天花板所能取到的最大面积，问题就转换为如何快速找到左侧和右侧的第一个比当前矩形更矮的矩形

线性序列找第一个大于/小于当前值的值，立刻想到单调栈，问题在于

1. 该维护递增栈还是递减栈
2. 能不能扫一次就得到左右的信息

首先看看如果维护一个递减栈，当迭代到 now 时，栈中有什么值

显然栈里是一个递减序列，如果用语言来描述，栈 stk 满足：

• 栈中任意一个元素 x，其下方的元素 y 是 x 左侧的第一个更大值

显然这和我们要维护的信息是相悖的，譬如上图中，到 now 时左侧蓝色矩形会被直接丢弃

我们再看维护一个递增栈，对称地可以知道，栈中元素应该满足下方元素是上方元素左侧的第一个更小值，这正是我们要求的

因而此题应该维护一个递增栈

再看第二个问题，能不能在维护栈的过程中同时得到右侧第一个更小值

这个问题看似不那么重要，只是一种可选的优化，然而其也蕴含了重要的性质。

答案是可以。

考虑递增栈的更新过程，蓝色代表栈中元素，现在迭代到绿色 now：

则 now 将挤掉栈中的顶部两个蓝色矩形，

综上，单调栈（递增栈）具有以下性质：

1. 栈中元素 x 下方是 y，则 y 是 x 左侧的第一个更小元素
2. 迭代到 x 后，x 一定是栈顶元素
3. 迭代到 x 时，x 挤掉了 y, z，则 x 一定是 y, z 的右侧第一个更小元素，并且一定不是其他任何元素的右侧第一个更小元素

单调队列

fft

理解完了之后试试高精度

比较树

copy 自邓俊辉《数据结构（第三版）》 2.7.4

基于比较的算法，即 CBA(comparison-based algorithm)，其执行情况可以用一棵比较树来描述，利用比较树的叶子节点数和树高度可以很直观地感觉到基于 CBA 的算法的下界

称苹果

三个苹果 A, B, C 中有一个的重量不同，用一杆称最少称几次才能找出不同的重量

基于比较树这样考虑：最终结果有三种，分别是 A 重量不同，B 重量不同，C 重量不同，因而比较树最少有三个叶子节点，因而树高度必然大于等于 2，于是不可能只比较一次就得到答案

CBA 排序下界

排序结果最坏情况下一共有多少种？

答案是 $n!$

因此比较树的高度不小于 $\log (n!)$

基于 stirling 近似，可以得到比较树的高度不低于 $\log (\sqrt{2\pi n}(\frac{n}{e}{)}^n)=\log (\sqrt{2\pi n})+n\log \frac{n}{e}$

于是确定了一个下界

从结果种数倒推

就像把有 $f(n)$ 个元素的集合分为 $n$ 个非空集合，至少需要分多少次一样

信息论

十位二进制数 0b0101001111，让人随机猜数，猜对的概率是 $\frac{1}{2^{10}}$

如果告诉他第一位是 0，那么他猜对的概率上升到 $\frac{1}{2^9}$

可知，如果告诉他全部 10 位，则猜对的概率为 $1$

比较树就可以看作这样一个逐渐获取信息的过程：一共 $n$ 种结果，其中只有一个是对的，那么猜中它的概率就是 $\frac{1}{n}$

将 $n$ 种结果看作 $[0,n-1]$ 这 $n$ 个数字，比较树的每一层就像获取了正确答案的二进制的一位，要保证获取到能唯一确定正确结果的信息量，就至少要获取 $\log n$ 位信息

hashmap 的一些问题

问题来源自邓俊辉《数据结构》的 ppt

lazy-deletion

在线性试探型的 hashmap 中，其采用了一个 bitmap 来记录被删去的元素

这并非真的是因为删除元素的开销大，而是因为若真的删除，会导致连续区间断开，可能查找失败

素数平方取值

1. $\{0,1,2,3,...{\}}^2\mathrm{mod}M$，$M$ 非素数，此时同余类可能少于 $\lceil M/2\rceil$
2. $\{0,1,2,3,...{\}}^2\mathrm{mod}P$，$M$ 是素数，此时同余类等于 $\lceil P/2\rceil$

首先，全体整数平方的模 $P$ 同余类，等价于 $\{0,1,2,...,P-1{\}}^2$ 的模 $P$ 同余类，这是显然的

然后，当 $P$ 是素数时，$(P-n{)}^2=P^2-2Pn+n^2$ 与 $n^2$ 模 $P$ 同余，因而同余类至多有 $\lceil P/2\rceil$ 种

取 $a,b\in \{0,1,2,...,\lceil P/2\rceil -1\}$ 且 $a>b$

若 $a^2\equiv b^2\mathrm{mod}P$，则 $P|(a^2-b^2)=(a-b)(a+b)$，矛盾

两个方向取值

$\{0,-1,1,-4,4,9,-9,...,-\lfloor P/2{\rfloor }^2,\lfloor P/2{\rfloor }^2\}$ 模 $P$ 构成完全剩余系，当且仅当 $P\equiv 3\mathrm{mod}4$

证明：

取 $a<b$，只需证明 $p|b^2+a^2$ 不成立

反证

模 $p$ 取逆，有 $p|(b/a{)}^2+1$，记 $A=b/a$，则

$$p|A^4-1$$

即 $A^4\equiv 1\mathrm{mod}p$

于是由费马小定理 $A^{p-1}\equiv 1\mathrm{mod}p$，知 $4|p-1$，即 $p\equiv 1\mathrm{mod}4$，与 $p\equiv 3\mathrm{mod}4$ 矛盾

ppt 的证明

它没完全证明，不知道为什么

给的引理是

1. 奇素数 $p$ 可以写为平方和当且仅当 $p\equiv 3\mathrm{mod}4$
2. $n$ 可表示为整数平方和，当且仅当其每一个模 $4$ 余 $3$ 的素因子都是偶数次方

ppt 上的第二条没完全证明，缺少一个引理：

若 $a,b$ 互素，则 $a^2+b^2$ 只有模 $4$ 余 $1$ 的素因子

设 $n=a^2+b^2$，且 $p|n$，$p\equiv 3\mathrm{mod}4$，则设 $gcd(a,b)=q$，有

$$n=a^2+b^2=q^2(c^2+d^2)$$

其中 $c,d$ 互素，于是 $p$ 必不为 $c^2+d^2$ 的因子，于是必为 $q^2$ 的因子，于是 $p^2$ 必为 $q^2$ 的因子

huffman 编码的证明

一堆字符 $\Sigma =\{...\}$，每个字符都有一个出现频率，可以直接视作权值

一个字符出现频率越低，则权值越低

huffman 二叉树的目的是找出一种 PFC，使得整棵编码树的加权和 $\text{wald}(\Sigma )$ 最小

有两个关键点，两个关键点都很关键，毕竟，证明任何关键问题的关键过程当中最关键的一点就是要找准关键点

1. huffman 二叉树当中，权值最小的两个字符 $v_1,v_2$ 必然在最底层，且互为兄弟

huffman 树没有度为 $1$ 的节点

2. 将 $v_1,v_2$ 替换为字符 $z$，$z$ 的权值为 $v_1,v_2$ 之和，则 $\text{wald}(\Sigma )-\text{wald}(\Sigma -\{v_1,v_2\}+\{z\})=\text{wald}(v_1)+\text{wald}(v_2)$，这是一个常数

由于 1，所以 $v_1,v_2$ 不可能分开，因而必然可以看作一个整体，从而当且仅当新的字符集取得最小加权和时，$\text{wald}(\Sigma )$ 取得最小值

导弹拦截和二维偏序

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

input: 
389 207 155 300 299 170 158 65

output : 
6
2

导弹之间形成了一个二维偏序关系，两个维度分别为发射时间先后和高度 (time, height)

分别以其为横轴和纵轴可以画出下图：

   ▲
   │
   │                                              │
   │        ▼ 399                                 │
   │                         ▼ 300                │
   │                            ▼ 299             │
   │             ▼ 207                            │
   │                                 ▼ 170        │
   │                                     ▼ 158    │
   │                  ▼ 155                       │
   │   ───────────────────────────────────────────┼────
   │                                              │ ▼ 65
   └───────────────────────────────────────────────────────────────►

可以看出假如不保留足够的信息，无法区分 65 这个导弹的上家是拦截 155 还是 158 更好，因而这里不能考虑贪心

朴素 dp

迭代到 65 时，不会考虑此前高度小于 65 的导弹，也不会考虑在 65 之后才要拦截的导弹，因而只需要考察上方图中 65 左上侧的导弹

于是有一个很简单的 dp 思路：以 dp1[i] 表示拦截第 i 个导弹的最长序列长度，则

$$dp1[i]=\max \{dp1[j]+1|j<i,\text{height[j]}\ge \text{height[i]}\}$$

树状数组

可以看到，如果能够考虑从 158 这个导弹接龙，则一定不用考虑从 170 这个导弹接龙，因为 170 在 158 的左上侧

这说明有重复信息可以利用，有优化空间

重新审查迭代过程，发现可以通过维护一个区间的值来利用这个信息：

当 155 高度的导弹迭代完成时，以其结尾的导弹序列长度为 dp2[155]，则此后高度在 [1, 155] 之间的导弹，起码能成为长度 dp2[155] + 1 的导弹序列结尾

因此，通过维护 [1, height[i]] 的区间最大值，可以立刻得到新导弹能接上的最长序列

可以通过树状数组来维护这样的区间值

单调性

可以看出，上方树状数组的做法中，若以 max[i] 表示 [1, i] 的区间最大值，则其是一个单调不增序列，这是由它的定义决定的

其实这里已经没有什么优化空间了，因为维护这样的区间最值，基本上也就是树状数组这个数据结构的最大能力了

其他题解不用树状数组的，基本上都是利用了这个单调性：

回过头来看上面的二维偏序图，不能仅仅维护图中的凸包络面：

  ▲
  │        ▼
  │                              ▼
  │                      ▼    ▼    x
  │           ▼    ▼   ▼  ▼      x
  │                      ▼
  │               ▼
  │                  ▼       y
  │       ▼       ▼     ▼      x4
  │ ▼    
  │    ▼
  │             x3
  │          x2
  │  x1
  │                                          A
──┴─────────────────────────────────────────────────────────►

图中迭代到 A 时，不能仅考察标为 x 的所有点，尽管其余所有点都包络在这些点的左上侧。（反例是接下来来了一个高度在 [x4, y] 之间的点）

实际上，所有在 “最右侧” 的点，都应该维护，唯一能保证可以丢弃的只有高度相同的点：

  ▲
  │        x
  │                              x
  │                      ▼    ▼    x
  │           ▼    ▼   ▼  ▼      x
  │                      x
  │               x
  │                  ▼       x
  │       ▼       ▼     ▼      x4
  │ x    
  │    x
  │             x3
  │          x2
  │  x1
  │                                          A
──┴─────────────────────────────────────────────────────────►

（所有标为 x 的点，接下来都有可能用到）

与此同时，这些点当中也有点可以不必维护：比如 x1, x2, x3 的最长导弹拦截序列都是 2，假如

1. A 同时小于这三者，则这三者对于 A 来说是等价的
2. 但如果 A 小于 x3 却大于 x2，则只需要考虑 x3，而不必考虑 x1, x2

因此，x3 是一定要保留的，而 x1, x2 却是可有可无的，综上，在这条包络线当中，对于最长序列长度相等的点，只需维护其中高度最高的点

或者，由于题目没有要求输出具体点，因而只需要维护最高高度，而不必关注具体是哪个点

于是仅仅需要维护 dp3[i] 表示长为 i 的拦截序列的尾部最大高度。这已经是需要维护的最少的信息

可以看出这个信息与上方树状数组中单调性等价：其实质是维护区间最大值的端点

同样可以看出，随着迭代过程，对于任意长度 i，dp3[i] 是只增不减的，这对应了上方树状数组的区间端点只增不减

第二问

据说有 Dilworth 定理，其在此题中的体现是：

将一个序列剖成若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数

我这里是直接贪心

代码（树状数组）

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

const int MAX_VALUE = 5e4 + 50;

template <std::size_t N> struct BIT {
  int c[N] = {0};

  static inline int lowbit(const int x) { return x & -x; }

  /// update value in [1, i] with n
  void update(int n, int i) {
    while (i > 0 && c[i] < n) {
      c[i] = n;
      i -= lowbit(i);
    }
  }

  int get(int i) {
    int ans = 0;
    while (i <= N) {
      ans = std::max(ans, c[i]);
      i += lowbit(i);
    }
    return ans;
  }
};

int main() {
  int n = 0;

  int a[(int)1e5 + 50];

  while (std::cin >> a[n++]) {
  };
  n -= 1;

  if (n == 0) {
    std::cout << "0\n0" << std::endl;
    return 0;
  }

  auto bit = BIT<MAX_VALUE>{};

  for (int i = 0; i < n; i++) {
    bit.update(bit.get(a[i]) + 1, a[i]);
  }

  auto v2 = std::vector<int>{a[0]};

  for (int i = 1; i < n; i++) {
    auto tmp = std::lower_bound(v2.begin(), v2.end(), a[i]);
    if (tmp == v2.end()) {
      v2.push_back(a[i]);
    } else {
      *tmp = a[i];
    }
  }

  std::cout << bit.get(1) << std::endl << v2.size();

  return 0;
}

互斥锁，信号量，以及管程

Mutex

等价于二值信号量，即 Semaphore(cnt = 1, limit = 1)

Semaphore

Dijkstra 作为荷兰人给它两个操作起名 P, V，但我看大伙好像都叫它 accquire, release

accquire 时阻塞

Monitor (Conditional Variable)

管程，其实压根没看这是啥，

经典同步问题

写的测试工具

也许不该用 Rust 来写，它编译的时候多线程环境就要求 Sync + Send，有时候显得我加的东西多此一举，比如读者优先的读写问题

math

learned person cast great shadow

基本是考研数学里的一些笔记

一胆二力三功夫

三手都要抓，三手都要硬

虽然天赋很重要，但是还是要学呀

概念与技巧

概念揭示了你该关注什么，技巧教你怎么去关注

Jacobi 行列式和隐函数存在定理

二元函数隐函数存在定理

这个定理是局部的，邻域的：

$F(x,y)$ 连续可微，方程 $F(x,y)=0$ 在 $(x_0,y_0)$ 附近满足 $\frac{\partial F}{\partial y}\ne 0$，则其附近存在一个邻域内能唯一确定一个函数 $y=f(x)$

证明：

由于 $F(x,y)$ 连续可微，则其偏导连续，即 $F_y$ 连续

不妨设 $F_y(x_0,y_0)>0$，则，直觉上说，其附近能找到一个方块邻域 $[x_0-a,x_0+a]\times [y_0-b,y_0+b]$，在这块区域里 $F_y(x,y)>0,F(x_0+a,y)>0,F(x_0-a,y)<0$

由于偏导恒正，于是竖向上 $F$ 单增，因而能确定唯一的一条连续曲线使得 $F(x,y)=0$，该曲线必有 $x$ 能确定一个唯一的 $y$

反过来说

反过来说，$\frac{\partial F}{\partial y}=0$ 并不一定就不存在唯一隐函数，譬如 $x+y^3=0$， 在 $(0,0)$ 附近其偏导 $\frac{\partial F}{\partial y}>=0$

二元函数中的隐函数相关问题

把微分以向量看待，全微分和偏导之间的关系很有意思

一阶偏导

$$F(x,y,z)=0⟹\frac{\partial F}{\partial x}+\frac{\partial F}{\partial z}\frac{\partial z}{\partial x}=0$$

我觉得这个式子的推导应该来自于全微分：

$$\begin{array}{rl}dF(x,y,z)& =d0=0\\ & =\frac{\partial F}{\partial x}dx+\frac{\partial F}{\partial y}dy+\frac{\partial F}{\partial z}dz\\ & =\frac{\partial F}{\partial x}dx+\frac{\partial F}{\partial y}dy+\frac{\partial F}{\partial z}(\frac{\partial z}{\partial x}dx+\frac{\partial z}{\partial y}dy)\end{array}$$

因此，如果对 $x$ 求偏导，则 $dy=0$，于是上式变为:

$$dF(x,y,z)=\frac{\partial F}{\partial x}dx+\frac{\partial F}{\partial z}\frac{\partial z}{\partial x}dx=0$$

上面的推导没有对 $x,y$ 的约束，因此这二者可以不必正交

二元函数上的曲线

如果二元函数 $f(x,y)$ 上由 $f(x,y)=0$ 确定了一条曲线 $l$

考虑 $l$ 方向的方向导数乘上 $l$ 的全微分（$l$ 方向上的导数实际上是 $0$)

$$\begin{array}{r}\frac{\partial f}{\partial l}dl=\frac{\partial f}{\partial l}(\frac{\partial l}{\partial x}dx+\frac{\partial l}{\partial y}dy)\end{array}\text{\hspace{1em}(1)}$$

再对比直接考虑 $f$ 的全微分：

$$\begin{array}{r}df=\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy\end{array}\text{\hspace{1em}(2)}$$

在 $l$ 方向上 $df=0$，由此得到

$$\frac{dy}{dx}=-\frac{\partial f}{\partial x}/\frac{\partial f}{\partial y}$$

但从 $(1)$ 式无法推出 $\frac{dy}{dx}$

$(1),(2)$ 两式的区别在哪。或者问 $(1),(2)$ 两个式子谁蕴含的信息更多

把 $(2)$ 式用 $l:y=l(x)$ 写为

$$\begin{array}{rl}df(x,l(x))& =\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial l}dl\\ & =\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial l}\frac{dl}{dx}dx\end{array}$$

此式中的微分含义不再是全微分：既然用 $y=l(x)$ 来约束了 $x,y$ 之间的关系，则在特定点处该微分即为该点处 $l$ 方向的方向导数

可见全微分

连续，偏导，可微

• 二元函数 $f(x,y)$ 在 $(x_0,y_0)$ 处连续，啥都推不出来，例如：

$$f(x,y)=\sqrt[4]{x^2+y^2}$$

在 $(0,0)$ 连续，偏导不存在，不可微

• 偏导存在并连续，则必可微

当全微分指向从 $(a,b)$ 到 $(c,d)$ 方向时，其值为该方向的方向导数

如果 $(a,b)$ 点处偏导数存在且连续，则 $(a,b)$ 附近有一块包含 $(c,b)$ 的邻域，满足 $f_Y(c,b)\to f_Y(a,b)$

在无穷小的情况下，有如下近似：

$$\begin{array}{rl}{f}_{(a,b)\to (c,d)}^{\prime }(a,b)& =\underset{(c,d)\to (a,b)}{\lim }\frac{f(c,d)-f(a,b)}{||(c,d)-(a,b)||}\\ & =\underset{(c,d)\to (a,b)}{\lim }\frac{f(c,d)-f(c,b)+f(c,b)-f(a,b)}{||(c,d)-(a,b)||}\\ & =\underset{(c,d)\to (a,b)}{\lim }\frac{f(c,d)-f(c,b)}{||(c,d)-(c,b)||}\frac{||(c,d)-(c,b)||}{||(c,d)-(a,b)||}+\frac{f(c,b)-f(a,b)}{||(c,b)-(a,b)||}\frac{||(c,b)-(a,b)||}{||(c,d)-(a,b)||}\\ & =\underset{(c,d)\to (a,b)}{\lim }{f}_Y(c,b)\frac{||(c,d)-(c,b)||}{||(c,d)-(a,b)||}+f_X(a,b)\frac{||(c,b)-(a,b)||}{||(c,d)-(a,b)||}\\ & =f_Y(a,b)\sin \alpha +f_X(a,b)\cos \alpha \end{array}$$

于是该方向的方向导数能用偏导线性表示

如果所有方向的方向导数都能用偏导数来同样的线性表示，那么称之为可微

用一个向量来表示这样的方向导数，称为该函数的全微分

上面这个同样的不太好描述清晰，举例而言，二元函数，也就是三维空间上的函数，其全微分应该处于由两个偏导数所张成的切平面上

从切平面上逼近切点，距离函数的差值是距离点的度量的高阶无穷小

换言之切点附近可以用切面去近似这个函数

如果用 Jacobi 行列式 $J$ 则更好说明。可微定义为：

$$\underset{\overrightarrow{h}\to \overrightarrow{(0,0)}}{\lim }\frac{||f(\overrightarrow{x})-f(\overrightarrow{x}+\overrightarrow{h})||-||J(\overrightarrow{h})||}{||\overrightarrow{h}||}=0$$

其中 $J(\overrightarrow{h})$ 就代表了全微分，相当于切面，而左边则是方向导数

注意 上方推导过程中，直到最后一步，都不要求 $x,y$ 垂直。从概念上看，只需两个偏导方向能张成所需空间即可

例如：已知 $f(x,y)$ 可微，且

$$\begin{gathered} f(x+1,\ln (x+1))=(1+x{)}^3+x\ln (1+x)(x+1{)}^{\ln (1+x)} \\ f(x^2,x-1)=x^4{e}^{x-1}+(x-1)(x^2-1)x^{2(x-1)} \end{gathered}$$

求 $df(1,0)$

• 可微不一定偏导连续

在一元函数上类比这句话，即可导不一定导数连续，这在一元函数上也是对的，如：

$$\begin{array}{rl}& f(x)=\{\begin{array}{ll}{x}^2\sin \frac{1}{x},& \text{others}\\ 0,& (0,0)\end{array}\\ \to & f^{\prime }(x)=\{\begin{array}{ll}2x\sin \frac{1}{x}-\cos \frac{1}{x},& \text{others}\\ 0,& (0,0)\end{array}\end{array}$$

其中

$$\begin{array}{rl}{f}^{\prime }(0)& =\underset{x\to 0}{\lim }\frac{x^2\sin \frac{1}{x}-0}{x-0}\\ & =\underset{x\to 0}{\lim }x\sin \frac{1}{x}\\ & =0\end{array}$$

也即 $f(x)$ 在 $x=0$ 处可导，并且导函数等于 $0$，然而在 $x=0$ 点处 $f^{\prime }(x)$ 其实又是震荡的，并不连续

将这个例子扩展到二元函数

$$f(x,y)=\{\begin{array}{ll}(x^2+y^2)\sin \frac{1}{x^2+y^2},& \text{others}\\ 0,& \text{(0, 0)}\end{array}$$

就得到了可微但偏导数不连续的例子

泰勒级数与递归的柯西中值

若 $f(x)$ 在一段区间上连续，则

$$\begin{array}{rl}f(x)& =f(x_0)+f^{\prime }(\xi )(x-x_0)\end{array}$$

若 $f(x)$ 在区间上无穷可微，则

$$\begin{array}{rl}f(x)& =f(x_0)+f^{\prime }({\xi }_1)(x-x_0)\\ & =f(x_0)+(f^{\prime }(x_0)+f^{\prime \prime }({\xi }_2)({\xi }_1-x_0))(x-x_0)\\ & =f(x_0)+f^{\prime }(x_0)(x-x_0)+f^{\prime \prime }({\xi }_2)({\xi }_1-x_0)(x-x_0)\\ & =f(x_0)+f^{\prime }(x_0)(x-x_0)+f^{\prime \prime }(x_0)({\xi }_1-x_0)(x-x_0)+f^{\prime \prime }({\xi }_3)({\xi }_2-x_0)({\xi }_1-x_0)(x-x_0)\\ & =f(x_0)+f^{\prime }(x_0)(x-x_0)+f^{\prime \prime }(x_0)({\xi }_1-x_0)(x-x_0)+f^{\prime \prime }(x_0)({\xi }_2-x_0)({\xi }_1-x_0)(x-x_0)+f^{\prime \prime }({\xi }_4)({\xi }_3-x_0)({\xi }_2-x_0)({\xi }_1-x_0)(x-x_0)\\ & =...\end{array}$$

看起来与泰勒展开很像，但是仍有差距，只能说上面的本意是好的，都是下面的人执行歪了

拉格朗日余项

出于简便考虑，这里全部取 $x_0=0$

$$f(x)=f(0)+f^{\prime }(0)x+\frac{f^{\prime \prime }(0)}{2!}{x}^2+\frac{f^{(3)}(0)}{3!}{x}^3+\frac{f^{(4)}(\xi )}{4!}{x}^4$$

其中 $\frac{f^{(4)}(\xi )}{3!}{x}^3$ 称为拉格朗日余项，记为 $R_4(x)$

下面证明上式，构造 $F(x)$：

$$F(x)=f(x)-(f(0)+f^{\prime }(0)x+\frac{f^{\prime \prime }(0)}{2!}{x}^2+\frac{f^{(3)}(0)}{3!}{x}^3)$$

则 $F(x)$ 有性质 $F(0)=F^{\prime }(0)=F^{\prime \prime }(0)=F^{(3)}(0)=0$，且对于更高阶导，$F^{(4)}(x)=f^{(4)}(x)$

由柯西中值定理：

$$\begin{array}{rl}F(x)& =F(x)-F(0)\\ & =x^4\frac{F(x)-F(0)}{x^4-0}\\ & =x^4\frac{F^{\prime }({\xi }_1)}{4{\xi }_1^3}\\ & =x^4\frac{1}{4}\frac{F^{\prime }({\xi }_1)-F^{\prime }(0)}{{\xi }_1^3-0}\\ & =x^4\frac{1}{4}\frac{F^{\prime \prime }({\xi }_2)}{3{\xi }_2^2}\\ & ...\\ & =x^4\frac{1}{4}\frac{1}{3}\frac{1}{2}\frac{F^{(4)}({\xi }_4)}{{\xi }_4^0}\\ & =\frac{x^4}{4!}{F}^{(4)}({\xi }_4)\\ & =\frac{x^4}{4!}{f}^{(4)}({\xi }_4)=R_4(x)\end{array}$$

从拉格朗日余项到皮亚诺余项

对拉格朗日余项取极限是显然的

$$\underset{x\to 0}{\lim }\frac{f(x)}{x^3}=\underset{x\to 0}{\lim }\frac{x}{4!}{f}^{(4)}({\xi }_4)=0$$

显式递归

$$\begin{array}{rl}f(x)& =f(x_0)+(x-x_0)\frac{f(x)-f(x_0)}{x-x_0}\\ & =f(x_0)+(x-x_0)f^{\prime }({\xi }_1)\\ & =f(x_0)+(x-x_0)f^{\prime }({\xi }_1)\end{array}$$

推广的积分中值定理 偷自 wiki

$f(x)$ 在 $[a,b]$ 上连续，$g(x)$ 在其上非负，则

$${\int }_a^{b}f(x)g(x)dx=f(\xi ){\int }_a^{b}g(x)dx$$

思路

$f(x)$ 把 $[a,b]$ 连续地映射到 $[m,M]$ 上

证

可知 $m\le f(x)\le M$，于是 $m{\int }_a^{b}g(x)dx\le {\int }_a^{b}f(x)g(x)dx\le M{\int }_a^{b}g(x)dx$

由介值性知存在 $\xi \in [a,b]$ 满足

$$f(\xi )=\frac{{\int }_a^{b}f(x)g(x)dx}{{\int }_a^{b}g(x)dx}$$

于是

$$f(\xi ){\int }_a^{b}g(x)dx={\int }_a^{b}f(x)g(x)dx$$

得证

一些极限题目

$$\lim \frac{n+n^2+n^3+...+n^n}{1^n+2^n+3^n+...+n^n}$$

夹逼，泰勒，等价无穷小，答案是 $\frac{e-1}{e}$

$$\underset{x\to 0}{\lim }\frac{{\int }_0^x\cos t^{2}dt}{x}$$

洛必达

同阶无穷小的归化

$$x^3+x^4\sim x^3$$

$x^4$ 是比 $x^3$ 高阶的无穷小，这指的是其收敛到 $0$ 的速度更快

若 $\lim \frac{a_n}{b_n}=0$，则称 $a_n$ 是 $b_n$ 的高阶无穷小

由极限的四则运算知 $\lim a_n=\frac{1}{\lim 1/a_n}$，因而两个无穷小之间的关系，要么是同阶（即比值极限为实数），要么互为高阶/低阶无穷小

$$\underset{x\to 0}{\lim }\frac{x^3+x^4}{x^3}=1+0=1\ne 0$$

拉格朗日中值

函数 $f(x)$ 相同，且 $x$ 逼近时，可以利用拉格朗日中值，将一个无穷小转化到另一个无穷小：

$$\begin{array}{rl}& \underset{x\to 0}{\lim }\ln (x+\sqrt{1+x^2})-\ln (1+x)\\ =& \underset{x\to 0}{\lim }\frac{1}{\xi (x)}((x+\sqrt{1+x^2})-(1+x))\\ =& \underset{x\to 0}{\lim }\frac{\sqrt{1+x^2}-1}{\xi (x)}\\ =& \underset{x\to 0}{\lim }\sqrt{1+x^2}-1\end{array}$$

我不好说，$x+\sqrt{1+x^2}$ 和 $\ln (1+x)$ 同时趋于 $1$，这保证了 $\xi (x)$ 趋于 $1$，因而能得到一个值

$$\begin{array}{rl}& \underset{x\to 0}{\lim }\frac{\ln (x+\sqrt{1+x^2})-\ln (1+x)}{x^2}\\ =& \underset{x\to 0}{\lim }\frac{\sqrt{1+x^2}-1}{x^2}\\ =& \frac{1}{2}\end{array}$$

$$\begin{array}{rl}& \underset{x\to +\infty }{\lim }{x}^2(\ln (x+\frac{1}{x})-\ln x)\\ =& \underset{x\to +\infty }{\lim }{x}^2\frac{1}{\xi (x)}(x+\frac{1}{x}-x)\\ =& \underset{x\to +\infty }{\lim }\frac{x}{\xi (x)}\\ =& 1\end{array}$$

当然这个也可以直接用对数函数变换：

$$\begin{array}{rl}& \underset{x\to +\infty }{\lim }{x}^2(\ln (x+\frac{1}{x})-\ln x)\\ =& \underset{x\to +\infty }{\lim }{x}^2\ln (1+\frac{1}{x^2})\\ =& 1\end{array}$$

如果

$$\begin{array}{rl}\underset{x\to +\infty }{\lim }{x}^2(\ln (x+\frac{1}{x})-\ln x)& =\underset{x\to +\infty }{\lim }{x}^2\frac{1}{\xi (x)}(x+\frac{1}{x}-x)\\ & =\underset{x\to +\infty }{\lim }\frac{x}{\xi (x)}\\ & =1\end{array}$$

$\ln (1+\frac{1}{x})$ 相关的无穷大

$$\begin{array}{rl}& \underset{x\to 0}{\lim }\sqrt{4x^2+x}\ln (2+\frac{1}{x})\\ =& \underset{x\to 0}{\lim }\sqrt{4x^2+x}(\ln (2x+1)-\ln x)\\ =& \underset{x\to 0}{\lim }\sqrt{4x^2+x}\ln (2x+1)-\sqrt{4x^2+x}\ln x\\ =& 0\end{array}$$

减号两侧都是趋于 $0$，其差也趋于 $0$

这里用到了 ${\lim }_{x\to 0}{x}^a\ln x=0$，只需 $a>0$

///

$若f(x)=x+o(x)$ 则 $f^{-1}(x)\sim x$

$$f(x)=\{\begin{array}{ll}x,& x\in \mathbb{Q}\\ -x,& \text{others}\end{array}$$

DE

$$F(x,\varphi (x),{\varphi }^{\prime }(x),{\varphi }^{\prime \prime }(x),...,{\varphi }^{(n)}(x))\equiv 0$$

最高几阶导，称为微分方程的阶

考核范围仅限线性微分方程

微分算子复习

考研范围大概只用掌握以下几类微分方程

• DE
  • 一阶线性
    • 可分离变量
    • 一阶齐次
    • 可化为齐次
    • 【概念】线性微分方程
      • 例：一阶非线性微分方程
  • 特例
    • 欧拉方程
      • 1. 观察可知 $y=x^r$ 是一个特解
      • 2. 另一种解法是通过换元 $x=e^t$
    • 伯努利方程
    • 可降阶的高阶微分方程
      • 1. $y^{(n)}=f(x)$
      • 2. $y^{\prime \prime }=f(x,y^{\prime })$
      • 3. $y^{\prime \prime }=f(y,y^{\prime })$
  • 特定二阶非齐次常系数线性
    • 二阶常系数齐次
    • 二阶常系数非齐次
    • $n$ 阶常系数齐次

一阶线性

可分离变量

$$P(x)dx=P(y)dy$$

解法是显然的

一阶齐次

$$\frac{dy}{dx}=\varphi (\frac{y}{x})$$

可化为齐次

$$\frac{dy}{dx}=\frac{ax+by+c}{a_{1}x+b_{1}y+c_1}$$

通过换元 $x^{\prime }=x+A,y^{\prime }=y+B$ 来将其转化为齐次

$$\frac{ax+by+c}{a_{1}x+b_{1}y+c_1}=\frac{a{x}^{\prime }+b{y}^{\prime }+(c-aA-bB)}{a_1{x}^{\prime }+b_1{y}^{\prime }+(c_1-a_{1}A-b_{1}B)}$$

因此只需通过

$$\{\begin{array}{ll}& c-aA-bB=0\\ & c_1-a_{1}A-b_{1}B=0\end{array}$$

来唯一确定 $A,B$

这个二元方程有四种情况，唯一解，一维任意解，二维任意解，无解

1. 唯一解对应 $A,B$ 系数矩阵可逆，解空间为整个平面
2. 一维任意解对应系数矩阵不可逆，但非零矩阵，同时 $\frac{c}{c_1}=\frac{a}{a_1}$，$(c,c_1)$ 在一维的解空间中
3. 二维任意解对应系数矩阵为零矩阵，同时 $c_1=c=0$，解空间为零点
4. 无解是除以上以外的任意情况，$(c,c_1)$ 不在 $(a,a_1)$ 和 $(b,b_1)$ 张成的向量空间中

只有 1. 需要换元，2. 的微分方程右侧为常数，3. 不可能出现（分母为 0），4. 可以分类讨论以下

1. 系数矩阵秩为 $0$，此时微分方程右侧为常数，或者 $c_1=0$ 时不可能
2. 系数矩阵秩为 $1$，此时微分方程右侧可以化为 $\frac{a}{a_1}+\frac{d}{a_{1}x+b_{1}y+c_1}$

具体例子来说

$$\frac{dy}{dx}=1+\frac{1}{x+y+1}$$

此时设 $u=x+y+1$，则 $dy/dx=d(u-x-1)/dx=du/dx-1$

于是转化为可分离变量的一阶线性微分方程

$$\frac{du}{dx}=2+\frac{1}{u}$$

【概念】线性微分方程

$$a_0(x)y+a_1(x)y^{\prime }+a_2(x)y^{\prime \prime }+...+a_n(x)y^{(n)}=b(x)$$

【同济】形如以下形式的方程称为一阶线性微分方程

$$\frac{dy}{dx}+P(x)y=Q(x)$$

例：一阶非线性微分方程

$$e^y+y^{\prime }=0$$

特例

欧拉方程

柯西-尤拉方程是形式如

$$x^2{y}^{\prime \prime }+bx{y}^{\prime }+cy=0$$ （其中 $b,c$ 是常數）的二階變係數常微分方程。

1. 观察可知 $y=x^r$ 是一个特解

$$\begin{array}{rl}& \frac{dy}{dx}=r{x}^{r-1}\\ & \frac{d^{2}y}{d{x}^2}=r(r-1)x^{r-2}\end{array}$$

于是方程转化为 $$(r(r-1)+br+c)y=0$$

wiki 对于这个二次方程的三个解做了分别讨论

1. 两个不同解时通解为 $y=c_1{x}^{m_1}+c_2{x}^{m_2}$
2. 两个相同解时通解为 $y=c_1{x}^m\ln (x)+c_2{x}^m$
3. 比较复杂，懒得写了，总之是复数

2. 另一种解法是通过换元 $x=e^t$

为什么这里好像假设了 $x>0$ 哦，$t$ 可以是复数，那没事了

微分算子复习

$D\to \frac{d}{dt}$

$Dy=x{y}^{\prime },D(D-1)y=x^2{y}^{\prime \prime }$

原方程转化为 $(D^2-D+bD+c)y=0$

于是变成 $y$ 对 $t$ 的二阶齐次线性微分方程

伯努利方程

$$\frac{dy}{dx}+P(x)y=Q(x)y^n$$

可降阶的高阶微分方程

1. $y^{(n)}=f(x)$

积 $n$ 次即可

2. $y^{\prime \prime }=f(x,y^{\prime })$

设 $y^{\prime }=p$，即有 $\frac{dp}{dx}=f(x,p)$

TODO: $y^{\prime }=e^{xy}$ 似乎也有这种形式，常数变易法能做吗

3. $y^{\prime \prime }=f(y,y^{\prime })$

设 $y^{\prime }=p$，则有

$$\begin{array}{rl}\frac{dp}{dx}& =f(y,p)\\ & =\frac{dp}{dy}\frac{dy}{dx}\\ & =\frac{dp}{dy}p\end{array}$$

转换为 $\frac{dp}{dy}=\frac{1}{p}f(y,p)$

特定二阶非齐次常系数线性

二阶常系数齐次

二阶常系数非齐次

$$a_1{f}^{\prime \prime }(x)+a_2{f}^{\prime }(x)+a_{3}f(x)=e^{cx}(b_1{x}^3+b_2{x}^2+b_{3}x+b_4)$$