For an algorithm, it is generally necessary to calculate its time complexity and space complexity to measure its efficiency. However,
Category: Courses
SAT and 3-SAT
【SAT Questions】 Call the Boolean satisfiability problem SAT: Given a set of clauses C_1,C_2,…,C_n on the set of variables X={{x_1,x_2,…,x_n}},
什么是算法（Algorithm）？算法的性质是什么？算法与程序的区别？
1 什么是算法？ 算法是指解决问题的一种方法或一个过程。 2 算法的性质 算法是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 3 什么是程序？ 程序是算法用某种程序设计语言的具体实现。 4 程序与算法的区别 程序可以不满足算法的性质(4)。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止 0
Orders of Growth（计算复杂度排行）
常见的时间复杂度从小到大的顺序依次是： Θ(lgn)，Θ(sqrt(n))，Θ(n)，Θ(nlgn)，Θ(n^2 )，Θ(n^3 )，Θ(2^n )，Θ(n!)。 0
Asymptotic Notation
1 How to measure the running speed of an algorithm? How to measure the running speed of an algorithm? What
Asymptotic Notation（渐进表示法、渐进分析）
1 How to measure the running speed of an algorithm?（如何衡量一个算法的运行速度？） How to measure the running speed of an algorithm? What
计算机是如何存储数据的？寄存器+内存
参考视频：https://www.youtube.com/watch?v=fpnE6UAfbtU&feature=youtu.be 图片是从视频中截取的，版权问题归 CrashCourse 作者。这里仅仅做学习使用。 （The images were captured from the video. The copyright is reserved for the CrashCourse authors. Here
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是加操作。
证明NPC问题的通用策略
证明NPC问题的通用策略 给定一个基本的问题X，证明其是NPC的基本策略是： （1）证明X是一个NP问题。 （2）选择一个已知的NPC问题Y。 （3）证明Y \leq_p X。 0
子集和问题是NP完全的
【子集和问题】 给定自然数w_1,w_2,…,w_n和目标值W，问{w_1,w_2,…,w_n}有一个子集加起来恰好等于W吗？ Ex: { 1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344 }, W = 3754. Yes. 1
三维匹配问题是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所示。