HIT-离散数学-近世代数笔记
近世代数笔记
半群和幺半群
半群
设代数系(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, ...
HIT-算法设计与分析课后作业
算法设计与分析课后作业
第一讲[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 ...
HIT-算法设计与分析笔记
算法设计与分析笔记
第二讲
增长的阶
描述增长率:忽略低阶项,保留最高阶项,忽略常数。
增长函数
输入规模非常大。常见记号: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,c1g(n)≤f(n)≤c2g(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存在。
严 ...
HIT-离散数学-近世代数课后作业
第一次作业
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=1naki
总可以拆分为
Πi=1n−1aki∘akn\Pi_{i=1}^{n-1} a_{k_i}\circ a_{k_n}
Πi=1n−1aki∘akn
那么对于前n-1个数的乘积 ...
HIT2018级概率论B考前笔记
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=1nBi=Ω,且任意的两个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 ...
HIT-CSAPP2018级根据考试内容调整的考前笔记
深入理解计算机系统-笔记
信息的表示与处理
信息储存
大小端序
x86 x64采取小端序,低字节存放低位。
常见的ARM采取大端序,低字节存放高位。
整数表示
无符号
x=∑i=0w−1(xi2i)x=\sum_{i=0}^{w-1}(x_i2^i)
x=i=0∑w−1(xi2i)
有符号(补码)
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−12w−1+i=0∑w−2(xi2i)
有无符号转换
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+2wx≥0x<0
IEEE浮点数
float=1Sign+9Exp+23Frac
double=1Sign+11Exp+52Frac
V=(−1)s×M×2EV=(-1)^s\times M\times 2^E
V ...