什么是算法(Algorithm)?算法的性质是什么?算法与程序的区别?

1 什么是算法? 算法是指解决问题的一种方法或一个过程。 2 算法的性质 算法是若干指令的有穷序列,满足性质: (1)输入:有外部提供的量作为算法的输入。 (2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法的每条指令是清晰,无歧义的。 (4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。 3 什么是程序? 程序是算法用某种程序设计语言的具体实现。 4 程序与算法的区别 程序可以不满足算法的性质(4)。 例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。 操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止 0

Read More

CPU如何执行一个程序(一条指令)?取指—译码—执行—写回过程

简介 对于一个CPU来说,执行指令一般要经过四个流程: 1.取指 2.译码 3.执行 4.写回 1 取指 在此图中,有程序计数器(PC)、存储器地址寄存器(MAR)、存储器数据寄存器(MDR)、控制器(CU)、内存(Memory)五个组件。内存当前的指令为(ADD:R1,R2),内存地址为101。 程序计数器指向当前指令在主存的位置。即PC指向内存的101地址。PC所指向的内容会放到指令地址总线上,对指令启动读命令。在一条指令取出后,PC指针指向的地址会加1,即指向102地址。 控制器将PC中的指令地址通过内部总线传输到MAR中。 MAR存储了指令或数据的内存地址。MAR将控制指令传输到地址总线上。 控制单元通过MAR提供的地址,发送信号访问存储器并进行读操作。 存储器通过地址译码器查到存储地址为101的存储单元的内容(ADD:R1,R2),并将存储单元的内容传送到MDR中。 MDR中保存的数据通过内部总线传送给IR寄存器(指令寄存器)。 至此,取指令部分完成! 2 译码 MDR中保存的数据通过内部总线传送给IR寄存器。指令包含操作数和地址码两部分。 IR寄存器会分析出操作码部分和地址码部分。将操作码送入解码器,解析出ADD是加操作。

Read More

电路可满足性问题

【电路可满足性问题】 电路可满足性问题(Circuit satisfiability problem)描述为:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。如图5为电路可满足性问题的一个实例。 图5 电路可满足性问题 图中的左边,从上到下依次是或门、非门。图中的右边是与门。当1和2输入都为1,3输入为0的时候,输出为1。即这个电路是满足的。 0

Read More

难问题的部分分类

难问题的部分分类 1 包装问题 包装问题主要有独立集问题和集合包装问题。 (1)独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗? (2)集合包装问题:给定 n 个元素的集合 U , U 的子集 S_1,S_2,…,S_m 以及数 k , 问在这些子集中至少含有 k 个集合两两不相交? 2

Read More

三维匹配问题是NP完全的

【三维匹配问题】 给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合T \subseteq X \times Y \times Z,集合T的大小为m。 问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。 三维匹配问题其实是集合覆盖和集合包装问题的特例。 三维匹配问题是NP完全的 首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT\leq_p三维匹配证明。 【3-SAT\leq_p三维匹配证明】 考虑任意的一个3-SAT实例,有n个变量x_1,x_2,…,x_n和k个子句C_1,C_2,…,C_n。构造3DM实例X,Y,Z,T。 对于每一个变量,都有一个零件相对应。如图9所示。每个零件有Core(核心)元素、Tip(边梢)元素、Triple元组。每一个零件大大小为2k。k为子句的大小。\ 则,对于每一个变量x_i,建立: A_i={a_{i,1},a_{i,2},…,a_{i,2k}}。 B_i={b_{i,1},b_{i,2},…,b_{i,2k}}。 t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j}}。 构造的零件如图9所示。

Read More