泊远的博客

近世代数笔记 半群和幺半群 半群 设代数系(S,∘)(S,\circ)(S,∘)，如果∘\circ∘满足结合律，则称S关于∘\circ∘构成一个半群，记为(S,∘)(S,\circ)(S,∘) 幺半群 有单位元素e的半群(S,∘)(S,\circ)(S,∘)称为独异点或幺半群，记作(S,∘,e)(S,\circ,e)(S,∘,e);然后如果集合S有限，称其为有限幺半群，S的基数被称为幺半群(S,∘,e)(S,\circ,e)(S,∘,e)的阶。 有限半群(S,∘,e)(S,\circ,e)(S,∘,e)是一个幺半群，当且仅当 ∃s,t∈S,sS=S,St=S\exists s,t \in S, sS=S,St=S ∃s,t∈S,sS=S,St=S 元素的幂 幺半群(S,∘,e)(S,\circ,e)(S,∘,e)中，可以定义元素的非负整数幂。∀a∈S\forall a\in S∀a∈S a0=e,an+1=an∘a,n≥0a^0=e,a^{n+1}=a^n\circ a,n\ge0 a0=e,an+1=an∘a,n≥0 幂运算满足普通幂运算的性质，即: 设(S,∘,e)(S, ...

算法设计与分析课后作业 第一讲[200225] 练习题 1.用伪代码写出求整数最大公因子的欧几里得算法 GCD(a,b) 1234r=a%bIf b=0 Then Return bElse Return GCD(b,r) 2.考虑如下伪代码 F(n) 1 if n=1 2 then return 1 3 else return n* F(n-1) 这是计算n！的算法 3.时间复杂度是否是衡量一个算法性能的主要标准，为什么？ 是的，时间复杂决定了执行一个算法的时间资源，那么对选择算法与选择设备有极大的参考意义 4.包含死循环的程序是不是算法，为什么？ 不是算法。因为对于一些输入，它不会停下来。 5.是否可以通过提高算法的时间复杂性来降低其空间复杂性？ 这是可以的。比如桶排序，虽然时间复杂性非常低，但是空间复杂性很高，那么我们可以改成虽然时间复杂度高一点的快速排序，来节约空间。 思考题 在信息产业中算法扮演什么角色？ 信息产业中的算法，就好像人的灵魂，指导信息产业的前进。 第二讲[200227] 练习题 1.证明或否证：f(n)+o(f(n))=Θ(f ...

算法设计与分析笔记 第二讲 增长的阶 描述增长率：忽略低阶项，保留最高阶项，忽略常数。 增长函数 输入规模非常大。常见记号：O,Θ,Ω,o,ωO,\Theta,\Omega,o,\omegaO,Θ,Ω,o,ω 同阶函数集合 定义Θ(g(n))={f(n)∣∃c1,c2>0,n0,∀n>n0,c1g(n)≤f(n)≤c2g(n)}\Theta(g(n))=\{f(n)|\exists c_1,c_2>0,n_0,\forall n>n_0,c_1g(n)\le f(n)\le c_2g(n)\}Θ(g(n))={f(n)∣∃c1​,c2​>0,n0​,∀n>n0​,c1​g(n)≤f(n)≤c2​g(n)}为g(n)的同阶函数集合。 那么如果f(n)∈Θ(g(n))f(n)\in\Theta(g(n))f(n)∈Θ(g(n))则称g(n)与f(n)同阶，记作f(n)=Θ(g(n))f(n)=\Theta(g(n))f(n)=Θ(g(n)) 题型 证真:把g(n)除过去考虑函数单调性。 证伪:反证，设定常数值，假设n0n_0n0​存在。 严 ...

第一次作业 1.证明定理1.2 设(S,∘)(S,\circ)(S,∘)是一个代数系，如果二元代数运算∘\circ∘适合交换率和结合律，则∀ai∈S,i=1,2,⋯ ,n,n个元素的乘积仅与这n个元素有关，但是与他们的次序无关\forall a_i\in S,i=1,2,\cdots,n,n个元素的乘积仅与这n个元素有关，但是与他们的次序无关∀ai​∈S,i=1,2,⋯,n,n个元素的乘积仅与这n个元素有关，但是与他们的次序无关 考虑到定理1.1已经证明了在这种情况下，该积结果与结合方式无关，下面证明结果与顺序也是无关的。 下面使用数学归纳法证明： 当n≤3n\le 3n≤3，根据交换率与结合律，结论显然成立。 假设对∀n<k\forall n<k∀n<k结论都成立，往证n=k+1也成立。 显然，乘积 Πi=1naki\Pi_{i=1}^n a_{k_i} Πi=1n​aki​​ 总可以拆分为 Πi=1n−1aki∘akn\Pi_{i=1}^{n-1} a_{k_i}\circ a_{k_n} Πi=1n−1​aki​​∘akn​​ 那么对于前n-1个数的乘积 ...

HIT-概率论B-笔记 概率 样本空间 实验结果总体。记作Ω\OmegaΩ，其元素记作ω\omegaω 事件 样本空间的特定子集，斜体大写字母表示。 概率测度 定义在Ω子集上的实函数，满足 P(Ω)=1 如果A⊂\subset⊂Ω，那么P(A)≥0 如果A、B不相交，P(A∪B)=P(A)+P(B) 条件概率 P(A|B)=P(AB)P(B)P\left( A \middle| B \right) = \frac{P(AB)}{P(B)} P(A∣B)=P(B)P(AB)​ 称为B发生条件下A发生的概率。 全概率定律 设B1,B2,B3,…,BnB_{1},B_{2},B_{3},\ldots,B_{n}B1​,B2​,B3​,…,Bn​满足⋃i=1nBi=Ω\bigcup_{i = 1}^{n}B_{i} = \Omega⋃i=1n​Bi​=Ω，且任意的两个BiB_{i}Bi​不相交，P(Bi)B_{i})Bi​)>0 那么，对于任意的A，P(A)=∑i=1nP(A|Bi)P(Bi)\sum_{i = 1}^{n}{P\left( A \middl ...

深入理解计算机系统-笔记 信息的表示与处理 信息储存 大小端序 x86 x64采取小端序，低字节存放低位。 常见的ARM采取大端序，低字节存放高位。 整数表示 无符号 x=∑i=0w−1(xi2i)x=\sum_{i=0}^{w-1}(x_i2^i) x=i=0∑w−1​(xi​2i) 有符号(补码) x=−xw−12w−1+∑i=0w−2(xi2i)x=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}(x_i2^i) x=−xw−1​2w−1+i=0∑w−2​(xi​2i) 有无符号转换 1int x; (unsigned)x={xx≥0x+2wx<0(unsigned)x=\begin{cases} x& x\ge0\\ x+2^w& x<0 \end{cases} (unsigned)x={xx+2w​x≥0x<0​ IEEE浮点数 float=1Sign+9Exp+23Frac double=1Sign+11Exp+52Frac V=(−1)s×M×2EV=(-1)^s\times M\times 2^E V ...