Skip to main content
  1. Posts/

华科软院计组概念复习

·6 mins
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

noip初赛加强版既视感…

自己手动整理的

第二章 机器数:正负符号数码化后的数据称为机器数。 BCD码:用二进制编码的十进制数称为bcd码。 有权码:每位二进制数码元都有确定权值的编码。 校验码:为了发现或纠正数据传送中出现错误的编码。 浮点数的精度由尾数的位数决定。 第三章 溢出:运算结果超出了机器能表示的数据范围。 溢出的特征:结果的符号与操作数的符号不同。 变形补码:两个符号位的补码(用来检测溢出,00,11说明没有溢出,10,01说明有溢出) 对阶:使阶码相等的过程(原则是小阶码向大阶码看齐) 结果规格化:将非规格化数处理为规格化形式。

*根据指令中所含操作数地址的数量可分为(4种): 三地址指令 双地址指令 单地址指令 零地址指令

第四章 存储位:存储器记忆信息中的最小单元。 地址:每个存储单元的编号。 主存储器的技术指标:存储容量,存取时间,存储周期,存储器带宽。(两类:存取速度和存储容量) 存储体:存储器中的记忆部件,通常由大量的存储单元组成。 MROM:掩膜型只读存储器。 PROM:可编程只读存储器。 EPROM:可擦写可编程只读存储器。 EEPROM:电可擦除可编程只读存储器(扩展) CACHE对程序员是透明的。 内存:Cache 与主存合称为内存。 全相联映射:将主存分成若干块,主存的任意一快可定位于Cache的任意一块中。 组相联映射:将主存分成若干区,每一区包括若干组,每一组包含若干块;将Cache也分成若干组,每组若干块。 组之间用直接映射方式,组内的块采用全相联映射方式 替换策略:最不经常使用(LFU,近期最少使用(LRU,随机替换 写操作策略:全写法(命中时既写入Cache,又写入主存) 写回法(命中时只写入Cache,不写入主存) 写一次法(第一次采取全写法,之后采取写回法) 硬盘存储器的主要指标包括存储密度、存储容量、存取时间及数据传输率。 平均存取时间:从发出读/写命令后到开始从盘片表面读出或写入信息所需要的平均时间。 平均存取时间=平均寻道时间+平均等待时间。

数据传输率:存储器在单位时间向主机传送数据的字节数。

*DRAM刷新方式: 集中刷新方式 分散刷新方式 异步刷新方式 第五章 机器指令:计算机能够直接识别,执行的指令称为机器指令,简称指令。 指令集;一台计算机中所能执行的指令的集合称为指令集(指令系统) 指令包含两种信息:指令和数据。 寻址方式:根据指令中的信息寻找物理地址的方式。 寻址方式包含指令寻址方式和操作数寻址方式两大类。 指令寻址方式:顺序寻址方式和跳跃寻址方式。 操作数寻址方式:直接寻址,寄存器相对寻址,寄存器间接寻址,基指+变址等 为什么多种寻址方式:效率和方便性上达到平衡,满足各种需要。 RISC指令系统特点: 指令系统简单,指令条数少; 寻址方式少; 指令格式简单,指令长度固定 cpu中设置大量寄存器以减少对存储器的访问。

**cache的工作原理: 当cpu访问的内存地址给出后,该地址先与相连存储器中存放的地址比较, 判定要访问的字是否在Cache中,在则访问Cache,称为命中; 不在则访问主存,称为未命中。 命中时需要先产生访问Cache的地址 未命中时根据cpu给出的地址访问主存。 第六章 中央控制器的主要功能: 指令序列控制 操作控制 时间控制

程序计数器(PC):给出下条指令在存储器中的地址。 指令寄存器(IR):用来保存当前正在执行的指令。 地址寄存器(AR):用来保存当前所访问的内存地址。 指令功能译码器(ID):对当前要执行的指令进行译码分析并指出指令功能。 操作控制器(OC):产生控制信号的功能部件。 根据设计方式的不同,OC分为硬布线控制器和微程序控制器。 硬布线控制器的核心部件:操作控制器。 时序产生器(TG):用来产生时序信号。

控制方式: 同步控制方式:选取执行部件中最长操作时间作为统一的时间标准。 异步控制方式:每条指令需要多少时间就给多少时间。 联合控制方式:同步异步相结合。 微程序控制器:用微程序方式设计的操作控制器。 微命令:在微程序控制的计算器中,打开或关闭控制门的控制信号。 微操作:微命令控制执行部件进行的操作。 *微(指令)周期:从存储器取出并执行一条微指令需要的时间。 微命令的表示: 直接表示法 编码表示法 混合表示法(前两种混合用) 微命令分类: 互斥性微命令:某时刻不能同时给出。 相容性微命令:某时刻可以同时给出。

微指令格式: 水平型微指令(直接表示法) 垂直型微指令(编码表示法)

微地址的形成: 下址字段法 计数器法

**微程序控制器的设计思想: 将指令系统中所有指令功能实现所需要的控制信号以微指令为单位存储,每条机器指令对应一段微程序。 **微程序控制器的设计“采用了存储技术和程序设计技术。 流水CPU:采用流水线技术对指令和数据进行处理的CPU 并行处理技术(三种): 时间并行 空间并行 时间-空间并行 流水线分类(3类): 指令流水线 运算流水线 处理器流水线 RISC的3个要素: 有限的指令集 大量的寄存器 强调对指令流水线的优化。

第七章 *总线:计算机系统内部的各个设备或部件间相互通信的公共通路。 总线分类:地址线(单向线),数据线(双向线),控制线(单向线)。 总线结构:单总线结构,双总线结构,三总线结构等(越来越好 *总线的仲裁方式解决总线的使用权问题。 总线的仲裁方式:集中仲裁方式(主流)(总线控制逻辑集中在一起),分布仲裁方式(总线控制逻辑分散在各个部件) 集中仲裁方式分类: 串行链接方式:从头开始一个一个问 定时查询方式:从某一个开始一个一个问 独立请求方式:非常快,优先次序控制灵活,n条BR,n条BG 总线通信方式: 同步通信:无应答通信,有同步脉冲。 异步通信:应答通信,“握手”,“当慢则慢,当快则快” 总线信息传送方式: 串行传送:一位一位传送,就一条传输线,慢。 并行传送:n位一起传送,n条传输线,快。 串并行传送:分组,组内并行,组间串行。 总线复用:地址线和数据线不严格区分,增加效率。 第八章不考。。。

第九章

CPU与外部设备交换信息的方式(三种): 程序查询方式 程序中断方式 直接存储器存取控制方式(DMA) 中断识别的方法(三种): 程序识别 单线查询识别 中断向量法识别

多模块存储器基本结构

硬布线控制器基本结构[

微程序控制器的组成

独立请求方式[

定时查询方式[

串行链接方式

Related

codeforces 660 C. Hard Process (ruler)

·1 min
cf660C solution:ruler.1A 1/* *********************************************** 2Author :111qqz 3Created Time :2016年06月08日 星期三 23时43分18秒 4File Name :code/cf/problem/660C.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=3E5+7; 34int n,k; 35int sum[N],a[N]; 36 37void ruler() 38{ 39 int head = 1; 40 int tail = 1; 41 int l,r; 42 int res = -1; 43 int cnt = 0 ; 44 45 while (tail<=n) 46 { 47 while (a[tail]==1) tail++; 48// cout<<"head:"<<head<<" tail:"<<tail<<endl; 49 if (a[tail]==0&&tail<=n) cnt++; 50 51 while (sum[tail]-sum[head-1]<=k&&tail<=n) tail++; 52// cout<<"head:"<<head<<"tail:"<<tail<<endl; 53 if (tail-head>res) 54 { 55 res = tail-head; 56 // cout<<"res:"<<res<<endl; 57 l = head; 58 r = tail-1; 59 } 60 61 while (head<=tail&&sum[tail]-sum[head-1]>k) head++; 62// cout<<"head::"<<head<<" tail:"<<tail<<endl; 63 if (tail<=n&&tail-head+1>res) 64 { 65 res = tail-head+1; 66 l = head; 67 r = tail; 68 } 69 70 71 } 72 73 74 for ( int i = l ; i <= r ; i++) a[i] = 1; 75 76 cout<<res<<endl; 77 for ( int i = 1 ; i <= n ; i++) cout<<a[i]<<" "; 78} 79int main() 80{ 81 #ifndef ONLINE_JUDGE 82 freopen("code/in.txt","r",stdin); 83 #endif 84 85 cin>>n>>k; 86 87 sum[0] = 0; 88 for ( int i = 1; i <= n ; i++) 89 { 90 scanf("%d",&a[i]); 91 sum[i] = sum[i-1] +(1-a[i]); 92 } 93 94 ruler(); 95 96 97 #ifndef ONLINE_JUDGE 98 fclose(stdin); 99 #endif 100 return 0; 101}

(转)树形dp题目集

·4 mins
树,一种十分优美的数据结构,因为它本身就具有的递归性,所以它和子树见能相互传递很多信息,还因为它作为被限制的图在上面可进行的操作更多,所以各种用于不同地方的树都出现了,二叉树、三叉树、静态搜索树、AVL树,线段树、SPLAY树,后缀树等等.. 枚举那么多种数据结构只是想说树方面的内容相当多,本专辑只针对在树上的动态规划,即树形DP.做树形DP一般步骤是先将树转换为有根树,然后在树上进行深搜操作,从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分,这个也没一般性的东西可讲,因为每道题目要求做的事都不尽相同。

KM算法总结

·1 min
km算法我的理解 刷了不到20道题。。。回来总结一发。。