Mengzelev's Blog

Mengzelev's Blog

Do not touch fish!

os期中复习
应用眼中的OS 操作系统一方面需要提供程序的执行的环境和相应的资源,还要提供和操作系统世界中其他对象交互的方法和约定 并发共享内存多线程 并发定义:一个程序、算法或问题的不同部分乱序或偏序执行而不影响最终结果的能力 程序经历了什么? 编译器优化$\to$顺序丧失 操作系统中断,多处理器、缓存(硬件)$\to$原子性)(all or nothing)丧失 缓存,乱序(硬件)$\to$可见性丧失 互斥评估一把锁的基本准则 所能够完成基本任务:提供互斥性质 锁的分配是公平的:不会有现成想要上锁却永远得不到它 锁的高效的:无等待时性能?多线程同时等待时性能?多CPU每个核的线程都要上锁...
问题求解学习笔记-密码算法
RSA公钥加密系统每个参与者都有一把公钥($P$)和密钥($S$) $\mathcal{D}$表示允许信息的集合,要求公钥与密钥指定一种从$\mathcal{D}$到自身的一一对应的函数。Alice的公钥函数$P_A()$和密钥函数$S_A()$都是$\mathcal{D}$的排列 系统中任何参与者的公钥与密钥都是匹配对,指定函数互为反函数,对任何消息$M\in \mathcal{D}$,有$$M=S_A(P_A(M))$$$$M=P_A(S_A(M))$$ 加密过程 Bob取得Alice的公钥$P_A$ Bob计算出相应与$M$的密文$C=P_A(M)$,并把$C$发送给Alice 当...
算法导论学习笔记-数论算法
输入规模和算数计算的代价给定$k$个整数输入$a_1,a_2,\cdots ,a_k$,如果算法可以在关于$\lg~a_1,\lg~a_2,\cdots ,\lg~a_k$的多项式时间内完成,即算法在关于二进制编码后的输入长度的多项式时间内完成,则称该算法为多项式时间算法 当输入很大时,基本运算也会变得耗时。两个$\beta$位整数相乘需要耗时$\Theta(\beta^2)$.一个$\beta$为整数除以另一个较短整数的商或余数需要耗时$\Theta(\beta^2)$ 基础数论概念整除性与约数你懂的 素数与合数你也懂的 除法定理、余数和等模定理31.1(除法定理): 对于任何整数$a...
问题求解学习笔记-数论基础
数学归纳法你都懂的 辗转相除法(Division Algorithm)定理2.9(辗转相除法): $a,b$为整数,满足$b>0$,则存在唯一的整数$q$和$r$使得$a=bq+r$,此处$0\le r<b$ $a\mid b$: $a$能整除$b$,$b$能被$a$整除 定理2.10: $a,b$为非零整数,则存在整数$r,s$使得gcd($a,b)=ar+bs$. $gcd(a,b)$是唯一的。但$r,s$不唯一 推论2.11: $a,b$为互质的整数,则存在整数$r,s$使得$ar+bs=1$【事实上是当且仅当的关系】 欧几里得算法(The Euclidean Algo...
算法导论学习笔记-字符串匹配
基本知识问题的形式化定义 文本是一个长度为$n$的数组$T[1,…n]$ 模式是一个长度为$m$的数组$P1,…m$ $P$和$T$的元素都是来自一个有限字母集$\Sigma$的字符 若$0\le s\le n-m$,且$T[s+1,…s+m]=P[1,…m]$,则称模式$P$在文本$T$中出现,且偏移为$s$(模式$P$在文本$T$中出现的位置是$s+1$开始的) 如果$P$在$T$中以偏移$s$出现,那么称$s$是有效偏移,否则是无效偏移 字符串匹配问题:找到所有的有效偏移 算法总运行时间=预处理时间+匹配时间 符号和术语 $\Sigma^*$: 包含所有有限长度的字符串的集合 ...
问求学习笔记-群同构基本定理与正规子群
同构(Isomorphisms)定义对两个群$(G,\cdot)$和$(H,\circ)$,若存在一个保群运算的双射$\phi:G\to H$,即对于任意$a,b\in G$$$\phi(a\cdot b)=\phi(a)\circ\phi(b)$$则称$G$和$H$同构(isomorphic),记作$G\cong H$. $\phi$称为同构函数(isomorphism)。 基本定理定理9.6: Let $\phi: G\to H$ be an isomorphism of two groups. Then the following statements are true. $\p...
问求学习笔记-置换群与拉格朗日定理
置换群(Permutation Group)定理5.1:The symmetric group on $n$ letters, $S_n$, is a group with $n!$ elements, wherethe binary operation is the composition of maps. 置换群(permutation group):所有排列的集合$S_n$的一个子集 Cycle NotationA permutation $\sigma\in S_X$ is a cycle of length $k$ if there exite elements $a_1,a_...
问求学习笔记-群论初步
由于接下来的书没有中文版了,因此笔记中英文都看心情 群整数等价类命题3.4:模运算下的整数等价类具有以下性质: 加法和乘法交换律 加法和乘法结合律 加法(0)与乘法(1)恒等式 乘法分配律 任意元素都存在加法逆元 $a$为非零整数,$gcd(a,n)=1$当且仅当$a$存在乘法逆元,即存在非零整数$b$,使得$ab\equiv 1(mod n)$ (虽然我觉得这玩意儿记了应该没什么卵用) 定义 二元运算(binary operation)或合成律(law of composition):a function $G\times G\to G$ that assigns to each ...
2019年寒假计划(flags)
美赛准备 MATLAB入门《MATLAB数学工具软件实例简明教程》 《MATLAB在数学建模中的应用》 研读优秀论文,总结模板 项目 学习Python 分析minilab的git log中的CE数据 HK学术竞赛 等打完美赛再来研究 番剧追番 多罗罗 灵能百分百第二季 关于我转生成为史莱姆的这档事 强风吹拂 不吉波普不笑 约定的梦幻岛 补番 战栗杀机 小林家的龙女仆 吉他 看B站教学视频
算法导论学习笔记-线性规划
知识背景 一个线性规划问题是一个线性函数最小化或最大化的问题,该线性函数服从一组有限个线性约束,分为最小化线性规划和最大化线性规划 可行解:所有满足约束条件的自变量的取值 可行区域:所有可行解在二维空间中构成的凸区域 目标函数:希望最大化的函数 目标值:目标函数在一个特定点上的值 最优解:所有目标值中最大的一个,其目标值为最优目标值 不可行的:一个线性规划没有可行解 无界的:一个线性规划有可行解但没有有限的最优目标值 标准型和松弛型标准型 所有的约束都是不等式 标准型=目标函数+约束+非负约束 重写为向量与矩阵的形式,可以用一个元组$(A,b,c)$来表示一个标准型的线性规划 ...
Mengzelev
Mengzelev
FRIENDS
Click here