Repository navigation
Expand file tree
/
Copy pathexample.typ
More file actions
165 lines (128 loc) · 5.31 KB
/
Copy pathexample.typ
File metadata and controls
165 lines (128 loc) · 5.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// example.typ — 最小使用示例。编译:typst compile example.typ
#import "lib.typ": *
#show: textbook.with(
title: "算法与数据结构",
title-en: "Algorithms and Data Structures",
subtitle: "从数学基础到工程实践 · 中英双语示例",
author: "张 伟 编著",
series: "计算机科学基础系列教材",
publisher: "示例大学出版社",
lang: "zh", // 改为 "en":定理→Theorem、第一章→Chapter 1、目录→Contents……
)
#front-matter[
#preface[
本书演示模板的全部功能:双语章标题、按环境着色的定理系统、带行号与文件名
标签的代码块、控制台输出、书末习题答案自动汇总、索引与 GB/T 7714 参考文献。
正文首行自动缩进两字。
引文与强调使用楷体,例如:#emph[程序是写给人读的,只是顺便让机器执行。]
]
#table-of-contents()
]
#main-matter[
#part("数学基础", en: "Mathematical Foundations")
#chapter("集合与逻辑", en: "Sets and Logic", label: "ch:sets")
#overview[
集合是后续各章共同的语言。本章固定基本运算的记号,完整证明一条定律,
并记下初学者最容易犯的一个错误。
]
集合#index("集合")#gls("集合", def: [由确定的、互不相同的对象组成的整体])是现代数学的通用语言。本章为最小示例,覆盖定义、定理、
命题、引理、证明、注记与习题环境。
== 集合的运算
#definition(title: "并集")[
设 $A, B$ 为集合,定义 $A union B = {x mid(|) x in A or x in B}$。
] <def:union>
#intuition[
对并集取补,剩下的只能是同时逃过两个集合的元素——于是并变成了交。
]
#theorem(title: "德摩根律")[
对任意集合 $A, B$ 与全集 $U$,有
$ (A union B)^c = A^c inter B^c. $ <eq:demorgan>
] <thm:demorgan>
#proof[
任取 $x in (A union B)^c$,则 $x in.not A$ 且 $x in.not B$,
故 $x in A^c inter B^c$;反向包含同理。
]
#lemma[若 $A subset B$,则 $B^c subset A^c$。] <lem:contra>
#proposition[
并对交满足分配律:$A union (B inter C) = (A union B) inter (A union C)$。
] <prop:distrib>
#note[@eq:demorgan 对任意多个集合的并同样成立。]
#pitfall[
「并集的补等于补集的并。」应当是补集的*交*,见 @thm:demorgan。
把两者弄反是初学证明时最常见的失误。
]
只为排版而写的行间公式不应占用编号,用 `unnumbered` 包起来:
#unnumbered[
$ A union B = B union A. $
]
#exercises-heading()
#exercise(solution: [由补集定义逐点验证即可。])[
证明 $(A inter B)^c = A^c union B^c$。
]
#part("程序设计", en: "Programming")
#chapter("排序算法", en: "Sorting Algorithms", label: "ch:sorting")
排序#index("排序", see-also: "算法")#gls("排序", def: [把元素按给定次序重排])是数据处理的基础。快速排序#index("排序!快速排序")#gls($O(n log n)$, def: [快速排序的期望时间复杂度], group: "notation", sort: "O")由 Hoare
提出 @clrs,期望时间复杂度为 $O(n log n)$。内联代码样式:调用
`quicksort(a)` 即可原地排序。
跨章引用按被引对象求值,而不是按引用所在页:集合部分见 @ch:sets,
其核心结论是 @thm:demorgan 与 @eq:demorgan,配套结论有 @lem:contra、
@prop:distrib 与 @def:union;记号见 @app:notation,列于 @tab:notation。
== 快速排序
#code(filename: "quicksort.py", caption: [快速排序的 Python 实现])[
```python
def quicksort(a, lo=0, hi=None):
"""原地快速排序(in-place quicksort)。"""
if hi is None:
hi = len(a) - 1
if lo >= hi:
return
p = partition(a, lo, hi) # 以基准元素划分
quicksort(a, lo, p - 1)
quicksort(a, p + 1, hi)
```
]
#console[```
$ python quicksort.py
输入: [9, 3, 7, 4, 1, 8]
输出: [1, 3, 4, 7, 8, 9]
```]
#algorithm(title: "快速排序", input: [数组 $a$ 与区间 $[l, h]$], output: [升序排列的 $a$])[
+ #alg-if($h - l <= 0$)[
+ #alg-return[]
]
+ 随机选取基准,原地划分,得基准位置 $p$
+ #alg-for([每个子区间 $[l, p-1]$、$[p+1, h]$])[
+ 递归排序该区间
]
] <alg:quicksort>
#example(title: "8 个元素的下界")[
当 $n = 8$ 时,$ceil(log_2 8!) = 16$,故任何比较排序最坏至少需 16 次比较。
] <ex:lower-bound>
上面的步骤是 @alg:quicksort,计数论证是 @ex:lower-bound,二者均按章编号并可按标签引用。
#warning[
最坏情况(已有序输入 + 固定基准)退化为 $O(n^2)$,务必随机化基准。
]
#exercises-heading()
#exercise(solution: [第一轮以 9 为基准划分,之后依次递归;全程共 15 次比较。])[
手工模拟快速排序处理数组 $[9, 3, 7, 4, 1, 8]$ 的全过程,统计比较次数。
]
#exercise[证明:对 5 个互异元素排序,7 次比较既是必要的,也是充分的。]
]
#appendix[
#chapter("数学记号", en: "Notation", label: "app:notation")
#figure(
table(
columns: (auto, 1fr),
[$O(f)$], [渐近上界],
[$Omega(f)$], [渐近下界],
[$Theta(f)$], [渐近紧界],
),
caption: [常用记号],
) <tab:notation>
]
#answers()
// 参考文献路径必须在你自己的文件里解析——传 bytes。
#references(read("refs.bib", encoding: none), full: true)
#make-glossary()
#make-glossary(group: "notation")
#make-index()