计算机基础
CPU
运算器: 运算相关
算术逻辑单元ALU: 在控制器的控制下完成各种算术运算和逻辑运算
累加寄存器AC: 通用寄存器. 为ALU提供一个工作区, 用于暂存运算数据
数据缓冲器DR: CPU与外部设备速度缓冲
状态条件寄存器PSW: 运算过程的状态和控制标记
控制器: 指令执行相关
指令寄存器IR: 保存正在执行的指令
程序计数器PC: 存储下一条指令地址, 计算过程地址保留
地址寄存器AR: 用来保存指令所访问的内存单元地址, CPU与内存速度缓冲
指令译码器ID: 解释指令操作码
寻址
立即寻址: 操作数在指令
寄存器寻址: 操作数在寄存器
直接寻址: 操作数在内存
寄存器间接: 操作数在内存, 地址在寄存器
校验码
- 海明码 n位数 k校验位: 2^校 >= 位 + 1 + 校
- 海明码 即可检错又可纠错.
流水线
- 流水线总时间: 第一条完整时间 + (n-1) * 最长步骤时间
- 加速比: 不采用流水线时间 / 采用流水线时间 (采用流水线工作才有加速)
- 操作周期: 最长步骤时间
- 吞吐率: n/流水线总时间
存储器
速度快 -> 慢: 【通用寄存器 - cache - 内存 - 硬盘】
中断
- 中断向量: 提供中断服务程序的入口地址
- 中断响应时间: 发出中断请求 -> 进入中断服务程序
- 保存现场: 返回继续执行源程序
I/O 控制方式
i/o 中断 cpu可屏蔽
- 程序查询 cpu 内存缓存
- cpu与外设【串行】工作, cpu轮询,【cpu利用率低】
- 一次读写一个字
- 往主存【cpu写数据】
- 中断驱动 键盘鼠标:插入时, cpu卡一下. 产生数据少, 需要时时响应
- cpu与外设【并行】工作, 外设通知cpu, 【cpu利用率高】
- 一次读写一个字
- 往主存【cpu写数据】(cpu暂停 干预过程)
- 直接存储器 【DMA】硬盘网卡
- cpu与外设【并行】工作, 外设开始和结束中断cpu, 【cpu利用率高】
- 一次读写一块
- 往主存【外设写数据】, 不需要cpu干预
- 占用总线资源
总线
分类: 数据总线 地址总线 控制总线
常见总线
- PCI, 并行内总线
- SASI, 并行外总线
- 字长 -> 数据总线和地址总线 宽度
- 总线结构 减少线数量
- 带宽: 频率 * (单位时钟的字)
加密与认证
窃听 篡改 假冒 否认
加密
- 对称加密
- 加密解密同【一把密钥】. 密钥不好分发
- 速度快, 适合大量明文
- 非对称加密
- 加密解密不同密钥. 【公钥私钥2把】. 公钥和私钥对同一消息加密结果一致.
- 公钥加密 用 私钥解密
- 私钥加密 用 公钥解密
- 发送的时候 用对方的公钥加密 这样只有对方收到能解密.
- 混合加密
- 用对方的公钥加密对称的密钥, 再用对称的密钥对信息做对称加密. 解决密钥分发问题.
认证
解决三方也知道对方的公钥, 进而篡改的问题
- 摘要
- 发送方把【明文hash】得到摘要一起发送
- 接收方把解密后明文也hash再对比是否一致
- 签名:
- 发送方用私钥对摘要进行加密, 得到【数字签名】与密文一起发送
- 接收方用对方公钥对数字签名进行解密. 验证成功则消息没有被假冒.
- 数字证书:
- 解决公钥传输时被篡改的问题
- 公钥向CA注册, CA私钥加密得到数字证书
可靠度公式
- 串联: R相乘
- 并联: 1-(1-R1)(1-R2)…(1-RN)
- 组合部件: 先算并联 再相乘计算并联
R -> 2R并 -> 2R并
R * (1- (1 - R)(1 - R)) * (1 - (1 - R)(1 - R))
杂题汇总
- 汇编程序编码, 可访问【指令寄存器】
- 最大执行指令字长 -> 指令寄存器位数
逻辑运算
0:假 1:真
- 与: 存在 0 则为 0 (女: 有点假 就为假)
- 或: 存在 1 则为 1 (豁: 有点真 就为真)
- 同或: 相同为 1, 不同为 0 (同真)
- 异或: 相同为 0, 不同为 1 (异真)
攻击
- 主动攻击: 重放, ip地址欺骗, 拒绝服务, 修改数据
- 被动攻击: 流量分析, 会话拦截
VLIW: 超长指令字
位运算
10 左移1位 10[0] 末尾补零
21 变成 421 相当于*2
cpu区分指令和数据
cpu 根据时钟信号操作 不同阶段做不同的事
CPI 每条指令的时钟周期
- 平均CPI 比例*CPI相加
- 计算机主频 G->M换算是 /10^3
程序设计语言
编译方式
- 编译方式: 源程序 -> 词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 代码优化 -> 目标代码生成
- 解释方式: 源程序 -> 词法分析 -> 语法分析 -> 语义分析
- 前3个必须且顺序固定
- 编译方式 中间代码与代码优化可以省略 (c语言和java区别)
符号表(关键字/变量名/函数名/类名)
- 不断收集, 记录和使用源程序的符号相关类型和特征, 存入符号表.
- 记录各字符的必要信息, 辅助语义检查和代码生成
编译过程
- 词法分析: 根据语言的符号表规定来识别. 【源程序】 -> 【记号流】. 分析【字符和符号】是否符合字符词法规定
- 语法分析: 【记号流】 -> 【语法树】(分析树). 【分支结构, 语法定义】是否正确, 判断【结构】是否合理, 变量是否声明, 括号是否匹配
- 语义分析: 分析【静态语义】和【动态语义】. 比如【类型】, 直接除0, 赋值类型. 动态语法, 表达式. 赋值除0
- 目标代码生成: 与具体机器密切相关. 寄存器分配在代码生成阶段.
中间代码
- 分类: 后缀式 三地址码 三元式 四元式 树(图) | 三地址后缀树4元3
- 中间代码 与机器无关 可以跨平台
正则表达式
- | 选择: 多选一
- 闭包: 出现0次或多次, 每次结果不定
- () 组成单位
有限自动机
字符串从左往右识别, 都符合自动的规定, 并回到终态(双圈)才合法.
- 词法分析的工具. 用于识别正规集
- 符号”E”表示链接, 可以直接过去
- 初态和终态为同一个时可以识别空串
- 不确定的自动机: 当识别一个字符的是否有多个转移(既能自己转圈, 又能转移他处)
- 先看自己转圈 在看开头和结尾
上下文无关文法
- 开始符号 -> 产生式集合 -> 非终结符号 -> 终结符号
- 通过文法 构造选项.
中缀后缀表达式
- 后缀(逆(根在后)波兰式 后序遍历 左右根) -> 中缀: 算术优先级依次替换 ab? -> a?b
- 算式(简单算术 中缀 左根右) -> 后缀: 算术优先级依次替换, a?b -> ab?
- 对应树: 从顶出发, 依次替换每个节点
杂题
- 脚本语言: 动态语言
- 高级语言中 变量为逻辑地址, 运行时映射为物理地址
- 全局变量在静态数据区
- 自上而下语法分析法: 递归下降分析法,预测分析法
- 自下而上语法分析法: 算符优先分析法, LR分析法, 移进-归约分析法
- 语法指导翻译: 静态语义分析
- 程序执行: 栈区函数调用和返回由系统管理. 堆区需要申请释放
- java: 采用即时编译(jvm实时优化) + new对象在堆中分配
- python: 元祖(tuple) 不可变, 集合(set) 去重
数据结构
时间复杂度 执行次数与总次数关系
对数: a^x = b -> x = logab
- 加法规则: 多项相加, 只保留最高阶, 并将最高阶系数化为1
- 乘法规则: 多项相乘, 并将系数化为1. 只关心数量级.
- 常数阶: 行数固定, 效率最高 -> O(1)
- 对数阶: 特殊2循环 变量做 i = i * 2 计算 到 n -> O(log2n)
- 线性阶: 普通循环 从 i 到 n -> O(n)
- 线性对数阶: 双循环 外层普通循环, 内层对数循环 -> nlog2n
- 平方阶: 双层普通循环 -> O(n^2)
- 立方阶: 3层普通循环 -> O(n^3)
- 指数阶: -> O(2^n)
- 阶乘阶: -> O(n!)
- n的方阶: -> O(n^n)
空间复杂度 执行次数与定义变量所占内存关系
- 也是大O表示法.
- 定义变量所在空间
递归式
- 等差求解: (n + 1) * n / 2
- 问题规模增加16倍 -> n*16
两个定理求时间复杂度
T(n) = aT(n/b) + f(n) : ab是常数, f(n)是函数
- 常数e>0, 有 f(n) = O(n^logba) -> T(n) = O(n^logba)
- 若 f(n) = O(n^logba * lg^k * n) -> T(n) = O(nlog^ba * lg^k+1 * n)
线性表 顺序结构和链式结构
- 插入一个元素的概率: n/2
- 删除一个元素的概率: (n-1)/2
- 平均时间复杂度都为 O(n)
- 只有顺序结构查找是O(1), 其他的查询,插入,删除都是O(n)
- 顺序结构, 删除需要移动元素. 链表结构, 删除元素, 只需删除指针
栈
- top[1] 指向下一个元素位置
队列
- 头指针: 直接给元素标注容量地址. 然后带入选项. 头 = (尾地址-长度+1+容量)%容量
知识产权
著作权
- 工业产权: 专业, 商标
- 著作权: 人身权包括: 发表权(死后50年), 署名权, 修改权, 完整权..其他都为财产权
- 地域性: 只在本国保护. 外国在外国可以侵权, 咱也可以侵权.
软件著作权
- <<著作权法>> + <<计算机软件保护条例>>(国务院)
- 著作权客体: 程序(源码和程序) + 文档(设计说明, 流程图, 手册), 开发完成即保护. 保护50年
- 只有署名权永久, 其他的都消失.
- 软件著作权属于开发者
著作权归属
职务作品
- 职务作品著作权归公司, 署名权可以共享个人
- 用了单位的设备, 不能属于个人
委托开发
- 有合同按合同, 无合同归开发方
- 原则上归公司, 有特别约定时, 按约定
侵权
专利权
- 先申请先得, 同一天申请需要协商
- 商标权注册管10年, 无限续杯. 专利权20年实用+外观10年. 著作权50年.
- 商业秘密公开即失效
- 公众使用的产品
商标权
- 商标注册: 如果同时申请, 看谁先使用
- 同天申请, 抽签
独家许可使用
买了原件 拥有所有权+展览权
烟草制品必须注册商标
面向对象
- 消息: 对象直接通信
- 状态 = 属性
- 多重继承 -> 钻石问题(二义问题). bc类都继承a类,并重写方法. d再同时继承bc类, 调用该方法
- 多态分类: 通用多态 = 参数多态 + 包含多态 (最纯 + 包含子类型)
- 多态分类: 特定多态 = 过载多态 + 强制多态 (过载多态: 同个名字在上下文含义不同)
- 多态由继承机制绑定
设计原则
- 单一原则: 类仅有一个引起变化的原因
- 开放-封闭: 扩展开放, 修改关闭
- 里氏替换: 父类出现的地方, 可以用子类替换
- 依赖倒置: 依赖抽象. 不依赖具体. 高层 !-> 低层.
- 接口分离: 依赖抽象, 不依赖具体
- 共同重用: 重用包中类, 需要重用包所有
- 共同封闭: 对包产生影响, 影响包所有
对象分析 -> 对象设计 -> 程序设计 -> 测试
分析
- 分析问题域 + 系统责任
- 侧重理解问题 描述软件做什么 理解解决方案
- 步骤: 确定问题域 -> 认定对象 -> 组织对象 -> 描述关系 -> 确定操作 -> 定义内部 (认定组织时, 拉拢关系, 确定操作后, 打入内部)
- 领域类模型: 属性 + 操作 + 关联
UML
分类
- 结构事物: 类, 接口, 协作, 用例, 主动类, 构件, 制品, 结点
- 行为事物: 消息, 状态, 动作
- 注释事物: 解释
- 分组事物: 组织部分, 包
关系
- 关联 【实线】: 结构关系, 整体和部分关系, 不同角色标识任意关联
聚合【实线 白菱形】: 整体消失了, 部分仍然存在
组合【实线 黑菱形】: 整体消失了, 部分也消失. (组合消失) - 依赖 【虚线 黑三角】: 一个事物发生变化 -> 另个事物. 使用其他类全局对象.
- 泛化 【实线 白三角】: 特殊, 一般. 子类父类关系.
- 实现 【虚线 白三角】
- 多对多的时候 需要创建新类表示关系
UML图
建模对象: 系统词汇, 简单协作, 逻辑数据库
- 类图: 最常见, 类接口关系图, 属性方法 +表示public -表示private #表示protected ~表示包
- 对象图: 对象间关系. 【对象:类】
- 用例图: (小人的操作)客户【人/物/硬件】与用例【功能 -> 事件】关系. 包含, 扩展: 用例间 泛化: 客户间. 用例间
- 序列图 -> 交互图: 强调顺序 返回消息【虚线】 【指向箭头】表示需要实现方法
- 通信图|协作图 -> 交互图: 强调对象 【对象:类】
- 状态图: 一个对象在多个用例的行为. 超状态:包含多个状态, 活动可以在状态内执行, 也可在转换时执行. 事件触发转换, 不是触发状态. 反应性对象建模. 每个箭头有个事件.
- 活动图: 特殊状态图. 一个活动->另一个活动.
- 构件图: (组件图)有电路标志. 供接口半圆(事半.功倍), 依赖○需接口
- 部署图: 物理建模, 数据库/服务器/浏览器. 实施阶段使用.
静态建模: 类图/对象图/用例图 | 固定的成员 代码/文档给自己看
动态建模: 序列图(顺序,时序)/通信图(协作图)/状态图/活动图 | 调用相关活动状态 给三方看
物理建模: 构件图(组件图)/部署图 :物理相关 给实施看
交互图: 序列图(顺序,时序)/通信图 给三方看
异步调用: 箭头有去无回
用例图
包含：—<
扩展：—<
泛化：实线+△ 子用例将继承父用例的所有结构、行为和关系。子用例可以使用父用例的一段行为，也可以重载它。父用例通常是抽象的。比如订票 可以分为电话订票和网上订票
设计模式
类
创建: Factory Method【工厂方法】
结构: Adapter【适配器】
行为: Interpreter【解释器】Template Method【模板方法】
对象
创建: Abstract Factory【抽象工厂】 Builder【生成器】 Prototype【原型】 Singleton【单例】
结构: Adapter【适配器】 Bridge【桥接】 Composite【组合】Decorator【装饰】Facade【外观】Flyweight【享元】Proxy【代理】
行为: Chain of Responsibility【责任链】 Command【命令】 Iterator【迭代器】 Mediator【中介者】 Observer【备忘录】 State【状态】 Strategy【策略】 Visitor【访问者】
创建模式 5 与对象创建相关
工厂方法
- 意图: 定义一个接口, 让子类决定实例化哪个类, 使有一个类的实例化【延迟】到子类
- 适用: 当类不知道必须创建的对象的类. 当一个类希望由他【子类】来指定创建对象
抽象工厂
- 意图: 定义一个创建【很多】相关依赖对象的接口. 无需指定具体的类
- 适用: 一个系统独立于产品创建/组合/表示. 又【多个产品】系列的一个来配置. 强调系列相关的对象设计. 提供一个类库, 只想显示他们的接口.
生成器
- 意图: 复杂对象的构建和表示分离. 使【相同过程创建不同结果】
- 试用: 创建复杂对象的算法独立于对象组成以及装配. 构造必须允许被构造对象有不同表示
原型
- 意图: 原型对象指定创建对象种类, 通过【复制】这些原型创建新的对象
- 适用: 一个系统独立于产品创建/构成/表示,
单例 | 私有构造方法, 静态返回实例
- 写法: 之所以可以new 对象, 是因为类中默认提供无参构造方法, 改【构造方法】为private, 再新增一个静态方法 getInstance 返回静态对象
- 意图: 保证类仅有一个实例, 提供【全局唯一】访问点
- 适用: 类有且仅有一个实例. 通过子类化可扩展, 客户无需修改代码即可使用扩展实例
结构模式 7 处理类或对象的组合
适配器 | 子类调其他类
- 写法: 新增一个USB的子类Adapter, 子类引用TypeC对象, 子类重写USB方法直接调TypeC方法. Usb use = new Adapter()
- 意图: 将一个接口转换成另一个接口. 是原本【不兼容】的接口和类一起工作
桥接
- 写法: 抽象产品类, 依赖颜色接口, 定义抽象公共方法调颜色接口的打印方法. 产品A extends 产品类, 通过set不同颜色对象. 即可打印不同颜色实现类的方法.
- 意图: 将【抽象部分】与【实现部分】分离, 使独立变化.
- 适用: 不希望抽象与实现绑定, 【不固定】希望运行时切换实现部分. 类的抽象和实现通过生成子类的方法扩充. 对抽象的实现部分修改不对客户影响. 想在多个对象共享实现.
组合
- 写法: 定义抽象文件类, 抽象新增/删除方法. 文件夹类继承抽象类, 可以实现方法. 文件类继承抽象文件类, return 实现方法
- 意图: 讲对象组合成树形结构, 表示【部分-整体】, 整体定义一堆组合方法, 根据情况部分实现, 使客户对象打印对象和组合关系具有一致性
装饰
- 写法: 抽象人类的子类是学生类, 新增抽象装饰类继承人类(抽象类继承不用实现人类动作)并引用人类, 通过构造函数赋值, 装饰类子类实现动作时先调人类动作, 再自定义动作. 人类 = new 学生 学生=new 装饰(学生)
- 意图: 动态的给一个对象加一些【额外的职责】【动态添加】
- 适用: 以动态/透明的方式诶单个对象添加职责. 处理可以撤销的职责
外观
- 意图: 为复杂子系统一组接口提供一致界面, 【一个顶级父类】
享元(对象)
- 意图: 运用共享技术有效支持大量【细粒度】的对象
- 适用: 大量对象, 造成很大的存储开销
代理(中介)
- 写法: 定义一个接口方法. 子类实现方法. 代理类也实现并执行动作, 并引用子类对象, 执行动作前后都可以调用原子类方法.
- 意图: 为其他对象提供一种代理, 【控制对象的访问】
行为模式 11 对类或对象怎样交互和分配职责
责任链
- 写法: 抽象类中, 引用自己作为next, 重写动作, 执行动作后调用next.动作
- 意图: 多个对象【依次处理】请求. 避免请求和响应耦合.
- 适用: 多个对象处理统一请求. 运行时决定哪个对象处理. 不明确接收者. 【动态指定】
命令
- 写法: 电视类存在开关机2个动作. 定义接口, 实现对象引用电视类, 重新父类时调用电视动作.
- 意图: 请求封装成对象, 用不同请求对客户【参数化】; 对请求排队或记录日志, 支持可撤销
解释器
- 意图: 给定语言, 定义文法的一种表示. 并定义一个解释器. 用来表示语言的句子
迭代器
- 意图: 提供一个方法【顺序访问】一个【聚合对象list】的各元素, 且不需要暴露对象的内部表示.
中介者
- 意图: 中介对象【封装一系列对象交互】
- 适用: 一组对象一组定义良好但复杂的方式通信, 产生依赖关系混乱. 一个对象引用其他很多对象并直接与这对象同学. 定制一个分布在多个类的行为, 又不想太多子类
备忘录
- 意图: 不破坏封装的前提下, 捕获对象内部的状态. 用于恢复到原先状态
观察者
- 意图: 定义对象间一对多的依赖关系. 当对象的状态发生修改时, 所有依赖他的对象都得到通知并自动更新
- 当一个抽象模型有2个方面, 一个依赖另外一个, 将两者封装在独立的对象中, 使他们可以独立改变和复用. 当一个对象改变需要通知其他对象, 且不知道有多少时. 不希望通知的对象耦合
状态
- 意图: 对象在【内部状态】改变时改变他的行为.
- 适用: 行为决定状态, 运行时状态控制行为. 根据自身情况将对象状态作为一个对象, 不依赖其他对象独立变化
策略
- 意图: 定义一系列算法. 把他们【封装起来. 可以相互替换】.
- 适用: 相关类仅是行为有异, 提供多个行为的一个类来响应.
模板方法
- 意图: 定义操作的算法骨架, 使子类可以不改变算法结构即可重写算法步骤
- 适用: 一次性实现算法不变的部分, 可变行为留给子类. 公共部分提取出来. 控制子类扩展.
访问者
- 意图: 表示一个作用于【对象结构】中各元素的操作. 不改变各元素的前提下定义新操作
- 适用: 一个对接结构包含很多对象. 有不同的接口. 用户想对对象实施依赖具体类的操作. 【accept】
面向对象
多态
- 参数多态: 应用广泛, 最纯
- 包含多态: 同样的操作可用于一个类型和子类型. 需要进行运行时类型检查
- 强制多态: 把对象类型强行加以变化, 符合函数或操作要求.
- 过载多态: 同一个名在不同上下文有不同类型
类
- 实体类: 现实世界真实实体, 人/物
- 接口(边界)类: 与实体类交互.
- 控制类: 控制活动流
- 泛化: 一个类与一个或多个【细化类】关系, 表达【一般-特殊】关系
- 聚集: 较大整体包含一个或多个【部分类】
- 组合: 整体不存在, 部分也不出存在
对象
- 状态: 包括所有属性
- 行为: 是根据状改变做出的反应.
- 操作: 类提供给他的对象的服务
算法
- 选择: 左边开始, 选择剩下的队伍中最小的元素, 选出来记录坐标 , 然后赋值到次位 【时间n^2 空间n1】 【不稳定】 稳定是指相对位置, 如果 441 -> 144 , 左边的4移到右边去了
- 冒泡: 左边开始, 依次遍历, 如果左边>右边, 则交换位置. 第一轮选出最大的 【时间n^2 空间n1】 【稳定】
- 插入: 第2位作为基准, 与前1位比较, 第3位与前位循环比较, 找到正确位置 【时间n^2 空间n1】 【稳定】
- 快速: 【时间nlogn 空间n】不稳定
- 归并: 取中点, 分为两段, 重复步骤拆至子数组长度为1, 再合并. 【时间nlogn 空间n】【稳定】
- 动态规划: 将一个问题分解成小问题, 并记录最优解. 从底到顶, 解决小问题开始
- 贪心算法: 每一步都是当前最优解, 比如找钱问题, 需要138, 会先选一张100, 再选50…
- 回溯算法: 穷举法. 记录所有的解
- 分治算法: 分解成小问题. 比如归并
